Paxos (počítačová věda) - Paxos (computer science)

Paxos je rodina protokolů pro řešení konsensu v síti nespolehlivých nebo omylných procesorů. Konsensus je proces odsouhlasení jednoho výsledku mezi skupinou účastníků. Tento problém se stává obtížným, když účastníci nebo jejich komunikace mohou zaznamenat selhání.

Konsensuální protokoly jsou základem pro přístup replikace stavového stroje k distribuovanému počítači, jak navrhl Leslie Lamport a průzkum provedl Fred Schneider . Replikace stavového stroje je technika pro převod algoritmu na distribuovanou implementaci odolnou proti chybám. Ad-hoc techniky mohou ponechat důležité případy selhání nevyřešené. Principiální přístup navržený Lamportem a kol. zajišťuje bezpečnou manipulaci se všemi případy.

Protokol Paxos byl poprvé předložen v roce 1989 a pojmenován podle fiktivního legislativního konsensuálního systému používaného na řeckém ostrově Paxos , kde Lamport napsal, že parlament musí fungovat „i když zákonodárci neustále bloudili dovnitř a ven z parlamentní komory“. Později byl publikován jako článek v časopise v roce 1998.

Rodina protokolů Paxos zahrnuje spektrum kompromisů mezi počtem procesorů, počtem zpoždění zpráv před učením dohodnuté hodnoty, úrovní aktivity jednotlivých účastníků, počtem odeslaných zpráv a typy selhání. Ačkoli žádný deterministický protokol shody tolerantní k chybám nemůže zaručit postup v asynchronní síti ( výsledek prokázaný v příspěvku Fischera , Lynche a Patersona ), Paxos zaručuje bezpečnost (konzistenci) a podmínky, které by mu mohly zabránit v pokroku, je obtížné provokovat.

Paxos se obvykle používá tam, kde je vyžadována trvanlivost (například pro replikaci souboru nebo databáze), kde by množství trvanlivého stavu mohlo být velké. Protokol se pokouší dosáhnout pokroku i v obdobích, kdy některý omezený počet replik nereaguje. Existuje také mechanismus pro zrušení trvale neúspěšné repliky nebo přidání nové repliky.

Dějiny

Toto téma předchází protokolu. V roce 1988 Lynch , Dwork a Stockmeyer prokázali řešitelnost konsensu v široké rodině „částečně synchronních“ systémů. Paxos má silnou podobnost s protokolem používaným pro dohodu při „replikaci viditelných razítek“, který poprvé publikovali Oki a Liskov v roce 1988, v kontextu distribuovaných transakcí. Bez ohledu na tuto předchozí práci nabízel Paxos obzvláště elegantní formalismus a zahrnoval jeden z prvních důkazů bezpečnosti pro protokol distribuované shody tolerantní k chybám.

Rekonfigurovatelné automaty mají silné vazby na předchozí práci na spolehlivých protokolů skupině výběrového vysílání, že členství podpora dynamická skupina, například Birma ‚s prací v roce 1985 a 1987 v podstatě synchronní gbcast protokolu. Gbcast je však neobvyklý v podpoře odolnosti a řešení selhání oddílů. Většina spolehlivých protokolů vícesměrového vysílání postrádá tyto vlastnosti, které jsou nutné pro implementace modelu replikace stavového stroje. Tento bod je zpracována ve stati Lamport , Malkhi a Zhou.

Protokoly Paxos jsou členy teoretické třídy řešení problému formalizovaného jako jednotná shoda se selháním selhání. Dolní hranice tohoto problému prokázali Keidar a Shraer. Derecho, softwarová knihovna C ++ pro replikaci stavových strojů v cloudovém měřítku, nabízí protokol Paxos, který byl integrován s virtuálním synchronním členstvím, které si spravujete sami. Tento protokol odpovídá hranicím optimality Keidar a Shraer a efektivně mapuje moderní hardware datového centra vzdáleného DMA (RDMA) (ale používá TCP, pokud RDMA není k dispozici).

Předpoklady

Aby se zjednodušila prezentace Paxosu, jsou následující předpoklady a definice výslovné. Techniky pro rozšíření použitelnosti jsou v literatuře známé a nejsou v tomto článku zahrnuty.

Procesory

  • Procesory pracují s libovolnou rychlostí.
  • Procesory mohou zaznamenat selhání.
  • Procesory se stabilním úložištěm se mohou po selhání znovu připojit k protokolu (podle modelu selhání při selhání).
  • Procesory nekomunikují, nelžou ani se jinak nepokoušejí rozvrátit protokol. (To znamená, že k byzantským selháním nedochází. Podívejte se na byzantský Paxos, kde najdete řešení, které toleruje selhání, která vyplývají z libovolného/zlomyslného chování procesů.)

Síť

  • Procesory mohou odesílat zprávy jakémukoli jinému procesoru.
  • Zprávy jsou odesílány asynchronně a jejich doručení může trvat libovolně dlouho.
  • Zprávy mohou být ztraceny, přeuspořádány nebo duplikovány.
  • Zprávy jsou doručovány bez poškození. (To znamená, že k byzantským selháním nedochází. Viz Byzantský Paxos o řešení, které toleruje poškozené zprávy, které vznikají z libovolného/škodlivého chování kanálů pro zasílání zpráv.)

