Lots of timers in node.js
Hello, readers of this article! I have liked the javascript language for a long time. It is considered to be a language with a low entry threshold, but despite this, if you look closely, you can find a lot of interesting things around it.
Node.js is a popular environment for javascript execution today. This environment, among other things, provides an API for working with timers, similar to the one in browsers. I became interested in understanding in detail how these timers work in node.js. I would like to share with you some of the results of my research.
Getting ready to deal with timers
It is known that in node.js timers are implemented within the libuv library. This library, in addition to supporting timers, contains a lot of other functionality, so in order to concentrate specifically on timers, I decided to throw out all the unnecessary and based on original libuv created your own analogue of libuvwhich contains only timers. I kept the directory structure, file names, functions, structures and their fields unchanged, so that it would be easier to compare them with the real libuv later. One of the key features of libuv is that this library is cross-platform, and I use Linux, so I also threw out everything that does not concern Linux. In the end, about 600 lines of code remained – this is already easier to navigate.
Data structures in action
First, let's look at what happens when we start the timer. There are a lot of illustrations on the web of how the event loop works, and these illustrations, in my opinion, give an abstract idea of what is happening. But here we will see in detail what is actually happening.
When we start timers, the order in which they are saved is determined by the order in which the corresponding function is called in the program code, but they will not work in this order, but in the order that will be determined by the timeouts that we passed when starting the timers. That is, the structure that will store the timers must support two operations: add a timer and return the closest “ripe” timer. Thus, we come to an abstract data type called priority queue. It can be implemented in different ways. Let's think about what data structures we can use to do this. For example, we can store timer values in an unsorted array or list, then adding an element will have complexity O(1), and retrieving it will have complexity O(N), where N is the number of elements. On the other hand, we can store elements in a sorted array or list, then adding will have complexity O(N), and retrieving it will have complexity O(1). Of course, we would like to be able to do everything in O(1), but this is impossible 🙂 But, nevertheless, there is such a data structure that allows both adding and retrieving an element faster than in O(N). This data structure is called heap. It allows adding and removing an element in O(log N). Every time we start a timer, its handle goes into a data structure, which is binary min heap. The heap is minimal because we prioritize timers with the smallest timeout, so they should be closer to the root of the heap. And since the heap is minimal, to extract the closest timer, we simply extract the root element from the heap. By the way, to simply find out the value of the closest timer, it is enough to simply access the root element, which is done in O(1).
Event Cycle Time and Timer Priorities
We have figured out that a priority queue implemented through a heap is used to store timers. But what values are used as priorities? Timers are closely related to the event loop – when we create a timer, we always specify a connection to the structure that is responsible for the event loop. Timers are also triggered within the event loop. In turn, the structure for servicing the event loop contains a pointer to the heap with timers. It also contains a special field that stores the number of milliseconds, starting from some unspecified point in the past, which does not change after the system is launched. For example, in Linux, the clock_gettime system call is used for this. This field is updated at each iteration of the event loop. When we start a timer, we specify a timeout. So, the sum of the timeout values and the event loop time will be used as a priority for the timer.
When the “ripe” timers are collected
Now let's see how it turns out whether the timer is “ripe” or not. To do this, simply compare the priority of the nearest timer (which is at the root of the heap) with the cycle time, which was mentioned above. If the cycle time has caught up with the timer priority, then we take it from the heap. But when to do this check? Of course, you can constantly look at the heap in a cycle, and eventually we will wait for a situation when you can take the timer. But we get an active wait, which leads to a useless waste of processor time. Therefore, we ask the operating system to put our process to sleep for a time equal to the difference between the priority of the nearest timer (at the root of the heap) and the cycle time. In Linux, the epoll software interface is used for this, which allows you to not only block a process for a certain time, but also wake up the process if input or output appears. Of course, if libuv only had timers, you could use simpler system calls to block the process.
How “ripe” timers are collected and callbacks are fired
Timers are extracted from the heap in a loop, because there may be several “ripe” timers. Then, very importantly, these timers are first moved to a temporary queue, and then, again in a loop, this queue is parsed and callbacks are executed for the timers. Why not immediately execute the callback for a timer as soon as we extract it from the heap? This cannot be done, because, for example, we can start a timer with a zero timeout, and inside the callback for this timer there may be logic that starts the same timer again, then this timer will be constantly added to the heap as “ripe”, and then our cycle of parsing timers from the heap will turn into an infinite one.
Let's conduct an experiment
Let's look at an example of how it all works.
#include <stdio.h>
#include <uv.h>
struct timer {
uv_timer_t timer;
uint64_t timeout;
};
void timer_callback(uv_timer_t *handle) {
printf("timer callback invoked, timeout = %ld\n", handle->timeout);
}
int main() {
int i;
uv_loop_t loop;
struct timer timers[] = {
{ timeout: 6000 },
{ timeout: 2000 },
{ timeout: 3000 },
{ timeout: 2000 },
{ timeout: 1000 },
{ timeout: 4000 },
{ timeout: 2000 },
{ timeout: 5000 },
};
uv_loop_init(&loop);
for (i = 0; i < sizeof(timers) / sizeof(*timers); i++) {
struct timer *timer = &timers[i];
uv_timer_init(&loop, &timer->timer);
uv_timer_start(&timer->timer, timer_callback, timer->timeout, 0);
}
return uv_run(&loop, UV_RUN_DEFAULT);
}In this example, several timers are created in sequence with timeouts of 6000, 2000, 3000, 2000, 1000, 4000, 2000, 5000. Let's assume that the cycle time at the start of the timers was 88456245. As a result, the heap with timers will look like this:
At the top of the rectangles in the diagram is the final priority, which is the sum of the timer timeout and the event loop time.
Then the event loop starts. Every time the timers “catch up,” the root element will be taken from the heap and moved to the queue, and the heap will be sifted to always match the heap property. For timers with a timeout of 2000 (we have three of these), when it comes time to sort the heap, a queue of three timers is formed. For all other cases, there will be only one timer in the queue.
If you run this example and use the strace utility, which shows what system calls were made during program execution, the output will look something like this:
$ strace --trace epoll_wait ./timers
epoll_wait(3, NULL, 1, 999) = 0
timer callback invoked, timeout = 88457245
epoll_wait(3, NULL, 1, 999) = 0
timer callback invoked, timeout = 88458245
timer callback invoked, timeout = 88458245
timer callback invoked, timeout = 88458245
epoll_wait(3, NULL, 1, 998) = 0
timer callback invoked, timeout = 88459245
epoll_wait(3, NULL, 1, 998) = 0
timer callback invoked, timeout = 88460245
epoll_wait(3, NULL, 1, 998) = 0
timer callback invoked, timeout = 88461245
epoll_wait(3, NULL, 1, 998) = 0
timer callback invoked, timeout = 88462245
+++ exited with 0 +++It is clear that the process went to sleep six times for slightly less than 1000 ms. Slightly less because each time, either 1 ms or 2 ms, the process had something to work on before going to sleep.
setTimeout vs setInterval
At the libuv level, the same function is used to implement setTimeout and setInterval functionality:
int uv_timer_start(
uv_timer_t* handle,
uv_timer_cb cb,
uint64_t timeout,
uint64_t repeat
);For setTimeout we pass 0 as the repeat value, and for setInterval we specify an interval, and then the timer will simply be restarted:
int uv_timer_again(uv_timer_t* handle) {
if (handle->timer_cb == NULL) {
return -1;
}
if (handle->repeat) {
uv_timer_stop(handle);
uv_timer_start(
handle,
handle->timer_cb,
handle->repeat,
handle->repeat
);
}
return 0;
}About the implementation of heap and queue in libuv
I found it interesting how the heap and queue are implemented in libuv.
The following structure is used for the queue:
struct uv__queue {
struct uv__queue* next;
struct uv__queue* prev;
};And for the heap the following structures are used:
struct heap_node {
struct heap_node* left;
struct heap_node* right;
struct heap_node* parent;
};
struct heap {
struct heap_node* min;
unsigned int nelts;
};It is clear that these structures do not contain information about what exactly is stored in the elements of these structures. There are only pointers to other elements. In turn, the timer descriptor in a simplified version has the structure:
struct uv_timer_s {
uv_loop_t* loop;
unsigned int flags;
uv_timer_cb timer_cb;
...
union {
void* heap[3];
struct uv__queue queue;
} node;
...
uint64_t timeout;
uint64_t repeat;
uint64_t start_id;
};I was interested in the node field, which can be used to determine the timer's location in the heap or queue, depending on the context. It turns out that the timer knows that it is an element of the heap or queue, and not the heap or queue that knows that they store timers. From the address of an element in the heap or queue, we can always understand what exactly this element is using the construction:
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) - offsetof(type, member)))
const struct heap_node* heap_node;
const uv_timer_t* handle;
handle = container_of(heap_node, uv_timer_t, node.heap);That is, knowing the location of a field in a structure, we can get the address of the structure itself. Thus, the heap and queue in libuv can be used for data of any type.
Summary
To summarize my research, I would like to highlight the main points that you need to know in order to understand how timers work in node.js.
Timers are part of the environment in which javascript runs, and in node.js they are implemented at the libuv library level.
When we start a timer, it is added to a heap that the event loop knows about.
The event loop has a field that stores a certain loop time, so that it can be used to compare the priorities of timers, which are made up of the loop time at the start of the timer and its timeout.
Next, a request is made to the operating system in order to block the process until the nearest timer “meets” in order to avoid active waiting.
A “ripe” timer is a timer whose priority value is not greater than the event cycle time.
When any timer “comes up”, all “come up” timers are selected from the pile and moved to the queue.
Then timers are selected from this queue until it is empty and their callbacks are executed.
conclusions
So, it would seem, we use timers all the time, call setTimeout and setInterval, and what's special about that. But if you dig deeper, it turns out that two data structures are used to work with timers – a heap and a queue. And if you look at it from the operating system's point of view, there are no multiple timers at all. It's just that, based on the timers that we created in the user space, the time that the process must sleep is calculated in a certain way in order to then wake up and execute the code from the callbacks.
I found it very interesting to understand this topic. I experienced great pleasure when the picture came together. I will be glad if my research will be useful to someone else.
