El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Models de Consistència

Següent ►
►

El Mòdul 2 va acabar amb una escena incòmoda: l'Anna reserva l'últim formatge-curat de la Formatgeria Montblanc, inventari el descompta, i durant el mig segon que triga estoc.actualitzat a arribar a cataleg, en Marc continua veient a la fitxa un formatge que ja no existeix. Ningú no ha comès cap error de programació; senzillament, la dada "unitats de formatge curat" ara viu en més d'un lloc, i aquests llocs no es posen d'acord a l'instant. La pregunta que obre aquest mòdul és què vol dir exactament que un sistema així sigui "consistent", perquè la paraula, dita sense més, no diu res: hi ha una dotzena de significats diferents, cadascun amb un cost i amb un conjunt d'anomalies que permet.

Aquesta lliçó construeix aquest vocabulari. Veurem que un model de consistència és un contracte entre el magatzem de dades i el programa que el fa servir, i recorrerem la jerarquia de contractes des del més fort (linealitzabilitat, i per què l'ideal de "consistència estricta" és físicament irrealitzable) fins al més feble (consistència eventual), passant per la serialitzabilitat de les bases de dades, la consistència seqüencial i la causal, que enllaça directament amb el happens-before i els rellotges vectorials de 01-05. Després canviarem de punt de vista i mirarem les garanties que importen a un client concret, l'Anna, quan edita la seva adreça de lliurament i la veu desaparèixer. Tot es farà visible amb una simulació en Python de les rèpliques inv-bcn i inv-vlc amb propagació retardada. Què es pot prometre quan la xarxa es parteix (CAP), com es posen d'acord els nodes (consens) i com es copien físicament les dades (replicació) són les lliçons següents; aquí només definim amb precisió què s'està prometent.

Contingut

  1. Un model de consistència és un contracte
  2. La jerarquia de models
  3. Linealitzabilitat i l'ideal irrealitzable de la consistència estricta
  4. Comprovar la linealitzabilitat d'un historial a mà (i en Python)
  5. Serialitzabilitat: s'hi assembla, però no és el mateix
  6. Consistència seqüencial
  7. Consistència causal: happens-before aplicat a les dades
  8. Consistència eventual i consistència eventual forta (CRDT)
  9. Models centrats en el client: el que l'Anna espera de la seva sessió
  10. Simulació: inv-bcn i inv-vlc amb propagació retardada
  11. Taula comparativa: model, garantia, cost i ús a Quilòmetre Zero
  12. Errors comuns i consells
  13. Exercicis
  14. Conclusió

  1. Un model de consistència és un contracte

Quan el monòlit de Quilòmetre Zero tenia una sola base de dades PostgreSQL, el programador no es preguntava mai "quina versió de l'estoc estic llegint": n'hi havia una, l'última. En distribuir la dada, apareixen diverses còpies que en cada instant poden diferir, i el magatzem ha de decidir què promet sobre aquestes còpies a qui llegeix i escriu. Aquesta promesa és el model de consistència.

Formalment, un model de consistència és el conjunt d'historials (seqüències d'operacions amb els seus resultats) que el magatzem considera vàlids. Si el programa observa un historial que el model no permet, el magatzem ha incomplert el contracte; si n'observa qualsevol altre, per estrany que li sembli, el magatzem ha complert. Dues conseqüències pràctiques:

  • El contracte té dues parts. El magatzem promet no produir certs historials, i el programa es compromet a funcionar correctament amb qualsevol historial permès. Si cataleg dona per fet que sempre llegeix l'últim estoc però el magatzem només garanteix consistència eventual, l'error no és del magatzem.
  • Més fort no vol dir millor sense més. Cada garantia addicional costa latència, disponibilitat o totes dues (ho quantificarem a 03-02). Triar un model és triar quines anomalies s'està disposat a tolerar a canvi de què.

A 01-05 vam aprendre a raonar sobre l'ordre dels esdeveniments sense rellotge global; els models de consistència són aquesta mateixa idea aplicada a lectures i escriptures: cada model imposa un tipus d'ordre diferent a les operacions.

  1. La jerarquia de models

Els models s'ordenen per força: un és més fort que un altre si permet un subconjunt dels seus historials. El diagrama mostra la jerarquia que farem servir al curs (simplificada; la real té desenes de models intermedis):

flowchart TB
    E["Consistència estricta<br/>(ideal físic: rellotge global perfecte)"]
    L["Linealitzabilitat<br/>(ordre total respectant el temps real)"]
    SS["Serialitzabilitat estricta<br/>(transaccions + temps real)"]
    SR["Serialitzabilitat<br/>(transaccions en algun ordre total)"]
    SQ["Consistència seqüencial<br/>(ordre total respectant l'ordre de cada procés)"]
    C["Consistència causal<br/>(només s'ordena allò causalment relacionat)"]
    CL["Models centrats en el client<br/>read-your-writes, monotonic reads..."]
    EV["Consistència eventual<br/>(les rèpliques convergeixen... algun dia)"]
    E -.-> L
    L --> SQ
    SS --> L
    SS --> SR
    SQ --> C
    C --> CL
    CL --> EV
    style E stroke-dasharray: 5 5

Les fletxes van de més fort a més feble. La columna esquerra (estricta → linealitzable → seqüencial → causal → eventual) es refereix a operacions individuals sobre objectes; la branca de la dreta (serialitzabilitat) es refereix a transaccions que agrupen diverses operacions, i totes dues es troben a la serialitzabilitat estricta. Recorrerem la jerarquia de dalt a baix.

  1. Linealitzabilitat i l'ideal irrealitzable de la consistència estricta

Consistència estricta

El model més fort imaginable diu: "tota lectura retorna el valor de l'escriptura més recent segons un rellotge global". És exactament el que ofereix una variable en un programa d'un sol fil, i és el que intuïtivament esperem. Però a 01-05 vam veure que el rellotge global no existeix: NTP sincronitza amb un error de mil·lisegons, i "l'escriptura més recent" no està definida per a dues escriptures que passen amb 100 microsegons de diferència a Girona i València, perquè cap informació no pot viatjar entre elles en aquest temps. La consistència estricta és un ideal físic, útil com a referència, però cap sistema distribuït no pot implementar-la ni verificar-la. Per això apareix amb línia discontínua al diagrama.

