本文指的路由,不是路由器,也不是PS4(5?),是特指后端API框架里的router,前端路由也有可以有借鉴的部分,但本文不承诺正确性。

今天不妨讨论个不那么大的话题,restful路由的实现。

我们眼中的路由是什么样子的?

我们常见的路由是这个样子的

router.get('/what/i/want', ... );

router.get('/what/i/hate', ... );

router.get('/what/u/want', ... );

我们今天就来讨论一下,当我们想访问 /what/i/want时,都有些什么玄机。

路由是怎么工作的

首先明确路由的目的,就是根据接收到的路径字符串,找到对应的业务处理逻辑。

为了弄明白业界常用框架对这一块,我专门查阅了若干开发框架的源码(express, koa, Gin, kratos, Lumen),最终概括成两种实现手段。

  • Key - Value 型路由
  • Tree 型路由

现在来分析一下两种路由的特性和适用场景。

Key - Value 型路由

这个模式,形如我们熟悉的hash table、字典,通过键值对维护这uri与函数的对应关系。

我们理所当然地认为,只要确定的访问地址, 如/what/i/want, 就能立即找到对应的业务方法functionA,是个铁骨铮铮的 O(1)操作。

当一个操作的复杂度与规模无关,就是一个O(1)的操作。比如无论我的 uri 地址有多少个,只要确定 uri 的值,总是能立即确定与之对应的方法。

然而遗憾的是,我就没见到有这么实现路由的。

真实的情况是,

Key - Value 型路由会从前到后一个一个比较,直到找到一个能匹配当前 uri 的key,再确定它对应的 function

所以实际上它是一个 O(n) 操作,平均情况下需要比较 N/2 次才能定位。

一个 O(n) 操作,其复杂度会随着数据规模的增大而线性增长,而我们普遍认为,在经过多次测量观察后,平均情况下会在 N/2 的位置上找到答案。

疑惑归疑惑,正如本文的作者一样,做轮子人并不是疯了。

之所以采用这种逐个匹配的模式,是因为我们的uri通过是不能确定的。

比如, 一些uri里甚至包含了变量

GET /staff/9527

GET /staff/709394

所以,我们通常是吧 Key - Value里面的Key,设计成正则表达式

相应的,在理论研究中的Hash Table也会被顺序表替代。

总结起来就是,


当我们访问一个确定的uri时,路由会尝试按顺序逐个匹配注册好的正则表达式,直到match到一个结果。

否则,返回 404


升华一下

如何压榨这种路由的性能? 既然是按顺序逐个匹配,那我们就根据自己的业务特点,把可能访问量最大的接口注册到前面去。

也有一些框架是会动态调整顺序的,这就是题外话。

--

Tree 型路由

这个模式相对来说思路要骚一些。

它把uri按照/分割一个,在之前构建好的路由树里,一个节点一个几点的检索,直到成功走到一个叶子节点。

与上面提到的N/2次比较相比,这个模式的比较次数比较稳定,就是uri的层数。

对于 /what/i/want,我们认为它是一个 3 层的地址,如果这个地址是存在的,那么在比较3次以后,就能找到对应的答案。

真是 “遇事不决,数据结构” 啊

这种树形的路由特别适合restful风格的API,因为我们设计restful接口的时候,通常每一层都有它自己的类聚含义,所以它会构建出一棵非常标致的树。

问(gang)题(jing)来了

Q1: 请问 Tree 型路由 怎么解决uri里有变量的情况呢?

很巧妙。当你注册的路由包含了变量,比如 /staff/:id这样的,它会在这个树staff的子节点里,也就第二层,创建一个通配节点(可能是*)。

它认为,不管staff后面跟什么内容,都能匹配这个*

Q2: 如果我同时注册了/staff/:id/staff/list呢?会匹配错吗?

考虑到这种情况,Tree 型路由的一般实现是,优先匹配确定值list,次要匹配*

有这种情况是要复杂一些,不过并不影响它的整体复杂度。

最后,作者喜欢哪一种?

尽管我在最近开发的一个框架里使用了Tree 型路由,这并不代表我的倾向。

实际上应该根据上文提到两种模式各自的特点,选择最好的实现方式。

当然

我期待读者自己做轮子的时候,能做出一个根据开发者注册的路由的特点,自动选择路由模型的智能路由


好了,今天先到这里,下次再会。