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

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

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

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

Замечу, что разных техник в этой документации описано 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 ^[5] в node.js, ускоряющий работу setTimeout() на 5%, в редких случаях на 50%.
2. Отправлен pull request ^[6] в 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. Полезно использовать одни и те же значения таймаутов, чтобы не плодить внутренние таймеры.

Автор: wickedweasel