Linealitzabilitat

La linealitzabilitat (Herlihy i Wing, 1990) és la versió realitzable d'aquest ideal. Observa que tota operació en un sistema real no és instantània: té un instant d'inici (el client envia la petició) i un instant de fi (en rep la resposta). La linealitzabilitat exigeix:

  1. Existeix un ordre total de totes les operacions.
  2. En aquest ordre, cada lectura retorna el valor de l'escriptura immediatament anterior (l'especificació seqüencial de l'objecte: per a un registre, "llegir retorna l'últim que s'ha escrit").
  3. L'ordre respecta el temps real: si l'operació A va acabar abans que l'operació B comencés, A va abans que B a l'ordre.

La conseqüència intuïtiva és que cada operació sembla que passi atòmicament en algun instant entre el seu inici i el seu final, l'anomenat punt de linealització. Dues operacions que se solapen en el temps es poden ordenar de qualsevol manera (aquí hi ha la llibertat que fa el model realitzable), però un cop una operació ha acabat, el seu efecte és visible per a tothom. A Quilòmetre Zero, la linealitzabilitat és el que fa que la reserva de l'últim formatge tingui sentit: si el ReservarEstoc de l'Anna retorna "confirmada", qualsevol consulta posterior de qualsevol persona, des de qualsevol rèplica, ha de veure 0 unitats. Ni inv-vlc pot continuar dient 1.

La linealitzabilitat és componible: si cada objecte és linealitzable per separat, el sistema complet ho és. Això no passa amb la consistència seqüencial ni amb la serialitzabilitat, i és una de les raons de la seva popularitat com a garantia dels sistemes de coordinació (etcd, ZooKeeper, que veurem a 03-03).

  1. Comprovar la linealitzabilitat d'un historial a mà (i en Python)

Un historial és una llista d'operacions, cadascuna amb procés, tipus, argument o resultat, i interval de temps real. Comprovar si és linealitzable consisteix a buscar un ordre total que compleixi les tres condicions. Prenguem l'estoc de formatge-curat, que comença amb valor 1:

Operació Client Inici (ms) Fi (ms) Resultat
A Anna: escriure estoc = 0 (reserva) 0 10 ok
B Marc: llegir estoc 12 15 1
C Llúcia: llegir estoc 5 20 0

A mà. A va acabar a 10 i B va començar a 12, així que A ha d'anar abans que B. Però B va llegir 1, és a dir, el valor d'abans d'A. No existeix cap ordre vàlid: l'historial no és linealitzable. És exactament el que li passava a en Marc al tancament de 02-05. Fixa't en C: se solapa amb A (5-20 davant de 0-10), així que pot anar abans o després d'A; va llegir 0, per tant ha d'anar després. Això és legal. Si B hagués llegit 0, l'ordre A, C, B (o A, B, C) seria vàlid i l'historial seria linealitzable.

En Python. Per a historials petits, la comprovació es pot fer per força bruta: generar totes les permutacions, descartar les que violin el temps real i comprovar l'especificació del registre contra les restants. No serveix per a historials reals (el problema és NP-complet, i eines com Jepsen/Knossos fan servir algorismes molt més llestos), però fa tangible la definició:

# km0/simulacions/linealitzabilitat.py
from dataclasses import dataclass
from itertools import permutations


@dataclass(frozen=True)
class Op:
    nom: str
    client: str
    tipus: str         # "escriure" o "llegir"
    valor: int         # el que escriu, o el que ha llegit
    inici: int
    fi: int


def respecta_temps_real(ordre: list[Op]) -> bool:
    """Si A va acabar abans que B comencés, A ha d'anar abans que B."""
    for i, a in enumerate(ordre):
        for b in ordre[i + 1:]:
            if b.fi < a.inici:        # b va acabar abans que a comencés, però va després
                return False
    return True


def compleix_especificacio(ordre: list[Op], valor_inicial: int) -> bool:
    """Un registre: cada lectura retorna l'última escriptura anterior a l'ordre."""
    actual = valor_inicial
    for op in ordre:
        if op.tipus == "escriure":
            actual = op.valor
        elif op.valor != actual:
            return False
    return True


def es_linealitzable(historial: list[Op], valor_inicial: int) -> list[Op] | None:
    """Retorna un ordre de linealització vàlid, o None si no n'hi ha cap."""
    for ordre in permutations(historial):
        ordre = list(ordre)
        if respecta_temps_real(ordre) and compleix_especificacio(ordre, valor_inicial):
            return ordre
    return None


if __name__ == "__main__":
    historial = [
        Op("A", "Anna",   "escriure", 0, inici=0,  fi=10),
        Op("B", "Marc",   "llegir",   1, inici=12, fi=15),
        Op("C", "Llúcia", "llegir",   0, inici=5,  fi=20),
    ]
    ordre = es_linealitzable(historial, valor_inicial=1)
    print("Historial 1:", "linealitzable" if ordre else "NO linealitzable",
          [op.nom for op in ordre] if ordre else "")

    historial[1] = Op("B", "Marc", "llegir", 0, inici=12, fi=15)   # en Marc veu el 0
    ordre = es_linealitzable(historial, valor_inicial=1)
    print("Historial 2:", "linealitzable" if ordre else "NO linealitzable",
          [op.nom for op in ordre] if ordre else "")

Sortida:

Historial 1: NO linealitzable
Historial 2: linealitzable ['A', 'B', 'C']

