通過源碼解析 Node.js 中高效的 timer

phpmatt 發(fā)布于2019-08-21 13:50 / 1574人閱讀

摘要：雙向鏈表的具體實(shí)現(xiàn)便在中可以看到，都是些修改鏈表中指針的操作，都十分高效。如此一來，既做到了定時(shí)器的復(fù)用優(yōu)化，又對(duì)鏈表結(jié)構(gòu)進(jìn)行了揚(yáng)長避短。

在 Node.js 中，許許多多的異步操作，都需要來一個(gè)兜底的超時(shí)，這時(shí)，就輪到 timer 登場(chǎng)了。由于需要使用它的地方是那么的多，而且都是基礎(chǔ)的功能模塊，所以，對(duì)于它性能的要求，自然是十分高的。總結(jié)來說，要求有：

更快的添加操作。

更快的移除操作。

更快的超時(shí)觸發(fā)。

接下來就讓我們跟著 Node.js 項(xiàng)目中的 lib/timer.js 和 lib/internal/linklist.js 來探究它具體的實(shí)現(xiàn)。

更快的添加 / 移除操作

說到添加和移除都十分高效的數(shù)據(jù)結(jié)構(gòu)，第一個(gè)映入腦簾的，自然就是鏈表啦。是的，Node.js 就是使用了雙向鏈表，來將 timer 的插入和移除操作的時(shí)間復(fù)雜度都降至 O(1) 。雙向鏈表的具體實(shí)現(xiàn)便在 lib/internal/linklist.js 中：

// lib/internal/linklist.js
"use strict";
function init(list) {
  list._idleNext = list;
  list._idlePrev = list;
}
exports.init = init;

function peek(list) {
  if (list._idlePrev == list) return null;
  return list._idlePrev;
}
exports.peek = peek;

function shift(list) {
  var first = list._idlePrev;
  remove(first);
  return first;
}
exports.shift = shift;

function remove(item) {
  if (item._idleNext) {
    item._idleNext._idlePrev = item._idlePrev;
  }

  if (item._idlePrev) {
    item._idlePrev._idleNext = item._idleNext;
  }

  item._idleNext = null;
  item._idlePrev = null;
}
exports.remove = remove;

function append(list, item) {
  remove(item);
  item._idleNext = list._idleNext;
  list._idleNext._idlePrev = item;
  item._idlePrev = list;
  list._idleNext = item;
}
exports.append = append;

function isEmpty(list) {
  return list._idleNext === list;
}
exports.isEmpty = isEmpty;

可以看到，都是些修改鏈表中指針的操作，都十分高效。

更快的超時(shí)觸發(fā)

鏈表的缺點(diǎn)，自然是它的查找時(shí)間，對(duì)于一個(gè)無序的鏈表來說，查找時(shí)間需要 O(n) ，但是，只要基于一個(gè)大前提，那么我們的實(shí)現(xiàn)就并不需要使用到鏈表的查詢，這也是更高效的超時(shí)觸發(fā)的基礎(chǔ)所在，那就是，對(duì)于同一延遲的 timers ，后添加的一定比先添加的晚觸發(fā)。所以，源碼的具體做法就是，對(duì)于同一延遲的所有 timers ，全部都維護(hù)在同一個(gè)雙向鏈表中，后來的，就不斷往鏈表末尾追加，并且這條鏈表實(shí)際上共享同一個(gè)定時(shí)器。這個(gè)定時(shí)器會(huì)在當(dāng)次超時(shí)觸發(fā)時(shí)，動(dòng)態(tài)計(jì)算下一次的觸發(fā)時(shí)間點(diǎn)。所有的鏈表，都保存在一個(gè)對(duì)象 map 中。如此一來，既做到了定時(shí)器的復(fù)用優(yōu)化，又對(duì)鏈表結(jié)構(gòu)進(jìn)行了揚(yáng)長避短。

讓我們先以 setTimeout 為例看看具體代碼，首先是插入：

// lib/timer.js
// ...
const refedLists = {};
const unrefedLists = {};

exports.setTimeout = function(callback, after) {
  // ... 
  var timer = new Timeout(after);
  var length = arguments.length;
  var ontimeout = callback;
  // ...
  timer._onTimeout = ontimeout;
  
  active(timer);
  return timer;
};

const active = exports.active = function(item) {
  insert(item, false);
};