Počet procesorů

Algoritmus konsensu může obecně dosáhnout pokroku pomocí procesorů, a to navzdory současnému selhání jakýchkoli procesorů: jinými slovy, počet nezávadných procesů musí být přísně vyšší než počet chybných procesů. Pomocí rekonfigurace však může být použit protokol, který přežije libovolný počet celkových selhání, pokud současně neselže více než F. U protokolů Paxos lze tyto rekonfigurace zpracovávat jako samostatné konfigurace .

Role

Paxos popisuje akce procesorů podle jejich rolí v protokolu: klient, akceptor, navrhovatel, žák a vůdce. V typických implementacích může jeden procesor hrát jednu nebo více rolí současně. To nemá vliv na správnost protokolu - je obvyklé sloučit role za účelem zlepšení latence a/nebo počtu zpráv v protokolu.

Klient
Klient vydá požadavek distribuovanému systému a čeká na odpověď . Například požadavek na zápis do souboru na distribuovaném souborovém serveru.
Akceptor (voliči)
Akceptory fungují jako „paměť“ protokolu odolná proti chybám. Akceptory jsou shromažďovány do skupin nazývaných Kvora. Jakákoli zpráva odeslaná příjemci musí být odeslána kvoru přijímačů. Jakákoli zpráva přijatá od přijímače je ignorována, pokud není od každého přijímače přijata kopie v kvoru.
Navrhovatel
Navrhovatel obhajuje požadavek klienta, pokouší se přesvědčit přijímače, aby na něm souhlasili, a jako koordinátor posune protokol vpřed, když dojde ke konfliktům.
Student
Studenti fungují jako replikační faktor pro protokol. Jakmile je žádost klienta odsouhlasena akceptory, může žák provést akci (tj. Provést požadavek a odeslat klientovi odpověď). Ke zlepšení dostupnosti zpracování lze přidat další studenty.
Vůdce
K dosažení pokroku Paxos vyžaduje významného navrhovatele (nazývaného vůdce). Mnoho procesů může věřit, že jsou vůdci, ale protokol zaručuje pokrok pouze v případě, že je nakonec vybrán jeden z nich. Pokud se dva procesy domnívají, že jsou vůdci, mohou protokol zablokovat nepřetržitým navrhováním konfliktních aktualizací. V tomto případě jsou však bezpečnostní vlastnosti stále zachovány.

Kvora

Kvora vyjadřují bezpečnostní (nebo konzistentní) vlastnosti Paxosu zajištěním toho, aby si alespoň některý přeživší procesor zachoval znalosti o výsledcích.

Kvora jsou definována jako podmnožiny sady akceptorů tak, že jakékoli dvě podmnožiny (tj. Jakákoli dvě kvora) sdílejí alespoň jednoho člena. Obvykle je kvorem jakákoli většina zúčastněných akceptorů. Například vzhledem k množině přijímačů {A, B, C, D} by většinovým kvorem byly jakékoli tři přijímače: {A, B, C}, {A, C, D}, {A, B, D} , {B, C, D}. Obecněji lze akceptorům přiřadit libovolné kladné váhy; v takovém případě může být Kvorum definováno jako jakákoli podskupina přijímačů se souhrnnou hmotností větší než polovina celkové hmotnosti všech přijímačů.

Číslo nabídky a dohodnutá hodnota

Každý pokus o definování dohodnuté hodnoty v se provádí s návrhy, které mohou, ale nemusí být přijímány Akceptory. Každý návrh je pro daného Navrhovatele jednoznačně očíslován. Například např. Každý návrh může mít formu (n, v) , kde n je jedinečný identifikátor návrhu a v je skutečná navrhovaná hodnota. Hodnotu odpovídající číslovanému návrhu lze vypočítat jako součást běhu protokolu Paxos, ale nemusí.

Vlastnosti bezpečnosti a živosti

Aby byla zaručena bezpečnost (také nazývaná „konzistence“), Paxos definuje tři vlastnosti a zajišťuje, že první dvě jsou vždy zadrženy, bez ohledu na typ selhání:

Platnost (nebo netrivialita )
Lze vybrat a naučit se pouze navrhované hodnoty.
Dohoda (nebo konzistence nebo bezpečnost )
Žádní dva odlišní žáci se nemohou naučit různé hodnoty (nebo nemůže být více než jedna rozhodovaná hodnota)
Ukončení (nebo živost)
Pokud byla navržena hodnota C, pak se žák L nakonec nějakou hodnotu naučí (pokud dostatečné množství procesorů zůstane bez závad).

Všimněte si toho, že Paxos není zaručeno, že skončí, a proto nemá vlastnost živosti. To podporuje výsledek Fischer Lynch Paterson nemožnosti (FLP), který uvádí, že protokol konzistence může mít pouze dva z hlediska bezpečnosti , životnosti a odolnosti proti chybám . Jelikož Paxos má za cíl zajistit odolnost proti chybám a zaručuje bezpečnost, nemůže také zaručit živost.

Typické nasazení

Ve většině nasazení Paxos působí každý zúčastněný proces ve třech rolích; Navrhovatel, přijímač a žák. To výrazně snižuje složitost zprávy, aniž by byla obětována správnost:

