Алгоритм консенсусу Raft — вибори лідера й реплікація журналу

1. Задача консенсусу

Розподілена система є узгодженою, якщо всі справні вузли погоджуються щодо однієї й тієї ж послідовності зафіксованих значень (реплікованого журналу). Клієнти надсилають команди; система має забезпечити:

• Безпеку (safety): зафіксовані записи ніколи не втрачаються й не змінюються, і всі вузли, що фіксують, застосовують однаковий запис на кожному індексі журналу.
• Живучість (liveness): система продовжує рухатися вперед (фіксувати нові записи), доки більшість вузлів доступні й працездатні.

Теорема неможливості FLP (Фішер, Лінч, Патерсон, 1985) доводить, що в повністю асинхронній системі жоден детермінований алгоритм не може гарантувати водночас безпеку й живучість, коли навіть один вузол може відмовити. Практичні системи обходять це за допомогою тайм-аутів (припущення слабкої синхронності) — Raft не виняток.

2. Ролі серверів і терміни

У будь-який момент кожен сервер Raft перебуває в одному з трьох станів:

• Лідер (Leader): приймає запити клієнтів, реплікує записи журналу послідовникам, надсилає серцебиття. Щонайбільше один лідер на термін.
• Послідовник (Follower): пасивний; відповідає на RPC від лідера й кандидатів. Якщо серцебиття не отримане в межах тайм-ауту виборів, перетворюється на кандидата.
• Кандидат (Candidate): намагається стати лідером; надсилає RPC RequestVote усім іншим серверам.

Час поділено на терміни — монотонно зростаючі цілі числа. Кожен термін починається з виборів. Якщо кандидат перемагає, він служить лідером до кінця терміну. Якщо жоден кандидат не перемагає (наприклад, розщеплення голосів), термін завершується без лідера й починається новий термін.

3. Вибори лідера

Коли в послідовника спливає тайм-аут виборів (не отримано серцебиття), він переходить у стан кандидата, збільшує свій поточний термін, голосує за себе й надсилає RequestVote RPC усім іншим серверам:

// Аргументи RPC RequestVote
type RequestVoteArgs struct {
  Term         int    // термін кандидата
  CandidateId  int    // кандидат, що просить голос
  LastLogIndex int    // індекс останнього запису журналу кандидата
  LastLogTerm  int    // термін останнього запису журналу кандидата
}

// Голосуючий віддає голос, якщо:
// 1. ще не голосував у цьому терміні (або голосував за цього кандидата)
// 2. журнал кандидата щонайменше такий же актуальний, як журнал отримувача
func handleRequestVote(args RequestVoteArgs) bool {
  if args.Term < currentTerm { return false }
  logUpToDate := args.LastLogTerm > lastLogTerm ||
    (args.LastLogTerm == lastLogTerm && args.LastLogIndex >= lastLogIndex)
  if (votedFor == -1 || votedFor == args.CandidateId) && logUpToDate {
    votedFor = args.CandidateId
    return true
  }
  return false
}

Якщо кандидат отримує голоси більшості серверів, він стає новим лідером і негайно надсилає серцебиття у вигляді RPC AppendEntries, щоб придушити подальші вибори.

Тайм-аут виборів рандомізований (зазвичай 150–300 мс), щоб уникнути розщеплення голосів, коли багато кандидатів стартують одночасно. Якщо розщеплення голосів усе ж стається, усі кандидати вичерпують тайм-аут і починають нові вибори.

4. Реплікація журналу

Щойно обраний, лідер приймає команди клієнтів, додає їх до свого журналу й реплікує послідовникам через RPC AppendEntries:

1. Клієнт надсилає команду лідеру.
2. Лідер додає запис до локального журналу з номером поточного терміну.
3. Лідер надсилає AppendEntries усім послідовникам паралельно (також слугує серцебиттям, коли порожній).
4. Щойно більшість серверів записали запис у свої журнали, лідер фіксує запис — застосовує його до своєї скінченної машини станів і відповідає клієнту.
5. Лідер включає commitIndex у наступні AppendEntries; послідовники фіксують аж до цього індексу.

5. Гарантії безпеки

Коректність Raft спирається на властивість повноти лідера (Leader Completeness Property): якщо запис журналу зафіксований у певному терміні, цей запис буде присутнім у журналах усіх лідерів для всіх термінів з вищими номерами.

Це забезпечується обмеженням виборів: кандидат не може перемогти у виборах, якщо його журнал не є щонайменше таким же актуальним, як у будь-якого іншого сервера в більшості, що голосує за нього. «Актуальність» визначається порівнянням (lastLogTerm, lastLogIndex) — вищий термін перемагає; за рівності перемагає довший журнал.

Raft також запобігає тонкій помилці: лідер не може фіксувати записи з попередніх термінів, рахуючи репліки — він може зафіксувати їх лише, зафіксувавши новий запис зі свого власного терміну (що приводить до неявної фіксації старіших записів через властивість збігу журналів).

6. Зміни складу кластера

Додавання чи видалення серверів потребує обережності — наївне миттєве перемикання могло б одночасно створити дві більшості. Спочатку Raft пропонував підхід спільного консенсусу (joint consensus) з переходом через об'єднану конфігурацію стара+нова. Сучасні реалізації зазвичай використовують простіший протокол зміни складу по одному серверу:

• За раз додається або видаляється один сервер.
• Оскільки стара й нова конфігурації перетинаються в більшості, розщеплення мозку неможливе.
• Зміна складу додається як спеціальний запис журналу; нова конфігурація набуває чинності після фіксації.

Новододані сервери стартують як учні без права голосу (non-voting learners), що реплікують журнал, не беручи участі у виборах і не зараховуючись до кворуму — це запобігає затримці виборів, поки вони наздоганяють потенційно петабайти історичного журналу.

7. Порівняння з Paxos

Raft і multi-Paxos розв'язують одну й ту саму задачу й мають подібні характеристики продуктивності. Головна перевага Raft — ясність специфікації; оригінальна стаття Онгаро й Оустергаута містить формальний доказ коректності та дослідження зручності, що показує: за однаковий час вивчення студенти розуміли Raft краще за Paxos. Ця зрозумілість виливається у менше помилок у промислових реалізаціях.

Сховище ключ-значення etcd використовує Raft і утворює координаційне серце Kubernetes — щоразу, коли планується под, вузол виводиться з обслуговування чи оновлюється ConfigMap, консенсус Raft гарантує, що зміна безпечно збережена на всіх репліках etcd ще до того, як API-сервер підтвердить успіх.