Отже, уявимо. У кімнаті замкнено 5 котів, і щоб піти розбудити господаря, їм необхідно всім разом домовитися між собою про це, адже двері вони можуть відчинити тільки вп'ятьох навалившись на неї. Якщо один із котів – кіт Шредінгера, а решта котів не знає про його вирішення, виникає питання: «Як вони можуть це зробити?»
У цій статті я простою мовою розповім вам про теоретичну складову світу розподілених систем та принципи їхньої роботи. А також поверхово розгляну головну ідею, що лежить в основі Paxos'а.
Коли розробники користуються хмарними інфраструктурами, різними базами даних, працюють у кластерах з великої кількості вузлів, вони впевнені, що ці дані будуть цілісними, збереженими і завжди доступними. Але звідки гарантії?
По суті, гарантії, які ми маємо – це гарантії постачальника. Вони описані в документації приблизно так: «Цей сервіс досить надійний, у нього є заданий SLA, не турбуйтеся, все буде розподілено працювати, як ви і очікуєте».
Ми схильні вірити у краще, адже розумні дядьки з великих компаній запевнили нас, що все буде гаразд. Ми не питаємо: а чому, власне, це взагалі може працювати? Чи є якесь формальне обґрунтування коректності роботи таких систем?
Нещодавно я їздив на і дуже надихнувся на цю тему. Лекції у школі більше нагадували заняття з математичного аналізу, ніж пов'язане з комп'ютерними системами. Але саме так свого часу і доводилися найважливіші алгоритми, якими ми користуємося щодня, не підозрюючи.
У більшості сучасних розподілених систем використовується алгоритм консенсусу Paxos та його різні модифікації. Найкрутіше, що обгрунтованість і, в принципі, можливість існування цього алгоритму може бути доведена просто за допомогою ручки і паперу. При цьому на практиці алгоритм застосовується у великих системах, що працюють на величезній кількості вузлів у хмарах.
Лайтова ілюстрація того, про що йтиметься далі: завдання двох генералівДавайте для розминки розберемо .
У нас є дві армії – руда та біла. Білі війська базуються в обложеному місті. Руді війська на чолі з генералами А1 і А2 розташовуються з обох боків міста. Завдання рудих – напасти на біле місто та перемогти. Проте військо кожного рудого генерала окремо менше за військо білих.
Умови перемоги для рудих: обидва генерали повинні напасти одночасно, щоб мати чисельну перевагу над білими. І тому генералам А1 і А2 треба домовитися друг з одним. Якщо кожен нападатиме окремо, руді програють.
Щоб домовитися, генерали А1 і А2 можуть посилати один одного гінців через територію білого міста. Гонець може успішно дістатися союзного генерала чи може бути перехопленим противником. Питання: чи є така послідовність комунікацій між рудими генералами (послідовність відправлення гінців від А1 до А2 і навпаки від А2 до А1), коли вони гарантовано домовляться про напад на годину Х. Тут, під гарантіями розуміється, що обидва генерали матимуть однозначне підтвердження , Що союзник (інший генерал) точно атакує у призначений час X.
Припустимо, що А1 посилає гінця до А2 з посланням: «Давай нападемо сьогодні опівночі!». Генерал А1 неспроможна напасти без підтвердження від генерала А2. Якщо гонець від А1 дійшов, генерал А2 посилає підтвердження з повідомленням: «Так, давай сьогодні завалимо білих». Але тепер генерал А2 не знає, дійшов його гонець чи ні, він не має гарантій, чи буде напад одночасним. Тепер уже генералу А2 знову потрібне підтвердження.
Якщо розписувати їхню комунікацію далі, з'ясується таке: хоч би скільки було циклів обміну повідомленнями, немає способу гарантовано повідомити обох генералів про те, що їх повідомлення отримані (за умови, що будь-який з гінців може бути перехоплений).
Завдання двох генералів – це чудова ілюстрація дуже простої розподіленої системи, де є два вузли з ненадійною комунікацією. Отже, у нас немає 100% гарантії того, що вони синхронізуються. Про подібні проблеми лише у більшому масштабі далі у статті.
Вводимо поняття розподілених систем
Розподілена система – це група комп'ютерів (далі називатимемо їх вузлами), які можуть обмінюватися повідомленнями. Кожен окремий вузол – це окрема автономна сутність. Вузол може самостійно обробляти завдання, але щоб взаємодіяти з іншими вузлами, йому потрібно надсилати та приймати повідомлення.
Як конкретно реалізовані повідомлення, які протоколи використовують – це нас не цікавить у даному контексті. Важливо, що вузли розподіленої системи можуть обмінюватися між собою даними шляхом надсилання повідомлень.
Саме визначення виглядає не дуже складним, але треба враховувати, що розподілена система має ряд атрибутів, які будуть важливими для нас.
Атрибути розподілених систем
- Паралелізм - Можливість виникнення одночасних або конкурентних подій у системі. Більше того, ми вважатимемо, що події, що відбулися на двох різних вузлах, потенційно конкурентні доти, доки ми не маємо точного порядку виникнення цих подій. А зазвичай у нас його немає.
- Відсутність глобального годинника. У нас немає чіткого порядку подій через відсутність глобальних годинників. У звичайному світі людей ми звикли до того, що ми маємо годинник і час абсолютно. Все змінюється, коли йдеться про розподілені системи. Навіть у надточного атомного годинника є дрифт, і можливі ситуації, коли ми не можемо сказати, яка з двох подій сталася раніше. Тому покладатися на якийсь час ми теж не можемо.
- Незалежна відмова вузлів системи. Є ще одна проблема: щось може піти не так просто, тому що наші вузли не вічні. Може вийти з ладу жорсткий диск, перезавантажитись віртуалка в хмарі, може моргнути мережу та повідомлення загубляться. Більш того, можливі ситуації, коли вузли працюють, але працюють проти системи. Останній клас проблем навіть отримав окрему назву: проблема . Найпопулярніший приклад розподіленої системи з такою проблемою – це Blockchain. Але сьогодні ми не розглядатимемо цей особливий клас проблем. Нас цікавитимуть ситуації, в яких просто один або кілька вузлів можуть виходити з ладу.
- Моделі комунікації (моделі обміну повідомленнями) між вузлами. Ми вже з'ясували, що вузли спілкуються шляхом обміну повідомленнями. Є дві відомі моделі обміну повідомленнями: синхронна та асинхронна.
Моделі комунікації між вузлами у розподілених системах
Синхронна модель – ми точно знаємо, що є кінцева відома дельта часу, яку повідомлення гарантовано доходить від одного вузла до іншого. Якщо цей час вийшов, а повідомлення не настав, ми можемо сміливо говорити, що вузол вийшов з ладу. У такій моделі ми маємо передбачуваний час очікування.
Асинхронна модель - В асинхронних моделях ми вважаємо, що час очікування звичайно, але не існує такої дельти часу, після якої можна гарантувати, що вузол вийшов з ладу. Тобто. час очікування повідомлення від вузла може бути як завгодно довгим. Це важливе визначення і ми поговоримо про це далі.
Поняття консенсусу у розподілених системах
Перш ніж формально визначити поняття консенсусу, розглянемо приклад ситуації, коли він нам потрібен, а саме – Реплікація кінцевого автомата.
Ми маємо деякий розподілений лог. Нам хотілося б, щоб він був консистентним і містив ідентичні дані на всіх вузлах розподіленої системи. Коли якийсь із вузлів дізнається нове значення, яке він збирається записати в лог, його завданням стає запропонувати це значення решті вузлів, щоб лог оновився на всіх вузлах, і система перейшла в новий консистентний стан. При цьому важливо, щоб вузли домовилися між собою: всі вузли погодилися, що запропоноване нове значення коректно, всі вузли це значення набули, і тільки в цьому випадку всі можуть записати в лог нове значення.
Іншими словами: ніхто з вузлів не заперечив, що має більш актуальну інформацію, а запропоноване значення неправильне. Домовленість між вузлами та згода про єдине правильне прийняте значення і є консенсус у розподіленій системі. Далі ми говоритимемо про алгоритми, які дозволяють розподіленій системі гарантовано досягати консенсусу.
Більш формально ми можемо визначити алгоритм досягнення консенсусу (або просто алгоритм консенсусу) як деяку функцію, яка переводить розподілену систему зі стану А в стан Б. Причому цей стан прийнято всіма вузлами, і всі вузли можуть його підтвердити. Як з'ясовується, це завдання зовсім не таке тривіальне, як здається на перший погляд.
Властивості алгоритму консенсусу
Алгоритм консенсусу повинен мати три властивості, щоб система продовжувала існувати і мала якийсь прогрес у переході зі стану в стан:
- Угода - всі коректно працюючі вузли повинні прийняти одне й те саме значення (у статтях ця властивість також зустрічається як safety property). Всі вузли, які зараз функціонують (не вийшли з ладу і не втратили зв'язок з рештою) повинні дійти згоди та прийняти якесь фінальне загальне значення.
Тут важливо розуміти, що вузли в розподіленій системі, що розглядається нами, хочуть домовитися. Тобто ми зараз говоримо про системи, які просто можуть щось відмовити (наприклад, відмовити якийсь вузол), але в цій системі точно немає вузлів, які навмисно працюють проти інших (завдання візантійських генералів). За рахунок цієї якості система залишається консистентною.
- Цілісність — якщо всі вузли, що коректно працюють, пропонують одне і те ж значення v, отже кожен коректно працюючий вузол повинен прийняти це значення v.
- Припинення – всі коректно працюючі вузли зрештою приймуть певне значення (liveness property), що дозволяє алгоритму мати прогрес у системі. Кожен окремий коректно працюючий вузол повинен рано чи пізно прийняти фінальне значення і підтвердити це: «Для мене – це значення істинно, я згоден з усією системою».
Приклад роботи алгоритму консенсусу
Поки що властивості алгоритму можуть бути не зовсім зрозумілі. Тому проілюструємо на прикладі, які стадії проходить найпростіший алгоритм консенсусу в системі з синхронною моделлю обміну повідомленнями, у якої всі вузли функціонують як належить, повідомлення не губляться і нічого не ламається (невже таке і справді трапляється?).
- Все починається з пропозиції руки та серця (Propose). Припустимо, що до вузла під назвою "Вузол 1" підключився клієнт і почав транзакцію, передавши вузлу нове значення - О. З цього моменту "Вузол 1" ми називатимемо пропозиція. Як proposer «Вузол 1» тепер повинен сповістити всю систему про те, що він має свіжі дані, і він розсилає решті вузлів повідомлення: «Дивіться! Мені прийшло значення "О", і я хочу його записати! Прошу підтвердити, що ви теж запишете «О» у свій лог».
- Наступна стадія – голосування за запропоноване значення (Voting). Навіщо вона потрібна? Може так статися, що іншим вузлам надійшла свіжіша інформація, і вони мають дані щодо цієї ж транзакції.
Коли вузол «Вузол 1» посилає свій пропоуз, решта вузлів перевіряє у своїх логах дані щодо цієї події. Якщо жодних протиріч немає, вузли оголошують: «Так, я не маю інших даних щодо цієї події. Значення «О» – це найсвіжіша інформація, на яку ми заслужили».У будь-якому іншому випадку вузли можуть відповісти «Вузлу 1»: «Послухай! У мене є свіжіші дані щодо цієї транзакції. Не «О», а дещо краще».
На стадії голосування вузли приходять до рішення: або всі приймають одне значення, або хтось із них голосує проти, позначивши, що він має свіжіші дані.
- Якщо раунд голосування пройшов успішно і всі були «за», то система переходить у нову стадію – прийняття значення (Accept). "Вузол 1" збирає всі відповіді інших вузлів і повідомляє: "Всі погодилися зі значенням "О"! Тепер я офіційно заявляю, що "О" - наше нове значення, єдине для всіх! Запишіть собі у книжечку, не забудьте. Запишіть у свій лог!»
- Інші вузли надсилають підтвердження (Accepted), що вони записали собі значення «О», нічого нового за цей час вчинити не встигло (свого роду двофазний коміт). Після цієї знаменної події ми вважаємо, що розподілена транзакція здійснилася.
Таким чином, алгоритм консенсусу в простому випадку складається з чотирьох кроків: propose, голосування (voting), прийняття (accept), підтвердження прийняття (accepted).
Якщо на якомусь кроці ми не змогли досягти згоди, то алгоритм запускається заново, з урахуванням інформації, яку нададуть вузли, які відмовилися підтверджувати запропоноване значення.
Алгоритм консенсусу в асинхронній системі
До цього все було гладко, адже йшлося про синхронну модель обміну повідомленнями. Але ми знаємо, що в сучасному світі ми все звикли робити асинхронно. Як же аналогічний алгоритм працює в системі з асинхронною моделлю обміну повідомленнями, де ми вважаємо, що час очікування відповіді від вузла може бути як завгодно довгим (до речі, вихід вузла з ладу, можна також розглядати як приклад, коли вузол може відповідати як завгодно довго ).
Тепер, коли ми знаємо, як у принципі працює алгоритм консенсусу, питання до тих допитливих читачів, хто дійшов до цього місця: скільки вузлів у системі з N вузлів з асинхронною моделлю повідомлень може вийти з ладу, щоб система, як і раніше, могла досягати консенсусу?
Правильна відповідь та обґрунтування за спойлером.Правильну відповідь: 0. Якщо хоча б один вузол в асинхронній системі виходить із ладу, система не зможе досягти консенсусу. Це твердження доведено у відомій у певних колах теоремі FLP (1985, Fischer, Lynch, Paterson, посилання на оригінал наприкінці статті): "Неможливість досягнення розподіленого консенсусу при виході з ладу хоча б одного вузла".
Хлопці, тоді у нас проблема, ми звикли, що в нас все асинхронно. А тут таке. Як далі жити?
Ми зараз говорили про теорію, математику. Що означає «консенсус не може бути досягнутий», перекладаючи з математичної мови на нашу інженерну? Це означає, що «не завжди можна досягти», тобто. існує такий кейс, у якому консенсус не досягнутий. А що ж це за нагода?
Це якраз порушення liveness property, описане вище. У нас немає спільної згоди, і система не може мати прогресу (не може завершитися за кінцевий час) у випадку, коли ми не маємо відповіді від усіх вузлів. Тому що в асинхронній системі ми не маємо передбачуваного часу відповіді, і ми не можемо знати, чи вийшов вузол з ладу, чи просто довго відповідає.
Але на практиці ми можемо знайти рішення. Нехай наш алгоритм може працювати довго у разі відмов (потенційно може працювати нескінченно). Але в більшості ситуацій, коли більшість вузлів коректно функціонують, ми матимемо прогрес у системі.
Насправді ми маємо справу з частково синхронними моделями комунікацій. Часткова синхронність розуміється так: у загальному випадку ми маємо асинхронну модель, але формально вводиться певне поняття «global stabilization time» певного моменту часу.
Цей момент часу може не наступати скільки завгодно довго, але одного разу він має настати. Продзвенить віртуальний будильник, і з цієї миті ми можемо передбачити дельту часу, яку повідомлення дійдуть. З цього моменту система з асинхронної перетворюється на синхронну. На практиці ми маємо справу саме із такими системами.
Алгоритм Paxos вирішує проблеми консенсусу
– це сімейство алгоритмів, які вирішують проблему консенсусу для частково синхронних систем, за умови, що якісь вузли можуть виходити з ладу. Автором Paxos'а є . Він запропонував формальний доказ існування та коректності алгоритму у 1989 році.
Але доказ виявився аж ніяк нетривіальним. Перша публікація була випущена лише у 1998 році (33 сторінки) з описом алгоритму. Як виявилося, вона була вкрай складною для розуміння, і у 2001 році було опубліковано пояснення до статті, що зайняло 14 сторінок. Обсяги публікацій наведені для того, щоб показати, що насправді проблема консенсусу зовсім непроста, і за подібними алгоритмами лежить величезна праця найрозумніших людей.
Цікаво, що сам Леслі Лемпорт у своїй лекції зауважив, що у другій статті-поясненні є одне твердження, один рядок (не уточнив який), який може бути по-різному трактований. І тому велика кількість сучасних реалізацій Paxos працюють не зовсім коректно.
Докладний розбір роботи Paxos'а потягне не одну статтю, тому я постараюся дуже коротко передати основну ідею алгоритму. У посиланнях наприкінці моєї статті ви знайдете матеріали для подальшого занурення на цю тему.
Ролі в Paxos
p align="justify"> В алгоритмі Paxos є поняття ролей. Розглянемо три основні (є модифікації з додатковими ролями):
- Proposers (також можуть зустрічатися терміни: лідери чи координатори). Це хлопці, які дізнаються про якесь нове значення від користувача та беруть він роль лідера. Їхнє завдання запустити раунд пропозиції нового значення та координувати подальші дії вузлів. Причому Paxos припускає наявність кількох лідерів у певних ситуаціях.
- Acceptors (Voters). Це вузли, які голосують за ухвалення чи неприйняття того чи іншого значення. Їхня роль дуже важлива, тому що саме від них залежить рішення: в який стан перейде (або не перейде) система після чергового етапу алгоритму консенсусу.
- Учні. Вузли, які просто приймають та записують нове прийняте значення, коли стан системи змінився. Вони не приймають рішення, просто отримують дані та можуть віддати їх кінцевому користувачеві.
Один вузол може поєднувати кілька ролей у різних ситуаціях.
Поняття кворуму
Ми припускаємо, що у нас є система з N вузлів. І з них максимум F вузлів може виходити з ладу. Якщо F вузлів виходить з ладу, значить у нас у кластері має бути як мінімум 2F + 1 вузлів acceptor'ів.
Це потрібно для того, щоб у нас завжди, навіть у найгіршій ситуації «хороші», коректно працюючі вузли мали більшість. Тобто Ж + 1 «добрих» вузлів, які погодилися, і фінальне значення буде ухвалено. В іншому випадку може бути ситуація, коли у нас різні локальні групи набудуть різного значення і не зможуть між собою домовитися. Тому нам потрібна абсолютна більшість, щоб перемогти у голосуванні.
Загальна ідея роботи алгоритму консенсусу Paxos
Алгоритм Paxos передбачає дві великі фази, які у свою чергу розбиваються на два кроки кожна:
- Phase 1a: Prepare. На етапі підготовки лідер (proposer) повідомляє всі вузли: «Ми розпочинаємо новий етап голосування. В нас новий раунд. Номер цього раунду – n. Нині ми почнемо голосувати». Поки що він просто повідомляє про початок нового циклу, але не повідомляє нове значення. Завдання цього етапу ініціювати новий раунд та повідомити всім його унікальний номер. Номер раунду важливий, це має бути більшим, ніж усі попередні номери голосувань від усіх попередніх лідерів. Оскільки саме завдяки номеру раунду інші вузли в системі розумітимуть, наскільки свіжі дані у лідера. Ймовірно, інші вузли вже мають результати голосування з набагато пізніших раундів, і вони просто розкажуть лідерові, що він відстав від життя.
- Phase 1b: Promise. Коли вузли-acceptor'и отримали номер нового етапу голосування, можливі два результати:
- Номер n нового голосування більший, ніж номер будь-якого з попередніх голосувань, у якому брав участь учасник. Тоді acceptor відправляє лідерові обіцянку, що більше брати участь у жодних голосуваннях із меншим номером, ніж n. Якщо acceptor вже встиг за щось проголосувати (тобто він вже у другій фазі прийняв якесь значення), то до своєї обіцянки він прикладає прийняте значення та номер голосування, в якому він брав участь.
- В іншому випадку, якщо гравець вже знає про голосування з великим номером, він може просто проігнорувати етап підготовки і не відповідати лідеру.
- Phase 2a: Accept. Лідеру потрібно дочекатися відповіді від кворуму (більшості вузлів у системі) і, якщо потрібна кількість відповідей отримана, то має два варіанти розвитку подій:
- Деякі з acceptor'ів надіслали значення, які вони вже голосували. У цьому випадку лідер вибирає значення із голосування з максимальним номером. Назвемо це значення x, і розсилає всім вузлам повідомлення виду: «Accept (n, x)», де перше значення – номер голосування зі свого кроку Propose, а друге значення – те навіщо всі збиралися, тобто. значення за яке, власне, голосуємо.
- Якщо ніхто з acceptor'ів не надіслав жодних значень, а просто вони пообіцяли голосувати в цьому раунді, лідер може запропонувати їм проголосувати за своє значення, то значення, заради якого він взагалі став лідером. Назвемо його y. Він розсилає всім вузлам повідомлення виду: "Accept (n, y)", за аналогією з попереднім результатом.
- Phase 2b: Accepted. Далі, вузли-acceptor'и, при отриманні повідомлення «Accept(…)», від лідера погоджуються з ним (розсилають усім вузлам підтвердження, що вони згодні з новим значенням) тільки в тому випадку, якщо вони не пообіцяли якомусь (іншому ) лідеру брати участь у голосуваннях з номером раунду n' > n, інакше вони ігнорують запит на підтвердження.
Якщо лідерові відповіли більшість вузлів, і всі вони підтвердили нове значення, то нове значення вважається прийнятим. Ура! Якщо ж більшість не набрано або є вузли, які відмовилися набувати нового значення, то все починається спочатку.
Ось так працює алгоритм Paxos. У кожного з цих етапів є багато тонкощів, ми практично не розглянули різні види відмов, проблеми множинних лідерів та багато іншого, але метою даної статті є лише на верхньому рівні познайомити читача зі світом розподілених обчислень.
Також варто зауважити, що Paxos — не єдиний у своєму роді, є й інші алгоритми, наприклад, але це вже тема для іншої статті.
Посилання на матеріали для подальшого вивчення
Рівень «новачок»:
- , Preethi Kasireddy, blog article on Medium
- , Adi Kancherla, blog article on Medium
- , Ittai Abraham, blog
- , Ittai Abraham, blog article
Рівень «Леслі Лемпорт»:
- , Fischer, Lynch and Paterson, research paper, 1985
- , Leslie Lamport, research paper, 1998
- , Leslie Lamport, research paper, 2001
Джерело: habr.com