Dacă consistența e despre ce pot să vadă citirile, timpul e despre ordinea în care s-au întâmplat lucrurile. Cele două sunt încurcate, pentru că majoritatea definițiilor de consistență sunt scrise în termeni de ordine, iar ordinea, pe o singură mașină, e ușoară. Ceasul ticăie. Lucrurile se întâmplă. Primul lucru se întâmplă înaintea celui de-al doilea.
Pe un sistem distribuit, ceasul nu ticăie. Există multe ceasuri, pe multe mașini, și nu sunt de acord. Două evenimente pe mașini diferite nu au o ordine inerentă, iar „când s-a întâmplat asta” devine una dintre cele mai grele întrebări din computing. Lecția anterioară a presupus că aveam o cale de a ordona operațiile. Lecția asta explică de ce de obicei nu avem și ce trucuri a inventat domeniul ca să recuperăm ordonarea atunci când contează.
O să trecem prin trei straturi: de ce ceasurile fizice sunt nesigure, ce ne dau în schimb ceasurile logice și cum a plătit Google bani serioși ca să facă ceasurile fizice destul de sigure încât să alimenteze Spanner.
De ce ceasurile fizice sunt nesigure
Planul naiv: fiecare mașină are un ceas, ceasul raportează un număr, folosim numărul ca să ordonăm evenimente. Numărul e timpul. Gata.
Planul nu supraviețuiește contactului cu un datacenter real. Cinci probleme se acumulează.
Clock skew. Două ceasuri nu sunt niciodată de acord exact. Două mașini de la același furnizor, montate una lângă alta în același rack, alimentate de același server NTP, vor raporta timpuri care diferă cu câteva milisecunde la orice moment dat. Diferența variază pe măsură ce cristalele se încălzesc, pe măsură ce se schimbă încărcarea, pe măsură ce mașina îmbătrânește. Skew de 1 până la 10 milisecunde e normal. Skew de secunde e comun în medii prost configurate. Skew de minute se întâmplă și e unul dintre cele mai distractive bug-uri de debug-uit la 3 dimineața.
Corecții NTP. Network Time Protocol împinge ceasul către adevăr, dar împingerile nu sunt întotdeauna înainte. Dacă ceasul tău a mers prea repede, NTP îl va încetini sau îl va da înapoi. Un ceas care crește monoton nu e ce-ți dă NTP. Codul care presupune „următoarea citire va fi cel puțin la fel de mare ca ultima” se poate strica atunci când NTP corectează.
Leap seconds. Aproximativ o dată la câțiva ani, organismele internaționale de timp adaugă o secundă la UTC pentru că rotația Pământului nu se potrivește exact cu timpul atomic. Unele sisteme repetă 23:59:59. Unele sisteme îngheață. Unele sisteme refuză să recunoască secundele intercalare și se îndepărtează încet de UTC. Leap second-ul din 2012 a doborât Reddit, LinkedIn, Yelp și o bună parte din internet, pentru că nucleul Linux de atunci nu îl gestiona elegant. Leap seconds sunt o sursă faimoasă de bug-uri de tipul „nu ne-am dat seama că timestamp-urile noastre sunt o minciună”.
Drift de mașină virtuală. Ceasul unui VM e oaspete al gazdei. Când gazda suspendă VM-ul (live migration, oversubscription, orice care ia CPU-ul de la oaspete pentru o vreme), ceasul oaspetelui rămâne în urma timpului real. Când VM-ul reia, ceasul fie sare înainte ca să recupereze (rupând monotonicitatea), fie recuperează încet citind valori greșite. Workload-urile cloud sunt pline de asta.
Incertitudine cross-region. Chiar dacă fiecare ceas din datacenter-ul tău e la câteva milisecunde de adevăr, un ceas din Singapore și un ceas din Virginia, ambele perfect sincronizate la sursele lor NTP respective, încă pot să nu fie de acord. Bugetul de eroare crește cu distanța, cu condițiile de rețea, cu cât de des rulează sincronizarea.
Concluzia pragmatică: nu te încrede în wall-clock time pentru nimic care necesită corectitudine. E în regulă pentru timestamp-uri de log citibile de oameni. Nu e în regulă pentru a decide care dintre două scrieri s-a întâmplat prima.
Relația „happened before”
Leslie Lamport, în 1978, a scris o lucrare intitulată „Time, Clocks, and the Ordering of Events in a Distributed System” care a rezolvat această problemă atât de curat încât următorii patruzeci de ani de teorie a sistemelor distribuite s-au construit pe ea. Ideea de bază e să abandonezi complet timpul fizic și să definești o ordonare bazată pe cauzalitate.
Două evenimente sunt ordonate, în sensul lui Lamport, dacă unul ar fi putut să-l cauzeze pe celălalt. Mai exact, A „happened before” B (scris A apoi B) când unul din trei lucruri e adevărat:
- A și B s-au întâmplat pe același nod, iar A a venit primul în ordinea locală a acelui nod.
- A e trimiterea unui mesaj și B e primirea aceluiași mesaj.
- Există un lanț de relații „happened before” care leagă A de B (e tranzitivă).
Orice altceva e concurent. Evenimentele concurente nu au relație cauzală: niciunul nu ar fi putut să-l cauzeze pe celălalt. Relația „happened before” dă o ordine parțială, nu una totală, și ăsta e răspunsul cinstit. Într-un sistem distribuit, în general nu poți spune care dintre două evenimente a venit primul. Uneori poți spune că unul l-a cauzat pe celălalt.
Restul lecției e ingineria lui „uneori”.
Lamport timestamps
Cea mai simplă schemă care respectă „happened before”.
Fiecare nod ține un singur contor întreg, pornind de la zero. Fiecare eveniment pe nod incrementează contorul. Când un nod trimite un mesaj, include contorul curent. Când un nod primește un mesaj, își setează contorul la max(local, received) + 1.
Rezultatul: dacă A happened before B, atunci timestamp-ul lui A e mai mic decât al lui B. Inversul nu e adevărat: un timestamp mai mic nu înseamnă un eveniment mai vechi, pentru că două noduri fără legătură pot ajunge independent la aceeași valoare a contorului sau unul poate să o ia înainte.
Lamport timestamps dau o ordine totală peste evenimente (cu departajare după node id) care e consistentă cu cauzalitatea. Două evenimente cu timestamp-uri 5 și 7 fie au o relație cauzală reală, fie sunt concurente. Nu poți spune care, doar din timestamp-uri, asta fiind capcana: Lamport timestamps detectează ordonarea, nu concurența.
sequenceDiagram
participant A as Node A
participant B as Node B
Note over A: counter = 0
Note over B: counter = 0
A->>A: local event (counter = 1)
A->>B: send msg, ts = 1
Note over B: receive, counter = max(0,1)+1 = 2
B->>B: local event (counter = 3)
B->>A: send msg, ts = 3
Note over A: receive, counter = max(1,3)+1 = 4
A->>A: local event (counter = 5)Diagrama arată contorul avansând la fiecare eveniment și la fiecare primire de mesaj. Observă că timestamp-ul 2 al lui B e mai mare decât timestamp-ul 1 al lui A, reflectând corect că trimiterea lui A s-a întâmplat înaintea primirii lui B. Dar dacă un alt nod C, fără legătură, ar fi marcat și el un eveniment cu 2, nu am putea spune dacă evenimentul lui C a venit înainte, după sau concurent cu cel al lui B.
Vector clocks
Ca să distingem evenimentele ordonate de cele concurente, avem nevoie de mai multe informații decât un singur contor. Vector clocks ne dau exact asta.
Fiecare nod ține un vector de contoare, câte o intrare pentru fiecare nod din sistem. Fiecare eveniment local pe nodul i incrementează intrarea i. Când nodul i trimite un mesaj, include întreg vectorul. Când nodul j primește un mesaj, își setează propriul vector la maximul element-cu-element între vectorul curent și cel primit, apoi incrementează intrarea j.
Comparând două timestamp-uri vectoriale:
- A e înainte de B dacă fiecare intrare din A e mai mică sau egală cu intrarea corespunzătoare din B și cel puțin una e strict mai mică.
- A e după B dacă inversul e adevărat.
- A și B sunt concurente dacă niciunul nu e înainte de celălalt (unele intrări spun că A e mai vechi, altele spun că B e mai vechi).
Vector clocks ne dau informația completă de cauzalitate. Îți spun exact care evenimente sunt ordonate și care sunt concurente. Prețul e stocarea: fiecare eveniment poartă un vector cu o intrare per nod și fiecare mesaj transportă acel vector. Într-un sistem cu mii de noduri, vectorii devin scumpi. Trucuri ca tăierea intrărilor pentru noduri de la care nu s-a auzit de mult ajută, dar introduc propriile bug-uri subtile.
Sisteme reale care folosesc vector clocks: Riak, versiunile timpurii ale Dynamo (lucrarea Amazon, 2007). Produsul DynamoDB a trecut ulterior la o schemă ușor diferită.
Hybrid logical clocks
Un compromis între timpul fizic și cel logic. Hybrid Logical Clocks (HLC) combină wall-clock time cu un contor logic. Fiecare timestamp e o pereche: ceasul de perete la momentul evenimentului, plus un mic întreg care departajează când ceasul de perete nu a avansat.
Invariantul: dacă A happened before B, atunci HLC-ul lui A e mai mic decât al lui B. În cadrul unui singur nod, partea de wall-clock avansează normal; contorul logic se resetează când ceasul de perete merge înainte. Între noduri, regula de primire de mesaj reflectă pe cea a lui Lamport: ia maximul, apoi incrementează contorul.
HLC-urile sunt compromisul modern pentru că îți dau ceva care arată ca un timestamp real (poți să-l citești ca o dată pentru debug) oferind în același timp garanțiile de ordonare parțială care contează. Sunt folosite în CockroachDB, sesiunile cauzale ale MongoDB, YugabyteDB și altele.
Capcana: HLC-urile presupun că wall-clock skew-ul e mărginit. Dacă ceasurile a două noduri se îndepărtează cu mai mult decât așteaptă protocolul, ordonarea se poate strica. Majoritatea implementărilor plafonează cât de mult înainte poate merge un HLC față de wall-clock-ul local și refuză să accepte mesaje de la noduri prea departe în viitor.
Google TrueTime
Baza de date Spanner, intern la Google, ia o abordare diferită. În loc să lucreze în jurul ceasurilor nesigure, Google a construit ceasuri sigure. Fiecare datacenter care rulează Spanner are receptoare GPS și ceasuri atomice, redundante, în mai multe rack-uri. API-ul TrueTime nu returnează un timestamp. Returnează un interval: „timpul curent e undeva între now - epsilon și now + epsilon”, unde epsilon e marginea de incertitudine.
Într-un datacenter Google sănătos, epsilon e în jur de 1 până la 7 milisecunde. Protocolul Spanner folosește aceste intervale ca să ofere external consistency, care e un nume sofisticat pentru linearizabilitate cu o garanție de ordonare în timp real. Trucul: când commit-uie o tranzacție, Spanner așteaptă să se scurgă incertitudinea. Alege un commit timestamp la capătul superior al intervalului TrueTime curent, apoi doarme până când marginea inferioară a noului interval a depășit acel timestamp. Până se termină așteptarea, fiecare apel TrueTime de oriunde în lume va returna un interval a cărui margine inferioară e mai mare decât commit timestamp-ul. Tranzacția e, prin definiție, în trecut.
Costul: fiecare commit Spanner plătește câteva milisecunde de „commit wait”. Beneficiul: linearizabilitate între continente, fără un lock global, fără un ceas global, fără un singur punct de coordonare. E singurul sistem de producție care reușește asta și o face fiind dispus să cheltuie bani serioși pe hardware. TrueTime nu e un algoritm; e un algoritm plus o flotă de antene GPS plus o clădire plină de ceasuri atomice. Dacă nu ai bugetul Google, nu ai TrueTime.
Când contează timpul
Trei clase de probleme unde întrebarea ceasului devine urgentă.
Audit logs. Un autoritar regulator întreabă: în ce ordine s-au întâmplat tranzacțiile astea? Dacă sistemul tău stochează wall-clock timestamps de la fiecare nod, nu poți răspunde cinstit: timestamp-urile sunt diferite cu milisecunde în cel mai bun caz. Dacă sistemul tău stochează Lamport sau HLC timestamps, poți răspunde pentru evenimentele care au o relație cauzală și recunoaște „concurent” pentru restul. Răspunsul cinstit e mai util decât cel greșit.
Rezolvarea conflictelor. Două scrieri lovesc replici diferite în aproape același moment. Care câștigă? „Last writer wins” sună simplu, dar necesită o noțiune definită de „ultimul”, iar ceasurile fizice nu o oferă. Sistemele mai bune folosesc vector clocks ca să detecteze conflictul, apoi îl rezolvă cu logică de aplicație (CRDT-urile, de exemplu, sunt explicit proiectate să combine în siguranță scrieri concurente).
Tranzacții distribuite. O tranzacție acoperă mai multe shard-uri și trebuie să facă commit atomic. Protocolul de commit trebuie să asigneze tranzacției un timestamp care e mai mare decât fiecare timestamp de care depinde, dar mai mic decât fiecare timestamp cu care intră în conflict. Fără TrueTime sau echivalentul, asta e partea grea a two-phase commit.
Programare. „Rulează acest job nu mai devreme de 9:00 AM” are nevoie de o noțiune de 9:00 AM cu care fiecare nod e de acord. Wall-clock timestamps merg aici, pentru că consecințele rulării unui job cu câteva secunde mai devreme sau mai târziu sunt de obicei mărginite. Dar pentru programare mai strictă (să zicem, „rotește cheia de criptare exact la miezul nopții, atomic”), ai nevoie de consensus, nu doar de un ceas.
Sfaturi pragmatice
Trei reguli empirice.
În primul rând, nu te încrede în wall-clock pentru nimic care necesită corectitudine. Citește-l pentru timestamp-uri de log, pentru afișări către oameni, pentru cron jobs. Nu-l folosi ca să decizi care scriere câștigă.
În al doilea rând, folosește ceasul potrivit pentru job. Ceasurile monotone (cele care merg doar înainte, ca CLOCK_MONOTONIC pe Linux) sunt unealta potrivită pentru a măsura durate: cât a durat cererea asta, a expirat lease-ul. Ceasurile logice (Lamport, vector, HLC) sunt unealta potrivită pentru a ordona evenimente între noduri. Wall clocks sunt unealta potrivită pentru „ce oră e” și pentru foarte puțin altceva.
În al treilea rând, când cerința e „linearizabil între continente”, acceptă costul. Costul e fie latența de coordonare (un round-trip per scriere), fie o investiție de tip TrueTime în hardware. Nu există a treia opțiune. Oricine îți vinde „linearizabil, latență mică, multi-region, fără coordonare” îți vinde un bug.
Lecția următoare merge un strat mai adânc, în protocoalele de consensus care transformă un grup de noduri cu ceasuri care nu sunt de acord și o rețea nesigură într-un sistem care poate fi de acord pe o singură valoare. Paxos, Raft și sistemele care rulează deasupra lor.