V Paxosu klienti posílají příkazy vedoucímu. Během normálního provozu vedoucí přijme klientský příkaz, přidělí mu nové číslo příkazu i a poté zahájí i tu instanci konsensuálního algoritmu odesláním zpráv do sady akceptorových procesů.

Sloučením rolí se protokol „sbalí“ do efektivního nasazení stylu klient-hlavní-replika, typické pro databázovou komunitu. Výhodou protokolů Paxos (včetně implementací se sloučenými rolemi) je záruka jeho bezpečnostních vlastností .

Tok zpráv typické implementace je popsán v části Multi-Paxos .

Základní Paxos

Tento protokol je nejzákladnějším z rodiny Paxos. Každá „instance“ (nebo „provedení“) základního protokolu Paxos rozhoduje o jediné výstupní hodnotě. Protokol probíhá v několika kolech. Úspěšné kolo má 2 fáze: fáze 1 (která je rozdělena na části a a b ) a fáze 2 (která je rozdělena na části a a b ). Viz níže popis fází. Pamatujte, že předpokládáme asynchronní model, takže např. Procesor může být v jedné fázi, zatímco jiný procesor může být v jiné.

Fáze 1

Fáze 1a: Připravte se

Navrhovatel vytvoří zprávu, kterou nazýváme „Připravte se“, která se identifikuje s číslem n . Všimněte si, že n není hodnota, která má být navržena a možná dohodnuta, ale pouze číslo, které jednoznačně identifikuje tuto počáteční zprávu navrhovatelem (má být zasláno akceptorům). Číslo n musí být větší než jakékoli číslo použité v kterékoli z předchozích zpráv Prepare tímto navrhovatelem. Potom pošle Připravit zprávu obsahující n k Quorum z akceptorů . Všimněte si, že zpráva Připravit obsahuje pouze číslo n (to znamená, že nemusí obsahovat např. Navrhovanou hodnotu, často označovanou v ). Navrhovatel rozhodne, kdo je v kvoru. Navrhovatel by neměl iniciovat Paxos, pokud nemůže komunikovat alespoň s kvorem přijímačů.

Fáze 1b: Slib

Kterýkoli z přijímačů čeká na zprávu Připravit od kteréhokoli z Navrhovatelů . Pokud Acceptor obdrží zprávu Prepare, musí se podívat na identifikační číslo n právě přijaté zprávy Prepare . Existují dva případy.
Pokud je n vyšší než každé předchozí číslo obdržené od některého z navrhovatelů od akceptora, musí příjemce přijmout navrhovateli zprávu, kterou nazýváme „slib“, aby ignoroval všechny budoucí návrhy s menším číslem než n . Pokud Akceptor v určitém okamžiku v minulosti přijal návrh, musí ve své odpovědi na Navrhovatele obsahovat číslo předchozího návrhu, řekněme m , a odpovídající přijatou hodnotu, řekněme w .
V opačném případě (to znamená, že n je menší nebo rovné jakémukoli předchozímu číslu nabídky přijatému od jakéhokoli Navrhovatele Akceptorem) může Akceptor ignorovat přijatý návrh. V tomto případě nemusí odpovídat, aby Paxos fungoval. Kvůli optimalizaci by však odeslání odmítnutí ( Nack ) navrhovateli řeklo, že může zastavit svůj pokus o dosažení konsensu s návrhem č .

Fáze 2

Fáze 2a: Přijmout

Pokud navrhovatel obdrží většinu slibů od kvora přijímajících, musí svému návrhu nastavit hodnotu v . Pokud jakýkoli přijímač dříve přijal jakýkoli návrh, pak pošle své hodnoty navrhovateli, který nyní musí nastavit hodnotu svého návrhu, v , na hodnotu spojenou s nejvyšším číslem návrhu hlášeným přijímači, nazvěme to z . Pokud žádný z přijímačů nepřijal návrh až do tohoto bodu, pak navrhovatel může zvolit hodnotu, kterou původně chtěl navrhnout, řekněme x .
Navrhovatel odešle zprávu Accept , (n, v) , kvoru uchazečů se zvolenou hodnotou pro její návrh v a číslem nabídky n (což je stejné jako číslo obsažené ve zprávě Prepare, která byla dříve odeslána Přijímače). Takže Accept zpráva je buď (N, V = Z) , nebo, v případě, žádný z akceptorů předtím přijal hodnotu, (N, V = x) .

Tato zpráva Přijmout by měla být interpretována jako „žádost“, jako v „Přijměte prosím tento návrh!“.

Fáze 2b: Přijato

Pokud se Acceptor obdrží potvrzovací zprávy (n, v) , z Navrhovatel, musí jej schválit tehdy a jen tehdy, pokud to není již slíbil (ve fázi 1b protokolu Paxos), aby v úvahu pouze návrhy, které mají identifikátor větší než n .
Pokud přijímač již neslíbil (ve fázi 1b) zvažovat pouze návrhy s identifikátorem větším než n , měl by zaregistrovat hodnotu v (právě přijaté zprávy Accept ) jako přijatou hodnotu (protokolu) a odeslat Přijatá zpráva navrhovateli a každému studentovi (což obvykle mohou být navrhovatelé sami).
Jinak může ignorovat zprávu nebo požadavek Přijmout.

