Go-Zero 是如何做路由管理的？
go-zero 是一個微服務(wù)框架，包含了 web 和 rpc 兩大部分。
而對于 web 框架來說，路由管理是必不可少的一部分，那么本文就來探討一下 go-zero 的路由管理是怎么做的，具體采用了哪種技術(shù)方案。
路由管理方案
路由管理方案有很多種，具體應(yīng)該如何選擇，應(yīng)該根據(jù)使用場景，以及實現(xiàn)的難易程度做綜合分析，下面介紹常見的三種方案。
注意這里只是做一個簡單的概括性對比。
標(biāo)準(zhǔn)庫方案
最簡單的方案就是直接使用 map[string]func() 作為路由的數(shù)據(jù)結(jié)構(gòu)，鍵為具體的路由，值為具體的處理方法。
// 路由管理數(shù)據(jù)結(jié)構(gòu)
type ServeMux struct {
mu sync.RWMutex // 對象操作讀寫鎖
m map[string]muxEntry // 存儲路由映射關(guān)系
}這種方案優(yōu)點就是實現(xiàn)簡單，性能較高；缺點也很明顯，占用內(nèi)存更高，更重要的是不夠靈活。
Trie Tree
Trie Tree 也稱為字典樹或前綴樹，是一種用于高效存儲和檢索、用于從某個集合中查到某個特定 key 的數(shù)據(jù)結(jié)構(gòu)。
Trie Tree 時間復(fù)雜度低，和一般的樹形數(shù)據(jù)結(jié)構(gòu)相比，Trie Tree 擁有更快的前綴搜索和查詢性能。
和查詢時間復(fù)雜度為 O(1) 常數(shù)的哈希算法相比，Trie Tree 支持前綴搜索，并且可以節(jié)省哈希函數(shù)的計算開銷和避免哈希值碰撞的情況。
最后，Trie Tree 還支持對關(guān)鍵字進(jìn)行字典排序。
Radix Tree
Radix Tree（基數(shù)樹）是一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲和搜索字符串鍵值對，它是一種基于前綴的樹狀結(jié)構(gòu)，通過將相同前綴的鍵值對合并在一起來減少存儲空間的使用。
Radix Tree 通過合并公共前綴來降低存儲空間的開銷，避免了 Trie Tree 字符串過長和字符集過大時導(dǎo)致的存儲空間過多問題，同時公共前綴優(yōu)化了路徑層數(shù)，提升了插入、查詢、刪除等操作效率。
比如 Gin 框架使用的開源組件 HttpRouter 就是采用這個方案。
go-zero 路由規(guī)則
在使用 go-zero 開發(fā)項目時，定義路由需要遵守如下規(guī)則：
- 路由必須以 / 開頭
- 路由節(jié)點必須以 / 分隔
- 路由節(jié)點中可以包含 :，但是 : 必須是路由節(jié)點的第一個字符，: 后面的節(jié)點值必須要在結(jié)請求體中有 path tag 聲明，用于接收路由參數(shù)
- 路由節(jié)點可以包含字母、數(shù)字、下劃線、中劃線
接下來就讓我們深入到源碼層面，相信看過源碼之后，你就會更懂這些規(guī)則的意義了。
go-zero 源碼實現(xiàn)
首先需要說明的是，底層數(shù)據(jù)結(jié)構(gòu)使用的是二叉搜索樹，還不是很了解的同學(xué)可以看這篇文章：使用 Go 語言實現(xiàn)二叉搜索樹。
節(jié)點定義
先看一下節(jié)點定義：
// core/search/tree.go
const (
colon = ':'
slash = '/'
)
type (
// 節(jié)點
node struct {
item interface{}
children [2]map[string]*node
}
// A Tree is a search tree.
Tree struct {
root *node
}
)重點說一下 children，它是一個包含兩個元素的數(shù)組，元素 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
}
// 把去掉 / 的路由作為參數(shù)傳入
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
}
// 繼續(xù)判斷，看看是不是有多個 /
if route[0] == slash {
return errDupSlash
}
for i := range route {
// 判斷是不是 /，目的就是去處兩個 / 之間的內(nèi)容
if route[i] != slash {
continue
}
token := route[:i]
// 看看有沒有子節(jié)點，如果有子節(jié)點，就在子節(jié)點下面繼續(xù)添加
children := nd.getChildren(token)
if child, ok := children[token]; ok {
if child != nil {
return add(child, route[i+1:], item)
}
return errInvalidState
}
// 沒有子節(jié)點，那么新建一個
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
}主要部分代碼都已經(jīng)加了注釋，其實這個過程就是樹的構(gòu)建，如果讀過之前那篇文章，那這里還是比較好理解的。
路由查找
先來看一段 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,
}
}這里有兩個參數(shù)：
- pat：路由樹中存儲的路由。
- token：實際請求的路由，可能包含參數(shù)值。
還是剛才的例子 /api/:user，如果是 api，沒有以 : 開頭，那就不會走 if 邏輯。
接下來匹配 :user 部分，如果實際請求的 url 是 /api/zhangsan，那么會將 user 作為 key，zhangsan 作為 value 保存到結(jié)果中。
下面是搜索查找代碼：
// 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 中有參數(shù)，會把鍵值對保存到結(jié)果中
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 多行，邏輯也并不復(fù)雜，通讀之后還是很有收獲的。
大家如果感興趣的話，可以找到項目更詳細(xì)地閱讀。也可以關(guān)注我，接下來還會分析其他模塊的源碼。
