Nejlepší odpověď
Tento dokument poskytuje překvapivě jasné vysvětlení a důkaz: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Pokusím se zde poskytnout jasné shrnutí:
Cíl Algoritmus Paxos má pro určitý počet vrstevníků dosáhnout dohody o hodnotě. Paxos zaručuje, že pokud jeden vrstevník věří, že některá hodnota byla schválena většinou, většina nikdy se nedohodněte na jiné hodnotě. Protokol je navržen tak, aby každá dohoda musela jít prostřednictvím většiny uzlů. Jakékoli budoucí pokusy o dohodu, pokud budou úspěšné, musí také projít alespoň jedním z těchto uzlů. Tedy: Jakýkoli uzel, který navrhuje po dosažení rozhodnutí, musí komunikovat s uzlem ve většině. Protokol zaručuje, že se naučí dříve ag spoléhejte na hodnotu této většiny.
Funguje to takto:
Předpokládejme, že máme 3 uzly, A, B a C. A by chtělo navrhnout hodnota „Foo.“
Algoritmus pracuje ve 3 fázích. V každé fázi musí být dosaženo potvrzení z většiny uzlů.
Nejprve máme fázi přípravy. A odešle žádost o přípravu na A, B a C. Paxos se spoléhá na pořadová čísla dosáhnout svých záruk. Požadavek na přípravu požádá uzel, aby slíbil: „Nikdy nepřijmu žádný návrh s pořadovým číslem menším, než je v požadavku na přípravu.“ Uzly odpovídají jakoukoli hodnotou, se kterou již dříve souhlasily (pokud existují). (A je to kriticky důležité): Uzel A musí navrhnout hodnotu, kterou obdrží, s nejvyšším pořadovým číslem. Tato akce poskytuje záruku, že budou zachovány dříve dohodnuté hodnoty.
Dále máme fázi přijetí. A odešle žádost o přijetí na A, B a C. V žádosti o přijetí se uvádí: “ Přijímáte foo? “ Pokud doprovodné pořadové číslo není nižší než to, co uzel dříve slíbil nebo požádal, aby uzel dříve přijal, přijme novou hodnotu a pořadové číslo.
Pokud uzel A přijímá přijetí od většina uzlů, hodnota je rozhodnuta. Toto kolo Paxosu nikdy nesouhlasí s jinou hodnotou.
Třetí fáze není nezbytně nutná, ale je zásadní optimalizace v jakékoli realizované produkci Paxos. Poté, co A přijme většinu přijetí, odešle rozhodnuto zprávy A, B a C. Tyto zprávy informují všechny vrstevníky o tom, že byla zvolena hodnota, a urychlí konec rozhodovacího procesu.
Bez této zprávy by se ostatní kolegové museli pokusit navrhnout hodnotu, která by se o dohodě dozvěděla. V přípravné fázi se dozvěděli o dříve dohodnuté hodnotě. Jakmile byla dohoda uzavřena, uzel dohodu uznal.
Zde jsem přeložil několik klíčových otázek:
- Všechna pořadová čísla se musí monotónně zvyšovat a na každý uzel jedinečná . To znamená, že A a B nemohou oba odeslat zprávu se pořadovým číslem k. Všechny zprávy odeslané v protokolu obsahují pořadová čísla. Uzel musí sledovat nejvyšší požadavek na přijetí, který viděl, a také nejvyšší hodnotu, kterou slíbil ve fázi přípravy.
- Podmínky selhání. Je docela možné, že kolo Paxos selže. V případě selhání se jeden uzel jednoduše pokusí navrhnout znovu s vyšším pořadovým číslem.
- Podmínky ukončení. Verze Paxos, kterou jsem „popsal“, nemusí nutně končit. Pro formální důkaz ukončení je zapotřebí několik vylepšení.
Odpověď
Protože Paxos dosahuje konsensu, lze jej použít také k replikaci zápisů v distribuované databázi, protože může zaručit konzistentní pořadí událostí mezi všemi uzly ve skupině. Chubby by Google používá Paxos k poskytování silně konzistentních souborů. Odtud pramení zmatek. Jaký je potom vztah mezi synchronizací pohledu a paxos, pokud lze oba použít pro replikaci?
Malá historie: Lamport představil koncept replikace stavového stroje počátkem 80. let. Replikace stavového stroje znamená, že systém doručuje události ve stejném pořadí do všech uzlů a jsou zpracovávány deterministicky zaručujícím konzistentní stavy napříč všemi uzly ve skupině. V době, kdy byl tento koncept představen, však zahrnoval nejrůznější předpoklady, včetně synchronní sítě.Replikace stavového stroje tedy zůstala pouze teoretickým nástrojem bez praktického využití. Synchronizace pohledů byla zavedena v tomto bodě a byla zaměřena na dosažení konzistence tím, že neexistují žádné takové předpoklady. Cílem bylo mít praktický systém, který by takové záruky poskytoval.
K publikaci Paxos došlo, když probíhala práce na synchronizaci pohledu. Paxos by mohl dosáhnout replikace stavového stroje, protože repliky by se nyní mohly dohodnout na pořadí provádění požadavků klientů pomocí tohoto konsensuálního algoritmu. Paxos nevytvářel žádné předpoklady o synchronní síti nebo poruchách. Paxos také poskytl protokol o členství ve skupině. Rozdíly, které nyní zůstaly mezi synchronizací zobrazení a Paxosem, byly pouze ve způsobu, jakým byly formulovány abstrakce. Oba poskytují dynamické členství a zpracovávají selhání podobně. Rozdíly jsou opravdu jen v modelu. Některé rozdíly, které lze zvýraznit, jsou:
- Virtual Synchrony má ve srovnání s Paxosem jednoduchý protokol členství ve skupině. Virtuální synchronizace spouští členství ve skupině jako samostatnou službu.
- Paxos může dosáhnout pokroku v určitých případech oddílu, kde virtuální synchronizace blokuje.
- Virtuální synchronizace je rychlejší než současná Paxos.
Oba systémy se vyvinuly a sblížily . V současné podobě je velmi obtížné mezi nimi rozlišit významné rozdíly.
Lalith jasně vysvětluje protokol Virtual Synchrony a správně poukazuje na to, že pro synchronizaci zobrazení lze použít Paxos nebo jakoukoli jinou variantu konsensu . Paxos kromě konsensu poskytuje členství ve skupině a další funkce, které virtuální synchronizace již poskytuje. Protože virtuální synchronizace i Paxos poskytují stejné záruky a byly vyvinuty přibližně ve stejnou dobu, specifikace virtuální synchronizace nepoužívá Paxos ke konsensu. Virtuální synchronní model však používá k dosažení atomového vysílání úplně uspořádaný odesílací protokol (známý také jako ABCAST) a další protokol k aktualizaci skupinových zobrazení, které lze považovat za variantu konsensu používá.
Mohlo by být zajímavé poznamenat, že běhový model ISIS-2 kombinuje model Paxos s modelem virtuální synchronizace, nikoli kvůli konsensu, ale kvůli vyřazení členství ve skupině jako samostatné služby v Paxosu. Díky tomu je Paxos rychlejší v případech, kdy se členství dynamicky nemění. Kombinací Virtual Synchrony a Paxos je ISIS2 schopen přeskočit určité kroky, které typické Paxos musí provést. V podstatě jsou Paxos a Virtual Synchrony různé modely pro dosažení stejné funkčnosti a lze je navzájem kombinovat pro dosažení variant nebo optimalizací.