Přijímač může přijímat více návrhů. K tomu může dojít, když jiný Navrhovatel, který si není vědom nové hodnoty, o které se rozhoduje, zahájí nové kolo s vyšším identifikačním číslem n . V takovém případě může Akceptor slíbit a později přijmout novou navrhovanou hodnotu, i když dříve přijal jinou. Tyto návrhy mohou mít dokonce různé hodnoty v případě určitých selhání. Protokol Paxos však zaručí, že se akceptoři nakonec dohodnou na jediné hodnotě.

Když kola selhávají

Kola se nezdaří, pokud více navrhovatelů odešle konfliktní zprávy Prepare , nebo když navrhovatel neobdrží kvórum odpovědí ( slibné nebo přijaté ). V těchto případech musí být zahájeno další kolo s vyšším číslem návrhu.

Paxos lze použít k výběru vůdce

Všimněte si, že navrhovatel v Paxosu by mohl navrhnout „Já jsem vůdce“ (nebo například „Navrhovatel X je vůdce“). Vzhledem k dohodě a zárukám platnosti Paxosu, pokud je přijato kvorem, je nyní navrhovatel znám jako vedoucí všech ostatních uzlů. To uspokojuje potřeby volby vůdce, protože existuje jeden uzel, který věří, že je vůdcem, a jeden uzel, o kterém je známo, že je vždy vůdcem.

Grafické znázornění toku zpráv v základním Paxosu

Následující diagramy představují několik případů/situací aplikace protokolu Basic Paxos. Některé případy ukazují, jak se protokol Basic Paxos vyrovnává se selháním určitých (nadbytečných) součástí distribuovaného systému.

Všimněte si toho, že hodnoty vrácené ve zprávě Slib jsou "null" při prvním podání návrhu (protože žádný Acceptor v tomto kole hodnotu předtím nepřijal).

Základní Paxos bez poruch

V níže uvedeném diagramu je 1 klient, 1 navrhovatel, 3 akceptoři (tj. Velikost kvora je 3) a 2 studenti (reprezentují 2 svislé čáry). Tento diagram představuje případ prvního kola, které je úspěšné (tj. Žádný proces v síti neselže). 

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,V)
   |         |<---------X--X--X------>|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Zde je V poslední z (Va, Vb, Vc).

Chybové případy v základním Paxosu

Nejjednoduššími chybovými případy jsou selhání přijímače (když kvórum přijímačů zůstává naživu) a selhání nadbytečného žáka. V těchto případech protokol nevyžaduje žádnou „obnovu“ (tj. Stále je úspěšný): nejsou vyžadována žádná další kola ani zprávy, jak je uvedeno níže (v následujících dvou diagramech/případech).

Základní Paxos, když Acceptor selže

V následujícím diagramu jeden z akceptorů v kvoru selže, takže velikost kvora se stane 2. V tomto případě je protokol Basic Paxos stále úspěšný. 

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |          |  |  !       |  |  !! FAIL !!
   |         |<---------X--X          |  |  Promise(1,{Va, Vb, null})
   |         X--------->|->|          |  |  Accept!(1,V)
   |         |<---------X--X--------->|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |          |  |

Základní Paxos, když nadbytečný žák selže

V následujícím případě jeden z (nadbytečných) žáků selže, ale protokol Basic Paxos je stále úspěšný. 

Client Proposer         Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,V)
   |         |<---------X--X--X------>|->|  Accepted(1,V)
   |         |          |  |  |       |  !  !! FAIL !!
   |<---------------------------------X     Response
   |         |          |  |  |       |

Základní Paxos, když navrhovatel selže

V tomto případě navrhovatel neuspěje po navržení hodnoty, ale před dosažením dohody. Konkrétně selže uprostřed zprávy Accept, takže hodnotu obdrží pouze jeden Acceptor kvora. Mezitím je zvolen nový vůdce (navrhovatel) (ale toto není podrobně uvedeno). Všimněte si, že v tomto případě existují 2 kola (kola probíhají svisle, shora dolů). 

Client  Proposer        Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{Va, Vb, Vc})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Leader fails during broadcast !!
   |      X------------>|  |  |       |  |  Accept!(1,V)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! NEW LEADER !!
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{V, null, null})
   |         X--------->|->|->|       |  |  Accept!(2,V)
   |         |<---------X--X--X------>|->|  Accepted(2,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Základní Paxos při konfliktu více navrhovatelů

Nejsložitější případ je, když se více navrhovatelů považuje za vůdce. Například aktuální vedoucí může selhat a později se obnovit, ale ostatní navrhovatelé již znovu vybrali nového vůdce. Zotavený vůdce se to ještě nenaučil a pokouší se zahájit jedno kolo v konfliktu se současným vůdcem. V níže uvedeném diagramu jsou znázorněna 4 neúspěšná kola, ale může jich být více (jak je naznačeno v dolní části diagramu). 

Client   Proposer       Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{null,null,null})
   |      !             |  |  |       |  |  !! LEADER FAILS
   |         |          |  |  |       |  |  !! NEW LEADER (knows last number was 1)
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{null,null,null})
   |      |  |          |  |  |       |  |  !! OLD LEADER recovers
   |      |  |          |  |  |       |  |  !! OLD LEADER tries 2, denied
   |      X------------>|->|->|       |  |  Prepare(2)
   |      |<------------X--X--X       |  |  Nack(2)
   |      |  |          |  |  |       |  |  !! OLD LEADER tries 3
   |      X------------>|->|->|       |  |  Prepare(3)
   |      |<------------X--X--X       |  |  Promise(3,{null,null,null})
   |      |  |          |  |  |       |  |  !! NEW LEADER proposes, denied
   |      |  X--------->|->|->|       |  |  Accept!(2,Va)
   |      |  |<---------X--X--X       |  |  Nack(3)
   |      |  |          |  |  |       |  |  !! NEW LEADER tries 4
   |      |  X--------->|->|->|       |  |  Prepare(4)
   |      |  |<---------X--X--X       |  |  Promise(4,{null,null,null})
   |      |  |          |  |  |       |  |  !! OLD LEADER proposes, denied
   |      X------------>|->|->|       |  |  Accept!(3,Vb)
   |      |<------------X--X--X       |  |  Nack(4)
   |      |  |          |  |  |       |  |  ... and so on ...

