Node.js 服务性能翻倍的秘密（二）

前言

前一篇文章介绍了 fastify 通过 schema 来序列化 JSON，为 Node.js 服务提升性能的方法。今天的文章会介绍 fastify 使用的路由库，翻阅其源码(lib/route.js)可以发现，fastify 的路由库并不是内置的，而是使用了一个叫做 find-my-way 的路由库。

route.js

这个路由库的简介也很有意思，号称“超级无敌快”的 HTTP 路由。

README

看上去 fastify 像是依赖了第三方的路由库，其实这两个库的作者是同一批人。

author

如何使用find-my-way 通过 on 方法绑定路由，并且提供了 HTTP 所有方法的简写。

1. const router = require('./index')() 
2.  
3. router.on('GET', '/a', (req, res, params) => { 
4.   res.end('{"message": "GET /a"}') 
5. }) 
6. router.get('/a/b', (req, res, params) => { 
7.   res.end('{"message": "GET /a/b"}') 
8. })) 

其实内部就是通过遍历所有的 HTTP 方法名，然后在原型上扩展的。

1. Router.prototype.on = function on (method, path, opts, handler) { 
2.   if (typeof opts === 'function') { 
3.     // 如果 opts 为函数，表示此时的 opts 为 handler 
4.     handler = opts 
5.     opts = {} 
6.   } 
7.   // ... 
8. } 
9. for (var i in http.METHODS) { 
10.   const m = http.METHODS[i] 
11.   const methodName = m.toLowerCase() 
12.   // 扩展方法简写 
13.   Router.prototype[methodName] = function (path, handler) { 
14.     return this.on(m, path, handler) 
15.   } 
16. } 

绑定的路由可以通过 lookup 调用，只要将原生的 req 和 res 传入 lookup 即可。

1. const http = require('http') 
2.  
3. const server = http.createServer((req, res) => { 
4.   // 只要将原生的 req 和 res 传入 lookup 即可 
5.   router.lookup(req, res) 
6. }) 
7.   
8. server.listen(3000) 

find-my-way 会通过 req.method/req.url 找到对应的 handler，然后进行调用。

1. Router.prototype.lookup = function lookup (req, res) { 
2.   var handle = this.find(req.method, sanitizeUrl(req.url)) 
3.   if (handle === null) { 
4.     return this._defaultRoute(req, res, ctx) 
5.   } 
6.   // 调用 hendler 
7.   return handle.handler(req, res, handle.params) 
8. } 

路由的添加和查找都基于树结构来实现的，下面我们来看看具体的实现。

Radix Tree

find-my-way 采用了名为 Radix Tree(基数树) 的算法，也被称为 Prefix Tree(前缀树)。Go 语言里常用的 web 框架echo和gin都使用了Radix Tree作为路由查找的算法。

• 在计算机科学中，基数树，或称压缩前缀树，是一种更节省空间的Trie(前缀树)。对于基数树的每个节点，如果该节点是确定的子树的话，就和父节点合并。

Radix Tree

在 find-my-way 中每个 HTTP 方法(GET、POST、PUT ...)都会对应一棵前缀树。

1. // 方法有所简化... 
2. function Router (opts) { 
3.   opts = opts || {} 
4.   this.trees = {} 
5.   this.routes = [] 
6. } 
7.  
8. Router.prototype.on = function on (method, path, opts, handler) { 
9.   if (typeof opts === 'function') { 
10.     // 如果 opts 为函数，表示此时的 opts 为 handler 
11.     handler = opts 
12.     opts = {} 
13.   } 
14.   this._on(method, path, opts, handler) 
15. } 
16.  
17. Router.prototype._on = function on (method, path, opts, handler) { 
18.   this.routes.push({ 
19.     method, path, opts, handler, 
20.   }) 
21.   // 调用 _insert 方法 
22.   this._insert(method, path, handler) 
23.  
24. } 
25. Router.prototype._insert = function _insert (method, path, handler) { 
26.   // 取出方法对应的 tree 
27.   var currentNode = this.trees[method] 
28.   if (typeof currentNode === 'undefined') { 
29.     // 首次插入构造一个新的 Tree 
30.     currentNode = new Node({ method }) 
31.     this.trees[method] = currentNode 
32.   } 
33.   while(true) { 
34.     // 为 currentNode 插入新的节点... 
35.   } 
36. } 

每个方法对应的树在第一次获取不存在的时候，都会先创建一个根节点，根节点使用默认字符(/)。

trees

每个节点的数据结构如下：

1. // 只保留了一些重要参数，其他的暂时忽略 
2. function Node(options) { 
3.   options = options || {} 
4.   this.prefix = options.prefix || '/' // 去除公共前缀之后的字符，默认为 / 
5.   this.label = this.prefix[0]         // 用于存放其第一个字符 
6.   this.method = options.method        // 请求的方法 
7.   this.handler = options.handler      // 请求的回调 
8.   this.children = options.children || {} // 存放后续的子节点 
9. } 

当我们插入了几个路由节点后，树结构的具体构造如下：

