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

Представете си, че в стаята са затворени 5 котки и за да събудят собственика, те трябва да се споразумеят помежду си, защото могат да отворят вратата само, ако се натрупат петима. Ако един от котките е котката на Шрьодингер, а останалите не знаят за нейното решение, възниква въпросът: „Как могат да го направят?“

В тази статия ще ви обясня по прост начин теоретичната основа на разпределените системи и принципите на тяхната работа. Ще се запознаем и повърхностно с основната идея на Paxos.

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

По същество, гаранциите, които имаме, са гаранции на доставчика. Те са описани в документацията по следния начин: „Тази услуга е достатъчно надеждна, има зададен SLA, не се притеснявайте, всичко ще работи разпределено, както очаквате.“

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

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

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

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

Имаме две армии – червена и бяла. Белите войски са базирани в обсадения град. Червените войски, водени от генералите А1 и А2, са разположени от двете страни на града. Задачата на червените е да нападнат бялата крепост и да спечелят. Въпреки това, войското на всеки червен генерал поотделно е по-малко от това на белите.

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

За да се споразумеят, генералите А1 и А2 могат да изпращат един на друг куриери през територията на белия град. Куриерът може успешно да достигне до съюзния генерал или може да бъде прихванат от врага. Въпросът е: съществува ли такава последователност на комуникации между червените генерали (последователност от изпращане на куриери от А1 до А2 и обратно от А2 до А1), при която те гарантирано ще се споразумеят за нападение в час Х. Тук, под гаранции, се разбира, че и двамата генерали ще имат недвусмислено потвърждение, че съюзникът (другият генерал) със сигурност ще атакува в определеното време Х.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Съгласие – всички коректно функциониращи възли трябва да приемат едно и също значение (в статиите това свойство също се среща като свойство на безопасността). Всички възли, които в момента функционират (не са се повредили и не са загубили връзка с останалите), трябва да постигнат съгласие и да приемат някакво окончателно общо значение.
Тук е важно да се разбере, че възлите в разглежданата от нас разпределена система искат да се споразумеят. Тоест, в момента говорим за системи, в които нещо може да се провали (например, да се провали някой възел), но в тази система определено няма възли, които умишлено работят против другите (задача на византийските генерали). Поради това свойство системата остава консистентна.
Цялост — ако всички коректно функциониращи възли предлагат едно и също значение 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, линк към оригинала в края на статията): "Невъзможност за постигане на разпределен консенсус при изход на поне един възел от строя."

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

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

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

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

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

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

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

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

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

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

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

Роли в Paxos

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

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

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

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

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

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

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

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

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

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

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