Problema: consensul într-un sistem distribuit
Ai un cluster de $N$ servere. Unele pot pica, altele pot fi încete, mesajele se pot pierde. Cum faci ca toate serverele să cadă de acord asupra aceleiași valori (de exemplu, „cine e liderul curent" sau „care e următoarea operație de executat")?
Asta e problema consensului distribuit. Pare simplă, dar e surprinzător de grea. Imposibilă în anumite condiții (vezi Teorema CAP).
Paxos e prima soluție corectă demonstrată matematic, propusă de Leslie Lamport în 1989 (publicată oficial în 1998, după celebra lucrare "The Part-Time Parliament").
1. Modelul de sistem
Paxos presupune:
- Noduri care pot pica (crash failure) — nu presupunem comportament rău intenționat (Byzantine)
- Mesaje asincrone — pot fi pierdute, întârziate, reordonate
- Rețea — nu e garantată livrarea, dar mesajele nu sunt corupte
- Timp — nu avem timeout-uri globale (sistem asincron)
În acest model, FLP impossibility (Fischer, Lynch, Patterson, 1985) spune că niciun algoritm determinist nu poate garanta consensul într-un sistem asincron cu măcar un nod care poate pica. Paxos ocolește această limitare prin terminare probabilistică — în practică converge aproape sigur.
2. Rolurile în Paxos
Paxos definește trei roluri logice (un nod poate îndeplini mai multe simultan):
| Rol | Responsabilitate | |---|---| | Proposer | Propune valori și inițiază votul | | Acceptor | Votează și memorează valorile acceptate | | Learner | Învață rezultatul (valoarea aleasă) |
Arhitectura comunicării
Proposer Acceptor 1
│ │
│───── Prepare(n) ──────>│
│<──── Promise(n, v_k) ──│
│ │
│───── Accept(n, v) ────>│
│<──── Accepted(n) ──────│
│ │
│ │ ... către ceilalți acceptori
3. Algoritmul în detaliu
Paxos funcționează în două faze, fiecare cu două sub-faze:
Faza 1: Prepare / Promise
1a. Prepare
Proposer-ul alege un număr de propunere $n$ (strict crescător, unic per proposer) și trimite un mesaj Prepare(n) către toți acceptorii.
1b. Promise
Fiecare acceptor răspunde cu Promise(n) dacă:
- Nu a mai promis pentru un număr mai mare decât $n$ (dacă a promis deja pentru $n' > n$, ignoră sau răspunde cu
Nack)
În Promise, acceptorul include și cea mai recentă valoare acceptată (dacă există) și numărul propunerii pentru care a acceptat-o $(v_{acc}, n_{acc})$.
Moment cheie: Dacă un acceptor a acceptat deja o valoare, o trimite înapoi. Asta permite noului proposer să continue de unde au rămas alții, nu să propună ceva diferit.
Faza 2: Accept / Accepted
2a. Accept
Proposer-ul așteaptă Promise de la majoritatea acceptorilor (un quorum). Apoi:
- Dacă cel puțin un acceptor a returnat o valoare acceptată $(v_{acc})$, proposer-ul alege valoarea cu numărul de propunere cel mai mare
- Dacă niciun acceptor nu a returnat o valoare, proposer-ul poate alege propria valoare
Apoi trimite Accept(n, v) către toți acceptorii.
2b. Accepted
Acceptorul acceptă valoarea $v$ dacă nu a promis pentru un număr mai mare. Trimite Accepted(n) către proposer și către learners.
Când un learner primește Accepted de la un quorum pentru aceeași valoare, consensul e atins.
Pseudo-cod
// Proposer
function propose(v):
n = next_ballot_number()
// Faza 1
promises = send_prepare(n) // trimite la toti acceptorii
if count(promises) < majority:
retry with larger n
// Alege valoarea cu cel mai mare numar din promisiuni
v' = max_by_ballot(promises.values) | v
// Faza 2
accepts = send_accept(n, v')
if count(accepts) < majority:
retry with larger n
return v'
// Acceptor
state = { promised: 0, accepted: (0, null) }
function handle_prepare(n):
if n > state.promised:
state.promised = n
return Promise(state.accepted)
return Nack
function handle_accept(n, v):
if n >= state.promised:
state.promised = n
state.accepted = (n, v)
return Accepted
return Nack
4. Safe-ty vs Liveness
Paxos garantează:
Safe-ty (siguranță) — mereu adevărat
- Acord (Agreement): Doar o singură valoare poate fi aleasă
- Validitate (Validity): Valoarea aleasă a fost propusă de cineva
- Integritate (Integrity): Un nod nu poate învăța două valori diferite
Liveness (viabilitate) — în anumite condiții
- Dacă un număr suficient de noduri sunt funcționale
- Dacă rețeaua livrează mesaje în timp finit
- Și dacă nu apar conflicte infinite de propuneri
Problema: Dacă doi proposeri concurează, fiecare poate invalida propunerea celuilalt (crescând numărul la infinit). Asta e liveness failure — algoritmul nu progresează, deși e safe.
Soluția practică: Liderul (leader election) — un singur proposer activ la un moment dat. Raft face exact asta: alege un lider și apoi rulează Paxos simplificat.
5. Paxos în variante
Classic Paxos (descris mai sus)
O singură valoare per instanță. Pentru un log distribuit (ca în Raft), rulezi multiple instanțe de Paxos, una per intrare în log.
Multi-Paxos
Optimizare crucială: după ce un lider e ales, Faza 1 nu se mai execută pentru instanțele următoare. Liderul trimite direct Accept pentru noile valori.
Instanța 1: [Prepare] → [Promise] → [Accept] → [Accepted] (lider ales)
Instanța 2: [Accept] → [Accepted] (fără Prepare!)
Instanța 3: [Accept] → [Accepted]
...
Astasta reduce latența de la 2 RTT-uri la 1 RTT per valoare.
Fast Paxos
Proposer-ul trimite direct valoarea, fără Faza 1 — dar necesită un quorum mai mare.
Cheap Paxos
Majoritatea nodurilor pot fi „ieftine" (doar replici), iar un subset mic de noduri „scumpe" gestionează consensul.
Flexible Paxos
Desparte quorum-ul de Faza 1 de quorum-ul de Faza 2. Faza 1 poate necesita un quorum diferit de Faza 2, permițând configurații mai flexibile.
6. Paxos vs Raft
Raft e de fapt Paxos simplificat, nu un algoritm fundamental diferit:
| Aspect | Paxos | Raft | |---|---|---| | Inteligibilitate | Notoriu de greu de înțeles | Proiectat să fie didactic | | Lider | Optional (optimizare) | Obligatoriu (parte din algoritm) | | Faze | 2 faze (Prepare/Accept) | 2 faze (RequestVote/AppendEntries) | | Log | Instanțe independente | Log unic cu indici secvențiali | | Termeni | Numere de propunere (n) | Termeni (termeni) | | Commit | Implicit prin Accept | Explicit prin commit index | | Safe-ty | Aceeași | Aceeași |
Diferența reală: Raft adaugă ordinea log-ului și mecanism explicit de alegere a liderului — două lucruri pe care Paxos le lasă la latitudinea implementării.
7. Implementări celebre
| Sistem | Algoritm | Folosit în | |---|---|---| | Google Chubby | Paxos | GFS, Bigtable (lock service) | | Apache Zookeeper (Zab) | Paxos-like | Kafka, HBase, Hadoop | | etcd | Raft | Kubernetes | | Consul | Raft | Service discovery | | Apache Cassandra | Paxos (lightweight transactions) | Baze de date NoSQL | | Spanner | Paxos + TrueTime | Google Cloud Spanner | | Microsoft Azure Cosmos DB | Paxos | Cosmos DB |
Chubby e poate cea mai faimoasă implementare — Lamport însuși a fost implicat. Documentația spune:
"Chubby uses the Paxos algorithm to keep its replicas consistent. ... The implementation of Paxos in Chubby is fairly standard."
8. Provocări practice
Performanța
- Latența minimă: 2 RTT-uri pentru Classic Paxos, 1 RTT pentru Multi-Paxos
- Throughput: Limitata de lider (single proposer) și de quorum-ul de acceptori
- Pipelining: Multi-Paxos permite pipeline la fel ca Raft
Byzantine Paxos
Ce se întâmplă dacă nodurile pot fi rău intenționate (Byzantine faults)? PBFT (Practical Byzantine Fault Tolerance) extinde Paxos pentru acest scenariu — necesită 3f+1 noduri pentru a tolera f noduri byzantine.
Geo-distribuire
Când acceptorii sunt pe continente diferite:
- Latența e dominată de viteza luminii
- Quorum-urile trebuie să fie cât mai mici
- Flexible Paxos permite configurarea optimă a quorum-urilor
Concluzie
Paxos e poate cel mai important algoritm distribuit după cele fundamentale (sortare, căutare, rutare). A demonstrat că consensul e posibil într-o lume nesigură, și a stat la baza tuturor sistemelor distribuite moderne — de la baze de date la sisteme de fișiere, de la lock service la cloud.
Pentru o înțelegere aprofundată a contextului distribuit, vezi Teorema CAP și Baze de date: SQL, NoSQL.
Referințe
- Lamport, L. The Part-Time Parliament (ACM TOCS, 1998) — lucrarea originală Paxos
- Lamport, L. Paxos Made Simple (2001) — explicația accesibilă
- Chandra, T. et al. Paxos Made Live (PODC, 2007) — lecții de la implementarea Google Chubby
- Ongaro, D. & Ousterhout, J. In Search of an Understandable Consensus Algorithm (Raft, 2014)
- Howard, H. et al. Flexible Paxos: Quorum Intersection Revisited (2016)