Несколько реализаций таймеров

1. Введение

Прежде чем мы перейдем к делу, давайте немного поболтаем. Некоторые люди говорят, что в предмете информатики исследование программного обеспечения — это математика, а исследование аппаратного обеспечения — физика.Самая легкая — это средняя группа пользователей, которые мало знают о физике и математике, но все же могут использовать компьютеры как их собственные средства к существованию. Это правило универсально применимо. Взгляните на пример «таймера».Для исследований на прикладном уровне есть такие фреймворки, как Quartz и Spring Schedule, для распределенных исследований — распределенное планирование задач, например SchedulerX и ElasticJob. различные принципы реализации таймера, эффективность работы и структуры данных, которые можно изучить более подробно... Простое начало работы и использование фреймворка не отражает ваш личный уровень Как выделиться среди других? Я думаю, по крайней мере, что-то должно быть сделано в одном направлении:

1. Углубленное изучение принципа реализации существующего фреймворка, например: чтение исходного кода
2. Традиционная технология хорошо распространяется в полевых условиях, многие из традиционных технологий могут хорошо развиваться в автономной работе, но распределенный сценарий требует большого дополнительного рассмотрения.
3. С точки зрения дизайнера, если вы проектируете колесо с нуля, как использовать соответствующие алгоритмы и структуры данных для его реализации.

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

2 Понимание таймеров

Таймеры используются во многих сценариях, таких как

1. При использовании длинного TCP-соединения клиенту необходимо периодически отправлять на сервер запрос пульса.
2. Финансовая система регулярно генерирует отчеты в конце каждого месяца.
3. В 0:00 на Double 11 переключатель спайков будет включен регулярно.

Как вода и воздух, таймеры вездесущи в различных сценариях.Общая форма задач на время: срабатывает через фиксированное время, периодически срабатывает с фиксированной частотой и срабатывает в определенное время. Что такое таймер? Его можно понимать как такую ​​структуру данных:

Храните серию наборов задач, а задачи с более близкими сроками имеют более высокий приоритет выполнения. С точки зрения пользователя поддерживаются следующие операции: NewTask: добавить новую задачу в коллекцию задач Отмена: отменить задачу С точки зрения планирования задач он также поддерживает: Выполнить: выполнение запланированной задачи с истекшим сроком действия.

Для определения сроков выполнения задачи в основном используется метод опроса.каждый второй отрезок времениПроверятьнедавние задачиНезависимо от того, должно ли это произойти, и после того, как произойдет поведение NewTask и Cancel, политика планирования задач также будет скорректирована.

В конце концов, таймер все еще реализован путем опроса потока.

3 структуры данных

В основном мы измеряем три показателя NewTask (новая задача), Cancel (отмена задачи) и Run (выполнение запланированной задачи в срок) и анализируем их временную/пространственную сложность с использованием различных структур данных.

3.1 Дважды упорядоченный связанный список

В Яве,LinkedListэто естественный вдвойне связанный список

Новая задача: O(N) Отмена: O(1) Пробег: О(1) N: количество задач

Newtask o (n) легко понять, просто найдите подходящее место в соответствии с Expiretime; отменять O (1), когда задача находится в отменах, она будет иметь ссылку на свой собственный узел, поэтому нет необходимости найти его Расположение в связанном списке, то есть удаление текущего узла может быть достигнута, поэтому мы используем вдвойне связанный список вместо нормального связанного списка; запустить o (1), поскольку весь вдвойне связанный список заказывается на основе Expiretime, планировщик должен только опросить первую задачу, которая она.

3.2 Кучи

В Яве,PriorityQueueпредставляет собой естественную кучу, которая может использовать входящиеComparatorдля определения приоритета элементов.

Новая задача: O (logN) Отменить: O (logN) Пробег: О(1) N: количество задач

