UK 
EnglishТипова
Polski💻 Розподілений Консенсус
Алгоритм консенсусу Raft, теорема CAP та візантійська відмовостійкість у розподілених системах.
Про цю симуляцію
Ця симуляція показує, як кластер із п'яти вузлів досягає згоди за допомогою алгоритму консенсусу Raft. Кожен вузол має рандомізований таймер виборів, голосує за кандидата, і щойно він набирає кворум із трьох голосів із п'яти — стає лідером на даний термін. Потім лідер реплікує команди клієнтів як записи журналу через повідомлення heartbeat та AppendEntries, тож увесь кластер лишається узгодженим, навіть якщо окремі вузли виходять з ладу або мережа розділяється.
🔬 Що показано
Анімований на канвасі кластер Raft із п'яти вузлів. Вузли циклічно змінюють ролі: фолловер, кандидат і лідер; таймери виборів показані як дуги, що заповнюються, а кольорові крапки позначають повідомлення RequestVote, Heartbeat та AppendEntries між вузлами. Вибори потребують кворуму більшості із трьох голосів, а записи журналу фіксуються лише після підтвердження більшістю.
🎮 Як користуватися
Оберіть алгоритм (Raft, Paxos або BFT) верхніми кнопками. Використовуйте «Append Log Entry», щоб лідер реплікував команду, «Network Partition», щоб розділити кластер на [N1,N2,N3] і [N4,N5], та «Heal Partition», щоб з'єднати його знову. Кожен вузол у списку має кнопки Kill/Revive, а «Reset Cluster» перезапускає вибори з нуля.
💡 Чи знали ви?
Raft розробили у 2013 році Дієго Онгаро та Джон Оустерхаут спеціально для того, щоб він був зрозумілішим за Paxos, зберігаючи ті самі гарантії відмовостійкості. Він працює у виробничих системах, як-от etcd, Consul і CockroachDB.
Часті запитання
Що таке розподілений консенсус?
Розподілений консенсус — це задача змусити багато незалежних машин погодитися на єдине спільне значення чи впорядковану послідовність команд, навіть якщо частина машин виходить з ладу або повідомлення губляться. Це основа відмовостійких баз даних, сховищ конфігурацій і реплікованих машин станів, яка гарантує, що кожен справний вузол зрештою матиме той самий зафіксований журнал.
Як тут працює алгоритм Raft?
Кожен фолловер має рандомізований таймаут виборів. Коли він спливає без сигналу від лідера, вузол стає кандидатом, збільшує свій термін і запитує голоси. Якщо він збирає кворум із трьох голосів із п'яти — стає лідером і надсилає періодичні heartbeat. Лідер реплікує нові записи фолловерам і позначає їх зафіксованими, щойно більшість підтверджує отримання.
Що роблять елементи керування та панелі статистики?
Кнопки алгоритму перемикають між Raft, Paxos і BFT та скидають кластер. «Append Log Entry» просить поточного лідера реплікувати команду; «Network Partition» ізолює вузли N4 і N5; кнопки Kill і Revive виводять вузли з ладу або відновлюють їх. Панель статистики показує поточного лідера, номер терміну, кількість зафіксованих записів, кількість живих вузлів, відсоток доступності та потрібний кворум.
Чому розділення мережі змушує проводити нові вибори?
Raft гарантує безпеку, вимагаючи кворуму більшості. Коли кластер розділяється на [N1,N2,N3] та [N4,N5], лише сторона з трьома чи більше вузлами може обрати лідера та зафіксувати записи. Якщо старий лідер опиняється в меншості з двох вузлів, він більше не може досягти кворуму, тож сторона більшості обирає нового лідера з вищим терміном, поки сторона меншості простоює.
Чи є це правдивою моделлю справжнього кластера Raft?
Вона точно відтворює основну механіку: терміни, рандомізовані таймаути виборів, голосування більшістю, heartbeat лідера, реплікацію журналу та фіксацію на основі кворуму. Для наочності спрощено деякі деталі, як-от повну перевірку узгодженості журналу, постійне зберігання даних і точну логіку повторних спроб RPC, а кнопки Paxos і BFT — ілюстративні варіанти, а не окремі повні реалізації.
Про Розподілений Консенсус — Raft і Візантійська Відмовостійкість
Ця симуляція моделює розподілений кластер із п'яти вузлів, що працює на алгоритмі консенсусу Raft, який вирішує фундаментальну задачу — змусити незалежні машини погодитися на спільний упорядкований журнал команд навіть тоді, коли вузли виходять з ладу чи мережа розділяється. Ви можете спостерігати за виборами лідера в реальному часі, коли вузли обмінюються повідомленнями RequestVote і Heartbeat, побачити, як кворум (більшість із трьох вузлів із п'яти) визначає кожну фіксацію, і поекспериментувати зі збоями вузлів та розділенням мережі, щоб побачити, як кластер відновлюється. Перемикання в режими Paxos або BFT ілюструє альтернативні підходи до тієї самої основної проблеми.
Алгоритми розподіленого консенсусу лежать в основі практично кожної надійної великомасштабної системи, від Google Spanner і Amazon DynamoDB до таких опорних систем з відкритим кодом, як etcd (що живить Kubernetes) та Apache Zookeeper, що робить цю тему однією з найбільш практично важливих у інформатиці.
Часті запитання
Що таке проблема консенсусу в розподілених системах?
Проблема консенсусу питає, як набір незалежних процесів, кожен зі своїм станом і схильних до збоїв, може надійно домовитися про єдине значення чи послідовність рішень. Коректний протокол консенсусу має одночасно задовольняти три властивості: безпеку (усі вузли, що приймають рішення, мають прийняти те саме значення), живучість (система має зрештою просуватися вперед) та відмовостійкість (протокол має продовжувати працювати попри обмежену кількість збоїв вузлів чи втрат повідомлень).
Як за допомогою цієї симуляції побачити вибори лідера?
Коли сторінка завантажується, усі п'ять вузлів починають як фолловери з рандомізованими таймерами виборів, показаними як жовті дуги, що заповнюються навколо кожного кола. Перший вузол, чий таймер спливає, стає кандидатом, надсилає повідомлення RequestVote (жовті крапки), і якщо він збирає три голоси — стає синім як новий лідер. Ви можете будь-коли примусово викликати нові вибори, натиснувши Kill на поточному лідері та спостерігаючи, як серед решти вузлів автоматично починаються нові вибори.
Що відбувається із записами журналу під час розділення мережі?
Натискання «Network Partition» ізолює вузли N4 і N5 від N1, N2 та N3. Оскільки Raft вимагає кворуму із трьох для фіксації будь-якого запису, менша сторона (N4, N5) заморожена і не може обрати лідера чи зафіксувати нові команди. Більша сторона (N1, N2, N3) може, як і раніше, обирати лідера й додавати записи. Коли ви натискаєте «Heal Partition», ізольовані вузли приєднуються знову, виявляють лідера з вищим терміном і автоматично синхронізують свої журнали.
Що таке кворум і чому це рівно три з п'яти?
Кворум — це мінімальна кількість вузлів, які мають брати участь у рішенні, щоб гарантувати, що будь-які два кворуми перетинаються принаймні в одному вузлі. Для кластера з N вузлів кворум Raft дорівнює floor(N/2) + 1. Для п'яти вузлів це floor(5/2) + 1 = 3. Ця властивість перетину гарантує, що будь-які дві більшості мають спільний вузол, який бачив найновіший зафіксований стан, запобігаючи тому, щоб два суперечливі лідери незалежно фіксували конфліктні записи й порушували узгодженість.
Чим Raft відрізняється від Paxos?
Paxos, описаний Леслі Лампортом у його статті 1989 року «The Part-Time Parliament» (опублікованій 1998 року), часто вважають канонічним алгоритмом консенсусу, але його відомо важко повністю зрозуміти й реалізувати, оскільки багато практичних деталей залишено неявними. Raft, розроблений Дієго Онгаро та Джоном Оустерхаутом і опублікований у 2014 році, розкладає задачу на три значною мірою незалежні підзадачі (вибори лідера, реплікацію журналу та безпеку) і використовує єдиного сильного лідера, щоб спростити міркування. Емпіричні дослідження показали, що студенти й інженери засвоюють Raft значно швидше за Paxos, тоді як обидва алгоритми надають еквівалентні гарантії відмовостійкості.
Що таке візантійська відмовостійкість і коли вона важлива?
Візантійські збої — найважчий клас відмов: вузол не просто виходить з ладу й замовкає, а активно надсилає неправильні, суперечливі чи зловмисні повідомлення різним однорангам. Протокол з візантійською відмовостійкістю (BFT), як-от PBFT чи варіант HotStuff, що використовується в багатьох блокчейнах, може витримати до floor((N-1)/3) візантійських вузлів, вимагаючи щонайменше 3f+1 вузлів для обробки f зрадників. Це дорожче за відмовостійкість Raft до збоїв (яка потребує лише 2f+1 вузлів для f збоїв), але є необхідним у відкритих ворожих середовищах, як-от блокчейн-мережі, де учасникам не можна довіряти.
Хто винайшов Raft і коли його опубліковано?
Raft створив Дієго Онгаро в рамках своєї докторської дисертації в Стенфордському університеті під керівництвом Джона Оустерхаута. Основоположну статтю «In Search of an Understandable Consensus Algorithm» представили на USENIX ATC у червні 2014 року, і вона здобула нагороду Best Paper. Мета Онгаро була явною: розробити алгоритм консенсусу, головна чеснота якого — зрозумілість, аби практикам було легше створювати коректні реалізації порівняно зі щільним формалізмом Paxos.
Які реальні системи використовують розподілений консенсус?
Raft використовується в etcd (опорному сховищі стану кластера Kubernetes), HashiCorp Consul (сервісна мережа й конфігурація), CockroachDB та TiKV (розподілений SQL) і InfluxDB. Paxos (або похідні від нього протоколи) лежить в основі Google Chubby, Google Spanner та Apache Zookeeper. Варіанти візантійського консенсусу живлять блокчейн-двигуни консенсусу, як-от Tendermint (Cosmos), HotStuff (Libra/Diem) та дозволені реєстри на основі PBFT. Amazon DynamoDB використовує підхід, подібний до Raft, для своїх внутрішніх груп реплікації.
Чи втрачає кластер Raft коли-небудь зафіксовані дані?
Поширена помилкова думка, що знищення вузлів може призвести до втрати вже зафіксованих записів. У Raft це неможливо, доки виживає кворум вузлів: запис позначається зафіксованим лише після того, як лідер отримав підтвердження від більшості, а властивість безпеки виборів Raft гарантує, що будь-який майбутній лідер матиме принаймні один вузол із тієї більшості у своєму власному кворумі, тож він завжди зберігатиме зафіксований запис. Дані можуть бути безповоротно втрачені лише тоді, коли одночасно виходить з ладу стільки вузлів, що жоден кворум не виживає — для п'яти вузлів це означає одночасну втрату трьох чи більше вузлів.
Як теорема CAP пов'язана з алгоритмами консенсусу?
Теорема CAP Еріка Брюера (формалізована Гілбертом і Лінч у 2002 році) стверджує, що розподілена система не може одночасно гарантувати узгодженість, доступність і стійкість до розділення: під час розділення мережі доведеться обрати одне з двох. Raft і Paxos обирають CP — під час розділення менша сторона стає недоступною, аби не ризикувати видачею застарілих чи неузгоджених даних. Сховища з остаточною узгодженістю, як-от Apache Cassandra, обирають AP, залишаючись доступними під час розділень, але потенційно видаючи застарілі читання. Цей симулятор безпосередньо демонструє вибір CP: ізольована частина N4/N5 припиняє обслуговувати запити, замість того щоб розійтися з більшістю.
Які нинішні напрями досліджень у розподіленому консенсусі?
Активні дослідження зосереджені на кількох напрямах: геороозподілений консенсус зі зменшеною затримкою за допомогою Flexible Paxos та WAN-оптимізованих варіантів; протоколи без лідера, як-от EPaxos і Atlas, що дозволяють будь-якому вузлу фіксувати неконфліктні команди паралельно, усуваючи вузьке місце лідера; протоколи реконфігурації, що безпечно додають чи видаляють вузли без зупинки системи; та інтеграцію з апаратними довіреними середовищами виконання (Intel TDX, AMD SEV) для зменшення вартості візантійської відмовостійкості. У сфері блокчейну BFT-протоколи на основі proof-of-stake, як-от Gasper в Ethereum, продовжують еволюціонувати в бік вищої пропускної здатності та формальної верифіковності.