Паксос англ Paxos це набір протоколів призначених для консенсусу в мережі ненадійних процесорів Консенсус процес отриман

Паксос (англ. Paxos) — це набір протоколів, призначених для консенсусу в мережі ненадійних процесорів. Консенсус — процес отримання узгодженого результату групою учасників. Вирішити цю проблему складно, якщо в учасників або в засобах їх комунікації виникають помилки.

Протоколи рішення задачі консенсусу є базовим елементом у розподілених обчисленнях, що запропонував Леслі Лампорт і дослідив далі Ф. Шнайдер.

Протокол Паксос був вперше опублікований у 1989 році та був названий на честь вигаданої законодавчої системи, що застосовувалася на острові Паксос у Греції. Пізніше був опублікований в науковій літературі в 1998 році.

Сімейство протоколів Паксос включає спектр компромісів між кількістю процесорів, кількістю затримок повідомлень, рівня активності окремих учасників та кількістю відправлених повідомлень. Результат відмовостійкого узгодження не визначений, однак умови, при яких консенсус неможливий, дуже рідкісні.

Паксос зазвичай використовується, для копіювання файлу чи бази даних. Протокол намагається досягти прогресу навіть у періоди, коли деяка обмежена кількість вузлів не відповідає. Існує також механізм видалення або додавання нового вузла.

Історія

У 1988 р. Лінч, Дрюк і Стокмейер продемонстрували розв'язність консенсусу в широкому сімействі «частково синхронних» систем. Паксос має сильну схожість з протоколом, який використовується для узгодження у «прогляді реплікації». Паксос запропонував особливо елегантний формалізм і включив одне з найбільш ранніх доказів безпеки для відмовостійкого протоколу розподіленого консенсусу.

Реконфігуровані машини мають міцні зв'язки з попередньою роботою над протоколами багатоадресної групи, які підтримують членство динамічної групи, наприклад роботи Бірмана 1985 та 1987 року практичного синхронного gbcast протоколу.

Протоколи Паксос є членами теоретичного класу рішень проблем, формалізованих як єдине узгодження з відмовами. Нижні межі цієї проблеми були доведені Кейдаром та Шраером. Derecho — це бібліотека програмного забезпечення для реплікації хмарних машин, що пропонує протокол Паксос, який інтегрований у систему. Цей протокол відповідає межам оптимальності Кейдара та Шраера і ефективно відображає сучасне обладнання віддаленого DMA (RDMA) центру обробки даних (але використовує TCP, якщо RDMA недоступний).

Припущення

Наступні припущення та визначення робляться явними. Методи розширення застосування не висвітлюються в цій статті.

Процесори

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

Мережа

Процесори можуть надсилати повідомлення на будь-який інший процесор.
Повідомлення надсилаються асинхронно та можуть доставляти довільну кількість часу.
Повідомлення можуть бути втрачені, переупорядковані або продубльовані.
Повідомлення доставляються без корупції, тобто, візантійські невдачі не відбуваються.

Кількість процесорів

Загалом алгоритм узгодження може досягти прогресу, за умови використання $n=2F+1$ процесорів, незважаючи на одночасний вихід з ладу будь-яких $F$ процесорів: іншими словами, кількість справних процесів повинна бути строго більшою, ніж кількість несправних процесів. Однак, використовуючи реконфігурацію, може бути використаний протокол, який переживає будь-яку загальну кількість збоїв до тих пір, поки їх не більше ніж F одночасно.

Ролі

Паксос описує дії процесорів за їх ролями в протоколі: клієнт, приймач, заявник, учень та провідник. У типових втіленнях один процесор може грати одну або більше ролей одночасно. Це не впливає на правильність протоколу — зазвичай поєднуються ролі, для поліпшення затримок та/або кількості повідомлень у протоколі.

Клієнт: Клієнт надсилає запит до розподіленої системи та чекає відповіді . Наприклад, запит на запис у файл на розподіленому файловому сервері.
Приймач (виборців): Приймачі виконують функцію відмовостійкої «пам'яті» протоколу. Приймачі збирають в групи, які називаються кворумами. Будь-яке повідомлення, надіслане Приймачу, має бути надіслане в кворум приймачів. Будь-яке повідомлення, отримане від Приймача, ігнорується, якщо копія не отримана від кожного Приймача в кворумі.
Заявник: Заявник просуває запит клієнта, намагаючись переконати Приймачів погодитися з ним. Виконує функцію координатора для зрушення протоколу вперед, коли виникають конфлікти.
Учень: Учні виступають чинником реплікації протоколу. Після того, як Приймачі погодили запит Клієнта, Учень може вжити потрібні заходи (тобто: виконати запит та надіслати відповідь клієнту). Для покращення доступності обробки, можна додати додаткових учнів.
Провідник: Паксос вимагає від зазначеного Заявника (його називають провідником), досягнення прогресу. Багато процесів можуть вважати, що вони ведуть, але протокол гарантує прогрес лише в тому випадку, якщо в кінцевому підсумку обраний один з них. Якщо два процеси вважають, що вони провідники, вони можуть зупиняти протокол, постійно пропонуючи суперечливі оновлення.

Кворуми

Кворуми представляють властивості безпеки алгоритму, забезпечуючи збереження інформації про результати у хоч б одного уцілілого процесора.

Кворуми визначаються як підмножини множини Приймачів таким чином, щоб будь-які дві підмножини (тобто будь-які два кворуму) мали принаймні один спільний елемент. Як правило, кворум є будь-якою більшістю Приймачів, що беруть участь. Наприклад, розглянемо множину Приймачів {А, B, С, D}, кворум більшості складатиметься з будь-яких трьох Приймачів: {А, B, С}, {А, С, D}, {А, В, D} або {B, C, D}. Загальніше, Приймачам і кворуму можуть бути призначені довільні позитивні ваги, які визначають як будь-яка підмножина Приймачів з сумарною вагою перевищує половину загальної ваги усіх Приймачів.

