En un programa que corre en una sola màquina, la pregunta "què va passar primer?" sempre té resposta: n'hi ha prou amb mirar el rellotge o l'ordre de les instruccions. En un sistema distribuït, aquesta pregunta es torna sorprenentment difícil. Cada node té el seu propi rellotge, aquests rellotges mai no coincideixen exactament i els missatges triguen un temps variable a arribar. Quan l'Anna, des de Barcelona, i en Marc, des de València, premen "comprar" sobre l'última unitat de formatge curat de la Formatgeria Montblanc, decidir qui va ser primer no és una qüestió de mirar dues marques de temps.

Aquesta lliçó explica per què no existeix un rellotge global, fins a quin punt podem sincronitzar els rellotges físics (NTP, PTP) i, sobretot, presenta la solució que Leslie Lamport va proposar el 1978 i que continua sent fonamental: substituir el temps físic per un ordre lògic basat en la causalitat. Implementarem pas a pas els rellotges de Lamport i els rellotges vectorials en Python, veurem com detecten esdeveniments concurrents i acabarem amb una visió dels rellotges híbrids i de TrueTime, que combinen el millor de tots dos mons.

1. Per què no hi ha un rellotge global
2. Rellotges físics: deriva i sincronització (NTP i PTP)
3. El problema d'ordenar esdeveniments: l'Anna, en Marc i l'últim formatge
4. La relació "va passar abans" (happens-before)
5. Rellotges lògics de Lamport
6. Rellotges vectorials
7. Rellotges híbrids i TrueTime: una visió general
8. Els rellotges lògics a la pràctica
9. Errors comuns i consells
10. Exercicis
11. Conclusió

Un "rellotge global" seria un instant de temps compartit i exacte que tots els nodes poguessin consultar. No existeix per tres raons que s'acumulen:

1. Cada node té el seu propi rellotge de maquinari, un oscil·lador de quars la freqüència del qual depèn de la temperatura, l'antiguitat i la fabricació. Dos rellotges idèntics, posats en hora alhora, divergeixen inevitablement.
2. Consultar el rellotge d'un altre node porta temps, i aquest temps és variable i desconegut. Si preguntes "quina hora és?" i la resposta triga 30 ms a arribar, l'hora que t'han donat és de fa 15 ms? De fa 5? De fa 25? No ho saps.
3. Els nodes s'aturen sense saber-ho. Un procés es pot aturar durant desenes o centenars de mil·lisegons per una recol·lecció de brossa, per una interrupció de la màquina virtual o per sobrecàrrega de CPU. Quan es reprèn, creu que "ara" és l'instant en què es va aturar.

La conseqüència pràctica: dues marques de temps preses en màquines diferents no es poden comparar amb una precisió millor que l'error de sincronització entre elles. Si aquest error és de 10 ms i les marques difereixen en 2 ms, l'ordre real és indeterminat.

La deriva (drift) és la velocitat a la qual un rellotge es desvia del temps real. Un quars típic de servidor té una deriva d'unes 50 parts per milió (ppm): es desvia 50 microsegons per cada segon, és a dir, uns 4,3 segons al dia. Sembla poc, però per a un sistema que processa centenars de comandes per segon, 4 segons són una eternitat. Per això els rellotges se sincronitzen periòdicament amb una font de referència.

NTP és el protocol que fan servir gairebé tots els sistemes operatius per posar en hora els seus rellotges a través d'Internet. Funciona en una jerarquia d'"estrats": els servidors d'estrat 0 són rellotges atòmics o receptors GPS; els d'estrat 1 se sincronitzen directament amb ells; els d'estrat 2 amb els d'estrat 1, etc. Un client NTP envia una petició, anota quan l'ha enviat i quan ha rebut la resposta, i fa servir les marques de temps del servidor per estimar el desfasament, assumint que el viatge d'anada triga el mateix que el de tornada. Aquesta suposició és la font principal d'error.

A més, NTP ajusta el rellotge de dues maneres: lliscant (slew), accelerant o frenant lleugerament el rellotge fins a corregir el desfasament, o saltant (step), si el desfasament és gran. Un salt enrere vol dir que el rellotge pot marcar dues vegades el mateix instant, o que una mesura de durada (fi - inici) pot sortir negativa. Per això els sistemes operatius ofereixen un rellotge monotònic (time.monotonic() en Python), que mai no retrocedeix i serveix per mesurar durades, davant del rellotge de paret (time.time()), que serveix per saber la data i l'hora però pot saltar.

