[prog.c++] Про реализации таймеров

Задался целью реализовать работу с таймерами в виде автономной header-only библиотеки, базирующейся только на возможностях C++11 (благо, практически все необходимое в стандартной библиотеке есть). Как показал беглый поиск по Интернету, в чистом виде ничего подобного не наблюдается. Реализации таймеров есть в разных библиотеках/фреймворках, навскидку: ACE (кстати говоря, весьма продвинутые), Boost (в ASIO, как мне помнится), в libuv/libev/libevent. Но вот что-то минималистичное, без внешних зависимостей... На глаза что-то не попалось. Если же кто-то знает что-то подобное, буду признателен за ссылку.

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

Проснуться нить может и в другом случае. А именно, когда кто-то добавил новую заявку в контейнер и эта новая заявка оказалась минимальной. Например, ранее самая первая заявка должна была сработать в 19:20:15, а новая заявка -- в 19:20:05. В этом случае нить пересчитывает время, которое ей нужно проспать и засыпает снова.

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

Гораздо интереснее два вопроса, связанных с работой такой таймерной нити:

1. Что из себя представляет контейнер, в котором хранятся заявки для таймерной нити? Этот вопрос более подробно будет рассматриваться ниже.
2. Могут ли заявки отменяться? Если могут, то как они должны идентифицироваться и какие проблемы связанны с идентификацией заявок? Эти вопросы в данной заметке будут затронуты лишь вскользь, а подробнее на эту тему я собираюсь поговорить отдельно.

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

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

List

Самая простая структура. Все заявки помещаются в отсортированный по возрастанию времени срабатывания список. В голове списка оказывается минимальная заявка.

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

Очевидно, что такая структура будет неэффективной, если генерируется много заявок с произвольными временами срабатывания (например, сначала куча заявок с задержкой в 500ms, затем куча с задержкой в 125ms, затем куча с 600ms, затем куча с 65ms и т.д.).

Зато у такого способа хранения все хорошо в случае, если приложение ставит заявки с одинаковой задержкой. Например, в 200ms. Скажем, приложение получает запрос, отсылает его далее и ставит задержку в 200ms на ожидание ответа. Если ответа за 200ms не пришло, то запрос объявляется неудачным и его инициатору отсылается отрицательный ответ.

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

Wheel (называемый еще Timer Wheel)

Этот способ хорош, если есть возможность задать дискретность (гранулярность) для таймера. Например, таймер работает с точностью до 5 миллисекунд. Т.е., если на таймер ставятся заявки с паузами в 20, 21 и 23 миллисекунды, то они будут обработаны на одном такте работы таймерной нити. А вот поставленная одновременно с ними заявка с паузой в 25ms попадет уже на следующий такт таймера.

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

На старте для Wheel задается два параметра: размер фиксированного массива (т.е. размер циклического буфера) и дискретность таймера.

При постановке заявки ее пауза пересчитывается в количество тактов таймера. Например, если дискретность 5ms, а пауза 600ms, то время обслуживания заявки наступит через 120 тактов.

Далее количество тактов преобразуется в индекс в фиксированном массиве. Допустим, что размер массива -- 100 элементов, берем остаток от деления 120 на 100 и получаем индекс 20. Именно по этому индексу будет располагаться тот односвязный список, в котором будет сохранена заявка.

Однако, нужно вычислить еще одно значение: количество полных оборотов "колеса" прежде чем наступит время обработки заявки (т.е. количество проходов по всем индексам массива). Для этого 120 делим на 100, получаем 1. Это значение сохраняется вместе с описанием заявки в односвязном списке.

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

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

Просто для информации: как я понял, самыми широкоизвестными работами на тему Timer Wheel (с различными модификациями) являются статьи George Varghese. Например, одна из них от 1997-го года: "Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility".

Heap

Это, на мой взгляд, самый универсальный способ. Сочетающий в себе эффективность обработки большого количества заявок, но при этом не требующий дискретной работы таймерной нити.

