内容简介:在上一篇文章中,我们聊了聊在Golang中怎么实现一个Http服务器。但是在最后我们可以发现,固然由所以在这篇文章中,我们将分析
摘要
在上一篇文章中,我们聊了聊在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(path) { path = path[i:] // 此时如果n的子节点是带参数的 if n.wildChild { n = n.children[0] n.priority++ // 判断是否会不合法 if len(path) >= 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) < 2 { panic("wildcards must be named with a non-empty name in path '" + fullPath + "'") } if len(n.children) > 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) < len(path) { // 把参数后面那部分再分出一个结点,continue继续处理 path = path[len(wildcard):] child := &node{ priority: 1, } n.children = []*node{child} n = child continue } // 把处理器设置进去 n.handle = handle return } else { // 另外一种情况 if i+len(wildcard) != len(path) { panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'") } if len(n.path) > 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 }
最关键的几个方法到这里就全部结束啦,先给看到这里的你鼓个掌!
这一部分理解会比较难,可能需要多看几遍。
如果还是有难以理解的地方,欢迎留言交流,或者直接来公众号找我~
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Go语言经典库使用分析(七)| 高性能可扩展 HTTP 路由 httprouter
- OpenResty 社区王院生:lua-resty-r3 高性能 OpenResty 路由实现
- vue路由篇(动态路由、路由嵌套)
- 小程序封装路由文件和路由方法,5种路由方法全解析
- Vue的路由及路由钩子函数
- gin 源码阅读(二)-- 路由和路由组
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。