Node.js 核心模块 Timers 详解
发布于 2 年前 作者 starkwang 2620 次浏览 来自 分享

Timers 模块应该是 Node.js 最重要的模块之一了。为什么这么说呢?

在 Node.js 基础库中,任何一个 TCP I/O 都会产生一个 timer(计时器)对象,以便记录请求/响应是否超时。例如,HTTP请求经常会附带 Connection:keep-alive 这个请求头,以让服务器维持 TCP 连接,但这个连接显然不可能一直保持着,所以会为它设置一个超时时间,这在内部库里正是通过 Timers 实现的。

所以可以肯定地说,任何使用 Node.js 编写的 Web 服务,一定在底层涉及到了 Timers 模块。(之后我们可以看到,Timers 模块的性能对于 Web 服务而言极其重要

另外,你的 Node.js 代码中也许会调用到诸如 setTimeoutsetInternalsetImmediate ,这些方法在浏览器内一般是由浏览器内部实现,而 Node.js 中,这些方法都是由 Timers 模块提供的:

// 浏览器中:
> setTimeout
//=> ƒ setTimeout() { [native code] }

// Node.js:
> setTimeout
//=> { [Function: setTimeout] [Symbol(util.promisify.custom)]: [Function] }

Timers 模块如此重要,所以了解它的运行机制和实现原理对我们深刻理解 Node.js 十分有帮助,那么就开始吧。


一、定时器的实现

刚才已经提到,在 Node.js 里,setTimeoutsetInternalsetImmediate 这些定时器相关的函数是由基础库实现的,那么它们到底是怎么实现的呢?

Node.js 底层通过 C++ 在 libuv 的基础上包裹了一个 timer_wrap 模块,这个模块提供了 Timer 对象,实现了在 runtime 层面的定时功能。

简单的说,你可以通过这个 Timer 对象实现一个你自己的 setTimeout

const Timer = process.binding('timer_wrap').Timer;
const kOnTimeout = Timer.kOnTimeout | 0;

function setTimeout(fn, ms) {
    var timer  = new Timer();  // 创建一个 Timer 对象
    timer.start(ms, 0);        // 设置触发时间
    timer[kOnTimeout] = fn;    // 设置回调函数
    return timer;              // 返回定时器
}


// 试一试
setTimeout(() => console.log('timeout!'), 1000);

当然,这个 setTimeout 方法不能真正地使用在生产环境中,因为它存在一个很严重的性能问题:

每次调用该方法,都会创建一个全新的 Timer 对象。

设想一下,服务器每一秒都会面对成千上万的 TCP 或 HTTP 请求,为每个请求都独立地创建一个 Timer 对象,这里的性能开销对于追求高并发的服务器端程序来说,是不可接受的。

所以我们需要一种更合理的数据结构来处理大量的 Timer 对象,Node.js 内部非常巧妙地使用了双向链表来解决这个问题。


二、名词声明

下面的文章中,我会使用 timer 表示 Node.js 层面的定时器对象,例如 setTimeoutsetInterval 返回的对象:

var timer = setTimeout(() => {}, 1000);

大写字母开头的 Timer 表示由底层 C++ time_wrap 模块提供的 runtime 层面的定时器对象

const Timer = process.binding('timer_wrap').Timer;

三、Node.js 的定时器双向链表

Node.js 会使用一个双向链表来保存所有定时时间相同timer,对于同一个链表中的所有 timer,只会创建一个 Timer 对象。当链表中前面的 timer 超时的时候,会触发回调,在回调中重新计算下一次超时的时间,然后重置 Timer 对象,以减少重复 Timer 对象的创建开销。

上面这两句话信息量比较大,第一次看不懂没关系,接着往下看。

举个例子,所有 setTimeout(func, 1000) 的定时器都会放置在同一个链表中,共用同一个 Timer 对象。下面我们来看 Node.js 是怎么做到的。

3.1、链表的创建

在程序执行最初,Timers 模块会初始化两个对象,用于保存链表的头部(看源码请点这里):

// - key = time in milliseconds
// - value = linked list
const refedLists = Object.create(null);
const unrefedLists = Object.create(null);

我们在后文中称这两个对象为 lists 对象,它们的区别在于, refedLists 是给 Node.js 外部的定时器(即第三方代码)使用的,而 unrefedLists 是给内部模块(如 nethttphttp2)使用。

相同之处在于,它们的 key 代表这一组定时器的超时时间,key 对应的 value,都是一个定时器链表。例如 lists[1000] 对应的就是由一个或多个超时时间为 1000mstimer 组成的链表。

当你的代码中第一次调用定时器方法时,例如:

var timer1 = setTimeout(() => {}, 1000);

这个时候,lists 对象中当然是空的,没有任何链表,Timers 便会在对应的位置上(这个例子中是lists[1000])创建一个 TimersList 作为链表的头部,并且把刚才创建的新的 timer 放入链表中(源码请点这里):

// Timers 模块部分源码:
const L = require('internal/linkedlist');
const lists = unrefed === true ? unrefedLists : refedLists;

// 如果已经有链表了,那么直接复用,没有的话就创建一个
var list = lists[msecs];
if (!list) {
    lists[msecs] = list = createTimersList(msecs, unrefed);
}

// 略过一些初始化步骤......

// 把 timer 加入链表
L.append(list, timer);

你可以亲自试一试:

var timer1 = setTimeout(() => {}, 1000)

timer1._idlePrev //=> TimersList { ...... }
timer1._idlePrev._idleNext //=> timer1

正如我们之前说到的,上面 setTimeout(() => {}, 1000) 这个定时器,会保存在 lists[1000] 这个链表中。

这个时候,我们链表的状态是这样的:

3.2、向链表中添加节点

假设我们一段时间后又添加了一个新的、相同时间的 timer:

var timer2 = setTimeout(() => {}, 1000);

这个新的 timer2 会被加入到链表中, 和之前的 timer1 在同一个链表中:

timer1._idlePrev === timer2 // true
timer2._idleNext === timer1 // true

如果画成图的话就是类似这样:

(PS:我们一直提到的这个双向链表,其实是是独立于 Timers 模块实现的,你可以在这里看到它的具体实现代码:linkedlist.js

用一张图来总结一下就是,Timers 模块是这样储存 timer的:

现在你已经知道了如何用双向链表保存 timer,接下来我们看看 Node.js 是如何利用双向链表实现 Timer 对象复用的吧。

3.3、使用双向链表复用 Timer 对象

虽然我们把定时时间相同的 timer 放到了一起,但由于它们的添加时间不一样,所以它们的执行时间也不一样。

例如,链表中的第 1 个 timer 是在程序最初设置的,而第 2 个 timer 是在稍后时间设置的,它们定时时间相同,所以位于同一链表中,但由于时间先后顺序,当然不可能同时触发。

在链表中,Node.js 使用 _idleStart 来记录 timer 设置定时的时间,或者理解为 timer 开始计时的时间。

var timer1 = setTimeout(() => {}, 100 * 1000) // 这里我们把时间设长一些,防止定时器超时后被从链表中删除
timer1._idleStart //=> 10829

// 一段时间后(100秒之内),设置第二个定时器 = ̄ω ̄=
var timer2 = setTimeout(() => {}, 100 * 1000)
timer2._idleStart //=> 23333

// 此时它们依然在同一个链表中:
timer1._idlePrev === timer2 // true
timer2._idleNext === timer1 // true

画成图的话就是这样:

你可能会很奇怪,为什么我们的链表中最左侧这个奇怪的 TimersList 到底是个啥?难道只是一个头部装饰品吗?

事实上,TimersList 就包含着我们所要复用的 Timer 对象,也就是底层 C++ 实现的那个定时器,它承担了整个链表的计时工作。

等时间到 100 秒时,timer1 该触发了,这个时候会发生一些系列事情:

  1. 承担计时任务的 TimersList 对象中的 Timer (也就是 C++ 实现的那个东西)触发回调,执行 timer1 所绑定的回调函数;
  2. timer1 从链表中移除;
  3. 重新计算多久后触发下一次回调(即 timer2 对应的回调),重置 Timer,重复 1 过程。

下面用图来描绘一下整个过程:

首先,在两个定时器添加之后:

100秒到了,此时 Timer 对象触发,执行 timer1 对应的回调函数:

然后 timer1 被移除出链表,重新计算下次触发时间,重设 Timer,此时状态变为:

整个过程的源码请参考这里

这样,我们便通过一个双向链表实现了 Timer 对象的复用,一个链表只需要一个 Timer,大大提高了 Timers 模块的性能。


四、为什么要这样设计?

看到这里你可能会觉得,上面提到的这些设计,都很理所当然,天经地义。

然而并非如此,对于处理多个 timer 对象,熟悉算法的同学肯定能想到,我们完全可以只用一个 Timer

例如,我们可以把所有 timer 都放在唯一一个链表中,每次创建 timer 时,都通过计算 timer 具体执行的时间,从而找到合适的位置,把新的 timer 插入到链表中:

比如,最初的链表是这样:

TimersList <-----> timer1 <-----> timer2 <-----> timer3 <-----> ......
                1000ms后执行     1050ms后执行      1200ms后执行

此时我们调用

var timer4 = setTimeout(() => {}, 1100);

timer4 应该插入到哪儿呢?一个线性查找便可以找到位置,即在 timer2timer3 之间:

                                                  插入!
TimersList <-----> timer1 <-----> timer2 <-----> timer4 <-----> timer3 <-----> ......
                1000ms后执行     1050ms后执行    1100ms后执行    1200ms后执行

熟悉算法的同学看到线性查找肯定立刻意识到了,完全可以用一个O(lgn)二叉树代替上面这个需要线性查找O(n)的链表。

这样我们不但可以只用一个 Timer 对象,而且可以用最佳的效率找到 timer 的插入位置,为什么 Node.js 都 v9.0 了还没有使用这样的算法呢?

事实上,社区很早之前就已经尝试过二叉树或者时间片轮转调度算法,但这些算法实际的性能数据却不如上文提到的多链表实现,为什么呢?

因为内部库里,如 nethttp 模块,为 timer 设定的超时时间基本是固定的,所以产生了一个经验性的假设:越晚创建的 timer 很可能越晚执行

基于这个假设我们再来看二叉树算法,由于假设的存在,每次插入新的 timer,由于插入时间最晚,执行时间极可能也是最晚的,所以很容易进入树的最右侧,此时,我们的二叉树便退化成了一个普通的链表。性能优势也不复存在。(平衡二叉树?那就更不可能了)


五、后谈

其实,Timers 模块的设计并非一簇而就,它的历史也是十分有趣。早在 Node.js v0.x 的史前时代,之前提到的 refedListsunrefedLists 这两个对象是分开实现的:对于第三方代码,使用的是多链表的结构;对于内部库,使用的是单一链表的结构。

你可以在这里看到当年是如何实现链表的线性查找插入的。

后来直到 2015 年的这个 PR 的提交才正式告别了之前的线性搜索:use unsorted array in Timers._unrefActive() #2540

现在,社区里又有人产生了新的关于优化 Timers 的想法:

Optimizing ‘unreferenced’ timers #16105

读懂了文章的你,有兴趣吗?

六、参考

1、Timers in Node.js

2、The Node.js Event Loop, Timers, and process.nextTick()

3、Node.js timer的优化故事 - 淘小杰

4、JavaScript 运行机制详解:再谈Event Loop - 阮一峰的网络日志

7 回复

好文章,赞一个

质量很高的文章

此处有掌声!

赞,要是能把libuv层面的timer_heap相关内容也加入一下就更棒了

回到顶部