原文鏈接： go-zero 是如何做路由管理的？

go-zero 是一個微服務框架，包含了 web 和 rpc 兩大部分。

而對于 web 框架來說，路由管理是必不可少的一部分，那么本文就來探討一下 go-zero 的路由管理是怎么做的，具體采用了哪種技術方案。

路由管理方案

路由管理方案有很多種，具體應該如何選擇，應該根據使用場景，以及實現的難易程度做綜合分析，下面介紹常見的三種方案。

注意這里只是做一個簡單的概括性對比，更加詳細的內容可以看這篇文章：HTTP Router 算法演進。

標準庫方案

最簡單的方案就是直接使用 map[string]func() 作為路由的數據結構，鍵為具體的路由，值為具體的處理方法。

// 路由管理數據結構

type ServeMux struct {
    mu    sync.RWMutex          // 對象操作讀寫鎖
    m     map[string]muxEntry   // 存儲路由映射關系
}

這種方案優點就是實現簡單，性能較高；缺點也很明顯，占用內存更高，更重要的是不夠靈活。

Trie Tree

Trie Tree 也稱為字典樹或前綴樹，是一種用于高效存儲和檢索、用于從某個集合中查到某個特定 key 的數據結構。

Trie Tree 時間復雜度低，和一般的樹形數據結構相比，Trie Tree 擁有更快的前綴搜索和查詢性能。

和查詢時間復雜度為 O(1) 常數的哈希算法相比，Trie Tree 支持前綴搜索，并且可以節省哈希函數的計算開銷和避免哈希值碰撞的情況。

最后，Trie Tree 還支持對關鍵字進行字典排序。

Radix Tree

Radix Tree（基數樹）是一種特殊的數據結構，用于高效地存儲和搜索字符串鍵值對，它是一種基于前綴的樹狀結構，通過將相同前綴的鍵值對合并在一起來減少存儲空間的使用。

Radix Tree 通過合并公共前綴來降低存儲空間的開銷，避免了 Trie Tree 字符串過長和字符集過大時導致的存儲空間過多問題，同時公共前綴優化了路徑層數，提升了插入、查詢、刪除等操作效率。

比如 Gin 框架使用的開源組件 HttpRouter 就是采用這個方案。

go-zero 路由規則

在使用 go-zero 開發項目時，定義路由需要遵守如下規則：

1. 路由必須以 / 開頭
2. 路由節點必須以 / 分隔
3. 路由節點中可以包含 :，但是 : 必須是路由節點的第一個字符，: 后面的節點值必須要在結請求體中有 path tag 聲明，用于接收路由參數
4. 路由節點可以包含字母、數字、下劃線、中劃線

接下來就讓我們深入到源碼層面，相信看過源碼之后，你就會更懂這些規則的意義了。

go-zero 源碼實現

首先需要說明的是，底層數據結構使用的是二叉搜索樹，還不是很了解的同學可以看這篇文章：使用 Go 語言實現二叉搜索樹

節點定義

先看一下節點定義：

// core/search/tree.go

const (
    colon = ':'
    slash = '/'
)

type (
    // 節點
    node struct {
        item     interface{}
        children [2]map[string]*node
    }

    // A Tree is a search tree.
    Tree struct {
        root *node
    }
)

重點說一下 children，它是一個包含兩個元素的數組，元素 0 存正常路由鍵，元素 1 存以 : 開頭的路由鍵，這些是 url 中的變量，到時候需要替換成實際值。

舉一個例子，有這樣一個路由 /api/:user，那么 api 會存在 children[0]，user 會存在 children[1]。

具體可以看看這段代碼：

func (nd *node) getChildren(route string) map[string]*node {
    // 判斷路由是不是以 : 開頭
    if len(route) > 0 && route[0] == colon {
        return nd.children[1]
    }

    return nd.children[0]
}

路由添加

