Raft: Як п’ять машин погоджуються на одну правду без начальника

Проблема, яку вирішує консенсус

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

Raft, опублікований Дієго Онгаро та Джоном Остерхоутом у 2014 році, було спеціально розроблено як зрозуміла альтернатива Paxos, яка доведено правильна, але відома своєю стійкістю до інтуїції. Raft розкладає консенсус на три окремі підзадачі – вибір лідера, реплікацію журналу та безпеку – кожна з яких може бути логічно обґрунтована переважно самостійно.

Кожен вузол завжди перебуває в одній з трьох станів

Сліпе (Follower) → пасивний; реагує на RPC від лідера або кандидата; стан за замовчуванням Кандидат (Candidate) → активно проводить кампанію за голоси після закінчення терміну вибору Лідер (Leader) → єдиний вузол, який приймає клієнтські запити та реплікує їх Сліпі, які не отримують жодних повідомлень до закінчення свого терміну вибору, стають Кандидатами. Зазвичай один переможець з кількох кандидатів стає Лідером для цього терміну. Час ділиться на терміни – монотонно зростаючі цілі числа, які діють як логічний годинник. Зазвичай лише один лідер може бути обраний на термін - це забезпечується тим, що вузол кидає лише один голос за термін, спочатку прийшов - першим обслуговував, тому кандидату потрібна чітка більшість голосів у цьому терміні для перемоги, і два кандидати не можуть обидва перемогти більшість одного й того ж набору виборців.

Follower   → passive; responds to RPCs from a leader or candidate; default state
Candidate  → actively campaigning for votes after an election timeout
Leader     → the one node currently accepting client writes and replicating them

Followers who hear nothing before their election timeout expires become Candidates.
Exactly one Candidate normally wins and becomes Leader for that term.

Вибір лідера: випадкові тайм-аути як вирішальний фактор

Слідовець, який не отримує серцебиття від поточного лідера протягом свого часу вибору, припускає, що лідер зник, збільшує термін (термін), голосує за себе та просить голоси від усіх інших вузлів. Один розумний, хоч і хитрий, детальний момент полягає в тому, що час вибору не є фіксованим – він обирається випадково з діапазону (у статті використовується 150-300мс) кожним вузлом:

electionTimeout = random(150мс, 300мс) // перезапускається кожного разу при скиданні // чому важливий випадковий вибір: // якщо всі слідовці використовують ОДИНАКВИЙ фіксований час вибору, то всі вони одночасно будуть збійовуватися, // стануть кандидатами одночасно, поділять голоси рівномірно, // і повторюватимуться вічно без перемоги будь-якого лідера. // випадковість означає, що таймер одного вузла майже завжди спрацює першим, він стане // кандидатом до того, як інші помітять це, і зазвичай перемагає без проблем. Якщо все ж таки відбувається розподіл голосів (два кандидата збійовуються близько один від одного та ділять слідовців), термін просто закінчується без переможця, і всі вузли перезапускають свій випадковий час вибору для наступного терміну – розподіл голосів рідкісний у практиці та самостійно вирішується протягом однієї або двох додаткових раундів, а не є джерелом тривалого недоступності.

electionTimeout = random(150ms, 300ms)   // re-rolled every time it resets

// why randomness matters:
// if every follower used the SAME fixed timeout, all of them would time out
// simultaneously, all become candidates at once, split the vote evenly,
// and repeat forever with no leader ever winning a majority.
// randomizing means one node's timer almost always fires first, it becomes
// a candidate before the others notice, and usually wins outright.

Реплікація журналу: більшість кворуму, а не єдинозначна згода

Після вибору лідера він єдиний вузол, який приймає команди від клієнтів. Він додає кожну команду до свого власного журналу та надсилає її всім пілотам паралельно через RPC AppendEntries. Важливо зазначити, що лідер вважає запис зафіксованим – надійним, стійким і гарантованим для виживання будь-якої майбутньої зміни лідера – як тільки більшість вузлів (включаючи його самого) зберегли його, а не всі:

У кластері з 5 вузлів потрібно 3 підтвердження для фіксації запису (більшість = 3 з 5) У кластері з 3 вузлів потрібно 2 підтвердження для фіксації запису (більшість = 2 з 3) // Саме тому кластери Raft використовують НЕПАРНІ розміри: 3, 5, 7 – парний розмір не потрібен, // оскільки він не забезпечує додаткової стійкості до відмов порівняно з наступним парним розміром нижче, // оскільки для більшості потрібно вижити однакова кількість вузлів у будь-якому випадку Цей більшості кворум є механізмом, який дозволяє кластеру продовжувати прогрес навіть якщо невелика кількість вузлів не працює або недоступна – 5-вузловий кластер може витримати 2 одночасні збої та продовжує записувати записи, оскільки 3 вузли все ще є більшістю. Саме тому кластери Raft мають непарну кількість: 4-вузловий кластер все ще може витримати лише 1 відмову (потрібно 3 з 4 для більшості, так само як і потрібно 2 з 3), тому 4-й вузол нічого не приносить, крім зайвого мережевого трафіку.

cluster of 5 nodes → needs 3 acknowledgments to commit an entry (majority = 3 of 5)
cluster of 3 nodes → needs 2 acknowledgments to commit an entry (majority = 2 of 3)

// this is why Raft clusters use ODD sizes: 3, 5, 7 — an even-sized cluster
// buys no extra fault tolerance over the next odd size down, because a
// majority requires the same number of survivors either way

Чому застарілий лідер не може безшумно перезаписувати підтверджені дані

Підводна качка в аргументі безпеки: що зупиняє вузол, який був відключений під час вибору лідера, пропустив декілька підтверджених записів і пізніше знову підключився та став лідером, намагаючись перезаписати історію, яку клієнти вже знали як стійку? Відповіддю Raft є обмеження вибору лідера – кандидатом в лідери RequestVote RPC включає індекс і номер терміну його останнього запису журналу, і обранець відмовляється давати голос кандидату, чий журнал застарів порівняно з його власним. Оскільки підтвердження запису вже вимагало більшості голосів, а перемога лідера також потребує більшості голосів, ці дві більшості повинні перетинатися принаймні в одному вузлі – відповідно до теореми Пірсона, будь-який вузол, здатний перемогти на виборах, гарантовано вже містить усі попередньо підтверджені записи. Застарілий журнал кандидата просто не може отримати більшість голосів у першому місці.

Розділи: меншість правильно відмовляється виконувати записи

Сеть, яка розділяє 5-ву кластер на групи по 3 та 2 вузли, є найбільш чітким прикладом концепції. Група з 3 вузлами все ще має більшість: вона може обрати лідера (якщо у неї його ще немає) і продовжувати комітувати нові записи нормально. Група з 2 вузлів не може сформувати більшість із 5 – будь-який вузол там, який тимчасово виходить з ладу та починає голосування, буде збільшувати термін і просити голоси, але ніколи не зможе зібрати необхідні 3 голоси, тому він ніколи не стане функціонуючим лідером, і меншість правильно припиняє приймати записи, щоб уникнути розбіжностей між двома лідерами. Після відновлення розділу застарілі або незавершені записи меншин просто перезаписуються записами AppendEntries від лідера більшості, і журнал згоможується в одну послідовну історію.

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

Часті запитання

Спробуйте наживо

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