分享一波gin的路由算法
- gin是什么呢？
- gin有啥特性呢？
- gin大致都包含了哪些知识点？
- 路由是什么？
- gin里面的路由
- 算法是什么？
- gin的路由算法
- 普通注册路由
- 使用中间件的方式注册路由
- 总结
gin的路由算法分享
gin是什么呢？
我们在github上看看官方简介
Gin is a web framework written in Go (Golang). It features a martini-like API with performance that is up to 40 times faster thanks to httprouter. If you need performance and good productivity, you will love Gin.
Gin 是用 Go 开发的一个微框架，Web框架，类似 Martinier 的 API，接口简洁，性能极高，也因为 httprouter的性能提高了 40 倍。
如果你需要良好的表现和工作效率，你会喜欢Gin。
img
gin有啥特性呢？
tag | 说明 |
|---|---|
异常处理 | 服务始终可用，不会宕机。Gin 可以捕获 panic，并恢复。而且有极为便利的机制处理HTTP请求过程中发生的错误。 |
路由分组 | 可以将需要授权和不需要授权的API分组，不同版本的API分组。而且分组可嵌套，且性能不受影响。例如v1/xxx/xxx v2/xxx/xxx |
渲染内置 | 原生支持JSON，XML和HTML的渲染。 |
JSON | Gin可以解析并验证请求的JSON。这个特性对Restful API的开发尤其有用。 |
中间件 | HTTP请求，可先经过一系列中间件处理就向日志Logger，Authorization等。中间件机制也极大地提高了框架的可扩展性。 |
gin大致都包含了哪些知识点？
gin的实战演练我们之前也有分享过，我们再来回顾一下，gin大致都包含了哪些知识点
:路由和*路由- query查询参数
- 接收数组和 Map
- Form 表单
- 单文件和多文件上传
- 分组路由，以及路由嵌套
- 路由中间件
- 各种数据格式的支持，json、struct、xml、yaml、protobuf
- HTML模板渲染
- url重定向
- 异步协程等等
要是朋友们对gin还有点兴趣的话，可以点进来看看，这里有具体的知识点对应的案例gin实战演练
路由是什么？
我们再来了解一下路由是什么
路由器是一种连接多个网络或网段的网络设备，它能将不同网络或网段之间的数据信息进行“翻译”，以使它们能够相互“读”懂对方的数据，从而构成一个更大的网络。
路由器有两大典型功能
- 即数据通道功能
包括转发决定、背板转发以及输出链路调度等，一般由特定的硬件来完成
- 控制功能
一般用软件来实现，包括与相邻路由器之间的信息交换、系统配置、系统管理等
gin里面的路由
路由是web框架的核心功能。
写过路由的朋友最开始是不是这样看待路由的：
- 根据路由里的
/把路由切分成多个字符串数组 - 然后按照相同的前子数组把路由构造成树的结构
当需要寻址的时候，先把请求的 url 按照 / 切分，然后遍历树进行寻址，这样子有点像是深度优先算法的递归遍历，从根节点开始，不停的向根的地方进行延伸，知道不能再深入为止，算是得到了一条路径
举个栗子
定义了两个路由 /v1/hi，/v1/hello
那么这就会构造出拥有三个节点的路由树，根节点是 v1，两个子节点分别是 hi hello。
上述是一种实现路由树的方式，这种是比较直观，容易理解的。对 url 进行切分、比较，可是时间复杂度是 O(2n)，那么我们有没有更好的办法优化时间复杂度呢？大名鼎鼎的GIn框架有办法，往后看
算法是什么？
再来提一提算法是啥。
算法是解决某个问题的计算方法、步骤，不仅仅是有了计算机才有算法这个名词/概念的，
例如我们小学学习的九九乘法表
中学学习的各种解决问题的计算方法，例如物理公式等等
现在各种吃播大秀厨艺，做法的流程和方法也是算法的一种
- 面临的问题是bug ， 解决的方法不尽相同，步骤也大相径庭
- 面临猪蹄，烹饪方法各有特色
- 面临我们生活中的难题，也许每个人都会碰到同样的问题，可是每个人解决问题的方式方法差异也非常大，有的人处理事情非常漂亮，有的人拖拖拉拉，总留尾巴
大学里面学过算法这本书，算法是计算机的灵魂，面临问题，好的算法能够轻易应对且健壮性好
面临人生难题，好的解决方式，也同样能够让我们走的更远，更确切有点来说，应该是好的思维模型。
算法有如下五大特征
每个事物都会有自己的特点，否则如何才能让人记忆深刻呢
- 有限性 ， 算法得有明确限步之后会结束
- 确切性，每一个步骤都是明确的，涉及的参数也是确切的
- 输入，算法有零个或者多个输入
- 输出，算法有零个或者多个输出
- 可行性，算法的每一个步骤都是可以分解出来执行的，且都可以在有限时间内完成
gin的路由算法
那我们开始进入进入正题，gin的路由算法，千呼万唤始出来
gin的路由算法类似于一棵前缀树
只需遍历一遍字符串即可，时间复杂度为O(n)。比上面提到的方式，在时间复杂度上来说真是大大滴优化呀
不过，仅仅是对于一次 http 请求来说，是看不出啥效果的
诶，敲黑板了，什么叫做前缀树呢？
Trie树，又叫字典树、前缀树（Prefix Tree），是一种多叉树结构
画个图，大概就能明白前缀树是个啥玩意了
这棵树还和二叉树不太一样，它的键不是直接保存在节点中，而是由节点在树中的位置决定
一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。
例如上图，我们一个一个的来寻址一下，会有这样的字符串
- MAC
- TAG
- TAB
- HEX
前缀树有如下几个特点：
- 前缀树除根节点不包含字符，其他节点都包含字符
- 每个节点的子节点包含的字符串不相同
- 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
- 每个节点的子节点通常有一个标志位，用来标识单词的结束
有没有觉得这个和路由的树一毛一样？
gin的路由树算法类似于一棵前缀树. 不过并不是只有一颗树, 而是每种方法**(POST, GET ，PATCH...)**都有自己的一颗树
例如，路由的地址是
- /hi
- /hello
- /:name/:id
那么gin对应的树会是这个样子的
GO中 路由对应的节点数据结构是这个样子的
type node struct {
path string
indices string
children []*node
handlers HandlersChain
priority uint32
nType nodeType
maxParams uint8
wildChild bool
}
具体添加路由的方法，实现方法是这样的
func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
assert1(path[0] == '/', "path must begin with '/'")
assert1(method != "", "HTTP method can not be empty")
assert1(len(handlers) > 0, "there must be at least one handler")
debugPrintRoute(method, path, handlers)
// 此处可以好好看看
root := engine.trees.get(method)
if root == nil {
root = new(node)
engine.trees = append(engine.trees, methodTree{method: method, root: root})
}
root.addRoute(path, handlers)
}
仔细看，gin的实现不像一个真正的树
因为他的children []*node所有的孩子都会放在这个数组里面，具体实现是，他会利用indices, priority变相的去实现一棵树
我们来看看不同注册路由的方式有啥不同？每一种注册方式，最终都会反应到gin的路由树上面
普通注册路由
普通注册路由的方式是 router.xxx，可以是如下方式
- GET
- POST
- PATCH
- PUT
- ...
router.POST("/hi", func(context *gin.Context) {
context.String(http.StatusOK, "hi xiaomotong")
})
也可以以组Group的方式注册，以分组的方式注册路由，便于版本的维护
v1 := router.Group("v1")
{
v1.POST("hello", func(context *gin.Context) {
context.String(http.StatusOK, "v1 hello world")
})
}
在调用POST, GET, PATCH等路由HTTP相关函数时, 会调用handle函数
func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
absolutePath := group.calculateAbsolutePath(relativePath) // calculateAbsolutePath
handlers = group.combineHandlers(handlers) // combineHandlers
group.engine.addRoute(httpMethod, absolutePath, handlers)
return group.returnObj()
}
calculateAbsolutePath 和 combineHandlers 还会再次出现
调用组的话，看看是咋实现的
func (group *RouterGroup) Group(relativePath string, handlers ...HandlerFunc) *RouterGroup {
return &RouterGroup{
Handlers: group.combineHandlers(handlers),
basePath: group.calculateAbsolutePath(relativePath),
engine: group.engine,
}
}
同样也会调用 calculateAbsolutePath 和 combineHandlers 这俩函数，我们来看看 这俩函数是干啥的，看到函数名字，也许大概也能猜出个所以然了吧，来看看源码
img
func (group *RouterGroup) combineHandlers(handlers HandlersChain) HandlersChain {
finalSize := len(group.Handlers) + len(handlers)
if finalSize >= int(abortIndex) {
panic("too many handlers")
}
mergedHandlers := make(HandlersChain, finalSize)
copy(mergedHandlers, group.Handlers)
copy(mergedHandlers[len(group.Handlers):], handlers)
return mergedHandlers
}
func (group *RouterGroup) calculateAbsolutePath(relativePath string) string {
return joinPaths(group.basePath, relativePath)
}
func joinPaths(absolutePath, relativePath string) string {
if relativePath == "" {
return absolutePath
}
finalPath := path.Join(absolutePath, relativePath)
appendSlash := lastChar(relativePath) == '/' && lastChar(finalPath) != '/'
if appendSlash {
return finalPath + "/"
}
return finalPath
}
joinPaths函数在这里相当重要，主要是做拼接的作用
从上面来看，可以看出如下2点：
- 调用中间件, 是将某个路由的handler处理函数和中间件的处理函数都放在了Handlers的数组中
- 调用Group, 是将路由的path上面拼上Group的值. 也就是/hi/:id, 会变成v1/hi/:id
使用中间件的方式注册路由
我们也可以使用中间件的方式来注册路由，例如在访问我们的路由之前，我们需要加一个认证的中间件放在这里，必须要认证通过了之后，才可以访问路由
router.Use(Login())
func (group *RouterGroup) Use(middleware ...HandlerFunc) IRoutes {
group.Handlers = append(group.Handlers, middleware...)
return group.returnObj()
}
不管是普通的注册，还是通过中间件的方式注册，里面都有一个关键的handler
handler方法 调用 calculateAbsolutePath 和 combineHandlers 将路由拼接好之后，调用addRoute方法，将路由预处理的结果注册到gin Engine的trees上，来在看读读handler的实现
func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
absolutePath := group.calculateAbsolutePath(relativePath) // <---
handlers = group.combineHandlers(handlers) // <---
group.engine.addRoute(httpMethod, absolutePath, handlers)
return group.returnObj()
}
那么，服务端写好路由之后，我们通过具体的路由去做http请求的时候，服务端是如何通过路由找到具体的处理函数的呢？
我们仔细追踪源码， 我们可以看到如下的实现
...
// 一棵前缀树
t := engine.trees
for i, tl := 0, len(t); i < tl; i++ {
if t[i].method != httpMethod {
continue
}
root := t[i].root
// Find route in tree
// 这里通过 path 来找到相应的 handlers 处理函数
handlers, params, tsr := root.getValue(path, c.Params, unescape)
if handlers != nil {
c.handlers = handlers
c.Params = params
// 在此处调用具体的 处理函数
c.Next()
c.writermem.WriteHeaderNow()
return
}
if httpMethod != "CONNECT" && path != "/" {
if tsr && engine.RedirectTrailingSlash {
redirectTrailingSlash(c)
return
}
if engine.RedirectFixedPath && redirectFixedPath(c, root, engine.RedirectFixedPath) {
return
}
}
break
}
...
func (c *Context) Next() {
c.index++
for c.index < int8(len(c.handlers)) {
c.handlers[c.index](c)
c.index++
}
}
当客户端请求服务端的接口时， 服务端此处 handlers, params, tsr := root.getValue(path, c.Params, unescape) ， 通过 path 来找到相应的 handlers 处理函数，
将handlers ， params 复制给到服务中，通过 c.Next()来执行具体的处理函数，此时就可以达到，客户端请求响应的路由地址，服务端能过对响应路由做出对应的处理操作了
总结
- 简单回顾了一下gin的特性
- 介绍了gin里面的路由
- 分享了gin的路由算法，以及具体的源码实现流程
img
好了，本次就到这里，下一次 分享 最常用的限流算法以及如何在http中间件中加入流控，
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是小魔童哪吒，欢迎点赞关注收藏，下次见~
腾讯云开发者