Explicació del codi per a qui comença:

  • Op és una operació amb el seu interval de temps real. frozen=True la fa immutable, cosa que permet fer-la servir a permutations sense sorpreses.
  • respecta_temps_real comprova la condició 3 de la definició: recorre cada parell (a abans que b a l'ordre candidat) i falla si b va acabar estrictament abans que a comencés.
  • compleix_especificacio recorre l'ordre portant el valor "actual" del registre i comprova que cada lectura retorna aquest valor. Canviar aquesta funció permetria comprovar altres objectes (una cua, un comptador).
  • es_linealitzable prova tots els ordres. Amb 3 operacions són 6 permutacions; amb 10 serien 3,6 milions. Serveix per entendre-ho, no per a producció.

  1. Serialitzabilitat: s'hi assembla, però no és el mateix

La serialitzabilitat ve del món de les bases de dades i parla de transaccions, no d'operacions individuals: un historial de transaccions és serialitzable si el seu resultat és igual al d'algun ordre seqüencial d'aquestes mateixes transaccions. És la "I" d'ACID en la seva forma més forta (reprendrem ACID a 03-05). Es confon constantment amb la linealitzabilitat perquè totes dues parlen d'"un ordre total", però difereixen en dues coses:

Aspecte Linealitzabilitat Serialitzabilitat
Unitat Una operació sobre un objecte Una transacció sobre diversos objectes
Restricció temporal Sí: respecta el temps real No: qualsevol ordre seqüencial val, encara que contradigui el temps real
Composició Componible per objecte No componible
On es veu Registres, locks, cues, sistemes de coordinació Bases de dades relacionals (nivell SERIALIZABLE)

L'absència de restricció temporal té conseqüències reals. Imagina que comandes executa la transacció T1 (crear P-2026-000123) i, després de rebre el "commit ok", la Llúcia executa T2 (llistar les comandes d'avui). Un sistema serialitzable pot ordenar legalment T2 abans que T1 i retornar a la Llúcia una llista sense la comanda, perquè aquest ordre seqüencial és vàlid. PostgreSQL amb SERIALIZABLE en un sol node no ho fa a la pràctica, però una base de dades distribuïda serialitzable amb rèpliques endarrerides sí que pot fer-ho.

La combinació de totes dues, la serialitzabilitat estricta (strict serializability), exigeix un ordre seqüencial de transaccions que a més respecti el temps real. És la garantia més forta que s'ofereix a la pràctica (Spanner la implementa amb TrueTime, esmentat a 01-05; CockroachDB i FoundationDB també la persegueixen) i la més cara. Quan a 03-02 parlem de la "C" de CAP, ens referirem a linealitzabilitat; quan a 03-05 parlem de transaccions, a serialitzabilitat.

  1. Consistència seqüencial

Relaxem la linealitzabilitat traient la restricció de temps real i deixant només aquesta: existeix un ordre total que respecta l'ordre de programa de cada procés. És a dir, les operacions de l'Anna apareixen en l'ordre en què l'Anna les va fer, les d'en Marc en l'ordre d'en Marc, però com s'entrellacen totes dues seqüències és lliure, sense que importi el rellotge.

Amb consistència seqüencial, l'historial 1 de l'apartat 4 sí que seria vàlid: l'ordre B, A, C (en Marc llegeix 1, l'Anna escriu 0, la Llúcia llegeix 0) respecta l'ordre de cada procés (cadascun va fer una sola operació) i l'especificació del registre. Que en Marc comencés a llegir després que l'Anna hagués acabat no importa. El que la consistència seqüencial prohibeix són historials on un procés vegi les seves pròpies operacions desordenades, o on dos processos vegin les escriptures d'altres en ordres diferents. Aquest és el model que ofereixen les CPU multinucli amb algunes restriccions (el "model de memòria" de Java o C++ està construït sobre aquesta idea) i, en sistemes distribuïts, un magatzem amb un sol líder que ordena totes les escriptures i rèpliques que les apliquen en aquest mateix ordre, encara que amb retard.

A Quilòmetre Zero, la consistència seqüencial és suficient per a l'historial de posicions de furgoneta-3: tothom qui miri el mapa veurà la furgoneta recórrer els mateixos carrers en el mateix ordre, encara que un la vegi un segon per darrere d'un altre.

  1. Consistència causal: happens-before aplicat a les dades

La consistència seqüencial continua exigint un ordre total, i això obliga que tots els nodes acordin com entrellaçar operacions que no tenen res a veure entre elles. La consistència causal relaxa precisament això: només exigeix que es respecti l'ordre de les operacions causalment relacionades, i deixa les concurrents en qualsevol ordre, fins i tot diferent per a observadors diferents.

"Causalment relacionades" és exactament la relació happens-before de 01-05, aplicada a lectures i escriptures:

  • Si un procés fa l'operació A i després la B, A → B.
  • Si un procés llegeix un valor escrit per A i després escriu B, A → B (l'escriptura pot haver depès d'allò llegit).
  • Transitivitat.

I "concurrents" són les operacions que no estan relacionades en cap direcció, les mateixes que a 01-05 detectàvem amb MarcaVectorial.concurrent. No és casualitat: els sistemes amb consistència causal (COPS, Antidote, o el mode causal de MongoDB) s'implementen amb rellotges vectorials o estructures equivalents, i una rèplica només aplica una escriptura quan ja ha aplicat totes les que la precedien causalment.

L'exemple canònic és una conversa. En Marc publica una pregunta a la fitxa de la Formatgeria Montblanc ("el curat porta llet crua?") i la formatgeria respon ("sí, de vaca frisona"). La resposta depèn causalment de la pregunta (la formatgeria la va llegir abans d'escriure). Amb consistència eventual, la Llúcia en una altra rèplica podria veure la resposta abans que la pregunta: un absurd. Amb consistència causal, això està prohibit; però si l'Anna publica al mateix temps una pregunta independent sobre l'enviament, que la Llúcia la vegi abans o després que la d'en Marc és irrellevant i el sistema no gasta res a decidir-ho.

La consistència causal és el model més fort que es pot oferir sense sacrificar disponibilitat durant una partició de xarxa, un resultat que la converteix en el punt d'equilibri preferit de la recerca acadèmica i que donarà sentit a la discussió de 03-02.

  1. Consistència eventual i consistència eventual forta (CRDT)

