Cel mai bun răspuns
Această lucrare oferă o explicație și o dovadă clar izbitoare: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Voi încerca să ofer un rezumat clar aici:
Scopul Algoritmul Paxos este ca un anumit număr de colegi să ajungă la un acord cu privire la o valoare. Paxos garantează că, dacă un coleg crede că o anumită valoare a fost convenită de o majoritate, majoritatea niciodată nu sunt de acord asupra unei valori diferite. Protocolul este conceput astfel încât orice acord trebuie prin majoritatea nodurilor. Orice încercare viitoare de acord, dacă are succes, trebuie să treacă și prin cel puțin unul dintre aceste noduri. Astfel: Orice nod care propune după ce a fost luată o decizie trebuie comunicați cu un nod în majoritate. Protocolul garantează că va învăța anterior ag pe baza valorii din acea majoritate.
Iată cum funcționează:
Să presupunem că avem 3 noduri, A, B și C. A ar dori să propună valoare „Foo”.
Algoritmul funcționează în 3 faze. La fiecare fază, trebuie să se ajungă la afirmarea majorității nodurilor.
Mai întâi, avem faza de pregătire. A trimite o pregătire cerere către A, B și C. Paxos se bazează pe numerele de ordine pentru atinge garanțiile sale. Solicitarea de pregătire solicită unui nod să promită: „Nu voi accepta niciodată o propunere cu un număr de ordine mai mic decât cel din solicitarea de pregătire”. Nodurile răspund cu orice valoare cu care au fost de acord anterior (dacă există). (Și acest lucru este extrem de important): Nodul A trebuie să propună valoarea pe care o primește cu cel mai mare număr de secvență. Această acțiune oferă garanția că valorile convenite anterior vor fi păstrate.
În continuare, avem faza de acceptare. A trimite o cerere de acceptare către A, B și C. Cererea de acceptare precizează: ” Acceptați foo? ” Dacă numărul de secvență însoțitor nu este mai mic decât cel promis anterior de nod sau a solicitat ca acesta să fi acceptat anterior, acesta va accepta noua valoare și numărul de ordine.
Dacă nodul A primește acceptă de la majoritatea nodurilor, se decide valoarea. Această rundă de Paxos nu va fi niciodată de acord cu o altă valoare.
A treia fază nu este strict necesară, dar este crucială optimizare în orice implementare Paxos productivă. După ce A primește majoritatea acceptărilor, trimite hotărât mesaje către A, B și C. Aceste mesaje informează toți colegii că a fost aleasă o valoare și accelerează sfârșitul procesului de decizie.
Fără acest mesaj, ceilalți colegi ar trebui să încerce să propună o valoare pentru a afla despre acord. În faza de pregătire, ar afla despre valoarea convenită anterior. Odată ce acordul a fost condus la încheiere, nodul ar recunoaște acordul.
Am analizat câteva aspecte cheie aici:
- Toate numerele de secvență trebuie să crească monoton și să fie unic pe nod . Adică, A și B nu pot trimite ambele un mesaj cu numărul de ordine k. Toate mesajele trimise în protocol includ numere de ordine. Un nod trebuie să urmărească cea mai mare solicitare de acceptare pe care a văzut-o, precum și cea mai mare valoare pe care a promis-o în faza de pregătire.
- Condiții de eșec. Este foarte posibil ca o rundă de Paxos să eșueze. În caz de eșec, un nod încearcă pur și simplu să propună din nou cu un număr de secvență mai mare.
- Condiții de terminare. Versiunea lui Paxos pe care am descris-o nu se termină neapărat. Câteva modificări sunt necesare pentru o dovadă formală a rezilierii.
Răspuns
Deoarece Paxos obține un consens, poate fi folosit și pentru a reproduce scrieri într-o bază de date distribuită în timp ce poate garanta ordinea consecventă a evenimentelor între toate nodurile dintr-un grup. Chubby by Google folosește Paxos pentru a servi fișiere puternic consistente. De aici rezultă confuzia. Care este atunci relația dintre sincronizarea vizualizării și paxos dacă ambele pot fi utilizate pentru replicare?
Puțină istorie: Lamport a introdus conceptul de replicare a mașinilor de stat la începutul anilor 80. Replicarea mașinii de stat înseamnă că un sistem livrează evenimente în aceeași ordine tuturor nodurilor și sunt procesate deterministic garantând stări consistente în toate nodurile din grup. Cu toate acestea, la momentul introducerii acestui concept, acesta presupunea tot felul de ipoteze, inclusiv rețeaua fiind sincronă.Deci, replicarea mașinii de stat a rămas doar un instrument teoretic, fără o utilizare practică. Sincronizarea vizualizării a fost introdusă în acest moment și a avut drept scop atingerea consecvenței, fără a face astfel de ipoteze. Ținta era să existe un sistem practic care să ofere astfel de garanții.
Publicarea lui Paxos s-a întâmplat în timp ce lucrarea privind sincronizarea vizualizării era în desfășurare. Paxos ar putea realiza replicarea mașinii de stat, deoarece replicile ar putea fi acum de acord asupra ordinii de execuție a cererilor clientului folosind acest algoritm de consens. Paxos nu a făcut nicio ipoteză despre rețea sincronă sau eșecuri. Paxos a furnizat, de asemenea, un protocol de apartenență la grup. Diferențele care au rămas acum între sincronizarea vizuală și Paxos au fost doar în modul în care au fost formulate abstractizările. Ambele oferă apartenență dinamică și gestionează eșecurile în mod similar. Diferențele sunt într-adevăr doar în model. Unele diferențe care pot fi evidențiate sunt:
- Sincronizarea virtuală are un protocol simplu de apartenență la grup în comparație cu Paxos. Sincronizarea virtuală rulează calitatea de membru al grupului ca serviciu separat.
- Paxos poate progresa în anumite cazuri de partiție în care sincronizarea virtuală se blochează.
- Sincronizarea virtuală este mai rapidă decât Paxosul contemporan.
Ambele sisteme au evoluate și convergente . Așa cum este astăzi, este foarte dificil să atragem diferențe semnificative între cele două.
Lalith explică în mod clar protocolul Virtual Synchrony și subliniază pe bună dreptate că Paxos sau orice altă variantă de consens poate fi utilizată în sincronizarea vizualizărilor. Paxos, în afară de consens, oferă apartenență la grup și alte caracteristici pe care sincronizarea virtuală le oferă deja. Deoarece atât sincronizarea virtuală, cât și Paxos oferă aceleași garanții și au fost dezvoltate în același timp, specificațiile sincroniei virtuale nu utilizează Paxos pentru consens. Modelul de sincronizare virtuală utilizează totuși protocolul de trimitere complet ordonat (cunoscut și sub numele de ABCAST) pentru a realiza difuzarea atomică și un alt protocol pentru actualizarea vizualizărilor de grup și acestea pot fi văzute ca variantă de consens pe care îl folosește.
S-ar putea să fie interesant de menționat faptul că modelul de runtime ISIS-2 combină modelul Paxos cu modelul de sincronizare virtuală, nu pentru consens, ci pentru luarea în considerare a apartenenței la grup ca serviciu separat în Paxos. Acest lucru face Paxos mai rapid în cazurile în care calitatea de membru nu se schimbă dinamic. Combinând sincronizarea virtuală și Paxos, ISIS2 poate sări peste anumiți pași pe care Paxos tipici trebuie să îi efectueze. În esență, Paxos și Virtual Synchrony sunt modele diferite pentru a obține aceeași funcționalitate și pot fi combinate între ele pentru a realiza variante sau optimizări.