**原文鏈接：** [go-zero 是如何做路由管理的？](https://mp.weixin.qq.com/s/uTJ1En-BXiLvH45xx0eFsA) go-zero 是一個微服務框架，包含了 web 和 rpc 兩大部分。 而對於 web 框架來說，路由管理是必不可少的一部分，那麼本文 ...
原文鏈接： 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 開發項目時，定義路由需要遵守如下規則：
- 路由必須以
/開頭 - 路由節點必須以
/分隔 - 路由節點中可以包含
:，但是:必須是路由節點的第一個字元，:後面的節點值必須要在結請求體中有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 多行，邏輯也並不複雜，通讀之後還是很有收穫的。
大家如果感興趣的話，可以找到項目更詳細地閱讀。也可以關註我，接下來還會分析其他模塊的源碼。
以上就是本文的全部內容，如果覺得還不錯的話歡迎點贊，轉發和關註，感謝支持。
推薦閱讀：
