这两天在接触 Gin, 对它的动态路由功能比较感兴趣, 特意做了笔记, 顺便跟 SpringMVC 作下对比.
1. 简介
Gin 是使用 Go/golang 语言实现的 HTTP web 框架. 接口简洁, 性能极高. 截止 1.4.0 版本, 包含测试代码, 仅 14K, 其中测试代码 9K 左右, 也就是说框架源码仅 5K 左右. SpringMVC 不用过多介绍, Java 市场的一把手.
Gin 支持动态路由, 简单示例如下:
- import (
- "github.com/gin-gonic/gin"
- "net/http"
- )
- func main() {
- r := gin.Default()
- r.GET("/hello/:name", func(context *gin.Context) {
- context.String(http.StatusOK, "Hello :"+context.Param("name"))
- })
- r.Run()
- }
对比 SpringMVC 的例子为:
import org.springframework.Web.bind.annotation.PathVariable; import org.springframework.Web.bind.annotation.RequestMapping; import org.springframework.Web.bind.annotation.RestController; @RestController public class HelloWorldController { @RequestMapping("/hello/{name}") public String antUser (@PathVariable("name") String name) { return "Hello :" + name; } }
二者有相似的地方.
2.Gin
Gin 使用 Trie 树来实现动态路由. Trie 树, 即字典树, 又称单词查找树或键树, 是一种树形结构, 是一种哈希树的变种. 典型应用是用于统计和排序大量的字符串(但不仅限于字符串), 所以经常被搜索引擎系统用于文本词频统计. 它的优点是: 最大限度地减少无谓的字符串比较, 查询效率比哈希表高.
Trie 的核心思想是空间换时间. 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的. 它有 3 个基本性质:
根节点不包含字符, 除根节点外每一个节点都只包含一个字符.
从根节点到某一节点, 路径上经过的字符连接起来, 为该节点对应的字符串.
每个节点的所有子节点包含的字符都不相同.
如上图示, 为一个保存了 8 个键的 trie 结构,"A", "to", "tea", "ted", "ten", "i", "in", "inn". 其中, 键标注在节点中, 值标注在节点之下. 每一个完整的英文单词对应一个特定的整数. Trie 可以看作是一个确定有限状态自动机, 尽管边上的符号一般是隐含在分支的顺序中的.
Trie 数的常见应用场景包括:
字符串检索
词频统计
前缀检索
前缀词频统计
对所有的字符串按照字典序排序
Gin 的路由实现也是跟上面的例子类似, 具体实现在 tree.go 文件里, 主要包括 trie 树的构建和查找过程.
2.1. 建树过程
先看 node 的定义
type node struct { path string // 当前节点相对路径, 即公共前缀 indices string // 所有孩子节点的 path[0]组成的字符串, 如果子节点有通配符, 则为空 children []*node // 孩子节点 handlers HandlersChain // 当前节点的处理函数(包括中间件) priority uint32 // 当前节点及子孙节点的实际路由数量 nType nodeType // 节点类型 maxParams uint8 // 子孙节点的最大参数数量 wildChild bool // 孩子节点是否有通配符(wildcard) fullPath string // 完整的请求路径, 各中间节点也有 }
建树过程主要由两个方法来完成
// 根据给定的路径增加一个节点, 主要用于处理公共前缀的分割 func (n *node) addRoute(path string, handlers HandlersChain) { } // 主要用于处理新节点的插入 func (n *node) insertChild(numParams uint8, path string, fullPath string, handlers HandlersChain) { }
流程如下:
使用 addRoute 方法从根节点添加一个新的路径 P, 如果树为空, 则作为新节点直接插入, 此时该节点为树中的第一个节点 (根节点),path 和 fullPath 值都为 P. 如果根节点存在子节点, 则找到 P 跟根节点 path 的公共前缀, 如果不存在公共前缀, 则将新节点作为根节点的子节点加入, 使用 insertChild 方法. 如果存在公共前缀, 则分裂当前节点, 将根节点(当前节点) 公共前缀后的内容独立为一个子节点, 并挂到当前节点下, 更新 indices; 接着获取 P 去掉公共前缀的第一个字符, 判断当前节点 indices 列表是否存在相同的字符, 即判断剩下的内容是要作为新节点加入, 还是要继续分裂, 如果需要继续分裂, 则重复 addRoute 方法.
以下面这段代码为例,
r.GET("/q/query", func(context *gin.Context) { context.String(http.StatusOK,"Hello"+context.Query("name")) }) r.GET("/q/qaz/:name", func(context *gin.Context) { context.String(http.StatusOK,"Hello"+context.Query("name")) }) r.GET("/q/qaj/:name/l", func(context *gin.Context) { context.String(http.StatusOK,"Hello"+context.Query("name")) })
构建的 trie 树为:
这里需要指出的是, 对于通配符,:xxxx 或者 *, 会作为一个单独的节点出现.
2.2. 查找过程
查找过程比较简单, 直接从根节点往下找, 知道找到匹配的节点, 过程如下:
3.SpringMVC
如下为一个简单的示例:
@RestController public class HelloWorldController { @RequestMapping("/hello/{name}") public String antUser (@PathVariable("name") String name) { return "hello :" + name; } }
之前在介绍《SpringMVC 加载流程》是说过, Spring MVC 路由的加载是由 RequestMappingHandlerMapping 来处理的. 该类会查找所有符合条件的 Method 上的注解, 然后添加到父类 AbstractHandlerMethodMapping 的 MappingRegistry 中封装为 HandlerMethod 进行缓存, 直接以 HashMap 的方式. 除了 RequestMappingHandlerMapping 外还有其他 HandlerMapping, 如 SimpleUrlHandlerMapping,BeanNameUrlHandlerMapping 等.
当查找符合的 HandlerMethod 时会遍历所有的 HandlerMapping, 如果某 HandlerMapping 能够处理, 返回对应的 HandlerExecutionChain, 同时退出循环, 由 HandlerAdapter 来执行具体的 Method,Apdater 会完成入参的注入. 而 RequestMappingHandler 的动态路由则体现在 HandlerMethod 的查找上, 该功能主要由 AbstractHandlerMethodMapping 的 lookupHandlerMethod 方法来实现. lookupHandlerMethod 方法会遍历 MappingRegistry 中的所有注册对象, 通过 PatternsRequestCondition 的 getMatchingCondition 来判断, 具体交由 AntPathMatcher 来实现.
AntPathMatcher 主要用来做类 URLs 字符串匹配, 可以匹配的规则如下:
? 匹配一个字符
* 匹配 0 个或多个字符
** 匹配 0 个或多个目录
具体实现在 doMatch 方法中.
即 SpringMVC 是通过遍历所有注册的 Url, 对每个 Url 应用 AntPathMatcher 来判断当前请求的 Url 是否符合注册的通配符写法, 从而找到对应的处理函数.
如下为简单的示意图:
4. 参考
https://zh.wikipedia.org/wiki/Trie
来源: http://www.tuicool.com/articles/qMBfiyV