[prog.с++] Продолжение про реализации таймеров. Идентификация таймеров

Обещанное продолжение темы про особенности самодельной реализации различных типов таймеров. Продолжение выходит чуть позже, чем я рассчитывал, но мне нужно было довести свою реализацию до работоспособного состояния, чтобы не получилось так, что говорю о вещах, работоспособность которых сам не проверил.

Итак, речь идет об обслуживании таймеров посредством отдельной нити. Эта таймерная нить складирует таймеры (таймерные заявки) в какой-то специализированной структуре данных. Из этой структуры каким-то образом выбираются таймеры, подлежащие обслуживанию и запускается код для их обработки. Если готовых для обработки таймеров нет, то нить определяет время, на которое можно заснуть и засыпает. Просыпается нить либо при наступлении времени обработки очередной порции заявок, либо же при получении сигнала на завершение работы.

Таймерные нити могут использовать разные структуры данных, каждая из которых предоставляет свой компромисс между эффективностью/накладными расходами. Что позволяет выбирать наиболее оптимальный тип таймера для прикладной задачи.

Для чего нужна идентификация заявок?

Главная причина -- это предоставление пользователю возможности отменить свою заявку. Например, есть программа для приема запросов от удаленной стороны, валидации и трансформации полученных запросов, передачи их бэк-энду, получение ответа и трансляция ответа бэк-энда обратно удаленной стороне. Получив запрос и переслав его бэк-энду, пользователь может завести периодический таймер. По тикам этого таймера запрос к бэк-энду будет повторяться. После N безуспешных попыток достучаться до бэк-энда удаленной стороне отсылается отрицательный ответ. Но таймер становится больше не нужен и он должен быть удален. Для этого нужно каким-то образом идентифицировать таймер, чтобы таймерная нить удалила именно его, а не еще сотню-другую тысяч параллельно обслуживаемых таймеров.

В процессе разбирательства с тем, как реализуются таймерные нити, я обнаружил, что используются два способа идентификации. Вполне очевидных, если подумать :)

Первый способ -- это прямая идентификация. Т.е. пользователь получает в распоряжение объект, который, собственно, и является самой таймерной заявкой. Ссылки на этот объект сохраняются внутри структур данных таймерной нити.

Такой подход характерен для чистых C-шных библиотек. Там, как я видел, таймер -- это просто экземпляр какой-то структуры, который должен быть создан самим пользователем. Например, в libuv:

uv_timer_t timer; // Фактически, выделили память под таймер.
uv_timer_init(uv_default_loop(), &timer); // Инициализировали таймер.
uv_timer_start(&timer, timer_cb, 50, 0); // Запустили таймер.

В принципе, такой подход разумен для чистого C, где не очень принято делать копирование объектов. Таймер может быть статической переменной в небольшой программке. Или же частью большой структуры, которая создается при начале обработке запроса, а затем удаляется вместе со всем, что относилось к этому запросу.

Кроме того, подход на основе прямой идентификации, когда пользователь сам отвечает на создание и удаление объектов-таймеров, можно вообще обойтись без использования динамической памяти внутри таймерной нити и ее структур данных.

Как обычно в C, если пользователь лопухнулся со своими предположениями о времени жизни созданного им таймера и освободил принадлежащую таймеру память раньше времени, произойдет что-нибудь неприятное, т.к. внутри таймерной нити останутся повисшие указатели на этот уже разрушенный таймер.

Второй способ -- это косвенная идентификация. Т.е. пользователь не отвечает за создание у себя экземпляра таймерной заявки и за контроль времени ее жизни. Вместо этого таймерную заявку создает сама таймерная нить, а пользователю возвращается какой-то обезличенный и непрозрачный идентификатор. Например, 64-битовое целое число.

Подход с косвенной идентификацией используется, например, в ACE Framework. Там идентификатором таймера является целое число типа long. Это число возвращается методом schedule. А что за ним скрывается пользователь не видит и не знает.

Как и во многих других вещах, в борьбе между двумя этими подходами нет однозначного победителя, т.к. у каждого есть свои достоинства и недостатки. И каждый хорош в своей ситуации.

