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 所有方法的簡寫。
- const router = require('./index')()
- router.on('GET', '/a', (req, res, params) => {
- res.end('{"message": "GET /a"}')
- })
- router.get('/a/b', (req, res, params) => {
- res.end('{"message": "GET /a/b"}')
- }))
其實內部就是通過遍歷所有的 HTTP 方法名，然后在原型上擴展的。
- Router.prototype.on = function on (method, path, opts, handler) {
- if (typeof opts === 'function') {
- // 如果 opts 為函數，表示此時的 opts 為 handler
- handler = opts
- opts = {}
- }
- // ...
- }
- for (var i in http.METHODS) {
- const m = http.METHODS[i]
- const methodName = m.toLowerCase()
- // 擴展方法簡寫
- Router.prototype[methodName] = function (path, handler) {
- return this.on(m, path, handler)
- }
- }
綁定的路由可以通過 lookup 調用，只要將原生的 req 和 res 傳入 lookup 即可。
- const http = require('http')
- const server = http.createServer((req, res) => {
- // 只要將原生的 req 和 res 傳入 lookup 即可
- router.lookup(req, res)
- })
- server.listen(3000)
find-my-way 會通過 req.method/req.url 找到對應的 handler，然后進行調用。
- Router.prototype.lookup = function lookup (req, res) {
- var handle = this.find(req.method, sanitizeUrl(req.url))
- if (handle === null) {
- return this._defaultRoute(req, res, ctx)
- }
- // 調用 hendler
- return handle.handler(req, res, handle.params)
- }
路由的添加和查找都基于樹結構來實現的，下面我們來看看具體的實現。
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 ...)都會對應一棵前綴樹。
- // 方法有所簡化...
- function Router (opts) {
- opts = opts || {}
- this.trees = {}
- this.routes = []
- }
- Router.prototype.on = function on (method, path, opts, handler) {
- if (typeof opts === 'function') {
- // 如果 opts 為函數，表示此時的 opts 為 handler
- handler = opts
- opts = {}
- }
- this._on(method, path, opts, handler)
- }
- Router.prototype._on = function on (method, path, opts, handler) {
- this.routes.push({
- method, path, opts, handler,
- })
- // 調用 _insert 方法
- this._insert(method, path, handler)
- }
- Router.prototype._insert = function _insert (method, path, handler) {
- // 取出方法對應的 tree
- var currentNode = this.trees[method]
- if (typeof currentNode === 'undefined') {
- // 首次插入構造一個新的 Tree
- currentNode = new Node({ method })
- this.trees[method] = currentNode
- }
- while(true) {
- // 為 currentNode 插入新的節點...
- }
- }
每個方法對應的樹在第一次獲取不存在的時候，都會先創建一個根節點，根節點使用默認字符(/)。
trees
每個節點的數據結構如下：
- // 只保留了一些重要參數，其他的暫時忽略
- function Node(options) {
- options = options || {}
- this.prefix = options.prefix || '/' // 去除公共前綴之后的字符，默認為 /
- this.label = this.prefix[0] // 用于存放其第一個字符
- this.method = options.method // 請求的方法
- this.handler = options.handler // 請求的回調
- this.children = options.children || {} // 存放后續的子節點
- }
當我們插入了幾個路由節點后，樹結構的具體構造如下：
- router.on('GET', '/a', (req, res, params) => {
- res.end('{"message":"hello world"}')
- })
- router.on('GET', '/aa', (req, res, params) => {
- res.end('{"message":"hello world"}')
- })
- router.on('GET', '/ab', (req, res, params) => {
- res.end('{"message":"hello world"}')
- })
GET Tree
- Node {
- label: 'a',
- prefix: 'a',
- method: 'GET',
- children: {
- a: Node {
- label: 'a',
- prefix: 'a',
- method: 'GET',
- children: {},
- handler: [Function]
- },
- b: Node {
- label: 'b',
- prefix: 'b',
- method: 'GET',
- children: {},
- handler: [Function]
- }
- },
- handler: [Function]
- }
如果我們綁定一個名為 /axxx 的路由，為了節約內存，不會生成三個 label 為x 的節點，只會生成一個節點，其 label 為 x，prefix 為 xxx。
- router.on('GET', '/a', (req, res, params) => {
- res.end('{"message":"hello world"}')
- })
- router.on('GET', '/axxx', (req, res, params) => {
- res.end('{"message":"hello world"}')
- })
GET Tree
- Node {
- label: 'a',
- prefix: 'a',
- method: 'GET',
- children: {
- a: Node {
- label: 'x',
- prefix: 'xxx',
- method: 'GET',
- children: {},
- handler: [Function]
- }
- },
- handler: [Function]
- }
插入路由節點
通過之前的代碼可以看到， on 方法最后會調用內部的 _insert 方法插入新的節點，下面看看其具體的實現方式：
- Router.prototype._insert = function _insert (method, path, handler) {
- // 取出方法對應的 tree
- var currentNode = this.trees[method]
- if (typeof currentNode === 'undefined') {
- // 首次插入構造一個新的 Tree
- currentNode = new Node({ method })
- this.trees[method] = currentNode
- }
- var len = 0
- var node = null
- var prefix = ''
- var prefixLen = 0
- while(true) {
- prefix = currentNode.prefix
- prefixLen = prefix.length
- len = prefixLen
- path = path.slice(len)
- // 查找是否存在公共前綴
- node = currentNode.findByLabel(path)
- if (node) {
- // 公共前綴存在，復用
- currentNode = node
- continue
- }
- // 公共前綴不存在，創建一個
- node = new Node({ method: method, prefix: path })
- currentNode.addChild(node)
- }
- }
插入節點會調用 Node 原型上的 addChild 方法。
- Node.prototype.getLabel = function () {
- return this.prefix[0]
- }
- Node.prototype.addChild = function (node) {
- var label = node.getLabel() // 取出第一個字符做為 label
- this.children[label] = node
- return this
- }
本質是遍歷路徑的每個字符，然后判斷當前節點的子節點是否已經存在一個節點，如果存在就繼續向下遍歷，如果不存在，則新建一個節點，插入到當前節點。
tree
查找路由節點
find-my-way 對外提供了 lookup 方法，用于查找路由對應的方法并執行，內部是通過 find 方法查找的。
- Router.prototype.find = function find (method, path, version) {
- var currentNode = this.trees[method]
- if (!currentNode) return null
- while (true) {
- var pathLen = path.length
- var prefix = currentNode.prefix
- var prefixLen = prefix.length
- var len = prefixLen
- var previousPath = path
- // 找到了路由
- if (pathLen === 0 || path === prefix) {
- var handle = currentNode.handler
- if (handle !== null && handle !== undefined) {
- return {
- handler: handle.handler
- }
- }
- }
- // 繼續向下查找
- path = path.slice(len)
- currentNode = currentNode.findChild(path)
- }
- }
- Node.prototype.findChild = function (path) {
- var child = this.children[path[0]]
- if (child !== undefined || child.handler !== null)) {
- if (path.slice(0, child.prefix.length) === child.prefix) {
- return child
- }
- }
- return null
- }
查找節點也是通過遍歷樹的方式完成的，找到節點之后還需要放到 handle 是否存在，存在的話需要執行回調。
總結
本文主要介紹了 fastify 的路由庫通過 Radix Tree 進行提速的思路，相比于其他的路由庫通過正則匹配(例如 koa-router 就是通過 path-to-regexp 來解析路徑的)，效率上還是高很多的。
