前天nodejs發(fā)布了新版本4.0,其中涉及到一個(gè)更新比較多的模塊，那就是下面要介紹的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

之前也對(duì)timer模塊有過(guò)比較多的研究新症，斷斷續(xù)續(xù)的看過(guò)這個(gè)模塊在github上的一些改動(dòng)择示，于是借著這次機(jī)會(huì)整理一下自己對(duì)timer模塊的理解阳准，和小伙伴們一起分享timer模塊的優(yōu)化過(guò)程源请。

使用場(chǎng)景

也許你在使用nodejs開(kāi)發(fā)項(xiàng)目時(shí)并沒(méi)有使用到timer模塊，諸如setTimeout以及setInterval和setImediate方法等等铲球。但如果你開(kāi)發(fā)的是web項(xiàng)目挺庞，那么你的項(xiàng)目中一定涉及到了timer模塊。

細(xì)心的同學(xué)在平時(shí)的http接口開(kāi)發(fā)調(diào)試中可能會(huì)注意到稼病，每個(gè)http的request header里都有一個(gè)Connection:keep-alive標(biāo)識(shí),這是http/1.1開(kāi)始引入的选侨，表示客戶(hù)端需要和服務(wù)端一直保持著tcp連接。當(dāng)然了溯饵，這個(gè)連接不能就這么一直保持著侵俗，所以一般都會(huì)有一個(gè)超時(shí)時(shí)間，超過(guò)這個(gè)時(shí)間客戶(hù)端還沒(méi)有發(fā)送新的http請(qǐng)求丰刊，那么服務(wù)器就需要自動(dòng)斷開(kāi)從而繼續(xù)為其他客戶(hù)端提供服務(wù)隘谣。

nodejs提供的http服務(wù)器便是采用timer模塊來(lái)滿(mǎn)足這種請(qǐng)求，每一個(gè)新的連接到來(lái)構(gòu)造出一個(gè)socket對(duì)象，便會(huì)調(diào)用socket.setTimeout設(shè)置一個(gè)定時(shí)器用于超時(shí)后自動(dòng)斷開(kāi)連接寻歧。

設(shè)計(jì)

在nodejs開(kāi)發(fā)的web項(xiàng)目中掌栅，timer模塊的使用頻率是非常高的，每一個(gè)新的連接到來(lái)都會(huì)設(shè)置它的超時(shí)時(shí)間码泛，而且每個(gè)連接的超時(shí)時(shí)間都一樣猾封，在http server中默認(rèn)是2 * 60 * 1000ms。nodejs使用c++包裹的Timer對(duì)象來(lái)實(shí)現(xiàn)定時(shí)器功能,下面的代碼示例了使用Timer對(duì)象來(lái)實(shí)現(xiàn)一個(gè)非常簡(jiǎn)單的定時(shí)器噪珊。

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);

那我們是否就可以用上面實(shí)現(xiàn)的mySetTimeout來(lái)對(duì)每個(gè)socket進(jìn)行超時(shí)操作呢

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

可以是可以,但是這樣真的好嗎晌缘？設(shè)想我們做的是一個(gè)非常棒的產(chǎn)品，每天好幾百萬(wàn)上千萬(wàn)的用戶(hù)痢站，高峰期在2 * 60 * 1000ms這段時(shí)間內(nèi)會(huì)產(chǎn)生非常多的新連接磷箕，必然會(huì)創(chuàng)建非常多的Timer對(duì)象，這個(gè)開(kāi)銷(xiāo)還真不姓竽选岳枷！

nodejs在設(shè)計(jì)之初就非常非常注重性能，所以像上面這種這么簡(jiǎn)單的方案必然是不能接受的呜叫。

實(shí)際上在這2分鐘之內(nèi)空繁，nodejs中的timer模塊只會(huì)創(chuàng)建一個(gè)Timer對(duì)象，一個(gè)Timer對(duì)象如何來(lái)滿(mǎn)足這么多連接的超時(shí)處理呢朱庆？

