Консенсус у розподілених системах

Тому завдання досягнення консенсусу – завдання отримання узгодженого значення групою учасників ситуації, коли можливі відмови окремих учасників, надання ними некоректної інформації, спотворення переданих значень середовищем передачі. Загалом сценарії нештатного функціонування компонентів розподілених систем можна розділити на два класи:

Повна відмова компонента. Характеризується цей клас проблем тим, що така відмова призводить до недоступності одного з компонентів розподіленої системи (або сегментації мережі у разі відмови комутатора). До цього класу проблем належать: відмова сервера, відмова системи зберігання даних, відмова комутатора, відмова операційної системи, відмова програми;
Візантійська помилка. Характеризується тим, що вузол системи продовжує функціонувати, але може повертати некоректну інформацію. Припустимо, при використанні оперативної пам'яті без ECC може спричинити зчитування некоректних даних з пам'яті, помилки мережного обладнання можуть призводити до пошкодження пакетів і т.п.

Помилки другого класу набагато складніші у виявленні та виправленні. В цілому, Леслі Лемпортом було доведено, що для виправлення Візантійської проблеми вNвузлах розподілена система повинна складатися як мінімум з3N+1вузлів і має реалізовувати спеціальний алгоритм консенсусу. Відмовостійкість на цьому рівні потрібна здебільшого в системах, критичність функціонування яких вкрай висока (наприклад, завдання космічної промисловості).

У кластерних обчисленнях під стійкістю до відмови зазвичай розуміють стійкість системи до повних відмов компонент. Для досягнення консенсусу в таких системах застосовується алгоритм Paxos.Алгоритм було запропоновано Леслі Лемпортом у 90-х роках минулого століття та названо на честь грецького острова Паксос із вигаданою системою організації роботи парламенту. Для досягнення консенсусу даному алгоритму необхідно, щоб у системі з2N+1вузлів функціонували як мінімумN+1вузла, ціN+1вузли називаються «кворум»

Суть алгоритму у взаємодії агентів із наступними ролями:

Client– клієнт розподіленої системи, який може надіслати запит та отримати на нього відповідь
Proposer– компонент розподіленої системи, який відповідає за організацію процесу голосування
Acceptor– компонент розподіленої системи, що має право голосу за прийняття чи відхилення конкретної пропозиції від Proposer
Learner– компонент системи, який запам'ятовує прийняте рішення

Базовий алгоритм Paxos складається з наступних етапів:

1а. Prepare(«пропозиція»). На цій фазі proposer генерує "пропозицію" з порядковим номеромNі відправляє її всім acceptor. Для кожної з наступних «пропозицій» номерNмає бути більшим за обраний раніше

1b. Promise («обіцяння»). Кожен acceptor отримує «пропозицію» з порядковим номеромNі значеннямV. Якщо номер «пропозиції» більший за всі прийняті раніше даним acceptor, він зобов'язаний відповісти на це повідомлення «обіцянням» не приймати більше «пропозицій» з порядковим номером меншеN. Якщо даний acceptor вже приймав якусь «пропозицію», він повинен повернути номерNiцієї «пропозиції» і прийняте значенняVi, в іншому випадку він повертає порожнє значення

2a. Accept!(«прийняти»). Якщо proposerотримав "обіцянки" від кворуму acceptor, він вважає запит готовим до подальшої обробки. У випадку, якщо з «обіцяннями» від acceptor прийшли також значенняNiіVi, proposer вибираєVдорівнює значеннюVi«обіцянки» з максимальнимNi. Потім proposer відправляє запит «прийняти» всім acceptor, який містить значенняNіV

2b. Accepted («прийнято»). Коли acceptor отримує повідомлення "прийняти" зі значеннямиNіV, він приймає його тільки в тому випадку, якщо раніше він не " обіцяв» приймати пропозиції з номерами строго більшеN. Інакше він набуває значення та відповідає повідомленням «прийнято» всім learner

Завдання learner проста – отримати повідомлення «прийнято» зі значеннямVта запам'ятати його

Приклад функціонування алгоритму:

Що ж відбувається, якщо якийсь із компонентів розподіленої системи відмовляє?

Відмова Acceptor: Оскільки у системі 3 вузла ассеptor, допускається відмова однієї з них, оскільки кворум у разі дорівнює двом

У разі відмови proposer система повинна вибрати нового proposer, зазвичай це здійснюється шляхом голосування після закінчення тайм-ауту очікування повернення старого proposer. У разі, якщо після вибору нового proposer старий повертається до життя, між лідерами може виникнути конфлікт, який може призвести до зациклювання системи: Для запобігання цьому в практичній реалізації алгоритму кожен proposer має порядковий номер і при виборі нового proposer цей номер збільшується на одиницю. Ніхто з acceptor не приймає повідомлення від старого proposer.

Як приклад реалізації наведу трохи модифікованийpython код одного з репозиторіїв github:

А у нас тут можна отримати грант на тестовий період Яндекс.Хмари. Варто лише у полі «секретний пароль» запровадити «Хабр»