Комментарии 6
>В случае с неблокирующими сокетами для эффективного вычисления значения таймаута, которое надо передать в функцию select() или ее аналоги, можно применить структуру данных, которая называется «двоичная куча». Другое ее название — «пирамида».
Типичная ошибка, которую наблюдаем в таких библиотеках как libev.
Нужно разделять два типа таймеров: первые будем называть таймаутами, вторые таймерами.
Таймауты — это такие таймеры, которые почти всегда будут удалены и добавлены заново, вероятность того что нам придётся его исполнить мала. Например отслеживаем когда пришёл последний пакет и если втечении 30секунд больше не прилетало пакетов, то принудительно дисконнектим.
Таймеры же наоборот, практически всегда будут исполняться и очень редко удаляться для передобавления.
Если у нас простое сетевое приложение и все клиенты должны обрубаться по таймауту в 30секунд, то мы можем воспользоваться обычной FIFO очередью, в которую будем добавлять таймауты, а чтобы определить сколько секунд осталось до последнего таймаут, то достаточно просто посмотреть на первый элемент в очереди, а потом передать это значение в select/etc.
В случае если у нас множество различных таймаутов, то можем воспользоваться алгоритмом Timing Wheel.
Ну а для таймеров отлично подойдёт Heap, rb-tree итд.
Типичная ошибка, которую наблюдаем в таких библиотеках как libev.
Нужно разделять два типа таймеров: первые будем называть таймаутами, вторые таймерами.
Таймауты — это такие таймеры, которые почти всегда будут удалены и добавлены заново, вероятность того что нам придётся его исполнить мала. Например отслеживаем когда пришёл последний пакет и если втечении 30секунд больше не прилетало пакетов, то принудительно дисконнектим.
Таймеры же наоборот, практически всегда будут исполняться и очень редко удаляться для передобавления.
Если у нас простое сетевое приложение и все клиенты должны обрубаться по таймауту в 30секунд, то мы можем воспользоваться обычной FIFO очередью, в которую будем добавлять таймауты, а чтобы определить сколько секунд осталось до последнего таймаут, то достаточно просто посмотреть на первый элемент в очереди, а потом передать это значение в select/etc.
В случае если у нас множество различных таймаутов, то можем воспользоваться алгоритмом Timing Wheel.
Ну а для таймеров отлично подойдёт Heap, rb-tree итд.
Быстро пробежался по видео, хорошее видео, про таймауты на списках там рассказывается :) Но всё же Timing Wheel для таймаутов лучше подходит.
Если кому-то вдруг понадобится реализация Timing Wheel, то можно без особых проблем вытащить из исходников Linux ядра, либо из исходников Erlang'а.
Если кому-то вдруг понадобится реализация Timing Wheel, то можно без особых проблем вытащить из исходников Linux ядра, либо из исходников Erlang'а.
И замечательное объяснение почему timer wheel, а не какая-то другая структура используется в линукс ядре: lwn.net/Articles/156329/
Спасибо за конструктивную критику. По поводу ссылки на LWN — действительно, в 2005 году использование Timer Wheel в качестве структуры данных было оправдано, поскольку эта структура естественным образом поддерживает «округление» времени срабатывания таймера до ближайшей jiffie, а таймеров высокого разрешения в то время не существовало.
Современные ядра linux имеют две системы обработки событий, связанных со временем. Одна, о которой уже было сказано, основана на Timer Wheel, а другая — на rb-tree. Действительно, если следовать Вашей терминологии, первая в основном используется для таймаутов (где округление времени срабатывания допустимо и иногда даже желательно), вторая — для таймеров.
Современные ядра linux имеют две системы обработки событий, связанных со временем. Одна, о которой уже было сказано, основана на Timer Wheel, а другая — на rb-tree. Действительно, если следовать Вашей терминологии, первая в основном используется для таймаутов (где округление времени срабатывания допустимо и иногда даже желательно), вторая — для таймеров.
Девятая лекция курса:
– Как решить проблему 10 000 соединений?
– Как решить проблему 10 000 соединений?
Заключительная лекция курса:
– О производительности сетевых программ
– О производительности сетевых программ
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как сделать программу нетерпеливой?