Номер пропозиції та узгоджена вартість

Кожна спроба визначити узгоджене значення v, виконується із пропозиціями, які можуть або не можуть бути прийняті Приймачем. Кожна пропозиція має унікальну нумерацію для даного Заявника. Отже, наприклад, кожна пропозиція може мати вигляд (n, v), де n це унікальний ідентифікатор пропозиції, а v це власне запропоноване значення. Значення, відповідне нумерованій пропозиції, може бути обчислено як частина запуску протоколу Paxos, але це не обов'язково.

Властивості безпеки та живості

Щоб гарантувати безпеку, алгоритм Паксос визначає три властивості та забезпечує постійне дотримання перших двох, незалежно від схеми відмов:

Вагомість (або нетривіальність): Вибирати та вивчати можна лише запропоновані значення.
Домовленість (або узгодженість чи безпека): Немає двох окремих учнів можуть засвоїти різні значення (або не може бути більше одного визначеного значення)
Припинення (або живість): Якщо було запропоновано значення C, то зрештою, учень L дізнається про деяке значення (якщо залишилось достатньо уцілілих процесорів).

Зауважте, що Паксос не гарантує завершення і тому не має властивості живості.

Типове розгортання

У більшості випадків кожен процес, що бере участь виконує три ролі; Заявника, Приймача та Учня. Це значно знижує складність повідомлення, не жервуючи правильністю.

Об'єднуючи ролі, протокол «згортається» в ефективне розгортання стилю клієнт-майстер-репліка, характерне для спільноти баз даних. Перевага протоколів Паксос (включно з утіленням з об'єднаними ролями) це гарантія його властивостей безпеки.

Базовий Паксос

Це найбазовіший протокол із сім'ї Паксос. Кожен «примірник» базового протоколу Паксос визначає одне вихідне значення. Протокол триває декілька раундів. Вдалий раунд має 2 фази: фазу 1 (яка має дві частини a і b) і 2 фазу (яка теж має дві частини a і b). Дивіться нижче опис фаз. Пам'ятайте, що ми припускаємо асинхронну модель, тому, наприклад, процесор може перебувати в одній фазі, а інший процесор — в іншій.

Фаза 1

Фаза 1а: Підготовка

Заявник створює повідомлення, яке ми називаємо «Підготовка» та ототожнює з числом n . Зауважте, що n — це не значення, а лише число, яке однозначно ідентифікує це початкове повідомлення, запропоноване заявником (яке повинно бути надіслане приймачем). Число n повинно бути більше, ніж будь-яке число, використовуване в будь-якому з попередніх фазах Підготовки повідомлення цього Заявника. Потім він надсилає повідомлення Підготовка, що містить n, до кворуму приймачів . Зауважте, що повідомлення цієї фази містить лише число n (тобто воно не повинно містити, наприклад, запропоноване значення, яке часто позначається v). Заявник вирішує, хто в кворумі ^[] ^] . Заявник не повинен ініціювати Paxos, якщо він не може спілкуватися хоча б з кворумом приймачів.

Фаза 1b: Зобов'язання

Будь-який з Приймачів чекає повідомлення з фази 1а від будь-якого із Заявника . Якщо Приймач отримує повідомлення, Приймач повинен переглянути ідентифікаційний номер n щойно отриманого повідомлення. Далі може бути такі випадки.

Число n вище, ніж будь-який попередній номер пропозиції, отриманий Приймачем від будь-якого із Заявників. Тоді Приймач повинен повернути повідомлення, яке ми називаємо «Обіцянкою» та ігнорувати всі майбутні пропозиції, що мають число менше ніж n . Якщо Приймач прийняв пропозицію в якийсь момент минулого, він повинен включити попередній номер пропозиції, скажімо m, і відповідне прийняте значення, скажімо, w, у своїй відповіді на адресу Заявника.

В іншому випадку (якщо n є меншим або рівним будь-якому попередньому номеру пропозиції, отриманому від будь-якого Заявника Приймачу), Приймач може ігнорувати отриману пропозицію.

Фаза 2

Фаза 2а: Погодження

Якщо Заявник отримує більшість «обіцянь» від кворуму Приймачів, йому необхідно встановити значення v своїй пропозиції. Якщо будь-який Приймач раніше прийняв будь-яку пропозицію, то вони надішлють свої значення Заявнику, який тепер повинен встановити значення своєї пропозиції, v, на значення, пов'язане з найвищим числом пропозицій (назвемо його z), про яке повідомили Приймача. Якщо жоден з Приймачів не прийняв пропозицію до цього моменту, то Замовник може вибрати значення, яке він спочатку хотів запропонувати, скажімо x .

Заявник надсилає повідомлення Accept ((n, v)) до кворуму приймачів із вибраним значенням для своєї пропозиції, v та номером пропозиції n. Отже, повідомлення Accept є або (n, v = z), або, якщо жоден з приймачів раніше не прийняв значення, (n, v = x) .

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

Якщо Приймач отримує повідомлення про прийняття (n, v) від Заявника, він повинен прийняти його, тільки якщо він не обіцяв (у фазі 1b протоколу Paxos) розглянути лише пропозиції, що мають ідентифікатор, більший ніж n .

Якщо Акцептор вже не пообіцяв (у Фазі 1b) розглядати лише пропозиції, що мають ідентифікатор, більший за n, він повинен зареєструвати значення v (щойно отриманого повідомлення Accept) як прийняте значення (протоколу) та надіслати Прийняте повідомлення Заявнику та кожному Учаснику (яким зазвичай можуть бути самі Заявники).

Крім того, він може ігнорувати повідомлення Прийняття або запит.

