Paxos ve svém srdci je velmi jednoduchý

algoritmus Paxos, pokud je prezentován v prosté angličtině, je velmi jednoduchý. — Leslie Lamportová 2001

pokusím se vysvětlit jedinou vyhlášku Paxos způsobem, doufejme, že je to snadné pochopit.

do dnešního dne, IMO, přednáška Johna Ousterhouta o Paxosu je to stále nejlepší. Materiál v tomto příspěvku si těžce půjčuje z přednášky Prof. Ousterhouta. Se souhlasem Johna Ousterhouta, použil jsem některé z jeho diapozitivů, abych pomohl vysvětlit Paxos.

konsensus

Paxos jako protokol se snaží vyřešit problém konsensu. Jednoduše řečeno, snaží se vyřešit problém, že systém vybere pouze jednu hodnotu, když jeden nebo více serverů může navrhnout různé hodnoty.

příkladem skutečného světa by bylo něco jako volby. Lidé mohou volit jiného prezidenta. Ale může být vybrán pouze jeden prezident.

Paxos je navržen tak, aby se vypořádat s fail-stop/crash (non-byzantské) a zpráva zpoždění/ztráty. Také existuje požadavek na živost, aby byla některá navrhovaná hodnota nakonec vybrána, pokud je spuštěna většina serverů. Tím se zabrání nezajímavým řešením, jako je nikdy nepřijímat žádnou hodnotu. Pokud neuděláte nic, neuděláte nic špatného. Stejně tak nechcete, aby byl zvolen více než jeden prezident a chcete mít prezidenta nakonec tak dlouho, dokud lidé volí.

abych byl upřímný, myslím, že snaha použít hlasování jako příklad k vysvětlení Paxosu v původním Parlamentním dokumentu na částečný úvazek je velmi přirozená. Ale nějak to nefungovalo moc dobře. Lamport také sám v rozhovoru řekl, že je to totální selhání, což je nešťastné.

jediný akceptor

Screen-Shot-2018-11-13-at-11.17.43-PM
s clusterem serverů 2F+1, co se stane, když vždy vytvoříme jedno určité pole pro přijetí návrhů. A je vybrán jakýkoli návrh, který tato krabice přijme.

problém tohoto přístupu spočívá v tom, že jediné dolní pole může způsobit, že služba nebude k dispozici. Požadavek však říká, že služba musí být v provozu, pokud je spuštěna většina serverů (v tomto případěF+1).

Všimněte si, že se jedná o jediný hlavní replikační model. A to je přesně důvod, proč je prostoj nevyhnutelný při replikaci master-slave.

kvorum

takže pokud jeden akceptor nefunguje, možná bychom měli počkat, dokud více serverů nepřijme návrh, než požadujeme zvolenou hodnotu.

kolik?

pokud jsou akceptory pevné a je to <=F, opět se nám nepodaří tolerovat F havarované servery. Pokud akceptory mohou být libovolné servery a je to <=F, v clusteru 2F+1 serverů, můžeme mít dva různé návrhy, které jdou na dvě nesouvislé sady akceptorů, což způsobí, že budou vybrány dvě hodnoty.

takže počet akceptorů musí být >=F+1. Vzhledem k tomu, že čím méně akceptorů, tím lépe, pojďme s F+1. A mohou to být libovolné servery F+1 v clusteru.

již jsme dosáhli určitého pokroku! Pokud je jakýkoli návrh přijat servery F+1, je vybrán.

přijímání návrhů

nyní se podívejme, jak by se akceptátoři měli rozhodnout, zda návrh přijmou nebo ne.

přijmout pouze první návrh?
Screen-Shot-2018-11-13-at-11.17.27-PM

to by nefungovalo, protože můžeme skončit nikdy mít žádnou hodnotu vybrán jako v případě výše. To porušuje požadavek na živost.

nemá smysl říkat přijmout druhý návrh nebo něco podobného, protože nikdy nevíte, jestli někdy bude druhý návrh.

takže musíme přijmout první návrh, ale možná ne pouze první návrh.

přijmout všechny návrhy?
Screen-Shot-2018-11-13-at-11.31.11-PM
to by porušilo bezpečnostní požadavek, protože můžeme nakonec zvolit více než jednu hodnotu.

jádro

zde přichází trik, který je podle mě nejzajímavější částí Paxosu.

jakmile je zvolena hodnota, budoucí návrhy musí navrhnout stejnou hodnotu.

