1 Запланированные задачи

У Netty, Quartz, Kafka и Linux есть запланированные задачи.

• Обычные инструменты JDK, такие как java.util.Timer и DelayedQueue, могут выполнять простые задачи синхронизации.кучаСтруктура данных и сложность доступа составляют O(nlog(n)), что не может поддерживать массивные задачи синхронизации.
• В сценарии с большим количеством запланированных задач и высокими требованиями к производительности, чтобы уменьшить временную сложность операций доступа и отмены задач до O(1), используйтеколесо времениплан.

2 Модель колеса времени и ее применение

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

• Схема структуры хешированного колеса времени

Применимая сцена

• Восстановление
• управление потоком
• Алгоритм планирования
• Управление жизненным циклом пакетов в сети

Таймеры дороги в обслуживании, если

• Процессор прерывается на каждом такте
• Используйте мелкозернистые таймеры
• Много незавершенных таймеров

Эффективные алгоритмы таймера необходимы для снижения общих накладных расходов на прерывания.

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

Модели и показатели производительности

правила в модели

• Звонок клиента:
  • START_TIMER(интервал времени, Request_ID, Expiry_Action)
  • STOP_TIMER (идентификатор_запроса)
• Вызов таймера:
  • PER_TICK_BOOKKEEPING
  • EXPIRY_PROCESSING

Представление

• пространство

память, используемая структурами данных

• Задерживать

Время, необходимое для запуска и завершения любой из вышеперечисленных процедур

3 Структура колеса времени Даббо

Реализация колеса времени Dubbo находится в пакете org.apache.dubbo.common.timer модуля dubbo-common Давайте проанализируем основные интерфейсы и реализации, задействованные в колесе времени.

основной интерфейс

TimerTask

В Dubbo должны быть реализованы все временные задачиИнтерфейс TimerTask. Определен только один метод run(), а входным параметром является объект интерфейса Timeout.

Timeout

Объект Timeout соответствует объекту TimerTask один к одному, аналогично взаимосвязи между объектом Future, возвращаемым пулом потоков, и объектом задачи, отправленным в пул потоков. С помощью объекта «Тайм-аут» вы можете не только просматривать состояние запланированной задачи, но и управлять этой задачей (например, отменять связанную с ней задачу).

• Методы в интерфейсе Timeout:

Интерфейс Timer определяет основное поведение таймера.newTimeout(): отправить задачу таймера (TimerTask) и вернуть связанный объект Timeout, аналогично отправке задачи в пул потоков.

HashedWheelTimeout

HashedWheelTimeout — единственная реализация интерфейса Timeout и внутренний класс HashedWheelTimer. HashedWheelTimeout играет две роли:

• Узел двусвязного списка в колесе времени, то есть контейнер задачи таймера TimerTask в HashedWheelTimer
• Дескриптор (Handle), возвращаемый после того, как задача таймера TimerTask отправляется в HashedWheelTimer, который используется для просмотра и управления запланированной задачей за пределами колеса времени.

основное поле

• предыдущий, следующий. Он используется для связывания тайм-аутов (временных задач) в HashedWheelTimerBucket через двусвязный список.Поскольку он действует только на WorkerThread, нет необходимости в синхронизации/изменчивости.

• задача, фактическая запланированная задача

• Крайний срок, время выполнения запланированной задачи. Указать при создании HashedWheelTimeout

Формула расчета:currentTime（创建 HashedWheelTimeout 的时间） + delay（任务延迟时间） - startTime（HashedWheelTimer 的启动时间）, нс

• состояние, текущее состояние запланированной задачи

- Необязательные состояния:- Существует также поле STATE_UPDATER для атомарных изменений состояния.

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

Основной API

• isCancelled()

• isExpired()

• state()

Проверьте текущий статус HashedWheelTimeout

• метод отмены()

• метод с истекшим сроком действия ()

• remove()

HashedWheelBucket

Щель в колесе времени. Слот в колесе времени на самом деле является контейнером для кэширования и управления двусвязным списком, а каждый узел в двусвязном списке являетсяHashedWheelTimeoutобъект, который связан сTimerTaskДела по расписанию.

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

Основной API

• addTimeout()

• pollTimeout()

• remove()

