關於 GIN 的路由樹
2022-06-22 12:01:08
GIN 是一個 golang 常用的 Web 框架，它對 API 比較友好，原始碼註釋也很明確明確，使用起來快速靈活，還有極高的容錯率。標題中的路由我們可以簡單理解為在瀏覽器中輸入的頁面地址，而「樹」則是 一種優化的資料結構。 因為在 GIN 這個 Web 框架中的路由樹是字首樹，所以我們今天會圍繞字首樹來講解。
什麼是字首樹
字首樹其實就是 Tire 樹，是雜湊樹的變種，通常大家都叫它單詞查詢樹。字首樹多應用於統計，排序和儲存大量字串。因為字首樹能夠利用字串的公共字首減少查詢時間，最大限度地減少不必要的字串比較。所以字首樹也經常被搜尋引擎系統用於文字詞頻統計。字首樹擁有以下特點：
-
根節點不包含字元，其他節點都包含字元
-
每一層的節點內容不同
-
從根節點到某一個節點，路徑上經過的字元連線起來，為該節點對應的字串
-
每個節點的子節點通常有一個標誌位，用來標識單詞的結束
以小時候查新華字典為例，我們來直觀認識一下字首樹。相信大家都用過音序查字法這種查詢方式， 其操作內容如下：
-
讀準字音，根據該字音節確定應查什麼字母。
-
在「漢語拼音音節索引」中找到這一字母，在這一字母相應部分找到該字的音節，看清這個音節旁標明的頁碼。
-
按此頁碼翻開字典的正文，按四聲順序找出所要查的字。
這整個流程其實可以看做一個粗略的字首樹查詢流程，比方說要查詢成語「心想事成」中的「心想」兩字，在字典中即如下結構：
在查詢的過程中，我們根據首字母 x，找到 x 當中的 xi 這一共同部分，然後再根據不同的字母找到所對應的剩餘部分。放到字首樹查詢上，案例中的「心」對應 xi -> n，而「想」則對應 xi -> ang
GIN中的字首樹-緊湊字首樹
GIN 中的字首樹相比普通的字首樹減少了查詢的層級，比如說上方我們想查詢的「心想」其中 xi 做為共有的部分，其實可以被分配在同一層同一個節點當中而不是分為兩部分：
這樣的就是緊湊字首樹，同理如果我們有如下四個路由，他們所形成的緊湊字首樹就會是這個樣子：
r.GET("/", handle1)
r.GET("/product", handle2)
r.GET("/product/:id", handle3)
r.GET("/product/:name", handle4)
在節點中儲存資訊
通過上面的內容可以看出，GIN 中字首樹整條查詢的地址只需通過路由樹中每個節點的拼接即可獲得。那麼 GIN 是如何完成在這些節點的增加的呢，每個節點中又存放了什麼內容？這個問題我們可以通過 GIN 的原始碼得到答案。
首先 GIN 中常用的宣告路由的方式如下：
func main(){
r := gin.Default()
r.GET("/", func(context *gin.Context) {
context.JSON(200, gin.H{
"status":"ok",
})
})
r.Run()
}
// default會初始化一個engin範例
func Default() *Engine {
debugPrintWARNINGDefault()
engine := New()
engine.Use(Logger(), Recovery())
return engine
}
type Engine struct {
RouterGroup
// type RouterGroup struct {
// Handlers HandlersChain
// basePath string
// engine *Engine
// root bool
// }
// 小寫私有的，不開放
trees methodTrees
// ...
}
type methodTrees []methodTree
type methodTree struct {
method string
root *node
}
// trees 路由樹這一部分由一個帶有method 和root欄位的node列表維護
// 每個node代表了路由樹中的每一個節點
// node所具有的欄位內容如下
type node struct {
path string // 當前節點的絕對路徑
indices string // 快取下一節點的第一個字元 在遇到子節點為萬用字元型別的情況下,indices=''
// 預設是 false，當 children 是 萬用字元型別時，wildChild 為 true 即 indices=''
wildChild bool // 預設是 false，當 children 是 萬用字元型別時，wildChild 為 true
// 節點的型別，因為在萬用字元的場景下在查詢的時候需要特殊處理，
// 預設是static型別
// 根節點為 root型別
// 對於 path 包含冒號萬用字元的情況，nType 是 param 型別
// 對於包含 * 萬用字元的情況，nType 型別是 catchAll 型別
nType nodeType
// 代表了有幾條路由會經過此節點，用於在節點
priority uint32
// 子節點列表
children []*node // child nodes, at most 1 :param style node at the end of the array
handlers HandlersChain
// 是從 root 節點到當前節點的全部 path 部分；如果此節點為終結節點 handlers 為對應的處理鏈，否則為 nil；
// maxParams 是當前節點到各個葉子節點的包含的萬用字元的最大數量
fullPath string
}
// 具體節點型別如下
const (
static nodeType = iota // default， 靜態節點，普通匹配(/user)
root // 根節點 (/)
param // 引數節點(/user/:id)
catchAll // 通用匹配，匹配任意引數(*user)
)
新增路由則可以通過以下操作：
// 在建立路由的過程中， 每一個方法都會最終都會被解析後丟給handle函數去處理
func main(){
r := gin.Default()
r.GET("/", func(context *gin.Context) {
context.JSON(200, gin.H{
"status":"ok",
})
})
r.Run()
}
func (group *RouterGroup) GET(relativePath string, handlers ...HandlerFunc) IRoutes {
return group.handle(http.MethodGet, relativePath, handlers)
}
func (group *RouterGroup) POST(relativePath string, handlers ...HandlerFunc) IRoutes {
return group.handle(http.MethodPost, relativePath, handlers)
}
// handle函數中會將絕對路徑轉換為相對路徑
// 並將 請求方法、相對路徑、處理方法 傳給addRoute
func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
absolutePath := group.calculateAbsolutePath(relativePath)
handlers = group.combineHandlers(handlers)
group.engine.addRoute(httpMethod, absolutePath, handlers)
return group.returnObj()
}
// 路由的新增主要在addRoute這個函數中完成
func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
// 校驗
// 路徑必須以 / 開頭
// 請求方法不允許為空
// 處理方法不允許為空
assert1(path[0] == '/', "path must begin with '/'")
assert1(method != "", "HTTP method can not be empty")
assert1(len(handlers) > 0, "there must be at least one handler")
// 如果開啟了gin的debug模式，則對應處理
debugPrintRoute(method, path, handlers)
// 根據請求方式獲取對應的樹的根
// 每一個請求方法都有自己對應的一顆緊湊字首樹，這裡通過請求方法拿到最頂部的根
root := engine.trees.get(method)
// 如果根為空，則表示這是第一個路由，則自己建立一個以 / 為path的根節點
if root == nil {
// 如果沒有就建立
root = new(node)
root.fullPath = "/"
engine.trees = append(engine.trees, methodTree{method: method, root: root})
}
// 此處的path是子路由
// 以上內容是做了一層預校驗，避免書寫不規範導致的請求查詢不到
// 接下來是新增路由的正文
root.addRoute(path, handlers)
}
// addRoute adds a node with the given handle to the path.
// Not concurrency-safe! 並行不安全
func (n *node) addRoute(path string, handlers HandlersChain) {
fullPath := path
// 新增完成後，經過此節點的路由條數將會+1
n.priority++
// Empty tree
// 如果為空樹， 即只有一個根節點"/" 則插入一個子節點， 並將當前節點設定為root型別的節點
if len(n.path) == 0 && len(n.children) == 0 {
n.insertChild(path, fullPath, handlers)
n.nType = root
return
}
parentFullPathIndex := 0
walk:
for {
// Find the longest common prefix.
// This also implies that the common prefix contains no ':' or '*'
// since the existing key can't contain those chars.
// 找到最長的共有字首的長度 即到i位置 path[i] == n.path[i]
i := longestCommonPrefix(path, n.path)
// Split edge
// 假設當前節點存在的字首資訊為 hello
// 現有字首資訊為heo的結點進入， 則當前節點需要被拆分
// 拆分成為 he節點 以及 (llo 和 o 兩個子節點)
if i < len(n.path) {
child := node{
// 除去公共字首部分，剩餘的內容作為子節點
path: n.path[i:],
wildChild: n.wildChild,
indices: n.indices,
children: n.children,
handlers: n.handlers,
priority: n.priority - 1,
fullPath: n.fullPath,
}
n.children = []*node{&child}
// []byte for proper unicode char conversion, see #65
n.indices = bytesconv.BytesToString([]byte{n.path[i]})
n.path = path[:i]
n.handlers = nil
n.wildChild = false
n.fullPath = fullPath[:parentFullPathIndex+i]
}
// Make new node a child of this node
// 將新來的節點插入新的parent節點作為子節點
if i < len(path) {
path = path[i:]
c := path[0]
// '/' after param
// 如果是引數節點 形如/:i
if n.nType == param && c == '/' && len(n.children) == 1 {
parentFullPathIndex += len(n.path)
n = n.children[0]
n.priority++
continue walk
}
// Check if a child with the next path byte exists
for i, max := 0, len(n.indices); i < max; i++ {
if c == n.indices[i] {
parentFullPathIndex += len(n.path)
i = n.incrementChildPrio(i)
n = n.children[i]
continue walk
}
}
// Otherwise insert it
if c != ':' && c != '*' && n.nType != catchAll {
// []byte for proper unicode char conversion, see #65
n.indices += bytesconv.BytesToString([]byte{c})
child := &node{
fullPath: fullPath,
}
n.addChild(child)
n.incrementChildPrio(len(n.indices) - 1)
n = child
} else if n.wildChild {
// inserting a wildcard node, need to check if it conflicts with the existing wildcard
n = n.children[len(n.children)-1]
n.priority++
// Check if the wildcard matches
if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
// Adding a child to a catchAll is not possible
n.nType != catchAll &&
// Check for longer wildcard, e.g. :name and :names
(len(n.path) >= len(path) || path[len(n.path)] == '/') {
continue walk
}
// Wildcard conflict
pathSeg := path
if n.nType != catchAll {
pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
}
prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
panic("'" + pathSeg +
"' in new path '" + fullPath +
"' conflicts with existing wildcard '" + n.path +
"' in existing prefix '" + prefix +
"'")
}
n.insertChild(path, fullPath, handlers)
return
}
// Otherwise add handle to current node
// 設定處理常式，如果已經存在，則報錯
if n.handlers != nil {
panic("handlers are already registered for path '" + fullPath + "'")
}
n.handlers = handlers
n.fullPath = fullPath
return
}
}
Priority 優先順序
為了能快速找到並組合完整的路由，GIN 在新增路由的同時，會在每個節點中新增 Priority 這個屬性。在查詢時根據 Priority 進行排序，常用節點(通過次數理論最多的節點) 在最前，並且同一層級裡面 Priority 值越大，越優先進行匹配。
為何要將 9 種請求方法放在 slice 而不是 map 中
這是因為 9 個請求方法對應 9 棵路由樹，而 GIN 對應的所有請求方法都維護了一顆路由樹，同時這些關鍵資訊都被包裹在 Node 結構體內，並被放置在一個陣列當中而非 map 中。這樣是為了固定請求數量，同時在專案啟動後請求方法會被維護在記憶體當中，採用固定長度的 slice 從而在保證一定查詢效率的同時減少記憶體佔用。
type methodTrees []methodTree
func (trees methodTrees) get(method string) *node {
for _, tree := range trees {
if tree.method == method {
return tree.root
}
}
return nil
}
查詢路由
路由樹構建完畢之後，GIN 即可開始正常接收請求。第一步是從 ServeHTTP 開始解析路由地址，而查詢的過程處理邏輯如下：
-
申請一塊記憶體用來填充響應體
-
處理請求資訊
-
從 trees 中遍歷比較請求方法，拿到最對應請求方法的路由樹
-
獲取根節點
func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {
c := engine.pool.Get().(*Context)
c.writermem.reset(w)
c.Request = req
c.reset()
// 真正開始處理請求
engine.handleHTTPRequest(c)
engine.pool.Put(c)
}
func (engine *Engine) handleHTTPRequest(c *Context) {
// ...
t := engine.trees
for i, tl := 0, len(t); i < tl; i++ {
// 根據請求方法進行判斷
if t[i].method != httpMethod {
continue
}
root := t[i].root
// 在該方法樹上查詢路由
value := root.getValue(rPath, c.params, unescape)
if value.params != nil {
c.Params = *value.params
}
// 執行處理常式
if value.handlers != nil {
c.handlers = value.handlers
c.fullPath = value.fullPath
c.Next() // 涉及到gin的中介軟體機制
// 到這裡時，請求已經處理完畢，返回的結果也儲存在對應的結構體中了
c.writermem.WriteHeaderNow()
return
}
// ...
break
}
if engine.HandleMethodNotAllowed {
for _, tree := range engine.trees {
if tree.method == httpMethod {
continue
}
if value := tree.root.getValue(rPath, nil, c.skippedNodes, unescape); value.handlers != nil {
c.handlers = engine.allNoMethod
serveError(c, http.StatusMethodNotAllowed, default405Body)
return
}
}
}
}
上面就是關於 GIN 路由樹的一些經驗分享，希望能夠幫助到大家。