Значи, да замислиме. Во собата се заклучени 5 мачки, а за да одат да го разбудат сопственикот, треба сите да се договорат за тоа меѓу себе, бидејќи вратата можат да ја отворат само со пет од нив потпрени на неа. Ако една од мачките е мачката на Шредингер, а другите мачки не знаат за неговата одлука, се поставува прашањето: „Како можат да го направат тоа?
Во оваа статија, ќе ви кажам со едноставни термини за теоретската компонента на светот на дистрибуираните системи и принципите на нивното функционирање. Исто така, површно ќе ја разгледам главната идеја во основата на Паксос.
Кога програмерите користат облак инфраструктури, различни бази на податоци и работат во кластери од голем број јазли, тие се уверени дека податоците ќе бидат целосни, безбедни и секогаш достапни. Но, каде се гаранциите?
Во суштина, гаранциите што ги имаме се гаранции на добавувачите. Тие се опишани во документацијата на следниов начин: „Оваа услуга е прилично сигурна, има дадена SLA, не грижете се, сè ќе работи дистрибуирано како што очекувате“.
Склони сме да веруваме во најдоброто, бидејќи паметните момци од големите компании не уверуваа дека се ќе биде во ред. Не го поставуваме прашањето: зошто, всушност, ова воопшто може да функционира? Дали има некакво формално оправдување за правилно функционирање на таквите системи?
Неодамна отидов во и беше многу инспириран од оваа тема. Предавањата на училиште повеќе личеа на часови за анализа отколку нешто поврзано со компјутерски системи. Но, токму вака едно време се докажаа најважните алгоритми што ги користиме секојдневно, без воопшто да го знаеме.
Повеќето модерни дистрибуирани системи го користат алгоритмот за консензус на Паксос и неговите различни модификации. Најкул е што валидноста и во принцип самата можност за постоење на овој алгоритам може да се докаже едноставно со пенкало и хартија. Во пракса, алгоритмот се користи во големи системи кои работат на огромен број јазли во облаците.
Лесна илустрација за она што ќе се дискутира понатаму: задачата на двајца генералиАјде да погледнеме за загревање .
Имаме две армии - црвена и бела. Белите трупи се сместени во опколениот град. Црвените трупи предводени од генералите А1 и А2 се наоѓаат на две страни од градот. Задачата на црвенокосите е да го нападнат белиот град и да победат. Меѓутоа, војската на секој црвен генерал поединечно е помала од белата војска.
Услови за победа на црвените: и двајцата генерали мора да напаѓаат во исто време за да имаат бројчана предност пред белите. За да го направите ова, генералите А1 и А2 треба да се договорат меѓу себе. Ако секој нападне посебно, црвенокосите ќе загубат.
За да постигнат договор, генералите А1 и А2 можат да испраќаат гласници еден до друг преку територијата на белиот град. Гласникот може успешно да стигне до сојузнички генерал или може да биде пресретнат од непријателот. Прашање: дали постои таков редослед на комуникации меѓу црвенокосите генерали (редоследот на испраќање гласници од А1 до А2 и обратно од А2 до А1), во кој гарантирано ќе се договорат за напад во часот X. Еве, гаранциите значат дека и двајцата генерали ќе имаат недвосмислена потврда дека сојузникот (друг генерал) дефинитивно ќе нападне во одреденото време X.
Да претпоставиме дека А1 испрати гласник до А2 со порака: „Ајде да нападнеме денес на полноќ!“ Генералот А1 не може да нападне без потврда од генералот А2. Ако гласникот од А1 пристигнал, тогаш генералот А2 испраќа потврда со пораката: „Да, ајде да ги убиеме белците денес“. Но, сега генералот А2 не знае дали неговиот гласник пристигнал или не, тој нема гаранција дали нападот ќе биде симултан. Сега на Генералниот А2 повторно му треба потврда.
Опишувањето на нивните комуникации дополнително го открива следново: без разлика колку циклуси на пораки има, не постои начин да се гарантира дека и двајцата генерали се известени дека нивните пораки се примени (претпоставувајќи дека кој било гласник може да биде пресретнат).
Проблемот на двајца генерали е одлична илустрација за многу едноставен дистрибуиран систем каде што има два јазли со несигурна комуникација. Ова значи дека немаме 100% гаранција дека тие се синхронизирани. Слични проблеми се дискутирани само во поголем обем подоцна во статијата.
Го воведуваме концептот на дистрибуирани системи
Дистрибуиран систем е група на компјутери (во натамошниот текст ќе ги нарекуваме јазли) кои можат да разменуваат пораки. Секој поединечен јазол е некој вид на автономен ентитет. Еден јазол може сам да обработува задачи, но за да комуницира со други јазли, треба да испраќа и прима пораки.
Како точно се имплементираат пораките, кои протоколи се користат - ова не е од интерес за нас во овој контекст. Важно е јазлите на дистрибуираниот систем да можат да разменуваат податоци едни со други преку испраќање пораки.
Самата дефиниција не изгледа многу комплицирано, но мора да земеме во предвид дека дистрибуираниот систем има голем број на атрибути кои ќе ни бидат важни.
Атрибути на дистрибуирани системи
- Concurrency – можност за симултани или истовремени настани кои се случуваат во системот. Згора на тоа, настаните што се случуваат на два различни јазли ќе ги сметаме за потенцијално истовремени сè додека немаме јасен редослед на појава на овие настани. Но, како по правило, го немаме.
- Нема глобален часовник. Немаме јасен редослед на настани поради немањето глобален часовник. Во обичниот свет на луѓе, ние сме навикнати на фактот дека имаме часовници и време апсолутно. Сè се менува кога станува збор за дистрибуирани системи. Дури и ултра прецизните атомски часовници се движат, и може да има ситуации кога не можеме да кажеме кој од двата настани се случил прв. Затоа, не можеме да се потпреме ниту на времето.
- Независен неуспех на системските јазли. Има уште еден проблем: нешто може да тргне наопаку едноставно затоа што нашите јазли не траат вечно. Хард дискот може да не успее, виртуелната машина во облакот може да се рестартира, мрежата може да трепка и пораките ќе се изгубат. Покрај тоа, може да има ситуации кога јазлите работат, но во исто време работат против системот. Последната класа на проблеми дури доби и посебно име: проблем . Најпопуларниот пример на дистрибуиран систем со овој проблем е Blockchain. Но, денес нема да ја разгледаме оваа посебна класа на проблеми. Ќе бидеме заинтересирани за ситуации во кои едноставно еден или повеќе јазли може да пропаднат.
- Модели за комуникација (модели за пораки) помеѓу јазли. Веќе утврдивме дека јазлите комуницираат со размена на пораки. Постојат два добро познати модели на пораки: синхрони и асинхрони.
Модели на комуникација помеѓу јазли во дистрибуирани системи
Синхрони модел – сигурно знаеме дека постои конечна позната временска делта за време на која пораката е загарантирана да стигне од еден до друг јазол. Ако ова време помина и пораката не пристигна, можеме безбедно да кажеме дека јазолот не успеа. Во овој модел имаме предвидливи времиња на чекање.
Асинхрон модел – кај асинхроните модели сметаме дека времето на чекање е конечно, но не постои таква делта на време по која можеме да гарантираме дека јазолот не успеал. Оние. Времето на чекање за порака од јазол може да биде произволно долго. Ова е важна дефиниција, и ќе зборуваме за тоа понатаму.
Концептот на консензус во дистрибуирани системи
Пред формално да го дефинираме концептот на консензус, да разгледаме пример за ситуација кога ни е потребен, имено - Репликација на состојбата на машината.
Имаме дистрибуиран дневник. Би сакале тој да биде конзистентен и да содржи идентични податоци за сите јазли на дистрибуираниот систем. Кога еден од јазлите ќе научи нова вредност што ќе ја запише во дневникот, неговата задача станува да ја понуди оваа вредност на сите други јазли, така што дневникот се ажурира на сите јазли и системот се преместува во нова конзистентна состојба. Во овој случај, важно е јазлите да се согласат меѓу себе: сите јазли се согласуваат дека предложената нова вредност е точна, сите јазли ја прифаќаат оваа вредност и само во овој случај секој може да ја запише новата вредност во дневникот.
Со други зборови: ниту еден од јазлите не се противеше дека има порелевантни информации, а предложената вредност беше неточна. Договорот помеѓу јазлите и договорот за една правилна прифатена вредност е консензус во дистрибуиран систем. Следно, ќе зборуваме за алгоритми кои овозможуваат да се гарантира дека дистрибуираниот систем ќе постигне консензус.
Поформално, можеме да дефинираме консензус алгоритам (или едноставно консензус алгоритам) како одредена функција која го пренесува дистрибуираниот систем од состојбата А во состојбата Б. Покрај тоа, оваа состојба е прифатена од сите јазли и сите јазли можат да ја потврдат. Како што се испоставува, оваа задача воопшто не е толку тривијална како што изгледа на прв поглед.
Својства на алгоритмот за консензус
Алгоритмот за консензус мора да има три својства за системот да продолжи да постои и да има одреден напредок во движењето од состојба во состојба:
- Договор – сите јазли кои правилно работат мора да ја имаат истата вредност (во написите ова својство се нарекува и безбедносно својство). Сите јазли кои моментално функционираат (не успеале или изгубиле контакт со другите) мора да се договорат и да прифатат некоја конечна заедничка вредност.
Овде е важно да се разбере дека јазлите во дистрибуираниот систем што го разгледуваме сакаат да се договорат. Односно, сега зборуваме за системи во кои нешто едноставно може да пропадне (на пример, некој јазол пропаѓа), но во овој систем дефинитивно нема јазли кои намерно работат против други (задачата на византиските генерали). Поради ова својство, системот останува конзистентен.
- Интегритет — ако сите правилно работат јазли нудат иста вредност v, што значи дека секој правилно оперативен јазол мора да ја прифати оваа вредност v.
- Престанок – сите правилно оперативни јазли на крајот ќе добијат одредена вредност (својство на живост), што му овозможува на алгоритмот да напредува во системот. Секој поединечен јазол што правилно работи мора порано или подоцна да ја прифати конечната вредност и да ја потврди: „За мене, оваа вредност е вистинита, се согласувам со целиот систем“.
Пример за тоа како функционира алгоритмот за консензус
Додека својствата на алгоритмот можеби не се целосно јасни. Затоа, со пример ќе илустрираме низ кои фази минува наједноставниот алгоритам за консензус во систем со модел на синхрони пораки, во кој сите јазли функционираат како што се очекува, пораките не се губат и ништо не се крши (дали ова навистина се случува?).
- Сè започнува со предлог за брак (Проложи). Да претпоставиме дека клиентот се поврзал со јазол наречен „Јазол 1“ и започнал трансакција, пренесувајќи нова вредност на јазолот - О. Отсега ќе го нарекуваме „Јазол 1“ понуда. Како предлагач, „Јазол 1“ сега мора да го извести целиот систем дека има свежи податоци и испраќа пораки до сите други јазли: „Гледај! Значењето „О“ ми дојде и сакам да го запишам! Ве молиме потврдете дека ќе снимите и „О“ во вашиот дневник“.
- Следната фаза е гласање за предложената вредност (Гласање). За што е? Може да се случи други јазли да добијат понови информации и да имаат податоци за истата трансакција.
Кога јазолот „Јазол 1“ го испраќа својот предлог, другите јазли ги проверуваат своите дневници за податоци за овој настан. Доколку нема противречности, јазлите објавуваат: „Да, немам други податоци за овој настан. Вредноста „О“ е најновата информација што ја заслужуваме“.Во секој друг случај, јазлите можат да одговорат на „Јазол 1“: „Слушај! Имам понови податоци за оваа трансакција. Не „О“, туку нешто подобро“.
Во фазата на гласање, јазлите доаѓаат до одлука: или сите ја прифаќаат истата вредност, или еден од нив гласа против, што покажува дека има понови податоци.
- Ако кругот на гласање беше успешен и сите беа за, тогаш системот преминува во нова фаза - Прифаќање на вредноста. „Јазол 1“ ги собира сите одговори од другите јазли и известува: „Сите се согласија за вредноста „О“! Сега официјално изјавувам дека „О“ е нашето ново значење, исто за сите! Запишете го во вашата мала книга, не заборавајте. Запишете го во вашиот дневник!“
- Останатите јазли испраќаат потврда (Прифатено) дека ја запишале вредноста „О“; ништо ново не пристигнало во ова време (еден вид на двофазен обврзување). По овој значаен настан, сметаме дека дистрибуираната трансакција е завршена.
Така, консензуалниот алгоритам во едноставен случај се состои од четири чекори: предложи, гласај (гласање), прифати (прифати), потврди прифаќање (прифатено).
Ако во некој чекор не успеавме да постигнеме договор, тогаш алгоритмот започнува повторно, земајќи ги предвид информациите обезбедени од јазлите кои одбија да ја потврдат предложената вредност.
Алгоритам за консензус во асинхрон систем
Пред ова, сè беше мазно, бидејќи зборувавме за модел на синхрони пораки. Но, знаеме дека во современиот свет сме навикнати да правиме сè асинхроно. Како функционира сличен алгоритам во систем со модел на асинхрони пораки, каде што веруваме дека времето на чекање за одговор од јазол може да биде произволно долго (патем, неуспехот на јазол може да се смета и како пример кога еден јазол може да реагира произволно долго време).
Сега кога знаеме како во принцип функционира алгоритмот за консензус, прашање за оние љубопитни читатели кои стигнаа до тука: колку јазли во систем од N јазли со модел на асинхрони пораки може да пропаднат така што системот сепак може да постигне консензус?
Точниот одговор и оправдувањето стојат зад спојлерот.Точниот одговор е: 0. Ако дури и еден јазол во асинхрон систем не успее, системот нема да може да постигне консензус. Оваа изјава е докажана во теоремата на FLP, добро позната во одредени кругови (1985, Fischer, Lynch, Paterson, линк до оригиналот на крајот од статијата): „Неможноста да се постигне дистрибуиран консензус ако барем еден јазол не успее .“
Дечки тогаш имаме проблем, навикнати сме се да е асинхроно. И еве го. Како да продолжите да живеете?
Зборувавме само за теорија, за математика. Што значи „не може да се постигне консензус“, преведување од математички јазик во наш - инженерство? Тоа значи дека „не може секогаш да се постигне“, т.е. Има случај во кој консензус не е постигнат. Каков случај е ова?
Ова е точно прекршување на имотот на живост опишан погоре. Немаме заеднички договор, а системот не може да има напредок (не може да се заврши во одредено време) во случај кога немаме одговор од сите јазли. Затоа што во асинхрон систем немаме предвидливо време на одговор и не можеме да знаеме дали некој јазол паднал или само му треба долго време за да одговори.
Но, во пракса можеме да најдеме решение. Нека нашиот алгоритам може да работи долго време во случај на неуспеси (потенцијално може да работи на неодредено време). Но, во повеќето ситуации, кога повеќето јазли функционираат правилно, ќе имаме напредок во системот.
Во пракса, ние се занимаваме со делумно синхрони комуникациски модели. Делумна синхронија се подразбира на следниов начин: во општ случај, имаме асинхрон модел, но формално е воведен одреден концепт на „глобално време на стабилизација“ на одреден момент во времето.
Овој момент во времето можеби нема да дојде долго време, но мора да дојде еден ден. Виртуелниот будилник ќе ѕвони и од тој момент можеме да ја предвидиме временската делта за која ќе пристигнат пораките. Од овој момент, системот се претвора од асинхрон во синхрон. Во пракса, ние се занимаваме со токму такви системи.
Алгоритмот Паксос решава проблеми со консензус
е фамилија на алгоритми кои го решаваат консензуалниот проблем за делумно синхрони системи, што е предмет на можноста некои јазли да откажат. Авторот на Паксос е . Тој предложи формален доказ за постоењето и исправноста на алгоритмот во 1989 година.
Но, доказот се покажа дека е далеку од тривијален. Првата публикација беше објавена дури во 1998 година (33 страници) опишувајќи го алгоритмот. Како што се испостави, беше исклучително тешко да се разбере, а во 2001 година беше објавено објаснување на статијата, кое траеше 14 страници. Обемот на публикации е даден со цел да се покаже дека всушност проблемот на консензус не е нималку едноставен, а зад таквите алгоритми се крие огромен труд од најпаметните луѓе.
Интересно е што самиот Лесли Лампорт во своето предавање забележа дека во вториот објаснувачки напис има една изјава, еден ред (не прецизираше кој), што може да се толкува на различни начини. И поради ова, голем број модерни имплементации на Paxos не функционираат целосно правилно.
Деталната анализа на работата на Паксос би траела повеќе од една статија, па ќе се обидам многу накратко да ја пренесам главната идеја за алгоритмот. Во врските на крајот од мојата статија ќе најдете материјали за понатамошно нуркање во оваа тема.
Улоги во Паксос
Алгоритмот Паксос има концепт на улоги. Ајде да разгледаме три главни (има модификации со дополнителни улоги):
- Предлагачи (исто така може да се користат термините: лидери или координатори). Тоа се момците кои учат за некоја нова вредност од корисникот и ја преземаат улогата на лидер. Нивната задача е да започнат круг на предлози за нова вредност и да ги координираат понатамошните активности на јазлите. Покрај тоа, Паксос дозволува присуство на неколку лидери во одредени ситуации.
- Прифаќачи (Гласачи). Тоа се јазли кои гласаат за прифаќање или отфрлање на одредена вредност. Нивната улога е многу важна, бидејќи од нив зависи одлуката: во каква состојба ќе оди (или нема) системот по следната фаза од консензусниот алгоритам.
- Ученици. Јазли кои едноставно ја прифаќаат и пишуваат новата прифатена вредност кога состојбата на системот ќе се промени. Тие не носат одлуки, туку само ги добиваат податоците и можат да му ги дадат на крајниот корисник.
Еден јазол може да комбинира неколку улоги во различни ситуации.
Концептот на кворум
Претпоставуваме дека имаме систем на N јазли А од нив максимумот F јазлите може да пропаднат. Ако F јазлите не успеат, тогаш мора да имаме барем 2F+1 акцепторски јазли.
Ова е неопходно за да имаме секогаш мнозинство, дури и во најлошата ситуација, од „добри“ јазли кои работат правилно. Тоа е F+1 „добри“ јазли кои се договорија, а конечната вредност ќе биде прифатена. Во спротивно, може да дојде до ситуација кога нашите различни локални групи добиваат различни значења и не можат да се договорат меѓу себе. Затоа, ни треба апсолутно мнозинство за да го добиеме гласот.
Општата идеја за тоа како функционира алгоритмот за консензус на Паксос
Алгоритмот Паксос вклучува две големи фази, кои пак се поделени во два чекора:
- Фаза 1а: Подгответе се. Во текот на подготвителната фаза, лидерот (предлагачот) ги известува сите јазли: „Започнуваме нова фаза на гласање. Имаме нов круг. Бројот на оваа рунда е n. Сега ќе почнеме да гласаме“. Засега, едноставно известува за почеток на нов циклус, но не известува за нова вредност. Задачата на оваа фаза е да иницира нов круг и да ги информира сите за неговиот единствен број. Кружниот број е важен, тој мора да биде вредност поголема од сите претходни гласачки броеви од сите претходни лидери. Бидејќи, благодарение на кружниот број, другите јазли во системот ќе разберат колку се најнови податоците на лидерот. Веројатно е дека другите јазли веќе имаат резултати од гласањето од многу подоцнежните кругови и едноставно ќе му кажат на лидерот дека е зад времето.
- Фаза 1б: Ветување. Кога јазлите за прифаќање го добија бројот на новата фаза на гласање, можни се два исхода:
- Бројот n на новото гласање е поголем од бројот на кое било претходно гласање во кое учествувал прифаќачот. Потоа прифаќачот му испраќа ветување на лидерот дека нема да учествува во повеќе гласови со број помал од n. Ако прифаќачот веќе гласал за нешто (т.е. веќе прифатил некоја вредност во втората фаза), тогаш на своето ветување ја приложува прифатената вредност и бројот на гласовите во кои учествувал.
- Во спротивно, ако прифаќачот веќе знае за гласот со поголем број, може едноставно да го игнорира чекорот за подготовка и да не одговори на лидерот.
- Фаза 2а: Прифатете. Лидерот треба да чека одговор од кворумот (повеќето јазли во системот) и, ако се добие потребниот број одговори, тогаш има две опции за развој на настани:
- Некои од прифаќачите испратија вредности за кои веќе гласаа. Во овој случај, лидерот ја избира вредноста од гласот со максимален број. Да ја наречеме оваа вредност x, и таа испраќа порака до сите јазли како: „Прифати (n, x)“, каде што првата вредност е гласачкиот број од неговиот чекор за предлог, а втората вредност е она за што се собраа сите, т.е. вредноста за која всушност гласаме.
- Ако ниту еден од прифаќачите не испратил никакви вредности, туку тие едноставно ветиле дека ќе гласаат во овој круг, лидерот може да ги повика да гласаат за нивната вредност, вредноста за која тој стана лидер на прво место. Ајде да го наречеме y. Испраќа порака до сите јазли како: „Прифати (n, y)“, слично на претходниот исход.
- Фаза 2б: Прифатено. Понатаму, јазлите-прифаќачи, по добивањето на пораката „Прифати(...)“ од лидерот, се согласуваат со неа (испратете потврда до сите јазли дека се согласуваат со новата вредност) само ако не ветиле некоја (друга) ) водачот да учествува во гласањето со круг број n' > n, во спротивно го игнорираат барањето за потврда.
Ако мнозинството јазли одговориле на лидерот и сите ја потврдиле новата вредност, тогаш новата вредност се смета за прифатена. Ура! Ако мнозинството не се постигне или има јазли кои одбиле да ја прифатат новата вредност, тогаш сè започнува од почеток.
Вака функционира алгоритмот Паксос. Секоја од овие фази има многу суптилности, практично не разгледавме разни видови неуспеси, проблеми на повеќе лидери и многу повеќе, но целта на овој напис е само да го запознае читателот во светот на дистрибуирани компјутери на високо ниво.
Исто така, вреди да се напомене дека Paxos не е единствениот од ваков вид, има и други алгоритми, на пример, , но ова е тема за друга статија.
Врски до материјали за понатамошно проучување
Почетно ниво:
- , Прети Касиреди, блог-напис на Медиум
- , Ади Канчерла, блог напис на Медиум
- , Итаи Абрахам, блог
- , Итаи Абрахам, блог статија
Ниво на Лесли Лампорт:
- , Фишер, Линч и Патерсон, истражувачки труд, 1985 година
- , Лесли Лампорт, истражувачки труд, 1998 година
- , Лесли Лампорт, истражувачки труд, 2001 година
Извор: www.habr.com