分享一波gin的路由算法

[TOC]

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。

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），是一种多叉树结构

画个图，大概就能明白前缀树是个啥玩意了

这棵树还和二叉树不太一样，它的键不是直接保存在节点中，而是由节点在树中的位置决定

一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

例如上图，我们一个一个的来寻址一下，会有这样的字符串

前缀树有如下几个特点：

前缀树除根节点不包含字符，其他节点都包含字符
每个节点的子节点包含的字符串不相同
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的子节点通常有一个标志位，用来标识单词的结束

有没有觉得这个和路由的树一毛一样？

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 这俩函数，我们来看看这俩函数是干啥的，看到函数名字，也许大概也能猜出个所以然了吧，来看看源码

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 的路由算法，以及具体的源码实现流程

好了，本次就到这里，下一次分享最常用的限流算法以及如何在 http 中间件中加入流控，

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是小魔童哪吒，欢迎点赞关注收藏，下次见～

本作品采用《CC 协议》，转载必须注明作者和本文链接

关注微信公众号：阿兵云原生

分享一波gin的路由算法

gin 的路由算法分享#

gin 是什么呢？#

gin 有啥特性呢？#

gin 大致都包含了哪些知识点？#

路由是什么？#

gin 里面的路由#

算法是什么？#

gin 的路由算法#

普通注册路由#

使用中间件的方式注册路由#

总结#

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

分享一波gin的路由算法

gin 的路由算法分享#

gin 是什么呢？#

gin 有啥特性呢？#

gin 大致都包含了哪些知识点？#

路由是什么？#

gin 里面的路由#

算法是什么？#

gin 的路由算法#

普通注册路由#

使用中间件的方式注册路由#

总结#

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录