timer模塊會(huì)使用一個(gè)鏈表來(lái)保存所有超時(shí)時(shí)間相同的對(duì)象盛泡，每個(gè)對(duì)象中都會(huì)存儲(chǔ)開(kāi)始時(shí)間_idleStart以及超時(shí)時(shí)間_idleTimeout。鏈表中第一個(gè)加入的對(duì)象一定會(huì)比后面加入的對(duì)象先超時(shí)娱颊，當(dāng)?shù)谝粋€(gè)對(duì)象超時(shí)完成處理后饭于，重新計(jì)算下一個(gè)對(duì)象是否已經(jīng)到時(shí)或者還有多久到時(shí)，之前創(chuàng)建的Timer對(duì)象便會(huì)再次啟動(dòng)并設(shè)置新的超時(shí)時(shí)間维蒙，直到當(dāng)鏈表上所有的對(duì)象都已經(jīng)完成超時(shí)處理，此時(shí)便會(huì)關(guān)閉這個(gè)Timer對(duì)象果覆。

通過(guò)這種巧妙的設(shè)計(jì)颅痊，使得一個(gè)Timer對(duì)象得到了最大的重用，從而極大的提升了timer模塊的性能畔派。這一場(chǎng)景其實(shí)在libev中已早有研究 http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod#Be_smart_about_timeouts

實(shí)現(xiàn)

上面說(shuō)到timer模塊通過(guò)c++提供的Timer對(duì)象妒蛇，最終生成setTimeout以及setInterval等函數(shù)暴露給用戶(hù)使用官紫。那Timer對(duì)象是如何實(shí)現(xiàn)的呢，下面我們就來(lái)一探究竟舰罚。

一個(gè)最底層的timer

熟悉linux網(wǎng)絡(luò)編程的同學(xué)一定聽(tīng)說(shuō)過(guò)epoll吧，

epoll是什么薛耻？按照man手冊(cè)的說(shuō)法：是為處理大批量句柄而作了改進(jìn)的poll营罢。當(dāng)然，這不是2.6內(nèi)核才有的，它是在2.5.44內(nèi)核中被引進(jìn)的(epoll(4) is a new API introduced in Linux kernel 2.5.44)饲漾，它幾乎具備了之前所說(shuō)的一切優(yōu)點(diǎn)蝙搔，被公認(rèn)為L(zhǎng)inux2.6下性能最好的多路I/O就緒通知方法。

其中有這么一個(gè)函數(shù)

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

收集在epoll監(jiān)控的事件中已經(jīng)發(fā)送的事件考传。參數(shù)events是分配好的epoll_event結(jié)構(gòu)體數(shù)組吃型，epoll將會(huì)把發(fā)生的事件賦值到events數(shù)組中（events不可以是空指針，內(nèi)核只負(fù)責(zé)把數(shù)據(jù)復(fù)制到這個(gè)events數(shù)組中僚楞，不會(huì)去幫助我們?cè)谟脩?hù)態(tài)中分配內(nèi)存）勤晚。maxevents告之內(nèi)核這個(gè)events有多大，這個(gè) maxevents的值不能大于創(chuàng)建epoll_create()時(shí)的size泉褐，參數(shù)timeout是超時(shí)時(shí)間（毫秒赐写，0會(huì)立即返回，-1將不確定兴枯，也有說(shuō)法說(shuō)是永久阻塞）血淌。如果函數(shù)調(diào)用成功，返回對(duì)應(yīng)I/O上已準(zhǔn)備好的文件描述符數(shù)目财剖，如返回0表示已超時(shí)悠夯。

當(dāng)我們監(jiān)聽(tīng)一個(gè)fd上的事件時(shí)，可以設(shè)置等待事件發(fā)生的超時(shí)時(shí)間躺坟。利用這個(gè)特性便可以非常簡(jiǎn)單的實(shí)現(xiàn)一個(gè)定時(shí)器功能沦补。

由于我使用的是mac系統(tǒng)，所以就用kqueue來(lái)代替epoll(它們之間非常相似,具體的詳細(xì)介紹以及使用方法感興趣的可以自行查閱相關(guān)資料)