Треба відмітити, що Приймач може брати кілька пропозицій. Це може статися, якщо інший Заявник, не знаючи про нове значення, розпочне новий раунд з більш високим ідентифікаційним номером n . У цьому випадку Приймач може пообіцяти і пізніше прийняти нове запропоноване значення, навіть якщо він прийняв інше раніше. Ці пропозиції можуть мати навіть різні значення за наявності певних невдач. Однак протокол Паксос гарантує, що Приймачі в кінцевому рахунку домовляться.

Коли раунди провалюються

Раунди не вдається, коли кілька заявників надсилають суперечливі підготувальні повідомлення або коли Заявник не отримує кворум відповідей (Обіцяння або Прийняття). У цих випадках слід розпочати ще один раунд із більшим числом пропозицій.

Paxos можна використовувати для вибору лідера

Зауважте, що Приймачі приймають запит та підтверджують лідерство Заявника. Отже, Паксос можна використовувати для вибору лідера в кластері вузлів.

Графічне зображення потоку повідомлень у базовому Паксосі

Наступні діаграми представляють випадки застосування протоколу базового Паксос. Деякі випадки показують, як протокол базового Паксос справляється з відмовою надлишкових компонентів розподіленої системи.

Зауважте, що значення, повернені у повідомленні Обіцяння, «стають нульовими» при першому внесенні пропозиції (оскільки жоден Приймач не прийняв значення до цього раунду).

Базовий Паксос без відмов

На наведеній нижче схемі є 1 Клієнт, 1 Заявник 3 Приймача (тобто розмір Кворуму — 3) та 2 Учні (представлені двома вертикальними лініями). Ця діаграма представляє випадок першого раунду, який є успішним (тобто жоден процес у мережі не завершується)

Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | |<---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->|->|->| | | Accept!(1,V) | |<---------X--X--X------>|->| Accepted(1,V) |<---------------------------------X--X Response | | | | | | |

Client Proposer Acceptor Learner  | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | |<---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->|->|->| | | Accept!(1,V) | |<---------X--X--X------>|->| Accepted(1,V) |<---------------------------------X--X Response | | | | | | |

Тут V — останній із (Va, Vb, Vc).

Випадки помилок у базовому Паксос

Найпростіші випадки помилок — це вихід з ладу Приймача (коли кворум приймачів залишається живим) та відмова зайвого Учня. У цих випадках протокол не треба «відновлювати»: не потрібні додаткові раунди чи повідомлення, які показані у двох наступних діаграмах / випадках.

Базовий Паксос, коли Приймач виходить з ладу

На наступній схемі один з Приймачів відмовляється, тому розмір Кворуму стає 2. У цьому випадку протокол Базовий Паксос все ще є успішним.

Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | | | |  ! | |  !! FAIL !! | |<---------X--X | | Promise(1,{Va, Vb, null}) | X--------->|->| | | Accept!(1,V) | |<---------X--X--------->|->| Accepted(1,V) |<---------------------------------X--X Response | | | | | |

Базовий Паксос, коли Учень виходить з ладу

У наступному випадку один із учнів виходить з ладу, але протокол Базовий Паксос все-таки є успішним.

Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | |<---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->|->|->| | | Accept!(1,V) | |<---------X--X--X------>|->| Accepted(1,V) | | | | | |  !  !! FAIL !! |<---------------------------------X Response | | | | | |

Базовий Паксос, коли Заявник виходить з ладу

У цьому випадку Заявник виходить з ладу після заявлених значень, але до досягнення згоди. Зокрема, воно не в середині повідомлення Accept, тому значення має лише один Приймач кворуму. Тим часом обирається новий Провідник. Зверніть увагу, що в цьому випадку є два раунди (раунди проходять вертикально, зверху вниз).

Client Proposer Acceptor Learner | | | | | | | X----->| | | | | | Request | X------------>|->|->| | | Prepare(1) | |<------------X--X--X | | Promise(1,{Va, Vb, Vc}) | | | | | | | | | | | | | |  !! Leader fails during broadcast !! | X------------>| | | | | Accept!(1,V) |  ! | | | | | | | | | | | |  !! NEW LEADER !! | X--------->|->|->| | | Prepare(2) | |<---------X--X--X | | Promise(2,{V, null, null}) | X--------->|->|->| | | Accept!(2,V) | |<---------X--X--X------>|->| Accepted(2,V) |<---------------------------------X--X Response | | | | | | |

Базовий Паксос, коли конфліктують декілька пропозицій

Найскладніший випадок, коли кілька Заявників вважають себе лідерами. Наприклад, поточний лідер може на деякий час вийти з ладу та пізніше відновитись, але інші Заявники вже обрали нового лідера. При цьому прийнятий лідер цього ще не дізнався і намагається розпочати новий раунд у конфлікті з нинішнім лідером. На діаграмі нижче показано 4 невдалих раунди, але їх може бути більше (як це запропоновано внизу діаграми).

Client Leader Acceptor Learner | | | | | | | X----->| | | | | | Request | X------------>|->|->| | | Prepare(1) | |<------------X--X--X | | Promise(1,{null,null,null}) |  ! | | | | |  !! LEADER FAILS | | | | | | |  !! NEW LEADER (knows last number was 1) | X--------->|->|->| | | Prepare(2) | |<---------X--X--X | | Promise(2,{null,null,null}) | | | | | | | |  !! OLD LEADER recovers | | | | | | | |  !! OLD LEADER tries 2, denied | X------------>|->|->| | | Prepare(2) | |<------------X--X--X | | Nack(2) | | | | | | | |  !! OLD LEADER tries 3 | X------------>|->|->| | | Prepare(3) | |<------------X--X--X | | Promise(3,{null,null,null}) | | | | | | | |  !! NEW LEADER proposes, denied | | X--------->|->|->| | | Accept!(2,Va) | | |<---------X--X--X | | Nack(3) | | | | | | | |  !! NEW LEADER tries 4 | | X--------->|->|->| | | Prepare(4) | | |<---------X--X--X | | Promise(4,{null,null,null}) | | | | | | | |  !! OLD LEADER proposes, denied | X------------>|->|->| | | Accept!(3,Vb) | |<------------X--X--X | | Nack(4) | | | | | | | | ... and so on ...

