Go-Zero 是如何做路由管理的？
go-zero 是一個微服務框架，包含了 web 和 rpc 兩大部分。
而對于 web 框架來說，路由管理是必不可少的一部分，那么本文就來探討一下 go-zero 的路由管理是怎么做的，具體采用了哪種技術方案。
路由管理方案
路由管理方案有很多種，具體應該如何選擇，應該根據使用場景，以及實現的難易程度做綜合分析，下面介紹常見的三種方案。
注意這里只是做一個簡單的概括性對比。
標準庫方案
最簡單的方案就是直接使用 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 開發項目時，定義路由需要遵守如下規則：
- 路由必須以 / 開頭
- 路由節點必須以 / 分隔
- 路由節點中可以包含 :，但是 : 必須是路由節點的第一個字符，: 后面的節點值必須要在結請求體中有 path tag 聲明，用于接收路由參數
- 路由節點可以包含字母、數字、下劃線、中劃線
接下來就讓我們深入到源碼層面，相信看過源碼之后，你就會更懂這些規則的意義了。
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 多行，邏輯也并不復雜，通讀之后還是很有收獲的。
大家如果感興趣的話，可以找到項目更詳細地閱讀。也可以關注我，接下來還會分析其他模塊的源碼。
