Pojďme si to tedy představit. V pokoji je zamčeno 5 koček, a aby mohly jít vzbudit majitele, musí se na tom všichni společně shodnout, protože dveře mohou otevřít jen tak, že se o ně opře s pěti. Pokud je jedna z koček Schrödingerova kočka a ostatní kočky o jeho rozhodnutí nevědí, vyvstává otázka: "Jak to mohou udělat?"
V tomto článku vám jednoduše řeknu o teoretické složce světa distribuovaných systémů a principech jejich práce. A také povrchně zvážit hlavní myšlenku, která je základem Paxos'a.
Když vývojáři používají cloudové infrastruktury, různé databáze, pracují v clusterech velkého počtu uzlů, jsou si jisti, že data budou konzistentní, bezpečná a vždy dostupná. Ale kde jsou záruky?
Ve skutečnosti záruky, které máme, jsou záruky dodavatele. V dokumentaci jsou popsány takto: "Tato služba je celkem spolehlivá, má dané SLA, nebojte se, vše bude fungovat distribuované tak, jak očekáváte."
Máme tendenci věřit v to nejlepší, protože chytří strejdové z velkých firem nás ujistili, že vše bude v pořádku. Neptáme se sami sebe: proč to vlastně může vůbec fungovat? Existuje nějaké formální zdůvodnění správného fungování takových systémů?
Nedávno jsem šel do a byl tímto tématem velmi inspirován. Přednášky ve škole připomínaly spíše hodiny matematické analýzy než cokoli souvisejícího s počítačovými systémy. Ale přesně tak byly najednou prokázány nejdůležitější algoritmy, které používáme každý den, aniž bychom to tušili.
Většina moderních distribuovaných systémů používá konsensus algoritmus Paxos a jeho různé modifikace. Nejúžasnější na tom je, že platnost a v zásadě i samotnou možnost existence tohoto algoritmu lze dokázat jednoduše tužkou a papírem. V praxi se přitom algoritmus používá ve velkých systémech pracujících na velkém počtu uzlů v cloudu.
Lehká ilustrace toho, o čem bude řeč dále: problém dvou generálůPojďme se podívat na rozcvičku .
Máme dvě armády – červenou a bílou. Bílé jednotky sídlí v obleženém městě. Rudé jednotky vedené generály A1 a A2 se nacházejí na dvou stranách města. Úkolem zrzek je zaútočit na bílé město a zvítězit. Armáda každého rudého generála jednotlivě je však menší než armáda bílých.
Podmínky vítězství pro zrzky: oba generálové musí zaútočit současně, aby měli početní převahu nad bílými. K tomu se musí generálové A1 a A2 vzájemně dohodnout. Pokud zaútočí každý zvlášť, zrzky prohrají.
K vyjednávání si mohou generálové A1 a A2 posílat posly přes území bílého města. Posel může úspěšně dosáhnout spojeneckého generála nebo může být zachycen nepřítelem. Otázka: existuje mezi rusovlasými generály taková posloupnost komunikace (sekvence vysílání poslů z A1 do A2 a naopak z A2 do A1), ve které se zaručeně dohodnou na útoku v hodinu X. Zde zárukami se rozumí, že oba generálové budou mít jednoznačné potvrzení, že spojenec (jiný generál) zaútočí přesně ve stanovený čas X.
Předpokládejme, že A1 pošle posla k A2 se zprávou: "Zaútočme dnes o půlnoci!". Generál A1 nemůže zaútočit bez potvrzení od generála A2. Pokud posel z A1 došel, pak generál A2 pošle potvrzení se zprávou: "Ano, dnes naplníme bílé." Ale nyní generál A2 neví, zda jeho posel dosáhl nebo ne, nemá žádné záruky, zda útok bude simultánní. Nyní potřebuje generál A2 opět potvrzení.
Pokud popíšeme jejich komunikaci dále, ukáže se následující: bez ohledu na to, kolik cyklů výměny zpráv existuje, neexistuje způsob, jak oběma generálům zaručit, že jejich zprávy byly přijaty (za předpokladu, že kterýkoli z poslů může být zachycen).
Problém dvou generálů je skvělou ilustrací velmi jednoduchého distribuovaného systému, kde existují dva uzly s nespolehlivou komunikací. Nemáme tedy 100% záruku, že jsou synchronizované. O podobných problémech jen ve větším měřítku dále v článku.
Představení konceptu distribuovaných systémů
Distribuovaný systém je skupina počítačů (dále jen uzly), které si mohou vyměňovat zprávy. Každý jednotlivý uzel je nějaká autonomní entita. Uzel může zpracovávat úkoly sám o sobě, ale aby mohl komunikovat s ostatními uzly, potřebuje odesílat a přijímat zprávy.
Jak jsou zprávy konkrétně implementovány, jaké protokoly se používají - to nás v tomto kontextu nezajímá. Je důležité, aby si uzly distribuovaného systému mohly navzájem vyměňovat data zasíláním zpráv.
Samotná definice nevypadá příliš složitě, ale mějte na paměti, že distribuovaný systém má řadu atributů, které pro nás budou důležité.
Atributy distribuovaných systémů
- Konkurence – možnost výskytu simultánních nebo konkurenčních událostí v systému. Navíc budeme uvažovat, že události, ke kterým došlo na dvou různých uzlech, jsou potenciálně souběžné, dokud nebudeme mít jasné pořadí, ve kterém se tyto události odehrávají. A většinou ne.
- Žádné globální hodiny. Nemáme jasné pořadí událostí, protože chybí globální hodiny. V běžném světě lidí jsme zvyklí, že máme hodiny a čas absolutně. Všechno se mění, pokud jde o distribuované systémy. Dokonce i ultra přesné atomové hodiny se posouvají a jsou situace, kdy nemůžeme říct, která ze dvou událostí se stala první. Nemůžeme tedy spoléhat ani na čas.
- Nezávislé selhání systémových uzlů. Je tu další problém: něco se může pokazit jednoduše proto, že naše uzly nejsou věčné. Pevný disk může selhat, virtuální počítač v cloudu se může restartovat, síť může blikat a zprávy budou ztraceny. Navíc existují situace, kdy uzly fungují, ale zároveň pracují proti systému. Poslední třída problémů dokonce dostala samostatný název: problém . Nejoblíbenějším příkladem distribuovaného systému s takovým problémem je Blockchain. Ale dnes nebudeme uvažovat o této zvláštní třídě problémů. Nás budou zajímat situace, ve kterých může selhat právě jeden nebo více uzlů.
- Komunikační modely (modely zasílání zpráv) mezi uzly. Již jsme zjistili, že uzly komunikují výměnou zpráv. Existují dva známé modely zasílání zpráv: synchronní a asynchronní.
Modely komunikace mezi uzly v distribuovaných systémech
Synchronní model - víme jistě, že existuje konečná známá delta času, po kterou zpráva zaručeně dorazí z jednoho uzlu do druhého. Pokud tento čas vypršel a zpráva nedorazila, můžeme bezpečně říci, že uzel selhal. V takovém modelu máme předvídatelnou čekací dobu.
Asynchronní model – v asynchronních modelech předpokládáme, že doba čekání je konečná, ale neexistuje žádná časová delta, po které lze zaručit, že uzel selhal. Tito. doba čekání na zprávu z uzlu může být libovolně dlouhá. Toto je důležitá definice a budeme o ní mluvit dále.
Koncepce konsenzu v distribuovaných systémech
Před formálním definováním pojmu konsensus zvažte příklad situace, kdy jej potřebujeme, konkrétně − Replikace státního stroje.
Máme nějaký distribuovaný protokol. Chtěli bychom, aby byl konzistentní a obsahoval identická data na všech uzlech distribuovaného systému. Když se některý z uzlů naučí novou hodnotu, kterou se chystá zapsat do protokolu, jeho úkolem je nabídnout tuto hodnotu všem ostatním uzlům, aby se protokol aktualizoval na všech uzlech a systém se přepnul do nového konzistentního stavu. Zároveň je důležité, aby se uzly mezi sebou dohodly: všechny uzly se dohodly, že navrhovaná nová hodnota je správná, všechny uzly tuto hodnotu akceptují a pouze v tomto případě může každý přihlásit novou hodnotu.
Jinými slovy: žádný z uzlů nenamítal, že má aktuálnější informace, a navrhovaná hodnota byla nesprávná. Shoda mezi uzly a shoda na jediné správné přijaté hodnotě je v distribuovaném systému konsensus. Dále budeme hovořit o algoritmech, které umožňují distribuovanému systému dosáhnout konsensu se zárukou.
Formálněji můžeme konsenzuální algoritmus (nebo jednoduše konsenzuální algoritmus) definovat jako nějakou funkci, která převádí distribuovaný systém ze stavu A do stavu B. Navíc tento stav je akceptován všemi uzly a všechny uzly jej mohou potvrdit. Jak se ukazuje, tento úkol není vůbec tak triviální, jak se na první pohled zdá.
Vlastnosti konsenzuálního algoritmu
Algoritmus konsenzu musí mít tři vlastnosti, aby systém mohl nadále existovat a měl určitý pokrok v přechodu ze stavu do stavu:
- Dohoda – všechny správně fungující uzly musí mít stejnou hodnotu (v článcích se tato vlastnost vyskytuje také jako bezpečnostní vlastnost). Všechny uzly, které nyní fungují (nejsou mimo provoz a neztratily kontakt se zbytkem), se musí dohodnout a přijmout nějakou konečnou společnou hodnotu.
Zde je důležité pochopit, že uzly v distribuovaném systému, o kterých uvažujeme, se chtějí dohodnout. To znamená, že se nyní bavíme o systémech, ve kterých může prostě něco selhat (například některý uzel selže), ale v tomto systému rozhodně nejsou uzly, které by záměrně fungovaly proti jiným (úkol byzantských generálů). Díky této vlastnosti zůstává systém konzistentní.
- Integrita - pokud všechny správně fungující uzly nabízejí stejnou hodnotu v, takže každý správně fungující uzel musí tuto hodnotu přijmout v.
- Ukončení - všechny správně fungující uzly nakonec získají nějakou hodnotu (vlastnost živosti), která umožní algoritmu postupovat v systému. Každý jednotlivý uzel, který funguje správně, musí dříve nebo později přijmout výslednou hodnotu a potvrdit ji: "Pro mě je tato hodnota pravdivá, souhlasím s celým systémem."
Příklad toho, jak funguje konsensuální algoritmus
Zatímco vlastnosti algoritmu nemusí být zcela jasné. Proto si ukážeme na příkladu, jakými fázemi prochází nejjednodušší konsenzuální algoritmus v systému se synchronním modelem zasílání zpráv, ve kterém všechny uzly fungují podle očekávání, zprávy se neztrácejí a nic se nerozbije (opravdu se to děje?).
- Vše začíná návrhem k sňatku (Propose). Předpokládejme, že se klient připojí k uzlu s názvem „Uzel 1“ a zahájí transakci, přičemž uzlu předá novou hodnotu – O. Od této chvíle budeme volat „Uzel 1“ nabídka. Jak teď musí navrhovatel „Uzel 1“ oznámit celému systému, že má čerstvá data, a všem ostatním uzlům posílá zprávy: „Podívejte! Dostal jsem hodnotu "O" a chci si to zapsat! Potvrďte prosím, že do svého deníku zaznamenáte také „O“.
- Další fází je hlasování o navržené hodnotě (Voting). K čemu to je? Může se stát, že jiné uzly obdržely novější informace a mají data o stejné transakci.
Když uzel "Uzel 1" odešle svůj propus, ostatní uzly zkontrolují své protokoly, zda neobsahují data o této události. Pokud nedojde ke konfliktu, uzly oznámí: „Ano, pro tuto událost nemám žádná další data. Hodnota 'O' je nejaktuálnější informace, kterou si zasloužíme."V každém jiném případě mohou uzly odpovědět na „Uzel 1“: „Poslouchejte! Mám novější údaje o této transakci. Ne "Oh", ale něco lepšího."
Ve fázi hlasování uzly dospějí k rozhodnutí: buď všechny přijmou stejnou hodnotu, nebo jeden z nich hlasuje proti, což znamená, že má novější data.
- Pokud bylo hlasování úspěšné a všichni byli pro, pak se systém přesune do nové fáze – přijetí hodnoty (Accept). "Uzel 1" shromažďuje všechny odpovědi od ostatních uzlů a hlásí: "Všichni se shodli na hodnotě 'O'! Nyní oficiálně prohlašuji, že „O“ je náš nový význam, stejný pro všechny! Zapište si to do sešitu, nezapomeňte. Napište si do logu!"
- Zbytek uzlů posílá potvrzení (Accepted), že si zapsali hodnotu „O“, během této doby nepřišlo nic nového (jakýsi dvoufázový commit). Po této významné události považujeme distribuovanou transakci za dokončenou.
Algoritmus konsenzu se tedy v jednoduchém případě skládá ze čtyř kroků: navrhnout, hlasovat (hlasování), přijetí (přijmout), potvrzení přijetí (přijmout).
Pokud jsme v některém kroku nemohli dosáhnout shody, pak se algoritmus restartuje, přičemž se zohlední informace poskytnuté uzly, které odmítly potvrdit navrhovanou hodnotu.
Konsenzuální algoritmus v asynchronním systému
Předtím bylo vše hladké, protože šlo o model synchronního zasílání zpráv. Ale víme, že v moderním světě jsme zvyklí dělat všechno asynchronně. Jak podobný algoritmus funguje v systému s asynchronním modelem zasílání zpráv, kde se domníváme, že čekací doba na odpověď z uzlu může být libovolně dlouhá (mimochodem, selhání uzlu lze také považovat za příklad, kdy uzel může reagovat libovolně dlouho).
Nyní, když víme, jak v principu funguje konsenzuální algoritmus, je otázka pro ty zvídavé čtenáře, kteří dosáhli tohoto bodu: kolik uzlů v systému N uzlů s asynchronním modelem zpráv může klesnout, aby systém stále mohl dosáhnout konsensu ?
Správná odpověď a zdůvodnění spoileru.Správná odpověď je: 0. Pokud dojde k výpadku byť jen jednoho uzlu v asynchronním systému, systém nebude schopen dosáhnout konsensu. Toto tvrzení je dokázáno ve známé větě FLP (1985, Fischer, Lynch, Paterson, odkaz na originál na konci článku): „Nemožnost dosažení distribuovaného konsenzu, pokud selže alespoň jeden uzel.“
Kluci, tak to máme problém, jsme zvyklí, že je u nás všechno asynchronní. A je to tady. Jak dál žít?
Právě jsme mluvili o teorii, o matematice. Co znamená „shody nelze dosáhnout“ v překladu z matematického jazyka do našeho – inženýrství? To znamená, že „ne vždy lze dosáhnout“, tzn. existuje případ, kdy konsensu není možné dosáhnout. A co je to za případ?
To je právě výše popsané porušení vlastnosti živosti. Nemáme společnou dohodu a systém nemůže postupovat (nemůže skončit v konečném čase) v případě, že nemáme odpověď ze všech uzlů. Protože v asynchronním systému nemáme předvídatelnou dobu odezvy a nemůžeme vědět, zda je uzel mimo provoz, nebo jen trvá dlouho, než odpovídá.
V praxi ale můžeme najít řešení. Nechte náš algoritmus běžet po dlouhou dobu v případě selhání (potenciálně může běžet neomezeně dlouho). Ale ve většině situací, kdy většina uzlů funguje správně, budeme mít v systému pokrok.
V praxi se jedná o částečně synchronní komunikační modely. Částečný synchronismus je chápán následovně: v obecném případě máme asynchronní model, ale formálně je zaveden určitý koncept „globální doby stabilizace“ určitého okamžiku.
Tento okamžik nemusí přijít libovolně dlouho, ale jednoho dne přijít musí. Zazvoní virtuální budík a od té chvíle můžeme předpovídat časovou deltu, do které zprávy dosáhnou. Od tohoto okamžiku se systém změní z asynchronního na synchronní. V praxi se s takovými systémy zabýváme.
Algoritmus Paxos řeší problémy s konsensem
je rodina algoritmů, které řeší problém konsenzu pro částečně synchronní systémy za předpokladu, že některé uzly mohou selhat. Autorem Paxosu je . V roce 1989 navrhl formální důkaz existence a správnosti algoritmu.
Ukázalo se ale, že důkaz nebyl v žádném případě triviální. První publikace byla vydána teprve v roce 1998 (33 stran) popisující algoritmus. Jak se ukázalo, bylo to extrémně těžké na pochopení a v roce 2001 vyšlo vysvětlení k článku, který zabral 14 stran. Svazky publikací jsou uvedeny proto, aby ukázaly, že problém konsensu není ve skutečnosti vůbec jednoduchý a za takovými algoritmy se skrývá obrovská práce těch nejchytřejších lidí.
Je zajímavé, že sám Leslie Lampor ve své přednášce poznamenal, že ve druhém článku-vysvětlení je jeden výrok, jeden řádek (neupřesnil který), které lze interpretovat různě. A kvůli tomu velké množství moderních implementací Paxos nefunguje zcela správně.
Podrobná analýza práce Paxosu zabere více než jeden článek, takže se pokusím velmi stručně zprostředkovat hlavní myšlenku algoritmu. V odkazech na konci mého článku najdete materiály pro další ponor do tohoto tématu.
Role ve společnosti Paxos
Algoritmus Paxos má koncept rolí. Zvažte tři hlavní (existují úpravy s dalšími rolemi):
- Navrhovatelé (mohou být také výrazy: vedoucí nebo koordinátoři). To jsou kluci, kteří se od uživatele dozvědí o nějakém novém významu a převezmou roli vůdce. Jejich úkolem je zahájit kolo návrhů na novou hodnotu a koordinovat další akce uzlů. Paxos navíc umožňuje přítomnost několika vůdců v určitých situacích.
- Akceptátoři (voliči). Toto jsou uzly, které hlasují pro přijetí nebo odmítnutí konkrétní hodnoty. Jejich role je velmi důležitá, protože na nich závisí rozhodnutí: do jakého stavu systém přejde (nebo nepřejde) po další fázi konsenzuálního algoritmu.
- Žáci. Uzly, které jednoduše přijímají a zapisují novou přijatou hodnotu, když se stav systému změní. Nerozhodují, pouze přijímají data a mohou je předat koncovému uživateli.
Jeden uzel může kombinovat několik rolí v různých situacích.
Koncept kvora
Předpokládáme, že máme systém N uzly. A většina z nich F uzly mohou selhat. Pokud F uzly selžou, měli bychom mít alespoň 2F+1 akceptorové uzly.
To je nutné, abychom vždy, i v nejhorší situaci, měli většinu „dobré“, správně fungující uzly. To znamená F+1 "dobré" uzly, které souhlasily, a konečná hodnota bude přijata. V opačném případě může nastat situace, kdy různé místní skupiny budou nabývat různých významů a nebudou se mezi sebou schopny dohodnout. K vítězství v hlasování tedy potřebujeme absolutní většinu.
Obecná myšlenka algoritmu konsensu Paxos
Algoritmus Paxos předpokládá dvě velké fáze, z nichž každá je rozdělena do dvou kroků:
- Fáze 1a: Připravte se. Během přípravné fáze vedoucí (navrhovatel) informuje všechny uzly: „Zahajujeme novou fázi hlasování. Máme nové kolo. Číslo tohoto kola je n. Nyní začneme hlasovat." Zatím hlásí jen začátek nového cyklu, ale nehlásí novou hodnotu. Úkolem této fáze je zahájit nové kolo a informovat každého o jeho jedinečném čísle. Důležité je číslo kola, musí být větší než všechna předchozí hlasovací čísla od všech předchozích lídrů. Protože právě díky kulatému číslu ostatní uzly v systému pochopí, jak čerstvá jsou data vedoucího. Pravděpodobně další uzly již mají výsledky hlasování z mnohem pozdějších kol a jednoduše řeknou lídrovi, že je pozadu.
- Fáze 1b: Slib. Když akceptorské uzly obdrží číslo nové fáze hlasování, jsou možné dva výsledky:
- Počet n nového hlasování je větší než počet jakýchkoli předchozích hlasování, kterých se příjemce zúčastnil. Poté akceptant zašle vedoucímu slib, že se již nebude účastnit žádného hlasování s číslem menším než n. Pokud akceptant již pro něco hlasoval (tedy již ve druhé fázi nějakou hodnotu přijal), pak ke svému slibu připojí přijatou hodnotu a číslo hlasu, kterého se účastnil.
- V opačném případě, pokud příjemce již ví o vysokém počtu hlasů, může jednoduše ignorovat krok přípravy a neodpovědět vedoucímu.
- Fáze 2a: Přijmout. Vedoucí musí počkat na odpověď od kvora (většina uzlů v systému) a pokud obdrží požadovaný počet odpovědí, má dvě možnosti pro vývoj událostí:
- Někteří z příjemců předložili hodnoty, pro které již hlasovali. V tomto případě vedoucí vybere hodnotu z hlasování s nejvyšším číslem. Nazvěme tuto hodnotu x a všem uzlům pošleme zprávu takto: „Přijmout (n, x)“, kde první hodnota je hlasovací číslo z vlastního kroku Navrhnout a druhá hodnota je to, kvůli čemu se všichni shromáždili, tzn. hodnotu, pro kterou ve skutečnosti hlasujeme.
- Pokud žádný z akceptantů neposlal žádné hodnoty, ale prostě slíbil, že v tomto kole bude hlasovat, může je vůdce vyzvat, aby hlasovali pro svou hodnotu, hodnotu, pro kterou se vůbec stal lídrem. Říkejme tomu y. Všem uzlům pošle zprávu ve tvaru: "Přijmout (n, y)", analogicky s předchozím výsledkem.
- Fáze 2b: Přijato. Dále akceptorské uzly po obdržení zprávy „Accept (...)“ od vedoucího s tím souhlasí (zašlou všem uzlům potvrzení, že souhlasí s novou hodnotou), pouze pokud neslíbily nějaké (jiné) vedoucí účastnit se hlasování s číslem kola n' > njinak výzvu k potvrzení ignorují.
Pokud většina uzlů odpověděla vedoucí a všechny potvrdily novou hodnotu, pak se nová hodnota považuje za přijatou. Hurá! Pokud většina není zadaná nebo existují uzly, které odmítly přijmout novou hodnotu, vše začíná znovu.
Takto funguje algoritmus Paxos. Každá z těchto fází má mnoho jemností, prakticky jsme nezvažovali různé typy selhání, problémy více vedoucích a mnoho dalšího, ale účelem tohoto článku je pouze uvést čtenáře do světa distribuovaného počítání na nejvyšší úrovni.
Za zmínku také stojí, že Paxos není jediný svého druhu, existují i jiné algoritmy, např. , ale to je téma na jiný článek.
Odkazy na materiály pro další studium
Úroveň nováčka:
- , Preethi Kasireddy, článek na blogu Medium
- , Adi Kancherla, článek na blogu Medium
- Blog Ittai Abrahama
- , Ittai Abraham, článek na blogu
Úroveň Leslie Lamport:
- Fischer, Lynch a Paterson, výzkumná práce, 1985
- , Leslie Lamport, výzkumná práce, 1998
- , Leslie Lamport, výzkumná práce, 2001
Zdroj: www.habr.com