🥇Кот Шрьодингер без кутия: проблемът с консенсуса в разпределените системи

Да предположим, в комнате находятся 5 котов, и для того чтобы разбудить хозяина, им нужно договориться и произнести это одновременно, так как дверь они могут открыть только вместе, наложившись друг на друга. Если один из котов — кот Шрёдингера, и остальные коты не знают о его намерении, возникает вопрос: «Как они смогут это сделать?»

В этой статье я доступно объясню вам теоретические аспекты распределённых систем и принципы их функционирования. Также я кратко рассмотрю основную идею, лежащую в основе алгоритма Paxos.

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

На самом деле, у нас есть только гарантии от поставщика. Они изложены в документации примерно следующим образом: «Этот сервис достаточно надёжный, он имеет установленный уровень обслуживания (SLA), не беспокойтесь, всё будет работать распределённым образом, как вы и ожидаете».

Мы склонны верить в лучшее, ведь умные люди из крупных компаний уверили нас, что всё будет хорошо. Мы не задаём вопрос: а почему это вообще может работать? Существует ли какое-то формальное обоснование корректности работы таких систем?

Недавно я посетил школу по распределённым вычислениям и был вдохновлён этой темой. Лекции в школе больше напоминали занятия по математическому анализу, чем изучение компьютерных систем. Но именно так в своё время доказывались важнейшие алгоритмы, которые мы используем каждый день, не подозревая об этом.

В большинстве современных распределённых систем используется алгоритм консенсуса Paxos и его различные модификации. Примечательно, что обоснованность и возможность существования этого алгоритма могут быть доказаны всего лишь с помощью ручки и бумаги. При этом на практике алгоритм применяется в крупных системах с огромным количеством узлов, развернутых в облаках.

Лёгкая иллюстрация того, о чём мы будем говорить дальше: задача двух генераловДавайте для разминки разберём задачу двух генералов.

Имаме две армии – рижа и бяла. Белите войски са разположени в обсадения град. Рижите войски, наченствани от генералите A1 и A2, са разположени от двете страни на града. Задачата на рижите е да атакуват белия град и да победи. Обаче войското на всеки рижи генерал поотделно е по-малко от войското на белите.

Условията за победа за рижите: двамата генерали трябва да атакуват едновременно, за да имат числено предимство над белите. За целта генералите A1 и A2 трябва да постигнат споразумение помежду си. Ако всеки нападне поотделно, рижите ще загубят.

За да се споразумеят, генералите A1 и A2 могат да си изпращат пратеници през територията на белия град. Пратеникът може успешно да достигне до съюзния генерал или може да бъде заловен от противника. Въпросът е: има ли такава последователност на комуникации между рижите генерали (последователност на изпращане на пратеници от A1 към A2 и обратно от A2 към A1), при която те гарантирано ще постигнат споразумение за атака в час X. Тук под гаранции се разбира, че и двамата генерали ще имат недвусмислено потвърждение, че съюзникът (другият генерал) със сигурност ще атакува в определеното време X.

Да предположим, че A1 изпраща пратеник до A2 с послание: «Нека атакуваме днес в полунощ!». Генерал A1 не може да атакува без потвърждение от генерал A2. Ако пратеникът от A1 е стигнал, генерал A2 изпраща потвърждение с послание: «Да, нека днес да пометем белите». Но сега генерал A2 не знае дали неговият пратеник е стигнал или не, и няма гаранции, че атаката ще бъде едновременно. Сега генерал A2 отново се нуждае от потвърждение.

Ако продължим да разглеждаме тяхната комуникация, ще установим следното: колкото и много цикли на обмен на съобщения да има, няма начин гарантирано да уведомим двамата генерали, че техните съобщения са получени (при условие, че всеки от пратениците може да бъде заловен).

Задачата на двамата генерали е прекрасно илюстриране на много проста разпределена система, където има два възела с ненадеждна комуникация. Това означава, че нямаме 100% гаранция, че те ще се синхронизират. Подобни проблеми в по-голям мащаб ще бъдат разгледани по-нататък в статията.

Въвеждаме понятието разпределени системи.

Разпределена система е група компютри (в жалото на „възли“), които могат да обменят съобщения. Всеки отделен възел е автономна единица. Възелът може самостоятелно да обработва задачи, но за да взаимодейства с други възли, трябва да изпраща и получава съобщения.

