Модуль: Распределённые системы · Уровень: Senior+

TL;DR#

• Консенсус — задача договориться о едином значении/порядке между несколькими узлами так, чтобы решение пережило отказы части узлов. Лежит в основе replicated state machine (RSM): одинаковый детерминированный лог команд -> одинаковое состояние на всех репликах.
• FLP impossibility: в асинхронной сети (нет границ на задержки) невозможно гарантировать консенсус при наличии даже одного отказавшего узла, который нельзя отличить от медленного. Практика обходит это через частичную синхронность и таймауты (рандомизированные) — жертвуем гарантированной liveness, сохраняя safety.
• Raft — алгоритм консенсуса, спроектированный как understandable альтернатива Paxos. Декомпозиция на три подзадачи: leader election, log replication, safety.
• Роли: leader / follower / candidate. Время делится на terms (логические эпохи). В каждом term не более одного лидера; все записи идут только через лидера (leader-only writes).
• Запись коммитится, когда её реплицировало большинство (кворум N/2+1). Поэтому нужно нечётное число нод — кворум тот же, а fault tolerance не теряется при чётности.
• Применяется в etcd, Consul, CockroachDB (Raft per range), TiKV. ZooKeeper использует ZAB — близкий по духу leader-based atomic broadcast.

Теория#

Зачем нужен консенсус#

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

Формально алгоритм консенсуса должен обеспечивать:

• Agreement (соглашение): все корректные узлы решают одно и то же значение.
• Validity (целостность): решённое значение было кем-то предложено (не выдумано).
• Termination (завершимость, liveness): все корректные узлы в итоге принимают решение.
• Integrity: каждый узел решает не более одного раза.

Replicated State Machine (RSM)#

Главное применение консенсуса. Идея: если у нас есть детерминированная state machine и все реплики применяют один и тот же лог команд в одном и том же порядке, то все реплики придут в идентичное состояние.

            consensus-обеспеченный лог (total order)
   [c1][c2][c3][c4]...      <- одинаков на всех репликах
      |   |   |   |
      v   v   v   v
   apply в детерминированную FSM -> одинаковое состояние везде

Таким образом, задача «реплицировать БД/KV-хранилище» сводится к задаче «согласовать порядок команд в логе» — это и решает консенсус. Total order broadcast (atomic broadcast) и консенсус эквивалентны по силе.

FLP impossibility (Fischer–Lynch–Paterson, 1985)#

Теорема: в полностью асинхронной модели (нет верхней границы на задержку сообщений и скорость процессов), детерминированный алгоритм консенсуса не может гарантировать termination, если хотя бы один процесс может отказать (crash).

Интуиция: в асинхронной сети невозможно отличить упавший узел от очень медленного. Узел не отвечает — он умер или просто тормозит? Если ждать его ответа — рискуем зависнуть навсегда (он мёртв). Если не ждать и пойти дальше — рискуем нарушить agreement (он жив и решит иначе). Всегда существует сценарий, в котором система бесконечно «не может определиться».

Важно: FLP запрещает гарантированную liveness (termination), но не safety. Поэтому практические алгоритмы:

• Сохраняют safety всегда (никогда не примут противоречивые решения).
• Обеспечивают liveness при условии частичной синхронности — то есть «рано или поздно сеть начинает вести себя достаточно стабильно» (модель partial synchrony, Dwork–Lynch–Stockmeyer).
• Используют таймауты как практический способ заподозрить отказ, а рандомизацию таймаутов — чтобы разорвать симметрию (избежать вечного повторения неудачных раундов). Именно это делает Raft рандомизированными election timeouts.

Вывод для собеседования: Raft/Paxos не «нарушают» FLP — они гарантируют корректность всегда и прогресс только при достаточно стабильной сети.

Raft подробно#

Raft (Ongaro & Ousterhout, 2014) задумывался так, чтобы инженер мог реализовать его, действительно понимая. Декомпозиция:

Роли узлов#

• Follower — пассивен, отвечает на RPC лидера/кандидатов. Стартовое состояние.
• Candidate — узел, который инициировал выборы (после таймаута без сигналов от лидера).
• Leader — единственный обработчик клиентских записей; рассылает heartbeats и реплицирует лог.

