Golang-gin 框架路由原理

什麼是 http 路由

擼過 http 框架的同學都知道，一個 MVC 模型的 http 框架肯定是少不了路由這一塊的，那麼什麼是路由呢。

簡而言之，http 路由即是一條 http 請求的 “嚮導”，根據 URI 上的路徑，指引該條請求到對應的方法裏去執行然後返回，中間可能會執行一些中間件。

路由的種類

框架 / 用戶提前生成一個路由表，一般是 map 結構，key 爲 URI 上的 path，value 爲代碼執行點。

優點：只需要讀取 map，沒有任何開銷，速度奇快。

缺點：無法正則匹配路由，只能一一對應，模糊匹配的場景無法使用。

用戶定義好路由匹配規則，框架匹配路由時，根據規則動態去規劃路由。

優點：適應性強，解決了靜態路由的缺點。

缺點：相比靜態路由有開銷，具體視算法和路由匹配規則而定。

gin 框架路由實現原理

gin 框架作爲一個輕量級的快速框架，採用的是前綴樹的方式實現的動態路由。

gin 框架使用路由

我們以下面代碼爲例，去看看 gin 是如何實現路由的。

r := gin.New()
r.GET("/user/:name", routeUser)
func routeUser(c *gin.Context){
    //todo something
}

上面定義了一個路由 /user/:name，它會精確匹配 /user/:name，而不會匹配 /user、/user/ 或者 /user/allen/abc。

接下來我們跟着源碼去探究 gin 是如何實現的。

初始化框架

r := gin.New() 生成了一個 Engine 對象，Engine 對象是整個框架的核心，也包含了對路由的操作和許多成員變量，其中包括路由要執行的任務鏈 Handlers HandlersChain，方法樹 trees methodTrees 等。

定義路由

r.GET("/user/:name", routeUser) 定義一個 GET 請求，模糊匹配 /user/:name。

步驟 1：

源碼：routergroup.go=>group.calculateAbsolutePath()

將相對路徑 /user/:namejoin 爲絕對路徑，因爲有可能是個路由組，前面還有一些路徑。路由組稍後再介紹。

步驟 2：

源碼：routergroup.go=>group.combineHandlers()

判斷 handlersChain 的長度，不能超過 math.MaxInt8 / 2 並且把路由方法裝載到 handlersChain 裏面去。

步驟 3：

源碼：routergroup.go=>group.engine.addRoute()

裝入路由存入 engine.trees 變量。

步驟 4：

返回當前對象，達到能使用鏈式操作的目的。

訪問路由

輸入 localhost:8080/user/abc，首先進入 net 的 ServeHTTP() 方法。然後被 gin 框架 handleHTTPRequest() 方法接受。循環之前註冊的路由樹 engine.tress。

匹配 method 部分源碼 gin.go=>handleHTTPRequest()：

t := engine.trees
for i, tl := 0, len(t); i < tl; i++ {
  if t[i].method != httpMethod {
    continue    //判斷請求method是否相等如果不等則continue
  }
  root := t[i].root
  // Find route in tree
  value := root.getValue(rPath, c.params, unescape)
  //匹配路由的核心算法，如果匹配出來的value爲空則直接退出。
  ...
  ...
}

匹配路由核心算法源碼 tree.go=>getValue()：

func (n *node) getValue(path string, params *Params, unescape bool) (value nodeValue) {
walk: // Outer loop for walking the tree
  for {
    prefix := n.path
    if len(path) > len(prefix) {
      if path[:len(prefix)] == prefix {
        //前綴匹配
          ...
          switch n.nType {
        case param:
        ...
        (*value.params)[i] = Param{
          Key:   n.path[1:],
          Value: val,
        }// 匹配出參數
      }
    }
    if path == prefix {
        // 完全匹配，無需匹配參數
        ...
    }
  }
}

前綴樹算法

前綴樹的本質就是一棵查找樹，有別於普通查找樹，它適用於一些特殊場合，比如用於字符串的查找。比如一個在路由的場景中，有 1W 個路由字符串，每個字符串長度不等，我們可以使用數組來儲存，查找的時間複雜度是 O(n)，可以用 map 來儲存，查找的複雜度是 O(1)，但是都沒法解決動態匹配的問題，如果用前綴樹時間複雜度是 O(logn)，也可以解決動態匹配參數的問題。

下圖展示了前綴樹的原理，有以下 6 個字符串，如果要查找 cat 字符串，步驟如下：

  1. 先拿字符 c 和 root 的第一個節點 a 比較，如果不等，再繼續和父節點 root 的第二個節點比較，直到找到 c。

  2. 再拿字符 a 和父節點 c 的第一個節點 a 比較，結果相等，則繼續往下。

  3. 再拿字符 t 和父節點 a 的第一個節點 t 比較，結果相等，則完成。

同理，在路由中，前綴樹可以規劃成如下：

具體查找方法和上面一致。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/8whRUnnzCwxOGIJ7Sck1ng

猜你喜歡