PTP (IEEE 1588) assoleix precisions de microsegons o menys gràcies al fet que les marques de temps les posen les mateixes targetes de xarxa i els commutadors per maquinari, eliminant la variabilitat del programari. Requereix maquinari compatible a tota la ruta, per la qual cosa es fa servir en centres de dades, en finances d'alta freqüència i en telecomunicacions, no a l'Internet obert.

Fins i tot amb PTP, els rellotges tenen un error. I aquest error, per petit que sigui, és suficient perquè dos esdeveniments "gairebé simultanis" no es puguin ordenar amb certesa. Necessitem una altra idea.

Suposem que Quilòmetre Zero ha replicat el servei inventari en dues ciutats per reduir la latència: una rèplica a Barcelona (inv-bcn) i una altra a València (inv-vlc). Queda una unitat de formatge curat de la Formatgeria Montblanc. L'Anna compra des de Barcelona i en Marc des de València, gairebé alhora.

Si ens refiem dels rellotges, en Marc va ser 2 ms abans. Però el rellotge d'inv-vlc està sincronitzat per NTP amb un error estimat de ±15 ms. Així que la "veritable" hora d'en Marc és entre 10:00:00.103 i 10:00:00.133: pot haver estat abans o després que l'Anna. Els rellotges físics no poden decidir.