Terms (термы)#

Время делится на terms — последовательные пронумерованные периоды. Term начинается с выборов. В каждом term — не более одного лидера (или ноль, если выборы провалились — split vote). Term — это логические часы Raft: каждый узел хранит currentTerm; каждое RPC несёт term. Правила:

• Если узел видит term больше своего — обновляет свой currentTerm и становится follower (старый лидер с устаревшим term немедленно «сдаётся»).
• RPC со старым term отвергаются. Это автоматически разруливает разделённого/«воскресшего» лидера.

Leader election (RequestVote RPC)#

• Каждый follower держит election timeout. Если за это время не пришёл ни heartbeat, ни AppendEntries от лидера — он считает, что лидера нет.
• Follower инкрементит currentTerm, переходит в candidate, голосует за себя и рассылает RequestVote всем.
• Узел отдаёт голос, если: term кандидата не меньше его собственного, он ещё не голосовал в этом term (votedFor), и лог кандидата не «отстаёт» (election restriction, см. safety).
• Кандидат, набравший большинство голосов (кворум), становится лидером и сразу начинает слать heartbeats, чтобы подавить новые выборы.

Split vote — несколько кандидатов стартовали одновременно, голоса разделились, никто не набрал большинство. Решение: randomized election timeouts (например, 150–300 мс случайно). Узлы таймаутят в разное время, обычно один успевает первым -> асимметрия разрывает цикл. Это прямой ответ на FLP-проблему симметрии.

RequestVote(term, candidateId, lastLogIndex, lastLogTerm)
  -> voteGranted, если:
       term >= currentTerm
       && (votedFor == null || votedFor == candidateId)
       && candidate's log is at least as up-to-date as receiver's

Log replication (AppendEntries RPC)#

• Клиент шлёт команду лидеру (followers перенаправляют). Лидер дописывает запись в свой лог (term + команда).
• Лидер рассылает AppendEntries с новыми записями всем followers (этот же RPC с пустым набором записей служит heartbeat).
• Когда запись реплицирована на большинство узлов, лидер двигает commitIndex и применяет команду к своей FSM, затем отвечает клиенту. Следующими AppendEntries он сообщает followers новый commitIndex, и они тоже применяют.

Лог (index: term:command):
  1:1:x=1   2:1:y=2   3:2:x=5   4:2:del z
                                   ^
                              commitIndex (реплицировано большинством)

AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit)

Consistency check: AppendEntries несёт prevLogIndex + prevLogTerm. Follower принимает записи, только если у него в prevLogIndex лежит запись с тем же prevLogTerm. Если нет — отвергает, и лидер откатывается назад (nextIndex–) и пересылает, пока логи не сойдутся. Так лидер принудительно приводит логи followers к своему (лог лидера — источник истины).

Кворум и majority#

• «Большинство» = floor(N/2) + 1. Для N=3 -> 2, для N=5 -> 3.
• Любые два большинства пересекаются хотя бы в одном узле. Это и есть фундамент safety: новый лидер обязательно получит голос от узла, который видел последнюю закоммиченную запись -> закоммиченные данные не теряются.

Safety properties#

Raft гарантирует пять свойств; ключевые для senior:

1. Election Safety: в одном term не более одного лидера (обеспечено правилом «один голос на term» + кворум).

2. Leader Append-Only: лидер никогда не перезаписывает/не удаляет записи в своём логе, только дописывает.

3. Log Matching Property: если две записи в логах разных узлов имеют одинаковый index и term, то (а) они содержат одну команду, и (б) все предыдущие записи тоже идентичны. Поддерживается consistency check’ом AppendEntries.

4. Leader Completeness: если запись закоммичена в term T, она присутствует в логах всех будущих лидеров (term > T). Обеспечивается election restriction.

5. State Machine Safety: если узел применил запись на index i, никакой другой узел не применит другую запись на том же index.

Election restriction (почему голосуют только за up-to-date лог)#

