Архитектура таймеров в node.js

Я бы хотел рассказать о таком замечательном и повсеместно используемом в node.js инструменте, как таймеры, и об их использовании в функциях setTimeout, setInterval и в модуле net. В node.js за таймеры отвечает модуль ядра timers.js. setTimeout — всего лишь доступная глобально функция из этого модуля.

В исходных кодах можно с лёгкостью найти комментарий:

По причине того, что много сокетов будут иметь один и тот же timeout, мы не будем использовать собственный таймер (имеется в виду низкоуровневый таймер из libuv) для каждого из них. Это даёт слишком много накладных расходов. Вместо этого мы будем использовать один такой таймер на пачку сокетов, у которых совпадают моменты таймаута. Сокеты мы будем объединять в двусвязные списки. Эта техника описина в документации libuv: http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod#Be_smart_about_timeouts

Замечу, что разных техник в этой документации описано 4 штуки. Задача, которая решалась: каждый раз при активности сокета, например, при поступлении новых данных, нужно продлять таймер.
Техники перечислены по возрастанию сложности и эффективности:
1. Останавливать, переинициализировать и стартовать таймер по активности. Почти всегда плох. Плюсов нет.
2. Продлять таймер с помощью ev_timer_again. Очень простое решение, которое обычно будет работать нормально.
3. Дать сработать таймеру тогда, когда было изначально запланировано, после этого проверить, нужно ли его продлить еще и на сколько. Сложнее, но в некоторых случаях работает более эффективно.
4. Использовать двусвязные списки для таймаутов. При необходимости продления таймера, он просто переносится из одного листа в другой. Еще сложнее, но крайне эффективно.
Именно 4й вариант реализован в node.js.

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

Что произойдёт, если вы выполните следующий код?

var start = Date.now(); // Зададим относительную точку отсчёта, она нам пригодится для понимания. var Timeout100 = setTimeout(function() {}, 100); // длинный блокирующий цикл на 10мс var Timeout110 = setTimeout(function() {}, 100); var Timeout210 = setTimeout(function() {}, 200); 

А произойдёт следующее. В модуле timers.js есть переменная модуля под названием lists, отвечающая за хранение (почти) всех активных таймеров.
Кратко внутреннюю логику setTimeout можно представить в следующем виде:

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

Таким образом, переменная timer будет содержать 2 ключа:

В момент start +100мс libuv постучится к Timer100, мол, действуй. Реакцией на это будет исполнение того обработчика, о котором я обещал рассказать попозже.

Что же сделает этот обработчик? Его логика тоже не очень сложная:

// тут я схалтурю и опишу переменные, берущиеся в оригинале из замыкания, как аргументы функции 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]; } 

Этот callback в нашем случае будет вызван 3 раза:

1. Момент start + 100:
   
   1. выполняем Timeout1
   2. видим, что до Timeout2 остаётся 10мс, заводим таймер на это время
   3. выходим.
2. Момент start + 110:
   
   1. выполняем Timeout2;
   2. видим, что лист пустой, удаляем Timer100 и ключ lists[100].
   3. выходим.
3. Момент start + 210:
   
   1. выполняем Timeout3;
   2. видим, что лист пустой, удаляем Timer200 и ключ lists[200].
   3. выходим.

clearTimeout(timeout)

Теперь давайте посмотрим, как работает clearTimeout. Эта функция принимает в качестве аргумента тот же объект класса Timeout, что был возвращён из 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];   } } 

Таким образом, если соответствующий Timer продолжит работать, то он уже не обнаружит удалённый item в списке, и, соответственно, не выполнит его. Запустив clearTimeout(Timeout2) сразу после его инициализации, мы превратим:

в

setInterval(callback, msecs, [arg], […]) и clearInterval(interval)

setInterval и clearInterval, в отличие от setTimeout, не используют никаких премудростей. На каждый интервал создаётся новый libuv’шный таймер и заряжается в режиме повторения каждые msecs миллисекунд. При clearinterval он останавливается и удаляется. Всё.

Сокеты (модуль net)

Сокеты не используют перечисленные выше функции.
Для сокетов характерно частое продление таймаутов, поэтому они не создают/удаляют таймеры на каждый пакет, а добавляются в структуру lists сами. Для этого они используют недокументированные функции модуля timers (но я вам этого не рассказывал!).
Таким образом, в реальности структура lists может выглядеть примерно так:

У сокетов в прототипе уже есть метод _onTimeout, поэтому для них не нужны замыкания.
Они просто расширяются свойствами _idleStart, _idleTimeout (свойства для учета времени), _idleNext и _idlePrev (свойства для двусвязного списка).
При поступлении и отправке данных сокет просто удаляется из соответствующего двусвязного списка…

… и сразу же добавляется в его конец:

Побочные эффекты написания этой статьи:

1. Отправлен pull request в node.js, ускоряющий работу setTimeout() на 5%, в редких случаях на 50%.
2. Отправлен pull request в node.js, исправляющий фальстарты таймеров.
3. Я выяснил, что на моих машинах под управлением Ubuntu 12.04 (на второй 11.04) 32 bit + PAE функция Date.now() в node.js и в браузерах работает в 15 раз медленнее, чем должна. Думаю, дело в нижележащем вызове gettimeofday(2). Апгрэйд до 64-битной Ubuntu 12.10 решает эту проблему.

Выводы:

1. Читайте исходные коды инструментов, которыми пользуетесь — узнаете много нового.
2. Разработчики Node.js придерживаются лучших практик работы с таймерами, тем не менее, есть некоторые упущения в реализации.
3. Разгребание очереди наступивших таймаутов происходит в цикле и синхронно.
4. Полезно использовать одни и те же значения таймаутов, чтобы не плодить внутренние таймеры.