我可能实现了个高性能 HTTP 路由器

这篇文章介绍一下我用 Go 语言实现的一个 HTTP 路由器（HTTP router）的原理以及优化方式，代码仓库在这。压测结果和目前同样基于 Go 标准库实现的最快的 httprouter 不相上下，且在匹配动态路由的时候比它少一次内存分配。两者使用的是相同的压测代码和测试环境。

背景

Go 语言标准库提供了完整的 HTTP 协议解析器，并将请求的处理抽象成了 http.Handler 接口，该接口就是传统意义上的 controller。只要对象实现了该接口的 ServeHTTP 方法，就能传入 http.Server，接收并处理 HTTP 请求。如下

1
2
3
4
5
6
7
8
9
type handler struct {}

func (h handler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    // 处理请求
}

func main() {
    http.ListenAndServe(":8000", new(handler))
}

这样，handler 就能收到并处理任何发到 8000 端口的 HTTP 请求。但我们大多数时候需要使用不同的 handler 来处理不同方法、不同路径来的请求，如下面 2 个常见的请求需要 2 个 handler 来分别处理（为方便显示，省略了协议和域名部分）。

GET /user/profile
GET /book/introduction

一种最简单的实现方式是在上面 handler 的 ServeHTTP 方法里使用条件判断，如 switch，匹配请求的方法和路径，再在 case 里调用对应的函数来处理。这种方式实现起来十分简单而且处理得很快，但对于有很多路由的服务端程序，需要写很长的条件判断语句。基于 HTTP 的微服务框架 twirp 就是使用的这种方式来处理不同路径的请求，因为微服务一般是不需要很多路由的。

另一种优雅点的方式是将路由信息存储在一个哈希表里（下称 map），路径作为键，处理请求的函数或方法作为值，这样便实现了时间复杂度为 O(1) 的路由查找。Go 语言标准库提供的便是这种方法，实现在 http.ServeMux 结构体中（Mux 就是指的 multiplexer，意思是「多路复用器」，和 Linux IO 复用有类似的含义。后来很多 Go 语言实现的 HTTP 路由器库或框架都沿用了这个词）

但这种方式不利于实现「动态路由」。以 GitHub 为例

GET /bob/web
GET /alice/wob
GET /jack/wab

这 3 个请求希望访问到 Bob, Alice, Jack 三个人不同的仓库，若使用上面所说的基于哈希表的方式，那作为键的路由是什么呢？

所以我们希望只通过定义一个下面这种路由来获取这种情况的请求

/:name/:repo

并在请求的处理函数中通过 name 和 repo 两个字段获取到请求中的真实参数值，如请求 /bob/web 时的结果就是

{
  "name": "bob",
  "repo": "web"
}

这种动态匹配路径的路由就叫做动态路由（至少我是这么叫了），这些参数被称作 named parameter，即有名字的参数。而像 /user/profile 这种就把它叫做静态路由吧。

基于哈希表的路由还有一个问题，就是浪费内存，考虑下面这种路由有公共前缀的情况

/foo/bar
/fee/baz
/har/:pee/:poo
/har/pee
/har/paa

这些公共前缀在基于哈希表的路由中是实打实地重复存在，且 Go 提供的 ServeMux 的性能并不高，主要问题出现在路由查找过程中的内存分配上。

目前用 Go 语言实现第三方最快的 HTTP 路由器 httprouter 的解决办法是使用一种叫做 compressed trie (或叫 radix tree) 的数据结构来存储路由，即「压缩前缀树」。这种数据结构能够使得这些公共前缀共享一片内存，如下图所示

flowchart TD /-->f /-->har f-->oo f-->ee oo-->bar ee-->baz har-->:pee :pee-->:poo har-->pee har-->poo

这样，这颗 n 叉树就存储了上面列举的 5 条路由，其中，根结点到每个叶子结点的路径就分别对应了每条路由，所以把对应路由的处理函数或方法保存在它对应的叶子结点即可。像 Go 最出名的 web 框架 echo 和 gin 都是基于的 httprouter（但其实我点也不喜欢 gin）

当接收到请求的路径为 /foo/bar 时，就会从根结点开始进行深度优先遍历，直到匹配到一个叶子结点，然后用存在该叶子结点的函数或方法处理该请求。