A l'extrem feble hi ha la consistència eventual: si deixen d'arribar escriptures, totes les rèpliques acabaran tenint el mateix valor. No diu quan ("eventual" pot ser un mil·lisegon o una hora), no diu què es llegeix mentrestant, i no diu quin serà el valor final si hi ha hagut escriptures concurrents. És més una propietat de convergència (o liveness) que un model de consistència en el sentit de l'apartat 1: gairebé qualsevol historial és vàlid mentre duri l'activitat. La seva virtut és que es pot oferir sempre, amb qualsevol xarxa i qualsevol latència, i per això és el model per defecte de DNS, de les memòries cau i de la majoria dels magatzems "AP" (03-02).

El problema de la consistència eventual pura és la reconciliació: quan dues rèpliques han acceptat escriptures concurrents, algú ha de decidir el valor final, i l'estratègia més comuna ("guanya l'última escriptura", last-write-wins) perd dades silenciosament, com veurem amb cruesa a 03-02. La consistència eventual forta (strong eventual consistency, Shapiro et al., 2011) elimina aquesta decisió: exigeix que dues rèpliques que hagin rebut el mateix conjunt d'actualitzacions, en qualsevol ordre, estiguin en el mateix estat. No cal reconciliar perquè el mateix tipus de dada està dissenyat perquè la fusió sigui determinista. Aquests tipus són els CRDT (Conflict-free Replicated Data Types).

El CRDT més senzill és el comptador de només increment, G-Counter: cada rèplica porta el seu propi compte, el valor total és la suma, i fusionar dos estats és prendre el màxim component a component (mai no es perd cap increment perquè cada rèplica només fa pujar la seva pròpia casella):

# km0/simulacions/gcounter.py
class GCounter:
    """Comptador replicat de només increment (CRDT basat en estat)."""

    def __init__(self, repliques: list[str]):
        self.comptes = {r: 0 for r in repliques}

    def incrementar(self, replica: str, n: int = 1) -> None:
        self.comptes[replica] += n            # cada rèplica només toca la seva casella

    def valor(self) -> int:
        return sum(self.comptes.values())

    def fusionar(self, altre: "GCounter") -> None:
        for r in self.comptes:
            self.comptes[r] = max(self.comptes[r], altre.comptes[r])

    def __repr__(self) -> str:
        return f"GCounter({self.comptes}, total={self.valor()})"


if __name__ == "__main__":
    repliques = ["inv-bcn", "inv-vlc"]
    # Unitats venudes de formatge-curat durant la "Setmana del Formatge Artesà",
    # comptades localment a cada rèplica sense coordinació.
    bcn = GCounter(repliques)
    vlc = GCounter(repliques)
    bcn.incrementar("inv-bcn", 3)      # 3 vendes a Barcelona
    vlc.incrementar("inv-vlc", 2)      # 2 a València, concurrents
    print("abans de fusionar:", bcn, vlc)

    # Fusió en totes dues direccions (tant és l'ordre: l'operació és commutativa,
    # associativa i idempotent)
    copia_bcn = GCounter(repliques); copia_bcn.comptes = dict(bcn.comptes)
    bcn.fusionar(vlc)
    vlc.fusionar(copia_bcn)
    print("després de fusionar:", bcn, vlc)
    bcn.fusionar(vlc)                  # fusionar una altra vegada no canvia res
    print("fusió repetida:", bcn)

Sortida:

abans de fusionar: GCounter({'inv-bcn': 3, 'inv-vlc': 0}, total=3) GCounter({'inv-bcn': 0, 'inv-vlc': 2}, total=2)
després de fusionar: GCounter({'inv-bcn': 3, 'inv-vlc': 2}, total=5) GCounter({'inv-bcn': 3, 'inv-vlc': 2}, total=5)
fusió repetida: GCounter({'inv-bcn': 3, 'inv-vlc': 2}, total=5)

La clau és a fusionar: max és commutativa (tant és qui fusiona qui), associativa (tant és en quin ordre arribin tres estats) i idempotent (fusionar dues vegades no duplica). Amb aquestes tres propietats, la propagació pot ser tan descurada com es vulgui (duplicats, reordenacions, retards) i les rèpliques convergeixen igualment. Hi ha CRDT per a conjunts (G-Set, OR-Set), registres (LWW-Register, MV-Register), mapes i text col·laboratiu, i els farem servir a 03-04 com una estratègia de resolució de conflictes en replicació multilíder.

El que un CRDT no pot fer és mantenir un invariant global com "l'estoc mai no baixa de zero": un comptador PN (increments i decrements) replicat permetria que inv-bcn i inv-vlc descomptessin cadascuna l'última unitat i el total fusionat fos -1. Comptar visites a la fitxa de tomaquet-rosa o unitats venudes en una campanya sí que és un cas de CRDT; reservar l'última unitat, no. Aquesta diferència entre "dades que se sumen" i "dades que es disputen" és la que guiarà les decisions de 03-02.

  1. Models centrats en el client: el que l'Anna espera de la seva sessió

Els models anteriors descriuen el sistema des de fora, per a tots els clients alhora. Però moltes anomalies que molesten de debò un usuari són sobre la seva pròpia sessió, i hi ha un conjunt de garanties, formulades per Terry et al. per al sistema Bayou el 1994, que es poden oferir amb un cost baix fins i tot sobre consistència eventual. Les quatre es veuen amb l'Anna editant la seva adreça de lliurament des del web, amb el perfil replicat en dos nodes i propagació retardada:

