美文网首页
分享一波gin的路由算法分享

分享一波gin的路由算法分享

作者: 阿兵云原生 | 来源:发表于2021-06-04 22:54 被阅读0次

[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

img

gin有啥特性呢?

tag 说明
异常处理 服务始终可用,不会宕机。<br />Gin 可以捕获 panic,并恢复。而且有极为便利的机制处理HTTP请求过程中发生的错误。
路由分组 可以将需要授权和不需要授权的API分组,不同版本的API分组。<br />而且分组可嵌套,且性能不受影响。<br />例如v1/xxx/xxx v2/xxx/xxx
渲染内置 原生支持JSON,XML和HTML的渲染。
JSON Gin可以解析并验证请求的JSON。<br />这个特性对Restful API的开发尤其有用。
中间件 HTTP请求,可先经过一系列中间件处理<br />就向日志Logger,Authorization等。<br />中间件机制也极大地提高了框架的可扩展性。

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

image

gin的实战演练我们之前也有分享过,我们再来回顾一下,gin大致都包含了哪些知识点

  • :路由*路由
  • query查询参数
  • 接收数组和 Map
  • Form 表单
  • 单文件和多文件上传
  • 分组路由,以及路由嵌套
  • 路由中间件
  • 各种数据格式的支持,json、struct、xml、yaml、protobuf
  • HTML模板渲染
  • url重定向
  • 异步协程等等

要是朋友们对gin还有点兴趣的话,可以点进来看看,这里有具体的知识点对应的案例gin实战演练

路由是什么?

我们再来了解一下路由是什么

路由器是一种连接多个网络或网段的网络设备,它能将不同网络或网段之间的数据信息进行“翻译”,以使它们能够相互“读”懂对方的数据,从而构成一个更大的网络。

路由器有两大典型功能

  • 即数据通道功能

包括转发决定、背板转发以及输出链路调度等,一般由特定的硬件来完成

  • 控制功能

一般用软件来实现,包括与相邻路由器之间的信息交换、系统配置、系统管理等

gin里面的路由

路由是web框架的核心功能

写过路由的朋友最开始是不是这样看待路由的:

  • 根据路由里的 / 把路由切分成多个字符串数组
  • 然后按照相同的前子数组把路由构造成树的结构

当需要寻址的时候,先把请求的 url 按照 / 切分,然后遍历树进行寻址,这样子有点像是深度优先算法的递归遍历,从根节点开始,不停的向根的地方进行延伸,知道不能再深入为止,算是得到了一条路径

举个栗子

定义了两个路由 /v1/hi/v1/hello

那么这就会构造出拥有三个节点的路由树,根节点是 v1,两个子节点分别是 hi hello

image

上述是一种实现路由树的方式,这种是比较直观,容易理解的。对 url 进行切分、比较,可是时间复杂度是 O(2n),那么我们有没有更好的办法优化时间复杂度呢?大名鼎鼎的GIn框架有办法,往后看

算法是什么?

再来提一提算法是啥。

算法是解决某个问题的计算方法、步骤,不仅仅是有了计算机才有算法这个名词/概念的,

例如我们小学学习的九九乘法表

中学学习的各种解决问题的计算方法,例如物理公式等等

现在各种吃播大秀厨艺,做法的流程和方法也是算法的一种

image
  • 面临的问题是bug , 解决的方法不尽相同,步骤也大相径庭
  • 面临猪蹄,烹饪方法各有特色
  • 面临我们生活中的难题,也许每个人都会碰到同样的问题,可是每个人解决问题的方式方法差异也非常大,有的人处理事情非常漂亮,有的人拖拖拉拉,总留尾巴

大学里面学过算法这本书,算法是计算机的灵魂,面临问题,好的算法能够轻易应对且健壮性好

面临人生难题,好的解决方式,也同样能够让我们走的更远,更确切有点来说,应该是好的思维模型。

算法有如下五大特征

每个事物都会有自己的特点,否则如何才能让人记忆深刻呢

  • 有限性 , 算法得有明确限步之后会结束
  • 确切性,每一个步骤都是明确的,涉及的参数也是确切的
  • 输入,算法有零个或者多个输入
  • 输出,算法有零个或者多个输出
  • 可行性,算法的每一个步骤都是可以分解出来执行的,且都可以在有限时间内完成

gin的路由算法

那我们开始进入进入正题,gin的路由算法,千呼万唤始出来

gin的是路由算法类似于一棵前缀树

只需遍历一遍字符串即可,时间复杂度为O(n)。比上面提到的方式,在时间复杂度上来说真是大大滴优化呀

不过,仅仅是对于一次 http 请求来说,是看不出啥效果的

诶,敲黑板了,什么叫做前缀树呢?

Trie树,又叫字典树前缀树(Prefix Tree),是一种多叉树结构

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

image

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

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

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

  • MAC
  • TAG
  • TAB
  • HEX

前缀树有如下几个特点:

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

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

gin的路由树算法类似于一棵前缀树. 不过并不是只有一颗树, 而是每种方法(POST, GET ,PATCH...)都有自己的一颗树

例如,路由的地址是

  • /hi
  • /hello
  • /:name/:id

那么gin对应的树会是这个样子的

image

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()
}

calculateAbsolutePathcombineHandlers 还会再次出现

调用组的话,看看是咋实现的

func (group *RouterGroup) Group(relativePath string, handlers ...HandlerFunc) *RouterGroup {
    return &RouterGroup{
        Handlers: group.combineHandlers(handlers),
        basePath: group.calculateAbsolutePath(relativePath),
        engine:   group.engine,
    }
}

同样也会调用 calculateAbsolutePathcombineHandlers 这俩函数,我们来看看 这俩函数是干啥的,看到函数名字,也许大概也能猜出个所以然了吧,来看看源码

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方法 调用 calculateAbsolutePathcombineHandlers 将路由拼接好之后,调用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请求的时候,服务端是如何通过路由找到具体的处理函数的呢?

image

我们仔细追踪源码, 我们可以看到如下的实现

...
// 一棵前缀树
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 处理函数,

handlersparams 复制给到服务中,通过 c.Next()来执行具体的处理函数,此时就可以达到,客户端请求响应的路由地址,服务端能过对响应路由做出对应的处理操作了

总结

  • 简单回顾了一下gin的特性
  • 介绍了gin里面的路由
  • 分享了gin的路由算法,以及具体的源码实现流程
img

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

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

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

相关文章

网友评论

      本文标题:分享一波gin的路由算法分享

      本文链接:https://www.haomeiwen.com/subject/fkmfeltx.html