Удаляет указанный узел HashedWheelTimeout из двусвязного списка.

• clearTimeouts()

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

• expireTimeouts()

Пройдите все узлы HashedWheelTimeout в двусвязном списке. При обработке запланированной задачи с истекшим сроком действия она будет удалена с помощью метода remove(), и для ее выполнения будет вызван ее метод expire(); для отмененной задачи она будет удалена сразу после удаления с помощью метода remove( ) метод; для задачи с неистекшим сроком действия это будет Уменьшение поля restRounds (количество оставшихся тактов) на единицу.

HashedWheelTimer

TimerРеализация интерфейса реализует таймер через алгоритм колеса времени.

функция

В соответствии с текущим указателем колеса времени выберите соответствующийHashedWheelBucketСлоты, итерация от головы списка, вычисление каждогоHashedWheelTimeoutДела по расписанию:

• Если он принадлежит текущему тактовому циклу, выньте его и запустите
• Если он не принадлежит, уменьшите оставшееся количество тактов на один

основной домен

• workerState

Текущее состояние колеса времени, три необязательных значения, устанавливаемыхAtomicIntegerFieldUpdaterРеализовать его атомарную модификацию.

• startTime

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

• wheel

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

• таймауты, отмененные таймауты

HashedWheelTimer будет обрабатывать данные этих двух очередей перед обработкой двусвязного списка HashedWheelBucket: - очередь таймаутов Буферизация задач по времени во внешних раундах отправки - очередь отмененных таймаутов Временно хранить отмененные запланированные задачи

• tick

родыHashedWheelTimer$Worker, указатель колеса времени, монотонно возрастающий счетчик с шагом 1

• mask

маска,mask = wheel.length - 1,воплощать в жизньticks & maskможет найти соответствующий слот часов

• ticksDuration

Фактическое время, представленное каждым приращением стрелки времени на 1, в наносекундах.

• pendingTimeouts

Общее количество запланированных задач, оставшихся в текущем временном раунде.

• workerThread

Поток, который фактически выполняет задачу синхронизации внутри колеса времени.

• worker

Логика, которая фактически выполняет задачу синхронизации, инкапсулирована в этом объекте Runnable.

newTimeout()

Чтобы отправить отложенную задачу, будет вызван метод start(), чтобы запустить колесо времени до того, как отложенная задача попадет в очередь тайм-аутов, которая выполнит следующие два ключевых шага:

1. Определяет поле startTime колеса времени
2. Запустите поток workerThread и начните выполнение рабочих задач.

Затем рассчитайте крайний срок временной задачи в соответствии с startTime и, наконец, инкапсулируйте временную задачу вHashedWheelTimeoutи добавить кtimeoutsочередь.

4 Поток выполнения одного оборота стрелки колеса времени

HashedWheelTimer$Worker.run() :

1. Стрелки колеса времени поворачиваются, и цикл колеса времени начинается.
2. Очистите запланированные задачи, которые пользователь добровольно отменяет. Когда пользователь отменяет эти запланированные задачи, они записываются вcancelledTimeoutsв очереди. Колесо времени очищает очередь каждый раз, когда указатель поворачивается
3. Перенесите задачу синхронизации, кэшированную в очереди тайм-аутов, в соответствующий слот колеса времени.
4. Найдите соответствующий слот в соответствии с текущим указателем и обработайте задачи синхронизации в двусвязном списке слота.
5. Проверьте состояние колеса времени. Если колесо времени находится в рабочем состоянии, вышеуказанные шаги выполняются циклически для непрерывного выполнения запланированной задачи. Если колесо времени находится в остановленном состоянии, выполните следующие шаги, чтобы получить невыполненную временную задачу и присоединиться к ней.unprocessedTimeoutsОчередь: пройдите каждый слот в колесе времени и позвонитеclearTimeouts() метод; циклически вызывает poll() для слотов, которые не добавлены в очередь тайм-аутов
6. Наконец, снова очистите запланированные задачи, отмененные пользователем, в очереди cancelledTimeouts.

5 Запланированное приложение задачи

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

Применение колеса времени Dubbo в основном заключается в следующих аспектах:

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

Ссылаться на

• zhuanlan.zhihu.com/p/32906730