Garantia Què promet Anomalia que evita Escena amb l'Anna
Read-your-writes (llegeix les teves escriptures) Després d'escriure un valor, el mateix client mai no en llegeix un d'anterior "He desat i ha desaparegut" L'Anna canvia la seva adreça de Carrer Major 12, Girona a Passeig de Gràcia 5, Barcelona, prem desar, recarrega la pàgina i veu la de Girona perquè la recàrrega ha caigut a la rèplica endarrerida
Monotonic reads (lectures monòtones) Si un client ha llegit una versió, no en llegirà després una de més antiga "Ha tornat enrere en el temps" L'Anna veu la seva adreça nova, torna a la pàgina i veu l'antiga; recarrega, i torna la nova
Monotonic writes (escriptures monòtones) Les escriptures d'un client s'apliquen a totes les rèpliques en l'ordre en què les va fer "El meu segon canvi ha trepitjat el primer" L'Anna canvia l'adreça i després el telèfon; una rèplica aplica primer el telèfon (amb l'adreça antiga incrustada al mateix document) i després l'adreça; una altra ho fa al revés, i l'estat final difereix
Writes-follow-reads (les escriptures segueixen les lectures) Una escriptura feta després de llegir un valor s'ordena després de l'escriptura que va produir aquest valor "Resposta abans que la pregunta" L'Anna llegeix la resposta de la Formatgeria Montblanc i escriu "gràcies"; el seu "gràcies" mai no ha de ser visible en una rèplica que encara no mostra la resposta

