对于一个 Node.js web 框架来说，路由系统的设计是重中之重。所谓路由，干的事情就是根据 HTTP method 和 URL 路径匹配需要执行的处理函数，并在处理函数中提供有关请求和回应的上下文。借助原生的 HTTP 模块，我们可以写出这样的代码，来实现一个简易的路由功能：
const http = require("http");
const host = 'localhost';
const port = 8000;
const requestListener = function (req, res) {
res.setHeader("Content-Type", "application/json");
switch (req.url) {
case "/hello":
res.writeHead(200);
res.end(JSON.stringify({"message": "world"}));
break;
default:
res.writeHead(404);
res.end(JSON.stringify({error:"Resource not found"}));
}
};
const server = http.createServer(requestListener);
server.listen(port, host, () => {
console.log(`Server is running on http://${host}:${port}`);
});
上面的这段代码有几个可优化点：
{"message": msg}，那直接做字符串拼接 '{"message":' + msg + '}'，它的执行速度就会比 JSON.stringify 快。关于这块的性能优化，我会放到下一篇文章中单独介绍。对于第 2 点，我们很容易可以想到的一个优化方案是：将所有路由注册到一个映射表上。这个映射表大概是这样的：
get / => home#index
get /name => user#index
post /user => user#create
箭头左边是请求方法和URL路径，右边是对应的处理函数。这样需要新增路由的时候，只需要更新映射表，而不用调整原有代码逻辑。这也是一种很常见的代码优化技巧。这种我将其称之为集中式路由，因为所有路由规则都是集中管理的。基于这种设计，写出来的 Controller 大概长这样：
export default class AppController {
index(){
return {
status: 'ok'
});
}
}
当请求过来时，框架要找到对应的处理函数，首先要去逐行读取这个映射表文件，对每一行做正则匹配，拿到它的 Controller 名和处理函数名。其次框架要对 Controller 的命名和位置做约束，这样才能根据 Controller 名和处理函数名定位到具体的处理函数。
还有一种思路是，将路由规则的定义放到对应的Controller内部，这样路由的注册就分散到各个Controller了。以 hoth(百度内部基于 Fastify 自研的 Node 框架)为例，比如：
import {Controller, GET} from '@hoth/decorators';
import type {FastifyReply, FastifyRequest} from 'fastify';
@Controller('/index')
export default class AppController {
@GET()
getApp(req: FastifyRequest, reply: FastifyReply) {
return {
status: 'ok'
});
}
}
它使用了 Controller 和 GET 两个装饰器，实现了路由规则和处理函数的解耦，提升了代码的可读性和可维护性。装饰器只是一个语法糖，最终它还是走的 fastify 内部的路由注册逻辑：
fastify.get('/index', (req, reply) => {})
这里的 fastify.get 方法会在 Node.js 应用启动时执行，将路由规则加载到内存中。
对于小型项目，采用集中式路由或是分散式路由，对性能的影响微乎其微。这两种方案只有在大型项目中才能体现出性能优劣。集中式路由的问题在于，新增了一个（或多个）文件来单独存储这些路由规则，注册路由时框架需要解析文件，这就涉及到文件 IO；查询路由时可能还需要用到正则匹配，这对性能也是一种损耗。而像 fastify 采用的这种分散式路由，路由规则提前被注册到内存中，没有文件 IO，也不用正则来解析规则。
而且集中式注册路由也不利于应用的横向扩展，试想下有多个子应用的场景，框架就需要知道所有子应用的路由规则。
除了上面讲到的注册路由的方式，存储路由的数据结构，对性能也有着不小的影响。最简单的可以想到用数组存储路由，它的查询性能是 O(n)，随着路由数量增加，性能会越来越差。而在实际场景中，许多 HTTP 请求的路径有着相同的前缀。某些框架，比如 go 的 echo 和 gin，Node.js 的 fastify 会引入另一种数据结构：Radix-Trie，来存储路由。
在计算机科学中，基数树（Radix Trie，也叫基数特里树或压缩前缀树）是一种数据结构，是一种更节省空间的Trie（前缀树），其中作为唯一子节点的每个节点都与其父节点合并，边既可以表示为元素序列又可以表示为单个元素。 因此每个内部节点的子节点数最多为基数树的基数r ，其中r为正整数，x为2的幂，x≥1，这使得基数树更适用于对于较小的集合（尤其是字符串很长的情况下）和有很长相同前缀的字符串集合。
Radix-Trie 的插入、删除、查询的时间复杂度均为 O(k)(k为字符串集合中最长的字符串长度），因此无论路由规则增长多少，它都可以保证查询性能始终是常量级的。
fastify 的核心路由逻辑是另一个库 find-my-way 实现的，fastify 提供了 get、post、all 等方法用来注册路由，它们的内部调用了 find-my-way 上的 router.on 方法。当应用启动时，它会将所有路由构建成多个 Radix-Trie，比如：
fastify.get('/index', (req, reply) => {})
它其实就是在 Radix-Trie 上插入了一个新节点，tree 的数据结构大体是这样的：
{
prefix: '/',
label: '/',
method: 'GET',
children: {
i: {
prefix: 'index',
label: 'i',
method: 'GET',
children: [Object],
numberOfChildren: 1,
kind: 0,
handler: [Object],
},
u: {
prefix: 'user',
label: 'u',
method: 'GET',
children: [Object],
numberOfChildren: 1,
kind: 0,
handler: [Object],
},
numberOfChildren: 2,
kind: 0,
handler: [Object],
params: []
}
}
fastify 根据不同 method，将路由划分到多个树中。prefix 标记路由前缀，如果某个节点只有一个子节点，那么会与其父节点合并。kind 用于标记路由的类型，find-my-way 支持这五种路由类型：
{
STATIC: 0, // 静态路由，/info/version
PARAM: 1, // 带参数路由 /aaa/:id
MATCH_ALL: 2, // 通配路由 /aaa/*
REGEX: 3, // 正则路由 /at/(^\\d+)
MULTI_PARAM: 4 // 多参数路由 /foo/:param1-:param2
}
现在有这样几条路由（省略了handler）：
GET /user
GET /user/list
GET /user/info
GET /admin/group
GET /admin/delete
它们构成的 tree 长这样：
现在要新增一条路由 GET /usage，假定它是节点 a，插入节点 a 到 tree 的步骤如下：
遍历 tree，找到节点在树中的最长公共前缀长度 len，这里 usage 在树中的最长公共前缀是us，长度是2。
如果最长公共前缀长度 maxCommonPrefixLen 等于当前节点的前缀长度 prefixLen，将（a - 公共前缀）插入到这个节点的子节点。显然节点 a 的 maxCommonPrefixLen 是小于 prefixLen 的。
如果 maxCommonPrefixLen 小于 prefixLen，将节点 a 拆分为公共前缀 + 剩余b，将公共前缀作为父节点，插入树中，然后对剩余部分 b 重复上述步骤。这里会将 us 作为父节点，插入到树中，然后将剩余部分 age 作为子节点插入。
最终，新的 tree 长这样：
讲完了路由节点的插入，再来看路由的查询。这里直接上代码：
Router.prototype.find = function find(method, path) {
var currentNode = this.trees[method];
if (!currentNode) return null;
var originalPath = path;
var originalPathLength = path.length;
var i = 0;
var idxInOriginalPath = 0;
while (true) {
var pathLen = path.length;
var prefix = currentNode.prefix;
var prefixLen = prefix.length;
var len = 0;
var previousPath = path;
if (pathLen === 0 || path === prefix) {
var handle = currentNode.handler;
if (handle !== null && handle !== undefined) {
return {
handler: handle.handler
};
}
}
i = pathLen < prefixLen ? pathLen : prefixLen;
while (len < i && path.charCodeAt(len) === prefix.charCodeAt(len)) len++;
if (len === prefixLen) {
path = path.slice(len);
pathLen = path.length;
idxInOriginalPath += len;
}
var node = currentNode.findChild(path);
if (node === null) {
var goBack = previousPath.charCodeAt(0) === 47 ? previousPath : '/' + previousPath;
if (originalPath.indexOf(goBack) === -1) {
var pathDiff = originalPath.slice(0, originalPathLength - pathLen);
previousPath = pathDiff.slice(pathDiff.lastIndexOf('/') + 1, pathDiff.length) + path;
}
idxInOriginalPath = idxInOriginalPath - (previousPath.length - path.length);
path = previousPath;
pathLen = previousPath.length;
len = prefixLen;
}
if (node.kind === NODE_TYPES.STATIC) {
currentNode = node;
continue;
}
}
};
web 框架中路由的性能主要取决于路由注册和路由匹配两个环节，采用何种介质、何种数据结构存储路由规则，很大程度影响了路由库的性能。本文介绍了一种数据结构 Radix-Trie，及其它在 fastify 中的应用。
除了路由之外，数据序列化也是一个性能优化点，在进程通信、请求响应等环节都会涉及到序列化。下一篇文章将介绍 fastify 中如何实现的高性能 JSON 序列化。
欢迎加微信 xxr0314 聊一聊技术、人生，本人微信公众号：小熊写字的地方
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。