Чтобы новый лидер не потерял закоммиченные данные, узел отдаёт голос только кандидату, чей лог не менее «свежий», чем собственный. «Свежесть» сравнивается так: больше lastLogTerm свежее; при равном term — больше lastLogIndex свежее. Поскольку закоммиченная запись лежит на большинстве, а лидер набирает большинство голосов, среди голосующих обязательно есть узел с этой записью — и он не проголосует за кандидата без неё. Значит лидером может стать только узел, содержащий все закоммиченные записи. Это и есть гарантия Leader Completeness.

Тонкость (часто копают): лидер не коммитит записи из прошлых terms по одному только факту репликации большинством. Он коммитит запись прошлого term только косвенно — реплицировав запись своего текущего term поверх неё. Это закрывает классический сценарий, описанный в §5.4.2 статьи Raft, где иначе можно было бы «откоммитить и потерять» запись.

Heartbeats#

Лидер периодически шлёт пустые AppendEntries (heartbeat interval « election timeout). Они: (а) подавляют выборы у followers, сбрасывая их election timer; (б) распространяют commitIndex. Если followers перестают слышать лидера -> запускаются новые выборы.

Membership changes (joint consensus) — кратко#

Менять состав кластера (добавить/убрать узел) опасно: если перейти от старой конфигурации к новой «мгновенно», на короткий период могут образоваться два непересекающихся большинства (по старому и по новому составу) -> два лидера -> split-brain.

Raft решает это joint consensus (двухфазно): вводится промежуточная конфигурация C_old,new, где решение требует большинства и в старом, и в новом составе одновременно. Пока активна C_old,new, никакое одностороннее большинство невозможно. После её фиксации переходят к C_new. (Альтернатива в современных реализациях — single-server membership changes: добавлять/убирать по одному узлу за раз, что тоже исключает разрыв большинств.)

Paxos кратко#

Paxos (Lamport) — исторически первый доказанный алгоритм консенсуса для асинхронной сети с crash-отказами.

• Basic (single-decree) Paxos согласовывает одно значение. Роли: proposer, acceptor, learner. Две фазы:
  1. Prepare/Promise — proposer выбирает номер n, спрашивает большинство acceptor’ов «обещаете не принимать предложения < n?»; acceptor’ы обещают и сообщают уже принятое значение, если было.
  2. Accept/Accepted — proposer рассылает значение (своё или ранее принятое с наибольшим номером) для номера n; при согласии большинства значение выбрано.
• Multi-Paxos — чтобы согласовать последовательность значений (лог), запускать basic Paxos на каждый слот дорого. Multi-Paxos выбирает стабильного лидера (distinguished proposer), который пропускает фазу Prepare для последующих записей -> остаётся фактически одна фаза на запись. Это уже очень похоже на лидер-ориентированную репликацию Raft.

Почему создали Raft: статья Paxos печально известна сложностью для понимания и тем, что между «basic Paxos» и работающей реплицированной системой огромный разрыв — Multi-Paxos описан расплывчато, реализации расходятся. Raft с самого начала проектировался вокруг понятности (understandability): явный сильный лидер, цельный лог (не разрозненные слоты), явные terms, декомпозиция на election/replication/safety. По силе и гарантиям Raft и Multi-Paxos эквивалентны.

Где применяется#

Почему нечётное число нод и кворум N/2+1#

Fault tolerance: кластер из N узлов с кворумом большинства переживает отказ floor((N-1)/2) узлов (пока живо большинство, можно коммитить).

Видно: переход с 3 на 4 узла не повышает отказоустойчивость (всё ещё 1), но увеличивает размер кворума (нужно 3 вместо 2) -> больше латентность записи и выше шанс потерять кворум. То же с 5 vs 6. Поэтому берут нечётное число: максимум устойчивости при минимальном кворуме. Плюс нечётность исключает «ровный раскол 50/50» при сетевом разделении — большинство всегда определимо однозначно (нет ничьей).