Multi-Paxos

Typické nasazení Paxosu vyžaduje nepřetržitý tok dohodnutých hodnot, které fungují jako příkazy k distribuovanému stavovému počítači. Pokud je každý příkaz výsledkem jedné instance protokolu Basic Paxos , dojde k významnému množství režie.

Pokud je vedoucí relativně stabilní, fáze 1 se stává zbytečnou. Je tedy možné přeskočit fázi 1 pro budoucí instance protokolu se stejným vedoucím.

Aby toho bylo dosaženo, je zahrnuto číslo kola I spolu s každou hodnotou, která je v každém kole zvýšena stejným vůdcem. Multi-Paxos snižuje bezchybné zpoždění zprávy (návrh na učení) ze 4 zpoždění na 2 zpoždění.

Grafické znázornění toku zpráv v systému Multi-Paxos

Multi-Paxos bez selhání

V následujícím diagramu je zobrazena pouze jedna instance (nebo „provedení“) základního protokolu Paxos s počátečním Leaderem (navrhovatelem). Všimněte si, že Multi-Paxos se skládá z několika instancí základního protokolu Paxos. 

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

kde V = poslední z (Va, Vb, Vc).

Multi-Paxos, když lze přeskočit fázi 1

V tomto případě následující instance základního protokolu Paxos (reprezentovaný I+1 ) používají stejného vedoucího, takže fáze 1 (těchto následných instancí základního protokolu Paxos), které se skládají z dílčích fází Připravit a Slíbit, je přeskočeno. Všimněte si, že Leader by měl být stabilní, tj. Neměl by se zhroutit ani změnit. 

Client   Proposer       Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Multi-Paxos, když jsou role sbaleny

Společné nasazení Multi-Paxos spočívá v sbalení role navrhovatelů, přijímačů a studentů na „servery“. Nakonec tedy existují pouze „Klienti“ a „Servery“.

Následující diagram představuje první „instanci“ základního protokolu Paxos, kdy jsou role Navrhovatele, Akceptora a Žáka sbaleny do jedné role, nazývané „Server“. 

Client      Servers
   |         |  |  | --- First Request ---
   X-------->|  |  |  Request
   |         X->|->|  Prepare(N)
   |         |<-X--X  Promise(N, I, {Va, Vb})
   |         X->|->|  Accept!(N, I, Vn)
   |         X<>X<>X  Accepted(N, I)
   |<--------X  |  |  Response
   |         |  |  |

Multi-Paxos, když jsou role sbaleny a vůdce je stabilní

V následujících instancích základního protokolu Paxos, se stejným vedoucím jako v předchozích instancích základního protokolu Paxos, lze fázi 1 přeskočit. 

Client      Servers
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N,I+1,W)
   |         X<>X<>X  Accepted(N,I+1)
   |<--------X  |  |  Response
   |         |  |  |

Optimalizace

Lze provést řadu optimalizací za účelem snížení počtu vyměněných zpráv, za účelem zlepšení výkonu protokolu atd. Některé z těchto optimalizací jsou uvedeny níže.