#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;//構(gòu)造一個(gè)不會(huì)有任何事件發(fā)生的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實(shí)現(xiàn)了一個(gè)非常簡(jiǎn)單非常底層的定時(shí)器咪橙。

libuv中的timer

前面講到夕膀，在http server中每一個(gè)新的連接并不會(huì)真的就去創(chuàng)建一個(gè)Timer對(duì)象。同樣美侦，在nodejs底層的定時(shí)器中产舞，并不會(huì)每次創(chuàng)建一個(gè)Timer對(duì)象就在kqueue上注冊(cè)一個(gè)事件等待超時(shí)。優(yōu)化的思路和nodejs中的timer模塊很相似菠剩，只不過(guò)現(xiàn)在不能保證每個(gè)定時(shí)器的超時(shí)時(shí)間都一樣易猫。

定時(shí)器有一個(gè)非常顯著的特征，超時(shí)時(shí)間最短的定時(shí)器一定最先觸發(fā)具壮，假設(shè)我們有很多的定時(shí)任務(wù)准颓，每個(gè)任務(wù)的執(zhí)行時(shí)間都不同。當(dāng)?shù)谝粋€(gè)定時(shí)器超時(shí)后棺妓，便從這些任務(wù)中查找出已經(jīng)到點(diǎn)的任務(wù)并執(zhí)行對(duì)應(yīng)的超時(shí)處理攘已，然后再重新計(jì)算余下任務(wù)中最先執(zhí)行的時(shí)間，并根據(jù)這個(gè)時(shí)間再次開(kāi)啟一個(gè)定時(shí)器怜跑。

對(duì)應(yīng)的算法需求就是每次都需要查找集合中最小的元素样勃，顯然二叉堆中的最小堆(父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值)是最適合不過(guò)的一種數(shù)據(jù)結(jié)構(gòu)了。由于最小的元素總是處于根節(jié)點(diǎn)，我們可以以O(shè)(1)時(shí)間找到最小值彤灶。對(duì)于插入操作看幼，在最壞的情況下，新插入的節(jié)點(diǎn)需要不斷的和它的父節(jié)點(diǎn)進(jìn)行交換幌陕，直到它為根節(jié)點(diǎn)為止诵姜。假設(shè)堆的高度為h, 二叉樹(shù)最多有2^(h+1) - 1 個(gè) 節(jié)點(diǎn). 因此新插入一個(gè)節(jié)點(diǎn)最多需要log(n+1) -1 次比較，其算法復(fù)雜度為O(logn)搏熄。

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

libuv中已經(jīng)實(shí)現(xiàn)了一個(gè)最小二叉堆的算法https://github.com/joyent/libuv/blob/master/src/heap-inl.h, 下面我們就用這個(gè)算法來(lái)實(shí)現(xiàn)一個(gè)支持設(shè)置不同超時(shí)時(shí)間的定時(shí)器棚唆。

#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;
}

執(zhí)行g(shù)cc timer.c -o timer && ./timer后輸出

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!

可以看到我們?cè)O(shè)置的9個(gè)定時(shí)器都預(yù)期執(zhí)行了，除了有5ms以?xún)?nèi)的偏差心例。這就是nodejs中最底層的定時(shí)器實(shí)現(xiàn)了宵凌。

nodejs中的timer

我們?cè)倩氐絥odejs中的timer模塊，為了不影響到nodejs中的event loop止后，timer模塊專(zhuān)門(mén)提供了一些內(nèi)部的api(timers._unrefActive)給像socket這樣的對(duì)象使用瞎惫。

timer內(nèi)部會(huì)維護(hù)一個(gè)unrefList鏈表以及一個(gè)unrefTimer Timer對(duì)象，當(dāng)有新的超時(shí)任務(wù)到來(lái)時(shí)便會(huì)添加到unrefList中译株，超時(shí)后便從unrefList中取出任務(wù)執(zhí)行瓜喇。