Как точно са реализирани съобщенията, кои протоколи се използват – това не ни интересува в този контекст. Важно е, че възлите на разпределената система могат да обменят данни помежду си чрез изпращане на съобщения.

Самото определение изглежда не много сложно, но трябва да имаме предвид, че разпределената система притежава редица атрибути, които ще бъдат важни за нас.

Атрибути на разпределените системи

Съпътстващост – възможност за възникване на съвместни или конкурентни събития в системата. Освен това, ще считаме, че събития, които се случват на два различни възли, са потенциално конкурентни, докато нямаме ясен ред за възникването на тези събития. А обикновено нямаме такъв ред.
Липса на глобални часовници. Нямаме ясен ред на събитията поради липсата на глобални часовници. В обикновения свят ние сме свикнали, че имаме часовници и абсолютно време. Всичко се променя, когато става въпрос за разпределени системи. Дори свръхточните атомни часовници имат отклонение, и могат да възникнат ситуации, когато не можем да кажем кое от двете събития е настъпило първо. Затова не можем да разчитаме на времето.
Независимо отказване на възли в системата. Има още един проблем: нещо може да се обърка просто защото нашите възли не са вечни. Може да се повреди твърд диск, виртуалната машина в облака може да се рестартира, мрежата може да прекъсне и съобщенията да се загубят. Освен това, могат да възникнат ситуации, когато възлите работят, но същевременно работят против системата. Последният клас проблеми е получил дори отделно име: проблем на византийските генерали. Най-популярният пример за разпределена система с такъв проблем е Blockchain. Но днес няма да разглеждаме този специфичен клас проблеми. Интересуват ни ситуации, в които просто един или няколко възли могат да се провалят.
Модели на комуникация (модели за обмен на съобщения) между възлите. Разбрахме, че възлите комуникират чрез обмен на съобщения. Има два известни модела на обмен на съобщения: синхронен и асинхронен.

Модели на комуникация между възлите в разпределени системи

Синхронен модел – ние точно знаем, че съществува крайна известна дельта време, в която съобщението гарантирано достига от един възел до друг. Ако това време изтече и съобщението не е пристигнало, можем спокойно да кажем, че възелът е излязъл от строя. В такъв модел имаме предсказуемо време на изчакване.

Асинхронен модел – в асинхронните модели считаме, че времето на изчакване е крайно, но не съществува такава дельта време, след която можем да гарантираме, че възелът е излязъл от строя. Т.е. времето на изчакване на съобщение от възел може да бъде произволно дълго. Това е важно определение и ще поговорим за него по-късно.

Понятието за консенсус в разпределени системи

Преди да формализираме понятието за консенсус, нека разгледаме пример за ситуация, в която той ни е необходим, а именно – Replicaция на състояния на машината.

Имаме известен разпределен лог. Бихме искали той да бъде последователен и да съдържа идентични данни на всички възли на разпределената система. Когато някой от възлите научи нова стойност, която иска да запише в лога, неговата задача е да предложи тази стойност на всички останали възли, така че логът да се обнови на всички възли и системата да премине в ново последователно състояние. Важно е възлите да се споразумеят помежду си: всички възли да са съгласни, че предложената нова стойност е коректна, всички възли да приемат тази стойност, и само в този случай всички могат да запишат новата стойност в лога.

С други думи: никой от възлите не е възразил, че има по-актуална информация и предложената стойност е невярна. Споразумението между възлите и съгласието относно единствената правилно приета стойност е консенсус в разпределената система. По-нататък ще говорим за алгоритмите, които позволяват на разпределената система да достига консенсус по сигурен начин.

По-формално, ние можем да определим алгоритъма за постигане на консенсус (или просто консенсусен алгоритъм) като функция, която преобразува разпределена система от състояние А в състояние Б. Това състояние е прието от всички възли и всички възли могат да го потвърдят. Както се оказва, тази задача не е толкова тривиална, колкото изглежда на пръв поглед.

Свойства на консенсусния алгоритъм

Консенсусният алгоритъм трябва да притежава три свойства, за да може системата да продължи да съществува и да има напредък в прехода от състояние в състояние:

Съгласие – всички коректно работещи възли трябва да приемат една и съща стойност (в статии това свойство се среща и като свойство на безопасност). Всички възли, които в момента функционират (не са се повредили и не са загубили връзка с останалите) трябва да достигнат до съгласие и да приемат някаква финална обща стойност.
Тук е важно да разберем, че възлите в разглежданата от нас разпределена система искат да постигнат съгласие. Тоест, в момента говорим за системи, в които просто може нещо да се провали (например, да се провали някакъв възел), но в тази система определено няма възли, които умишлено работят срещу другите (задачата на византийските генерали). Поради това свойство системата остава консистентна.
Цялостност — ако всички коректно работещи възли предлагат една и съща стойност, vтогава всеки коректно работещ възел трябва да приеме тази стойност. v.
Завършване – всички коректно работещи възли в крайна сметка ще приемат някаква стойност (свойство на активност), което позволява на алгоритъма да има напредък в системата. Всеки отделен коректно работещ възел трябва рано или късно да приеме финалната стойност и да потвърди това: «За мен – тази стойност е вярна, съгласен съм с цялата система».

Пример за работа на консенсусния алгоритъм

Докато свойствата на алгоритъма могат да не са напълно ясни, нека илюстрираме с пример какви етапи преминава най-простият консенсусен алгоритъм в система с синхронен модел за обмен на съобщения, в която всички възли функционират правилно, съобщенията не се губят и нищо не се поврежда (наистина ли това всъщност се случва?).

Всичко започва с предложението за ръка и сърце (Propose). Да предположим, че клиент се е присъединил към възела, наречен „Възел 1“, и е започнал транзакция, предавайки нова стойност на възела – О. От този момент нататък ще наричаме „Възел 1“ proposer. Като proposer „Възел 1“ сега трябва да уведомят цялата система, че разполага със свежи данни, и той праща съобщения до всички останали възли: „Вижте! Получих стойността „О“ и искам да я запиша! Моля, потвърдете, че и вие ще запишете „О“ в своя лог.“
Следващата фаза е гласуването за предложената стойност (Voting). За какво служи това? Може да се случи, че на другите възли е изпратена по-свежа информация и те разполагат с данни по същата транзакция.

Когато възел „Възел 1“ изпрати своя пропоуз, останалите възли проверяват в своите лога данните за това събитие. Ако няма противоречия, възлите обявяват: „Да, нямам други данни за това събитие. Стойността „О“ е най-свежата информация, която получихме.“
В противен случай, възлите могат да отговорят на „Възел 1“: „Слушай! Аз имам по-свежи данни за тази транзакция. Не „О“, а нещо по-добро.“
На етапа на гласуване възлите стигат до решение: или всички приемат една стойност, или някой от тях гласува против, указвайки, че разполага с по-свежи данни.
Ако кръгът на гласуването е успешен и всички са „за“, системата преминава в нова фаза – приемане на стойността (Accept). „Възел 1“ събира всички отговори от другите възли и съобщава: „Всички се съгласиха със стойността „О“! Сега официално обявявам, че „О“ е нашата нова стойност, единна за всички! Запишете си в тетрадката, не забравяйте. Запишете в своя лог!“
Останалите възли изпращат потвърждение (Accepted), че са записали стойността „О“, без да са получили нещо ново за това време (в своя род двуфазен комит). След това значимо събитие считаме, че разпределената транзакция е изпълнена.

Така алгоритъмът на консенсуса в прост случай се състои от четири стъпки: propose, гласуване (voting), приемане (accept), потвърждение на приемането (accepted).

Ако на някой етап не успеем да постигнем съгласие, алгоритъмът се стартира отново, с информацията, предоставена от възлите, отказали се да потвърдят предложената стойност.

Алгоритъм за консенсус в асинхронната система

До момента всичко беше гладко, защото ставаше дума за синхронен модел на обмен на съобщения. Но ние знаем, че в съвременния свят сме свикнали да работим асинхронно. Как работи аналогичният алгоритъм в система с асинхронен модел на обмен на съобщения, където смятаме, че времето за изчакване на отговор от възел може да бъде произволно дълго (между другото, излизането на възела от строя също може да се разглежда като пример, когато възел може да отговаря произволно дълго).