function insert(item, unrefed) {
  const msecs = item._idleTimeout;
  if (msecs < 0 || msecs === undefined) return;

  item._idleStart = TimerWrap.now();

  var list = lists[msecs];
  if (!list) {
    // ...
    list = new TimersList(msecs, unrefed);
    L.init(list);
    list._timer._list = list;

    if (unrefed === true) list._timer.unref();
    list._timer.start(msecs, 0);

    lists[msecs] = list;
    list._timer[kOnTimeout] = listOnTimeout;
  }

  L.append(list, item);
  assert(!L.isEmpty(list));
}

即檢查當(dāng)前在對(duì)象 map 中，是否存在該超時(shí)時(shí)間（msecs）的雙向鏈表，若無，則新建一條。你應(yīng)該已經(jīng)看出，超時(shí)觸發(fā)時(shí)具體的處理邏輯，就在 listOnTimeout 函數(shù)中：

// lib/timer.js
// ...
function listOnTimeout() {
  var list = this._list;
  var msecs = list.msecs;

  var now = TimerWrap.now();

  var diff, timer;
  while (timer = L.peek(list)) {
    diff = now - timer._idleStart;

    if (diff < msecs) {
      this.start(msecs - diff, 0);
      return;
    }
    L.remove(timer);
    // ...
    tryOnTimeout(timer, list);
    // ...
  }

  this.close();
  // ...
}

即不斷從鏈表頭取出封裝好的包含了注冊(cè)時(shí)間點(diǎn)和處理函數(shù)的對(duì)象，然后挨個(gè)執(zhí)行，直到計(jì)算出的超時(shí)時(shí)間點(diǎn)已經(jīng)超過當(dāng)前時(shí)間點(diǎn)。

舉個(gè)圖例，在時(shí)間點(diǎn) 10，100，400 時(shí)分別注冊(cè)了三個(gè)超時(shí)時(shí)間為 1000 的 timer，在時(shí)間點(diǎn) 300 注冊(cè)了一個(gè)超時(shí)時(shí)間為 3000 的 timer，即在時(shí)間點(diǎn) 500 時(shí)，對(duì)象 map 的結(jié)構(gòu)即為：

隨后在時(shí)間點(diǎn) 1200 觸發(fā)了超時(shí)事件，并在時(shí)間點(diǎn) 1300 執(zhí)行完畢，彼時(shí)對(duì)象 map 的結(jié)構(gòu)即為：

setInterval 和 setImmediate

setInterval 的實(shí)現(xiàn)總體和 setTimeout 很相似，區(qū)別在于對(duì)注冊(cè)的回調(diào)函數(shù)進(jìn)行了封裝，在鏈表的尾部重新插入：

// lib/timer.js
// ...

function wrapper() {
  timer._repeat(); // 執(zhí)行傳入的回調(diào)函數(shù)

  if (!timer._repeat)
    return;

  // ...
  timer._idleTimeout = repeat;
  active(timer);
}

而 setImmediate 和 setTimeout 實(shí)現(xiàn)上的主要區(qū)別則在于，它會(huì)一次性將鏈表中注冊(cè)的，都執(zhí)行完：

// lib/timer.js
// ...
function processImmediate() {
  var queue = immediateQueue;
  var domain, immediate;

  immediateQueue = {};
  L.init(immediateQueue);

  while (L.isEmpty(queue) === false) {
    immediate = L.shift(queue);
    // ...
    tryOnImmediate(immediate, queue);
    // ...
  }

  if (L.isEmpty(immediateQueue)) {
    process._needImmediateCallback = false;
  }
}

所以作為功能類似的 process.nextTick 和 setImmediate ，在功能層面上看，每次事件循環(huán)，它們都會(huì)將存儲(chǔ)的回調(diào)都執(zhí)行完，但 process.nextTick 中的存儲(chǔ)的回調(diào)，會(huì)先于 setImmediate 中的執(zhí)行：

"use strict"
const print = (i) => () => console.log(i)

process.nextTick(print(1))
process.nextTick(print(2))

setImmediate(() => {
  print(3)()
  setImmediate(print(6))
  process.nextTick(print(5))
})
setImmediate(print(4))

console.log("發(fā)車")

// 發(fā)車
// 1
// 2
// 3
// 4
// 5
// 6

最后

參考：

https://github.com/nodejs/node/blob/master/lib/timers.js

https://github.com/nodejs/node/blob/master/lib/internal/linkedlist.js