Секрет удвоения производительности сервисов Node.js (2)

Node.js внешний интерфейс
Секрет удвоения производительности сервисов Node.js (2)

предисловие

Предыдущая статья представилаfastifyСпособ повысить производительность служб Node.js за счет сериализации JSON через схему. Сегодняшняя статья познакомит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 для поиска.

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Найдите соответствующий обработчик, а затем сделайте звонок.

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(префиксное дерево). Часто используемые веб-фреймворки на языке Goechoа также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Маршрутизация в целях экономии памяти не будет генерировать три метки, т.к.x, будет сгенерирован только один узел, и его меткаx, префикс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)
  }
}

Вставка вызовов узла в прототип узла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
}

Поиск узла также осуществляется путем обхода дерева.После нахождения узла нужно поставить хэндл, чтобы посмотреть, существует ли он.Если он есть, то нужно выполнить обратный вызов.

Суммировать

Эта статья в основном знакомитfastifyбиблиотека маршрутизации черезRadix TreeИдея ускорения, по сравнению с другими библиотеками маршрутизации за счет регулярного сопоставления (например, koa-router черезpath-to-regexpдля разбора пути) эффективность все же намного выше.

Категории