Golang Web入门（2）：如何实现一个高性能的路由
摘要
在上一篇文章中，我们聊了聊在Golang中怎么实现一个Http服务器。但是在最后我们可以发现，固然 DefaultServeMux 可以做路由分发的功能，但是他的功能同样是不完善的。
由 DefaultServeMux 做路由分发，是不能实现 RESTful 风格的API的，我们没有办法定义请求所需的方法，也没有办法在 API 路径中加入 query 参数。其次，我们也希望可以让路由查找的效率更高。
所以在这篇文章中，我们将分析 httprouter 这个包，从源码的层面研究他是如何实现我们上面提到的那些功能。并且，对于这个包中最重要的 前缀树 ，本文将以图文结合的方式来解释。
1 使用
我们同样以怎么使用作为开始，自顶向下的去研究 httprouter 。我们先来看看官方文档中的小例子：
package main
import (
"fmt"
"net/http"
"log"
"github.com/julienschmidt/httprouter"
)
func Index(w http.ResponseWriter, r *http.Request, _ httprouter.Params) {
fmt.Fprint(w, "Welcome!\n")
}
func Hello(w http.ResponseWriter, r *http.Request, ps httprouter.Params) {
fmt.Fprintf(w, "hello, %s!\n", ps.ByName("name"))
}
func main() {
router := httprouter.New()
router.GET("/", Index)
router.GET("/hello/:name", Hello)
log.Fatal(http.ListenAndServe(":8080", router))
}
其实我们可以发现，这里的做法和使用Golang自带的 net/http 包的做法是差不多的。都是先注册相应的URI和函数，换一句话来说就是将路由和处理器相匹配。
在注册的时候，使用 router.XXX 方法，来注册相对应的方法，比如 GET ， POST 等等。
注册完之后，使用 http.ListenAndServe 开始监听。
至于为什么，我们会在后面的章节详细介绍，现在只需要先了解做法即可。
2 创建
我们先来看看第一行代码，我们定义并声明了一个 Router 。下面来看看这个 Router 的结构，这里把与本文无关的其他属性省略：
type Router struct {
//这是前缀树，记录了相应的路由
trees map[string]*node
//记录了参数的最大数目
maxParams uint16
}
在创建了这个 Router 的结构后，我们就使用 router.XXX 方法来注册路由了。继续看看路由是怎么注册的：
func (r *Router) GET(path string, handle Handle) {
r.Handle(http.MethodGet, path, handle)
}
func (r *Router) POST(path string, handle Handle) {
r.Handle(http.MethodPost, path, handle)
}
...
在这里还有一长串的方法，他们都是一样的，调用了
r.Handle(http.MethodPost, path, handle)
这个方法。我们再来看看：
func (r *Router) Handle(method, path string, handle Handle) {
...
if r.trees == nil {
r.trees = make(map[string]*node)
}
root := r.trees[method]
if root == nil {
root = new(node)
r.trees[method] = root
r.globalAllowed = r.allowed("*", "")
}
root.addRoute(path, handle)
...
}
在这个方法里，同样省略了很多细节。我们只关注一下与本文有关的。我们可以看到，在这个方法中，如果 tree 还没有初始化，则先初始化这颗 前缀树 。
然后我们注意到，这颗树是一个 map 结构。也就是说，一个方法，对应了一颗树。然后，对应这棵树，调用 addRoute 方法，把 URI 和对应的 Handle 保存进去。
3 前缀树
3.1 定义
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
简单的来讲，就是要查找什么，只要跟着这棵树的某一条路径找，就可以找得到。
比如在搜索引擎中，你输入了一个 蔡 ：
他会有这些联想，也可以理解为是一个前缀树。
再举个例子：
在这颗 GET 方法的前缀树中，包含了以下的路由：
- /wow/awesome
- /test
- /hello/world
- /hello/china
- /hello/chinese
说到这里你应该可以理解了，在构建这棵树的过程中， 任何两个节点，只要有了相同的前缀，相同的部分就会被合并成一个节点 。
3.2 图解构建
上面说的 addRoute 方法，就是这颗前缀树的插入方法。假设现在数为空，在这里我打算以图解的方式来说明这棵树的构建。
假设我们需要插入的三个路由分别为：
- /hello/world
- /hello/china
- /hello/chinese
（1）插入 /hello/world
因为此时树为空，所以可以直接插入：
(2)插入 /hello/china
此时，发现 /hello/world 和 /hello/china 有相同的前缀 /hello/ 。
那么要先将原来的 /hello/world 结点，拆分出来，然后将要插入的结点 /hello/china ，截去相同部分，作为 /hello/world 的子节点。
(3)插入 /hello/chinese
此时，我们需要插入 /hello/chinese ，但是发现， /hello/chinese 和结点 /hello/ 有公共的前缀 /hello/ ，所以我们去查看 /hello/ 这个结点的子节点。
注意，在结点中有一个属性，叫 indices 。它记录了这个结点的子节点的首字母，便于我们查找。比如这个 /hello/ 结点，他的 indices 值为 wc 。而我们要插入的结点是 /hello/chinese ，除去公共前缀后， chinese 的第一个字母也是 c ，所以我们进入 china 这个结点。
这时，有没有发现，情况回到了我们一开始插入 /hello/china 时候的局面。那个时候公共前缀是 /hello/ ，现在的公共前缀是 chin 。
所以，我们同样把 chin 截出来，作为一个结点，将 a 作为这个结点的子节点。并且，同样把 ese 也作为子节点。
3.3 总结构建算法
到这里，构建就已经结束了。我们来总结一下算法。
具体带注释的代码将在本文最末尾给出，如果想要了解的更深可以自行查看。在这里先理解这个过程：
（1）如果树为空，则直接插入
（2）否则，查找当前的结点是否与要插入的 URI 有公共前缀
（3）如果没有公共前缀，则直接插入
（4）如果有公共前缀，则判断是否需要分裂当前的结点
（5）如果需要分裂，则将公共部分作为父节点，其余的作为子节点
（6）如果不需要分裂，则寻找有无前缀相同的子节点
（7）如果有前缀相同的，则跳到(4)
（8）如果没有前缀相同的，直接插入
（9）在最后的结点，放入这条路由对应的 Handle
但是到了这里，有同学要问了： 怎么这里的路由，不带参数的呀？
其实只要你理解了上面的过程，带参数也是一样的。逻辑是这样的：在每次插入之前，会扫描当前要插入的结点的path是否带有参数（即扫描有没有 / 或者 * ）。如果带有参数的话，将当前结点的 wildChild 属性设置为 true ，然后将参数部分，设置为一个 新的子节点 。
4 监听
在讲完了路由的注册，我们来聊聊路由的监听。
在上一篇文章的内容中，我们有提到这个：
type serverHandler struct {
srv *Server
}
func (sh serverHandler) ServeHTTP(rw ResponseWriter, req *Request) {
handler := sh.srv.Handler
if handler == nil {
handler = DefaultServeMux
}
if req.RequestURI == "*" && req.Method == "OPTIONS" {
handler = globalOptionsHandler{}
}
handler.ServeHTTP(rw, req)
}
当时我们提到，如果我们不传入任何的 Handle 方法，Golang将使用默认的 DefaultServeMux 方法来处理请求。而现在我们传入了 router ，所以将会使用 router 来处理请求。
因此， router 也是实现了 ServeHTTP 方法的。我们来看看（同样省略了一些步骤）：
func (r *Router) ServeHTTP(w http.ResponseWriter, req *http.Request) {
...
path := req.URL.Path
if root := r.trees[req.Method]; root != nil {
if handle, ps, tsr := root.getValue(path, r.getParams); handle != nil {
if ps != nil {
handle(w, req, *ps)
r.putParams(ps)
} else {
handle(w, req, nil)
}
return
}
}
...
// Handle 404
if r.NotFound != nil {
r.NotFound.ServeHTTP(w, req)
} else {
http.NotFound(w, req)
}
}
在这里，我们选择 请求方法 所对应的 前缀树 ，调用了 getValue 方法。
简单解释一下这个方法：在这个方法中会不断的去匹配当前路径与结点中的 path ，直到找到最后找到这个路由对应的 Handle 方法。
注意，在这期间，如果路由是RESTful风格的，在路由中含有参数，将会被保存在 Param 中，这里的 Param 结构如下：
type Param struct {
Key string
Value string
}
如果未找到相对应的路由，则调用后面的404方法。
5 处理
到了这一步，其实和以前的内容几乎一样了。
在获取了该路由对应的 Handle 之后，调用这个函数。
唯一和之前使用 net/http 包中的 Handler 不一样的是，这里的 Handle ，封装了从API中获取的参数。
type Handle func(http.ResponseWriter, *http.Request, Params)
6 写在最后
谢谢你能看到这里~
至此，httprouter介绍完毕，最关键的也就是前缀树的构建了。在上面我用图文结合的方式，模拟了一次前缀树的构建过程，希望可以让你理解前缀树是怎么回事。当然，如果还有疑问，也可以留言或者在微信中与我交流~
当然，如果你不满足于此，可以看看 后面的附 录，有前缀树的 全代码注释 。
当然了，作者也是刚入门。所以，可能会有很多的疏漏。如果在阅读的过程中，有哪些解释不到位，或者理解出现了偏差，也请你留言指正。
再次感谢~
PS：如果有其他的问题，也可以在公众号找到作者。并且，所有文章第一时间会在公众号更新，欢迎来找作者玩~
7 源码阅读
7.1 树的结构
type node struct {
path string //当前结点的URI
indices string //子结点的首字母
wildChild bool //子节点是否为参数结点
nType nodeType //结点类型
priority uint32 //权重
children []*node //子节点
handle Handle //处理器
}
7.2 addRoute
func (n *node) addRoute(path string, handle Handle) {
fullPath := path
n.priority++
// 如果这是个空树，那么直接插入
if len(n.path) == 0 && len(n.indices) == 0 {
//这个方法其实是在n这个结点插入path，但是会处理参数
//详细实现在后文会给出
n.insertChild(path, fullPath, handle)
n.nType = root
return
}
//设置一个flag
walk:
for {
// 找到当前结点path和要插入的path中最长的前缀
// i为第一位不相同的下标
i := longestCommonPrefix(path, n.path)
// 此时相同的部分比这个结点记录的path短
// 也就是说需要把当前的结点分裂开
if i < len(n.path) {
child := node{
// 把不相同的部分设置为一个切片，作为子节点
path: n.path[i:],
wildChild: n.wildChild,
nType: static,
indices: n.indices,
children: n.children,
handle: n.handle,
priority: n.priority - 1,
}
// 将新的结点作为这个结点的子节点
n.children = []*node{&child}
// 把这个结点的首字母加入indices中
// 目的是查找更快
n.indices = string([]byte{n.path[i]})
n.path = path[:i]
n.handle = nil
n.wildChild = false
}
// 此时相同的部分只占了新URI的一部分
// 所以把path后面不相同的部分要设置成一个新的结点
if i = len(n.path) && n.path == path[:len(n.path)] &&
n.nType != catchAll &&
(len(n.path) >= len(path) || path[len(n.path)] == '/') {
continue walk
} else {
pathSeg := path
if n.nType != catchAll {
pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
}
prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
panic("'" + pathSeg +
"' in new path '" + fullPath +
"' conflicts with existing wildcard '" + n.path +
"' in existing prefix '" + prefix +
"'")
}
}
// 把截取的path的第一位记录下来
idxc := path[0]
// 如果此时n的子节点是带参数的
if n.nType == param && idxc == '/' && len(n.children) == 1 {
n = n.children[0]
n.priority++
continue walk
}
// 这一步是检查拆分出的path，是否应该被合并入子节点中
// 具体例子可看上文中的图解
// 如果是这样的话，把这个子节点设置为n，然后开始一轮新的循环
for i, c := range []byte(n.indices) {
if c == idxc {
// 这一部分是为了把权重更高的首字符调整到前面
i = n.incrementChildPrio(i)
n = n.children[i]
continue walk
}
}
// 如果这个结点不用被合并
if idxc != ':' && idxc != '*' {
// 把这个结点的首字母也加入n的indices中
n.indices += string([]byte{idxc})
child := &node{}
n.children = append(n.children, child)
n.incrementChildPrio(len(n.indices) - 1)
// 新建一个结点
n = child
}
// 对这个结点进行插入操作
n.insertChild(path, fullPath, handle)
return
}
// 直接插入到当前的结点
if n.handle != nil {
panic("a handle is already registered for path '" + fullPath + "'")
}
n.handle = handle
return
}
}
7.3 insertChild
func (n *node) insertChild(path, fullPath string, handle Handle) {
for {
// 这个方法是用来找这个path是否含有参数的
wildcard, i, valid := findWildcard(path)
// 如果不含参数，直接跳出循环，看最后两行
if i < 0 {
break
}
// 条件校验
if !valid {
panic("only one wildcard per path segment is allowed, has: '" +
wildcard + "' in path '" + fullPath + "'")
}
// 同样判断是否合法
if len(wildcard) 0 {
panic("wildcard segment '" + wildcard +
"' conflicts with existing children in path '" + fullPath + "'")
}
// 如果参数的第一位是`:`，则说明这是一个参数类型
if wildcard[0] == ':' {
if i > 0 {
// 把当前的path设置为参数之前的那部分
n.path = path[:i]
// 准备把参数后面的部分作为一个新的结点
path = path[i:]
}
//然后把参数部分作为新的结点
n.wildChild = true
child := &node{
nType: param,
path: wildcard,
}
n.children = []*node{child}
n = child
n.priority++
// 这里的意思是，path在参数后面还没有结束
if len(wildcard) 0 && n.path[len(n.path)-1] == '/' {
panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
}
// 判断在这之前有没有一个/
i--
if path[i] != '/' {
panic("no / before catch-all in path '" + fullPath + "'")
}
n.path = path[:i]
// 设置一个catchAll类型的子节点
child := &node{
wildChild: true,
nType: catchAll,
}
n.children = []*node{child}
n.indices = string('/')
n = child
n.priority++
// 把后面的参数部分设置为新节点
child = &node{
path: path[i:],
nType: catchAll,
handle: handle,
priority: 1,
}
n.children = []*node{child}
return
}
}
// 对应最开头的部分，如果这个path里面没有参数，直接设置
n.path = path
n.handle = handle
}
最关键的几个方法到这里就全部结束啦，先给看到这里的你鼓个掌！
这一部分理解会比较难，可能需要多看几遍。
如果还是有难以理解的地方，欢迎留言交流，或者直接来公众号找我~
About The Author
maynard
懒散，不想无聊