/

Gin框架的路由是怎么实现的?

该篇文章首发于boyn.top,转载请声明 题图来源于Gin框架Logo

Gin框架简介

Gin框架是Go语言实现的一款轻量级的网络框架,它兼具生产力和速度.在工业界被广泛应用

对于我们来说,Gin是一款非常易用的网络框架,无需太多配置,写很少的代码量,就可以搭建起来一个简单的Web应用.但是对于很多同学而言,Gin框架仅仅只是停留在用的阶段,却不知道,Gin框架的设计也是非常优秀的.

这篇文章中,我们将会浅析Gin框架中Mux的设计,Mux即多路复用器,也就是路由树.

Mux使用了什么数据结构?

Gin的路由使用的是Github上的一个开源库httpRouter,在它的README中,我们知道,它使用的是压缩前缀树,也就是我们常说的Radix Tree,能够将有公共前缀的结点共享公共的字符串,它的优点在于相比起前缀树,它能够更有效地节省内存,我们找到了一张benchmark的图片,来看看HttpRouter的实际表现

image-20200331201024860

可以看到,HttpRouter排在了第二位,还是十分优秀的.

Mux在Gin中的表示方法

在Gin中,我们要添加一个路由的话,可以通过GET(),POST()方法来进行.

在Gin的主结构Engine中,有一个表示方法树的变量type methodTrees []methodTree,它们代表着不同方法对应的路由,如GET,POST都会对应到不同的方法树当中去.每一个方法树的根结点中包含这棵树所对应的方法以及路由树的根节点

1
2
3
4
type methodTree struct {
method string
root *node
}

而本篇文章的重点,就是在于这个root变量.

我们先来看看这个node的基本结构

1
2
3
4
5
6
7
8
9
10
11
type node struct {
path string //该节点的路径
indices string //该节点所有子节点的首字母集合
children []*node // 子节点数组
handlers HandlersChain //handlers处理链
priority uint32 // 优先级(该节点的所有子节点数量)
nType nodeType //node的类型,static静态节点,root根节点,param单参数节点,catchAll多参数节点
maxParams uint8 //子节点最大参数的数量
wildChild bool // 是否为通配符节点(上面的param或catchAll)
fullPath string // 从根节点到这个节点的全路径
}

在Mux中添加一个路由

我们在外面通过route.GET等方法可以添加一个路由到Mux中,但是其内部是怎么做的呢?下面我们给出详细的流程图以及解释.构建的过程其实就是在不断地寻找最长前缀的过程

Gin 路由添加与查找流程图

其实Mux的添加过程,与trie树是十分相似的,因为Radix Tree就是一种压缩后的Trie树.我们来简单地说一下它的流程,详细过程可以参照Trie树的插入过程,Radix与Trie的不同在于它会将多个具有共同前缀的节点抽取出一个前缀作为单个节点.

而在Gin中,为了保证效率,还有一个优先级的设定.某个节点的优先级=它的子节点数量.

关于图片和转载

知识共享许可协议
本作品采用知识共享署名 4.0 国际许可协议进行许可。 转载时请注明原文链接,图片在使用时请保留图片中的全部内容,可适当缩放并在引用处附上图片所在的文章链接,图片使用 Sketch 进行绘制,你可以在 技术文章配图指南 一文中找到画图的方法和素材。