且这种基于压缩前缀树的方法也能更方便的处理动态请求，如收到请求的路径为 /har/apple/banana 时就会依次选择到结点 har :pee :poo ，在到达这些结点时就可以顺便解析出这两个参数。具体怎么讲这些参数交给接下来处理请求的函数或方法，不同框架有不同的做法，如 httprouter 提供两种方法，一种是将这些参数放到 httprouter.Params 中作为参数传给自己定义的 Handler 接口，另一种是通过 Go 的 Context 来传递这些参数给 http.Handler，前者与 http.Handler 不兼容。

但是，这种方式并不好实现，httprouter 整整花了 680 行来实现压缩前缀树，且为了提高在树中的查询效率，httprouter 不得不使用了 goto 关键字（我猜的，因为这样能利于 Go 编译器编译出路由查询部分的高效率汇编指令）

所以，我试着设计了一种简单的、针对路由格式特点的方式来实现压缩前缀树，并且在同样的测试条件下，获得了和 httprouter 这个目前基于 Go 标准库中最快的 HTTP 路由器不相上下的结果，在一些特定的条件下甚至有略快的表现。

路由查找

还是那 5 条路由，在我简化后的压缩前缀树（下简称树）中的样子如下图所示，其中 ∅ 表示结点中没有任何前缀（后面会解释为什么使用 ∅ 而不是像 httprouter 那样使用 / 作为根结点）

flowchart TD w1["∅"]-->foo-->bar w1-->fee-->baz har-->paa har-->pee w1-->har-->:pee-->:poo

即先根据 / 来切分路由，然后用切分出的部分组成树路径上的节点，同样的，每条从根结点到叶子结点的路径对应了一条路由，每个叶子结点保存了其对应的路由的请求处理函数或方法。这样，当收到请求后，就先对请求的路径做同样的切分处理，然后逐个在树中对应的层上比较，分三种路由的情况。

静态路由

静态路由的查找算法如下面伪代码所示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function search(结点, 请求路径)
  chunks = split(请求路径, "/")
  for chunk in chunks:
    找到结点 = false
    for 子结点 in 结点:
      if 子结点 不与 chunk 匹配
        continue
      结点 = 子结点
      找到结点 = true
      break
    if not 找到结点:
      return NULL
  return 结点

其基本思想就是遍历 chunks，每轮依次比较对应那层的子结点，若匹配到一个，则进行下一层子结点的比较，否则直接返回空结点，不用再比较剩下的结点了。

以路径为 /fee/baz 的请求为例，调用 search

1
目标结点 = search(根结点, "/fee/baz")

该路径首先会被分割，得到 chunks 为 ["", "fee", "baz"]，然后会用 chunks 的第一个元素，即空字符串匹配到根结点，然后第二个元素 “fee” 匹配到第一层的 fee 结点，最后用第三个元素 “baz” 匹配到第二层的 baz 结点便完成了查找。这样便用对数时间复杂度找到了处理该请求的叶子结点，然后调用该结点里的函数或方法处理该请求即可。

动态路由

考虑这样一个情况，若我们的路由表里包含下面两条路由，即有一条静态路由和一条动态路由发生冲突。

/:bee/:gee
/foo/bar

按照目前我们的理解是发给路由 /foo/bar 的请求永远会被 /:bee/:gee 拦截到。所以 httprouter 的解决的方式是直接不允许这种情况的发生，当你尝试定义这种路由时，会收到 httprouter 的报错提示。

但更合理的逻辑是，只有路径为 /foo/bar 的请求才会被静态路由 /foo/bar 处理，其他的像 /fee/bar, /bee/gee 等就会被动态路由 /:bee/:gee 处理，且解析出对应的参数。

所以我们需要为子结点排序！因为在上述静态路由的查找算法中，某个节点的子结点是依次被比较的，只要先比较的是静态路由的结点就可以避免这个问题。若先静态结点没有匹配到，才会接着匹配动态结点。

具体的做法是为每个结点设置一个权重，若静态结点为 1，动态结点为 2，则每插入一个结点就将该层的结点按权重由小到大排序，这样就能保证静态路由比动态路由先进行匹配。

通配路由

除了上述的两种路由外，还有一种十分常见的路由情况，思考这下面三条路由的含义

/foo/
/foo/:bar
/foo/bar

