Розподілений Консенсус: Raft, Терміни та Теорема CAP |… |…

Чому узгодження однієї вартості важко

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

жива демонстрація · пов'язана симуляція● LIVE

Raft: один лідер, один журнал, по одному терміну за раз

Raft, розроблений Ongaro та Ousterhout у 2014 році, було спеціально створено для того, щоб його було легше розуміти, ніж більш ранній протокол Paxos, одночасно забезпечуючи ті ж самі гарантії безпеки. Кожен сервер перебуває в одному з трьох станів – послідовник, кандидат або лідер, а час розділений на монотонно зростаючі терміни, кожен з яких містить не більше одного лідера. Усі команди від клієнтів проходять через поточного лідера, які додають їх до свого власного журналу та потім реплікують їх до послідовників за допомогою віддалених викликів AppendEntries, позначених терміном, в якому вони були записані.

Вибір лідера з випадковими тайм-аутами

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

grant_vote(candidate) = candidate.term >= self.currentTerm AND self.votedFor in {null, candidate.id} AND candidate.log є принаймні так само актуальним, як і self.log

// кандидат, який виграє більшість, стає лідером для цього терміну // і негайно відправляє серцебиття для придушення подальших виборів Випадкування тайм-ауту - це вся суть: якщо кожен слідувальник чекав однакового інтервалу часу, то всі б починали вибори одночасно та розділили б голоси назавжди. З випадковими тайм-аутами один слідувальник майже завжди відправляє повідомлення першим і збирає більшість до того, як інші помітять, що лідер зник. Термін діє як логічний годинник — будь-яке повідомлення з застарілим номером терміну відхиляється на місці, що запобігає тому, щоб старий, тимчасово відключений лідер пошкодив журнал після відновлення зв’язку.

grant_vote(candidate) =
  candidate.term  >= self.currentTerm
  AND self.votedFor in {null, candidate.id}
  AND candidate.log is at least as up-to-date as self.log

// a candidate that wins a majority becomes leader for that term
// and immediately sends heartbeats to suppress further elections

Реплікація даних та правило коміту

Запис вважається зафіксованим (committed) і безпечним для застосування до станомішини лише після того, як лідер підтверджує його збереження на більшості серверів – у кластері з п’яти вузлів це означає лідера плюс два послідовників. Це єдине правило дозволяє Raft витримувати ⌊(n-1)/2⌋ відмов: п'ятивузловий кластер виживе дві одночасні аварії, оскільки будь-які дві більшості з п’яти серверів повинні перетинатися принаймні в одному вузлі, тому що нещодавно обраний лідер ніколи не «забуде» значення, яке вже було зафіксовано більшістю.

Теорема CAP: обирайте дві, але P насправді не є необов’язковою

Згідно з теоремою CAP Еріка Брюера, сховище даних розподіленого типу може забезпечувати щонайбільше дві з таких властивостей: узгодженість (кожне читання бачить останнє записування), доступність (кожний запит отримує відповідь) та стійкість до поділів (система продовжує функціонувати при розриві мережі). Оскільки реальні мережі дійсно діляться, відмова від стійкості до поділів не є серйозним варіантом, тому практичний вибір зводиться до CP проти AP. Raft та Paxos – це системи CP: під час поділу меншість відмовляється приймати запису, щоб уникнути ризику двох лідерів, які погоджуються на суперечливі значення — свідомий компроміс доступності для забезпечення кожного підтвердженого запису надійності та правильності.

Збійні помилки проти помилок бізнес-мейнтових

Raft передбачає збійні відмови типу 'crash-stop': поганий вузол просто мовчить, він ніколи не надсилає пошкоджені або суперечливі повідомлення. Це припущення дозволяє 2f+1 реплікам витримувати f збійок. Помилки бізнес-мейнтових повністю відкидають це припущення та припускають, що несправний вузол може поводитися хаотично, включаючи активне обман різних учасників – для цього потрібно 3f+1 реплік плюс криптографічне підписання, щоб витримати той самий f збій, і тому протоколи BFT, такі як PBFT та HotStuff, призначені переважно для блокчейнів та інших ворожих середовищ, а не для звичайних внутрішніх інфраструктур, таких як etcd або метадані KRaft Kafka.

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

Чому Рафт використовує випадкові часові обмеження виборів замість фіксованого?

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

Що саме з Теореми CAP змушує вас відмовитися?

Під час реального розриву мережі ви можете гарантувати лише дві з Consistency (консистентності), Availability (доступності) та Partition tolerance (толерантності до поділів). Оскільки події розриву відбуваються, то толерантність до поділів не є необов’язковою — справжній вибір полягає між консистентністю та доступністю. Raft і Paxos є системами CP: менша сторона під час поділу припиняє приймати запити, щоб уникнути обслуговування застарілих або суперечливих даних, жертвуючи доступність для забезпечення довговічності та правильності кожного підтвердженого запису.

Яка різниця між стійкістю до збоїв і Byzantine стійкістю до збоїв?

Алгоритми стійкості до збоїв, такі як Raft, припускають, що відключений вузол просто перестає відповідати — він ніколи не надсилає спотворені, суперечливі або шкідливі повідомлення. Byzantine стійкість до збоїв передбачає, що відключений вузол може поводитися будь-яким чином, включаючи брехню перед різними пірами, що вимагає 3f+1 реплік для толерантності до f несправних вузлів замість 2f+1 у Raft, а також додаткових раундів криптографічної підписи повідомлень — ця додаткова вартість пояснює, чому BFT використовується лише в блокчейнах і ворожих середовищах, а не для звичайних внутрішніх інфраструктур.

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

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

▶ Відкрити симуляцію the simulation