ASCII диаграмма переходов состояний#

                       starts up / recovers
                              |
                              v
                       +-------------+
          discovers    |             |  times out (no heartbeat
          leader or    |  FOLLOWER   |  from leader within
          higher term  |             |  randomized election timeout)
        +------------->|             |-------------------+
        |              +-------------+                   |
        |                    ^                           |
        |    discovers       |                           v
        |    current leader  | discovers higher    +-------------+
        |    or higher term  | term / new leader   |             |
        |                    |                     | CANDIDATE   |
        |              +-------------+              |             |
        |              |             |  wins        +-------------+
        +--------------|   LEADER    |<--majority---| starts new  |
   higher term seen    |             |   of votes   | election,   |
   (step down to       +-------------+              | votes self, |
    follower)                ^                      | RequestVote |
                             |   times out          +-------------+
                             |   (election fails:        |
                             +---- split vote) ----------+
                                  retry election, new term

Краткая словесная версия:

• Follower -> Candidate: election timeout без сигналов лидера.
• Candidate -> Leader: набрал большинство голосов.
• Candidate -> Candidate: split vote / timeout -> новый term, повторные выборы.
• Candidate/Leader -> Follower: увидел больший term (или нового легитимного лидера).

Подводные камни / gotchas#

• Кворум != запись на всех. Коммит требует большинства; отстающие реплики догоняют асинхронно. Чтение с follower может вернуть устаревшие данные (нужен read-from-leader / ReadIndex / lease read для linearizable reads).
• Чётное число узлов — антипаттерн. Не повышает fault tolerance, повышает кворум и риск. Всегда нечётное (3/5/7).
• Запись прошлого term нельзя коммитить «по большинству». Лидер коммитит её только через репликацию записи текущего term поверх — иначе возможна потеря данных (§5.4.2). Классическая ошибка наивных реализаций.
• Split-brain при mgmt-change без joint consensus. Мгновенная смена конфигурации может породить два большинства -> два лидера. Только joint consensus / single-server change.
• Слишком короткий election timeout -> постоянные перевыборы, слишком длинный -> долгая недоступность после падения лидера. Heartbeat interval должен быть « election timeout (обычно в разы).
• Нерандомизированные таймауты -> вечный split vote. Рандомизация обязательна для liveness.
• FLP -> нет гарантии прогресса при флапающей сети. При нестабильной сети возможны бесконечные перевыборы; safety при этом сохраняется, но система может «не двигаться».
• Лог растёт бесконечно без снапшотов (log compaction). Реальные реализации (etcd) делают snapshot + InstallSnapshot RPC для отставших узлов.
• Время и lease-reads. Lease-based linearizable reads опираются на ограниченный clock drift; нарушение предположений о часах ломает корректность чтений.
• Дубликаты от клиента. Клиентский retry после таймаута может задвоить команду; нужны идемпотентные client request id (dedup в state machine).

Вопросы на собеседовании#

В: Что такое replicated state machine и при чём тут консенсус? О: RSM — это подход, где несколько реплик применяют одинаковый детерминированный лог команд в одинаковом порядке и потому приходят в идентичное состояние. Задача консенсуса здесь — согласовать сам порядок команд в логе (total order broadcast). Решив консенсус, мы автоматически реплицируем любую детерминированную систему (KV, БД).

В: Сформулируйте FLP impossibility и как Raft с ней живёт. О: В полностью асинхронной сети детерминированный консенсус не может гарантировать завершимость при возможности хотя бы одного отказа, потому что упавший узел неотличим от медленного. Raft не нарушает теорему: он гарантирует safety всегда, а liveness — только при частичной синхронности. Практически это реализуется таймаутами (рандомизированными), которые дают прогресс, когда сеть стабильна.

В: Зачем рандомизировать election timeout? О: Чтобы избежать split vote — ситуации, когда несколько кандидатов стартуют одновременно и делят голоса так, что никто не набирает большинство. Случайные таймауты разносят старты выборов во времени, обычно один кандидат успевает первым и выигрывает. Это разрыв симметрии — практический ответ на FLP.

В: Как Raft гарантирует, что новый лидер не потеряет закоммиченные данные? О: Через election restriction: узел голосует только за кандидата, чей лог не менее свежий (по lastLogTerm, затем lastLogIndex). Закоммиченная запись лежит на большинстве, лидер набирает большинство голосов, два большинства пересекаются -> среди голосующих есть узел с этой записью, и он не выберет кандидата без неё. Значит лидером станет узел со всеми закоммиченными записями (Leader Completeness).