"Zprávy můžeme ukládat za cenu dalšího zpoždění zpráv tím, že máme jednoho význačného žáka, který informuje ostatní žáky, když zjistí, že byla zvolena hodnota. Přijímatelé pak odesílají přijaté zprávy pouze význačnému žákovi. Ve většině aplikací, role vedoucího a význačného žáka jsou vykonávány stejným zpracovatelem.
„Vedoucí může posílat své zprávy Připravte se a přijímejte! Jen kvoru akceptorů. Dokud všichni akceptoři v tomto kvoru fungují a mohou komunikovat s vůdcem a studenty, není potřeba, aby to přijímali akceptoři, kteří nejsou v kvoru, cokoliv.
"Akceptorům je jedno, jaká hodnota je zvolena. Jednoduše reagují na zprávy Připravit a přijmout! Zajistit, aby i přes neúspěchy bylo možné vybrat pouze jednu hodnotu. Pokud se však akceptor dozví, jaká hodnota byla zvolena, může ji uložit." hodnota ve stabilním úložišti a smaže všechny ostatní informace, které tam uložila. Pokud akceptor později obdrží zprávu Připravte nebo Přijmout! místo provedení akce Phase1b nebo Phase2b může jednoduše informovat vedoucího o zvolené hodnotě.
„Namísto odeslání Hodnota V, vůdce může poslat hash V některých akceptory ve svých Přijmout! Zpráv. Učící se naučí, že v se volí v případě, že obdrží předběžnou autorizaci zprávy buď v nebo jeho kontrolní součet z usnášeníschopnosti akceptorů, a alespoň jedna z těchto zpráv obsahuje spíše v než hash. Vůdce však může přijímat zprávy Promise, které mu sdělují hash hodnoty v, kterou musí použít ve své akci Phase2a, aniž by mu sdělil skutečnou hodnotu v. Pokud to stane se, vedoucí nemůže provést svou akci Phase2a, dokud nekomunikuje s nějakým procesem, který zná v. "
"Navrhovatel může zaslat svůj návrh pouze vedoucímu, nikoli všem koordinátorům. To však vyžaduje, aby výsledek algoritmu pro výběr vedoucího byl vyslán navrhovatelům, což může být drahé. Takže by bylo lepší nechat navrhovatel zašle svůj návrh všem koordinátorům. (V takovém případě musí pouze koordinátoři sami vědět, kdo je vůdce.)
„Místo toho, aby každý akceptor rozeslal přijaté zprávy každému studentovi, mohou akceptoři posílat své přijaté zprávy vedoucímu a vedoucí může informovat studenty, když byla zvolena hodnota. Tím se však přidává další zpoždění zprávy.
„Nakonec si všimněte, že fáze 1 je pro 1. kolo zbytečná. Vedoucí 1. kola může kolo zahájit odesláním zprávy Accept! S jakoukoli navrhovanou hodnotou.“

Levné Paxos

Levný Paxos rozšiřuje Basic Paxos tak, aby toleroval selhání F s hlavními procesory F+1 a pomocnými procesory F dynamickou rekonfigurací po každém selhání.

Toto snížení požadavků na procesor jde na úkor živosti; pokud příliš mnoho hlavních procesorů selže v krátkém čase, systém se musí zastavit, dokud pomocné procesory nebudou moci systém překonfigurovat. Během stabilních období se pomocné procesory neúčastní protokolu.

„S pouhými dvěma procesory p a q nemůže jeden procesor rozlišit selhání druhého procesoru od selhání komunikačního média. Je zapotřebí třetí procesor. Ten třetí procesor se však nemusí podílet na volbě posloupnosti příkazů. Musí proveďte akci pouze v případě, že p nebo q selže, poté nic neudělá, zatímco buď p nebo q pokračuje v provozu systému sám. Třetí procesor může být tedy malý/pomalý/levný nebo procesor primárně věnovaný jiným úkolům . "

Tok zpráv: Levné Multi-Paxos

Příklad zahrnující tři hlavní akceptory, jeden pomocný akceptor a velikost kvora tři, ukazující selhání jednoho hlavního procesoru a následnou rekonfiguraci: 

            {  Acceptors   }
Proposer     Main       Aux    Learner
|            |  |  |     |       |  -- Phase 2 --
X----------->|->|->|     |       |  Accept!(N,I,V)
|            |  |  !     |       |  --- FAIL! ---
|<-----------X--X--------------->|  Accepted(N,I,V)
|            |  |        |       |  -- Failure detected (only 2 accepted) --
X----------->|->|------->|       |  Accept!(N,I,V)  (re-transmit, include Aux)
|<-----------X--X--------X------>|  Accepted(N,I,V)
|            |  |        |       |  -- Reconfigure : Quorum = 2 --
X----------->|->|        |       |  Accept!(N,I+1,W) (Aux not participating)
|<-----------X--X--------------->|  Accepted(N,I+1,W)
|            |  |        |       |

Rychlý Paxos

Fast Paxos generalizuje Basic Paxos, aby omezil zpoždění zpráv od konce do konce. V Basic Paxos je zpoždění zprávy od požadavku klienta na učení 3 zpoždění zprávy. Fast Paxos umožňuje 2 zpoždění zpráv, ale vyžaduje, aby (1) byl systém složen z přijímačů 3f+ 1, aby tolerovaly až f závady (namísto klasických 2f+ 1), a (2) aby klient odeslal svůj požadavek na více destinací .

Intuitivně, pokud vůdce nemá žádnou hodnotu, kterou by mohl navrhnout, pak by klient mohl poslat Přijmout! zprávu přímo příjemcům. Akceptoři by reagovali stejně jako v základním Paxosu a posílali přijaté zprávy vedoucímu a každému studentovi, aby dosáhl dvou zpoždění zpráv od klienta k žákovi.

Pokud vedoucí detekuje kolizi, vyřeší kolizi odesláním Přijmout! zprávy pro nové kolo, které jsou přijímány jako obvykle. Tato koordinovaná metoda obnovy vyžaduje čtyři zpoždění zpráv od klienta k žákovi.

Ke konečné optimalizaci dochází, když vedoucí předem určí techniku ​​obnovy, což umožňuje akceptorům provést obnovu po kolizi sami. Nekoordinované zotavení po kolizi tedy může nastat ve třech zpožděních zpráv (a pouze ve dvou zpožděních zpráv, pokud jsou všichni studenti také přijímači).

