go-zero 是如何做路由管理的？

原文链接： go-zero 是如何做路由管理的？
go-zero 是一个微服务框架，包含了 web 和 rpc 两大部分。
而对于 web 框架来说，路由管理是必不可少的一部分，那么本文就来探讨一下 go-zero 的路由管理是怎么做的，具体采用了哪种技术方案。
路由管理方案

路由管理方案有很多种，具体应该如何选择，应该根据使用场景，以及实现的难易程度做综合分析，下面介绍常见的三种方案。
注意这里只是做一个简单的概括性对比，更加详细的内容可以看这篇文章：HTTP Router 算法演进。
标准库方案

最简单的方案就是直接使用 map[string]func() 作为路由的数据结构，键为具体的路由，值为具体的处理方法。

1. // 路由管理数据结构
3. type ServeMux struct {
4.     mu    sync.RWMutex          // 对象操作读写锁
5.     m     map[string]muxEntry   // 存储路由映射关系
6. }

复制代码

这种方案优点就是实现简单，性能较高；缺点也很明显，占用内存更高，更重要的是不够灵活。
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 语言实现二叉搜索树
节点定义

先看一下节点定义：

1. // core/search/tree.go
3. const (
4.     colon = ':'
5.     slash = '/'
6. )
8. type (
9.     // 节点
10.     node struct {
11.         item     interface{}
12.         children [2]map[string]*node
13.     }
15.     // A Tree is a search tree.
16.     Tree struct {
17.         root *node
18.     }
19. )

复制代码

重点说一下 children，它是一个包含两个元素的数组，元素 0 存正常路由键，元素 1 存以 : 开头的路由键，这些是 url 中的变量，到时候需要替换成实际值。
举一个例子，有这样一个路由 /api/:user，那么 api 会存在 children[0]，user 会存在 children[1]。
具体可以看看这段代码：

1. func (nd *node) getChildren(route string) map[string]*node {
2.     // 判断路由是不是以 : 开头
3.     if len(route) > 0 && route[0] == colon {
4.         return nd.children[1]
5.     }
7.     return nd.children[0]
8. }

复制代码

路由添加

1. // Add adds item to associate with route.
2. func (t *Tree) Add(route string, item interface{}) error {
3.     // 需要路由以 / 开头
4.     if len(route) == 0 || route[0] != slash {
5.         return errNotFromRoot
6.     }
8.     if item == nil {
9.         return errEmptyItem
10.     }
12.     // 把去掉 / 的路由作为参数传入
13.     err := add(t.root, route[1:], item)
14.     switch err {
15.     case errDupItem:
16.         return duplicatedItem(route)
17.     case errDupSlash:
18.         return duplicatedSlash(route)
19.     default:
20.         return err
21.     }
22. }
25. func add(nd *node, route string, item interface{}) error {
26.     if len(route) == 0 {
27.         if nd.item != nil {
28.             return errDupItem
29.         }
31.         nd.item = item
32.         return nil
33.     }
35.     // 继续判断，看看是不是有多个 /
36.     if route[0] == slash {
37.         return errDupSlash
38.     }
40.     for i := range route {
41.         // 判断是不是 /，目的就是去处两个 / 之间的内容
42.         if route[i] != slash {
43.             continue
44.         }
46.         token := route[:i]
47.         
48.         // 看看有没有子节点，如果有子节点，就在子节点下面继续添加
49.         children := nd.getChildren(token)
50.         if child, ok := children[token]; ok {
51.             if child != nil {
52.                 return add(child, route[i+1:], item)
53.             }
55.             return errInvalidState
56.         }
58.         // 没有子节点，那么新建一个
59.         child := newNode(nil)
60.         children[token] = child
61.         return add(child, route[i+1:], item)
62.     }
64.     children := nd.getChildren(route)
65.     if child, ok := children[route]; ok {
66.         if child.item != nil {
67.             return errDupItem
68.         }
70.         child.item = item
71.     } else {
72.         children[route] = newNode(item)
73.     }
75.     return nil
76. }

复制代码

主要部分代码都已经加了注释，其实这个过程就是树的构建，如果读过之前那篇文章，那这里还是比较好理解的。
路由查找

先来看一段 match 代码：

1. func match(pat, token string) innerResult {
2.     if pat[0] == colon {
3.         return innerResult{
4.             key:   pat[1:],
5.             value: token,
6.             named: true,
7.             found: true,
8.         }
9.     }
11.     return innerResult{
12.         found: pat == token,
13.     }
14. }

复制代码

这里有两个参数：

• pat：路由树中存储的路由
  
• token：实际请求的路由，可能包含参数值
  

还是刚才的例子 /api/:user，如果是 api，没有以 : 开头，那就不会走 if 逻辑。
接下来匹配 :user 部分，如果实际请求的 url 是 /api/zhangsan，那么会将 user 作为 key，zhangsan 作为 value 保存到结果中。
下面是搜索查找代码：

1. // Search searches item that associates with given route.
2. func (t *Tree) Search(route string) (Result, bool) {
3.     // 第一步先判断是不是 / 开头
4.     if len(route) == 0 || route[0] != slash {
5.         return NotFound, false
6.     }
8.     var result Result
9.     ok := t.next(t.root, route[1:], &result)
10.     return result, ok
11. }
13. func (t *Tree) next(n *node, route string, result *Result) bool {
14.     if len(route) == 0 && n.item != nil {
15.         result.Item = n.item
16.         return true
17.     }
19.     for i := range route {
20.         // 和 add 里同样的提取逻辑
21.         if route[i] != slash {
22.             continue
23.         }
25.         token := route[:i]
26.         return n.forEach(func(k string, v *node) bool {
27.             r := match(k, token)
28.             if !r.found || !t.next(v, route[i+1:], result) {
29.                 return false
30.             }
31.             // 如果 url 中有参数，会把键值对保存到结果中
32.             if r.named {
33.                 addParam(result, r.key, r.value)
34.             }
36.             return true
37.         })
38.     }
40.     return n.forEach(func(k string, v *node) bool {
41.         if r := match(k, route); r.found && v.item != nil {
42.             result.Item = v.item
43.             if r.named {
44.                 addParam(result, r.key, r.value)
45.             }
47.             return true
48.         }
50.         return false
51.     })
52. }

复制代码

以上就是路由管理的大部分代码，整个文件也就 200 多行，逻辑也并不复杂，通读之后还是很有收获的。
大家如果感兴趣的话，可以找到项目更详细地阅读。也可以关注我，接下来还会分析其他模块的源码。
以上就是本文的全部内容，如果觉得还不错的话欢迎点赞，转发和关注，感谢支持。
推荐阅读：

• 使用 Go 语言实现二叉搜索树
  
• HTTP Router 算法演进
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！