Мульти-Паксос

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

Якщо лідер стабільний, фаза 1 стає непотрібною. Таким чином, можна пропустити фазу 1 для майбутніх екземплярів протоколу з тим же лідером.

Для цього кругле число I включається разом із кожним значенням, яке збільшується в кожному раунді одним і тим же Провідником. Мульти-Паксос зменшує затримку безвідмовного повідомлення (пропозицію до навчання) з 4 затримок до 2 затримок.

Графічне зображення потоку повідомлень в Базовий Паксос

Мульти-Паксос без відмов

На наступній діаграмі показаний лише один екземпляр базового протоколу Паксос з початковим лідером. Зауважте, що Мульти-Паксос складається з декількох примірників базового протоколу Паксос.

Client Proposer Acceptor Learner | | | | | | | --- First Request --- X-------->| | | | | | Request | X--------->|->|->| | | Prepare(N) | |<---------X--X--X | | Promise(N,I,{Va,Vb,Vc}) | X--------->|->|->| | | Accept!(N,I,V) | |<---------X--X--X------>|->| Accepted(N,I,V) |<---------------------------------X--X Response | | | | | | |

де V = останній з (Va, Vb, Vc).

Мульти-Паксос, коли фаза 1 може бути пропущена

У цьому випадку екземпляри послідовності базового протоколу Паксос використовують того ж самого лідера, тому фаза 1, яка складається з більш коротших фаз Підготувати та Обіцяти, пропускається. Зауважте, що лідер повинен бути стабільним, тобто не повинен виходити з ладу або змінюватися.

Client Proposer Acceptor Learner | | | | | | | --- Following Requests --- X-------->| | | | | | Request | X--------->|->|->| | | Accept!(N,I+1,W) | |<---------X--X--X------>|->| Accepted(N,I+1,W) |<---------------------------------X--X Response | | | | | | |

Мульти-Паксос, коли ролі згортаються

Поширене розгортання Мульти-Паксос полягає у згортанні ролі Заявників, Приймачів та Учнів на «Сервери». Отже, зрештою, є лише «Клієнти» та «Сервери».

Наведена нижче схема представляє перший "екземпляр" базового протоколу Паксос, коли ролі Заявника, Приймача та Учня згортаються в роль "Сервер".

Client Servers | | | | --- First Request --- X-------->| | | Request | X->|->| Prepare(N) | |<-X--X Promise(N, I, {Va, Vb}) | X->|->| Accept!(N, I, Vn) | X<>X<>X Accepted(N, I) |<--------X | | Response | | | |

Мульти-Паксос, коли ролі згортаються, а лідер стійкий

У наступних випадках базового протоколу Паксос з тим самим лідером, що і в попередніх екземплярах базового протоколу Паксос, фаза 1 може бути пропущена.

Client Servers X-------->| | | Request | X->|->| Accept!(N,I+1,W) | X<>X<>X Accepted(N,I+1) |<--------X | | Response | | | |

Оптимізація

Для зменшення кількості повідомлень та покращення продуктивності протоколу можна здійснити ряд оптимізацій. Нижче наведено декілька таких оптимізацій.

Дешевий Паксос

Дешевий Паксос розширює Базовий Паксос, щоб переносити збої F з основними процесорами F + 1 та F допоміжними процесорами шляхом динамічної корекції після кожного збою.

Це зниження потреби в процесорі відбувається за рахунок життєздатності; якщо занадто багато основних процесорів виходять з ладу за короткий час, система повинна зупинитися, поки допоміжні процесори не зможуть переконфігурувати систему. У стабільні періоди допоміжні процесори не беруть участі в протоколі.

Потік повідомлень: Дешевий Мульти-Паксос

Приклад, що включає три основних приймача, один допоміжний приймач і розмір кворуму в три, показує вихід з ладу одного основного процесора та наступну конфігурацію:

{ Acceptors } Proposer Main Aux Learner | | | | | | -- Phase 2 -- X----------->|->|->| | | Accept!(N,I,V) | | |  ! | | --- FAIL! --- |<-----------X--X--------------->| Accepted(N,I,V) | | | | | -- Failure detected (only 2 accepted) -- X----------->|->|------->| | Accept!(N,I,V) (re-transmit, include Aux) |<-----------X--X--------X------>| Accepted(N,I,V) | | | | | -- Reconfigure : Quorum = 2 -- X----------->|->| | | Accept!(N,I+1,W) (Aux not participating) |<-----------X--X--------------->| Accepted(N,I+1,W) | | | | |

Швидкий Паксос

Швидкий узагальнює базовий Паксос, щоб зменшити затримки повідомлення в кінці. У базовому Паксос, затримка повідомлення від запита клієнта до навчання становить 3 затримки за повідомлення. Швидкий Paxos дозволяє затримати 2 повідомлення, але вимагає, щоб (1) система складалася з 3 приймачів + 1 +, щоб допустити до f помилок, і (2) Клієнт надсилає свій запит у кілька напрямків .

Очевидно, якщо керівник не має жодної підстави на запит, то клієнт може надіслати повідомлення безпосередньо Приймачам. Приймачі відповідатимуть як у базових Паксос, надсилаючи Прийняті повідомлення керівнику та кожному Учневі, досягаючи двох затримок повідомлень від Клієнта до Учня.

Якщо лідер виявить збій, то він вирішує його, відправивши повідомлення на новий раунд. Ця координована методика відновлення вимагає чотирьох затримок повідомлень від клієнта до учня.