Tok zpráv: Rychlý Paxos, nekonfliktní 

Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |

Tok zpráv: Rychlý Paxos, konfliktní návrhy

Konfliktní návrhy s koordinovaným vymáháním. Poznámka: protokol neurčuje, jak zpracovat zrušený požadavek klienta. 

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      X------->|->|->|->|      |  |  Accept!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

Konfliktní návrhy s nekoordinovaným vymáháním. 

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      X------->|->|->|->|      |  |  Any(N,I,Recovery)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

Tok zpráv: Rychlý Paxos s nekoordinovanou obnovou, sbalené role

(sloučené role Acceptor/Learner) 

Client         Servers
 |  |         |  |  |  |
 |  |         X->|->|->|  Any(N,I,Recovery)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V)
 X-----------?|-?|-?|-?|  Accept!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X<>X->|->|  Accepted(N,I,V)
 |  |         |<-|<-X<>X  Accepted(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |  |         X<>X<>X<>X  Accepted(N+1,I,W)
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |

Generalizovaný Paxos

Generalizovaný konsensus zkoumá vztah mezi operacemi replikovaného stavového stroje a protokolem konsensu, který jej implementuje. Hlavní objev zahrnuje optimalizace Paxosu, pokud by konfliktní návrhy mohly být použity v libovolném pořadí. tj. když jsou navrhované operace komutativní operace pro stavový stroj. V takových případech lze konfliktní operace akceptovat, čímž se vyhnete zpožděním nutným pro řešení konfliktů a znovu navrhnete odmítnuté operace.

Tento koncept je dále zobecněn na stále rostoucí sekvence komutativních operací, o kterých je známo, že jsou stabilní (a lze je tedy provést). Protokol sleduje tyto sekvence a zajišťuje, že všechny navrhované operace jedné sekvence jsou stabilizovány, než se jakákoli operace, která s nimi nedojíždí, stane stabilní.

Příklad

Aby se ilustroval generalizovaný Paxos, níže uvedený příklad ukazuje tok zpráv mezi dvěma souběžně prováděcími klienty a replikovaným stavovým strojem implementujícím operace čtení/zápisu přes dva odlišné registry A a B.

Tabulka komutativity
Číst) Napsat) Přečíst (B) Napsat (B)
Číst) Ne
Napsat) Ne Ne
Přečíst (B) Ne
Napsat (B) Ne Ne

Všimněte si, že Tmavě červená x.svgv této tabulce jsou uvedeny operace, které nejsou komutativní.

Možný sled operací: 

 <1:Read(A), 2:Read(B), 3:Write(B), 4:Read(B), 5:Read(A), 6:Write(A)>

Protože 5:Read(A)dojíždí s oběma 3:Write(B)a 4:Read(B), je jednou z možných permutací ekvivalentní předchozí objednávce následující: 

 <1:Read(A), 2:Read(B), 5:Read(A), 3:Write(B), 4:Read(B), 6:Write(A)>

V praxi dochází k dojíždění pouze tehdy, když jsou operace navrhovány souběžně.

Tok zpráv: Zobecněný Paxos (příklad)

Odpovědi se nezobrazují. Poznámka: Zkratky zpráv se liší od předchozích toků zpráv kvůli specifikám protokolu, viz úplná diskuse. 

Client      Leader  Acceptor       Learner
 |  |         |      |  |  |         |  |  !! New Leader Begins Round
 |  |         X----->|->|->|         |  |  Prepare(N)
 |  |         |<-----X- X- X         |  |  Promise(N,null)
 |  |         X----->|->|->|         |  |  Phase2Start(N,null)
 |  |         |      |  |  |         |  | 
 |  |         |      |  |  |         |  |  !! Concurrent commuting proposals
 |  X------- ?|-----?|-?|-?|         |  |  Propose(ReadA)
 X-----------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         X------X-------------->|->|  Accepted(N,<ReadA,ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! No Conflict, both accepted
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Concurrent conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(<WriteB,ReadA>)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N,<WriteB,ReadA> . <ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB> . <WriteB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Conflict detected, leader chooses
 |  |         |      |  |  |         |  |  commutative order:
 |  |         |      |  |  |         |  |  V = <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+1,V)
 |  |         |<-----X- X- X-------->|->|  Accepted(N+1,V)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  | !! More conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(WriteA)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadA)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N+1,<WriteA> . <ReadA>)
 |  |         |<--------X- X-------->|->|  Accepted(N+1,<ReadA> . <WriteA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Leader chooses order:
 |  |         |      |  |  |         |  |  W = <WriteA, ReadA>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+2,W)
 |  |         |<-----X- X- X-------->|->|  Accepted(N+2,W)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB> .
 |  |         |      |  |  |         |  |           <WriteA, ReadA>
 |  |         |      |  |  |         |  |

Výkon

Výše uvedený tok zpráv nám ukazuje, že generalizovaný Paxos může využít sémantiku operací, aby se vyhnul kolizím, když selže spontánní uspořádání sítě. To umožňuje, aby byl protokol v praxi rychlejší než Fast Paxos. Když však dojde ke kolizi, generalizovaný Paxos potřebuje k obnovení dva další zpáteční lety. Tato situace je znázorněna operacemi WriteB a ReadB ve výše uvedeném schématu.