ExpiRetime этоComparatorпараметры сравнения. NewTask O(logN) и Cancel O(logN) соответствуют временной сложности вставки и удаления элементов из кучи соответственно; Run O(1), небольшая корневая куча, образованная expireTime, мы всегда можем найти самую быстро истекающую вершина кучи Задача.

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

3.3 Колесо времени

Netty оптимизирована для сценария планирования времени ожидания ввода-вывода и реализуетHashedWheelTimerалгоритм времени колеса.

HashedWheelTimerЯвляется кольцевой структурой, по аналогии с часами, есть много циферблатов ведра, в каждом ведре может храниться множество задач, срок действия всех задач, использующих один из списка, истекает, а указатель на ячейку со временем сетка вращения и выполнять все задачи, связанные с соответствующим ведром. Задания取模Решите, в какое ведро нужно положить. Подобно принципу HashMap, newTask соответствует put и использует List для разрешения конфликтов Hash.

В качестве примера на приведенном выше рисунке, если предположить, что ведро составляет 1 секунду, период времени, представленный одним оборотом указателя, составляет 8 с. Предполагая, что текущий указатель указывает на 0, необходимо запланировать задачу, которая должна быть выполнена через 3 с. Очевидно, его следует добавить к (0+3=3), указатель может быть выполнен после обхода 3 раза; если задача должна выполняться через 10 с, она должна дождаться, пока указатель завершит обход нуля 2, прежде чем выполнять его, поэтому его следует поставить в 2 и округлить (1) Сохранить в задачу. При проверке выполнения задач выполняется только раунд 0, а раунд других задач в корзине уменьшается на 1.

Глядя на ведро5 на рисунке, мы можем знать, что вПосле этого необходимо выполнить две задачи, вЕсть задача, которую нужно выполнить позже.

Новая задача: O(1) Отмена: O(1) Бег: О(М) Отметить: О(1) M: ведро, M ~ N/C, где C — количество ведер в одном раунде, по умолчанию 512 в Netty.

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

Традиционные таймеры ориентированы на задачи, а таймеры колеса времени ориентированы на сегменты.

Построить НеттиHashedWheelTimerЕсть два важных параметра:tickDurationиticksPerWheel.

1. tickDuration: То есть время, представленное ведром, по умолчанию равно 100 мс, Netty считает, что этот параметр не нужно изменять в большинстве сценариев;
2. ticksPerWheel: Вероятность задачи, назначенной на ту же задачу, если можно увеличить ведро этого параметра, уменьшение количества ведра содержит, по умолчанию 512.

3.4 Иерархическое колесо времени

Kafka оптимизирована для алгоритма колеса времени и реализует иерархическое колесо времени.TimingWheel

Если временной интервал задачи велик, а число большое, традиционнаяHashedWheelTimerвызовет задачуroundОчень большой, список задач одного ведра очень длинный и будет поддерживаться в течение длительного времени. В настоящее время колесо рулетки можно классифицировать по степени детализации по времени:

Теперь каждая задача сохраняется в дополнение к текущей рулеткеround, Также рассчитывается во всех нижних рулеткахround.当本层的roundКогда он равен 0, задача переходит на следующий уровень.roundЗначения проталкиваются на нижнее колесо и, наконец, выполняются на нижнем колесе.

Новая задача: O(H) Отмена: O(H) Бег: О(М) Отметить: О(1) H: количество слоев

Представьте себе временную задачу, которая запланирована на 3 дня, 10 часов, 50 минут и 30 секунд.В однослойном колесе времени с tickDuration = 1s она должна пройти:Движение вторичного указателя может быть выполнено. Но в четырехслойном колесе времени с wheel1 tickDuration = 1 день, wheel2 tickDuration = 1 час, wheel3 tickDuration = 1 минута и wheel4 tickDuration = 1 секунда, вам нужно только пройтиДвижение вторичного указателя!

По сравнению с одноуровневым колесом времени иерархическое колесо времени имеет очевидные преимущества, когда промежуток времени велик.