Остаточна оптимізація відбувається, коли лідер заздалегідь вказує техніку відновлення, дозволяючи Приймачам самостійно виконувати відновлення зіткнення. Таким чином, неузгоджене відновлення зіткнення може відбутися за три затримки повідомлення (і лише дві затримки повідомлення, якщо всі Учні також приймачі).

Потік повідомлень: Швидкий Паксос, безконфліктний

Client Leader Acceptor Learner | | | | | | | | | X--------->|->|->|->| | | Any(N,I,Recovery) | | | | | | | | X------------------->|->|->|->| | | Accept!(N,I,W) | |<---------X--X--X--X------>|->| Accepted(N,I,W) |<------------------------------------X--X Response(W) | | | | | | | |

Потік повідомлень: Швидкий Паксос, суперечливі пропозиції

Конфлікт пропозицій з координованим відновленням. Примітка: протокол не вказує, як обробляти скинутий запит клієнта.

Client Leader Acceptor Learner | | | | | | | | | | | | | | | | | | | | | | | | | | |  !! Concurrent conflicting proposals | | | | | | | | |  !! received in different order | | | | | | | | |  !! by the Acceptors | X--------------?|-?|-?|-?| | | Accept!(N,I,V) X-----------------?|-?|-?|-?| | | Accept!(N,I,W) | | | | | | | | | | | | | | | | | |  !! Acceptors disagree on value | | |<-------X--X->|->|----->|->| Accepted(N,I,V) | | |<-------|<-|<-X--X----->|->| Accepted(N,I,W) | | | | | | | | | | | | | | | | | |  !! Detect collision & recover | | X------->|->|->|->| | | Accept!(N+1,I,W) | | |<-------X--X--X--X----->|->| Accepted(N+1,I,W) |<---------------------------------X--X Response(W) | | | | | | | | |

Суперечність пропозицій з неузгодженим відновленням.

Client Leader Acceptor Learner | | | | | | | | | | | X------->|->|->|->| | | Any(N,I,Recovery) | | | | | | | | | | | | | | | | | |  !! Concurrent conflicting proposals | | | | | | | | |  !! received in different order | | | | | | | | |  !! by the Acceptors | X--------------?|-?|-?|-?| | | Accept!(N,I,V) X-----------------?|-?|-?|-?| | | Accept!(N,I,W) | | | | | | | | | | | | | | | | | |  !! Acceptors disagree on value | | |<-------X--X->|->|----->|->| Accepted(N,I,V) | | |<-------|<-|<-X--X----->|->| Accepted(N,I,W) | | | | | | | | | | | | | | | | | |  !! Detect collision & recover | | |<-------X--X--X--X----->|->| Accepted(N+1,I,W) |<---------------------------------X--X Response(W) | | | | | | | | |

Потік повідомлень: Швидкий Паксос з некоординованим відновленням, згорнуті ролі

Client Servers | | | | | | | | X->|->|->| Any(N,I,Recovery) | | | | | | | | | | | |  !! Concurrent conflicting proposals | | | | | |  !! received in different order | | | | | |  !! by the Servers | X--------?|-?|-?|-?| Accept!(N,I,V) X-----------?|-?|-?|-?| Accept!(N,I,W) | | | | | | | | | | | |  !! Servers disagree on value | | X<>X->|->| Accepted(N,I,V) | | |<-|<-X<>X Accepted(N,I,W) | | | | | | | | | | | |  !! Detect collision & recover | | X<>X<>X<>X Accepted(N+1,I,W) |<-----------X--X--X--X Response(W) | | | | | |

Узагальнений Паксос

Узагальнений консенсус досліджує взаємозв'язок операцій реплікованої машини та протоколу узгодження, який його реалізує . Основне відкриття передбачає оптимізацію Паксос, коли суперечливі пропозиції можуть бути застосовані в будь-якому порядку, тобто коли запропоновані операції є комутаційними операціями для машини. У таких випадках конфліктуючі операції можуть бути прийняті як уникнення затримок, необхідних для вирішення конфліктів.

Ця концепція додатково узагальнена у постійно зростаючій послідовності комутативних операцій, деякі з яких є стабільними. Протокол відстежує ці послідовності та гарантує стабілізацію запропонованих операцій однієї послідовності.

Потік повідомлень: Узагальнений Паксос (приклад)

Client Leader Acceptor Learner | | | | | | | |  !! New Leader Begins Round | | X----->|->|->| | | Prepare(N) | | |<-----X- X- X | | Promise(N,null) | | X----->|->|->| | | Phase2Start(N,null) | | | | | | | | | | | | | | | |  !! Concurrent commuting proposals | X------- ?|-----?|-?|-?| | | Propose(ReadA) X-----------?|-----?|-?|-?| | | Propose(ReadB) | | X------X-------------->|->| Accepted(N,<ReadA,ReadB>) | | |<--------X--X-------->|->| Accepted(N,<ReadB,ReadA>) | | | | | | | | | | | | | | | |  !! No Conflict, both accepted | | | | | | | | Stable = <ReadA, ReadB> | | | | | | | | | | | | | | | |  !! Concurrent conflicting proposals X-----------?|-----?|-?|-?| | | Propose(<WriteB,ReadA>) | X--------?|-----?|-?|-?| | | Propose(ReadB) | | | | | | | | | | X------X-------------->|->| Accepted(N,<WriteB,ReadA> . <ReadB>) | | |<--------X--X-------->|->| Accepted(N,<ReadB> . <WriteB,ReadA>) | | | | | | | | | | | | | | | |  !! Conflict detected, leader chooses | | | | | | | | commutative order: | | | | | | | | V = <ReadA, WriteB, ReadB> | | | | | | | | | | X----->|->|->| | | Phase2Start(N+1,V) | | |<-----X- X- X-------->|->| Accepted(N+1,V) | | | | | | | | Stable = <ReadA, ReadB> . | | | | | | | | <ReadA, WriteB, ReadB> | | | | | | | | | | | | | | | | !! More conflicting proposals X-----------?|-----?|-?|-?| | | Propose(WriteA) | X--------?|-----?|-?|-?| | | Propose(ReadA) | | | | | | | | | | X------X-------------->|->| Accepted(N+1,<WriteA> . <ReadA>) | | |<--------X- X-------->|->| Accepted(N+1,<ReadA> . <WriteA>) | | | | | | | | | | | | | | | |  !! Leader chooses order: | | | | | | | | W = <WriteA, ReadA> | | | | | | | | | | X----->|->|->| | | Phase2Start(N+2,W) | | |<-----X- X- X-------->|->| Accepted(N+2,W) | | | | | | | | Stable = <ReadA, ReadB> . | | | | | | | | <ReadA, WriteB, ReadB> . | | | | | | | | <WriteA, ReadA> | | | | | | | |