一个合理的解释为，除了路径为 /foo/bar 的请求被静态路由 /foo/bar 处理和路径的格式为 /*/* 的请求被动态路由处理外，其他的请求都由路由 /foo/ 处理，即 /foo/ 表示 foo 下的所有路由，所以叫「通配」路由。这三条路由的 chunks 分别为

["", "foo", ""]
["", "foo", ":bar"]
["", "foo", "bar"]

表示成树就是

flowchart TD foo-->bar foo-->:pee w1["∅"]-->foo-->w2["∅"]

所以只需要在前面的基础上为空字符串结点设置权重为 3，即三种路由的权重关系为

静态结点 < 动态结点 < 通配结点

这样就能在前两种路由都没匹配到的时候，使用通配路由来 “兜个底”

到这里，你应该能明白为什么使用空字符串 "" 来表示根结点了吧，而不是像其他路由器那样直接使用 /。正是因为只有一个根结点的路由，即 "/"，其实只是通配路由的一个特殊情况，若你还是没懂，就考虑这么一个情况

即只有一个根通配路由，这条路由的 chunks 为

["", ""]

其对应的树为

flowchart w1["∅"]-->w2["∅"]

当朝根路径 / 发起请求时，根据上面的查找算法，该请求路径也会被分割成 ["", ""] 来进行匹配，刚好能满足此树。

特例一

哈哈，到这还没完呢。在上面通配路由例子的基础上，考虑这么一个特殊情况

/
/foo/
/foo/bar

其对应的树为

flowchart w1["∅1"]-->foo-->bar w1-->w2["∅2"] foo-->w3["∅3"]

若收到请求路径为 /foo/bar/pee ，按照我们所描述的查找算法来看，会依次经过结点 ∅1, foo, bar，然后会因为匹配不到 pee 而返回一个空结点，因为请求路径的 chunks 的长度超过了树的深度，可是按照我们的期望，该请求应该被通配路由 /foo/ 拿到，即匹配到使用距离最后一次比较的结点最近的通配结点 ∅3 。

为处理该特殊情况，我们可以让每个结点单独维护一下指向它通配子结点的指针，若他没有通配子结点，则该指针为空，然后在查询过程中记录一下沿路遇到的非空通配结点。这样就可以在没有匹配到结点的时候，返回当前记录的通配结点，即为最近的一个通配结点。所以现在只需要在前面的查找算法上加上几行即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function search(结点, 请求路径)
  最近的通配结点 = NULL
  chunks = split(请求路径, "/")
  for chunk in chunks:
    找到结点 = false
    if 结点.通配结点 != NULL:
      最近的通配结点 = 结点.通配结点
    for 子结点 in 结点:
      if 子结点 不与 chunk 匹配
        continue
      结点 = 子结点
      找到结点 = true
      break
    if not 找到结点:
      return 最近的通配结点
  return 结点

特例二

在目前的基础上，考虑下面两种情况的路由树

flowchart w1["∅1"]-->foo-->bar w1-->w2["∅2"] w3["∅1"]-->:foo-->baz w3-->w4["∅2"]

当收到路径为 /foo 的请求时，根据我们对通配结点的定义，无论是哪棵树，该请求应该都被结点 ∅2 处理，但目前的查找算法最终会返回结点 foo 或 :foo，因为静态结点和动态结点的权重都比通配结点的小，所以会先匹配结点 foo 或 :foo，而此时外层对 chunks 的遍历已经完成，不会再继续匹配下一层了，所以返回的结点是 foo 或 :foo，而非叶子结点是无法处理请求的。

解决这个问题的方法也很简单，只需要在返回查询的结果前判断一下是不是叶子结点即可，若是，直接返回结果即可，否则返回最近的通配结点。由于只有叶子结点上才有处理请求的函数或方法，所以可以根据查询到的结点里的请求处理函数或方法是否为空就能判断是否为叶子结点了。

整理一下最终的查找算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function search(结点, 请求路径)
  最近的通配结点 = 空
  chunks = split(请求路径, "/")
  for chunk in chunks:
    找到结点 = false
    if 结点.通配结点 不为空:
      最近的通配结点 = 结点.通配结点
    for 子结点 in 结点:
      if 子结点 不与 chunk 匹配
        continue
      结点 = 子结点
      找到结点 = true
      break
    if not 找到结点:
      return 最近的通配结点
  if 结点.handler 为空:
     结点 = 最近的通配结点
  return 结点

构造路由

通过调用 insert 方法来往树中插入新路由，实现 insert 方法的伪代码直接贴出来，大家可以自己思考一下（其实是因为我写到这儿已经很累了 233）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function insert(node, chunks, height, handler):
  if chunks 的长度 == height:
    node.handler = handler
    return
  if node 的子结点为空:
  	初始化 node 的子结点
  chunk = chunks[height]
  child = 找到 node 中能和 chunk 匹配的子结点
  
  if child 为空:
    child = 新键对应 chunk 的结点
    将 child 添加到 node 的子结点中
    按权重由小到大 对 node 的子结点排序
    
    if child 是通配结点:
      node.wild = child
  insert(child, chunks, height+1, handler)

可见，这是一个递归算法，其中 height 表示当前所处的层数。其实最开始前面的路由查询算法也是实现的递归形式，但我觉得迭代应该比递归性能好一些。这儿说句外话，在我的理解中，递归和迭代的本质区别是，递归在碰到挡板（终止条件）时，会原路返回，因为递归本身是利用了函数调用栈的先进后出特性，而迭代并不一定会。

路由索引

现在我们已经实现了满足静态、动态、通配三种路由的树的构造和查询，但问题还没结束，考虑下面三种常见的 RESTful 风格的请求路径

GET /user/bob
PUT /user/bob
DELETE /user/bob

它们的路径是一样的，但是表达的含义完全不一样。根据 RESTful API 的规定，处理这三个请求的接口应分别独立完成对用户名为 bob 的用户的查询、更改、删除操作。而我们目前的路由树，只能实现对请求路径的查询。一种最简单的方式就是用多棵树分别维护不同请求方法的路径，然后再使用一个哈希表来维护请求方法到其对应的树的映射，即请求方法作为键，路由树作为值。事实上，这也是大多数基于压缩前缀树实现的路由器，包括 httprouter，的做法。

基于这种方式，完整的路由查询过程就是

从请求中获取请求方法，如 GET
再在哈希表中找到 GET 对应的路由树
调用前面讲到的查询算法找到处理该请求的结点

但其实我们没必要用哈希表，因为目前 HTTP 1.1 版本协议只规定了 8 种请求方法，他们分别是（先不考虑 CONNECT 方法）

GET
POST
HAED
PUT
PATCH
DELETE
TRACE
OPTIONS

也就是说，哈希表里最多只有 8 个键，一般这种情况，就该考虑使用「数组」来进行优化了，也就是说将这八个字符串转换成数组的索引。你可能会问了：那这和用哈希表有什么区别呢？的确，基于拉链法的哈希表就是通过哈希函数将键转换成数组索引来找到对应值构成的链表头结点（Go map 底层正是用拉链法 + 重哈希实现的）

但是你看这 8 个请求方法的最短不同子串的长度只为 2，我们只用这两个字符带入哈希函数算出的索引值也不会冲突。

那该用啥哈希函数呢？只要满足这两个条件的 hash 函数都行

简单、快
算出的索引值不能太大

对于第一点，肯定要比 Go map 使用的通用哈希函数快；第二点是因为我们只需要使用数组的 8 个位置，若有索引值很大，则数组就会很长，空间利用率很低。这里我用的哈希函数只是简单的将两个字符的 ASCII 码的和模上 18，因为 18 是我通过暴力枚举找到的满足第二点条件的最小的整数。

1
2
function hash(s):
  return (s[1]+s[2]) % 18

该哈希函数算出的 8 个索引值分别为

0, 1, 2, 3, 5, 7, 8, 9, 13

还好不算太大，用长度为 14 的数组就行。

好了，到现在我们处理 HTTP 请求的过程就能被简单描述为

1
2
3
4
5
function lookup(请求):
  索引 = hash(请求.方法)
  树根 = 维护所有树根结点的数组[索引]
  结点 = search(树根, 请求.路径)
  处理请求(结点, 请求)

压测

写到这儿，真的想睡觉了，后面再把压测结果补上吧，包括如何使用内存池优化路由查询过程。或者可以自己去仓库把代码拉下来运行压测脚本，运行方法在 README.md 中。