Сега, когато знаем принципно как работи алгоритъмът за консенсус, въпросът към любопитните читатели, които стигнаха до този момент: колко възла в система от N възли с асинхронен модел на съобщения могат да излязат от строя, за да може системата все още да постигне консенсус?

Правилният отговор и обосновка са зад спойлера.Правилният отговор: 0. Ако поне един възел в асинхронна система излезе от строя, системата не може да постигне консенсус. Това твърдение е доказано в известната в определени среди теорема FLP (1985, Fischer, Lynch, Paterson, линк към оригинала в края на статията): «Невъзможността за постигане на разпределен консенсус при излизането от строя на поне един възел».

Хора, тогава имаме проблем, свикнали сме, че всичко е асинхронно. А тук е така. Как да продължим напред?

Току-що говорехме за теория, за математика. Какво означава „консенсус не може да бъде постигнат“, преведено от математическия език на нашия – инженерния? Това означава, че „не винаги може да бъде постигнат“, т.е. съществува такъв случай, при който консенсусът не е постижим. А какъв бисе този случай?

Това е точно нарушаването на свойството за жизненост, описано по-горе. Нямаме общо съгласие и системата не може да напредва (не може да завърши за ограничено време), когато нямаме отговор от всички възли. Защото в асинхронна система нямаме предсказуемо време за отговор и не можем да знаем дали възелът е излязъл от строя или просто отговаря бавно.

Но на практика можем да намерим решение. Нека нашият алгоритъм може да работи дълго при откази (потенциално може да работи безкрайно). Но в повечето ситуации, когато повечето възли функционират правилно, ще имаме напредък в системата.

На практика имаме работа с частично синхронни комуникационни модели. Частичната синхронност се разбира така: като цяло имаме асинхронен модел, но формално се въвежда понятието "глобално стабилизиране на времето" за определен момент.

Този момент може да не настъпи безкрайно дълго, но веднъж той трябва да се случи. Звънецът на виртуалния будилник ще прозвъни и от този момент можем да предскажем делтата на времето, за което съобщенията ще достигнат до нас. От този момент системата от асинхронна става синхронна. На практика имаме работа именно с такива системи.

Алгоритъмът Paxos решава проблеми с консенсуса

Paxos – това е семейство алгоритми, които решават проблема с консенсуса за частично синхронни системи, при условие че някои възли могат да излязат от строя. Автор на Paxos е Leslie Lamport. Той предложи формално доказателство за съществуването и коректността на алгоритма през 1989 година.

Но доказателството се оказа никак не тривиално. Първата публикация беше издадена едва през 1998 година (33 страници), описваща алгоритъма. Както се оказа, тя беше изключително трудна за разбиране и през 2001 година беше публикувано пояснение към статията, което зае 14 страници. Обемите на публикациите са посочени, за да се покаже, че всъщност проблемът с консенсуса е доста сложен и зад подобни алгоритми стои огромен труд на най-интелигентните хора.

Интересно е, че самият Лесли Лампорта в своя лекция отбеляза, че във втората статия-пояснение има едно твърдение, една линия (не уточнява какво), която може да бъде тълкувана по различен начин. И поради това голямо количество съвременни реализации на Paxos не работят съвсем коректно.

Подробен анализ на работата на Paxos ще изисква повече от една статия, затова ще се опитам много накратко да предам основната идея на алгоритъма. В линковете в края на моята статия ще намерите материали за по-дълбочинно потапяне в тази тема.

Ролите в Paxos

В алгоритъма Paxos съществува понятието роли. Нека разгледаме три основни (има модификации с допълнителни роли):

Proposers (понякога могат да се срещат термини: лидери или координатори). Те са хората, които откриват ново значение от потребителя и поемат ролята на лидер. Тяхната задача е да стартират кръг от предложения за ново значение и да координират следващите действия на узлите. Система Paxos позволява наличието на няколко лидера при определени обстоятелства.
Приемачи (Гласоподаватели). Това са узли, които гласуват за приемането или неприемането на дадено значение. Неговата роля е много важна, защото именно от тях зависи решението: в какво състояние ще премине (или няма да премине) системата след поредния етап на алгоритъма за консенсус.
Обучаващи. Узли, които просто приемат и записват новоприето значение, когато състоянието на системата се е променило. Те не вземат решения, просто получават данни и могат да ги предоставят на крайния потребител.

