Cele două lecții anterioare au acoperit modelele de consistență (ce pot să vadă citirile) și timpul (cum să ordonăm evenimente). Ambele au presupus ceva ce încă nu am justificat: că sistemul poate lua decizii. Că un grup de replici se poate pune de acord pe o valoare, pe o ordine, pe un leader, pe o configurație. Fără acea capacitate, restul spectrului se prăbușește: nu poți oferi linearizabilitate fără o cale de a fi de acord pe care scriere a venit prima, nu poți oferi replicare bazată pe leader fără o cale de a fi de acord pe leader, nu poți evolua membership-ul cluster-ului fără o cale de a fi de acord pe noul membership.
Numele tehnic pentru această capacitate e consensus. Să faci un grup de noduri să fie de acord pe o singură valoare, chiar și când unele sunt lente, lipsă sau spun minciuni, e problema dificilă canonică a sistemelor distribuite. Există rezultate de imposibilitate bine cunoscute (FLP, în 1985, a demonstrat că niciun protocol asincron nu poate garanta atât safety cât și liveness chiar și cu un singur nod defectuos) și soluții bine cunoscute care funcționează în practică oricum (Paxos, Raft și o mică familie de verișori). Lecția asta acoperă cele două protocoale pe care chiar le vei întâlni în sistemele de producție și compromisurile care au făcut ca unul să-l înlocuiască în mare parte pe celălalt.
Ce e consensus și pentru ce-l folosim
Problema consensus-ului, formal: un grup de N noduri, fiecare propune o valoare. Protocolul trebuie să se termine cu fiecare nod nedefectuos hotărând pe aceeași valoare, iar acea valoare trebuie să fie una pe care a propus-o cineva. Protocolul trebuie să satisfacă două proprietăți:
- Safety. Toate nodurile nedefectuoase care decid, decid pe aceeași valoare. Sistemul nu se contrazice niciodată cu sine, nu commit-uie niciodată două valori diferite pentru același slot.
- Liveness. Protocolul se termină în cele din urmă, iar o valoare e decisă. Sistemul face progres.
Cele două sunt în tensiune. Un protocol care se oprește mereu la primul semn de problemă e safe dar nu live. Un protocol care alege mereu ceva, chiar când e nesigur, e live dar nu safe. Protocoalele de consensus din lumea reală garantează safety necondiționat și oferă liveness „când condițiile sunt destul de bune” (rețeaua merge în mare parte, o majoritate a nodurilor sunt sus, leader-ii nu sunt aleși și realeși într-o buclă). Ăsta e compromisul practic în jurul rezultatului de imposibilitate FLP.
De ce vrem consensus, în termeni concreți:
- Leader election. Multe sisteme sunt mai ușor de raționat când un nod e leader pentru un rol dat. Alegerea acelui leader și realegerea când leader-ul curent eșuează necesită consensus.
- Replicated logs. Un log susținut de consensus e fundația mașinilor de stare replicate: fiecare replică aplică aceeași secvență de operații în aceeași ordine și ajunge în aceeași stare. Aceasta e modalitatea standard de a construi o bază de date tolerantă la defecte.
- Distributed locks și leases. Când doi clienți se întrec pentru același lock, cineva trebuie să decidă cine l-a primit. Acea decizie e consensus.
- Configuration storage. Membership-ul cluster-ului, topologia, feature flag-urile. Orice unde „fiecare nod trebuie să fie de acord pe răspuns” trăiește într-un store susținut de consensus.
Aproape orice sistem distribuit fiabil pe care-l poți numi are un protocol de consensus în nucleu, chiar dacă materialul de marketing nu-l menționează. Kubernetes rulează pe etcd, care rulează Raft. Cloud Spanner rulează Multi-Paxos sub fiecare tablet. Kafka, de la îndepărtarea ZooKeeper, rulează propria variantă Raft numită KRaft. Protocolul e zidul portant.
Paxos
Primul algoritm care a rezolvat consensus-ul corect într-o rețea asincronă cu defecte de tip crash-stop. Leslie Lamport l-a descris într-un raport tehnic din 1989 sub o metaforă elaborată despre parlamentele grecești, apoi l-a publicat formal în 1998 ca „The Part-Time Parliament”. Metafora era menită să fie fermecătoare. A reușit mai ales să facă lucrarea greu de urmărit. Lamport însuși a scris o versiune mai simplă în 2001 numită „Paxos Made Simple”, care nu e ea însăși simplă.
Despuiat de metaforă, Paxos de bază funcționează astfel. Trei roluri: proposers (care vor să facă o valoare aleasă), acceptors (care formează un quorum și votează pe valori) și learners (care află ce a fost ales). Un nod joacă de obicei mai multe roluri. O rundă de Paxos are două faze.
Phase 1 (Prepare). Un proposer alege un număr de propunere unic și crescător n și trimite un mesaj „prepare” către o majoritate de acceptors. Fiecare acceptor care nu a promis ceva cu un număr mai mare răspunde cu o promisiune: „nu voi accepta nicio propunere cu un număr mai mic decât n”. Dacă acceptor-ul a acceptat deja o valoare într-o rundă anterioară, include acea valoare și numărul ei în răspuns.
Phase 2 (Accept). Dacă proposer-ul primește promisiuni de la o majoritate, alege o valoare de propus. Dacă vreun acceptor a raportat o valoare acceptată anterior, proposer-ul trebuie să propună acea valoare (mai exact, pe cea cu cel mai mare număr acceptat). Altfel, proposer-ul e liber să propună propria valoare. Apoi trimite o cerere „accept” cu valoarea aleasă. Dacă o majoritate de acceptors acceptă, valoarea e aleasă.
Protocolul garantează că odată ce o valoare e aleasă, nicio altă valoare nu poate fi aleasă pentru același slot. Demonstrația se bazează pe suprapunerea majorității: oricare două majorități de N acceptors trebuie să împartă cel puțin un acceptor, iar promisiunile și acceptările acelui acceptor suprapus impun proprietatea de safety.
Pentru un sistem cu o singură decizie asta e suficient. Sistemele reale au nevoie să ia o secvență de decizii: fiecare intrare în log-ul replicat e propria instanță de consensus. Rularea Paxos-ului de bază pentru fiecare intrare e corectă, dar scumpă (două round-trip-uri per decizie). Optimizarea e Multi-Paxos: alege un leader stabil, lasă leader-ul să sară peste Phase 1 pentru rundele următoare și plătește un round-trip per decizie în loc de două. Multi-Paxos e ce rulează efectiv sistemele de producție.
Multi-Paxos are o reputație. E corect, bine studiat și demonstrat la scară. E de asemenea considerat pe scară largă greu de implementat, greu de debug-uit și greu de predat. Mai multe echipe au publicat povești de război despre cum au greșit Paxos în moduri subtile: curse la leader election, bug-uri off-by-one în schema numerelor de propunere, schimbări de configurație care au violat suprapunerea de quorum.
Raft
Diego Ongaro și John Ousterhout, lucrând la Stanford, au scris o lucrare în 2014 intitulată „In Search of an Understandable Consensus Algorithm”. Teza lor era simplă: Paxos e corect, dar incapacitatea domeniului de a-l preda consistent e ea însăși un bug. Au proiectat Raft de la zero cu inteligibilitatea ca obiectiv principal. Lucrarea oferă aceleași garanții de safety și liveness ca Paxos, dar le prezintă într-un mod în care un inginer le poate citi o dată și implementa.
Raft face câteva alegeri ferme care simplifică protocolul.
Strong leadership. Raft are un leader în orice moment (decât dacă e o alegere în curs). Toate cererile clienților trec prin leader. Leader-ul e responsabil cu adăugarea în log și replicarea către followers. Nu există conceptul de „orice nod poate propune”; leader-ul propune, followers confirmă.
Trei roluri. Fiecare nod e într-una din trei stări la un moment dat: leader, follower sau candidate. Un follower primește heartbeat-uri de la leader și acceptă intrări în log. Un candidate e un nod care încearcă să devină leader. Un leader e nodul aflat în prezent la conducere. Tranzițiile de stare sunt clar definite: un follower devine candidate când nu mai aude de la leader, un candidate devine leader când câștigă o alegere, un leader se retrage când vede dovada unui term mai recent.
Numere de term. Raft împarte timpul în terms, fiecare începând cu o alegere. Un term e identificat de un întreg care crește monoton. Fiecare mesaj poartă un număr de term, iar orice nod care vede un term mai mare se retrage imediat la follower și își actualizează term-ul. Acest singur mecanism înlocuiește schema de numere de propunere a Paxos-ului și e mult mai ușor de raționat.
Log matching. Replicarea de log a Raft are un invariant puternic: dacă două log-uri sunt de acord pe intrarea de la indexul i, sunt de acord pe toate intrările până la i. Leader-ul impune asta trimițând intrări cu atât indexul cât și term-ul indexului anterior, iar followers resping orice intrare care nu se potrivește cu propria intrare anterioară. Asta face inconsistențele de log ușor de detectat și reparat.
Costul: Raft e ușor mai puțin flexibil decât Multi-Paxos în câteva scenarii avansate. Multi-Paxos poate, în principiu, să commit-uie intrări de log în afara ordinii, să grupeze decizii în moduri neobișnuite și să tolereze unele configurații pe care Raft le refuză. În practică, aproape niciun sistem de producție nu are nevoie de acea flexibilitate, iar simplitatea Raft a dominat.
O alegere de leader în Raft e exemplul canonic al cât de curat e protocolul. Followers rulează un timeout de alegere (randomizat între 150 și 300 milisecunde, de obicei). Dacă un follower expiră fără să fi auzit de la leader, își incrementează term-ul, votează pentru sine și cere fiecărui alt nod votul. Un nod votează pentru cel mult un candidate per term și doar dacă log-ul candidate-ului e cel puțin la fel de actual ca al său. Dacă un candidate primește o majoritate de voturi, devine leader și începe să trimită heartbeat-uri. Dacă doi candidates împart votul, ambii expiră și încearcă din nou cu un term nou.
sequenceDiagram
participant F1 as Follower 1
participant F2 as Follower 2
participant C as Candidate
Note over C: election timeout
Note over C: term = term + 1, vote for self
C->>F1: RequestVote(term, log info)
C->>F2: RequestVote(term, log info)
F1-->>C: VoteGranted
F2-->>C: VoteGranted
Note over C: majority received
Note over C: become Leader
C->>F1: AppendEntries (heartbeat)
C->>F2: AppendEntries (heartbeat)Diagrama capturează întreaga alegere în cinci schimburi de mesaje. Echivalentul Paxos, desenat cinstit, necesită o notă de subsol despre leader leases, ballot numbers și ce se întâmplă când doi proposers se întrec în Phase 1.
De ce Raft a înlocuit în mare parte Paxos
Schimbarea din industrie între aproximativ 2014 și 2020 e aproape în întregime despre costul de onboarding. Sistemele distribuite noi aleg Raft pentru că:
- Un inginer poate citi lucrarea Raft într-o după-amiază și poate implementa o versiune funcțională într-o săptămână. Paxos durează mult mai mult, iar prima implementare e de obicei subtil greșită.
- Raft are implementări de referință în fiecare limbaj major (implementarea Go din etcd, hashicorp/raft, raft-rs din tikv în Rust). Alegerea uneia gata făcute e o opțiune reală. Multi-Paxos are mai puține astfel de biblioteci, iar cele care există sunt strâns cuplate de sistemele lor părinte.
- Debug-ul Raft în producție e mai ușor pentru că mașina de stare e mică și invariantele sunt explicite. Debug-ul Paxos se reduce adesea la „ce numere de propunere erau în zbor când a eșuat leader-ul”.
Compromisul e suficient de mic în practică încât industria a votat cu picioarele. Multi-Paxos rămâne în sistemele mai vechi pentru că rescrierea unei implementări de consensus funcționale e riscantă și rareori merită. Sistemele noi aleg Raft.
Sisteme reale
Un tur scurt.
Construite pe Raft. etcd (creierul Kubernetes), Consul (catalogul de servicii și config store al HashiCorp), CockroachDB (fiecare range e propriul grup Raft), TiDB (același model), RethinkDB, Vault, Nomad, protocolul de alegere a replica set-ului MongoDB începând cu versiunea 3.2 (o variantă inspirată de Raft). Apache Kafka de la tranziția KRaft.
Construite pe Paxos sau o variantă Paxos. Google Spanner (Multi-Paxos per tablet). Google Chubby (serviciul original de lock care a inspirat ZooKeeper). Google Megastore. Apache ZooKeeper (care folosește Zab, o variantă Paxos optimizată pentru broadcasts ordonate). Microsoft Azure Cosmos DB (Multi-Paxos sub câteva din nivelele sale de consistență). Câteva sisteme interne Amazon.
Lista spune o poveste generațională. Google a construit pe Paxos în anii 2000 pentru că ăsta era cel mai bine înțeles algoritm la momentul respectiv. Următoarea generație de sisteme open-source, scrise în mare parte după 2014, a ales Raft din motivele de mai sus.
Costul de performanță
Consensus nu e gratuit. Fiecare operație commit-uită necesită un round-trip la o majoritate de noduri. Într-un cluster de cinci noduri, asta înseamnă să aștepți cel puțin trei confirmări. Pragul de latență e setat de cel mai lent nod din quorum, plus timpul de round-trip al rețelei.
Într-un cluster dintr-un singur datacenter, asta e în jur de 1 până la 2 milisecunde per commit. Între regiuni, poate fi 50 până la 200 milisecunde. De aceea sistemele de consensus cu throughput mare grupează agresiv: un leader care livrează 1000 de intrări de log într-un singur mesaj AppendEntries plătește costul unui round-trip pentru 1000 de decizii, nu 1000 de round-trip-uri. Batching-ul e ceea ce face Raft viabil la scară și e primul loc unde să te uiți când performanța consensus-ului e proastă.
Cealaltă pârghie e geografia. Un grup Raft cu membri pe trei continente va plăti latență la scară de continent la fiecare scriere. Arhitecții cărora le pasă atât de availability cât și de latență de obicei rulează mai multe grupuri Raft, fiecare ancorat la o singură regiune pentru scrierile sale, cu replicare cross-region gestionată în afara protocolului de consensus. „Geo-partitioning”-ul CockroachDB și plasarea la nivel de directory a Spanner sunt ambele versiuni ale acestei idei.
Închiderea buclei
Consensus e fundația fiecărui sistem distribuit fiabil. Fără el, nu poți oferi consistență linearizabilă, nu poți alege fiabil leader-i, nu poți evolua configurația cluster-ului în siguranță. Cu el, poți construi sisteme care supraviețuiesc defectelor de noduri, partițiilor și greșelilor de operator, cu costul unui round-trip per decizie și complexității operaționale a rulării unui quorum.
Următoarele două lecții acoperă ce se întâmplă când echipele încearcă să sară peste consensus și să construiască sisteme distribuite pe fundații mai slabe: modurile de eșec care rezultă și uneltele (gossip protocols, CRDTs, replicare leaderless) care există pentru cazurile unde consensus-ul ar fi prea scump. Să știi când să nu folosești consensus e la fel de important ca să știi cum să-l folosești.