Краткий ответ

Тайм-аут выборов должен быть случайным для каждого узла, например выбранным из диапазона 300–600 мс. Это снижает вероятность, что несколько узлов одновременно станут кандидатами и разделят голоса между собой.

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

Исторический контекст

В распределённом кластере нельзя надёжно определить, отказал ли лидер или временно недоступна сеть. Поэтому узлы используют тайм-аут отсутствия управляющих сообщений и запускают новую попытку выбора.

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

Постановка проблемы

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

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

Подробное решение

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

on_start:
    role = FOLLOWER
    reset_timer(random(300ms, 600ms))

on_timeout:
    role = CANDIDATE
    term = term + 1
    vote_for = self
    request_votes(term)

on_valid_heartbeat(term):
    role = FOLLOWER
    reset_timer(random(300ms, 600ms))

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

Диапазон тайм-аутов должен быть заметно больше типичной задержки heartbeat и обработки сообщения, иначе исправный лидер будет ошибочно считаться отказавшим. Одновременно он не должен быть чрезмерно большим, иначе восстановление после отказа станет медленным. На практике конкретные значения зависят от задержек и джиттера сети.

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

Ситуация из практики

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

Рассматривались три варианта. Фиксированный короткий тайм-аут давал быстрое обнаружение отказа, но часто вызывал разделение голосов. Большой фиксированный тайм-аут снижал вероятность конфликта, но увеличивал время восстановления. Случайный диапазон сохранил приемлемую скорость и уменьшил синхронный старт кандидатов.

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

Что кандидаты часто упускают

Достаточно ли одной случайности, чтобы гарантировать выбор лидера?

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

Можно ли сбрасывать таймер при любом входящем сообщении?

Нельзя. Запоздалое или относящееся к старой эпохе сообщение может искусственно удерживать узел в роли последователя. Таймер следует сбрасывать только после проверки актуальности сообщения и его права подтверждать живого лидера — например, после корректного heartbeat текущей или более новой эпохи.

Как выбирать диапазон случайных тайм-аутов?

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