本文指的路由,不是路由器,也不是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 型路由,这并不代表我的倾向。
实际上应该根据上文提到两种模式各自的特点,选择最好的实现方式。
当然
我期待读者自己做轮子的时候,能做出一个根据开发者注册的路由的特点,自动选择路由模型的智能路由。
好了,今天先到这里,下次再会。