to znamená, že by byl zapotřebí dvoufázový protokol. V první fázi musí navrhovatelé zjistit, zda již byla vybrána nějaká hodnota. A navrhnout ve druhé fázi.

pokud jste veterán distribuovaného systému, musíte si již všimnout jednoho klíčového slova v předchozím příkazu. A je to “budoucnost”. Zkontroloval jsem čas a objednávku dříve. Distribuovaný systém je o objednávání. “budoucnost” zde znamená uspořádání (stane se před vztahem). Takže musíme objednat všechny návrhy. Pak v příkladu níže můžeme odmítnout red, protože víme, že blue je vybrán a red je starý návrh.

Screen-Shot-2018-11-13-at-11.39.37-PM

číslo hlasování

snadný způsob, jak objednat návrhy, je mít jedinečné číslo hlasování pro každý návrh ve formě <seq_id, server_id>. Aby bylo zaručeno objednání, seq_id musí přetrvávat křížový pád/restart. Takže musí být trvale uložen lokálně.

Paxos

nyní jsme všichni nastaveni tak, abychom popsali skutečný dvoufázový protokol Paxos. První fázi budeme nazývat fází prepare a druhou fází fází accept. prepare fáze slouží dvěma účelům v jednom zpáteční cestě.

  1. Zjistěte více o již zvolené hodnotě
  2. zabraňte akceptorům přijímat jakékoli starší návrhy (velmi podobně jako rezervní krok ve dvou fázích Commit)

Screen-Shot-2018-11-13-at-11.53.52-PM
akceptor musí trvale uložit několik věcí

  • minProposal
  • acceptedProposal
  • acceptedValue
    Všimněte si, že místo “vysílání na všechny servery”by mělo být” vysílání na alespoň servery F+1″. A navrhovatel by měl odeslat zprávu accept na stejnou sadu serverů F + 1 jako ve fázi přípravy.

podívejme se blíže na každý krok.

připravte fázi

v této fázi se navrhovatel snaží získat příslib od příjemce, že nepřijme žádné návrhy starší než jeho. Zároveň budou příjemci informovat navrhovatele, jaké hodnoty již byly dosud přijaty.

v krocích 3 a 4 navrhovatel změní svůj návrh na nejnovější přijatý návrh od akceptorů, se kterými hovořil. Zdá se, že je velmi konzervativní, protože byste mohli dostat přijatý návrh, který není vybrán, a navrhovatel se nakonec vzdá svého návrhu. Ale to je v pořádku, protože nám záleží jen na konsensu. V první fázi je pro navrhovatele těžké vědět, zda je vybrána hodnota nebo ne. Přijatá hodnota nemusí být vybrána. Zvolená hodnota však musí být přijata většinou serverů! A akceptoři odmítají starší návrhy (krok 6). Se dvěma invarianty víme, že poslední přijatý návrh vrácený k návrhu v první fázi byl buď již vybrán, nebo v tuto chvíli nebyla vybrána žádná hodnota. Ať tak či onak, je bezpečné navrhnout tuto hodnotu.

Proč sledovat minProposal?
v přípravné fázi mohou být dva závodní návrhy, zatímco dosud nebylo přijato nic. To znamená, že se oba přestěhují do fáze přijetí. Díky celkové objednávce, kterou máme pro všechny návrhy a požadavku F+1, alespoň jeden akceptor uvidí novější návrh a odmítne zprávu accept ze ztraceného / staršího návrhu. Invariant zde je minProposal >= acceptedProposal.

Screen-Shot-2018-11-14-at-12.28.11-AM

to je pravděpodobně nejzajímavější případ, protože druhý navrhovatel neviděl předchozí přijatou hodnotu a hodnota nebyla vybrána v době přípravné fáze. V takovém případě bude pokračovat a odešle accept(Y) na jiné servery. Protože S3 slíbil, že přijme návrhy až později než 4.5, odmítá X. Pokud nebudeme sledovat minProposal, X bude přijat S3. Pak by oba X a Y byly přijaty třemi servery a považovány za vybrané, což porušuje bezpečnostní požadavek.

tady to máte. Toto je jediná vyhláška Paxos. Jak již bylo řečeno, implementace Paxos se ukázala jako velmi těžká.

  1. Paxos jednoduché https://lamport.azurewebsites.net/pubs/paxos-simple.pdf ↩︎

  2. Parlament na částečný úvazek https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf ↩︎

  3. Paxos živě https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf ↩︎

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.