Заявки при этом способе хранятся в какой-то структуре данных, аналогичной heap-у. Т.е. первым элементом там будет минимальная заявка. При ее удалении первой снова окажется минимальная заявка и т.д. Принцип работы при этом будет такой же, как и в случае с List-структурой.

Главный вопрос при работе с таймером на основе heap-а будет заключаться в том, допускается ли отмена заявок до времени их срабатывания. Если допускается, то вопрос упрется в то, как именно будет организован heap -- будет ли это реализовано вручную на основе массива, либо же за основу будет взята какая-то древовидная структура. Например, в C++ можно взять std::set/std::map и не париться. Если же по каким-то причинам накладные расходы на std::set/std::map кажутся чрезмерными, то тогда не остается ничего другого, как делать свою реализацию на массивах. И вопрос будет в том, насколько простой и эффективной эта реализация окажется (а так же сколько шишек доведется себе набить при отладке и сопровождении).

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

Если же оставаться более-менее на поверхности, то с различными структурами данных тесно связан еще один аспект: а именно возможность автоматического повторения таймерной заявки. На практике часто встречается ситуация, когда таймер должен срабатывать с темпом, скажем, в 1 секунду. Или же первый раз должен сработать через 500ms, а затем должен повторяться каждые 100ms. В этом случае таймерная нить должна понять, что заявка повторяющаяся и, когда она обслужена, она снова должна быть поставлена в очередь. И здесь тип структуры данных так же будет оказывать большое влияние на эффективность и масштабируемость таймера.

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

Самое же веселое, что связано с идентификаторами заявок, это возможность проверки их корректности.

Т.е. пользователь ставит заявку с задержкой в 600ms, получает некий ID, сохраняет этот ID у себя. А спустя 20 секунд спохватывается и дает команду на отмену заявки с этим ID. Такой заявки уже давно нет. И таймерная нить должна это понять. С пониманием же связано два нюанса:

• если ID является числом, то при некоторых подходах к организации системы идентификаторов вполне может получиться, что такой же ID выдан новой заявке. Например, описания заявок хранятся в массиве, а идентификатором заявки является индекс в этом массиве. Заявка, будучи обслуженной, из массива удаляется, а на ее место помещается новая заявка. Т.о. индекс переиспользуется и новая заявка получает старый ID. В этом случае если пользователь через 20 секунд после срабатывания заявки спохватился и ринулся удалять заявку по имеющемуся у него ID, то он запросто может удалить совсем другую заявку;
• если в качестве идентификатора возвращается указать на какой-то динамически созданный объект, то важно обеспечить, с одной стороны, валидность этого указателя до тех пор, пока пользователь хранит его у себя. С другой стороны, нужно избежать утечек ресурсов из-за того, что пользователь сохранил у себя кучу идентификаторов и забыл про них (этот фактор нужно учитывать не только в C++, но и в языках со сборкой мусора).

Еще один интересный аспект проблемы. Допустим, пользователь хочет видеть один библиотечный класс TimerThread с фиксированным набором методов (start/stop, schedule/erase). Но чтобы этому классу можно было указать, какой механизм должен использоваться внутри (либо List, либо Wheel, либо Heap). При этом снаружи для пользователя чтобы ничего не менялось.

Что при этом получается с идентификаторами заявок? Эти идентификаторы должны быть унифицированными. А вот как это сделать? Использовать какой-то скалярный тип, скажем, uint64?

Или же определять какой-то интерфейс TimerDemandID, а от него уже затем наследовать конкретные типы вроде TimerListDemandID, TimerWheelDemandID, TimerHeapDemandID? Но в случае с таким интерфейсом какие накладные расходы будут у пользователя? В случае C++ это не так уж очевидно: придется ассоциировать TimerDemandID с каким-то умным указателем (в идеале интрузивным, дабы избежать дополнительного выделения памяти), а затем платить за атомарные операции инкремента/декремента ссылок на объект TimerDemandID...

Вот о таких проблемах я надеюсь более подробно поговорить в следующий раз.

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