How does Node.js manage timers internally10 Feb 2017 | node-js
This API provides us with the
clearInterval methods which allows us to schedule code for later execution, either once or repeatedly.
Thanks to Node.js timer module, these methods (along with a few others, such as
clearImmediate) are also available natively
in node code. On top of user code and 3rd-party libraries using timers, timers are also used internally by the Node.js platform itself. For example, a dedicated
timer is used with each TCP connection to detect a possible connection timeout. It’s very possible that Node.js will have to manage a large number of timers, so it’s important that
the implementation will be highly efficient. In this post I will look at the way Node.js manages these timers under the hood.
Before tackling the timers implementation, it’s worthwhile to examine Node.js implementation of linked lists; they play a large role in the timers implementation, and have some interesting parts to them as well.
The relevant code is quite short, and contain all the
methods you’d expect to find in a linked list implementation, such as
One thing to note is that this is not a “Class”, and there is no constructor. Instead, these methods are in fact utility functions
that operate on an existing object. Two fields are used to manage the links between the nodes:
_idleNext points to the older item, while
_idlePrev points to the newer item.
Let’s look at the
In the root object,
_idleNext points to the head of the list (the oldest element) and
_idlePrev points to the tail of the list (the newest element).
Initially, both point to the list root itself.
Let’s continue and look at the
remove functions. Notice that
append first calls
remove to ensure the list is unique.
Notice that at no point we actually traverse the list. Thus,
remove are very efficient, operations.
To make this a bit more concrete, lets initialize a new list and append two items. We’ll show the objects graph after initialization and after each append.
Here’s a diagram of the list right after initialization:
Here’s how it looks after a first append:
Here’s how it looks after a second append:
From this point, I think it’s quite clear how later appends will look. It is now time to look at timers in more detail.
Each Timer instance is initialized with
msec argument which determines the delay (in millisecond) until timeout.
It’s quite intuitive that if we initialized two timers with the same
msec argument, then the second timer will timeout either with or after the first.
Node.js uses this and organizes the Timers by indexing them according to their
msec: all Timers with the same
msec value will form a linked list, ordered
by creation time (there are actually two indexes, one for
refed timers and one for
unrefed timers, but we’ll ignore this fact for now. See
here to read about the difference).
In this example, we initialized 6 timers.
T3 were initialized with 50 msec,
T4 with 10 msec and
T5,T6 with 200 msec.
Each Timers list is backed up by a
TimerWrap, which is a wrapper over a
uv_timer_t, a native libuv timer type.
Since we know the timers in each list are ordered by non-decreasing timeout, a single
TimerWrap is enough, as we can reuse it between timeouts.
In pseudo code, the (a bit simplified) strategy on timeout is as follows:
Once the last timer in a list timeouts, we can remove the list’s
msec key and free the backing native timer.
Same as the
remove operations on linked lists, the timeout operation runs in constant time, regardless the number of scheduled timers.
It follows that less than constant-time operations are limited to 2 places:
- The native libuv timers implementation
- The lookup for certain list of timers based on a
However, according to the source code, these operations combined have shown to be trivial in comparison to other alternative timers architectures.