// Add adds item to associate with route.
func (t *Tree) Add(route string, item interface{}) error {
    // 需要路由以 / 開頭
    if len(route) == 0 || route[0] != slash {
        return errNotFromRoot
    }

    if item == nil {
        return errEmptyItem
    }

    // 把去掉 / 的路由作為參數傳入
    err := add(t.root, route[1:], item)
    switch err {
    case errDupItem:
        return duplicatedItem(route)
    case errDupSlash:
        return duplicatedSlash(route)
    default:
        return err
    }
}


func add(nd *node, route string, item interface{}) error {
    if len(route) == 0 {
        if nd.item != nil {
            return errDupItem
        }

        nd.item = item
        return nil
    }

    // 繼續判斷，看看是不是有多個 /
    if route[0] == slash {
        return errDupSlash
    }

    for i := range route {
        // 判斷是不是 /，目的就是去處兩個 / 之間的內容
        if route[i] != slash {
            continue
        }

        token := route[:i]
        
        // 看看有沒有子節點，如果有子節點，就在子節點下面繼續添加
        children := nd.getChildren(token)
        if child, ok := children[token]; ok {
            if child != nil {
                return add(child, route[i+1:], item)
            }

            return errInvalidState
        }

        // 沒有子節點，那么新建一個
        child := newNode(nil)
        children[token] = child
        return add(child, route[i+1:], item)
    }

    children := nd.getChildren(route)
    if child, ok := children[route]; ok {
        if child.item != nil {
            return errDupItem
        }

        child.item = item
    } else {
        children[route] = newNode(item)
    }

    return nil
}

主要部分代碼都已經加了注釋，其實這個過程就是樹的構建，如果讀過之前那篇文章，那這里還是比較好理解的。

路由查找

先來看一段 match 代碼：

func match(pat, token string) innerResult {
    if pat[0] == colon {
        return innerResult{
            key:   pat[1:],
            value: token,
            named: true,
            found: true,
        }
    }

    return innerResult{
        found: pat == token,
    }
}

這里有兩個參數：

• pat：路由樹中存儲的路由
• token：實際請求的路由，可能包含參數值

還是剛才的例子 /api/:user，如果是 api，沒有以 : 開頭，那就不會走 if 邏輯。

接下來匹配 :user 部分，如果實際請求的 url 是 /api/zhangsan，那么會將 user 作為 key，zhangsan 作為 value 保存到結果中。

下面是搜索查找代碼：

// Search searches item that associates with given route.
func (t *Tree) Search(route string) (Result, bool) {
    // 第一步先判斷是不是 / 開頭
    if len(route) == 0 || route[0] != slash {
        return NotFound, false
    }

    var result Result
    ok := t.next(t.root, route[1:], &result)
    return result, ok
}

func (t *Tree) next(n *node, route string, result *Result) bool {
    if len(route) == 0 && n.item != nil {
        result.Item = n.item
        return true
    }

    for i := range route {
        // 和 add 里同樣的提取邏輯
        if route[i] != slash {
            continue
        }

        token := route[:i]
        return n.forEach(func(k string, v *node) bool {
            r := match(k, token)
            if !r.found || !t.next(v, route[i+1:], result) {
                return false
            }
            // 如果 url 中有參數，會把鍵值對保存到結果中
            if r.named {
                addParam(result, r.key, r.value)
            }

            return true
        })
    }

    return n.forEach(func(k string, v *node) bool {
        if r := match(k, route); r.found && v.item != nil {
            result.Item = v.item
            if r.named {
                addParam(result, r.key, r.value)
            }

            return true
        }

        return false
    })
}

以上就是路由管理的大部分代碼，整個文件也就 200 多行，邏輯也并不復雜，通讀之后還是很有收獲的。

大家如果感興趣的話，可以找到項目更詳細地閱讀。也可以關注我，接下來還會分析其他模塊的源碼。

以上就是本文的全部內容，如果覺得還不錯的話歡迎點贊，轉發和關注，感謝支持。

推薦閱讀：

• 使用 Go 語言實現二叉搜索樹
• HTTP Router 算法演進