Продуктивність

Вищенаведений потік повідомляє нам, що узагальнений Паксос може використовувати семантику операцій, для уникнення зіткнень, та коли мимовільне впорядкування мережі не вдається. Це дозволяє зробити протокол на практиці швидше, ніж Швидкий Паксос. Однак, коли трапляється зіткнення, узагальненому Паксос потрібні дві додаткові поїздки в обидва кінці, щоб відновитися.

У загальному випадку такі тури неминучі і випливають з того, що під час раунду можна прийняти кілька команд. Це робить протокол дорожчим, ніж Паксос, коли конфлікти часті. Сподіваємось, можливі два вдосконалення узагальненого Паксос для покращення часу відновлення.

По-перше, якщо координатор є частиною кожного кворуму Приймачів, то він відновлюється в раунді N + 1 при зіткнення на раунді N. Координатор пропускає фазу 1 і пропонує на фазі 2 останню послідовність, яку він прийняв під час раунду N. Це зменшує витрати на відновлення одної поїздки в обидва кінці.
По-друге, якщо обидва раунди N і N + 1 використовують унікальний і однаковий центрований кворум, коли Приймач виявляє зіткнення в N раунді. Він спонтанно пропонує в раунді N + 1 послідовність, що суфіксує обидві послідовності (і), прийняту в раунді N координатором та (ii) найбільший безконфліктний префікс, який він прийняв у раунді N. За такої зміни вартість відновлення — це затримка одного повідомлення, яка, очевидно, є оптимальною. Це випливає з того, що будь-який процес у цьому кворумі є кворумом читання для фази підготовки наступних раундів.

Візантійський Паксос

Паксос також може бути поширений на підтримку довільних відмов учасників, включаючи брехню, вигадку повідомлень, змову з іншими учасниками, вибіркове неучасть тощо. Такі типи невдач називаються задачами візантійських генералів.

Задача візантійських генералів представлена Кастро та Ліськовим, додає додаткове повідомлення (Перевірити), яка поширує знання та перевіряє дій інших процесорів:

Потік повідомлень: Задача візантійських генералів Мульти-Паксос, стаціонарний стан

Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Accept!(N,I,V) | | X<>X<>X | | Verify(N,I,V) - BROADCAST | |<---------X--X--X------>|->| Accepted(N,V) |<---------------------------------X--X Response(V) | | | | | | |

Швидкий візантійський Паксос представлений Мартіном та Алвісі, усуває цю додаткову затримку, оскільки клієнт відправляє команди безпосередньо Приймачам.

Зверніть увагу, що Прийняте повідомлення у швидких візантійських Паксос надсилається всім Приймачам та всім Учням, тоді як Швидкий Паксос надсилає Прийняті повідомлення лише Учням):

Потік повідомлень: Швидкий візантійський Мульти-Паксон, стаціонарний стан

Client Acceptor Learner | | | | | | X----->|->|->| | | Accept!(N,I,V) | X<>X<>X------>|->| Accepted(N,I,V) - BROADCAST |<-------------------X--X Response(V) | | | | | |

Сценарій відмови однаковий для обох протоколів. Кожен Учень чекає отримання F + 1 однакових повідомлень від різних Приймачів. Якщо цього не відбудеться, самі Приймачі також будуть про це знати, і правильні Приймачі повторно транслюватимуть узгоджене значення:

Потік повідомлень: Швидкий візантійський Мульти-Паксон, невдача

Client Acceptor Learner | | |  ! | |  !! One Acceptor is faulty X----->|->|->! | | Accept!(N,I,V) | X<>X<>X------>|->| Accepted(N,I,{V,W}) - BROADCAST | | |  ! | |  !! Learners receive 2 different commands | | |  ! | |  !! Correct Acceptors notice error and choose | X<>X<>X------>|->| Accepted(N,I,V) - BROADCAST |<-------------------X--X Response(V) | | |  ! | |

Адаптація Паксос до мереж RDMA

З появою дуже швидких надійних мереж центрів обробки даних, які підтримують віддалений DMA (RDMA), виникла значна зацікавленість в оптимізації Паксос для використання апаратного розвантаження, в якому мережева карта інтерфейсу та мережеві маршрутизатори забезпечують надійність та контроль перевантаженості мережевого рівня, звільняючи хост-процесор для інших завдань. Бібліотека Derecho C ++ Paxos [ 14 січня 2022 у Wayback Machine.] — це реалізація Паксос з відкритим кодом, яка досліджує цей варіант .

