Куча таймеров в node.js
Приветствую вас, читатели этой статьи! Мне с давних пор нравится язык javascript. Считается, что это язык с низким порогом входа, но, несмотря на это, если приглядеться, можно найти много интересного вокруг него.
На сегодняшний день node.js является популярной средой для выполнения javascript. Эта среда, помимо всего прочего, предоставляет API для работы с таймерами, схожий с тем, который есть в браузерах. Мне стало интересно досконально разобраться с тем, как работают эти таймеры в node.js. Я хотел бы поделиться с вами некоторыми результатами своих исследований.
Готовимся разбираться с таймерами
Известно, что в node.js таймеры реализованы в рамках библиотеки libuv. Эта библиотека помимо поддержки таймеров содержит еще много другого функционала, поэтому, чтобы сконцентрироваться именно на таймерах, я решил выбросить все лишнее и на основе оригинального libuv создал свой собственный аналог libuv, который содержит только таймеры. Я сохранил структуру каталогов, названия файлов, функций, структур и их полей неизменными, чтобы проще было потом сопоставить их с настоящим libuv. Одна из ключевых особенностей libuv — это то, что эта библиотека кроссплатформенная, а я использую linux, поэтому также выбросил еще и все то, что не касается linux. В итоге осталось около 600 строчек кода — в этом уже проще ориентироваться.
Структуры данных в деле
Для начала рассмотрим, что происходит, когда мы стартуем таймер. В сети очень много иллюстраций, как работает цикл событий, и эти иллюстрации, на мой взгляд, дают абстрактное представление о том, что происходит. Но здесь мы в деталях увидим, что происходит на самом деле.
Когда мы стартуем таймеры, порядок их сохранения определяется порядком вызова соответствующей функции в коде программы, но сработают они не в этом же порядке, а в порядке, который будет определяться таймаутами, которые мы передавали при старте таймеров. То есть структура, которая будет хранить таймеры, должна поддерживать две операции: добавить таймер и вернуть ближайший «поспевший» таймер. Таким образом, мы подходим с вами к абстрактному типу данных, который называется очередь с приоритетом. Реализовать ее можно различными способами. Давайте подумаем, на основе каких структур данных мы можем это сделать. Например, мы можем хранить значения таймеров в неотсортированном массиве или списке, тогда добавление элемента будет иметь сложность O (1), а извлечение — O (N), где N — количество элементов. С другой стороны, мы можем хранить элементы в отсортированном массиве или списке, тогда добавление будет иметь сложность O (N), а извлечение — O (1). Конечно, хотелось бы все уметь делать за O (1), но это невозможно :) Но, все же, есть такая структура данных, которая позволяет и добавлять, и извлекать элемент быстрее, чем за O (N). Эта структура данных называется куча. Она позволяет добавлять и извлекать элемент за O (log N). Каждый раз, когда мы стартуем таймер, его дескриптор попадает в структуру данных, которая является двоичной минимальной кучей. Куча минимальная, потому что для нас приоритетнее таймеры с наименьшим таймаутом, поэтому они должны быть ближе к корню кучи. И, поскольку куча минимальная, чтобы извлечь ближайший таймер, мы просто извлекаем корневой элемент из кучи. Кстати, чтобы просто узнать значение ближайшего таймера, достаточно просто обратиться к корневому элементу, что делается за O (1).
Время цикла событий и приоритеты таймеров
Мы разобрались, что для хранения таймеров используется очередь с приоритетом, реализованная через кучу. Но какие именно значения используются в качестве приоритетов? Таймеры тесно связаны с циклом событий — когда мы создаем таймер, мы обязательно указываем связь со структурой, которая отвечает за цикл событий. Срабатывают таймеры тоже в рамках цикла событий. В свою очередь, структура для обслуживания цикла событий содержит в себе указатель на кучу с таймерами. А также она содержит специальное поле, которое хранит количество миллисекунд, начиная с какого-то неопределенного момента в прошлом, который не меняется после запуска системы. Например, в linux для этого используется системный вызов clock_gettime. Это поле обновляется на каждой итерации цикла событий. Когда мы стартуем таймер, мы указываем таймаут. Так вот, в качестве приоритета для таймера будет использоваться сумма значений таймаута и времени цикла событий.
Когда собираются «поспевшие» таймеры
Теперь посмотрим, как выясняется, «поспел» таймер или нет. Для этого просто сравнивается приоритет ближайшего таймера (который стоит в корне кучи) со временем цикла, про которые было упомянуто выше. Если время цикла настигло приоритет таймера, то мы забираем его из кучи. Но когда делать эту проверку? Конечно, можно в цикле постоянно смотреть на кучу, и в конце концов мы дождемся ситуацию, когда можно забирать таймер. Но мы получаем активное ожидание, которое приводит к бесполезной трате процессорного времени. Поэтому мы просим операционную систему усыпить наш процесс на время, равное разности приоритета ближайшего таймера (в корне кучи) и времени цикла. В linux для этого используется программный интерфейс epoll, который позволяет не просто заблокировать процесс на определенное время, но еще и пробуждать процесс, если появляется ввод или вывод. Конечно, если бы в libuv были одни таймеры, можно было бы применять более простые системные вызовы, чтобы заблокировать процесс.
Как собираются «поспевшие» таймеры и запускаются колбеки
Таймеры извлекаются из кучи в цикле, потому что может быть несколько «поспевших» таймеров. Затем, что очень важно, эти таймеры сначала перекладываются во временную очередь, а потом, опять таки в цикле, разбирается эта очередь и выполняются колбеки у таймеров. Почему бы сразу не выполнять колбек у таймера, как только мы его извлекли из кучи? Так нельзя делать, потому что, к примеру, мы можем стартовать таймер с нулевым таймаутом, а внутри колбека у этого таймера может быть логика, которая опять стартует этот же таймер, тогда этот таймер будет постоянно добавляться в кучу как «поспевший», и тогда наш цикл по разбору таймеров из кучи превратится в бесконечный.
Проведем эксперимент
Посмотрим на примере, как все это работает.
#include
#include
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);
} В этом примере создается последовательно несколько таймеров с таймаутами 6000, 2000, 3000, 2000, 1000, 4000, 2000, 5000. Предположим, что время цикла на момент старта таймеров было 88456245. В результате, куча с таймерами примет вид:
Вверху прямоугольников на диаграмме указан итоговый приоритет, который складывается из таймаута таймера и времени цикла событий.
Затем запускается цикл событий. Каждый раз, когда будут «поспевать» таймеры, из кучи будет забираться корневой элемент и перекладываться в очередь, а куча будет просеиваться, чтобы всегда соответствовать свойству кучи. Для таймеров с таймаутом 2000 (таких у нас три), когда придет время разбирать кучу, формируется очередь из трех таймеров. Для всех остальных случаев в очереди будет только один таймер.
Если при запуске этого примера использовать утилиту strace, которая показывает, какие системные вызовы были сделаны в ходе выполнения программы, то вывод будет примерно таким:
$ 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 +++Видно, что процесс засыпал шесть раз чуть меньше, чем на 1000 мс. Чуть меньше, потому что каждый раз то 1 мс, то 2 мс процессу было над чем поработать прежде, чем заснуть.
setTimeout vs setInterval
На уровне libuv для реализации функциональности setTimeout и setInterval используется одна и та же функция:
int uv_timer_start(
uv_timer_t* handle,
uv_timer_cb cb,
uint64_t timeout,
uint64_t repeat
);Для setTimeout мы передаем в нее 0 в качестве значения repeat, а в случае с setInterval мы указываем интервал, и тогда просто таймер будет перезапущен:
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;
}О реализации кучи и очереди в libuv
Любопытным мне показалось то, как реализованы куча и очередь в libuv.
Для очереди используется структура:
struct uv__queue {
struct uv__queue* next;
struct uv__queue* prev;
};А для кучи используются структуры:
struct heap_node {
struct heap_node* left;
struct heap_node* right;
struct heap_node* parent;
};
struct heap {
struct heap_node* min;
unsigned int nelts;
};Видно, что эти структуры не содержат информации о том, что конкретно хранится в элементах этих структур. Есть только указатели на другие элементы. В свою очередь, дескриптор таймера в упрощенном варианте имеет структуру:
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;
};Интерес у меня вызвало поле node, которое может использоваться для определения места таймера в куче либо в очереди, в зависимости от контекста. Получается, что это таймер знает, что он является элементом кучи или очереди, а не куча или очередь знает, что в них хранятся таймеры. По адресу элемента в куче или очереди мы всегда можем понять, что именно из себя представляет этот элемент с помощью конструкции:
#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);То есть, зная место поля в структуре, мы можем получить адрес самой структуры. Таким образом, кучу и очередь в libuv можно применять для данных любого типа.
Резюме
Подводя итог своим исследованиям, я бы хотел выделить основные моменты, про которые нужно знать, чтобы понимать, как работают таймеры в node.js.
Таймеры являются частью окружения, в котором работает javascript, и в node.js они реализованы на уровне библиотеки libuv.
Когда мы стартуем таймер, он добавляется в кучу, про которую знает цикл событий.
У цикла событий есть поле, которое хранит некое время цикла, чтобы с ним потом сравнивать приоритеты таймеров, которые складываются из времени цикла на момент старта таймера и его таймаута.
Далее выполняется запрос к операционной системе с целью блокировать процесс до «поспевания» ближайшего таймера, чтобы избежать активного ожидания.
«Поспевший» таймер — это таймер, у которого значение приоритета не больше времени цикла событий.
Когда какой-нибудь таймер «поспевает», из кучи выбираются все «поспевшие» таймеры и перекладываются в очередь.
Затем из этой очереди, пока она не опустеет, выбираются таймеры и выполняются их колбеки.
Выводы
Вот так, казалось бы, все время пользуемся таймерами, вызываем setTimeout и setInterval, и что тут особенного. А если копнуть вглубь, то оказывается, что для работы с таймерами применяются две структуры данных — куча и очередь. И если смотреть с точки зрения операционной системы, то нет вообще никаких нескольких таймеров. Просто, исходя из таймеров, которые мы насоздавали в пространстве пользователя, рассчитывается определенным образом время, которое должен проспать процесс, чтобы потом проснуться и выполнить код из колбеков.
Мне было очень интересно разбираться с этой темой. Я испытал большое удовольствие, когда картинка сложилась. Буду рад, если мои исследования еще кому-то пригодятся.