Les quatre juntes equivalen a la consistència causal restringida a un client (per això al diagrama de l'apartat 2 són just a sota). I les quatre s'aconsegueixen amb dues tècniques barates que veurem a la simulació:

  • Sessions enganxoses (sticky sessions): cada client parla sempre amb la mateixa rèplica. Trivialment dona read-your-writes i monotonic reads, amb l'inconvenient que si la rèplica cau, la sessió perd les seves garanties (o cal esperar que una altra rèplica es posi al dia).
  • Versions al client: el client recorda la versió (un número, un LSN de PostgreSQL, una marca vectorial) de l'últim que va escriure o llegir, i cada lectura exigeix a la rèplica "no em responguis fins que tinguis com a mínim aquesta versió". Funciona amb qualsevol rèplica i és el que fan els causal tokens de MongoDB o el ReadYourWrites d'algunes biblioteques client.

  1. Simulació: inv-bcn i inv-vlc amb propagació retardada

Construirem en Python dues rèpliques de l'estoc amb un mecanisme deliberadament simple: cada escriptura rep un número de versió creixent, s'aplica a la rèplica que la rep i es propaga a l'altra amb un retard. Un balancejador reparteix les lectures a l'atzar entre totes dues. Amb això n'hi haurà prou per veure aparèixer les anomalies de l'apartat anterior i per corregir-les.

# km0/simulacions/repliques_retardades.py
import random
from dataclasses import dataclass, field


@dataclass
class Versio:
    valor: int
    numero: int          # versió creixent assignada pel sistema


@dataclass
class Replica:
    nom: str
    dades: dict[str, Versio] = field(default_factory=dict)
    pendents: list[tuple[int, str, Versio]] = field(default_factory=list)  # (instant, producte, versió)

    def aplicar(self, producte: str, v: Versio) -> None:
        actual = self.dades.get(producte)
        if actual is None or v.numero > actual.numero:     # mai no retrocedir de versió
            self.dades[producte] = v

    def lliurar(self, ara: int) -> None:
        """Aplica les propagacions l'instant d'arribada de les quals ja ha passat."""
        llestes = [p for p in self.pendents if p[0] <= ara]
        self.pendents = [p for p in self.pendents if p[0] > ara]
        for _, producte, v in sorted(llestes):
            self.aplicar(producte, v)

    def llegir(self, producte: str) -> Versio:
        return self.dades[producte]


class Sistema:
    """Dues rèpliques, propagació asíncrona amb retard, balancejador aleatori."""

    def __init__(self, retard_ms: int, llavor: int = 7):
        self.repliques = {"inv-bcn": Replica("inv-bcn"), "inv-vlc": Replica("inv-vlc")}
        self.retard = retard_ms
        self.rellotge = 0
        self.ultima_versio = 0
        self.rng = random.Random(llavor)

    def avancar(self, ms: int) -> None:
        self.rellotge += ms
        for r in self.repliques.values():
            r.lliurar(self.rellotge)

    def escriure(self, replica: str, producte: str, valor: int) -> Versio:
        self.ultima_versio += 1
        v = Versio(valor, self.ultima_versio)
        self.repliques[replica].aplicar(producte, v)
        for nom, altra in self.repliques.items():
            if nom != replica:
                altra.pendents.append((self.rellotge + self.retard, producte, v))
        return v

    def replica_a_latzar(self) -> Replica:
        return self.rng.choice(list(self.repliques.values()))


def escenari_sense_garanties() -> None:
    print("=== Sense garanties: balancejador aleatori, propagació de 300 ms ===")
    s = Sistema(retard_ms=300)
    s.escriure("inv-bcn", "formatge-curat", 3); s.avancar(1000)     # estat inicial propagat
    v = s.escriure("inv-bcn", "formatge-curat", 2)                  # l'Anna reserva 1 unitat a inv-bcn
    print(f"t={s.rellotge:4} ms  Anna reserva: estoc=2 (versió {v.numero}) a inv-bcn")
    for _ in range(4):
        s.avancar(100)
        r = s.replica_a_latzar()
        lectura = r.llegir("formatge-curat")
        print(f"t={s.rellotge:4} ms  Anna llegeix a {r.nom}: estoc={lectura.valor} (versió {lectura.numero})")


class ClientEnganxos:
    """Sempre llegeix de la rèplica amb què va començar."""
    def __init__(self, s: Sistema, replica: str):
        self.s, self.replica = s, replica
    def llegir(self, producte: str) -> Versio:
        return self.s.repliques[self.replica].llegir(producte)


class ClientVersionat:
    """Recorda l'última versió vista i rebutja rèpliques més antigues."""
    def __init__(self, s: Sistema):
        self.s, self.minim = s, 0
    def escriure(self, replica: str, producte: str, valor: int) -> None:
        self.minim = self.s.escriure(replica, producte, valor).numero
    def llegir(self, producte: str) -> tuple[str, Versio]:
        for r in self.s.rng.sample(list(self.s.repliques.values()), k=2):   # prova en ordre aleatori
            v = r.llegir(producte)
            if v.numero >= self.minim:
                self.minim = v.numero           # monotonic reads: mai no acceptar menys
                return r.nom, v
        raise TimeoutError("cap rèplica no té encara la versió mínima; reintentar més tard")


def escenari_amb_garanties() -> None:
    print("\n=== Sessió enganxosa a inv-bcn ===")
    s = Sistema(retard_ms=300)
    s.escriure("inv-bcn", "formatge-curat", 3); s.avancar(1000)
    anna = ClientEnganxos(s, "inv-bcn")
    s.escriure("inv-bcn", "formatge-curat", 2)
    for _ in range(3):
        s.avancar(100)
        print(f"t={s.rellotge:4} ms  Anna llegeix a inv-bcn: estoc={anna.llegir('formatge-curat').valor}")

    print("\n=== Client amb versió mínima, balancejador aleatori ===")
    s = Sistema(retard_ms=300)
    s.escriure("inv-bcn", "formatge-curat", 3); s.avancar(1000)
    anna = ClientVersionat(s)
    anna.escriure("inv-bcn", "formatge-curat", 2)
    for _ in range(4):
        s.avancar(100)
        try:
            nom, v = anna.llegir("formatge-curat")
            print(f"t={s.rellotge:4} ms  Anna llegeix a {nom}: estoc={v.valor} (versió {v.numero})")
        except TimeoutError as e:
            print(f"t={s.rellotge:4} ms  {e}")


if __name__ == "__main__":
    escenari_sense_garanties()
    escenari_amb_garanties()

Sortida (la llavor fixa fa l'execució reproduïble):

=== Sense garanties: balancejador aleatori, propagació de 300 ms ===
t=1000 ms  Anna reserva: estoc=2 (versió 2) a inv-bcn
t=1100 ms  Anna llegeix a inv-vlc: estoc=3 (versió 1)
t=1200 ms  Anna llegeix a inv-bcn: estoc=2 (versió 2)
t=1300 ms  Anna llegeix a inv-vlc: estoc=2 (versió 2)
t=1400 ms  Anna llegeix a inv-bcn: estoc=2 (versió 2)

=== Sessió enganxosa a inv-bcn ===
t=1100 ms  Anna llegeix a inv-bcn: estoc=2
t=1200 ms  Anna llegeix a inv-bcn: estoc=2
t=1300 ms  Anna llegeix a inv-bcn: estoc=2

=== Client amb versió mínima, balancejador aleatori ===
t=1100 ms  Anna llegeix a inv-bcn: estoc=2 (versió 2)
t=1200 ms  Anna llegeix a inv-bcn: estoc=2 (versió 2)
t=1300 ms  Anna llegeix a inv-bcn: estoc=2 (versió 2)
t=1400 ms  Anna llegeix a inv-vlc: estoc=2 (versió 2)

Què mostra cada bloc:

  • Sense garanties: a t=1100 l'Anna, que acaba de reservar, llegeix 3 a inv-vlc: violació de read-your-writes. Si la seqüència de lectures hagués estat bcn, vlc, bcn (canvia la llavor i ho veuràs), hauria llegit 2, 3, 2: violació de monotonic reads. És literalment la història d'en Marc i el formatge de 02-05, ara amb la mateixa Anna com a víctima.
  • Sessió enganxosa: en llegir sempre d'inv-bcn, on va escriure, l'Anna veu la seva reserva des del primer instant. El cost és que la càrrega no es reparteix i que si inv-bcn cau, la sessió de l'Anna es trenca.
  • Client amb versió mínima: l'Anna porta amb ella minim = 2. Quan el balancejador l'envia a inv-vlc abans de t=1300, inv-vlc només té la versió 1 i el client la descarta i prova l'altra rèplica (per això les tres primeres lectures acaben a inv-bcn encara que l'ordre de prova sigui aleatori). A t=1400 la propagació ja ha arribat i inv-vlc respon amb la versió 2. Si totes dues rèpliques estiguessin endarrerides, el client esperaria (TimeoutError) en lloc de mentir. Observa que aplicar mai no retrocedeix de versió: això és el que dona monotonic writes a nivell de rèplica.

En un sistema real, el "número de versió" seria l'LSN del WAL de PostgreSQL, l'offset de Kafka, o una marca vectorial com la de 01-05; ho veurem a 03-04 quan muntem la rèplica de km0_comandes de debò.

  1. Taula comparativa: model, garantia, cost i ús a Quilòmetre Zero

Model Garantia (en una frase) Cost típic On el fa servir Quilòmetre Zero
Consistència estricta Lectura = última escriptura per rellotge global Irrealitzable Mai (referència teòrica)
Linealitzabilitat Ordre total que respecta el temps real; cada operació és atòmica en un instant Latència de coordinació a cada operació; no disponible durant particions Reserva de l'últim formatge-curat; locks i elecció de líder (etcd, 03-03); saldo a pagaments
Serialitzabilitat estricta Transaccions en ordre seqüencial que respecta el temps real La més cara; requereix rellotges acotats o coordinació global Cap avui; candidata si pagaments necessités transaccions multiobjecte distribuïdes
Serialitzabilitat Transaccions equivalents a algun ordre seqüencial Aborts per conflicte, latència Dins de cada servei, PostgreSQL amb SERIALIZABLE a km0_comandes
Consistència seqüencial Ordre total que respecta l'ordre de cada procés Un líder que ordena; les rèpliques poden endarrerir-se Historial de posicions de furgoneta-3 (tothom veu el mateix recorregut)
Consistència causal Només s'ordena allò causalment relacionat Marques vectorials o equivalents; metadades per operació Preguntes i respostes a fitxes de productors; comentaris de comandes
Centrats en el client Read-your-writes, monotonic reads/writes, writes-follow-reads per a cada sessió Sessions enganxoses o versions al client Perfil i adreça de l'Anna; cistell; "les meves comandes"
Consistència eventual forta (CRDT) Rèpliques amb les mateixes actualitzacions tenen el mateix estat, sense reconciliar Tipus de dada restringits; no admet invariants globals Comptadors de vendes per campanya, visites a fitxes, "m'agrada"
Consistència eventual Les rèpliques convergeixen si cessen les escriptures Gairebé nul; anomalies de tota mena mentrestant Memòria cau del catàleg a Redis; índex de cerca; agregats d'analitica

La lectura important de la taula és que Quilòmetre Zero no tria un model, en tria un per dada. La mateixa plataforma necessita linealitzabilitat per a l'última unitat i s'acontenta amb eventual per al nombre de visites. Justificar cada fila de l'última columna davant de les fallades de xarxa és exactament el tema de la propera lliçó.

Errors Comuns i Consells

  • Dir "consistent" sense cognom. En una reunió de disseny, "la base de dades és consistent" no vol dir res. Pregunta sempre: linealitzable?, serialitzable?, causal?, eventual amb quina reconciliació? La resposta canvia l'arquitectura.
  • Confondre la C d'ACID amb la C de CAP. La consistència d'ACID és "les transaccions respecten els invariants de l'esquema" (claus foranes, restriccions). La dels models d'aquesta lliçó és sobre l'ordre de lectures i escriptures entre rèpliques. No tenen res a veure, i a 03-02 la C de CAP serà concretament linealitzabilitat.
  • Confondre serialitzabilitat amb linealitzabilitat. Una base de dades distribuïda SERIALIZABLE et pot retornar una lectura antiga després que la teva transacció hagi confirmat. Si necessites totes dues coses, el terme que busques és serialitzabilitat estricta, i el preu és alt.
  • Creure que "eventual" és un termini. No ho és. Si un requisit diu "eventualment consistent, en menys d'un segon", el segon és un objectiu operatiu (SLO) que cal mesurar (07-01), no una garantia del model.
  • Demanar linealitzabilitat a tot per precaució. Cada operació linealitzable travessa la xarxa com a mínim una vegada amb coordinació. Aplicar-la al comptador de visites de tomaquet-rosa multiplicaria la latència sense cap benefici. Classifica les dades com a la taula de l'apartat 11.
  • Oblidar les garanties de sessió en afegir rèpliques de lectura. L'error més freqüent a la pràctica: s'afegeix una rèplica per escalar lectures i de sobte els usuaris "perden" el que acaben de desar. Abans d'encaminar lectures a rèpliques, decideix si faràs servir sessions enganxoses o versions.
  • Consell: quan dissenyis un servei, escriu al costat de cada taula o entitat el model de consistència que necessita i l'anomalia concreta que aquest model evita. Si no saps anomenar l'anomalia, probablement el model feble és suficient.

Exercicis

Exercici 1: Classificar historials

L'estoc de vi-crianca del Celler Roure Alt comença a 5. Per a cada historial, indica si és linealitzable, si és seqüencialment consistent i si és causalment consistent (raona-ho, i comprova la linealitzabilitat amb es_linealitzable):

Historial H1

Op Client Inici Fi Operació
A Anna 0 10 escriure 4
B Marc 20 30 escriure 3
C Llúcia 40 50 llegir → 4

Historial H2 (dos processos, sense temps, només l'ordre dins de cadascun)

  • Anna: escriure 4; llegir → 4; llegir → 3
  • Marc: escriure 3; llegir → 3; llegir → 4

Exercici 2: Diagnosticar l'anomalia de sessió

Un usuari informa del següent a l'app de Quilòmetre Zero: "He afegit carbasso al cistell, he anat a la pestanya de pagament i el cistell era buit; he tornat enrere i hi havia el carbassó; he tornat a pagament i tornava a ser buit". El cistell és en dues rèpliques amb replicació asíncrona i un balancejador round-robin. Indica quines garanties de sessió es violen, quina de les dues tècniques de l'apartat 9 aplicaries i quin inconvenient tindria cadascuna en el cas concret d'un cistell.

Exercici 3: Un CRDT que no ho ha de ser

Modifica GCounter per obtenir un PNCounter (increments i decrements, amb dos G-Counter interns, positius i negatius). Fes-lo servir per modelar l'estoc de formatge-fresc (inicial 1) amb inv-bcn i inv-vlc descomptant concurrentment una unitat cadascuna, fusiona i mostra el valor. Explica per què el resultat demostra que l'estoc no s'ha de modelar com a CRDT i quina dada de Quilòmetre Zero sí que encaixaria amb un PNCounter.

Solucions

Solució 1:

H1: A acaba (10) abans que B comenci (20), i B acaba (30) abans que C comenci (40); el temps real força l'ordre A, B, C. En aquest ordre C hauria de llegir 3, però va llegir 4: no és linealitzable. Sense la restricció temporal, l'ordre B, A, C és vàlid (cada procés té una sola operació, així que l'ordre de programa no restringeix res) i C llegeix 4: sí que és seqüencialment consistent, i per tant també causalment consistent (A i B són concurrents en el sentit causal, la Llúcia les pot veure en qualsevol ordre). es_linealitzable retorna None per a H1 amb valor_inicial=5.

H2: no hi ha temps, així que la linealitzabilitat no es pot avaluar més enllà del que és seqüencial. Existeix un ordre total que respecti l'ordre de programa de cadascun? L'Anna necessita veure 4 i després 3, així que a l'ordre total la seva escriptura de 4 precedeix la d'en Marc (3) o com a mínim l'Anna llegeix entremig; en Marc necessita veure 3 i després 4, així que l'escriptura de 3 precedeix la de 4. Totes dues exigències són contradictòries en un únic ordre total: no és seqüencialment consistent. Tanmateix, les dues escriptures són causalment concurrents (cap procés no va llegir la de l'altre abans d'escriure), així que cada procés les pot aplicar en un ordre diferent i les lectures són legals: sí que és causalment consistent. És l'exemple clàssic de la diferència entre tots dos models.

Solució 2:

Es violen monotonic reads (l'usuari veu el cistell amb carbassó, després buit, després amb carbassó: retrocedeix en el temps) i, a la primera visita a pagament, read-your-writes (acaba d'escriure el carbassó i no el llegeix). El round-robin garanteix precisament alternar rèpliques, la pitjor opció possible sense garanties de sessió.

  • Sessió enganxosa: el balancejador encamina cada usuari sempre a la mateixa rèplica (per galeta o per hash de l'id d'usuari). Resol totes dues anomalies amb zero canvis a l'aplicació. Inconvenient per a un cistell: si la rèplica cau, l'usuari perd la sessió a mitja compra (o cal esperar que l'altra rèplica assoleixi la versió); a més, un usuari amb mòbil i navegador podria caure en rèpliques diferents si l'enganxositat és per connexió i no per usuari.
  • Versió al client: l'app desa la versió del cistell després de cada escriptura i l'envia a cada lectura; la rèplica que no hi arriba redirigeix o espera. Tolera caigudes de rèplica i funciona en diversos dispositius. Inconvenient: cal tocar client i servidor, i en el pitjor cas (totes les rèpliques endarrerides) la lectura espera. Per a un cistell, la segona és preferible; una alternativa habitual és encaminar totes les operacions del cistell, lectures incloses, al node primari, sacrificant l'escalat de lectures per a aquesta dada petita i crítica.

Solució 3:

from gcounter import GCounter


class PNCounter:
    def __init__(self, repliques: list[str]):
        self.positius = GCounter(repliques)
        self.negatius = GCounter(repliques)
    def incrementar(self, replica: str, n: int = 1) -> None:
        self.positius.incrementar(replica, n)
    def decrementar(self, replica: str, n: int = 1) -> None:
        self.negatius.incrementar(replica, n)
    def valor(self) -> int:
        return self.positius.valor() - self.negatius.valor()
    def fusionar(self, altre: "PNCounter") -> None:
        self.positius.fusionar(altre.positius)
        self.negatius.fusionar(altre.negatius)

repliques = ["inv-bcn", "inv-vlc"]
bcn, vlc = PNCounter(repliques), PNCounter(repliques)
bcn.incrementar("inv-bcn", 1)          # arriba 1 formatge fresc, es propaga a totes dues
vlc.fusionar(bcn)
bcn.decrementar("inv-bcn")             # l'Anna el reserva a Barcelona
vlc.decrementar("inv-vlc")             # en Marc el reserva a València, concurrentment
print(bcn.valor(), vlc.valor())        # 0 0: cada rèplica creu que ha venut l'últim
bcn.fusionar(vlc); vlc.fusionar(bcn)
print(bcn.valor(), vlc.valor())        # -1 -1

El CRDT ha fet exactament el que promet: les dues rèpliques convergeixen al mateix estat sense coordinació. Però l'estat és -1: s'ha venut un formatge que no existeix. Un CRDT garanteix convergència, no invariants que depenen de veure l'estat global abans de decidir (com "no descomptar si en queda zero"). Decidir sobre l'última unitat requereix que algú tingui l'última paraula, és a dir, linealitzabilitat o com a mínim coordinació (03-02, 03-03). Un PNCounter sí que encaixa per a dades on restar no viola res: unitats reservades i després alliberades en un comptador estadístic de campanya, o el nombre d'articles a la llista de desitjos de l'Anna (afegir i treure sense límit inferior significatiu).

Conclusió

Un model de consistència és el contracte que fixa quins historials de lectures i escriptures pot produir un magatzem replicat, i aquesta lliçó ha recorregut la jerarquia de contractes amb el vocabulari que farem servir la resta del curs. La consistència estricta és un ideal físic impossible sense rellotge global; la linealitzabilitat és la seva versió realitzable, on cada operació sembla atòmica en algun punt entre el seu inici i el seu final, i hem comprovat a mà i amb es_linealitzable que l'historial d'en Marc veient el formatge de l'Anna no la compleix. La serialitzabilitat parla de transaccions i no respecta el temps real, i la seva unió amb la linealitzabilitat és la costosa serialitzabilitat estricta. Baixant per la jerarquia, la consistència seqüencial només exigeix respectar l'ordre de cada procés; la causal, únicament l'ordre d'allò relacionat per happens-before, cosa que la connecta amb els rellotges vectorials de 01-05 i la converteix en el model més fort compatible amb la disponibilitat; i l'eventual només promet convergència, llevat que es faci servir un CRDT com GCounter, que converteix la fusió en una operació determinista a canvi de renunciar a invariants com "l'estoc no baixa de zero". Les garanties centrades en el client (read-your-writes, monotonic reads, monotonic writes, writes-follow-reads) han resultat ser les que l'Anna nota de debò, i la simulació d'inv-bcn i inv-vlc ha mostrat com les sessions enganxoses i les versions al client les restauren sobre una replicació endarrerida. La taula final deixa clar que Quilòmetre Zero no tria un model, sinó un per dada.

Queda la pregunta que la taula esquiva: per què no donar linealitzabilitat a tot? Si inv-bcn i inv-vlc no poden parlar entre elles durant trenta segons perquè un router de Barcelona s'ha reiniciat, la reserva de l'últim formatge pot esperar o pot acceptar-se a tots dos costats i arreglar-se després, però no pot ser linealitzable i estar disponible a les dues ciutats alhora. Aquesta impossibilitat té nom i enunciat formal, es malinterpreta més del que s'entén i té una extensió que parla també de la latència en absència de fallades. És el tema de la lliçó següent: el teorema CAP i PACELC.

◄ Anterior
◄
Següent ►
►

Curs d'Arquitectures Distribuïdes

Mòdul 1: Introducció als Sistemes Distribuïts

Mòdul 2: Comunicació en Sistemes Distribuïts

Mòdul 3: Consistència i Replicació

Mòdul 4: Emmagatzematge Distribuït

Mòdul 5: Computació Distribuïda

Mòdul 6: Seguretat en Sistemes Distribuïts

Mòdul 7: Monitoratge i Manteniment

Mòdul 8: Casos d'Estudi i Aplicacions

El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats