Consistency models: strong, eventual, causal, monotonic

Prima reacție pe care o au majoritatea inginerilor la consistency, după una sau două prelegeri despre teorema CAP, e să o claseze ca pe un binar. Există consistency „strong”, unde sistemul se comportă ca o singură mașină, și există consistency „eventual”, unde sistemul are voie să mintă o vreme și apoi să recupereze. Strong e corect și lent. Eventual e rapid și ciudat. Alege unul.

Acest binar e greșit, iar greșeala contează. Sistemele reale oferă un spectru de garanții de consistency, iar majoritatea bazelor de date interesante îți permit să combini și să potrivești: strong pentru unele operații, mai slab pentru altele, cu butoane explicite. Dacă știi doar cele două capete, alegi între „prea scump” și „prea confuz” fără să-ți dai seama că există cinci sau șase stații utile între ele.

Lecția asta e harta. Vom parcurge spectrul de la cel mai puternic la cel mai slab, vom defini fiecare model suficient de precis încât să-ți poți da seama când e încălcat, apoi vom rula un singur exemplu concret (un coș de cumpărături) sub fiecare model și vom urmări ce se schimbă.

Spectrul

Există șase consistency models care merită cunoscute pe nume. Formează o ordine parțială: modelele mai puternice implică toate garanțiile celor mai slabe, motiv pentru care asta e o ierarhie și nu o listă de alternative.

Linearizable (strong consistency)

Sistemul se comportă ca și cum ar exista o singură copie a datelor și fiecare operație are efect la un moment unic în timp între momentul când a fost emisă și momentul când a returnat. Odată ce o scriere reușește, fiecare read ulterior, pe orice replică, vede acea scriere sau una mai târzie. Read-urile și scrierile apar în ordine de timp real.

Acesta e cel mai puternic model practic de consistency și cel mai scump. Pentru a livra linearizability între replici, sistemul trebuie să coordoneze fiecare scriere printr-un quorum, ceea ce costă cel puțin un round-trip către o majoritate de noduri. Într-o bază de date care se întinde peste regiuni, acel round-trip poate fi de 50 până la 200 de milisecunde. Linearizability interzice și trucuri precum servirea read-urilor dintr-o replică locală fără verificare, pentru că replica locală ar putea fi învechită.

Sisteme reale care oferă linearizability: Google Spanner (cu TrueTime, care e lecția următoare), etcd, Zookeeper, Postgres pe un singur nod în mod trivial, DynamoDB când ceri ConsistentRead=true.

Sequential consistency

Toate operațiile apar într-o ordine totală, aceeași la fiecare observator, dar ordinea nu trebuie să se potrivească timpului real. Dacă procesul A scrie X la 10:00:01 și procesul B scrie Y la 10:00:02, sequential consistency permite ca fiecare observator să vadă Y mai întâi atâta timp cât toată lumea vede Y mai întâi.

Asta e rară ca țintă de design în bazele de date moderne. Apare în manuale mai vechi, în hardware cu memorie partajată (modelele de memorie ale x86 și ARM sunt aproximativ sequential consistency pentru unele operații, mai slabe pentru altele) și ca pas în demonstrații. Cele mai multe cereri de „vreau un sistem strong” înseamnă de fapt linearizable.

Causal consistency

Dacă operația A a influențat cauzal operația B, fiecare observator vede A înainte de B. Operațiile fără relație cauzală pot fi observate în orice ordine. „Influențat cauzal” e definit prin schimb de mesaje: dacă A s-a întâmplat pe un nod, apoi B s-a întâmplat pe un nod care observase A, atunci A e cauză a lui B.

Causal consistency e cel mai puternic model care nu necesită coordonare la fiecare scriere. Replicile pot continua să accepte scrieri locale; trebuie doar să urmărească ce scrieri depind de care altele. Asta o face o țintă populară pentru sistemele care vor să se simtă corect pentru oameni fără să plătească taxa de coordonare a linearizability.

Exemplul clasic: un utilizator postează un status update, apoi un comentariu pe propriul update. Causal consistency garantează că oricine vede comentariul vede și postarea originală. Nu garantează că doi utilizatori fără legătură care postează în același timp apar în aceeași ordine pentru toată lumea.

Read-your-writes

După ce un client scrie X, read-urile ulterioare ale aceluiași client văd X (sau o valoare care îl înlocuiește pe X). Alți clienți nu primesc o astfel de garanție.

Acesta e un model la nivel de sesiune, nu unul global. E de obicei implementat prin direcționarea read-urilor unui client către replica care a tratat ultima sa scriere, sau prin transportarea unui cookie cu „last write timestamp” pe care calea de read îl folosește pentru a aștepta replicarea. Aproape orice aplicație de consum așteaptă asta fără să-și dea seama: când trimiți un formular, te aștepți să-ți vezi propria trimitere, chiar dacă încă nu s-a propagat în alte regiuni.

Monotonic reads

Odată ce un client a citit o valoare, read-urile ulterioare returnează acea valoare sau una mai nouă. Clientul nu vede niciodată timpul mergând înapoi.

Asta e și ea la nivel de sesiune. Modul de eșec pe care îl previne: un client citește din replica A și vede versiunea 5, apoi citește din replica B și vede versiunea 3. Fără monotonic reads, clientul pare că călătorește înapoi în timp, ceea ce strică starea UI, animațiile și încrederea utilizatorului. Monotonic reads e de obicei implementat prin afinitate de client (rămâi pe o replică) sau verificări de version-vector.

Eventually consistent

Dacă scrierile se opresc, toate replicile converg în cele din urmă către aceeași valoare. Nu există nicio garanție despre când, nicio garanție despre ordinea în care apar stările intermediare, nicio garanție despre ce văd read-urile individuale.

Acesta e cel mai slab dintre modelele numite. E și suficient pentru multe workload-uri reale: numărul de „vizualizări” pe un video, dimensiunea aproximativă a unei cozi, ultima locație cunoscută a unui curier de livrări. În fiecare caz, „răspunsul corect plus sau minus câteva secunde” e bine.

Un exemplu concret: coșul de cumpărături

Ia o singură utilizatoare, Alice, cu un coș de cumpărături într-un magazin replicat global. Replicile trăiesc în trei regiuni. Alice navighează de pe un telefon în Milano. Serverele aplicației magazinului direcționează cererile ei către replica cea mai apropiată.

Alice face trei lucruri în secvență:

Adaugă produsul X în coș.
Adaugă produsul Y în coș.
Scoate produsul X din coș.

Acum ia în considerare ce se întâmplă sub fiecare model când Alice (sau partenerul ei Bob, pe o replică diferită) citește coșul.

Linearizable. Orice read, de către oricine, după pasul 3 returnează „doar Y”. Read-urile luate între pași returnează stări de coș care se potrivesc cu timpul real: „X” după pasul 1, „X și Y” după pasul 2, „Y” după pasul 3. Costul: fiecare scriere așteaptă un quorum peste cele trei regiuni. Dacă regiunile sunt la continente distanță, fiecare add-to-cart durează 100 de milisecunde sau mai mult.

Causal. Read-urile văd operațiile în ordinea în care le-a făcut Alice: nimeni nu vede remove-X fără să fi văzut add-X. Dar doi utilizatori concurenți care adaugă produse într-un coș de familie partajat ar putea să vadă adăugările celuilalt în ordini diferite. Pentru un coș cu un singur utilizator, causal se simte indistinct de linearizable. Pentru un coș partajat, causal e modelul corect: păstrează intenția utilizatorului fără să plătească pentru ordonare globală.

Read-your-writes. Telefonul lui Alice îi vede schimbările imediat: add-X, apoi add-X-and-Y, apoi Y. Dacă Alice deschide coșul pe laptop, care direcționează către o replică diferită, ar putea vedea pe scurt coșul în starea sa anterioară. Bob, care se uită la același coș din Roma, ar putea vedea orice versiune a lui. Latency e mult mai mică decât linearizable; prețul e că alți observatori pot fi confuzi.

Monotonic reads. Alice nu vede niciodată coșul mergând înapoi. Dacă a văzut coșul cu produsele X și Y, nu va vedea, la următorul refresh, doar X. Dar ar putea să nu-și vadă imediat propria scoatere a lui X, dacă citește dintr-o replică ce încă nu a primit-o. Acest model exclude cel mai rău bug de UI („mi-a revenit produsul”), fără să rezolve problema actualității datelor.

Eventually consistent. Coșul va ajunge, în cele din urmă, într-o stare în care toată lumea e de acord. Între timp, orice e posibil: telefonul lui Alice ar putea arăta X și Y, laptopul ei ar putea arăta doar Y, iar Bob ar putea vedea un coș gol. După ce praful se așază, toate replicile converg. Latency e cea mai mică; experiența utilizatorului e cea mai proastă.

Ideea exemplului e că modelul corect de consistency nu e „cel mai puternic disponibil”. E cel mai slab model care nu produce bug-uri vizibile pentru workload-ul tău. Coșurile vor în mare parte causal plus read-your-writes. Soldurile bancare vor linearizable. Numărul de like-uri vrea eventually consistent.

Tabelul cost-beneficiu

Model	Read latency	Write latency	Coordonare	Bug-uri comune prevenite
Linearizable	Mare	Mare	Quorum la fiecare scriere, read-uri proaspete	Read-uri învechite, scrieri pierdute, călătorie în timp
Causal	Mică	Mică	Urmărire de dependențe, fără quorum	Efecte cauzale în ordine greșită
Read-your-writes	Mică	Mică	Routing per sesiune	„Unde s-a dus trimiterea mea?”
Monotonic reads	Mică	Mică	Afinitate per sesiune	„Datele mele s-au întors în timp”
Eventual	Cea mai mică	Cea mai mică	Niciuna	Aproape niciunul

Partea scumpă a modelelor mai puternice nu e algoritmul; e coordonarea. Fiecare garanție despre ce văd read-urile e plătită în mesaje între replici, iar fiecare mesaj are o limită inferioară de latency setată de viteza luminii.

Sisteme reale și ce oferă

Un scurt tur al bazelor de date și al butoanelor de consistency pe care le expun.

Google Spanner. Linearizable implicit, global, folosind TrueTime pentru a limita incertitudinea de ceas. Prețul e că fiecare tranzacție așteaptă un „commit wait” TrueTime de câteva milisecunde. Spanner e dovada de existență că linearizable poate fi făcut suficient de rapid pentru producție la scară planetară, având un buget pentru ceasuri atomice.
DynamoDB. Read-uri eventually consistent implicit, configurabile la read-uri „strongly consistent” la dublul costului și latency mai mare. Read-urile strong sunt linearizable pe o singură partiție. Tranzacțiile cross-partition sunt o primitivă separată, mai scumpă.
MongoDB. Tunable per query prin setările read concern și write concern. „Read concern majority” plus „write concern majority” îți dă read-uri linearizable pe leader. Setări mai laxe îți dau read-your-writes sau eventual.
Cassandra. Tunable per operație prin consistency levels (ONE, QUORUM, LOCAL_QUORUM, ALL). Read-uri quorum plus scrieri quorum îți dau ceva apropiat de linearizable pe o singură cheie. Niveluri mai joase îți dau eventual.
Replicare Postgres. Primary-ul e linearizable trivial. Replicile sincrone sunt linearizable. Replicile async sunt eventually consistent, cu opțiunea de read-your-writes dacă aplicația ta e atentă la routing.

Observă pattern-ul: nicio bază de date distribuită majoră nu alege un model și se ține de el. Toate expun butoane, pentru că operații diferite în aceeași aplicație au nevoi diferite de consistency. Abilitatea arhitecturală e să știi ce buton să rotești pentru ce operație.

Ierarhia

flowchart TD
    L[Linearizable] --> S[Sequential]
    S --> C[Causal]
    C --> RYW[Read-your-writes]
    C --> MR[Monotonic reads]
    RYW --> E[Eventually consistent]
    MR --> E

Modelele mai puternice sunt sus. O săgeată de la A la B înseamnă „A implică B”: dacă sistemul tău e linearizable, e și causal, monotonic și eventually consistent. A alege un model înseamnă a alege cât de departe în jos pe diagramă ești dispus să cazi.

Concluzia

Trei lucruri de luat cu tine în lecția următoare.

Întâi, „strong” și „eventual” sunt capetele unui spectru real, nu singurele opțiuni. Causal consistency în special e subutilizată; surprinde majoritatea a ceea ce așteaptă utilizatorii, la o fracțiune din costul de coordonare.

În al doilea rând, consistency e per operație, nu per sistem. Aceeași bază de date poate fi linearizable pentru o actualizare de sold și eventually consistent pentru un contor de vizualizări. Tratarea consistency-ului ca pe o singură setare globală aruncă cea mai mare parte a spațiului de design.

În al treilea rând, costul modelelor mai puternice e plătit în latency, iar latency e setată de fizică. Coordonarea peste continente ia timp. Dacă sistemul tău are nevoie atât de scară globală, cât și de linearizable consistency, vei plăti pentru asta în întârziere vizibilă pentru utilizator, sau în ceasuri atomice, sau ambele.

Lecția următoare merge sub consistency, în timp însuși: de ce ceasurile fizice sunt nesigure, ce ne dau în loc Lamport timestamps și vector clocks și cum cumpără Spanner linearizable consistency la scară planetară cumpărând ceasuri mai bune.