Timer Architecture in node.js

I would like to talk about such a wonderful and commonly used tool in node.js as timers, and about their use in the setTimeout, setInterval functions and in the net module. In node.js, the timers.js kernel module is responsible for the timers. setTimeout is just a globally accessible function from this module.

In the source code, you can easily find a comment:

Due to the fact that many sockets will have the same timeout, we will not use our own timer (meaning the low-level timer from libuv ) for each of them. This gives too much overhead. Instead, we will use one such timer per packet of sockets, which have timeout times. Sockets we will merge into doubly linked lists . This technique is described in the libuv documentation: http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod#Be_smart_about_timeouts

I note that different techniques in this documentation describe 4 pieces. The problem that was solved: every time the socket is active, for example, when new data is received, the timer must be extended.
Techniques are listed in order of increasing complexity and efficiency:
1. Stop, re-initialize and start the timer by activity. Almost always bad. There are no pluses.
2. Extend the timer using ev_timer_again. A very simple solution that will normally work fine.
3. Let the timer work when it was originally planned, then check whether it needs to be extended further and by how much. More difficult, but in some cases it works more efficiently.
4. Use doubly linked lists for timeouts. If the timer needs to be extended, it is simply transferred to the end of the doubly linked list. Even more difficult, but extremely effective.
It is the 4th option implemented in node.js.

setTimeout (callback, msecs, [arg], [...])

What happens if you run the following code?

var start = Date.now(); //    ,     . var Timeout100 = setTimeout(function() {}, 100); //     10 var Timeout110 = setTimeout(function() {}, 100); var Timeout210 = setTimeout(function() {}, 200); 

And the following will happen. In the timers.js module, there is a module variable called lists, which is responsible for storing (almost) all active timers.
Briefly, the internal logic of setTimeout can be represented as follows:

 function setTimeout(callback, msecs) { var list = lists[msecs]; //      ,   ,     //     msecs. if (!list) { //    process.binding('timer_wrap').Timer ,  libuv' . list = lists[msecs] = new Timer(); //    ,   . list.ontimeout = ...; //  . list.start(msecs, 0); //  ,       . L.init(list); } //   ,       callback  msecs . var item = Timeout; item._idleStart = Date.now(); //    item._idleTimeout = msecs; //   item._onTimeout = callback; //    //      . // ,         //   item',  ..     ,    //      . L.append(list, item); return item; } 

')
Thus, the timer variable will contain 2 keys:


At the moment of start + 100ms libuv will knock on Timer100, say, act. The response to this will be the execution of that handler, which I promised to talk about later.

What will this handler do? Its logic is also not very complicated:

 //      ,     ,    function callback(Timer list, msecs) { var now = Date.now(); var first; //       ,    ,    , //    ,   .   . while(first = L.peek()) { // ,     var wait = item._idleStart + item._idleTimeout - now; //     if (wait <= 0) { //     L.remove(first); //  callback first.onTimeout(); } else { //    wait  list.start(wait, 0); // , ..      -   //       return; } } //     , ,   . //  . list.stop(); //   delete lists[msecs]; } 

This callback in our case will be called 3 times:

1. Moment start + 100:
   
   1. perform Timeout1
   2. we see that there is 10ms to Timeout2, we start a timer for this time
   3. we leave.
2. Moment start + 110:
   
   1. perform Timeout2;
   2. see that the sheet is empty, delete Timer100 and key lists [100].
   3. we leave.
3. Moment start + 210:
   
   1. perform Timeout3;
   2. we see that the sheet is empty, delete Timer200 and key lists [200].
   3. we leave.

clearTimeout (timeout)

Now let's see how clearTimeout works. This function takes as argument the same Timeout object that was returned from setTimeout.

 function clearTimeout(item) { //    . L.remove(item); var msecs = item._idleTimeout; //   var list = lists[msecs]; //   ,  if (list && L.isEmpty(list)) { list.close(); delete lists[msecs]; } } 

Thus, if the corresponding Timer continues to work, it will no longer detect the deleted item in the list, and, accordingly, will not execute it. Having started clearTimeout (Timeout2) right after its initialization, we will transform:

at

setInterval (callback, msecs, [arg], [...]) and clearInterval (interval)

setInterval and clearInterval, unlike setTimeout, do not use any intricacies. At each interval, a new timer is created in libuv'sh and charged in repeat mode every msecs milliseconds. With clearinterval, it stops and deletes. Everything.

Sockets (net module)

Sockets do not use the functions listed above.
Sockets are characterized by frequent timeout extensions, so they do not create / delete timers for each packet, but add themselves to the lists structure. To do this, they use the undocumented functions of the timers module (but I did not tell you this!).
Thus, in reality, the structure of lists may look like this:

Sockets in the prototype already have a _onTimeout method, so no closures are needed for them.
They are simply extended with the _idleStart, _idleTimeout (time keeping properties), _idleNext and _idlePrev properties (properties for a doubly linked list).
When data is received and sent, the socket is simply deleted from the corresponding doubly linked list ...

... and immediately added to its end:

Side effects of writing this article:

1. A pull request was sent to node.js, which speeds up setTimeout () by 5%, in rare cases by 50%.
2. Sent a pull request to node.js, correcting the false starts of the timers.
3. I found out that on my machines running Ubuntu 12.04 (on the second - 11.04) 32 bit + PAE the Date.now () function in node.js and in browsers is 15 times slower than it should. I think the point is in the underlying gettimeofday (2) call. Upgrading to 64-bit Ubuntu 12.10 solves this problem.

Findings:

1. Read the source codes of the tools you use - you will learn a lot of new things.
2. Node.js developers adhere to best practices for working with timers, however, there are some omissions in implementation.
3. The raking of the queue of arrived timeouts occurs in a loop and synchronously.
4. It is useful to use the same timeout values ​​in order not to produce internal timers.