[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中间件中退出流控，

技术是凋谢的，咱们的心态，更应是凋谢的。拥抱变动，背阴而生，致力向前行。

我是小魔童哪吒，欢送点赞关注珍藏，下次见~

关于后端:分享一波gin的路由算法

gin的路由算法分享

gin是什么呢？

gin有啥个性呢？

gin大抵都蕴含了哪些知识点？

路由是什么？

gin外面的路由

算法是什么？

gin的路由算法

一般注册路由

应用中间件的形式注册路由

总结

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于后端:分享一波gin的路由算法

gin的路由算法分享

gin是什么呢？

gin有啥个性呢？

gin大抵都蕴含了哪些知识点？

路由是什么？

gin外面的路由

算法是什么？

gin的路由算法

一般注册路由

应用中间件的形式注册路由

总结

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复