Така че нека си представим. 5 котки са затворени в стаята и за да отидат да събудят стопанина, трябва всички заедно да се споразумеят за това, защото могат да отворят вратата само като се облегнат на нея с пет от тях. Ако една от котките е котката на Шрьодингер и другите котки не знаят за неговото решение, възниква въпросът: „Как могат да направят това?“
В тази статия ще ви разкажа с прости думи за теоретичния компонент на света на разпределените системи и принципите на тяхната работа. И също така повърхностно разгледайте основната идея, залегнала в Paxos'a.
Когато разработчиците използват облачни инфраструктури, различни бази данни, работят в клъстери от голям брой възли, те са уверени, че данните ще бъдат последователни, безопасни и винаги достъпни. Но къде са гаранциите?
Всъщност гаранциите, които имаме, са гаранции на доставчика. Те са описани в документацията по следния начин: „Тази услуга е доста надеждна, има зададен SLA, не се притеснявайте, всичко ще работи разпределено, както очаквате.“
Склонни сме да вярваме в най-доброто, защото умни чичковци от големи компании ни уверяваха, че всичко ще бъде наред. Ние не задаваме въпроса защо всъщност това изобщо може да работи? Има ли някаква формална обосновка за правилната работа на такива системи?
Наскоро ходих при и беше много вдъхновен от тази тема. Лекциите в училище приличаха повече на часове по математически анализ, отколкото на нещо, свързано с компютърни системи. Но точно така навремето се доказаха най-важните алгоритми, които използваме всеки ден, без да подозираме.
Повечето съвременни разпределени системи използват консенсусния алгоритъм Paxos и неговите различни модификации. Най-готиното е, че валидността и по принцип самата възможност за съществуването на този алгоритъм може да се докаже просто с химикал и хартия. В същото време на практика алгоритъмът се използва в големи системи, работещи на огромен брой възли в облаците.
Лека илюстрация на това, което ще бъде обсъдено по-нататък: проблемът за двама генералиНека да разгледаме загрявката .
Имаме две армии - червена и бяла. Белите войски са базирани в обсадения град. Червените войски, водени от генерали A1 и A2, са разположени от двете страни на града. Задачата на червенокосите е да атакуват белия град и да спечелят. Въпреки това армията на всеки червен генерал поотделно е по-малка от армията на белите.
Условия за победа на червенокосите: и двамата генерали трябва да атакуват едновременно, за да имат числено предимство пред белите. За да направите това, генералите A1 и A2 трябва да се споразумеят помежду си. Ако всеки атакува поотделно, червенокосите ще загубят.
За да преговарят, генералите A1 и A2 могат да изпращат пратеници един на друг през територията на белия град. Пратеникът може успешно да достигне до съюзнически генерал или може да бъде прихванат от врага. Въпрос: има ли такава последователност от комуникации между червенокосите генерали (последователността на изпращане на пратеници от A1 до A2 и обратно от A2 до A1), при която те гарантирано ще се споразумеят за атака в час X. Тук, под гаранции се разбира, че и двамата генерали ще имат недвусмислено потвърждение, че съюзник (друг генерал) ще атакува точно в определеното време X.
Да предположим, че A1 изпраща пратеник до A2 със съобщението: "Нека атакуваме днес в полунощ!". Генерал А1 не може да атакува без потвърждение от Генерал А2. Ако пратеникът от A1 е достигнал, тогава генерал A2 изпраща потвърждение със съобщението: "Да, нека да напълним белтъците днес." Но сега Генерал А2 не знае дали пратеникът му е достигнал или не, той няма гаранции дали атаката ще бъде едновременна. Сега генерал A2 отново се нуждае от потвърждение.
Ако опишем комуникацията им по-нататък, се оказва следното: колкото и цикли на обмен на съобщения да има, няма начин да гарантираме и на двамата генерали, че съобщенията им са получени (ако приемем, че всеки от пратениците може да бъде прихванат).
Проблемът с двата генерала е чудесна илюстрация на много проста разпределена система, в която има два възела с ненадеждна комуникация. Така че нямаме 100% гаранция, че са синхронизирани. За подобни проблеми само в по-голям мащаб по-късно в статията.
Въвеждане на концепцията за разпределени системи
Разпределената система е група от компютри (наричани по-нататък възли), които могат да обменят съобщения. Всеки отделен възел е някаква автономна единица. Един възел може сам да обработва задачи, но за да комуникира с други възли, трябва да изпраща и получава съобщения.
Как конкретно се реализират съобщенията, какви протоколи се използват – това не ни интересува в този контекст. Важно е възлите на една разпределена система да могат да обменят данни помежду си чрез изпращане на съобщения.
Самото определение не изглежда много сложно, но имайте предвид, че разпределената система има редица атрибути, които ще бъдат важни за нас.
Атрибути на разпределени системи
- Concurrency – възможността за възникване на едновременни или конкурентни събития в системата. Освен това ще считаме, че събитията, настъпили на два различни възела, са потенциално едновременни, докато нямаме ясен ред, в който се случват тези събития. И обикновено не го правим.
- Няма глобален часовник. Нямаме ясен ред на събитията поради липсата на глобален часовник. В обикновения свят на хората сме свикнали с факта, че имаме часове и време абсолютно. Всичко се променя, когато става въпрос за разпределени системи. Дори свръхпрецизните атомни часовници имат дрейф и има ситуации, в които не можем да кажем кое от двете събития се е случило първо. Следователно не можем да разчитаме и на времето.
- Независим отказ на системни възли. Има и друг проблем: нещо може да се обърка просто защото нашите възли не са вечни. Твърдият диск може да се повреди, виртуалната машина в облака може да се рестартира, мрежата може да мига и съобщенията ще бъдат загубени. Освен това има ситуации, когато възлите работят, но в същото време работят срещу системата. Последният клас проблеми дори получи отделно име: проблемът . Най-популярният пример за разпределена система с такъв проблем е Blockchain. Но днес няма да разглеждаме този специален клас задачи. Ще се интересуваме от ситуации, в които само един или повече възли могат да се провалят.
- Комуникационни модели (модели за съобщения) между възлите. Вече разбрахме, че възлите комуникират чрез обмен на съобщения. Има два добре известни модела на съобщения: синхронен и асинхронен.
Модели на комуникация между възли в разпределени системи
Синхронен модел - знаем със сигурност, че има крайна известна делта от време, за което съобщението гарантирано ще достигне от един възел до друг. Ако това време е изтекло и съобщението не е пристигнало, можем спокойно да кажем, че възелът е неуспешен. При такъв модел имаме предвидимо време на изчакване.
Асинхронен модел – в асинхронните модели приемаме, че времето за изчакване е ограничено, но няма времева делта, след която може да се гарантира, че възелът е неуспешен. Тези. времето за изчакване на съобщение от възел може да бъде произволно дълго. Това е важно определение и ще говорим за него по-нататък.
Концепцията за консенсус в разпределени системи
Преди да дефинирате официално концепцията за консенсус, помислете за пример за ситуация, в която имаме нужда от него, а именно − Репликация на държавна машина.
Имаме някакъв разпространен дневник. Бихме искали да бъде последователен и да съдържа идентични данни за всички възли на разпределена система. Когато един от възлите научи нова стойност, която ще запише в дневника, неговата задача е да предложи тази стойност на всички други възли, така че дневникът да се актуализира на всички възли и системата да превключи към ново последователно състояние. В същото време е важно възлите да са съгласни помежду си: всички възли са съгласни, че предложената нова стойност е правилна, всички възли приемат тази стойност и само в този случай всеки може да регистрира нова стойност.
С други думи: нито един от възлите не възрази, че разполага с по-актуална информация и предложената стойност беше неправилна. Споразумението между възлите и споразумението за една правилна приета стойност е консенсусът в разпределена система. След това ще говорим за алгоритми, които позволяват на разпределена система да постигне консенсус с гарантиран.
По-формално, можем да дефинираме консенсусен алгоритъм (или просто консенсусен алгоритъм) като някаква функция, която превежда разпределена система от състояние А в състояние Б. Освен това, това състояние се приема от всички възли и всички възли могат да го потвърдят. Както се оказва, тази задача съвсем не е толкова тривиална, колкото изглежда на пръв поглед.
Свойства на консенсусния алгоритъм
Консенсусният алгоритъм трябва да има три свойства, за да може системата да продължи да съществува и да има известен напредък в прехода от състояние към състояние:
- Съгласие – всички правилно работещи възли трябва да приемат една и съща стойност (в статиите това свойство се среща и като свойство за безопасност). Всички възли, които сега функционират (не са излезли от строя и не са загубили връзка с останалите), трябва да постигнат споразумение и да приемат някаква крайна обща стойност.
Тук е важно да се разбере, че възлите в разпределената система, която разглеждаме, искат да се съгласят. Тоест сега говорим за системи, в които нещо може просто да се повреди (например някой възел да се повреди), но в тази система определено няма възли, които умишлено работят срещу други (задачата на византийските генерали). Благодарение на това свойство системата остава последователна.
- интегритет - ако всички правилно работещи възли предлагат една и съща стойност v, така че всеки правилно работещ възел трябва да приеме тази стойност v.
- Приключване - всички коректно работещи възли в крайна сметка ще приемат някаква стойност (свойство на жизненост), което позволява на алгоритъма да има прогрес в системата. Всеки отделен възел, който работи правилно, рано или късно трябва да приеме крайната стойност и да я потвърди: "За мен тази стойност е вярна, съгласен съм с цялата система."
Пример за това как работи консенсусният алгоритъм
Докато свойствата на алгоритъма може да не са напълно ясни. Затова ще илюстрираме с пример през какви етапи преминава най-простият консенсусен алгоритъм в система със синхронен модел на съобщения, в който всички възли функционират според очакванията, съобщенията не се губят и нищо не се поврежда (това наистина ли се случва?).
- Всичко започва с предложение за брак (Propose). Да предположим, че клиент се свързва към възел, наречен "Възел 1" и започва транзакция, като предава нова стойност на възела - O. Отсега нататък ще наричаме "Възел 1" оферта. Тъй като предлагащият „възел 1“ сега трябва да уведоми цялата система, че има свежи данни, и той изпраща съобщения до всички останали възли: „Вижте! Получих стойността "O" и искам да я запиша! Моля, потвърдете, че ще запишете и „O“ във вашия дневник.“
- Следващият етап е гласуване за предложената стойност (Гласуване). За какво е? Може да се случи, че други възли са получили по-нова информация и имат данни за същата транзакция.
Когато възелът „Възел 1“ изпрати своя пропус, другите възли проверяват своите регистрационни файлове за данни за това събитие. Ако няма конфликт, възлите съобщават: „Да, нямам други данни за това събитие. Стойността „O“ е най-актуалната информация, която заслужаваме.“Във всеки друг случай възлите могат да отговорят на „Възел 1“: „Слушай! Имам по-нови данни за тази сделка. Не "О", а нещо по-добро."
На етапа на гласуване възлите стигат до решение: или всички приемат една и съща стойност, или един от тях гласува против, което означава, че разполага с по-нови данни.
- Ако кръгът на гласуване е бил успешен и всички са били за, тогава системата преминава към нов етап - приемане на стойността (Приемам). „Възел 1“ събира всички отговори от други възли и докладва: „Всички са съгласни със стойността „О“! Сега официално заявявам, че "О" е нашето ново значение, еднакво за всички! Запишете го в бележника си, не забравяйте. Пишете в дневника си!"
- Останалите възли изпращат потвърждение (Прието), че са записали стойността „O“ за себе си, нищо ново не е получено през това време (вид двуфазов ангажимент). След това важно събитие считаме, че разпределената транзакция е завършена.
По този начин алгоритъмът за консенсус в прост случай се състои от четири стъпки: предложение, гласуване (гласуване), приемане (приема), потвърждение на приемане (прието).
Ако на дадена стъпка не можем да постигнем съгласие, тогава алгоритъмът се рестартира, като се вземе предвид информацията, предоставена от възлите, които отказаха да потвърдят предложената стойност.
Консенсусен алгоритъм в асинхронна система
Преди това всичко беше гладко, защото ставаше дума за модела за синхронни съобщения. Но знаем, че в съвременния свят сме свикнали да правим всичко асинхронно. Как работи подобен алгоритъм в система с асинхронен модел на съобщения, където вярваме, че времето за изчакване за отговор от възел може да бъде произволно дълго (между другото, повреда на възел също може да се разглежда като пример, когато възел може да отговаря произволно дълго).
Сега, след като знаем как работи консенсусният алгоритъм по принцип, въпросът е за онези любознателни читатели, които са достигнали дотук: колко възли в система от N възли с асинхронен модел на съобщения могат да отпаднат, така че системата все още да може да достигне консенсус ?
Правилният отговор и обосновката зад спойлера.Правилният отговор е: 0. Ако дори един възел в асинхронна система падне, системата няма да може да постигне консенсус. Това твърдение е доказано в добре известната теорема на FLP (1985, Фишер, Линч, Патерсън, връзка към оригинала в края на статията): „Невъзможността за постигане на разпределен консенсус, ако поне един възел се провали.“
Момчета, тогава имаме проблем, свикнали сме, че при нас всичко е асинхронно. И ето го. Как да продължа да живея?
Току що говорихме за теория, за математика. Какво значи „не може да се постигне консенсус“, преведено от математически език на нашия – инженерство? Това означава, че "не винаги може да се постигне", т.е. има случай, в който консенсус не може да се постигне. И какъв е този случай?
Това е точно описаното по-горе нарушение на свойството жизненост. Нямаме общо споразумение и системата не може да прогресира (не може да прекрати за крайно време) в случай, че нямаме отговор от всички възли. Тъй като в асинхронна система нямаме предсказуемо време за реакция и не можем да знаем дали даден възел не работи или просто отнема много време, за да отговори.
Но на практика можем да намерим решение. Нека нашият алгоритъм може да работи дълго време в случай на неизправности (потенциално може да работи за неопределено време). Но в повечето ситуации, когато повечето от възлите функционират правилно, ще имаме напредък в системата.
На практика имаме работа с частично синхронни комуникационни модели. Частичният синхронизъм се разбира по следния начин: в общия случай имаме асинхронен модел, но официално се въвежда определена концепция за „глобално стабилизиращо време“ на определен момент от времето.
Този момент във времето може да не дойде безкрайно, но един ден трябва да дойде. Виртуалният будилник ще звъни и от този момент нататък можем да предвидим делтата на времето, в която ще достигнат съобщенията. От този момент нататък системата се превръща от асинхронна в синхронна. На практика се занимаваме с такива системи.
Алгоритъмът Paxos решава консенсусни проблеми
е семейство от алгоритми, които решават проблема с консенсуса за частично синхронни системи, при условие че някои възли могат да се провалят. Авторът на Paxos е . Той предложи официално доказателство за съществуването и коректността на алгоритъма през 1989 г.
Но доказателството се оказа никак нетривиално. Първата публикация е издадена едва през 1998 г. (33 страници), описваща алгоритъма. Оказа се, че е изключително трудно за разбиране и през 2001 г. е публикувано обяснение към статията, което заема 14 страници. Обемите на публикациите са дадени, за да се покаже, че всъщност проблемът с консенсуса не е никак прост и зад подобни алгоритми стои огромен труд на най-умните хора.
Интересно е, че самият Лесли Лампор в своята лекция отбеляза, че във втората статия-обяснение има едно твърдение, един ред (той не уточни кой), който може да се тълкува по различни начини. И поради това голям брой съвременни реализации на Paxos не работят съвсем правилно.
Подробният анализ на работата на Paxos ще отнеме повече от една статия, така че ще се опитам да предам основната идея на алгоритъма много накратко. Във връзките в края на моята статия ще намерите материали за по-нататъшно гмуркане в тази тема.
Роли в Паксос
Алгоритъмът Paxos има концепция за роли. Помислете за три основни (има модификации с допълнителни роли):
- Предложители (може да има и термини: ръководители или координатори). Това са момчетата, които научават за някакво ново значение от потребителя и поемат ролята на лидер. Тяхната задача е да стартират кръг от предложения за нова стойност и да координират по-нататъшните действия на възлите. Освен това Paxos позволява присъствието на няколко лидера в определени ситуации.
- Приемащи (гласоподаватели). Това са възлите, които гласуват за приемане или отхвърляне на определена стойност. Тяхната роля е много важна, тъй като от тях зависи решението: до какво състояние ще отиде (или няма да отиде) системата след следващия етап от консенсусния алгоритъм.
- Учащите. Възли, които просто приемат и записват новата приета стойност, когато състоянието на системата се промени. Те не вземат решения, те просто получават данни и могат да ги дадат на крайния потребител.
Един възел може да комбинира няколко роли в различни ситуации.
Понятието кворум
Предполагаме, че имаме система от N възли. И повечето от тях F възлите може да се провалят. Ако F възлите се провалят, тогава трябва да имаме поне 2F+1 акцепторни възли.
Това е необходимо, така че винаги, дори и в най-лошата ситуация, „добрите“, правилно работещи възли да имат мнозинство. Това е Ж + 1 „добри“ възли, които са съгласни, и крайната стойност ще бъде приета. В противен случай може да има ситуация, при която различни местни групи ще приемат различни значения и няма да могат да се споразумеят помежду си. Така че имаме нужда от абсолютно мнозинство, за да спечелим вота.
Обща идея за консенсусния алгоритъм Paxos
Алгоритъмът Paxos предполага две големи фази, които от своя страна са разделени на две стъпки всяка:
- Фаза 1а: Подгответе. По време на подготвителния етап лидерът (предложителят) информира всички възли: „Започваме нов етап на гласуване. Имаме нов кръг. Номерът на този кръг е n. Сега ще започнем да гласуваме." Досега той само отчита началото на нов цикъл, но не отчита новата стойност. Задачата на този етап е да започне нов кръг и да информира всички за неговия уникален номер. Кръглото число е важно, то трябва да е по-голямо от всички предишни числа за гласуване от всички предишни лидери. Тъй като благодарение на кръглото число другите възли в системата ще разберат колко свежи са данните на лидера. Вероятно други възли вече имат резултати от гласуване от много по-късни рундове и просто ще кажат на лидера, че изостава.
- Фаза 1b: Обещание. Когато акцепторните възли са получили номера на новия етап на гласуване, са възможни два резултата:
- Броят n на новия вот е по-голям от броя на който и да е от предишните гласувания, в които е участвал акцептантът. След това акцепторът изпраща обещание на лидера, че повече няма да участва в никакви гласувания с номер по-малък от n. Ако акцепторът вече е гласувал за нещо (т.е. вече е приел някаква стойност във втората фаза), тогава той добавя приетата стойност и номера на гласуването, в което е участвал, към своето обещание.
- В противен случай, ако акцепторът вече знае за гласуването с голям брой, той може просто да игнорира подготвителната стъпка и да не отговори на лидера.
- Фаза 2а: Приемете. Лидерът трябва да изчака отговор от кворума (повечето възли в системата) и ако се получи необходимия брой отговори, той има две възможности за развитие на събитията:
- Някои от акцепторите са представили стойности, за които вече са гласували. В този случай лидерът избира стойността от вота с най-голям брой. Нека наречем тази стойност x и изпратим съобщение като това до всички възли: „Приемам (n, x)“, където първата стойност е броят на гласуване от собствената й стъпка за предлагане, а втората стойност е това, за което всички са се събрали, т.е. стойност, за която всъщност гласуваме.
- Ако никой от акцепторите не изпрати никакви стойности, а просто обеща да гласува в този кръг, лидерът може да ги покани да гласуват за тяхната стойност, стойността, за която изобщо е станал лидер. Нека го наречем y. Той изпраща до всички възли съобщение от формата: "Приемам (n, y)", по аналогия с предишния резултат.
- Фаза 2b: Прието. Освен това акцепторните възли, при получаване на съобщението "Приеми (...)", от лидера се съгласяват с него (изпращат потвърждение до всички възли, че са съгласни с новата стойност), само ако не са обещали някои (други) лидер да участва в гласуването с номера на кръга n' > nв противен случай те игнорират подканата за потвърждение.
Ако по-голямата част от възлите отговориха на лидера и всички те потвърдиха новата стойност, тогава новата стойност се счита за приета. Ура! Ако мнозинството не е въведено или има възли, които са отказали да приемат новата стойност, тогава всичко започва отначало.
Ето как работи алгоритъмът Paxos. Всеки от тези етапи има много тънкости, ние практически не разглеждаме различни видове повреди, проблеми на множество лидери и много други, но целта на тази статия е само да въведе читателя в света на разпределените изчисления на най-високо ниво.
Също така си струва да се отбележи, че Paxos не е единственият по рода си, има и други алгоритми, напр. , но това е тема за друга статия.
Връзки към материали за допълнително проучване
Ниво начинаещ:
- , Preethi Kasireddy, статия в блога на Medium
- , Ади Канчерла, статия в блога на Medium
- Блог на Ittai Abraham
- , Ittai Abraham, статия в блога
Ниво на Лесли Лампорт:
- Фишер, Линч и Патерсън, изследователска статия, 1985 г
- , Лесли Лампорт, изследователска статия, 1998 г
- , Лесли Лампорт, изследователска статия, 2001 г
Източник: www.habr.com