В: Что такое Log Matching Property и как она поддерживается? О: Если записи в двух логах имеют одинаковые index и term, то они содержат одну команду и все предшествующие записи идентичны. Поддерживается consistency check в AppendEntries: RPC несёт prevLogIndex/prevLogTerm, follower принимает записи только при совпадении предыдущей; иначе лидер откатывается назад, пока логи не сойдутся, и переписывает расхождение.

В: Почему берут нечётное число узлов? О: Кворум — большинство (N/2+1). Нечётное N даёт максимум отказоустойчивости при минимальном кворуме: 3 узла переживают 1 отказ, 4 — тоже только 1, но требуют кворум 3 (выше латентность, выше риск). Плюс нечётность исключает раскол 50/50 при сетевом разделении.

В: Чем Multi-Paxos похож на Raft и почему создали Raft? О: Multi-Paxos вводит стабильного лидера, который пропускает фазу Prepare и фактически реплицирует лог одной фазой — это близко к лидер-репликации Raft, и по гарантиям они эквивалентны. Raft создали ради понятности: явный сильный лидер, цельный лог вместо разрозненных слотов, явные terms и чёткая декомпозиция на election/replication/safety. Paxos сложен и оставляет большой разрыв между теорией и реализацией.

В: Можно ли коммитить запись из предыдущего term, как только она реплицирована большинством? О: Нет. Это небезопасно (сценарий §5.4.2): такую запись можно потерять при последующих выборах. Лидер коммитит запись прошлого term только косвенно — реплицировав поверх неё запись своего текущего term, которая, будучи закоммиченной большинством, «тянет» за собой и предыдущие по Log Matching.

В: Как Raft меняет состав кластера без split-brain? О: Через joint consensus: вводится промежуточная конфигурация C_old,new, где для любого решения нужно большинство и в старом, и в новом составе одновременно. Это исключает существование двух непересекающихся большинств. После фиксации переходят к C_new. Современная альтернатива — менять по одному узлу за раз.

В: ZooKeeper использует Raft? О: Нет, ZooKeeper использует ZAB (Zookeeper Atomic Broadcast). Идейно он близок Raft — лидер, эпохи (аналог terms), кворум, total order broadcast, — но это отдельный, более ранний алгоритм. Raft, etcd, Consul, CockroachDB (per range), TiKV — это лагерь Raft.

На что копают на senior+#

• Граница safety vs liveness и связь с FLP. Senior должен чётко разделять: safety никогда не нарушается, liveness гарантируется лишь при частичной синхронности. Это объясняет, почему «вечные перевыборы» при флапающей сети — не баг корректности.
• Тонкость коммита записей прошлого term (§5.4.2). Знание этого нюанса — маркер, что человек реально читал статью Raft, а не пересказ.
• Linearizable reads. Коммит ≠ свежее чтение с любой реплики. Как сделать линеаризуемые чтения: read-from-leader, ReadIndex (подтвердить лидерство кворумом перед чтением), lease reads (с допущениями о часах) и их компромиссы.
• Кворумная интуиция через пересечение большинств. Почему именно большинство, почему два большинства пересекаются и как это даёт и election safety, и сохранность данных.
• Log compaction / snapshots. Реальный Raft невозможен без снапшотов и InstallSnapshot для отставших/новых узлов; рост лога — практическая проблема.
• Membership changes без split-brain (joint consensus vs single-server) и почему «просто заменить конфиг» опасно.
• Multi-Raft и шардирование. Как CockroachDB/TiKV держат тысячи Raft-групп (per range/region), балансировка лидеров, hot range, и почему один глобальный Raft не масштабируется по записи.
• Сравнение моделей отказов. Raft/Paxos — это crash-fault tolerance; для византийских отказов (произвольное/злонамеренное поведение) нужны другие алгоритмы (PBFT, и кворум 3f+1). Умение провести эту границу ценится.
• Связь с CAP. Консенсус-системы — это выбор CP: при потере кворума жертвуют доступностью на запись ради консистентности. Это перекликается с поведением quorum queues в RabbitMQ.