I ara la pregunta clau: importa realment "qui va ser primer" en temps físic? El que el sistema necessita és que totes dues rèpliques prenguin la mateixa decisió (una de les dues compres guanya, l'altra rep "sense estoc") i que aquesta decisió respecti les relacions de causa i efecte que sí que coneixem. Per exemple, si l'Anna va consultar l'estoc, va veure "1 unitat" i després va comprar, la seva compra va passar després de la seva consulta, i això sí que és un fet.

Aquesta és la idea de Lamport: renunciar al temps físic i quedar-nos només amb el que podem saber amb certesa, la causalitat.

Lamport va definir la relació "va passar abans" (que s'escriu a → b, "a va passar abans que b") a partir de només tres regles:

1. Mateix procés. Si a i b són esdeveniments del mateix procés i a passa abans que b en la seva execució, aleshores a → b.
2. Enviament i recepció. Si a és l'enviament d'un missatge i b és la recepció d'aquest mateix missatge, aleshores a → b.
3. Transitivitat. Si a → b i b → c, aleshores a → c.

I una definició fonamental: si ni a → b ni b → a, aleshores a i b són concurrents (a ∥ b). Concurrent no vol dir "al mateix temps": vol dir que cap dels dos no pot haver influït en l'altre, perquè no hi ha cap cadena de missatges que els connecti. Per això, per al sistema, el seu ordre és indiferent: qualsevol ordre és igual de vàlid, sempre que tots els nodes triïn el mateix.

En aquest diagrama: a2 → a3 (mateix procés), a3 → a4 → m4 (enviament i recepció, més transitivitat). Però a3 i m3 (les dues compres) són concurrents: no hi ha cap cadena de missatges entre elles. El sistema no pot saber quina va ser "realment" primer, i tampoc no ho necessita: el que necessita és una regla determinista per desempatar.

Un rellotge lògic de Lamport és un comptador enter per procés que assigna a cada esdeveniment una marca L(e) de manera que es compleix la condició de rellotge: si a → b, aleshores L(a) < L(b). L'algorisme té tres regles, en paral·lel a les tres de happens-before:

1. Abans de cada esdeveniment local, el procés incrementa el seu comptador: L = L + 1.
2. En enviar un missatge, el procés incrementa el seu comptador i adjunta el valor al missatge.
3. En rebre un missatge amb marca Lm, el procés fa L = max(L, Lm) + 1.

La regla 3 és la clau: garanteix que la recepció sempre té una marca més gran que l'enviament, i que a partir d'aquest moment el receptor "sap" que existeix com a mínim aquest temps lògic.

La sortida:

El mateix escenari, dibuixat com a diagrama de seqüència amb la marca de Lamport de cada esdeveniment:

Observacions importants:

1. La condició de rellotge es compleix. Cada recepció té una marca més gran que el seu enviament (1 → 2, 2 → 3, 5 → 6), i dins de cada procés les marques creixen. Tota cadena causal té marques creixents.
2. Hi ha empats. "Anna compra" (inv-bcn, 4) i "Marc consulta" (inv-vlc, 4) tenen la mateixa marca. Lamport resol els empats amb un criteri arbitrari però determinista: si les marques coincideixen, ordena pel nom (o identificador) del procés. És el que fa sorted(...) amb les tuples (marca, nom, descripcio). Així, tots els nodes que apliquin la mateixa regla obtindran el mateix ordre total.
3. L'ordre total no és "l'ordre real", i no importa. A l'ordre final, "Anna compra" (4) precedeix "Marc compra" (5). Va ser així en el temps físic? No ho sabem ni ho podem saber. Però és un ordre consistent amb tota la causalitat coneguda i és el mateix per a tothom, que és exactament el que necessitàvem per decidir qui s'emporta el formatge.
4. La limitació de Lamport. Si a → b, aleshores L(a) < L(b). Però el recíproc és fals: de L(a) < L(b) no se'n dedueix a → b. "Anna compra" (4) té una marca més petita que "Marc compra" (5), però són esdeveniments concurrents: no hi ha cap relació causal entre ells. Mirant només les marques de Lamport no podem distingir "va passar abans" de "concurrent". Per a això calen els rellotges vectorials.

Un rellotge vectorial substitueix l'enter únic per un vector amb un comptador per procés. Si hi ha tres processos, cada esdeveniment porta una marca com {inv-bcn: 3, inv-vlc: 1, formatgeria: 2}, que es llegeix com "aquest esdeveniment coneix fins a l'esdeveniment 3 de Barcelona, l'1 de València i el 2 de la formatgeria". Les regles:

1. Abans de cada esdeveniment local, el procés i incrementa la seva pròpia component: V[i] = V[i] + 1.
2. En enviar, incrementa la seva component i adjunta el vector complet al missatge.
3. En rebre un missatge amb vector Vm, fa V[k] = max(V[k], Vm[k]) per a cada component k, i després incrementa la seva pròpia component.

I la comparació, que és el que hi guanyem:

• V(a) ≤ V(b) si totes les components de V(a) són més petites o iguals que les de V(b).
• a → b si i només si V(a) ≤ V(b) i V(a) ≠ V(b).
• a ∥ b (concurrents) si ni V(a) ≤ V(b) ni V(b) ≤ V(a): és a dir, cadascun té alguna component més gran que l'altre.

Ara el recíproc sí que es compleix: comparant vectors podem saber amb certesa si dos esdeveniments estan causalment relacionats o són concurrents.

La sortida:

Analitzem el que hi hem guanyat:

1. Detectem la concurrència. a3 (Anna compra) té inv-bcn:3 més gran que m3, però m3 (Marc compra) té inv-vlc:3 més gran que a3. Cadascun "sap alguna cosa" que l'altre no sap: són concurrents, i el sistema ho pot detectar mecànicament. Amb Lamport, això era impossible.
2. Confirmem la causalitat. a3 → m4: quan València rep l'avís de Barcelona, el seu vector absorbeix el de Barcelona (inv-bcn:4), i a partir d'aquí tot el que passi a València "sap" de la compra de l'Anna. El vector de m4 domina el d'a3 en totes les components.
3. Un detall subtil: q1 → m3. La formatgeria va enviar q1 a Barcelona, no a València, així que com és que m3 "sap" de q1? Perquè q2 va passar després de q1 a la formatgeria (mateixa component: 2 > 1), i m1 va rebre q2. La transitivitat es propaga sola a través del vector.
4. El preu. Cada marca ocupa tants enters com processos hi ha. Amb 3 processos és trivial; amb 1.000 rèpliques o amb milions de clients, no. A la pràctica es fan servir vectors només amb els nodes que escriuen (no els clients), o variants compactades (dotted version vectors), o s'accepta la pèrdua d'informació de Lamport quan no cal detectar concurrència.

Els rellotges lògics resolen l'ordenació causal, però perden una cosa valuosa: la relació amb el temps real. Una marca de Lamport 4732 no diu res de si l'esdeveniment va passar aquest matí o l'any passat, i hi ha molts usos (auditoria, caducitats, "dona'm les comandes de l'última hora") que necessiten temps físic. Dues famílies de solucions combinen tots dos mons:

• Rellotges lògics híbrids (HLC, Hybrid Logical Clocks, 2014). Una marca HLC té dues parts: el temps físic (segons NTP) i un comptador lògic. Es comporta com un rellotge de Lamport (respecta la causalitat: si a → b, HLC(a) < HLC(b)), però la seva part física es manté sempre a prop del temps real (amb un error acotat pel de NTP). El comptador lògic només intervé per desempatar esdeveniments que el temps físic no pot ordenar. Els fan servir bases de dades distribuïdes com CockroachDB o MongoDB.
• TrueTime (Google Spanner, 2012). En lloc de donar un instant, l'API de TrueTime retorna un interval [mes_aviat, mes_tard] que amb certesa conté l'instant real, gràcies a rellotges atòmics i GPS a cada centre de dades, que mantenen l'interval en uns pocs mil·lisegons. Spanner assigna a cada transacció una marca de temps i, abans de confirmar-la, espera que l'interval d'incertesa hagi passat del tot (commit wait). Així garanteix que si la transacció A va acabar abans que comencés la B en temps real, aleshores la marca d'A és més petita que la de B, a qualsevol part del món. És una solució cara (maquinari especialitzat) però conceptualment elegant: converteix la incertesa del rellotge en una espera explícita i acotada.

On apareixen aquests mecanismes en sistemes reals, i a Quilòmetre Zero?

• Ordenació de missatges i esdeveniments. Quan el servei repartiment rep posicions dels repartidors per 4G, poden arribar desordenades. Si cada posició porta un comptador per repartidor (un rellotge de Lamport d'un sol procés), repartiment pot descartar posicions antigues que arriben tard. Els sistemes de missatgeria (lliçó 02-04) ofereixen garanties d'ordre basades en la mateixa idea de números de seqüència.
• Detecció de conflictes en replicació. Quan dues rèpliques d'inventari (o dues còpies del cistell de l'Anna, una al seu mòbil i una altra al servidor) es modifiquen de manera concurrent, els vectors de versió permeten detectar que hi ha un conflicte real (dues escriptures concurrents) davant d'una simple actualització (una escriptura que va passar després de l'altra). El sistema pot aleshores resoldre el conflicte (amb una regla de negoci, demanant-ho a l'usuari, o quedant-se amb totes dues versions). És el mecanisme que va popularitzar Amazon Dynamo i que estudiarem a la lliçó 03-04.
• Instantànies consistents. Perquè analitica calculi "l'estoc total a les 12:00" sobre dades repartides en moltes rèpliques sense aturar el sistema, cal saber quins esdeveniments incloure. Els rellotges lògics permeten definir talls consistents (l'algorisme de Chandy-Lamport) que no incloguin un efecte sense la seva causa.
• Marques de temps de transaccions. Les bases de dades distribuïdes assignen marques de temps (HLC, TrueTime) a les transaccions per decidir quina versió d'una dada veu cada lectura. Apareixerà al Mòdul 3 i a la lliçó 04-04.

La regla pràctica que es deriva de tot això: mai no facis servir marques de temps físiques preses en màquines diferents per decidir l'ordre d'operacions que afecten la coherència de les dades. Fes-les servir per al que serveixen (dates per a humans, caducitats, mètriques) i fes servir comptadors o vectors per a l'ordenació.

• Fer servir time.time() per mesurar durades. El rellotge de paret pot saltar enrere per un ajust de NTP i donar durades negatives o absurdes. Per mesurar quant triga alguna cosa, fes servir sempre time.monotonic().
• Ordenar esdeveniments de nodes diferents per la seva marca de temps física. És l'error d'"últim a escriure guanya" (last-writer-wins) basat en rellotges: amb rellotges desincronitzats, una escriptura més antiga pot "guanyar" una de més recent i perdre dades silenciosament. Si es fa servir aquesta estratègia, cal ser conscient que pot perdre escriptures.
• Creure que Lamport detecta concurrència. De L(a) < L(b) no se'n dedueix res sobre la relació causal entre a i b. Si necessites saber si dos esdeveniments són concurrents, necessites vectors.
• Oblidar el desempat determinista. Un ordre total de Lamport exigeix una regla per als empats (habitualment l'identificador de procés). Sense ella, dos nodes poden ordenar de manera diferent dos esdeveniments amb la mateixa marca.
• Vectors que creixen sense control. Si cada client que escriu afegeix una component al vector, el vector creix sense límit. Cal decidir qui "compta" com a procés (normalment les rèpliques, no els clients) i podar components antigues.
• Consell: a cada missatge o registre que travessi la xarxa, inclou-hi sempre dues coses: una marca de temps física (per als humans i per a les mètriques) i un número de seqüència o vector (per a l'ordenació). Costen pocs bytes i estalvien hores de depuració.

Tres processos, comandes, pagaments i analitica, comencen amb rellotge 0. Passen, en aquest ordre d'execució, els esdeveniments següents:

1. comandes esdeveniment local "crea comanda de la Llúcia".
2. comandes envia "cobra 14,50 €" a pagaments.
3. analitica esdeveniment local "inicia informe".
4. pagaments rep el missatge de comandes.
5. pagaments esdeveniment local "cobrament acceptat".
6. pagaments envia "cobrament OK" a comandes i també a analitica (dos enviaments consecutius).
7. analitica rep "cobrament OK".
8. comandes rep "cobrament OK".

Calcula la marca de Lamport de cada esdeveniment i indica dos esdeveniments que siguin concurrents encara que les seves marques siguin diferents.

L'Anna modifica el seu cistell des del mòbil (procés mobil) i des del navegador (procés web), i tots dos se sincronitzen amb el servidor (procés servidor). Fent servir la classe ProcesVectorial, simula:

1. servidor envia el cistell inicial a mobil i a web (dos enviaments).
2. mobil rep, i afegeix "formatge fresc" (esdeveniment local).
3. web rep, i afegeix "vi negre" (esdeveniment local).
4. mobil envia el seu cistell al servidor; el servidor el rep.
5. web envia el seu cistell al servidor; el servidor el rep.

Comprova amb concurrent() si les dues modificacions són concurrents i explica què hauria de fer el servidor. Després, canvia l'ordre perquè web rebi el cistell del servidor després que aquest hagi integrat el de mobil, i comprova que ara la modificació de web passa després de la de mobil.

El servei repartiment rep posicions d'un repartidor per una xarxa que les desordena. Escriu una classe SeguimentRepartidor amb un mètode rebre_posicio(sequencia, lat, lon) que només actualitzi la posició actual si sequencia és més gran que l'última aplicada, i que compti quantes posicions ha descartat per antigues. Simula l'arribada de les seqüències [1, 2, 4, 3, 5, 7, 6, 8] i mostra la posició final i el nombre de descarts. Quina informació es perd amb aquesta estratègia i quan seria acceptable?

Solució 1:

Esdeveniments concurrents amb marques diferents: "inicia informe" (analitica, 1) i "cobrament acceptat" (pagaments, 4). No hi ha cap cadena de missatges entre ells (analitica encara no havia rebut res), així que són concurrents, encara que 1 < 4. Un altre parell: "crea comanda" (1) i "inicia informe" (1), amb marques iguals i també concurrents. Fixa't que "inicia informe" (1) i "rep cobrament OK" a comandes (6) també són concurrents: el 6 de comandes descendeix de pagaments, no d'analitica.

Solució 2:

El resultat és {servidor:1, mobil:2, web:0} davant de {servidor:2, mobil:0, web:2}: concurrents. Cap modificació no sabia de l'altra. El servidor no s'ha de quedar amb l'última que ha arribat (perdria el formatge o el vi): ha de fusionar totes dues (el cistell amb formatge i vi) o, si la fusió no és òbvia (per exemple, totes dues han canviat la quantitat del mateix producte), preguntar a l'Anna.

A la variant seqüencial (el servidor integra primer el cistell de mobil i després envia el cistell actualitzat a web, que aleshores afegeix el vi), la marca de w2 serà una cosa com {servidor:3, mobil:3, web:2}, que domina mv2: mv2.va_passar_abans(w2) és True. No hi ha conflicte: la modificació de web ja coneixia la de mobil, i el servidor la pot aplicar sense més.

Solució 3:

La posició final és la de la seqüència 8 i es descarten 2 posicions (la 3 i la 6). Es perd el recorregut complet: si analitica volgués reconstruir la ruta exacta, li faltarien dos punts. L'estratègia és acceptable quan només importa la posició actual (mostrar el repartidor al mapa), que és el cas del seguiment en temps real; si cal l'històric, caldria desar totes les posicions i ordenar-les per seqüència després, en lloc de descartar-les.

No existeix un rellotge global: cada node té el seu, amb deriva pròpia, i sincronitzar-los (NTP amb precisió de mil·lisegons, PTP de microsegons) redueix l'error però mai no l'elimina. Per això l'ordre de dos esdeveniments passats en màquines diferents no es pot decidir comparant les seves marques de temps físiques, com mostra el cas de l'Anna i en Marc comprant l'últim formatge.

La sortida de Lamport va ser canviar la pregunta: en lloc de "què va passar abans en el temps?", preguntar "què pot haver causat què?". La relació va passar abans captura exactament aquesta causalitat, els rellotges de Lamport la converteixen en un ordre total que tots els nodes comparteixen (a costa de no distingir la concurrència), i els rellotges vectorials hi afegeixen la capacitat de detectar quan dos esdeveniments són concurrents, que és la base de la detecció de conflictes en replicació. Els rellotges híbrids i TrueTime reconcilien la causalitat amb el temps real per als sistemes que necessiten totes dues coses.

Amb això tanquem els fonaments conceptuals del mòdul. La lliçó següent, Del Monòlit a la Plataforma Distribuïda: el Cas Quilòmetre Zero, recull tot el que hem vist —fallades parcials, models, avantatges i costos, fal·làcies, temps— i ho aplica a un disseny concret: l'arquitectura objectiu que construirem durant la resta del curs.