Дакле, замислимо. У просторији је закључано 5 мачака, а да би пробудили власника, сви морају да се договоре о томе, јер могу да отворе врата само са пет њих ослоњених на њих. Ако је једна од мачака Шредингерова мачка, а друге мачке не знају за његову одлуку, поставља се питање: „Како то могу да ураде?“
В этой статье я простым языком расскажу вам о теоретической составляющей мира распределённых систем и принципах их работы. А также поверхностно рассмотрю главную идею, лежащую в основе Paxos’а.
Когда разработчики пользуются облачными инфраструктурами, различными базами данных, работают в кластерах из большого числа узлов, они уверены, что данные будут целостными, сохранными и всегда доступными. Но откуда гарантии?
По сути, гарантии, которые у нас есть – это гарантии поставщика. Они описаны в документации примерно следующим образом: «Этот сервис достаточно надёжный, у него есть заданный SLA, не беспокойтесь, всё будет распределённо работать, как вы и ожидаете».
Склони смо да верујемо у најбоље, јер су нас паметни момци из великих компанија уверавали да ће све бити у реду. Не постављамо питање: зашто, у ствари, ово уопште може да функционише? Да ли постоји формално оправдање за исправан рад оваквих система?
Недавно сам отишао у и био је веома инспирисан овом темом. Предавања у школи су више личила на часове математике него на нешто везано за компјутерске системе. Али управо тако су се својевремено доказали најважнији алгоритми које свакодневно користимо, а да то нисмо ни свесни.
Већина савремених дистрибуираних система користи Пакос консензус алгоритам и његове различите модификације. Најкул ствар је што се валидност и, у принципу, сама могућност постојања овог алгоритма може доказати једноставно оловком и папиром. У пракси, алгоритам се користи у великим системима који раде на огромном броју чворова у облацима.
Лайтовая иллюстрация того, о чем пойдёт речь дальше: задача двух генераловХајде да погледамо за загревање .
Имамо две војске – црвену и белу. Беле трупе се налазе у опкољеном граду. Црвене трупе које предводе генерали А1 и А2 налазе се на две стране града. Задатак црвенокосих је да нападну бели град и победе. Међутим, војска сваког црвеног генерала појединачно је мања од беле војске.
Услови победе за црвене: оба генерала морају да нападну истовремено да би имали бројчану предност над белима. Да би то урадили, генерали А1 и А2 морају да се договоре једни са другима. Ако сви нападну засебно, црвенокоси ће изгубити.
Да би постигли договор, генерали А1 и А2 могу да пошаљу гласнике једни другима преко територије белог града. Гласник може успешно доћи до савезничког генерала или га непријатељ може пресрести. Питање: постоји ли такав редослед комуникације између црвенокосих генерала (редослед слања гласника од А1 до А2 и обрнуто од А2 до А1), у којем се гарантовано договоре о нападу у часу Кс. Овде, гаранције значе да ће оба генерала имати недвосмислену потврду да ће савезник (други генерал) дефинитивно напасти у одређено време Кс.
Претпоставимо да А1 шаље гласника А2 са поруком: „Нападнимо данас у поноћ!“ Генерал А1 не може да нападне без потврде генерала А2. Ако је стигао гласник из А1, онда генерал А2 шаље потврду са поруком: „Да, хајде да данас убијемо белце. Али сада генерал А2 не зна да ли је његов гласник стигао или не, нема гаранције да ли ће напад бити истовремен. Сада је генералу А2 поново потребна потврда.
Ако даље опишемо њихову комуникацију, постаје јасно да без обзира на то колико циклуса размене порука постоји, не постоји начин да се гарантује да су оба генерала примила своје поруке (под претпоставком да било који гласник може бити пресретнут).
Проблем два генерала је одлична илустрација веома једноставног дистрибуираног система где постоје два чвора са непоузданом комуникацијом. То значи да немамо 100% гаранцију да су синхронизовани. О сличним проблемима се касније у чланку говори само у већем обиму.
Уводимо концепт дистрибуираних система
Дистрибуирани систем је група рачунара (у даљем тексту их називамо чворови) који могу да размењују поруке. Сваки појединачни чвор је нека врста аутономног ентитета. Чвор може самостално да обрађује задатке, али да би комуницирао са другим чворовима, мора да шаље и прима поруке.
Как конкретно реализованы сообщения, какие протоколы используются – это нас не интересует в данном контексте. Важно, что узлы распределённой системы могут обмениваться друг с другом данными путем отправки сообщений.
Само определение выглядит не очень сложным, но нужно учитывать, что у распределённой системы есть ряд атрибутов, которые будут важны для нас.
Атрибути дистрибуираних система
- Цонцурренци – могућност истовремених или истовремених догађаја у систему. Штавише, сматраћемо да су догађаји који се дешавају на два различита чвора потенцијално истовремени све док немамо јасан редослед настанка ових догађаја. Али, по правилу, немамо.
- Нема глобалног сата. Немамо јасан редослед догађаја због недостатка глобалног сата. У обичном свету људи, навикли смо на чињеницу да имамо сатове и време апсолутно. Све се мења када су у питању дистрибуирани системи. Чак и ултра-прецизни атомски сатови имају померање, и могу постојати ситуације у којима не можемо рећи који се од два догађаја први догодио. Дакле, не можемо се ослонити ни на време.
- Независни отказ системских чворова. Постоји још један проблем: нешто може поћи наопако једноставно зато што наши чворови не трају вечно. Чврсти диск може покварити, виртуелна машина у облаку може поново да се покрене, мрежа може да трепери и поруке ће бити изгубљене. Штавише, могу постојати ситуације у којима чворови раде, али у исто време раде против система. Последња класа задатака је чак добила посебан назив: проблем . Најпопуларнији пример дистрибуираног система са овим проблемом је Блоцкцхаин. Али данас нећемо разматрати ову посебну класу проблема. Бићемо заинтересовани за ситуације у којима једноставно један или више чворова може да откаже.
- Модели коммуникации (модели обмена сообщениями) между узлами. Мы уже выяснили, что узлы общаются путем обмена сообщениями. Есть две известные модели обмена сообщениями: синхронная и асинхронная.
Модели коммуникации между узлами в распределённых системах
Синхрони модел – поуздано знамо да постоји коначна позната делта времена током којег порука гарантовано стиже од једног чвора до другог. Ако је ово време прошло, а порука није стигла, можемо са сигурношћу рећи да је чвор пропао. У овом моделу имамо предвидљива времена чекања.
Асинхрони модел – у асинхроним моделима сматрамо да је време чекања коначно, али не постоји таква делта времена након које можемо гарантовати да је чвор отказао. Оне. Време чекања на поруку од чвора може бити произвољно дуго. Ово је важна дефиниција и о томе ћемо даље говорити.
Понятие консенсуса в распределённых системах
Прежде, чем формально определить понятие консенсуса, рассмотрим пример ситуации, когда он нам нужен, а именно – Репликација државног строја.
Имамо неки дистрибуирани дневник. Желели бисмо да буде конзистентан и да садржи идентичне податке на свим чворовима дистрибуираног система. Када један од чворова научи нову вредност коју ће записати у дневник, његов задатак постаје да понуди ову вредност свим осталим чворовима тако да се дневник ажурира на свим чворовима и систем пређе у ново конзистентно стање. У овом случају, важно је да се чворови међусобно слажу: сви чворови се слажу да је предложена нова вредност тачна, сви чворови прихватају ову вредност, и само у овом случају свако може да упише нову вредност у дневник.
Другим речима: ниједан од чворова није приговорио да има релевантније информације, а предложена вредност је нетачна. Договор између чворова и договор о једној исправној прихваћеној вредности је консензус у дистрибуираном систему. Затим ћемо говорити о алгоритмима који омогућавају да дистрибуирани систем гарантовано постигне консензус.
Формалније, можемо дефинисати консензус алгоритам (или једноставно алгоритам консензуса) као одређену функцију која преноси дистрибуирани систем из стања А у стање Б. Штавише, ово стање прихватају сви чворови и сви чворови га могу потврдити. Како се испоставило, овај задатак уопште није тако тривијалан као што се чини на први поглед.
Особине алгоритма консензуса
Алгоритм консенсуса должен обладать тремя свойствами, чтобы система продолжала существовать и имела какой-то прогресс в переходе из состояния в состояние:
- Договор – сви исправно оперативни чворови морају имати исту вредност (у чланцима се ово својство назива и безбедносним својством). Сви чворови који тренутно функционишу (нису отказали или изгубили контакт са осталима) морају се договорити и прихватити неку коначну заједничку вредност.
Овде је важно разумети да чворови у дистрибуираном систему који разматрамо желе да се сложе. Односно, сада говоримо о системима у којима нешто једноставно може да закаже (на пример, неки чвор откаже), али у овом систему дефинитивно нема чворова који намерно раде против других (задатак византијских генерала). Због ове особине, систем остаје конзистентан.
- Интегритет — если все корректно работающие узлы предлагают одно и то же значение v, значит каждый корректно работающий узел должен принять это значение v.
- Завршетак – сви исправно радни чворови ће на крају попримити одређену вредност (својство животности), што омогућава алгоритму да напредује у систему. Сваки појединачни чвор који исправно ради мора пре или касније да прихвати коначну вредност и потврди је: „За мене је ова вредност тачна, слажем се са целим системом.
Пример работы алгоритма консенсуса
Док својства алгоритма можда нису сасвим јасна. Због тога ћемо примером илустровати кроз које фазе пролази најједноставнији алгоритам консензуса у систему са моделом синхроне размене порука, у којем сви чворови функционишу како се очекује, поруке се не губе и ништа се не ломи (да ли се ово заиста дешава?).
- Всё начинается с предложения руки и сердца (Propose). Предположим, что к узлу под названием «Узел 1» подключился клиент и начал транзакцию, передав узлу новое значение – О. С этого момента «Узел 1» мы будем называть понуда. Као предлагач, „Чвор 1“ сада мора да обавести цео систем да има свеже податке и шаље поруке свим осталим чворовима: „Погледајте! Значење „О“ ми је дошло и желим да га запишем! Потврдите да ћете такође уписати „О“ у свој дневник.“
- Следећа фаза је гласање за предложену вредност (Вотинг). За шта је то? Може се десити да други чворови добију новије информације и да имају податке о истој трансакцији.
Када чвор „Чвор 1” пошаље свој предлог, остали чворови проверавају своје дневнике за податке о овом догађају. Ако нема противречности, чворови објављују: „Да, немам других података за овај догађај. Вредност „О“ је најновија информација коју заслужујемо.“В любом другом случае, узлы могут ответить «Узлу 1»: «Послушай! У меня есть более свежие данные по этой транзакции. Не «О», а кое-что получше».
На стадии голосования узлы приходят к решению: либо все принимают одно значение, либо кто-то из них голосует против, обозначив, что у него есть более свежие данные.
- Ако је круг гласања био успешан и сви су били за, онда систем прелази у нову фазу – прихватање вредности. „Чвор 1“ прикупља све одговоре од других чворова и извештава: „Сви су се сложили око вредности „О“! Сада званично изјављујем да је „О“ наше ново значење, исто за све! Запишите то у своју малу књигу, не заборавите. Запишите то у свој дневник!"
- Преостали чворови шаљу потврду (Прихваћено) да су записали вредност „О“; ништа ново није стигло за то време (нека врста двофазног урезивања). Након овог значајног догађаја, сматрамо да је дистрибуирана трансакција завршена.
Дакле, алгоритам консензуса у једноставном случају састоји се од четири корака: предложити, гласати (гласати), прихватити (прихватати), потврдити прихватање (прихватати).
Ако у неком кораку нисмо успели да постигнемо договор, алгоритам почиње поново, узимајући у обзир информације које су дали чворови који су одбили да потврде предложену вредност.
Алгоритам консензуса у асинхроном систему
Пре овога је све било глатко, јер смо говорили о моделу синхроне размене порука. Али знамо да смо у савременом свету навикли да све радимо асинхроно. Како сличан алгоритам функционише у систему са асинхроним моделом размене порука, где сматрамо да време чекања на одговор од чвора може бити произвољно дуго (успут, отказ чвора се такође може сматрати примером када чвор може да одговара произвољно дуго времена).
Сада када знамо како алгоритам консензуса функционише у принципу, питање за оне радознале читаоце који су догурали овако далеко: колико чворова у систему од Н чворова са моделом асинхроних порука може да поквари тако да систем ипак може да постигне консензус?
Тачан одговор и оправдање су иза спојлера.Тачан одговор је: 0. Ако чак и један чвор у асинхроном систему откаже, систем неће моћи да постигне консензус. Ова тврдња је доказана у ФЛП теореми, добро познатој у одређеним круговима (1985, Фисцхер, Линцх, Патерсон, линк на оригинал на крају чланка): „Немогућност постизања дистрибуираног консензуса ако барем један чвор откаже .”
Ребята, тогда у нас проблема, мы же привыкли, что у нас всё асинхронно. А тут такое. Как дальше жить?
Причали смо само о теорији, о математици. Шта значи „консензус се не може постићи“, преводећи са математичког језика на наш – инжењерство? То значи да се „не може увек постићи“, тј. Постоји случај у којем није могуће постићи консензус. Какав је ово случај?
Ово је управо кршење својства животности описаног изнад. Немамо заједнички договор, а систем не може имати напредак (не може се завршити у коначном времену) у случају да немамо одговор од свих чворова. Зато што у асинхроном систему немамо предвидљиво време одговора и не можемо знати да ли се чвор срушио или му је само потребно много времена да одговори.
Али у пракси можемо наћи решење. Нека наш алгоритам може дуго да ради у случају кварова (потенцијално може да ради неограничено). Али у већини ситуација, када већина чворова функционише исправно, имаћемо напредак у систему.
У пракси се бавимо делимично синхроним комуникационим моделима. Делимична синхронизација се схвата на следећи начин: у општем случају имамо асинхрони модел, али се формално уводи одређени концепт „време глобалне стабилизације“ одређене тачке у времену.
Овај тренутак у времену можда неће доћи дуго, али мора доћи једног дана. Виртуелни будилник ће зазвонити и од тог тренутка можемо предвидети временску делту за коју ће поруке стизати. Од овог тренутка систем прелази из асинхроног у синхрони. У пракси се бавимо управо таквим системима.
Пакос алгоритам решава проблеме консензуса
– это семейство алгоритмов, которые решают проблему консенсуса для частично синхронных систем, при условии что какие-то узлы могут выходить из строя. Автором Paxos’а является . Он предложил формальное доказательство существования и корректности алгоритма в 1989 году.
Али показало се да је доказ далеко од тривијалног. Прва публикација објављена је тек 1998. године (33 странице) која описује алгоритам. Како се испоставило, било је изузетно тешко разумети, а 2001. године објављено је објашњење чланка које је заузимало 14 страница. Обим публикација је дат како би се показало да заправо проблем консензуса није нимало једноставан, а иза оваквих алгоритама се крије огроман рад најпаметнијих људи.
Занимљиво је да је и сам Лесли Лампорт у свом предавању приметио да у другом експланаторном чланку постоји један исказ, један ред (није прецизирао који), који се може тумачити на различите начине. И због тога, велики број модерних Пакос имплементација не ради сасвим исправно.
Подробный разбор работы Paxos’а потянет не на одну статью, поэтому я постараюсь очень коротко передать основную идею алгоритма. В ссылках в конце моей статьи вы найдете материалы для дальнейшего погружения в эту тему.
Улоге у Паксосу
В алгоритме Paxos есть понятие ролей. Рассмотрим три основные (есть модификации с дополнительными ролями):
- Proposers (также могут встречаться термины: лидеры или координаторы). То су момци који од корисника уче о некој новој вредности и преузимају улогу лидера. Њихов задатак је да покрену круг предлога за нову вредност и координирају даље акције чворова. Штавише, Пакос дозвољава присуство неколико лидера у одређеним ситуацијама.
- Прихватачи (гласачи). Это узлы, которые голосуют за принятие или непринятие того или иного значения. Их роль очень важна, потому что именно от них зависит решение: в какое состояние перейдет (или не перейдет) система после очередного этапа алгоритма консенсуса.
- Ученици. Чворови који једноставно прихватају и пишу нову прихваћену вредност када се стање система промени. Они не доносе одлуке, они само примају податке и могу их дати крајњем кориснику.
Один узел может совмещать несколько ролей в разных ситуациях.
Концепт кворума
Претпостављамо да имамо систем од N чворови И од њих максимум F узлов может выходить из строя. Если F узлов выходит из строя, значит у нас в кластере должно быть, как минимум 2Ф+1 акцепторски чворови.
Это нужно для того, чтобы у нас всегда, даже в худшей ситуации «хорошие», корректно работающие узлы имели большинство. То есть Ф + 1 "добри" чворови који су се сложили, а коначна вредност ће бити прихваћена. У супротном, може доћи до ситуације да наше различите локалне групе поприме различита значења и да се не могу сложити међу собом. Дакле, потребна нам је апсолутна већина да бисмо добили гласове.
Общая идея работы алгоритма консенсуса Paxos
Алгоритм Paxos предполагает две больших фазы, которые в свою очередь разбиваются на два шага каждая:
- Фаза 1а: Припремите се. Током припремне фазе, лидер (предлагач) обавештава све чворове: „Почињемо нову фазу гласања. Имамо нови круг. Број овог круга је н. Сада ћемо почети да гласамо“. За сада, једноставно пријављује почетак новог циклуса, али не пријављује нову вредност. Задатак ове фазе је да покрене нови круг и обавести све о свом јединственом броју. Округли број је важан, он мора бити вредност већа од свих претходних гласачких бројева свих претходних лидера. Зато што ће захваљујући округлом броју други чворови у систему разумети колико су нови подаци лидера. Вероватно је да други чворови већ имају резултате гласања из много каснијих рунди и да ће једноставно рећи лидеру да је иза времена.
- Фаза 1б: Обећање. Когда узлы-acceptor’ы получили номер нового этапа голосования, возможны два исхода:
- Број н новог гласа је већи од броја било ког претходног гласања у коме је акцептант учествовао. Тада акцептант шаље обећање лидеру да неће учествовати у више гласова са бројем мањим од н. Ако је акцептант већ за нешто гласао (тј. већ је прихватио неку вредност у другој фази), онда он свом обећању приписује прихваћену вредност и број гласа у којем је учествовао.
- В противном случае, если acceptor уже знает о голосовании с большим номером, он может просто проигнорировать этап подготовки и не отвечать лидеру.
- Фаза 2а: Прихватите. Лидеру нужно дождаться ответа от кворума (большинства узлов в системе) и, если нужное число ответов получено, то у него есть два варианта развития событий:
- Неки од прималаца су послали вредности за које су већ гласали. У овом случају, лидер бира вредност из гласања са максималним бројем. Назовимо ову вредност к, и она шаље поруку свим чворовима као што је: „Прихвати (н, к)“, где је прва вредност број гласања из сопственог корака Предлога, а друга вредност је оно због чега су се сви окупили, тј. вредност за коју заправо гласамо.
- Ако нико од примаоца није послао ниједну вредност, али су једноставно обећали да ће гласати у овом кругу, лидер их може позвати да гласају за њихову вредност, вредност због које је он пре свега постао лидер. Назовимо то и. Шаље поруку свим чворовима попут: „Прихвати (н, и)“, слично претходном исходу.
- Фаза 2б: Прихваћено. Даље, акцепторски чворови, по пријему поруке „Прихватам(...)“ од лидера, сагласни су са њом (шаљу потврду свим чворовима да се слажу са новом вредношћу) само ако нису обећали неку (другу) лидер да учествује у гласању са округлим бројем н' > н, иначе игноришу захтев за потврду.
Ако је већина чворова одговорила лидеру и сви су потврдили нову вредност, онда се нова вредност сматра прихваћеном. Ура! Ако већина није достигнута или постоје чворови који су одбили да прихвате нову вредност, онда све почиње изнова.
Овако функционише Пакос алгоритам. Свака од ових фаза има много суптилности, ми практично нисмо разматрали разне врсте кварова, проблеме вишеструких лидера и још много тога, али сврха овог чланка је само да уведе читаоца у свет дистрибуираног рачунарства на високом нивоу.
Также стоит заметить, что Paxos — не единственный в своем роде, есть и другие алгоритмы, например, , али ово је тема за други чланак.
Везе до материјала за даље проучавање
Почетни ниво:
- , Preethi Kasireddy, blog article on Medium
- , Ади Канчерла, чланак на блогу на Медијуму
- , Иттаи Абрахам, блог
- , Иттаи Абрахам, чланак на блогу
Ниво Лесли Лампорт:
- , Fischer, Lynch and Paterson, research paper, 1985
- , Леслие Лампорт, истраживачки рад, 1998
- , Леслие Лампорт, истраживачки рад, 2001
Извор: ввв.хабр.цом