Прямая идентификация удобна своей простотой и эффективностью. А, еще, как бы неожиданно это не звучало, некоторой безопасностью :) Странно звучит после того, как я упомянул про неприятности из-за не вовремя удаленного таймера, но речь идет вот о чем: с однократными таймерами бывают ситуации, когда таймер уже сработал, таймерная нить выбросила его из своих структур данных, а пользователь вдруг решает отменить этот таймер.

Если объект таймера принадлежит пользователю, то в таком сценарии нет ничего страшного. Как правило в таймере есть какие-то ссылки, описывающие расположение таймера внутри структуры данных таймерной нити. Например, если нить работает по принципу timer_list, то это будут ссылки на следующий и предыдущий элементы списка таймеров. Так вот, при изъятии таймера из своей структуры данных таймерной нити достаточно просто занулить данные ссылки или же в самом таймере выставить какой-то признак, что он не активен.

А вот при косвенной идентификации ситуация сложнее. Например, нить таймера реализована так, что идентификатором таймера является индекс в каком-то внутреннем массиве. Поскольку массив этот конечен, а таймеров приложение может создавать за время своей работы сотни миллионов, а то и миллиарды раз, то очевидно, что идентификаторы таймеров будут переиспользоваться. Что означает, что когда кто-то пытается удалить таймер с идентификатором X, существует ненулевая вероятность, что этот идентификатор уже был ранее освобожден и затем выдан совсем другому таймеру.

Насколько вероятен такой сценарий сказать сложно. Тем не менее, прямая идентификация этой проблемы не имеет вообще.

Зато косвенная идентификация позволяет скрыть внутри таймерной нити конкретный способ обслуживания таймеров. Ведь для каждого механизма обслуживания нужна своя структура таймерной заявки. Например, для timer_wheel в заявке нужно хранить номер позиции в "колесе", количество оставшихся полных оборотов "колеса", ссылки на соседей по текущей позиции в колесе. А вот для timer_list нужно иметь точное время срабатывания заявки и ссылки на соседей в списке. Для timer_set (где базовой структурой будет упорядоченное двоичное дерево, например rb-tree) -- точное время срабатывание, ссылки на родительский узел, на дочерние узлы + еще какая-то специфическая для типа дерева информация (скажем, цвет узла для rb-tree).

При использовании косвенной идентификации вся эта кухня может быть скрыта от пользователя. Наружу может быть выставлен один унифицированный интерфейс таймерной нити, а использующийся внутри механизм может настраиваться параметрами при создании таймерной нити. Пользователю будет без разницы, как именно обслуживаются его таймеры, он всегда будет работать с одним и тем же типом идентификаторов. Именно такой подход взят за основу таймеров в ACE Framework, где за единым фасадом скрыта целая куча реализаций: timer_wheel, timer_list, timer_heap и timer_hash.

С другой стороны, косвенность приводит к дополнительным накладным расходам. Т.к. таймерная нить вынуждена поддерживать, как минимум, две параллельные структуры данных: какой-то словарь/массив идентификаторов, откуда ведут ссылки на конкретную структуру с таймерными заявками (wheel, list, set, heap и т.д.). Соответственно, для того, чтобы обратиться к таймеру по его идентификатору, нужно пройти по двум структурам. Очевидно, что это не бесплатно.

Кроме скорости доступа к таймерной заявке при косвенной индексации плохо еще и то, что это усложнение реализации таймера. Все-таки две структуры -- это не одна, их нужно держать согласованными. А ведь может быть еще и третья структура: если идентификаторы переиспользуются, то может потребоваться вести отдельный список свободных идентификаторов.

Еще одна забавная проблема, которая есть при косвенной идентификации. Допустим, мы хотим создать периодический таймер, который сам себя деактивирует. Как-то вот так:

timer_thread tt;
tt.start();
timer_id id = tt.schedule(
  // Пауза перед первым срабатыванием.
  std::chrono::milliseconds(1),
  // Период повтора.
  std::chrono::milliseconds(3),
  // Само действие для таймера.
  [&]() {
    if( /* какое-то условие */ )
      tt.cancel(id);
  } );
...
tt.join();