Един узел може да комбинира няколко роли в различни ситуации.

Понятие за кворум

Предполагаме, че имаме система от N узли. И от тях максимум F узла може да излезе от строя. Ако F узла излизат от строя, то в клъстера трябва да има поне 2F + 1 узли приемачи.

Това е необходимо, за да имаме винаги, дори в най-лошата ситуация, "добри", коректно работещи узли, които да имат мнозинство. Тоест, F + 1 "добри" узли, които са се съгласили, и финалното значение ще бъде прието. В противен случай може да настъпи ситуация, в която различни локални групи приемат различно значение и не могат да се споразумеят помежду си. Затова ни е необходимо абсолютно мнозинство, за да спечелим в гласуването.

Общата идея на работа на алгоритъма за консенсус Paxos

Алгоритъмът Paxos предвижда две основни фази, всяка от които се разделя на две стъпки:

Фаза 1а: Подготовка. На етапа на подготовка лидер (proposer) уведомява всички възли: „Започваме нов етап на гласуване. Имаме нов рунд. Номерът на този рунд е n. Сега ще започнем да гласуваме“. Докато той просто уведомява за началото на нов цикъл, но не съобщава нова стойност. Задачата на този етап е да се инициира нов рунд и да се съобщи на всички неговият уникален номер. Номерът на рунда е важен, това трябва да бъде стойност, по-голяма от всичките предишни номера на гласувания от всички предишни лидери. Именно благодарение на номера на рунда другите възли в системата ще разбират колко актуални са данните при лидера. Вероятно, другите възли вече имат резултати от гласуването от много по-късни рундове и те просто ще кажат на лидера, че той е изостанал.
Етап 1б: Обещание. Когато възлите-acceptor’и получат номера на новия етап на гласуване, възможни са два изхода:
- Номерът n на новото гласуване е по-голям от номера на всяко от предишните гласувания, в които е участвал acceptor. Тогава acceptor изпраща на лидера обещание, че няма да участва повече в никакви гласувания с по-малък номер от n. Ако acceptor вече е успял да гласува за нещо (т.е. той вече е в втория етап и е приел някаква стойност), той прикрепя към обещанието си приетата стойност и номера на гласуването, в което е участвал.
- В противен случай, ако acceptor вече знае за гласуването с по-висок номер, той може просто да игнорира етапа на подготовка и да не отговаря на лидера.
Етап 2а: Приемане. Лидерът трябва да изчака отговор от кворума (броя на възлите в системата) и, ако е получен необходимият брой отговори, той има два варианта за развитие на събитията:
- Някои от acceptor’ите са изпратили стойности, за които вече са гласували. В този случай лидерът избира стойността от гласуването с максимален номер. Нека наречем тази стойност x и разпраща на всички възли съобщение от вида: „Accept (n, x)“, където първата стойност – номерът на гласуването от неговата стъпка Propose, а втората стойност – това, за което всъщност се събират, т.е. стойността, за която всъщност гласуваме.
- Ако никой от acceptor'ите не е изпратил стойности и просто е обещал да гласува в този рунд, лидерът може да им предложи да гласуват за своето значение, за което изобщо е станал лидер. Нека го наречем y. Той разпраща на всички възли съобщение от вида: "Accept (n, y)", по аналогия с предишния резултат.
Фаза 2b: Прието. По-нататък, възлите-acceptor'и, при получаване на съобщение "Accept(…)" от лидера, се съгласяват с него (разпращат на всички възли потвърждение, че са съгласни с новата стойност) само ако не са обещали на някой (друг) лидер да участват в гласуванията с номер на рунда. n’ > n, в противен случай те игнорират искането за потвърдение.
Ако лидерът е получил отговор от мнозинството възли и всички те са потвърдили новата стойност, то новата стойност се счита за приета. Ура! Ако обаче мнозинството не е постигнато или има възли, които отказват да приемат новата стойност, всичко започва отначало.

Така работи алгоритъмът Paxos. Всеки от тези етапи има много нюанси, практически не разгледахме различни видове откази, проблеми с множествени лидери и много други, но целта на тази статия е единствено да запознае читателя на високо ниво с света на разпределените изчисления.

Също така трябва да се отбележи, че Paxos не е единственият в своя род, има и други алгоритми, например, Raft, но това вече е тема за друга статия.