V obecném případě jsou takové okružní jízdy nevyhnutelné a pocházejí ze skutečnosti, že během kola lze přijmout více příkazů. V případě častých konfliktů je proto protokol dražší než Paxos. Naštěstí jsou možná dvě možná upřesnění Generalized Paxos, která mohou zkrátit dobu obnovy.

  • Za prvé, je -li koordinátor součástí každého kvora akceptorů (kolo N se říká střed ), pak se v kole N+1 vzpamatuje ze srážky v kole N, koordinátor přeskočí fázi 1 a ve fázi 2 navrhne posloupnost, kterou přijal jako poslední. během kola N. Tím se sníží náklady na zotavení na jeden zpáteční let.
  • Za druhé, pokud obě kola N a N+1 používají jedinečné a identické centrované kvorum, když akceptor detekuje kolizi v kole N, spontánně navrhne v kole N+1 sekvenci doplňující obě (i) ​​sekvenci přijatou v kole N koordinátor a (ii) největší nekonfliktní předpona, kterou přijal v kole N. Pokud například koordinátor a akceptor přijali v kole N <WriteB, ReadB> a <ReadB, ReadA>, akceptor spontánně přijme < WriteB, ReadB, ReadA> v kole N+1. U této varianty jsou náklady na obnovu zpoždění jedné zprávy, což je zjevně optimální. Zde si všimněte, že použití jedinečného kvora v jednom kole nepoškozuje život. Vyplývá to ze skutečnosti, že jakýkoli proces v tomto kvoru je čtením kvora pro přípravnou fázi dalších kol.

Byzantský Paxos

Paxos lze také rozšířit tak, aby podporoval libovolné selhání účastníků, včetně lhaní, vytváření zpráv, tajných dohod s jinými účastníky, selektivní neúčasti atd. Tyto typy selhání se nazývají byzantské selhání , podle řešení propagovaného společností Lamport.

Byzantský Paxos představený Castrem a Liskovem přidává další zprávu (Ověřit), která slouží k šíření znalostí a ověřování činností ostatních procesorů:

Tok zpráv: Byzantský Multi-Paxos, ustálený stav 

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |          X<>X<>X       |  |  Verify(N,I,V) - BROADCAST
   |         |<---------X--X--X------>|->|  Accepted(N,V)
   |<---------------------------------X--X  Response(V)
   |         |          |  |  |       |  |

Rychlý byzantský Paxos zavedený Martinem a Alvisim toto extra zpoždění odstraní, protože klient odesílá příkazy přímo přijímačům.

Všimněte si, že přijatá zpráva v Fast Byzantine Paxos je odeslána všem přijímačům a všem studentům, zatímco Fast Paxos odesílá přijaté zprávy pouze studentům):

Tok zpráv: Rychlý byzantský Multi-Paxos, ustálený stav 

Client    Acceptor     Learner
   |      |  |  |       |  |
   X----->|->|->|       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  |       |  |

Scénář selhání je pro oba protokoly stejný; Každý žák čeká na přijetí F+1 identických zpráv od různých přijímačů. Pokud k tomu nedojde, uvědomí si to i samotní přijímači (protože si ve vysílacím kole navzájem vyměnili zprávy) a správní přijímači znovu vysílají dohodnutou hodnotu:

Tok zpráv: Rychlý byzantský Multi-Paxos, selhání 

Client    Acceptor     Learner
   |      |  |  !       |  |  !! One Acceptor is faulty
   X----->|->|->!       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,{V,W}) - BROADCAST
   |      |  |  !       |  |  !! Learners receive 2 different commands
   |      |  |  !       |  |  !! Correct Acceptors notice error and choose
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  !       |  |

Přizpůsobení Paxosu pro sítě RDMA

Se vznikem velmi vysokorychlostních spolehlivých sítí datových center, které podporují vzdálené DMA ( RDMA ), existuje značný zájem o optimalizaci Paxosu, aby se využilo vykládání hardwaru, ve kterém karta síťového rozhraní a síťové směrovače zajišťují spolehlivost a řízení zahlcení síťové vrstvy, což uvolňuje hostitelský procesor pro jiné úkoly. Knihovna Derecho C ++ Paxos je implementace Paxos s otevřeným zdrojovým kódem, která tuto možnost zkoumá.

Derecho nabízí jak klasický Paxos s trvanlivostí dat napříč sekvencemi úplného vypnutí/restartu, tak vertikální Paxos (atomové vícesměrové vysílání) pro replikaci v paměti a synchronizaci stavového stroje. Protokoly Paxos používané Derecho bylo třeba upravit tak, aby maximalizovaly asynchronní streamování dat a odstranily další zdroje zpoždění na kritické cestě vůdce. Díky tomu může Derecho udržovat plnou obousměrnou datovou rychlost RDMA. Na rozdíl od toho, ačkoli lze tradiční protokoly Paxos migrovat do sítě RDMA jednoduchým mapováním operací odesílání zpráv na nativní operace RDMA, ponechá to na kritické cestě zpoždění zpomalení. Ve vysokorychlostních sítích RDMA mohou být i malá zpoždění dostatečně velká, aby zabránila využití plné potenciální šířky pásma.

Produkční využití Paxosu

Viz také

Reference

externí odkazy