4 Общие реализации

4.1 Timer

в JDKTimerЭто очень ранняя реализация, и сейчас она не выглядит хорошим дизайном.

// 运行一个一秒后执行的定时任务
Timer timer = new Timer();
timer.schedule(new TimerTask() {
    @Override
    public void run() {
        // do sth
    }
}, 1000);

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

public class Timer {
    private final TaskQueue queue = new TaskQueue();
    private final TimerThread thread = new TimerThread(queue);
}

Где TaskQueue — это простая куча, реализованная с использованием массивов. Еще одним примечательным свойством являетсяTimerThread,TimerИспользуйте один поток, отвечающий за опрос и выполнение задач.TimerПреимущество в том, что его легко использовать, но поскольку все задачи планируются одним и тем же потоком, весь процесс выполняется последовательно, одновременно может выполняться только одна задача, а задержка или исключение предыдущей задачи будет влияют на последующие задачи.

Если во время опроса обнаружено значение currentTime

1. TimerМожет быть запланировано только одним потоком
2. TimerTaskисключения вTimerИсполнение.

Из-за этих двух дефектов JDK 1.5 поддерживает новую программу таймера.ScheduledExecutorService.

4.2 ScheduledExecutorService

// 运行一个一秒后执行的定时任务
ScheduledExecutorService service = Executors.newScheduledThreadPool(10);
service.scheduleA(new Runnable() {
    @Override
    public void run() {
        //do sth
    }
}, 1, TimeUnit.SECONDS);

по сравнению сTimer,ScheduledExecutorServiceРешена проблема блокировки проблем, связанных с тем, что один и тот же таймер планирует несколько задач, а исключение задачи не прерывается.ScheduledExecutorService.

ScheduledExecutorServiceПредоставляет два часто используемых метода периодического планирования ScheduleAtFixedRate и ScheduleWithFixedDelay.

SCHENETETFIXEDRATE Каждое время выполнения заключается в миссии, чтобы задержать начало интервала времени, что каждое время выполнения:, , , ...

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

Можно видеть, что ScheduleAtFixedRate основан на фиксированном интервале времени для планирования задач, ScheduleWithFixedDelay зависит от продолжительности времени выполнения каждой задачи и основан на планировании задач с нерегулярными временными интервалами.

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

4.3 HashedWheelTimer

Timer timer = new HashedWheelTimer();
//等价于 Timer timer = new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 512);
timer.newTimeout(new TimerTask() {
    @Override
    public void run(Timeout timeout) throws Exception {
        //do sth
    }
}, 1, TimeUnit.SECONDS);

Он был представлен ранее в NettyHashedWheelTimerДля внутренней структуры данных конструктор по умолчанию настроит период опроса на 100 мс и количество сегментов на 512. Его использование и JDKTimerпохожи.

private final Worker worker = new Worker();// Runnable
private final Thread workerThread;// Thread

Из-за нехватки места я не буду делать подробный анализ исходного кода, но две приведенные выше строки взяты изHashedWheelTimerКод иллюстрирует тот факт:HashedWheelTimerВнутри один поток также используется для планирования задач. с JDKTimerТочно так же существует проблема «слишком большое время выполнения предыдущей задачи, что влияет на выполнение последующих запланированных задач».

Понимание ticksPerWheel и tickDuration в HashedWheelTimer и их разумная настройка могут позволить пользователям получить наилучшую производительность в соответствующих сценариях.

5 лучших практик

5.1 Выберите подходящий таймер

Излишне говорить, что JDKTimerИспользуемая сцена является самой узкой и может быть полностью заменена двумя последними. какScheduledExecutorServiceиHashedWheelTimerКак выбрать между ними, нужно выделить сцену и провести простое сравнение:

1. ScheduledExecutorServiceОн ориентирован на задачи.Когда количество задач очень велико, использование кучи (PriorityQueue) для поддержки добавления и удаления задач приведет к снижению производительности.HashedWheelTimerДля бакетов ставьте разумные ticksPerWheel, tickDuration, которые нельзя ограничивать количеством задач. Так что, когда задач много,HashedWheelTimerможет показать свои преимущества.
2. И наоборот, если громкость задачи невелик,HashedWheelTimerРабочий внутренний поток все равно не остановит тумблер указателя, хоть и не особо потребляет производительность, но по крайней мере сказать не могу:HashedWheelTimerКонечноScheduledExecutorServiceотлично.
3. HashedWheelTimerПоскольку массив бакетов открыт, занимаемая память будет немного больше.

Вышеприведенное сравнение позволяет нам получить лучший опыт: когда задач много, используйтеHashedWheelTimerЭто может улучшить производительность. Например, задача перехода на карту в структуре управления службами, экземпляр службы очень много, каждый клиент должен отправлять пульс, каждый сервер должен определять состояние соединения, что является очень подходящим использованием.HashedWheelTimerместо действия.

5.2 Одиночная резьба и бизнес-пул

Нам нужно обратить вниманиеHashedWheelTimerИспользуйте один поток для планирования задач. Если задача требует много времени, вам следует настроить пул бизнес-потоков дляHashedWheelTimerВ качестве триггера синхронизации фактическое выполнение задачи передается пулу бизнес-потоков.

Если все задачи удовлетворяют: taskNSStartTime - taskN-1StartTime > taskN-1CostTime, то есть интервал между любыми двумя задачами меньше времени выполнения задачи, выполненной первой, то об этой проблеме можно не беспокоиться.

5.3 Глобальный таймер

фактическое использованиеHashedWheelTimerчас,Его следует рассматривать как глобальный планировщик задач, например, разработанный как статический.. Всегда помните:HashedWheelTimerСоответствует потоку, если экземпляр создается каждый разHashedWheelTimer, Первый поток много, а затем алгоритм временного раунда будет совершенно бессмысленным.

5.4 Установите разумные параметры для HashedWheelTimer

Особенно важны два параметра ticksPerWheel и tickDuration. ticksPerWheel управляет количеством сегментов в колесе времени и определяет вероятность конфликта.ickDuration определяет частоту переключения указателя, которая будет влиять на точность синхронизации, с одной стороны, и определяет С другой стороны, потребление ЦП. Когда количество задач очень велико, рассмотрите возможность увеличения ticksPerWheel; когда точность времени невысока, вы можете соответствующим образом увеличить tickDuration, но в большинстве случаев вам не нужно заботиться об этом параметре.

5.5 Когда использовать иерархическое колесо времени

Когда промежуток времени велик, увеличение tickDuration однослойного колеса времени может уменьшить количество простоев, но это приведет к снижению точности времени.Иерархическое колесо времени может избежать снижения точности и количества раз указатель бездействует. Если есть временная задача с большим промежутком времени, она может быть передана в иерархический цикл времени для планирования. Кроме того, вы можете создать несколько однослойных колес времени с различными функциями в зависимости от точности синхронизации, dayHashedWheelTimer, hourHashedWheelTimer, minHashedWheelTimer и настроить различные значения tickDurations.Хотя этот метод невелик, он все же является решением. Разработано НеттиHashedWheelTimerОн специально используется для оптимизации планирования ввода-вывода, а сцена относительно ограничена, поэтому иерархическое колесо времени не реализовано; в то время как в Kafka область применения таймера шире, поэтому он реализует иерархическое колесо времени для решения задач. с более сложными сценами.

6 ссылок

[1] Woohoo. IBM.com/developer Я…

[2] novoland.github.io/concurrency/2014/07/…

[3] Ууху. В это время. Колумбия. Quota/~Nahum/I 699…

Добро пожаловать на мой общедоступный номер WeChat: «Технический обмен Кирито», на любые вопросы по статье будет получен ответ, и вы получите больше технического обмена, связанного с Java.