前言
前一篇文章介紹了 fastify
通過 schema 來序列化 JSON,為 Node.js 服務提升效能的方法。今天的文章會介紹 fastify
使用的路由庫,翻閱其原始碼(lib/route.js
)可以發現,fastify
的路由庫並不是內建的,而是使用了一個叫做 find-my-way
的路由庫。
這個路由庫的簡介也很有意思,號稱“超級無敵快”的 HTTP 路由。
看上去 fastify
像是依賴了第三方的路由庫,其實這兩個庫的作者是同一批人。
如何使用
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(字首樹)。對於基數樹的每個節點,如果該節點是確定的子樹的話,就和父節點合併。
在 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 插入新的節點...
}
}
複製程式碼
每個方法對應的樹在第一次獲取不存在的時候,都會先建立一個根節點,根節點使用預設字元(/
)。
每個節點的資料結構如下:
// 只保留了一些重要引數,其他的暫時忽略
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"}')
})
複製程式碼
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"}')
})
複製程式碼
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
}
複製程式碼
本質是遍歷路徑的每個字元,然後判斷當前節點的子節點是否已經存在一個節點,如果存在就繼續向下遍歷,如果不存在,則新建一個節點,插入到當前節點。
查詢路由節點
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 來解析路徑的),效率上還是高很多的。