關於 GIN 的路由樹

2022 年 6 月 22 日
筆記
golang, 前端, 架構

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 路由樹的一些經驗分享，希望能夠幫助到大家。