Протокол консенсусу Paxos: Як розподілені системи погоджуються на одне значення

Проблема: Узгодження в несприятливих умовах

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

Познайомтесь з персонажами: Пропонуючі, Приймальники та Навчалі

Paxos призначає кожному учасникові вузлу одну або кілька ролей. Пропонуючий – це вузол, який хоче отримати прийняття значення, наприклад запит клієнта на запис нової записи до реплікованого журналу. Приймальник – це вузол, який голосує за пропозиції; приймальники утворюють міцну пам’ять системи та повинні зберігати свої зобов’язання навіть під час перезавантажень. Навчаль – це вузол, який просто хоче дізнатися, яке значення було обрано, не беручи участі в голосуванні. У реальних розгортаннях один фізичний сервер часто виконує кілька ролей одночасно, діючи як пропонуючий і приймальник. Розділення ролей робить Paxos таким гнучким: будь-який вузол може спробувати запропонувати значення в будь-який час, декілька пропонуючих можуть конкурувати одночасно, і протокол збігається на єдиного переможця. Приймальники ніколи не координує по собі безпосередньо; вони реагують лише на пропозиції, що робить комунікаційний шаблон простим і усуває необхідність у крихкому, завжди активному лідері. Ця конструкція також означає, що система зношується граційно. Якщо пропонуючий аварію під час раунду, інший пропонуючий може просто розпочати новий раунд із вищим номером пропозиції та продовжити з того місця, де все залишилося без змін, не пошкоджуючи нічого, що записали приймальники.

Фаза 1: Підготовка та обіцянка

Кожен раунд Paxos починається з унікального номеру пропозиції, і ці монотонно зростаючі номери пропозицій є механізмом вирішення конфліктів між конкуруючими пропонуючими. У Фазі 1 запроситель обирає номер пропозиції n вище за будь-який, який він використовував раніше, і надсилає запит на підготовку з цим номером до більшості приймачів. Кожен приймач, який отримує запит, порівнює n із найвищим номером пропозиції, який він вже обіцяв виконувати. Якщо n вище, приймач обіцяє ніколи не приймати жодної майбутньої пропозиції з номером нижчим за n, і він відповідає цим обіцянкою, а також значенням найвищого номера пропозиції, який він вже прийняв, якщо є. Якщо n не вище, приймач просто ігнорує або відхиляє запит. Цей етап насправді є розвідкою: запроситель перевіряє, чи безпечно все, і, що важливо, дізнається, чи вже була прийнята якась попередня пропозиція частиною більшості. Це відкриття запобігає Paxos безшумному перезапису значень, які вже отримав інший запроситель. Лише після того, як запроситель почув обіцянки назад від більшості приймачів, він має достатньо інформації, щоб безпечно перейти до фактичного пропонування значення у Фазі 2.

Фаза 2: Прийняття та Прийняте

Зозброєний більшістю обіцянок, запроситель переходить до Фази 2. Він повинен уважно вибрати значення для пропозиції: якщо будь-який приймач у Фазі 1 повідомив про вже прийняте значення, запроситель зобов’язаний прийняти значення з найвищого номера такого звіту, а не замінити його власним. Це правило є запобіжним заходом Paxos, гарантуючим, що вже обране значення не може бути тихо замінене. Запроситель надсилає запит на прийняття, який містить номер пропозиції n та обране значення, до цієї ж більшості приймачів. Кожен приймач приймає запит і записує значення, якщо воно ще не було обіцяно у відповідь на вищий номер підготовки від іншого запросителя, ігноруючи пропозиції з номером n або нижчим. Якщо запроситель отримує прийняття від більшості приймачів, значення офіційно обране, хоча інші вузли ще не знають цього. Навчальники дізнаються про обране значення безпосередньо від приймачів або через виділеного навчальника, який агрегує та транслятує результат. Оскільки значення стає обраним лише тоді, коли досягається повна більшість прийняття, і оскільки будь-які дві більшості завжди перетинаються, математично неможливо, щоб два різні значення досягли більшості прийняття.

Чому більшість кворумів гарантують безпеку, і Парокс у реальному світі

Причина, по якій більшість кворумів є настільки потужною, полягає в простому перекритті множини: з будь-якою групою вузлів дві підмножини, кожна з яких містить більше ніж половину членів, гарантовано матимуть спільний вузол. Цей спільний вузол бачив обидва раунди та забезпечує узгодженість між ними, оскільки він не буде приймати пропозицію нижчого номера після того, як пообіцяв її підтримати. Це властивість зберігається навіть під час мережевого розриву, оскільки в межах розділеної мережі може бути лише одна сторона з більшістю, тому лише одна сторона може зробити прогрес, а меншість просто зупиняється до відновлення зв’язку. Цей компроміс, який віддає пріоритет безпеці перед доступністю під час розриву, точно передбачає теорему CAP для узгоджених систем. Ідеї Парокса були настільки фундаментальними, що вони сформували десятиліття інфраструктури. Сервіс блокування Google Chubby, описаний у широко читаній статті 2006 року, використовував заснований на Пароксі відрегульований журнал для підтримки узгодженості даних блокування та конфігурації в різних центрах обробки даних, а Chubby, своєю чергою, надихнув ZooKeeper. Більш нещодавно алгоритм консенсусу Рафт був спеціально розроблений як більш зрозуміла альтернатива Пароксу, і системи, такі як etcd, які живлять Kubernetes, будуються на основі Рафта. Незважаючи на різне пакування, спадщина лідерського вибору та механізмів реплікації журналу Рафт безпосередньо відходить до Парокса, тому справедливо вважати Парокс предком всієї сучасної родини консенсусу.

Frequently asked questions

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

Усе, що вище, працює прямо у вашому браузері — відкрийте The Paxos Consensus Protocol: How Distributed Systems Agree on One Value і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.