Se la consistency riguarda cosa possono vedere le letture, il tempo riguarda in quale ordine sono successe le cose. Le due cose sono intrecciate, perché la maggior parte delle definizioni di consistency è scritta in termini di ordine, e l’ordine, su una singola macchina, è facile. Il clock ticchetta. Le cose succedono. La prima cosa succede prima della seconda.
In un sistema distribuito, il clock non ticchetta. Ci sono molti clock, su molte macchine, e non sono d’accordo. Due eventi su macchine diverse non hanno un ordine intrinseco, e “quando è successo” si trasforma in una delle domande più difficili dell’informatica. La lezione precedente ha assunto che avessimo un modo per ordinare le operazioni. Questa lezione spiega perché di solito non ce l’abbiamo, e quali trucchi il campo ha inventato per recuperare l’ordinamento quando conta.
Affronteremo tre livelli: perché i clock fisici sono inaffidabili, cosa ci danno invece i clock logici, e come Google ha speso una cifra seria per rendere i clock fisici abbastanza affidabili da far girare Spanner.
Perché i clock fisici sono inaffidabili
Il piano ingenuo: ogni macchina ha un clock, il clock riporta un numero, usiamo il numero per ordinare gli eventi. Il numero è il tempo. Fatto.
Il piano non sopravvive al contatto con un datacenter vero. Cinque problemi si accumulano.
Clock skew. Nessun paio di clock concorda esattamente. Due macchine dello stesso vendor, montate una accanto all’altra, alimentate dallo stesso server NTP, riporteranno tempi che divergono di qualche millisecondo in qualunque istante dato. La divergenza varia man mano che i cristalli si scaldano, mentre il carico cambia, mentre la macchina invecchia. Uno skew di 1 a 10 millisecondi è normale. Uno skew di secondi è comune in ambienti mal configurati. Uno skew di minuti capita, ed è uno dei bug più divertenti da debuggare alle 3 di notte.
Correzioni NTP. Il Network Time Protocol spinge il clock verso la verità, ma le spinte non sono sempre in avanti. Se il tuo clock è andato troppo veloce, NTP lo rallenterà o lo farà tornare indietro a scatti. Un clock monotonicamente crescente non è ciò che NTP ti dà. Codice che assume “la prossima lettura sarà almeno grande quanto l’ultima” può rompersi quando NTP corregge.
Leap second. Più o meno una volta ogni qualche anno, gli enti internazionali del tempo aggiungono un secondo a UTC perché la rotazione della Terra non corrisponde esattamente al tempo atomico. Alcuni sistemi ripetono 23:59:59. Alcuni sistemi si bloccano. Alcuni sistemi si rifiutano di riconoscere i leap second e divergono lentamente da UTC. Il leap second del 2012 ha tirato giù Reddit, LinkedIn, Yelp, e una fetta non trascurabile di internet, perché il kernel Linux dell’epoca non lo gestiva con grazia. I leap second sono una fonte famosa di bug del tipo “non ci eravamo accorti che i nostri timestamp erano una bugia”.
Drift delle macchine virtuali. Il clock di una VM è ospite dell’host. Quando l’host sospende la VM (live migration, oversubscription, qualunque cosa porti via la CPU al guest per un po’), il clock del guest rimane indietro rispetto al tempo reale. Quando la VM riprende, il clock o salta in avanti per recuperare (rompendo la monotonicità) o recupera lentamente leggendo valori sbagliati nel mentre. I workload cloud sono pieni di questa cosa.
Incertezza cross-region. Anche se ogni clock nel tuo datacenter è entro pochi millisecondi dalla verità, un clock a Singapore e un clock in Virginia, entrambi perfettamente sincronizzati con le rispettive sorgenti NTP, possono comunque divergere. Il budget d’errore cresce con la distanza, con le condizioni di rete, con quanto spesso gira la sync.
La conclusione pragmatica: non fidarti del wall-clock time per nulla che richieda correttezza. Va bene per timestamp di log leggibili dagli umani. Non va bene per decidere quale di due write sia successa per prima.
La relazione “happened before”
Leslie Lamport, nel 1978, scrisse un paper intitolato “Time, Clocks, and the Ordering of Events in a Distributed System” che risolse questo problema in modo così pulito che i quarant’anni successivi di teoria dei sistemi distribuiti ci hanno costruito sopra. L’idea centrale è abbandonare del tutto il tempo fisico e definire un ordinamento basato sulla causalità.
Due eventi sono ordinati, nel senso di Lamport, se uno avrebbe potuto causare l’altro. Nello specifico, A “happened before” B (scritto A poi B) quando vale una di tre cose:
- A e B sono successi sullo stesso nodo, e A è venuto prima nell’ordine locale di quel nodo.
- A è l’invio di un messaggio e B è la ricezione dello stesso messaggio.
- Esiste una catena di relazioni “happened before” che connette A a B (è transitiva).
Qualunque altra cosa è concorrente. Eventi concorrenti non hanno relazione causale: nessuno avrebbe potuto causare l’altro. La relazione “happened before” dà un ordine parziale, non un ordine totale, e questa è la risposta onesta. In un sistema distribuito, in generale non puoi dire quale di due eventi sia venuto prima. A volte puoi dire che uno ha causato l’altro.
Il resto della lezione è l’ingegneria del “a volte”.
Lamport timestamp
Lo schema più semplice che rispetta “happened before”.
Ogni nodo tiene un singolo contatore intero, che parte da zero. Ogni evento sul nodo incrementa il contatore. Quando un nodo invia un messaggio, include il suo contatore corrente. Quando un nodo riceve un messaggio, imposta il suo contatore a max(local, received) + 1.
Il risultato: se A è happened before B, allora il timestamp di A è minore di quello di B. Il contrario non è vero: un timestamp più piccolo non significa un evento precedente, perché due nodi non correlati possono raggiungere indipendentemente lo stesso valore di contatore o uno può scappare avanti.
I Lamport timestamp danno un ordine totale sugli eventi (rompendo i pareggi con l’id del nodo) che è consistente con la causalità. Due eventi con timestamp 5 e 7 o hanno una relazione causale reale o sono concorrenti. Non puoi dire quale dei due dai soli timestamp, ed è il trucco: i Lamport timestamp rilevano l’ordinamento, non la concorrenza.
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)Il diagramma mostra il contatore che avanza a ogni evento e a ogni ricezione di messaggio. Nota che il timestamp 2 di B è maggiore del timestamp 1 di A, riflettendo correttamente che il send di A è happened before la receive di B. Ma se un nodo non correlato C avesse anche timbrato un evento come 2, non potremmo dire se l’evento di C sia venuto prima, dopo, o concorrente a quello di B.
Vector clock
Per distinguere eventi ordinati da eventi concorrenti, ci serve più informazione di un singolo contatore. I vector clock ci danno esattamente questo.
Ogni nodo tiene un vettore di contatori, una entry per ogni nodo nel sistema. Ogni evento locale sul nodo i incrementa la entry i. Quando il nodo i invia un messaggio, include l’intero vettore. Quando il nodo j riceve un messaggio, imposta il proprio vettore al massimo elemento per elemento tra il vettore corrente e quello ricevuto, poi incrementa la entry j.
Confrontando due vector timestamp:
- A è prima di B se ogni entry di A è minore o uguale alla entry corrispondente di B, e almeno una è strettamente minore.
- A è dopo B se vale il contrario.
- A e B sono concorrenti se nessuno dei due è prima dell’altro (alcune entry dicono che A è più vecchio, altre dicono che B è più vecchio).
I vector clock ci danno l’informazione di causalità completa. Ti dicono esattamente quali eventi sono ordinati e quali sono concorrenti. Il prezzo è lo storage: ogni evento porta con sé un vettore con una entry per nodo, e ogni messaggio spedisce quel vettore. In un sistema con migliaia di nodi, i vettori diventano costosi. Trucchi come potare le entry per nodi che non si sono fatti sentire da un po’ aiutano, ma introducono i loro bug sottili.
Sistemi reali che usano vector clock: Riak, le prime versioni di Dynamo (il paper di Amazon, 2007). DynamoDB il prodotto si è poi spostato a uno schema leggermente diverso.
Hybrid logical clock
Un compromesso tra tempo fisico e tempo logico. Gli Hybrid Logical Clock (HLC) combinano il wall-clock time con un contatore logico. Ogni timestamp è una coppia: il wall clock al momento dell’evento, più un piccolo intero che rompe i pareggi quando il wall clock non è avanzato.
L’invariante: se A è happened before B, allora l’HLC di A è minore di quello di B. Dentro un singolo nodo, la parte wall-clock avanza normalmente; il contatore logico si resetta quando il wall clock va avanti. Tra nodi, la regola di ricezione del messaggio rispecchia quella di Lamport: prendi il max, poi incrementa il contatore.
Gli HLC sono il compromesso moderno perché ti danno qualcosa che assomiglia a un timestamp reale (puoi leggerlo come una data per il debug) fornendo le garanzie di ordinamento parziale che contano. Sono usati in CockroachDB, nelle causal session di MongoDB, in YugabyteDB, e altrove.
Il trucco: gli HLC assumono che lo skew del wall-clock sia limitato. Se i clock di due nodi divergono più di quanto il protocollo si aspetti, l’ordinamento si può rompere. La maggior parte delle implementazioni mette un tetto a quanto avanti un HLC possa correre rispetto al wall clock locale e rifiuta di accettare messaggi da nodi troppo nel futuro.
Google TrueTime
Il database Spanner, internamente in Google, prende un approccio diverso. Invece di girare attorno a clock inaffidabili, Google ha costruito clock affidabili. Ogni datacenter che fa girare Spanner ha ricevitori GPS e clock atomici, in modo ridondante, in più rack. L’API TrueTime non restituisce un timestamp. Restituisce un intervallo: “il tempo corrente è da qualche parte tra now - epsilon e now + epsilon”, dove epsilon è il limite sull’incertezza.
In un datacenter Google in salute, epsilon è attorno a 1 a 7 millisecondi. Il protocollo Spanner usa questi intervalli per fornire external consistency, che è un nome elegante per linearizability con una garanzia di ordinamento real-time. Il trucco: quando fa il commit di una transaction, Spanner aspetta che l’incertezza passi. Sceglie un commit timestamp all’estremo superiore dell’intervallo TrueTime corrente, poi dorme finché il limite inferiore del nuovo intervallo non ha superato quel timestamp. Quando l’attesa è finita, ogni chiamata TrueTime in qualsiasi parte del mondo restituirà un intervallo il cui limite inferiore è maggiore del commit timestamp. La transaction è, per definizione, nel passato.
Il costo: ogni commit di Spanner paga qualche millisecondo di “commit wait”. Il beneficio: linearizability tra continenti, senza un lock globale, senza un clock globale, senza un singolo punto di coordinamento. È l’unico sistema in produzione che ce la fa, e lo fa essendo disposto a spendere una cifra seria in hardware. TrueTime non è un algoritmo; è un algoritmo più una flotta di antenne GPS più un edificio pieno di clock atomici. Se non hai il budget di Google, non hai TrueTime.
Quando il tempo conta
Tre classi di problemi dove la questione del clock diventa urgente.
Audit log. Un regolatore chiede: in che ordine sono successe queste transactions? Se il tuo sistema memorizza wall-clock timestamp da ogni nodo, non puoi rispondere onestamente: i timestamp sono sfasati di millisecondi nella migliore delle ipotesi. Se il tuo sistema memorizza Lamport o HLC timestamp, puoi rispondere per gli eventi che hanno una relazione causale, e ammettere “concorrente” per il resto. La risposta onesta è più utile di quella sbagliata.
Risoluzione dei conflitti. Due write colpiscono replica diverse quasi nello stesso istante. Quale vince? “Last writer wins” suona semplice ma richiede una nozione definita di “last”, e i clock fisici non te ne forniscono una. Sistemi migliori usano vector clock per rilevare il conflitto, poi lo risolvono con la logica applicativa (i CRDT, per esempio, sono esplicitamente progettati per fondere write concorrenti in modo sicuro).
Distributed transaction. Una transaction copre più shard e deve fare commit in modo atomico. Il protocollo di commit deve assegnare alla transaction un timestamp che sia maggiore di ogni timestamp da cui dipende, ma minore di ogni timestamp con cui è in conflitto. Senza TrueTime o equivalente, questa è la parte difficile del two-phase commit.
Scheduling. “Esegui questo job non prima delle 9:00 AM” richiede una nozione di 9:00 AM su cui ogni nodo concordi. I wall-clock timestamp funzionano qui, perché le conseguenze di eseguire un job qualche secondo prima o dopo sono di solito limitate. Ma per uno scheduling più stretto (diciamo, “ruota la chiave di crittografia esattamente a mezzanotte, in modo atomico”), ti serve consensus, non solo un clock.
Consigli pragmatici
Tre regole pratiche.
Primo, non fidarti del wall clock per nulla che richieda correttezza. Leggilo per i timestamp di log, per i display umani, per i job cron. Non usarlo per decidere quale write vince.
Secondo, usa il clock giusto per il lavoro. I clock monotonici (quelli che vanno solo avanti, come CLOCK_MONOTONIC su Linux) sono lo strumento giusto per misurare durate: quanto è durata questa request, è scaduto il lease. I clock logici (Lamport, vector, HLC) sono lo strumento giusto per ordinare eventi tra nodi. I wall clock sono lo strumento giusto per “che ore sono” e poco altro.
Terzo, quando il requisito è “linearizable tra continenti”, accetta il costo. Il costo è o latenza di coordinamento (un round-trip per write) o un investimento hardware in stile TrueTime. Non c’è una terza opzione. Chiunque ti stia vendendo “linearizable, low-latency, multi-region, no coordination” ti sta vendendo un bug.
La prossima lezione va uno strato più in profondità, dentro i protocolli di consensus che trasformano un gruppo di nodi con clock in disaccordo e una rete inaffidabile in un sistema capace di concordare su un singolo valore. Paxos, Raft, e i sistemi che girano sopra di loro.