Taobao FED

timer 的优化故事

timer 的优化故事

前段时间 Node.js 发布了新版本 4.0,其中涉及到一个更新比较多的模块,那就是下面要介绍的 timer 模块。

timers: Improved timer performance from porting the 0.12 implementation, plus minor fixes (Jeremiah Senkpiel)#2540, (Julien Gilli)nodejs/node-v0.x-archive#8751nodejs/node-v0.x-archive#8905

之前也对 timer 模块有过比较多的研究,断断续续的看过这个模块在 github 上的一些改动,于是借着这次机会整理一下自己对 timer 模块的理解,和小伙伴们一起分享 timer 模块的优化过程。

使用场景

也许你在使用 Node.js 开发项目时并没有使用到 timer 模块,诸如 setTimeout 以及 setInterval 和 setImediate 方法等等。但如果你开发的是 web 项目,那么你的项目中一定涉及到了 timer 模块。

细心的同学在平时的 http 接口开发调试中可能会注意到,每个 http 的 request header 里都有一个 Connection:keep-alive 标识,这是 http/1.1 开始引入的,表示客户端需要和服务端一直保持着 tcp 连接。当然了,这个连接不能就这么一直保持着,所以一般都会有一个超时时间,超过这个时间客户端还没有发送新的 http 请求,那么服务器就需要自动断开从而继续为其他客户端提供服务。

Node.js 提供的 http 服务器便是采用 timer 模块来满足这种请求,每一个新的连接到来构造出一个 socket 对象,便会调用 socket.setTimeout 设置一个定时器用于超时后自动断开连接。

设计

在 Node.js 开发的 web 项目中,timer 模块的使用频率是非常高的,每一个新的连接到来都会设置它的超时时间,而且每个连接的超时时间都一样,在 http server 中默认是 2*60*1000ms。Node.js 使用 c++ 包裹的 Timer 对象来实现定时器功能,下面的代码示例了使用 Timer 对象来实现一个非常简单的定时器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const Timer = process.binding('timer_wrap').Timer;
const kOnTimeout = Timer.kOnTimeout | 0;

var mySetTimeout = function (fn, ms) {
var timer = new Timer();
timer.start(ms, 0);
timer[kOnTimeout] = fn;
return timer;
}

var myClearTimeout = function(timer){
if(timer && timer.close) {
timer.close();
}
}

mySetTimeout(function() {
console.log('timeout!');
},1000);

那我们是否就可以用上面实现的 mySetTimeout 来对每个 socket 进行超时操作呢

1
mySetTimeout(function(){socket.close();},2 * 60 * 1000);

可以是可以,但是这样真的好吗?设想我们做的是一个非常棒的产品,每天好几百万上千万的用户,高峰期在 2* 60* 1000ms这段时间内会产生非常多的新连接,必然会创建非常多的 Timer 对象,这个开销还真不小!

Node.js 在设计之初就非常非常注重性能,所以像上面这种这么简单的方案必然是不能接受的。

实际上在这2分钟之内,Node.js 中的 timer 模块只会创建一个 Timer 对象,一个 Timer 对象如何来满足这么多连接的超时处理呢?

timer 模块会使用一个链表来保存所有超时时间相同的对象,每个对象中都会存储开始时间 _idleStart 以及超时时间 _idleTimeout。链表中第一个加入的对象一定会比后面加入的对象先超时,当第一个对象超时完成处理后,重新计算下一个对象是否已经到时或者还有多久到时,之前创建的 Timer 对象便会再次启动并设置新的超时时间,直到当链表上所有的对象都已经完成超时处理,此时便会关闭这个 Timer 对象。

通过这种巧妙的设计,使得一个 Timer 对象得到了最大的重用,从而极大的提升了 timer 模块的性能。这一场景其实在 libev 中已早有研究 http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod#Be_smart_about_timeouts

实现

上面说到 timer 模块通过 c++ 提供的 Timer 对象,最终生成 setTimeout 以及 setInterval 等函数暴露给用户使用。那 Timer 对象是如何实现的呢,下面我们就来一探究竟。

一个最底层的 timer

熟悉 linux 网络编程的同学一定听说过 epoll 吧,

epoll 是什么?按照 man 手册的说法:是为处理大批量句柄而作了改进的 poll。当然,这不是 2.6 内核才有的,它是在 2.5.44 内核中被引进的 (epoll(4) is a new API introduced in Linux kernel 2.5.44),它几乎具备了之前所说的一切优点,被公认为 Linux2.6 下性能最好的多路 I/O 就绪通知方法。

其中有这么一个函数

