Выборы лидера в Raft: таймауты, правила голосования и четыре свойства безопасности

Election timeout и heartbeat-ы

Лидер утверждает свою власть, отправляя heartbeat-ы AppendEntries каждому follower-у с фиксированным интервалом — обычно 50 мс. У каждого follower-а есть election timeout, сбрасываемый каждым валидным heartbeat-ом. Если таймаут срабатывает (heartbeat не получен), follower считает лидера мёртвым и запускает выборы.

Таймаут рандомизирован — обычно в диапазоне 150–300 мс. Без рандомизации все follower-ы таймаутили бы одновременно, каждый голосовал за себя, и голос бы раздробился. При достаточно широком диапазоне с высокой вероятностью один follower срабатывает первым, отправляет RequestVote всем остальным и собирает большинство до того, как кто-то другой таймаутит. Ничьи всё ещё возможны, но редки; любая ничья просто начинает новый term, и новый случайный таймаут быстро её разрешает.

Правило голосования RequestVote

Нода отдаёт голос в RequestVote только если:

1. Она ещё не голосовала в этом term (один голос на term на ноду).
2. Лог candidate-а как минимум так же актуален, как собственный лог voter-а.

“Как минимум так же актуален” сравнивается по: больший lastLogTerm побеждает; при равных term-ах побеждает больший lastLogIndex. Это правило — ключ к безопасности.

Почему правило completeness лога важно

Без проверки up-to-date candidate со stale-логом мог бы выиграть выборы и стать лидером, не имея закоммиченных entry. Эти entry были бы перезаписаны, нарушая гарантию, что закоммиченное entry сохраняется навсегда.

Аргумент пересечения кворумов объясняет, почему правило работает: каждое закоммиченное entry было подтверждено большинством. Любой election-кворум пересекается с этим commit-кворумом хотя бы в одной ноде. Через эту общую ноду candidate должен иметь закоммиченное entry (иначе voter откажет). Вместе пересечение кворумов и правило completeness лога дают Leader Completeness: каждый лидер term T+1 имеет все entry, закоммиченные в term-ах 1–T.

Четыре свойства безопасности

Доказательство корректности Raft сводится к четырём инвариантам:

1. Election Safety — максимум один лидер на term. Следует из “один голос на ноду на term + требуется большинство”.
2. Leader Append-Only — лидер никогда не перезаписывает и не удаляет свои log entry; только дописывает.
3. Log Matching — если два лога имеют общий entry на index i с term t, они идентичны для всех index до i включительно. Следует из проверки целостности AppendEntries.
4. Leader Completeness — любое entry, закоммиченное в каком-то term, есть в логе каждого лидера более высоких term-ов. Следует из пересечения кворумов + правила голосования.

Эти четыре инварианта работают цепочкой: Safety предотвращает двух лидеров (1), Append-Only сохраняет лог лидера нетронутым (2), Log Matching заставляет follower-ы к нему сходиться (3), а Completeness гарантирует: новый лидер не стартует с пробелом (4). Без любого звена цепь рвётся — именно поэтому etcd трактует каждый инвариант как обязательное требование протокола.

State Machine Safety (выводится): никакие две ноды никогда не применяют разные команды на одном index.