Алгоритм Паксос

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

Історія[ред. | ред. код]

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

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

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

Припущення[ред. | ред. код]

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

Процесори[ред. | ред. код]

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

Мережа[ред. | ред. код]

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

Кількість процесорів[ред. | ред. код]

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

Ролі[ред. | ред. код]

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

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

Кворуми[ред. | ред. код]

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

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

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

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

Властивості безпеки та живості[ред. | ред. код]

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

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

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

Типове розгортання[ред. | ред. код]

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

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

Базовий Паксос[ред. | ред. код]

Це найбазовіший протокол із сім'ї Паксос. Кожен «примірник» базового протоколу Паксос визначає одне вихідне значення. Протокол триває декілька раундів. Вдалий раунд має 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[9] .
Заявник надсилає повідомлення 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)
 |  |         |  |  |  |

Узагальнений Паксос[ред. | ред. код]

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

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

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

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>
 |  |         |      |  |  |         |  |

Продуктивність[ред. | ред. код]

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

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

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

Візантійський Паксос[ред. | ред. код]

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

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

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

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)
   |         |          |  |  |       |  |

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

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

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

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.] — це реалізація Паксос з відкритим кодом, яка досліджує цей варіант[16] .

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

Використання Паксос[ред. | ред. код]

Примітки[ред. | ред. код]

  1. ↑ Pease, Marshall; Shostak, Robert; Lamport, Leslie (April 1980). «Reaching Agreement in the Presence of Faults» [Архівовано 16 серпня 2007 у Wayback Machine.]. Journal of the Association for Computing Machinery. 27 (2). Retrieved 2007-02-02.
  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.
  3. ↑ Leslie Lamport's history of the paper. Архів оригіналу за 5 серпня 2011. Процитовано 21 листопада 2019.
  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.
  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.
  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 ACM Symposium on Principles of Distributed Computing. pp. 8–17. doi:10.1145/62546.62549.
  7. ↑ Birman, Kenneth; Joseph, Thomas (February 1987). «Reliable Communication in the Presence of Failures». ACM Transactions on Computer Systems: 47–76.
  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. ISBN 9781595936165
  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.
  10. ↑ Lamport, Leslie (2005). «Generalized Consensus and Paxos» [Архівовано 16 серпня 2007 у Wayback Machine.]. Cite journal requires |journal= (help)
  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 9781605583969. {{cite book}}: Проігноровано |journal= (довідка)
  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). Practical Byzantine Fault Tolerance (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). Fast Byzantine Consensus (PDF). IEEE Transactions on Dependable and Secure Computing. 3 (3): 202—215. doi:10.1109/TDSC.2006.35. Архів оригіналу (PDF) за 18 січня 2021. Процитовано 5 березня 2018.
  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». ACM Transactions on Computer Systems. 36 (2). doi:10.1145/3302258.
  17. ↑ Aahlad et al.(2011). «The Distributed Coordination Engine (DConE)» [Архівовано 15 квітня 2016 у Wayback Machine.]. WANdisco white paper.
  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).
Отримано з https://uk.wikipedia.org/w/index.php?title=Алгоритм_Паксос&oldid=42350968