Derecho пропонує як класичний Paxos, що має довговічність даних у послідовності повного відключення / перезавантаження, так і вертикальний Paxos (атомний передавач) для реплікації в пам'яті та синхронізації стану та машини. Протоколи Paxos, застосовані Derecho, потребували адаптації для максимізації асинхронного потоку даних та усунення інших джерел затримки на критичному шляху лідера. Таким чином, це дозволяє Derecho підтримувати повну двонаправлену швидкість передачі даних RDMA. На відміну від цього, хоча традиційні протоколи Paxos можуть бути переміщені до мережі RDMA шляхом простого відображення операцій надсилання повідомлень у нативній операції RDMA, але це залишає затримки в зворотному напрямку на критичному шляху. У високошвидкісних мережах RDMA навіть невеликі затримки можуть бути досить великими, щоб запобігти використанню повної потенційної пропускної здатності.

Використання Паксос

Google використовує алгоритм Паксос у своїй службі розподіленого блокування Chubby, щоб підтримувати послідовність реплік у разі відмови. Chubby використовується Bigtable, який зараз випускається в Google Analytics та інших продуктах.
Google Spanner та Megastore використовують алгоритм Паксос.
Служба реплікації OpenReplica [ 9 серпня 2018 у Wayback Machine.] використовує Паксос для підтримання копій для системи відкритого доступу, яка дозволяє користувачам створювати об'єкти, стійкі до відмов. Це забезпечує високу ефективність за рахунок одночасних раундів та гнучкість завдяки динамічним змінам членства.
IBM нібито використовує алгоритм Паксос в своєму продукті IBM SAN Volume Controller для реалізації віртуальної машини загального призначення, стійкої до відмов, що використовується для запуску конфігураційних та керуючих компонентів служб віртуалізації зберігання, пропонованих кластером. (Оригінальний дослідницький документ MIT & IBM [ 21 травня 2020 у Wayback Machine.])
Microsoft використовує Paxos в службі керування кластерами автопілотів [ 7 травня 2016 у Wayback Machine.] від компанії Bing та в кластеризації відключення Windows Server.
WANdisco впровадив Paxos в рамках своєї технології активної реплікації DConE.
XtreemFS використовує алгоритм узгодження оренди на основі Paxos для стійкої до відмов та послідовної реплікації файлових даних та метаданих.
Heroku використовує Doozerd, [ 16 жовтня 2019 у Wayback Machine.] який реалізує Paxos для послідовного розподіленого сховища даних.
Ceph використовує Paxos як частину процесів монітора, щоб узгодити, які екранні екрани знаходяться в кластері.
Розподілена база даних Slustrix Clustrix використовує Paxos для розподіленої роздільної здатності транзакцій [ 6 грудня 2019 у Wayback Machine.] .
База даних графіків HA Neo4j реалізує Paxos, замінюючи Apache ZooKeeper з версії 1.9
База даних Apache Cassandra NoSQL використовує лише Paxos для функції легкої ваги [ 20 квітня 2019 у Wayback Machine.]
Amazon Elastic Container Services використовує Paxos для підтримки послідовного перегляду стану кластерів [ 4 червня 2020 у Wayback Machine.]

Примітки

Pease, Marshall; Shostak, Robert; Lamport, Leslie (April 1980). «Reaching Agreement in the Presence of Faults» [ 16 серпня 2007 у Wayback Machine.]. . 27 (2). Retrieved 2007-02-02.
Lamport, Leslie (July 1978). «Time, Clocks and the Ordering of Events in a Distributed System» [ 16 серпня 2007 у Wayback Machine.]. Communications of the ACM. 21 (7): 558—565. doi:10.1145/359545.359563. Retrieved 2007-02-02.
. Архів оригіналу за 5 серпня 2011. Процитовано 21 листопада 2019.
Lamport, Leslie (May 1998). «The Part-Time Parliament» [ 16 серпня 2007 у Wayback Machine.]. ACM Transactions on Computer Systems. 16 (2): 133—169. doi:10.1145/279227.279229. Retrieved 2007-02-02.
Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (April 1988). «Consensus in the Presence of Partial Synchrony» [ 18 червня 2019 у Wayback Machine.] (PDF). Journal of the ACM. 35 (2): 288—323. CiteSeerX 10.1.1.13.3423. doi:10.1145/42282.42283.
Oki, Brian; Liskov, Barbara (1988). «Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems». PODC '88: Proceedings of the seventh annual . pp. 8–17. doi:10.1145/62546.62549.
Birman, Kenneth; Joseph, Thomas (February 1987). «Reliable Communication in the Presence of Failures». ACM Transactions on Computer Systems: 47–76.
Chandra, Tushar; Griesemer, Robert; Redstone, Joshua (2007). Paxos Made Live — An Engineering Perspective [ 21 липня 2016 у Wayback Machine.]. PODC '07: 26th ACM Symposium on Principles of Distributed Computing. pp. 398–407. doi:10.1145/1281100.1281103.
Lamport, Leslie (2001). Paxos Made Simple [ 5 серпня 2011 у Wayback Machine.] ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58.
Lamport, Leslie (2005). «Generalized Consensus and Paxos» [ 16 серпня 2007 у Wayback Machine.]. Cite journal requires |journal= ()
Pierre, Sutra; Marc, Shapiro (2011). «Fast Genuine Generalized Consensus» [ 12 грудня 2014 у Wayback Machine.] (PDF). SRDS'11: 30th IEEE Symposium on Reliable Distributed Systems.
Lamport, Leslie; Malkhi, Dahlia; Zhou, Lidong (2009). Vertical Paxos and Primary-backup Replication. PODC '09. New York, NY, USA: ACM. с. 312—313. doi:10.1145/1582716.1582783. ISBN . {{}}: Проігноровано |journal= ()
Lamport, Leslie; Shostak, Robert; Pease, Marshall (July 1982). «The Byzantine Generals Problem» [ 16 серпня 2007 у Wayback Machine.]. ACM Transactions on Programming Languages and Systems. 4 (3): 382—401. CiteSeerX 10.1.1.64.2312. doi:10.1145/357172.357176. Retrieved 2007-02-02.
Castro, Miguel; Liskov, Barbara (February 1999). (PDF). Proceedings of the Third Symposium on Operating Systems Design and Implementation: 173—186. Архів оригіналу (PDF) за 4 березня 2018. Процитовано 5 березня 2018.
Martin, Jean-Philippe; Alvisi, Lorenzo (July 2006). (PDF). IEEE Transactions on Dependable and Secure Computing. 3 (3): 202—215. doi:10.1109/TDSC.2006.35. Архів оригіналу (PDF) за 18 січня 2021. Процитовано 5 березня 2018.
Jha, Sagar; Behrens, Jonathan; Gkountouvas, Theo; Milano, Matthew; Song, Weijia; Tremel, Edward; van Renesse, Robbert; Zink, Sydney; Birman, Ken (April 2019). «Derecho: Fast State Machine Replication for Cloud Services». . 36 (2). doi:10.1145/3302258.
Aahlad et al.(2011). «The Distributed Coordination Engine (DConE)» [ 15 квітня 2016 у Wayback Machine.]. WANdisco white paper.
Kolbeck, Björn; Högqvist, Mikael; Stender, Jan; Hupfeld, Felix (2011). «Flease — Lease Coordination without a Lock Server» [ 5 вересня 2021 у Wayback Machine.]. 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2011).