1. router.on('GET', '/a', (req, res, params) => { 
2.   res.end('{"message":"hello world"}') 
3. }) 
4. router.on('GET', '/aa', (req, res, params) => { 
5.   res.end('{"message":"hello world"}') 
6. }) 
7. router.on('GET', '/ab', (req, res, params) => { 
8.   res.end('{"message":"hello world"}') 
9. }) 

GET Tree

1. Node { 
2.   label: 'a', 
3.   prefix: 'a', 
4.   method: 'GET', 
5.   children: { 
6.     a: Node { 
7.       label: 'a', 
8.       prefix: 'a', 
9.       method: 'GET', 
10.       children: {}, 
11.       handler: [Function] 
12.     }, 
13.     b: Node { 
14.       label: 'b', 
15.       prefix: 'b', 
16.       method: 'GET', 
17.       children: {}, 
18.       handler: [Function] 
19.     } 
20.   }, 
21.   handler: [Function] 
22. } 

如果我们绑定一个名为 /axxx 的路由，为了节约内存，不会生成三个 label 为x 的节点，只会生成一个节点，其 label 为 x，prefix 为 xxx。

1. router.on('GET', '/a', (req, res, params) => { 
2.   res.end('{"message":"hello world"}') 
3. }) 
4. router.on('GET', '/axxx', (req, res, params) => { 
5.   res.end('{"message":"hello world"}') 
6. }) 

GET Tree

1. Node { 
2.   label: 'a', 
3.   prefix: 'a', 
4.   method: 'GET', 
5.   children: { 
6.     a: Node { 
7.       label: 'x', 
8.       prefix: 'xxx', 
9.       method: 'GET', 
10.       children: {}, 
11.       handler: [Function] 
12.     } 
13.   }, 
14.   handler: [Function] 
15. } 

插入路由节点

通过之前的代码可以看到， on 方法最后会调用内部的 _insert 方法插入新的节点，下面看看其具体的实现方式：

1. Router.prototype._insert = function _insert (method, path, handler) { 
2.   // 取出方法对应的 tree 
3.   var currentNode = this.trees[method] 
4.   if (typeof currentNode === 'undefined') { 
5.     // 首次插入构造一个新的 Tree 
6.     currentNode = new Node({ method }) 
7.     this.trees[method] = currentNode 
8.   } 
9.  
10.   var len = 0 
11.   var node = null 
12.   var prefix = '' 
13.   var prefixLen = 0 
14.   while(true) { 
15.     prefix = currentNode.prefix 
16.     prefixLen = prefix.length 
17.     len = prefixLen 
18.     path = path.slice(len) 
19.     // 查找是否存在公共前缀 
20.     node = currentNode.findByLabel(path) 
21.     if (node) { 
22.       // 公共前缀存在，复用 
23.       currentNode = node 
24.       continue 
25.     } 
26.     // 公共前缀不存在，创建一个 
27.     node = new Node({ method: method, prefix: path }) 
28.     currentNode.addChild(node) 
29.   } 
30. } 

插入节点会调用 Node 原型上的 addChild 方法。

1. Node.prototype.getLabel = function () { 
2.   return this.prefix[0] 
3. } 
4.  
5. Node.prototype.addChild = function (node) { 
6.   var label = node.getLabel() // 取出第一个字符做为 label 
7.   this.children[label] = node 
8.   return this 
9. } 

本质是遍历路径的每个字符，然后判断当前节点的子节点是否已经存在一个节点，如果存在就继续向下遍历，如果不存在，则新建一个节点，插入到当前节点。

tree

查找路由节点

find-my-way 对外提供了 lookup 方法，用于查找路由对应的方法并执行，内部是通过 find 方法查找的。

1. Router.prototype.find = function find (method, path, version) { 
2.   var currentNode = this.trees[method] 
3.   if (!currentNode) return null 
4.  
5.   while (true) { 
6.     var pathLen = path.length 
7.     var prefix = currentNode.prefix 
8.     var prefixLen = prefix.length 
9.     var len = prefixLen 
10.     var previousPath = path 
11.     // 找到了路由 
12.     if (pathLen === 0 || path === prefix) { 
13.       var handle = currentNode.handler 
14.       if (handle !== null && handle !== undefined) { 
15.         return { 
16.           handler: handle.handler 
17.         } 
18.       } 
19.     } 
20.     // 继续向下查找 
21.     path = path.slice(len) 
22.     currentNode = currentNode.findChild(path) 
23.   } 
24. } 
25.  
26. Node.prototype.findChild = function (path) { 
27.   var child = this.children[path[0]] 
28.   if (child !== undefined || child.handler !== null)) { 
29.     if (path.slice(0, child.prefix.length) === child.prefix) { 
30.       return child 
31.     } 
32.   } 
33.  
34.   return null 
35. } 

查找节点也是通过遍历树的方式完成的，找到节点之后还需要放到 handle 是否存在，存在的话需要执行回调。

总结

本文主要介绍了 fastify 的路由库通过 Radix Tree 进行提速的思路，相比于其他的路由库通过正则匹配(例如 koa-router 就是通过 path-to-regexp 来解析路径的)，效率上还是高很多的。

原文地址：https://mp.weixin.qq.com/s/gnd0hLc7ztiDTxD-F4U8Vw