Как вы думаете, все ли здесь нормально? :)

Конечно же нет ;) В зависимости от условий, пауза в 1ms может быть настолько маленькой, что за это время не успеет произойти возврат из schedule, а таймер уже сработает и внутри его обработчика уже может быть вызван метод cancel(). Но будет ли в переменной id актуальное значение идентификатора таймера? Понятное дело, что это косяк конкретной реализации таймера, а не подхода на основе косвенной идентификации, но показатель того, что думать нужно :)

Вот в общих чертах получается какая-то такая картинка. Как говорится, "выбирай, но осторожно, но выбирай" :)

В итоге я выбрал вариант с прямой идентификацией. Но не в чистом виде, а с добавлением небольшого элемента косвенности. Если пользователю нужно иметь идентификатор таймера, то таймер должен быть создан самим пользователем. Делается это обращением к методу allocate(), внутри которого создается специфический для конкретного механизма обслуживания таймеров объект. А из метода allocate() возвращается умный указатель на этот объект. Все последующие манипуляции с таймером производятся посредством этого умного указателя:

using namespace timertt;
timer_list_thread_t tt;
tt.start();

timer_holder_t id = tt.allocate();
tt.activate(
  id,
  std::chrono::milliseconds(1),
  std::chrono::milliseconds(3),
  [&]() {
    if( /* проверка какого-то условия */ )
      tt.deactivate(id);
  } );
...
tt.join();

Такой подход мне показался разумным компромиссом между эффективностью, ресурсоемкостью, удобством, безопасностью и расширяемостью. timer_holder_t -- это умный интрузивный указатель. Объект, на который он ссылается, остается живым, пока на него есть ссылки. Неважно откуда эти ссылки -- из кода пользователя или из таймерной нити. Если таймерная нить вычеркнула таймер из своих структур, то заявка останется в памяти, т.к. на нее будут ссылаться timer_holder-ы из кода пользователя. Если же пользователь закроет все свои timer_holder-ы, а заявка еще будет в структурах данных таймерной нити, то опять ничего страшного -- объект останется живым, никаких повисших указателей.

Все это дело реализовано в небольшой header-only библиотечке timertt, состоящей всего из одного заголовочного файла. Создавалась эта библиотека для SObjectizer и ее исходники лежат в том же репозитории, но к SObjectizer она не привязана и может использоваться сама по себе.

На данный момент в timertt реализовано два механизма: timer_wheel (шаблон timer_wheel_thread_template_t) и timer_list (шаблон timer_list_thread_template_t). Сама библиотека в состоянии стабильной бета-версии, на днях опробовал ее в новой ветке SObjectizer-а, выбросив ACE-овские таймеры. За выходные хочу реализовать еще timer_set или timer_heap, после чего можно будет сделать и отдельный релиз этой библиотеке. Пока же желающие могут глянуть в репозиторий, правда код еще "не причесан" и нет примеров с документаций, только тесты.

При реализации таймеров испытал много острых и давно забытых ощущений. Особенно при ручной возне с двухсвязными списками и при попытках разобраться, откуда возникают всякие неожиданные эффекты при взаимодействии нескольких нитей :) Поэтому в завершение хочу сказать простую, но очень важную штуку:

Пожалуйста, не делайте собственных реализаций таймеров, если на это у вас нет ну очень веских и уникальных причин. Если вы уже используете в своих проектах Boost, ACE, libuv, libev/libevent или еще какую-то серьезную библиотеку, в которой есть свои таймеры, то используйте их. Спать будете гораздо спокойнее. Если же вы не хотите тащить в свой проект ничего из вышеперечисленного, поищите какую-нибудь легковесную, но готовую библиотеку. Например, timertt ;)

Я вполне серьезно, кроме шуток. За время реализации timertt еще больше проникся уважением к разработчикам ACE Framework. Мощную штуку они сделали, труда в нее было вложено немало. Жаль только, что она настолько монстрообразная и несколько устаревшая морально. Если бы не желание превратить ядро SObjectizer в маленькую библиотеку с минимумом внешних зависимостей, реализация собственных таймеров взамен ACE-овских была бы совершенно неоправданной.