Пошук уроків, статей та іншого контенту
Пояснимо задачу консенсусу, кворуми та роль алгоритмів Raft і Paxos у погодженні стану між вузлами.
Консенсус — це процес, у якому кілька вузлів розподіленої системи погоджують одне значення або один порядок операцій, навіть якщо частина вузлів недоступна чи працює ненадійно.
Наприклад, кластер із п’яти вузлів має погодити операцію:
balance[user-42] = 100
Для клієнта важливо, щоб після підтвердження цієї операції різні вузли не вважали одночасно істинними суперечливі стани:
один вузол зберігає баланс 100;
інший — баланс 0;
третій приймає нову операцію на основі неправильного значення.
Консенсус потрібен, щоб узгодити:
яке значення є прийнятим;
у якому порядку застосовувати операції;
коли операцію можна вважати зафіксованою;
який вузол має право координувати запис.
Консенсус не означає, що всі вузли постійно мають однакові копії даних. Під час мережевої затримки або збою вони можуть тимчасово відрізнятися. Важливо, щоб після відновлення система могла безпечно визначити єдиний узгоджений результат.
Алгоритм консенсусу зазвичай оцінюють за двома основними властивостями.
Якщо операція вже була прийнята, алгоритм не повинен пізніше прийняти іншу операцію на тому самому місці замість неї.
У контексті журналу операцій це означає:
одна позиція журналу має містити лише одну команду;
погоджені записи не змінюються;
вузли не можуть одночасно мати двох легітимних лідерів для одного терміну.
Порушення safety — це логічна помилка, яка може призвести до некоректних даних або подвійного виконання операції.
Життєздатність означає, що система зрештою продовжить роботу й погодить нові значення, якщо для цього є необхідні умови.
Наприклад:
мережа перестала втрачати пакети;
доступна достатня кількість вузлів;
новий лідер може бути обраний.
Система може тимчасово зупинити запис, щоб не порушити safety. Це краще, ніж прийняти суперечливі зміни.
Можливості алгоритму залежать від припущень щодо відмов.
У найпоширенішій моделі вузли можуть:
аварійно завершитися;
тимчасово втратити мережеве з’єднання;
працювати повільно;
надсилати повідомлення із затримкою або в іншому порядку.
Такі вузли називають crash-faulty: вони можуть перестати відповідати, але не надсилають навмисно шкідливі повідомлення.
Інша модель — візантійські відмови, коли вузол може поводитися довільно:
надсилати різним вузлам різні значення;
брехати про свій стан;
навмисно порушувати протокол.
Raft і класичний Paxos призначені насамперед для моделі crash-відмов. Вони не захищають від довільно шкідливих вузлів. Для цього потрібні інші алгоритми та додаткові припущення.
Кворум — мінімальна кількість вузлів, яка повинна підтвердити операцію або рішення.
Для кластера з N вузлів часто використовують більшість:
[ Q = \left\lfloor \frac{N}{2} \right\rfloor + 1 ]
Приклади:
3 вузли → кворум 2;
5 вузлів → кворум 3;
7 вузлів → кворум 4.
Два кворуми більшості обов’язково перетинаються хоча б в одному вузлі.
Для п’яти вузлів:
перший кворум: A, B, C;
другий кворум: C, D, E.
Спільний вузол C потрібен для того, щоб нове рішення не було незалежно прийняте двома розділеними групами.
Загальна умова для перетину кворумів:
[ 2Q > N ]
Якщо кворум не є більшістю, дві групи можуть прийняти суперечливі рішення:
група A, B прийняла значення x;
група C, D прийняла значення y;
між групами немає спільного вузла, який міг би перешкодити конфлікту.
Кворум забезпечує безпечність, але зменшує доступність під час відмов.
У кластері з п’яти вузлів можна пережити відмову двох вузлів, оскільки залишаються три вузли для кворуму.
Якщо доступні лише два вузли:
вони можуть продовжувати читати локальні дані;
але не можуть безпечно підтвердити новий консенсус більшості.
Тому система має відмовити в записі або чекати відновлення вузлів, а не створювати окрему історію змін.
Нижче наведено невелику модель: команда вважається зафіксованою лише після підтвердження більшості вузлів. Це не реалізація Raft, а ілюстрація принципу кворуму.
from dataclasses import dataclass, field
@dataclass
class Cluster:
nodes: list[str]
acknowledgements: dict[str, set[str]] = field(default_factory=dict)
@property
def quorum_size(self) -> int:
return len(self.nodes) // 2 + 1
def append(self, command: str, node: str) -> bool:
if node not in self.nodes:
raise ValueError(f"Невідомий вузол: {node}")
self.acknowledgements.setdefault(command, set()).add(node)
confirmed = len(self.acknowledgements[command]) >= self.quorum_size
print(
f"{command}: підтверджень "
f"{len(self.acknowledgements[command])}/{self.quorum_size} "
f"-> {'зафіксовано' if confirmed else 'очікує'}"
)
return confirmed
cluster = Cluster(nodes=["node-a", "node-b", "node-c", "node-d", "node-e"])
cluster.append("set balance=100", "node-a")
cluster.append("set balance=100", "node-c")
cluster.append("set balance=100", "node-e")
print(f"Розмір кворуму: {cluster.quorum_size}")Для п’яти вузлів третє підтвердження досягає кворуму 3. У справжній системі підтвердження також прив’язані до конкретного терміну, позиції журналу та попереднього стану. Самої кількості підтверджень недостатньо для повної реалізації консенсусу.
Практичні алгоритми консенсусу часто погоджують не поточний стан безпосередньо, а журнал команд.
Наприклад, журнал може містити:
1. CREATE_ACCOUNT user-42
2. DEPOSIT user-42 100
3. WITHDRAW user-42 30Кожен вузол:
отримує записи журналу;
погоджує їхню позицію;
записує їх на диск;
чекає моменту фіксації;
застосовує команди до локальної машини станів.
Якщо всі вузли застосовують однакові детерміновані команди в однаковому порядку, вони отримують однаковий стан.
Важливе розділення:
replicated — запис скопійований на вузол;
committed — запис має достатню гарантію, що він не буде замінений іншим;
applied — запис уже застосований до локальної машини станів.
Запис може бути скопійований, але ще не бути committed. Наприклад, лідер встиг передати його одному вузлу, але ще не отримав кворум.
Raft — алгоритм консенсусу для реплікації журналу в кластері з crash-відмовами. Його головна мета — зробити механіку консенсусу зрозумілішою завдяки явному лідеру та поділу протоколу на окремі частини.
У кожен момент вузол має одну з ролей:
follower — очікує повідомлень від лідера;
candidate — намагається бути обраним лідером;
leader — приймає записи та реплікує їх на інші вузли.
Raft ділить час на логічні періоди, які називаються terms.
Кожен термін має номер. Номер:
монотонно збільшується;
допомагає виявляти застарілі повідомлення;
відрізняє старого лідера від нового;
зберігається на диску, щоб не втратити його після перезапуску.
Якщо вузол отримує повідомлення з більшим терміном, він оновлює свій термін і повертається до ролі follower.
Follower запускає таймер виборів. Якщо протягом певного часу він не отримує повідомлення від лідера, то:
збільшує номер терміну;
переходить у стан candidate;
голосує за себе;
надсилає запити на голосування іншим вузлам.
Кандидат стає лідером, якщо отримує більшість голосів.
Щоб уникати постійних одночасних виборів, таймери зазвичай мають випадкову тривалість у заданому діапазоні. Це зменшує ймовірність того, що кілька вузлів одночасно стануть кандидатами.
Клієнт надсилає команду лідеру. Лідер:
додає команду до власного журналу;
надсилає запис follower-вузлам;
чекає підтверджень;
вважає запис committed після підтвердження більшості;
застосовує команду до своєї машини станів;
повідомляє follower-вузлам, що запис можна застосувати.
Follower може мати неповний або застарілий журнал. Raft виправляє його за допомогою перевірки попереднього запису.
Для нового запису лідер передає, зокрема:
номер терміну попереднього запису;
індекс попереднього запису;
новий запис;
індекс останнього committed-запису.
Follower приймає запис лише тоді, коли його журнал узгоджується з попереднім записом. Інакше лідер відступає до попередньої позиції та повторює синхронізацію.
Raft гарантує, що committed-запис не буде замінений іншим записом.
Це досягається кількома правилами:
лідер може голосувати лише за кандидата з достатньо актуальним журналом;
при виборі враховуються термін і індекс останнього запису;
новий лідер має містити всі записи, які були committed у попередніх термінах;
вузол не голосує повторно в одному терміні.
У спрощеному вигляді протокол використовує два основні типи запитів:
RequestVote — запит голосу від кандидата;
AppendEntries — реплікація журналу або heartbeat від лідера.
Heartbeat не обов’язково містить новий запис. Він повідомляє follower-вузлам, що лідер активний, і запобігає непотрібним виборам.
Paxos — сімейство алгоритмів консенсусу, що формалізує погодження значення між вузлами за наявності crash-відмов.
Класична модель Paxos описує ролі:
proposer — пропонує значення;
acceptor — бере участь у прийнятті пропозиції;
learner — дізнається про прийняте значення.
В одному фізичному вузлі можуть одночасно бути реалізовані всі ці ролі.
Кожна пропозиція має унікальний, монотонно порівнюваний номер.
Процес відбувається у дві фази.
Proposer обирає номер пропозиції n і надсилає acceptor-вузлам запит:
Чи обіцяєте ви не приймати пропозиції з номером, меншим за
n?
Acceptor:
запам’ятовує найбільший номер обіцянки;
повертає вже прийняте значення, якщо воно існує;
відхиляє запити зі старими номерами.
Якщо proposer отримав обіцянки від кворуму, він надсилає запит прийняти значення.
Якщо серед відповідей уже було прийняте значення, proposer повинен продовжити саме його. Він не може просто замінити його власним значенням.
Якщо попереднього прийнятого значення немає, proposer може запропонувати нове.
Значення вважається прийнятим після підтвердження кворумом acceptor-вузлів.
Класичний Paxos погоджує одне значення. Для журналу операцій потрібно погодити багато послідовних позицій, тому використовують варіанти на кшталт Multi-Paxos.
Multi-Paxos оптимізує повторне погодження, зазвичай призначаючи стабільного координатора для багатьох послідовних операцій.
У практичних системах Raft часто обирають через простішу модель:
є один явний лідер;
журнал має природний порядок;
вибори та реплікація описані окремо;
простіше пояснювати стан вузлів і відновлення журналу.
Paxos має сильну теоретичну основу, але його базовий опис менш безпосередньо відповідає структурі прикладного журналу.
Обидва алгоритми:
використовують кворуми;
працюють у моделі crash-відмов;
не приймають рішення без достатньої кількості вузлів;
захищають уже прийняті значення;
залежать від коректного зберігання метаданих на диску;
можуть втрачати liveness під час мережевого розділення.
Основна відмінність — у способі організації протоколу.
Raft:
має явного лідера;
реплікує впорядкований журнал;
використовує терміни та вибори;
зазвичай легше реалізується й аналізується на рівні системи.
Paxos:
описує погодження через proposer, acceptor і learner;
допускає більш загальну організацію координаторів;
вимагає уважного опрацювання багатьох варіантів для журналу;
часто подається як набір протоколів, а не як одна проста схема роботи кластера.
Розглянемо кластер із п’яти вузлів, розділений на групи:
група 1: два вузли;
група 2: три вузли.
Група з трьох вузлів має більшість і може продовжити погодження. Група з двох вузлів не має кворуму та повинна зупинити підтвердження нових записів.
Це запобігає ситуації, коли після відновлення мережі обидві групи мають власну історію committed-записів.
Якщо розділення ділить кластер навпіл, жодна група не має більшості. У такому випадку запис зупиняється повністю, хоча вузли можуть залишатися доступними для локальних операцій читання залежно від гарантій конкретної системи.
Для безпечного відновлення після перезапуску вузол має зберігати критичний стан на стабільному сховищі.
Залежно від алгоритму це може бути:
поточний термін;
останній номер голосування;
журнал записів;
індекс або метадані committed-стану.
Порядок запису також важливий. Вузол не повинен повідомляти іншим, що дані збережені, якщо вони ще можуть бути втрачені через збій живлення.
На практиці для цього використовують надійний запис на диск і відповідні гарантії flush. Деталі залежать від сховища, але принцип незмінний:
підтвердження клієнту має відповідати стану, який система справді може відновити.
Консенсус має ціну:
додаткові мережеві обміни;
затримка очікування кворуму;
дискові операції;
складне відновлення відсталих вузлів;
зменшення доступності під час втрати більшості.
Для кластера з більшістю потрібні щонайменше:
один обмін для передачі операції;
підтвердження від кворуму;
застосування committed-запису на вузлах.
Тому узгоджений запис зазвичай повільніший за локальний запис в один вузол. Ця затримка є платою за гарантію, що підтверджена операція не залежить від одного екземпляра.
Клієнт надсилає команду лідеру.
Лідер додає команду до свого журналу.
Лідер реплікує запис follower-вузлам.
Вузли підтверджують запис після його прийняття.
Лідер перевіряє наявність кворуму.
Запис стає committed.
Лідер застосовує його до машини станів.
Лідер повідомляє follower-вузлам новий committed-індекс.
Follower-вузли застосовують запис локально.
Клієнт отримує успішну відповідь.
Якщо лідер падає до кроку 5, запис може залишитися лише в частині журналів і не бути committed. Новий лідер може зберегти або видалити такий непідтверджений запис, якщо це потрібно для узгодження журналів.
Якщо лідер падає після кроку 5, committed-запис має залишитися в журналі майбутнього лідера.
Копіювання даних на кілька вузлів не гарантує узгодженості. Потрібно визначити:
хто має право приймати запис;
який кворум достатній;
як вибирається наступний лідер;
як виправляються конфліктні журнали.
Відповідь одного вузла не захищає від його відмови. Для більшості кластерів запис потрібно підтвердити кворумом.
Вузол може бути доступним по мережі, але його група може не мати кворуму. У такому разі безпечний запис неможливий.
Кворум лише допомагає координувати рішення. Потрібні також:
коректна логіка виборів;
монотонні терміни або номери пропозицій;
перевірка порядку журналу;
надійне зберігання стану;
ідемпотентна або правильно контрольована обробка команд.
Запис може бути committed, але ще не застосованим на конкретному вузлі. Читання має враховувати потрібну гарантію узгодженості.
Raft і класичний Paxos не вирішують проблему вузла, який навмисно бреше або підробляє повідомлення. Вони розраховані на інший тип відмов.
Потрібно явно перевірити поведінку системи, коли:
лідер ізольований від більшості;
follower-вузли бачать різні частини кластера;
вузол повертається після тривалої відсутності;
дві групи намагаються приймати записи одночасно.
Без цього система може виглядати коректною в нормальних умовах, але втрачати узгодженість під час аварії.
Консенсус погоджує значення або порядок операцій між вузлами.
Safety забороняє суперечливі рішення, а liveness забезпечує продовження роботи за сприятливих умов.
Кворум більшості забезпечує перетин різних рішень.
Кластер із 2f + 1 вузлів може пережити відмову до f вузлів без втрати можливості погоджувати записи.
Raft використовує явного лідера, терміни та реплікований журнал.
Paxos погоджує значення через proposer, acceptor і learner; Multi-Paxos розширює підхід для послідовності операцій.
Реплікований, committed і applied — різні стани запису.
Під час втрати кворуму система має зупинити безпечний запис, а не створювати конфліктні історії.
Консенсус не усуває мережеві затримки та відмови, а визначає правила безпечної роботи в їхній присутності.