GoFast（二）| 路由核心基于RadixTree

很多场景中，高效的数据结构都离不开树状结构，什么完全二叉树、红黑树、Radix树、图等好多名词都是具备子孙节点的树状结构，自由灵活的节点内容更让使用者扑朔迷离。一般树都是通过链表来实现，也有通过数组实现的；链表实现自由灵活相对简单，数组实现比较复杂而且不能随意变更节点数量，有其局限性，但是数组实现的内存占用更小更高效。GoFast将采用数组来实现路由RadixTree。

为什么路由采用RadixTree

在开发Web应用后台的时候，指定了URL和对应的处理逻辑；客户的请求如何快速的定位到对应的业务逻辑呢？这个匹配算法决定了应用的性能。常用的方法有很多，比如：哈希、正则匹配、树查找。

哈希性能不错，但是无法模糊匹配路由。
正则可以模糊匹配，但是性能太差。
树是非常高效的搜索数据结构，还能实现模糊匹配。

你会发现很多优秀的Web框架都采用RadixTree来实现核心路由，比如Node.js中的fastify和Go中的Gin都是如此。毫无疑问，为了追求尽量的高效，我们也采用RadixTree来实现路由。

看看RadixTree的实现原理：https://www.pianshen.com/article/388263675/

Gin的路由实现

Gin的路由树借用了 httprouter 的实现，稍微做了些调整，下面我们看看他的节点定义：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


type node struct {
	path      string		// 16
	indices   string		// 16
	wildChild bool			// 1
	nType     nodeType		// 1
	priority  uint32		// 4
	children  []*node		// 24
	handlers  HandlersChain	// 24
	fullPath  string		// 16
}

每个节点占用多少字节呢（先不考虑内存对齐的问题）？数数后面的数字就知道了，是102字节。如果一个应用路由树最后产生了100个节点，那么仅这棵路由树大概占用10KB的内存，如果是1000个节点，就要占用100KB内存。这还只是算这颗路由树结构，还是有点占内存的。

说Gin的路由树节点只是一个引子，从这里出发，下面来说说GoFast如何来整体改变这个实现逻辑。

GoFast路由实现

节点内存占用问题，来看看GoFast的实现，全是基于数组的索引，具体的值全部保存在各自的数组当中：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


type radixMiniNode struct {
	// 前缀字符（3字节）
	matchLen   uint8
	matchStart uint16

	// 子节点（3字节）
	childLen   uint8
	childStart uint16

	// 分组事件索引+当前路由匹配节点事件索引（4字节）
	hdsGroupIdx int16
	hdsItemIdx  int16

	// 节点类型 （1字节）
	nType uint8
}

这个节点只需要占用11个字节，即使内存对齐也只占用16字节。而整棵树的节点分布是一模一样的；这一点上GoFast内存占用要远少于Gin。

问题来了，你把节点改的这么小，不会在别的地方会增加损耗吧？

接下来我们逐一分析。

前缀字符

先看一个简单的RadixTree示例：

(GET)
└── /admin                                                       [false-/2]
    ├── /chende                                                  [true-]
    └── 2/                                                       [false-zg]
        ├── zht                                                  [true-]
        └── group2/lmx                                           [true-]
(POST)
└── /root                                                        [true-]

Gin调试之后，看看下面的数据结构：

GoFast的实现，全部是索引，看不到具体值，具体值存在数组中：

上面图中能看出GET Method下面的路由树，根节点中path，在matchStart=0 matchLen=6 中能找到对应的字符串，下面看看GoFast内部小型数据中心是否能找到这些值：

看到没有treeChars[0:6]刚好就是/admin。这就是GoFast的套路。

子节点

根有两个子节点，一个对应路由片段2/，另一个对应/chende，这两个子节点分别以字符2、/开头，那么父节点中索引标志字段indices="2/"，路由向下查找的时候就是按照这个字符串中的前后顺序来比对下一个要匹配的节点可能是第几个，定位到索引之后，直接到children中找对应位置的节点即可。

看看Gin的实现，明文的：

再看看GoFast的情况：两个子节点通过索引也能找到对应的字符串。细心的朋友可能会发现这里两个子节点的顺序好像和上面Gin的不一样？的确是这样的，这个问题以后专门讨论（可以实现更高效的节点索引）。

处理函数（handlers）

Gin的实现，直接看到某个节点下面绑定的一个处理函数。

GoFast的实现是什么样的呢？下一篇文章将事件处理函数的时候再详细说明这个设计。

（未完待续…）

系列文章导航