在最初的設(shè)計(jì)中，每次執(zhí)行_unrefActive添加任務(wù)時(shí)都會(huì)維持著unrefList的順序歉糜，保證超時(shí)時(shí)間最小的處于前面乘寒。這樣在定時(shí)器超時(shí)后便可以以最快的速度處理超時(shí)任務(wù)并設(shè)置下一個(gè)定時(shí)器，但是在添加任務(wù)時(shí)最壞的情況下需要遍歷unrefList鏈表中的所有節(jié)點(diǎn)匪补。具體實(shí)現(xiàn)可參考https://github.com/nodejs/node/blob/5abd4ac079b390467360d671a186a061b5aba736/lib/timers.js

很顯然伞辛，在web開(kāi)發(fā)中建立連接是最頻繁的操作，那么向unrefList鏈表中添加節(jié)點(diǎn)也就非常頻繁了夯缺，而且最開(kāi)始設(shè)置的定時(shí)器其實(shí)最后真正會(huì)超時(shí)的非常少蚤氏，因?yàn)橹虚g涉及到io的正常操作時(shí)便會(huì)取消定時(shí)器。所以問(wèn)題就變成最耗性能的操作非常頻繁踊兜，而幾乎不花時(shí)間的操作卻很少被執(zhí)行到瞧捌。

針對(duì)這種情況，如何解決呢润文？目前在node社區(qū)主要有2種方案。

使用不排序的鏈表

主要思路就是將對(duì)unrefList鏈表的遍歷操作殿怜，移到unrefTimeout定時(shí)器超時(shí)處理中典蝌。這樣每次查找出已經(jīng)超時(shí)的任務(wù)就需要花比較多的時(shí)間了O(n)，但是插入操作卻變得非常簡(jiǎn)單O(1)头谜，而插入節(jié)點(diǎn)正是最頻繁的操作骏掀。

使用二叉堆

原理和libuv中的timer實(shí)現(xiàn)一樣，添加和查找一個(gè)節(jié)點(diǎn)都能達(dá)到O(log(n))的復(fù)雜度(找出最小節(jié)點(diǎn)本身很快，但是刪除它需要O(log(n))的復(fù)雜度)截驮，能夠在二者之間保持一個(gè)很好的平衡笑陈。

benchamark

這2種方案都有比較詳細(xì)benchamark數(shù)據(jù)， 具體可參考https://github.com/nodejs/node-v0.x-archive/wiki/Optimizing-_unrefActive

小結(jié)

在高并發(fā)連接到來(lái)并且很少有實(shí)際的超時(shí)事件發(fā)生時(shí)unrefList使用沒(méi)有排序的鏈表來(lái)存儲(chǔ)超時(shí)任務(wù)時(shí)性能是非常棒的葵袭。但是一旦出現(xiàn)很多超時(shí)事件都發(fā)生的情況下涵妥，對(duì)超時(shí)事件的處理會(huì)再次變成一個(gè)瓶頸。

而使用二叉堆來(lái)存儲(chǔ)超時(shí)任務(wù)時(shí)坡锡，當(dāng)有大量超時(shí)事件發(fā)生時(shí)性能會(huì)比鏈表好很多蓬网，沒(méi)有超時(shí)事件觸發(fā)時(shí)性能比鏈表稍差。

可見(jiàn)nodejs在不同的場(chǎng)景中使用的定時(shí)器實(shí)現(xiàn)也不都一樣鹉勒，說(shuō)nodejs對(duì)性能的追求達(dá)到極致一點(diǎn)也不為過(guò)帆锋。當(dāng)我們自己在實(shí)際的開(kāi)發(fā)時(shí)，如果需要使用到定時(shí)器功能禽额，不妨好好思考下哪種方案更適合業(yè)務(wù)場(chǎng)景锯厢，能夠最大的提升timer模塊的性能。

參考文檔

• HTTP Keep Alive分析與優(yōu)化總結(jié)
• 使用 kqueue 在 FreeBSD 上開(kāi)發(fā)高性能應(yīng)用服務(wù)器
• https://github.com/nodejs/node/blob/master/lib/timers.js
• https://github.com/nodejs/node/commit/e5bb66886bfa40818de7a96e982c5964eef9eb78
• https://github.com/nodejs/node-v0.x-archive/wiki/Optimizing-_unrefActive
• http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod#Be_smart_about_timeouts
• binary heap