1
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

收集在 epoll 监控的事件中已经发送的事件。参数 events 是分配好的 epoll_event 结构体数组,epoll 将会把发生的事件赋值到 events 数组中(events 不可以是空指针,内核只负责把数据复制到这个 events 数组中,不会去帮助我们在用户态中分配内存)。maxevents 告之内核这个 events 有多大,这个 maxevents 的值不能大于创建 epoll_create() 时的 size,参数 timeout 是超时时间(毫秒,0 会立即返回,-1 将不确定,也有说法说是永久阻塞)。如果函数调用成功,返回对应 I/O 上已准备好的文件描述符数目,如返回 0 表示已超时。

当我们监听一个 fd 上的事件时,可以设置等待事件发生的超时时间。利用这个特性便可以非常简单的实现一个定时器功能。

由于我使用的是 mac 系统,所以就用 kqueue 来代替 epoll(它们之间非常相似,具体的详细介绍以及使用方法感兴趣的可以自行查阅相关资料)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/event.h>
#include <sys/time.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <errno.h>

const int MAX_EVENT_COUNT = 5000;

int main() {
struct timeval t_start,t_end;
int fd = -1;//构造一个不会有任何事件发生的fd
int kq = kqueue();
struct kevent changes[1];
EV_SET(&changes[0], fd, EVFILT_READ, EV_ADD, 0, 0, NULL);
int timeout = 3500;
struct kevent events[MAX_EVENT_COUNT];
struct timespec spec;
spec.tv_sec = timeout / 1000;
spec.tv_nsec = (timeout % 1000) * 1000000;
gettimeofday(&t_start, NULL);
kevent(kq, NULL, 0, events, MAX_EVENT_COUNT, &spec);
gettimeofday(&t_end, NULL);
printf("timeout = %d, run time is %ld\n", timeout, t_end.tv_sec*1000+t_end.tv_usec/1000 - (t_start.tv_sec*1000+t_start.tv_usec/1000));
return 0;
}

至此我们便利用 kqueue 实现了一个非常简单非常底层的定时器。

libuv 中的 timer

前面讲到,在 http server 中每一个新的连接并不会真的就去创建一个 Timer 对象。同样,在 Node.js 底层的定时器中,并不会每次创建一个 Timer 对象就在 kqueue 上注册一个事件等待超时。优化的思路和 Node.js 中的 timer 模块很相似,只不过现在不能保证每个定时器的超时时间都一样。

定时器有一个非常显著的特征,超时时间最短的定时器一定最先触发,假设我们有很多的定时任务,每个任务的执行时间都不同。当第一个定时器超时后,便从这些任务中查找出已经到点的任务并执行对应的超时处理,然后再重新计算余下任务中最先执行的时间,并根据这个时间再次开启一个定时器。

对应的算法需求就是每次都需要查找集合中最小的元素,显然二叉堆中的最小堆(父结点的键值总是小于或等于任何一个子节点的键值)是最适合不过的一种数据结构了。由于最小的元素总是处于根节点,我们可以以 O(1) 时间找到最小值。对于插入操作,在最坏的情况下,新插入的节点需要不断的和它的父节点进行交换,直到它为根节点为止。假设堆的高度为 h, 二叉树最多有 2^(h+1) - 1 个 节点. 因此新插入一个节点最多需要 log(n+1) -1 次比较,其算法复杂度为 O(logn)。

http://gtms02.alicdn.com/tps/i2/TB1r0H9JpXXXXXaXpXXDezOOXXX-2004-1220.png

libuv 中已经实现了一个最小二叉堆的算法 https://github.com/joyent/libuv/blob/master/src/heap-inl.h, 下面我们就用这个算法来实现一个支持设置不同超时时间的定时器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/event.h>
#include <sys/time.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <errno.h>

//https://github.com/joyent/libuv/blob/master/src/heap-inl.h
#include "heap-inl.h"

#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) - offsetof(type, member)))


const int MAX_EVENT_COUNT = 5000;

typedef struct {
struct heap_node* heap_node[3];
int value;
}node_t;

static int less_than(const struct heap_node* ha, const struct heap_node* hb) {
const node_t* a;
const node_t* b;

a = container_of(ha, const node_t, heap_node);
b = container_of(hb, const node_t, heap_node);

if (a->value < b->value)
return 1;
return 0;
}


