Паксос () — це набір протоколів, призначених для консенсусу в мережі ненадійних процесорів. Консенсус — процес отримання узгодженого результату групою учасників. Вирішити цю проблему складно, якщо в учасників або в засобах їх комунікації виникають помилки.Pease, Marshall; Shostak, Robert; Lamport, Leslie (April 1980). «Reaching Agreement in the Presence of Faults» . Journal of the Association for Computing Machinery. 27 (2). Retrieved 2007-02-02.

Протоколи рішення задачі консенсусу є базовим елементом тиражованого автомата (автоматного підходу) у розподілених обчисленнях, що запропонував Леслі ЛампортLamport, Leslie (July 1978). «Time, Clocks and the Ordering of Events in a Distributed System» . Communications of the ACM. 21 (7): 558—565. doi:10.1145/359545.359563. Retrieved 2007-02-02. і дослідив далі Ф. Шнайдер.

Протокол Паксос був вперше опублікований у 1989 році та був названий на честь вигаданої законодавчої системи, що застосовувалася на острові Паксос у Греції. Пізніше був опублікований в науковій літературі в 1998 році.Lamport, Leslie (May 1998). «The Part-Time Parliament» . ACM Transactions on Computer Systems. 16 (2): 133—169. doi:10.1145/279227.279229. Retrieved 2007-02-02.

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

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

Історія У 1988 р. Лінч, Дрюк і Стокмейер продемонструвалиDwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (April 1988). «Consensus in the Presence of Partial Synchrony» (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 ACM Symposium on Principles of Distributed Computing. pp. 8–17. doi:10.1145/62546.62549. Паксос запропонував особливо елегантний формалізм і включив одне з найбільш ранніх доказів безпеки для відмовостійкого протоколу розподіленого консенсусу.

Реконфігуровані машини мають міцні зв'язки з попередньою роботою над протоколами багатоадресної групи, які підтримують членство динамічної групи, наприклад роботи Бірмана 1985 та 1987 року практичного синхронного gbcastBirman, Kenneth; Joseph, Thomas (February 1987). «Reliable Communication in the Presence of Failures». ACM Transactions on Computer Systems: 47–76. протоколу.

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

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

Процесори

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

Мережа

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

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

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

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

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

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

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

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

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

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

Типове розгортання У більшості випадків кожен процес, що бере участь виконує три ролі; Заявника, Приймача та Учня.Chandra, Tushar; Griesemer, Robert; Redstone, Joshua (2007). Paxos Made Live — An Engineering Perspective . PODC '07: 26th ACM Symposium on Principles of Distributed Computing. pp. 398–407. doi:10.1145/1281100.1281103. ISBN 9781595936165 Це значно знижує складність повідомлення, не жервуючи правильністю.

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

Базовий Паксос Це найбазовіший протокол із сім'ї Паксос. Кожен «примірник» базового протоколу Паксос визначає одне вихідне значення. Протокол триває декілька раундів. Вдалий раунд має 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), про яке повідомили Приймача. Якщо жоден з Приймачів не прийняв пропозицію до цього моменту, то Замовник може вибрати значення, яке він спочатку хотів запропонувати, скажімо xLamport, Leslie (2001). Paxos Made Simple ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58. .

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

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