[agree-1] Pease, Marshall; Shostak, Robert; Lamport, Leslie (April 1980). «Reaching Agreement in the Presence of Faults» [ 16 серпня 2007 у Wayback Machine.]. . 27 (2). Retrieved 2007-02-02.

[clocks-2] Lamport, Leslie (July 1978). «Time, Clocks and the Ordering of Events in a Distributed System» [ 16 серпня 2007 у Wayback Machine.]. Communications of the ACM. 21 (7): 558—565. doi:10.1145/359545.359563. Retrieved 2007-02-02.

[Lamport-3] . Архів оригіналу за 5 серпня 2011. Процитовано 21 листопада 2019.

[paxos-4] Lamport, Leslie (May 1998). «The Part-Time Parliament» [ 16 серпня 2007 у Wayback Machine.]. ACM Transactions on Computer Systems. 16 (2): 133—169. doi:10.1145/279227.279229. Retrieved 2007-02-02.

[LDS88-5] Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (April 1988). «Consensus in the Presence of Partial Synchrony» [ 18 червня 2019 у Wayback Machine.] (PDF). Journal of the ACM. 35 (2): 288—323. CiteSeerX 10.1.1.13.3423. doi:10.1145/42282.42283.

[vr-6] Oki, Brian; Liskov, Barbara (1988). «Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems». PODC '88: Proceedings of the seventh annual . pp. 8–17. doi:10.1145/62546.62549.

[BJ87-7] Birman, Kenneth; Joseph, Thomas (February 1987). «Reliable Communication in the Presence of Failures». ACM Transactions on Computer Systems: 47–76.

[live-8] Chandra, Tushar; Griesemer, Robert; Redstone, Joshua (2007). Paxos Made Live — An Engineering Perspective [ 21 липня 2016 у Wayback Machine.]. PODC '07: 26th ACM Symposium on Principles of Distributed Computing. pp. 398–407. doi:10.1145/1281100.1281103.

[paxos-simple-9] Lamport, Leslie (2001). Paxos Made Simple [ 5 серпня 2011 у Wayback Machine.] ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58.

[general-10] Lamport, Leslie (2005). «Generalized Consensus and Paxos» [ 16 серпня 2007 у Wayback Machine.]. Cite journal requires |journal= ()

[fggc-11] Pierre, Sutra; Marc, Shapiro (2011). «Fast Genuine Generalized Consensus» [ 12 грудня 2014 у Wayback Machine.] (PDF). SRDS'11: 30th IEEE Symposium on Reliable Distributed Systems.

[12] Lamport, Leslie; Malkhi, Dahlia; Zhou, Lidong (2009). Vertical Paxos and Primary-backup Replication. PODC '09. New York, NY, USA: ACM. с. 312—313. doi:10.1145/1582716.1582783. ISBN . {{}}: Проігноровано |journal= ()

[byzgen-13] Lamport, Leslie; Shostak, Robert; Pease, Marshall (July 1982). «The Byzantine Generals Problem» [ 16 серпня 2007 у Wayback Machine.]. ACM Transactions on Programming Languages and Systems. 4 (3): 382—401. CiteSeerX 10.1.1.64.2312. doi:10.1145/357172.357176. Retrieved 2007-02-02.

[14] Castro, Miguel; Liskov, Barbara (February 1999). (PDF). Proceedings of the Third Symposium on Operating Systems Design and Implementation: 173—186. Архів оригіналу (PDF) за 4 березня 2018. Процитовано 5 березня 2018.

[15] Martin, Jean-Philippe; Alvisi, Lorenzo (July 2006). (PDF). IEEE Transactions on Dependable and Secure Computing. 3 (3): 202—215. doi:10.1109/TDSC.2006.35. Архів оригіналу (PDF) за 18 січня 2021. Процитовано 5 березня 2018.

[Derecho-16] Jha, Sagar; Behrens, Jonathan; Gkountouvas, Theo; Milano, Matthew; Song, Weijia; Tremel, Edward; van Renesse, Robbert; Zink, Sydney; Birman, Ken (April 2019). «Derecho: Fast State Machine Replication for Cloud Services». . 36 (2). doi:10.1145/3302258.

[WANdisco-17] Aahlad et al.(2011). «The Distributed Coordination Engine (DConE)» [ 15 квітня 2016 у Wayback Machine.]. WANdisco white paper.

[flease-18] Kolbeck, Björn; Högqvist, Mikael; Stender, Jan; Hupfeld, Felix (2011). «Flease — Lease Coordination without a Lock Server» [ 5 вересня 2021 у Wayback Machine.]. 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2011).