int main() {

struct heap *heap_p = malloc(sizeof(node_t));
heap_init(heap_p);

int a[] = {10,9,8,6,7,3,5,4,2};

int len = sizeof(a)/sizeof(int);
for(int i=0;i<len;i++){
node_t *node_p = malloc(sizeof(node_t));
node_p->value = a[i]*1000;
heap_insert(heap_p, (struct heap_node*)node_p->heap_node, less_than);
}


int fd = -1;
int kq = kqueue();

struct kevent changes[1];
EV_SET(&changes[0], fd, EVFILT_READ, EV_ADD, 0, 0, NULL);

struct kevent events[MAX_EVENT_COUNT];
struct timeval t_start,t_end;

while(heap_p->nelts) {
node_t *node_p = container_of(heap_p->min, node_t, heap_node);
struct timespec spec;
spec.tv_sec = node_p->value / 1000;
spec.tv_nsec = (node_p->value % 1000) * 1000000;
gettimeofday(&t_start, NULL);
kevent(kq, NULL, 0, events, MAX_EVENT_COUNT, &spec);
gettimeofday(&t_end, NULL);
printf("timeout = %d, run time is %ld\n", node_p->value, t_end.tv_sec*1000+t_end.tv_usec/1000 - (t_start.tv_sec*1000+t_start.tv_usec/1000));
heap_dequeue(heap_p, less_than);
}

printf("timer is over!\n");

return 0;
}

执行 gcc timer.c -o timer && ./timer 后输出

1
2
3
4
5
6
7
8
9
10
timeout = 2000, run time is 2004
timeout = 3000, run time is 3000
timeout = 4000, run time is 4003
timeout = 5000, run time is 5005
timeout = 6000, run time is 6005
timeout = 7000, run time is 7005
timeout = 8000, run time is 8004
timeout = 9000, run time is 9000
timeout = 10000, run time is 10005
timer is over!

可以看到我们设置的 9 个定时器都预期执行了,除了有 5ms 以内的偏差。这就是 Node.js 中最底层的定时器实现了。

nodejs 中的 timer

我们再回到 Node.js 中的 timer 模块,为了不影响到 Node.js 中的 event loop,timer 模块专门提供了一些内部的 api(timers._unrefActive) 给像 socket 这样的对象使用。

timer 内部会维护一个 unrefList 链表以及一个 unrefTimer Timer 对象,当有新的超时任务到来时便会添加到 unrefList 中,超时后便从 unrefList 中取出任务执行。

在最初的设计中,每次执行 _unrefActive 添加任务时都会维持着 unrefList 的顺序,保证超时时间最小的处于前面。这样在定时器超时后便可以以最快的速度处理超时任务并设置下一个定时器,但是在添加任务时最坏的情况下需要遍历 unrefList 链表中的所有节点。具体实现可参考https://github.com/nodejs/node/blob/5abd4ac079b390467360d671a186a061b5aba736/lib/timers.js

很显然,在 web 开发中建立连接是最频繁的操作,那么向 unrefList 链表中添加节点也就非常频繁了,而且最开始设置的定时器其实最后真正会超时的非常少,因为中间涉及到 io 的正常操作时便会取消定时器。所以问题就变成最耗性能的操作非常频繁,而几乎不花时间的操作却很少被执行到。

针对这种情况,如何解决呢?目前在node社区主要有2种方案。

使用不排序的链表

主要思路就是将对 unrefList 链表的遍历操作,移到unrefTimeout定时器超时处理中。这样每次查找出已经超时的任务就需要花比较多的时间了 O(n),但是插入操作却变得非常简单 O(1),而插入节点正是最频繁的操作。

使用二叉堆

原理和 libuv 中的 timer 实现一样,添加和查找一个节点都能达到 O(log(n)) 的复杂度(找出最小节点本身很快,但是删除它需要 O(log(n)) 的复杂度),能够在二者之间保持一个很好的平衡。

benchamark

这2种方案都有比较详细 benchamark 数据, 具体可参考https://github.com/nodejs/node-v0.x-archive/wiki/Optimizing-_unrefActive

小结

在高并发连接到来并且很少有实际的超时事件发生时 unrefList 使用没有排序的链表来存储超时任务时性能是非常棒的。但是一旦出现很多超时事件都发生的情况下,对超时事件的处理会再次变成一个瓶颈。

而使用二叉堆来存储超时任务时,当有大量超时事件发生时性能会比链表好很多,没有超时事件触发时性能比链表稍差。

可见 Node.js 在不同的场景中使用的定时器实现也不都一样,说 Node.js 对性能的追求达到极致一点也不为过。当我们自己在实际的开发时,如果需要使用到定时器功能,不妨好好思考下哪种方案更适合业务场景,能够最大的提升 timer 模块的性能。

参考文档