[[360400]]

前言

前一篇文章介紹了 fastify 通過(guò) schema 來(lái)序列化 JSON，為 Node.js 服務(wù)提升性能的方法。今天的文章會(huì)介紹 fastify 使用的路由庫(kù)，翻閱其源碼(lib/route.js)可以發(fā)現(xiàn)，fastify 的路由庫(kù)并不是內(nèi)置的，而是使用了一個(gè)叫做 find-my-way 的路由庫(kù)。

route.js

這個(gè)路由庫(kù)的簡(jiǎn)介也很有意思，號(hào)稱“超級(jí)無(wú)敵快”的 HTTP 路由。

README

看上去 fastify 像是依賴了第三方的路由庫(kù)，其實(shí)這兩個(gè)庫(kù)的作者是同一批人。

author

如何使用find-my-way 通過(guò) on 方法綁定路由，并且提供了 HTTP 所有方法的簡(jiǎn)寫。

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"}') 
})) 

其實(shí)內(nèi)部就是通過(guò)遍歷所有的 HTTP 方法名，然后在原型上擴(kuò)展的。

Router.prototype.on = function on (method, path, opts, handler) { 
  if (typeof opts === 'function') { 
    // 如果 opts 為函數(shù)，表示此時(shí)的 opts 為 handler 
    handler = opts 
    opts = {} 
  } 
  // ... 
} 
for (var i in http.METHODS) { 
  const m = http.METHODS[i] 
  const methodName = m.toLowerCase() 
  // 擴(kuò)展方法簡(jiǎn)寫 
  Router.prototype[methodName] = function (path, handler) { 
    return this.on(m, path, handler) 
  } 
} 

綁定的路由可以通過(guò) lookup 調(diào)用，只要將原生的 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 會(huì)通過(guò) req.method/req.url 找到對(duì)應(yīng)的 handler，然后進(jìn)行調(diào)用。

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) 
  } 
  // 調(diào)用 hendler 
  return handle.handler(req, res, handle.params) 
} 

路由的添加和查找都基于樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的，下面我們來(lái)看看具體的實(shí)現(xiàn)。

Radix Tree

find-my-way 采用了名為 Radix Tree(基數(shù)樹(shù)) 的算法，也被稱為 Prefix Tree(前綴樹(shù))。Go 語(yǔ)言里常用的 web 框架echo和gin都使用了Radix Tree作為路由查找的算法。

• 在計(jì)算機(jī)科學(xué)中，基數(shù)樹(shù)，或稱壓縮前綴樹(shù)，是一種更節(jié)省空間的Trie(前綴樹(shù))。對(duì)于基數(shù)樹(shù)的每個(gè)節(jié)點(diǎn)，如果該節(jié)點(diǎn)是確定的子樹(shù)的話，就和父節(jié)點(diǎn)合并。

Radix Tree

在 find-my-way 中每個(gè) HTTP 方法(GET、POST、PUT ...)都會(huì)對(duì)應(yīng)一棵前綴樹(shù)。

// 方法有所簡(jiǎn)化... 
function Router (opts) { 
  opts = opts || {} 
  this.trees = {} 
  this.routes = [] 
} 
 
Router.prototype.on = function on (method, path, opts, handler) { 
  if (typeof opts === 'function') { 
    // 如果 opts 為函數(shù)，表示此時(shí)的 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, 
  }) 
  // 調(diào)用 _insert 方法 
  this._insert(method, path, handler) 
 
} 
Router.prototype._insert = function _insert (method, path, handler) { 
  // 取出方法對(duì)應(yīng)的 tree 
  var currentNode = this.trees[method] 
  if (typeof currentNode === 'undefined') { 
    // 首次插入構(gòu)造一個(gè)新的 Tree 
    currentNode = new Node({ method }) 
    this.trees[method] = currentNode 
  } 
  while(true) { 
    // 為 currentNode 插入新的節(jié)點(diǎn)... 
  } 
} 

每個(gè)方法對(duì)應(yīng)的樹(shù)在第一次獲取不存在的時(shí)候，都會(huì)先創(chuàng)建一個(gè)根節(jié)點(diǎn)，根節(jié)點(diǎn)使用默認(rèn)字符(/)。

trees

每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：

// 只保留了一些重要參數(shù)，其他的暫時(shí)忽略 
function Node(options) { 
  options = options || {} 
  this.prefix = options.prefix || '/' // 去除公共前綴之后的字符，默認(rèn)為 / 
  this.label = this.prefix[0]         // 用于存放其第一個(gè)字符 
  this.method = options.method        // 請(qǐng)求的方法 
  this.handler = options.handler      // 請(qǐng)求的回調(diào) 
  this.children = options.children || {} // 存放后續(xù)的子節(jié)點(diǎn) 
} 

當(dāng)我們插入了幾個(gè)路由節(jié)點(diǎn)后，樹(shù)結(jié)構(gòu)的具體構(gòu)造如下：

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] 
} 

如果我們綁定一個(gè)名為 /axxx 的路由，為了節(jié)約內(nèi)存，不會(huì)生成三個(gè) label 為x 的節(jié)點(diǎn)，只會(huì)生成一個(gè)節(jié)點(diǎn)，其 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] 
} 

插入路由節(jié)點(diǎn)

通過(guò)之前的代碼可以看到， on 方法最后會(huì)調(diào)用內(nèi)部的 _insert 方法插入新的節(jié)點(diǎn)，下面看看其具體的實(shí)現(xiàn)方式：

Router.prototype._insert = function _insert (method, path, handler) { 
  // 取出方法對(duì)應(yīng)的 tree 
  var currentNode = this.trees[method] 
  if (typeof currentNode === 'undefined') { 
    // 首次插入構(gòu)造一個(gè)新的 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) { 
      // 公共前綴存在，復(fù)用 
      currentNode = node 
      continue 
    } 
    // 公共前綴不存在，創(chuàng)建一個(gè) 
    node = new Node({ method: method, prefix: path }) 
    currentNode.addChild(node) 
  } 
} 

插入節(jié)點(diǎn)會(huì)調(diào)用 Node 原型上的 addChild 方法。

Node.prototype.getLabel = function () { 
  return this.prefix[0] 
} 
 
Node.prototype.addChild = function (node) { 
  var label = node.getLabel() // 取出第一個(gè)字符做為 label 
  this.children[label] = node 
  return this 
} 

本質(zhì)是遍歷路徑的每個(gè)字符，然后判斷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否已經(jīng)存在一個(gè)節(jié)點(diǎn)，如果存在就繼續(xù)向下遍歷，如果不存在，則新建一個(gè)節(jié)點(diǎn)，插入到當(dāng)前節(jié)點(diǎn)。

tree

查找路由節(jié)點(diǎn)

find-my-way 對(duì)外提供了 lookup 方法，用于查找路由對(duì)應(yīng)的方法并執(zhí)行，內(nèi)部是通過(guò) 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 
        } 
      } 
    } 
    // 繼續(xù)向下查找 
    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 
} 

查找節(jié)點(diǎn)也是通過(guò)遍歷樹(shù)的方式完成的，找到節(jié)點(diǎn)之后還需要放到 handle 是否存在，存在的話需要執(zhí)行回調(diào)。

總結(jié)

本文主要介紹了 fastify 的路由庫(kù)通過(guò) Radix Tree 進(jìn)行提速的思路，相比于其他的路由庫(kù)通過(guò)正則匹配(例如 koa-router 就是通過(guò) path-to-regexp 來(lái)解析路徑的)，效率上還是高很多的。