El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

A la lliçó anterior vam dir amb naturalitat que un sistema CP "rebutja les escriptures que no assoleixen quòrum" i que "el costat de la partició amb majoria continua funcionant". Darrere d'aquestes frases hi ha un problema que la informàtica distribuïda va trigar dècades a resoldre: com un grup de nodes, cadascun amb el seu propi rellotge, amb missatges que es perden o arriben tard i amb companys que poden morir en qualsevol moment, es posa d'acord en un valor, de manera que cap no decideixi una cosa diferent i que, si les coses van raonablement bé, algun decideixi de debò. Aquest problema s'anomena consens, i és la peça que converteix l'etiqueta "CP" en un mecanisme.

Aquesta lliçó l'aborda en tres nivells. Primer, el problema en si: quines propietats exigeix, per què el resultat FLP de 01-02 diu que no té solució garantida en un sistema asíncron i per què, tot i així, es resol a la pràctica cada dia. Segon, els dos algorismes que dominen la indústria: Paxos, l'original de Lamport, amb els seus rols i les seves dues fases, i Raft, dissenyat per ser comprensible, amb els seus termes, la seva elecció de líder i el seu log replicat; tots dos amb simulacions en Python que mostren diversos proposers en conflicte i un líder que cau. Tercer, una visió general del consens bizantí (PBFT) i de quan cal. Tancarem amb els sistemes que empaqueten aquests algorismes (etcd, ZooKeeper, Consul) i amb el seu primer ús real a Quilòmetre Zero: garantir que només una instància del relay outbox de 02-05 publica en cada moment, fent servir etcd amb un lease. La replicació de dades en general (líder-seguidor, multilíder, quòrums de lectura i escriptura) és la lliçó següent; aquí el consens serveix per triar líders i acordar valors petits.

Contingut

El problema del consens
Per què és difícil: FLP i la sortida pràctica
Per a què es fa servir el consens
Paxos: rols, fases i números de proposta
Simulació: Paxos amb dos proposers en conflicte
Raft: termes, elecció de líder i log replicat
Simulació: elecció de líder a Raft i caiguda del líder
Consens bizantí: PBFT en una pàgina
Taula comparativa: Paxos, Raft i PBFT
Sistemes que l'implementen i el seu ús a Quilòmetre Zero: etcd i el relay outbox
Errors comuns i consells
Exercicis
Conclusió

El problema del consens

Un conjunt de N processos, cadascun amb un valor inicial propi proposat, ha de decidir un únic valor. Un algorisme de consens és correcte si compleix tres propietats:

Propietat	Enunciat	Tipus
Acord (agreement)	Dos processos correctes mai no decideixen valors diferents	Seguretat (safety): mai no passa res dolent
Validesa (validity)	El valor decidit va ser proposat per algun procés (no val decidir un valor per defecte que ningú no va proposar)	Seguretat
Terminació (termination)	Tot procés correcte acaba decidint	Vivacitat (liveness): alguna cosa bona acaba passant

Les dues primeres són propietats de seguretat: es poden violar en un instant concret i ja no hi ha marxa enrere (si inv-bcn decideix que el líder és relay-1 i inv-vlc que és relay-2, el mal ja està fet). La tercera és de vivacitat: només es viola si el sistema es queda encallat per sempre. Aquesta distinció és central perquè, com veurem, els algorismes pràctics mai no sacrifiquen seguretat i accepten sacrificar vivacitat temporalment.

A Quilòmetre Zero, el "valor" a decidir seran coses com "qui és el líder del relay outbox al terme 7", "la configuració vigent és la versió 12" o, en el cas general de la replicació per consens, "l'entrada número 4.312 del log és reservar formatge-curat per a P-2026-000123".

Per què és difícil: FLP i la sortida pràctica

A 01-02 vam presentar el resultat de Fischer, Lynch i Paterson (1985): en un sistema asíncron (sense cotes en la latència dels missatges ni en la velocitat dels processos), cap algorisme determinista de consens no garanteix terminació si un sol procés pot fallar per aturada. La intuïció: si un procés no respon, els altres no poden distingir si ha mort o si el seu missatge està trigant; si esperen, poden esperar per sempre; si decideixen sense ell, pot resultar que era viu i a punt de decidir una altra cosa. Sempre existeix un adversari (una planificació de retards) que manté l'algorisme indecís.

FLP no diu que el consens sigui impossible a la pràctica; diu que no es pot garantir en el pitjor cas asíncron. Les sortides pràctiques són les que vam anticipar a 01-02:

Sincronia parcial: assumir que la xarxa es comporta bé "la major part del temps" i fer servir timeouts. Paxos i Raft garanteixen seguretat sempre, en qualsevol xarxa, i terminació només quan la xarxa és en un període estable. És exactament la divisió seguretat/vivacitat de l'apartat 1.
Aleatorietat: els timeouts aleatoris de Raft i alguns protocols probabilistes trenquen la simetria que l'adversari de FLP necessita.
Detectors de fallades: sospitar d'un node després d'un timeout, acceptant equivocar-se (un node lent tractat com a mort continua sent segur, només costa progrés).

I una regla que convé gravar-se: el consens necessita majoria. Amb N nodes, es toleren f fallades d'aturada si N ≥ 2f + 1: tres nodes en toleren una, cinc en toleren dues. La raó és que dues majories qualssevol de N s'intersequen com a mínim en un node, i aquest node comú és el que impedeix que dos grups decideixin valors diferents. És també per això que un sistema CP amb dos nodes, com el de la simulació de 03-02, no pot tolerar cap partició.

Per a què es fa servir el consens

El consens pur (acordar un valor) rarament es fa servir directament. Es fa servir com a primitiva per construir:

Ús	Què es decideix	Exemple a Quilòmetre Zero
Elecció de líder	Qui mana durant un període	Una sola instància del relay outbox de `comandes` publica a `comandes.esdeveniments`; un únic planificador assigna repartidors
Màquina d'estats replicada (log replicat)	L'ordre de totes les operacions	Base d'un magatzem CP: totes les rèpliques apliquen el mateix log en el mateix ordre i per tant tenen el mateix estat (així funcionen etcd, CockroachDB, Kafka amb KRaft)
Configuració distribuïda	La versió vigent de la configuració	Llindar d'estoc per passar a mode CP (03-02), llista de mercats actius, feature flags de la "Setmana del Formatge Artesà"
Locks distribuïts i membresia	Qui té el lock; quins nodes són al grup	Evitar que dos processos d'`analitica` reconstrueixin el mateix informe; saber quines rèpliques d'`inventari` són vives
Commit atòmic	Si una transacció es confirma o s'avorta	Variant de consens amb requisits diferents, a 03-05

La idea de la màquina d'estats replicada (Lamport, 1978; Schneider, 1990) mereix una frase més: si diversos nodes parteixen del mateix estat i apliquen les mateixes operacions deterministes en el mateix ordre, acaben en el mateix estat. El consens es fa servir per acordar l'ordre (entrada 1, entrada 2, entrada 3...), i a partir d'aquí la replicació és trivial. És el patró darrere de Multi-Paxos i de Raft, i la raó per la qual tots dos parlen de "log".

Paxos: rols, fases i números de proposta

Leslie Lamport va publicar Paxos el 1998 (després d'un rebuig inicial de l'article, escrit com una paràbola sobre un parlament grec, el 1989). Resol el consens d'un sol valor (single-decree Paxos) amb tres rols, que a la pràctica acostumen a coexistir a cada node:

Proposer: proposa un valor. N'hi pot haver diversos alhora, i aquí hi ha la dificultat.
Acceptor: vota. Recorda dues coses en emmagatzematge estable: el número de proposta més alt que ha promès no ignorar, i l'última proposta que ha acceptat (número i valor). Un valor queda elegit quan una majoria d'acceptors l'ha acceptat amb el mateix número de proposta.
Learner: s'assabenta del valor elegit (preguntant als acceptors o rebent notificacions).

Cada proposta porta un número de proposta únic i totalment ordenat; el truc habitual és n = ronda * 10 + id_proposer, de manera que dos proposers mai no generen el mateix número. El protocol té dues fases:

sequenceDiagram
    participant P as Proposer (relay-1)
    participant A1 as Acceptor a1
    participant A2 as Acceptor a2
    participant A3 as Acceptor a3
    Note over P,A3: Fase 1: prepare / promise
    P->>A1: prepare(n=1)
    P->>A2: prepare(n=1)
    P->>A3: prepare(n=1)
    A1-->>P: promise(1, sense acceptat)
    A2-->>P: promise(1, sense acceptat)
    A3-->>P: promise(1, sense acceptat)
    Note over P: Majoria de promeses i ningú no havia acceptat res: proposo el meu valor
    Note over P,A3: Fase 2: accept / accepted
    P->>A1: accept(n=1, "relay-1")
    P->>A2: accept(n=1, "relay-1")
    P->>A3: accept(n=1, "relay-1")
    A1-->>P: accepted(1)
    A2-->>P: accepted(1)
    A3-->>P: accepted(1)
    Note over P,A3: Majoria d'accepted amb n=1: el valor "relay-1" queda ELEGIT

Fase 1 (prepare/promise). El proposer tria un número n i envia prepare(n) als acceptors. Un acceptor que rep prepare(n) amb n més gran que qualsevol número que hagi promès respon promise(n, acceptat), comprometent-se a no acceptar cap proposta amb número menor que n, i incloent-hi la proposta que hagués acceptat abans, si n'hi ha. Si n és menor o igual que la seva promesa, ignora o rebutja.

Fase 2 (accept/accepted). Si el proposer rep promeses d'una majoria, tria el valor a proposar amb aquesta regla, que és el cor de Paxos: si alguna promesa incloïa una proposta ja acceptada, ha de proposar el valor de l'acceptada amb número més alt; només si cap no incloïa res, pot proposar el seu propi valor. Envia accept(n, valor); cada acceptor l'accepta si no ha promès un número més gran entretant, i respon accepted. Amb una majoria d'accepted, el valor està elegit.

Per què funciona. Suposa que el valor v ha estat elegit amb número n (una majoria el va acceptar). Qualsevol proposta posterior amb número m > n ha d'obtenir promeses d'una majoria, que necessàriament s'interseca amb la majoria que va acceptar v; com a mínim un acceptor d'aquesta intersecció informarà de (n, v) a la seva promesa, i la regla de la fase 2 obligarà el nou proposer a proposar v de nou. Per inducció, un cop elegit un valor, totes les propostes futures porten aquest mateix valor: acord garantit, amb qualsevol nombre de proposers i qualsevol ordre de missatges. La validesa és immediata (només es proposen valors proposats) i la terminació... no està garantida (FLP): dos proposers es poden tornar a la fase 1 amb números creixents, invalidant-se mútuament les promeses per sempre (livelock). La solució pràctica és triar un proposer distingit amb timeouts, és a dir, un líder.

Per què és difícil d'implementar. Paxos d'un sol valor és elegant, però un sistema real necessita decidir una seqüència de valors (el log de la màquina d'estats). Multi-Paxos fa això: executa una instància de Paxos per entrada del log, i optimitza triant un líder estable que fa la fase 1 una sola vegada per a totes les entrades futures i després només executa la fase 2 per entrada. Però l'article de Lamport no especifica com triar el líder, com gestionar canvis de membresia, com compactar el log ni com recuperar acceptors que s'han quedat enrere. Cada implementació (Chubby de Google, Spanner, Cassandra per a les seves transaccions lleugeres) omple aquests buits a la seva manera, i els autors de Chubby van escriure que "hi ha buits significatius entre la descripció de l'algorisme i les necessitats d'un sistema real". Aquesta frustració és l'origen de Raft.

Simulació: Paxos amb dos proposers en conflicte

Implementarem Paxos d'un sol valor amb tres acceptors i dos proposers, relay-1 i relay-2, cadascun dels quals vol ser elegit líder del relay outbox. La xarxa permet descartar missatges concrets per reproduir el cas interessant: relay-1 aconsegueix que un acceptor accepti el seu valor, perd la resta de missatges, i relay-2 arriba després amb un número més gran.

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


@dataclass
class Acceptor:
    nom: str
    promes: int | None = None                    # número més alt promès
    acceptat: tuple[int, str] | None = None      # (número, valor) de l'última proposta acceptada

    def prepare(self, n: int) -> tuple[str, object]:
        if self.promes is None or n > self.promes:
            self.promes = n
            return ("promise", self.acceptat)       # inclou el que ja hagués acceptat
        return ("nack", self.promes)

    def accept(self, n: int, valor: str) -> tuple[str, object]:
        if self.promes is None or n >= self.promes:
            self.promes = n
            self.acceptat = (n, valor)
            return ("accepted", n)
        return ("nack", self.promes)


class Xarxa:
    """Descarta els missatges llistats a `perduts`: (proposer, acceptor, fase)."""
    def __init__(self) -> None:
        self.perduts: set[tuple[str, str, str]] = set()

    def lliura(self, proposer: str, acceptor: str, fase: str) -> bool:
        return (proposer, acceptor, fase) not in self.perduts


@dataclass
class Proposer:
    nom: str
    id: int
    acceptors: list[Acceptor]
    xarxa: Xarxa
    ronda: int = 0
    traca: list[str] = field(default_factory=list)

    def _log(self, msg: str) -> None:
        print(f"  [{self.nom}] {msg}")

    def proposar(self, valor: str) -> str | None:
        self.ronda += 1
        n = self.ronda * 10 + self.id                        # número únic i creixent
        majoria = len(self.acceptors) // 2 + 1
        self._log(f"fase 1: prepare(n={n}) volent proposar '{valor}'")

        promeses: list[tuple[int, str] | None] = []
        for a in self.acceptors:
            if not self.xarxa.lliura(self.nom, a.nom, "prepare"):
                self._log(f"    prepare a {a.nom} PERDUT"); continue
            tipus, dada = a.prepare(n)
            self._log(f"    {a.nom} -> {tipus} {dada if dada else ''}")
            if tipus == "promise":
                promeses.append(dada)
        if len(promeses) < majoria:
            self._log(f"fase 1 fallida: {len(promeses)} promeses < majoria {majoria}")
            return None

        # Regla clau: si algú ja ha acceptat alguna cosa, adoptar el valor del número més alt
        ja_acceptades = [p for p in promeses if p is not None]
        if ja_acceptades:
            n_prev, valor_prev = max(ja_acceptades)
            if valor_prev != valor:
                self._log(f"fase 2: un acceptor ja va acceptar ({n_prev}, '{valor_prev}'): ADOPTO '{valor_prev}' i abandono '{valor}'")
            valor = valor_prev
        self._log(f"fase 2: accept(n={n}, '{valor}')")

        acceptats = 0
        for a in self.acceptors:
            if not self.xarxa.lliura(self.nom, a.nom, "accept"):
                self._log(f"    accept a {a.nom} PERDUT"); continue
            tipus, dada = a.accept(n, valor)
            self._log(f"    {a.nom} -> {tipus} {dada}")
            acceptats += tipus == "accepted"
        if acceptats >= majoria:
            self._log(f"ELEGIT '{valor}' amb n={n} ({acceptats} de {len(self.acceptors)})")
            return valor
        self._log(f"fase 2 fallida: {acceptats} acceptats < majoria {majoria}")
        return None


if __name__ == "__main__":
    xarxa = Xarxa()
    acceptors = [Acceptor("a1"), Acceptor("a2"), Acceptor("a3")]
    relay1 = Proposer("relay-1", id=1, acceptors=acceptors, xarxa=xarxa)
    relay2 = Proposer("relay-2", id=2, acceptors=acceptors, xarxa=xarxa)

    print("Ronda A: relay-1 proposa, però els seus accept a a2 i a3 es perden")
    xarxa.perduts = {("relay-1", "a2", "accept"), ("relay-1", "a3", "accept")}
    print("  resultat:", relay1.proposar("relay-1"))

    print("\nRonda B: relay-2 proposa amb un número més gran; la xarxa ja funciona")
    xarxa.perduts = set()
    print("  resultat:", relay2.proposar("relay-2"))

    print("\nRonda C: relay-1 reintenta amb un número encara més gran")
    print("  resultat:", relay1.proposar("relay-1"))

    print("\nEstat final dels acceptors:")
    for a in acceptors:
        print(f"  {a.nom}: promes={a.promes}, acceptat={a.acceptat}")

Sortida:

Ronda A: relay-1 proposa, però els seus accept a a2 i a3 es perden
  [relay-1] fase 1: prepare(n=11) volent proposar 'relay-1'
  [relay-1]    a1 -> promise
  [relay-1]    a2 -> promise
  [relay-1]    a3 -> promise
  [relay-1] fase 2: accept(n=11, 'relay-1')
  [relay-1]    a1 -> accepted 11
  [relay-1]    accept a a2 PERDUT
  [relay-1]    accept a a3 PERDUT
  [relay-1] fase 2 fallida: 1 acceptats < majoria 2
  resultat: None

Ronda B: relay-2 proposa amb un número més gran; la xarxa ja funciona
  [relay-2] fase 1: prepare(n=12) volent proposar 'relay-2'
  [relay-2]    a1 -> promise (11, 'relay-1')
  [relay-2]    a2 -> promise
  [relay-2]    a3 -> promise
  [relay-2] fase 2: un acceptor ja va acceptar (11, 'relay-1'): ADOPTO 'relay-1' i abandono 'relay-2'
  [relay-2] fase 2: accept(n=12, 'relay-1')
  [relay-2]    a1 -> accepted 12
  [relay-2]    a2 -> accepted 12
  [relay-2]    a3 -> accepted 12
  [relay-2] ELEGIT 'relay-1' amb n=12 (3 de 3)
  resultat: relay-1

Ronda C: relay-1 reintenta amb un número encara més gran
  [relay-1] fase 1: prepare(n=21) volent proposar 'relay-1'
  [relay-1]    a1 -> promise (12, 'relay-1')
  [relay-1]    a2 -> promise (12, 'relay-1')
  [relay-1]    a3 -> promise (12, 'relay-1')
  [relay-1] fase 2: accept(n=21, 'relay-1')
  [relay-1]    a1 -> accepted 21
  [relay-1]    a2 -> accepted 21
  [relay-1]    a3 -> accepted 21
  [relay-1] ELEGIT 'relay-1' amb n=21 (3 de 3)
  resultat: relay-1

Estat final dels acceptors:
  a1: promes=21, acceptat=(21, 'relay-1')
  a2: promes=21, acceptat=(21, 'relay-1')
  a3: promes=21, acceptat=(21, 'relay-1')

El que ensenya l'execució:

A la ronda A, relay-1 obté les tres promeses però només a1 accepta: el valor no ha estat elegit (no hi ha majoria). Tanmateix, a1 recorda (11, 'relay-1').
A la ronda B, relay-2 vol proposar-se a si mateix, però la promesa d'a1 l'informa que ja hi ha una proposta acceptada. La regla de la fase 2 l'obliga a abandonar el seu valor i adoptar relay-1, encara que relay-1 mai no va arribar a ser elegit. És un comportament conservador: Paxos no pot saber si (11, 'relay-1') va ser acceptat per una majoria de la qual només en veu un membre, així que assumeix que podria haver-ho estat. El resultat és que relay-2 fa elegir relay-1.
A la ronda C, relay-1 reintenta i, naturalment, confirma el mateix valor. Acord preservat a les tres rondes, amb missatges perduts i proposers competint. Observa que els números de proposta (11, 12, 21) mai no col·lideixen gràcies a ronda * 10 + id.

Prova de fer que la ronda A perdi també l'accept a a1: aleshores cap promesa de la ronda B no inclourà res, i relay-2 serà elegit. I prova d'alternar perduts perquè cada proposer invalidi les promeses de l'altre a la fase 1: veuràs el livelock que motiva tenir un líder.

Raft: termes, elecció de líder i log replicat

Diego Ongaro i John Ousterhout van publicar Raft el 2014 amb un objectiu declarat: ser comprensible, amb la mateixa tolerància a fallades i rendiment que Multi-Paxos. La seva estratègia va ser descompondre el problema en tres subproblemes (elecció de líder, replicació del log i seguretat) i reduir el nombre d'estats possibles. Avui és l'algorisme d'etcd, Consul, CockroachDB, TiKV, Kafka (KRaft) i RabbitMQ (quorum queues), entre d'altres.

Termes i estats

El temps es divideix en termes (terms), numerats de manera creixent. Cada terme comença amb una elecció; si l'elecció té èxit, un únic líder governa la resta del terme. Els termes actuen com a rellotge lògic (01-05): cada missatge porta el terme de l'emissor, i un node que veu un terme més gran que el seu l'adopta immediatament i passa a seguidor. Cada node és en un de tres estats:

stateDiagram-v2
    [*] --> Seguidor
    Seguidor --> Candidat: timeout d'elecció sense batecs del líder
    Candidat --> Lider: vots de la majoria
    Candidat --> Seguidor: descobreix un líder o un terme més gran
    Candidat --> Candidat: timeout sense majoria (nou terme)
    Lider --> Seguidor: descobreix un terme més gran

Elecció de líder

Tot node comença com a seguidor i espera batecs (heartbeats) del líder. Cada seguidor té un timeout d'elecció aleatori (típicament entre 150 i 300 ms).
Si el timeout expira sense haver rebut batecs, el seguidor es converteix en candidat: incrementa el seu terme, es vota a si mateix i envia RequestVote als altres.
Cada node concedeix un sol vot per terme, al primer candidat que l'hi demana i que compleixi la condició de seguretat de més avall. Si el candidat rep vots de la majoria, és líder i comença a enviar batecs immediatament, cosa que fa que els altres candidats es rendeixin.
Si dos candidats divideixen els vots (cap amb majoria), tots dos esperen un nou timeout aleatori i ho intenten en un terme nou. L'aleatorietat fa molt improbable que empatin repetidament: a la pràctica, un d'ells expira abans i guanya.

És l'aleatorietat la que resol el livelock de Paxos i esquiva FLP: seguretat sempre, terminació amb probabilitat 1 quan la xarxa s'estabilitza.

Replicació del log

Els clients parlen només amb el líder. Cada operació s'afegeix al log del líder com una entrada (índex, terme, ordre) i s'envia als seguidors amb AppendEntries (el mateix missatge que serveix de batec quan va buit). Quan el líder sap que l'entrada és en una majoria de logs, la marca com a confirmada (committed), l'aplica a la seva màquina d'estats, respon al client i informa els seguidors perquè l'apliquin també. Un seguidor amb el log desalineat (per haver estat caigut) és corregit pel líder, que el fa retrocedir fins a l'últim punt en comú i li reenvia la resta: el log del líder és sempre la veritat.

Seguretat

La propietat que Raft demostra és que una entrada confirmada mai no es perd ni se sobreescriu, encara que canviï el líder. Dues regles ho garanteixen:

Restricció d'elecció: un node només vota per un candidat el log del qual estigui com a mínim tan actualitzat com el seu (comparant el terme de l'última entrada i, en cas d'igualtat, l'índex). Com que una entrada confirmada és en una majoria, i el candidat necessita vots d'una majoria, com a mínim un votant té l'entrada i no votarà per un candidat que no la tingui. El líder elegit té per tant totes les entrades confirmades, sense necessitat de la transferència d'estat de Paxos.
Commit només d'entrades del terme actual: un líder només compta rèpliques per confirmar entrades del seu propi terme; les de termes anteriors es confirmen indirectament en confirmar-ne una de posterior. Evita un cas subtil en què una entrada antiga replicada tardanament pogués confirmar-se i després ser sobreescrita.

Raft especifica a més els canvis de configuració (afegir o treure nodes amb configuració conjunta) i la compactació del log mitjançant snapshots, precisament els buits que Paxos deixava oberts.

Simulació: elecció de líder a Raft i caiguda del líder

La simulació següent implementa l'elecció de líder de Raft amb asyncio: tres nodes amb timeouts aleatoris, termes, vots amb restricció de log i batecs. No replica el log (els nodes tenen un log fix per poder mostrar la restricció d'elecció), però permet veure una elecció real, la caiguda del líder i la reelecció, i què passa quan un node amb el log endarrerit intenta ser líder.

# km0/simulacions/raft_eleccio.py
import asyncio
import random

T0 = None


def ara() -> float:
    return asyncio.get_running_loop().time() - T0


class Xarxa:
    """Lliura missatges amb latència aleatòria; no lliura a nodes caiguts."""
    def __init__(self, nodes: dict, rng: random.Random):
        self.nodes, self.rng = nodes, rng

    async def cridar(self, desti: str, metode: str, *args):
        await asyncio.sleep(self.rng.uniform(0.002, 0.010))     # latència de xarxa
        node = self.nodes[desti]
        if not node.viu:
            await asyncio.sleep(0.05)                          # timeout de RPC
            return None
        return getattr(node, metode)(*args)


class NodeRaft:
    def __init__(self, id: str, ultim_index: int, ultim_terme: int, rng: random.Random,
                 primer_termini: float | None = None):
        self.id, self.rng = id, rng
        self.primer_termini = primer_termini             # per forçar qui expira primer a la demo
        self.estat = "seguidor"
        self.terme = 0
        self.votat_per: str | None = None
        self.ultim_index, self.ultim_terme = ultim_index, ultim_terme   # log fix
        self.viu = True
        self.termini = 0.0
        self.xarxa: Xarxa | None = None

    # --- RPC que reben els altres nodes ---------------------------------------
    def sollicitar_vot(self, terme: int, candidat: str, ult_idx: int, ult_term: int):
        if terme > self.terme:
            self.terme, self.estat, self.votat_per = terme, "seguidor", None
        log_al_dia = (ult_term, ult_idx) >= (self.ultim_terme, self.ultim_index)
        concedir = (terme == self.terme and self.votat_per in (None, candidat) and log_al_dia)
        if concedir:
            self.votat_per = candidat
            self._reiniciar_termini()
        elif terme == self.terme and not log_al_dia:
            print(f"{ara():6.3f}s  {self.id}: DENEGO el vot a {candidat} (el seu log ({ult_term},{ult_idx}) "
                  f"va per darrere del meu ({self.ultim_terme},{self.ultim_index}))")
        return (self.terme, concedir)

    def rebre_batec(self, terme: int, lider: str):
        if terme >= self.terme:
            if self.estat != "seguidor" or terme > self.terme:
                print(f"{ara():6.3f}s  {self.id}: reconec {lider} com a líder del terme {terme}")
            self.terme, self.estat, self.votat_per = terme, "seguidor", None
            self._reiniciar_termini()
        return self.terme

    # --- bucle principal ------------------------------------------------------
    def _reiniciar_termini(self) -> None:
        self.termini = ara() + self.rng.uniform(0.150, 0.300)

    async def executar(self, parells: list[str]) -> None:
        self._reiniciar_termini()
        if self.primer_termini is not None:
            self.termini = ara() + self.primer_termini
        while True:
            await asyncio.sleep(0.010)
            if not self.viu:
                continue
            if self.estat == "lider":
                await asyncio.gather(*(self.xarxa.cridar(p, "rebre_batec", self.terme, self.id) for p in parells))
                await asyncio.sleep(0.040)                      # batecs cada ~50 ms
            elif ara() > self.termini:
                await self._eleccio(parells)

    async def _eleccio(self, parells: list[str]) -> None:
        self.terme += 1
        self.estat, self.votat_per = "candidat", self.id
        self._reiniciar_termini()
        print(f"{ara():6.3f}s  {self.id}: timeout, em presento al terme {self.terme}")
        respostes = await asyncio.gather(*(self.xarxa.cridar(p, "sollicitar_vot", self.terme, self.id,
                                                             self.ultim_index, self.ultim_terme) for p in parells))
        if self.estat != "candidat":              # algú altre ha guanyat mentre esperava
            return
        vots = 1 + sum(1 for r in respostes if r and r[1] and r[0] == self.terme)
        for r in respostes:
            if r and r[0] > self.terme:
                self.terme, self.estat = r[0], "seguidor"; return
        if vots > (len(parells) + 1) // 2:
            self.estat = "lider"
            print(f"{ara():6.3f}s  {self.id}: LÍDER del terme {self.terme} amb {vots} vots")


async def main() -> None:
    global T0
    T0 = asyncio.get_running_loop().time()
    rng = random.Random(3)
    # node-3 té el log endarrerit (índex 3 davant de 5) i és el primer a expirar (0,12 s):
    # NO ha de poder ser líder per molt que es presenti el primer
    nodes = {"node-1": NodeRaft("node-1", 5, 1, rng), "node-2": NodeRaft("node-2", 5, 1, rng),
             "node-3": NodeRaft("node-3", 3, 1, rng, primer_termini=0.120)}
    xarxa = Xarxa(nodes, rng)
    for n in nodes.values():
        n.xarxa = xarxa
    tasques = [asyncio.create_task(n.executar([p for p in nodes if p != n.id])) for n in nodes.values()]

    await asyncio.sleep(1.0)
    lider = next(n for n in nodes.values() if n.estat == "lider")
    print(f"{ara():6.3f}s  --- {lider.id} CAU ---")
    lider.viu = False
    await asyncio.sleep(1.0)
    print(f"{ara():6.3f}s  --- {lider.id} TORNA (creu que continua al terme {lider.terme}) ---")
    lider.viu = True
    await asyncio.sleep(0.5)
    print("estat final:", {n.id: (n.estat, n.terme) for n in nodes.values()})
    for t in tasques:
        t.cancel()


if __name__ == "__main__":
    asyncio.run(main())

Sortida (els temps poden variar uns mil·lisegons perquè depenen del planificador d'asyncio, però la seqüència de fets és la mateixa a cada execució gràcies a la llavor i al primer_termini de node-3):

 0.122s  node-3: timeout, em presento al terme 1
 0.125s  node-2: DENEGO el vot a node-3 (el seu log (1,3) va per darrere del meu (1,5))
 0.129s  node-1: DENEGO el vot a node-3 (el seu log (1,3) va per darrere del meu (1,5))
 0.194s  node-1: timeout, em presento al terme 2
 0.203s  node-1: LÍDER del terme 2 amb 3 vots
 1.001s  --- node-1 CAU ---
 1.153s  node-3: timeout, em presento al terme 3
 1.163s  node-2: DENEGO el vot a node-3 (el seu log (1,3) va per darrere del meu (1,5))
 1.281s  node-2: timeout, em presento al terme 4
 1.336s  node-2: LÍDER del terme 4 amb 2 vots
 2.001s  --- node-1 TORNA (creu que continua al terme 2) ---
 2.003s  node-1: reconec node-2 com a líder del terme 4
estat final: {'node-1': ('seguidor', 4), 'node-2': ('lider', 4), 'node-3': ('seguidor', 4)}

Què cal observar:

Restricció d'elecció en acció. node-3, amb el log endarrerit, és el primer a esgotar el seu timeout i es presenta al terme 1, però els altres dos li deneguen el vot perquè la seva última entrada (1, 3) és anterior a la d'ells (1, 5). Mai no podrà ser líder mentre estigui endarrerit, cosa que protegeix les entrades confirmades que ell no té. La seva petició ha tingut un efecte, però: els altres han adoptat el terme 1, i quan node-1 expira poc després es presenta al terme 2 i guanya amb els tres vots (node-3 també el vota: el seu log està més al dia que el propi).
Caiguda i reelecció. En caure node-1, els batecs cessen. node-3 torna a ser el primer a expirar (terme 3) i torna a ser denegat per node-2; node-1 no respon perquè està caigut. Uns 130 ms després expira node-2, es presenta al terme 4 i guanya amb dos vots (el seu i el de node-3): majoria de 3. El sistema ha estat sense líder uns 335 ms. Aquest és el cost de disponibilitat d'un sistema CP durant una fallada: acotat i petit, no indefinit. Observa que el terme ha saltat de 2 a 4: els termes consumits per eleccions fallides no es reutilitzen.
El líder antic torna. node-1 reviu creient-se líder del terme 2, però el primer batec de node-2 amb terme 4 el fa retrocedir a seguidor. Els termes com a rellotge lògic eviten que hi hagi dos líders actuant: un missatge amb terme antic és ignorat per tothom. (En un sistema real, node-1 podria haver intentat enviar un AppendEntries de terme 2 abans de rebre el batec; els seguidors el rebutjarien per terme obsolet.)

Si treus el primer_termini de node-3, l'ordre en què expiren els nodes depèn dels timeouts aleatoris i la traça canvia a cada execució; en moltes d'elles node-3 ni tan sols arriba a presentar-se. És el que passa en producció: la restricció d'elecció només es manifesta quan el node endarrerit expira abans que els altres.

Consens bizantí: PBFT en una pàgina

Tot l'anterior assumeix el model de fallada crash de 01-02: un node que falla, calla. Si un node pot mentir (fallada bizantina: un bug que envia missatges incoherents, un disc que corromp el log, un participant maliciós), Paxos i Raft no serveixen: un acceptor que promet a dos proposers alhora o un líder que envia logs diferents a cada seguidor trenquen l'acord.

El consens bizantí resol aquest cas amb un cost més gran. El resultat clàssic (Lamport, Shostak i Pease, 1982) és que calen N ≥ 3f + 1 nodes per tolerar f bizantins: 4 nodes per tolerar-ne 1, 7 per tolerar-ne 2. La intuïció: amb f mentiders, una majoria honesta de les respostes que un node rep (N - f, perquè els mentiders poden callar) ha de continuar sent majoria encara que f d'aquestes respostes siguin falses, cosa que exigeix N - 2f > f. PBFT (Castro i Liskov, 1999) va ser el primer algorisme bizantí pràctic: un líder (primary) proposa l'ordre, i les rèpliques intercanvien tres rondes de missatges signats (pre-prepare, prepare, commit) de manera que cadascuna recull 2f + 1 confirmacions de les altres abans d'executar; si el líder es comporta malament, les rèpliques el canvien per votació (view change). El cost és O(N²) missatges per decisió i signatures criptogràfiques a cadascun, davant d'O(N) de Raft.

Quan cal? Quan els nodes pertanyen a parts que no confien entre elles: cadenes de blocs amb permisos (Hyperledger Fabric, Tendermint/Cosmos fan servir variants de PBFT), sistemes de control aeroespacial amb redundància davant de maquinari defectuós, o consorcis. A Quilòmetre Zero tots els nodes són de la mateixa organització i es protegeixen contra bugs amb proves i contra intrusos amb la seguretat del Mòdul 6; una fallada bizantina interna es tracta com un incident, no amb consens bizantí. Raft és més que suficient.

Taula comparativa: Paxos, Raft i PBFT

Aspecte	Paxos (Multi-Paxos)	Raft	PBFT
Model de fallada	Crash (aturada / recuperació)	Crash	Bizantí
Nodes per tolerar f fallades	2f + 1	2f + 1	3f + 1
Líder	Opcional en teoria; distingit a Multi-Paxos	Obligatori; elecció integrada amb timeouts aleatoris	Primary amb canvi de vista
Missatges per decisió (règim estable)	O(N): només fase 2 amb líder estable	O(N): un `AppendEntries`	O(N²), signats
Comprensibilitat	Baixa; buits d'especificació	Alta; especificació completa (membresia, snapshots)	Mitjana-baixa
Qui pot ser líder	Qualsevol (rep l'estat a la fase 1)	Només qui té el log al dia	Rotació determinista
Seguretat garantida	Sempre	Sempre	Sempre (amb f < N/3)
Terminació	Amb sincronia parcial i líder estable	Amb sincronia parcial (aleatorietat)	Amb sincronia parcial
Usat a	Chubby, Spanner, Cassandra (LWT), Neo4j	etcd, Consul, CockroachDB, TiKV, Kafka KRaft, RabbitMQ quorum queues	Hyperledger Fabric, Tendermint, sistemes crítics

Sistemes que l'implementen i el seu ús a Quilòmetre Zero: `etcd` i el relay outbox

Gairebé ningú no implementa Raft o Paxos per a la seva aplicació: es fa servir un sistema de coordinació que l'encapsula i exposa primitives senzilles sobre un magatzem clau-valor linealitzable:

Sistema	Algorisme	Primitives	On es veu
etcd	Raft	Clau-valor amb revisions, leases (TTL), watch, transaccions compare-and-swap	Kubernetes hi desa tot el seu estat
ZooKeeper	ZAB (semblant a Raft, anterior)	Znodes jeràrquics, nodes efímers i seqüencials, watches	Kafka (fins a KRaft), HBase, Hadoop
Consul	Raft	Clau-valor, sessions, descobriment de serveis, health checks	Service mesh HashiCorp

Els tres són PC/EC a la taula de 03-02: cada escriptura passa per consens i el costat minoritari d'una partició rebutja escriptures (i, per defecte, lectures linealitzables). Es despleguen en clústers de 3 o 5 nodes i es fan servir per a dades petites i crítiques: qui és líder, quina configuració és vigent, quins nodes són vius. Mai per a dades d'aplicació (l'estoc, les comandes): són lents per disseny i la seva capacitat és de megabytes, no de terabytes.

El problema de Quilòmetre Zero

A 02-05 vam escriure el relay del patró Outbox: un procés que llegeix de la taula outbox de km0_comandes amb FOR UPDATE SKIP LOCKED i publica a comandes.esdeveniments. Amb una instància funciona. Però comandes es desplega amb tres rèpliques a Kubernetes (01-06), i si les tres executen el relay, encara que SKIP LOCKED eviti que dues agafin la mateixa fila alhora, l'ordre de publicació per comanda deixa d'estar garantit (dos relays publiquen files de la mateixa comanda en paral·lel) i el relay que mor després de publicar i abans de marcar duplica esdeveniments amb més freqüència. Volem una sola instància activa i que, si mor, una altra prengui el relleu en segons. És una elecció de líder, i la farem amb etcd.

Afegim etcd al docker-compose.yml:

  etcd:
    image: quay.io/coreos/etcd:v3.5.15
    command: >
      etcd --name etcd0
           --listen-client-urls http://0.0.0.0:2379
           --advertise-client-urls http://etcd:2379
    ports:
      - "2379:2379"

(Un sol node per a desenvolupament; en producció serien 3 o 5, perquè un etcd d'un node és un punt únic de fallada que no tolera res.) El mecanisme es recolza en dues primitives d'etcd:

Lease: un contracte amb TTL. Les claus associades a un lease desapareixen automàticament si el client deixa de renovar-lo (keep-alive). Si el relay líder mor, la seva clau s'esborra sola en expirar el TTL.
Transacció compare-and-swap: "si la clau no existeix, crea-la amb la meva identitat i aquest lease". Com que etcd és linealitzable, només una de diverses instàncies concurrents veurà "no existeix" i guanyarà.

# km0/serveis/comandes/relay_lider.py
import os
import socket
import time

import etcd3                                   # pip install etcd3
from etcd3.events import DeleteEvent

CLAU = "/km0/lider/relay-outbox"
TTL_SEGONS = 10
JO = f"{socket.gethostname()}-{os.getpid()}"

client = etcd3.client(host=os.environ.get("ETCD_HOST", "etcd"), port=2379)


def intentar_ser_lider(lease) -> bool:
    """Crea la clau només si no existeix (compare-and-swap linealitzable)."""
    reeixit, _ = client.transaction(
        compare=[client.transactions.version(CLAU) == 0],         # version 0 = la clau no existeix
        success=[client.transactions.put(CLAU, JO, lease=lease)],
        failure=[],
    )
    return reeixit


def esperar_que_quedi_lliure() -> None:
    valor, _ = client.get(CLAU)
    print(f"[{JO}] líder actual: {valor.decode() if valor else '(cap)'}; espero")
    esdeveniments, cancellar = client.watch(CLAU)
    for esdeveniment in esdeveniments:
        if isinstance(esdeveniment, DeleteEvent):   # el lease del líder ha expirat o l'ha revocat
            break
    cancellar()


def publicar_pendents() -> int:
    """El relay de 02-05: llegeix outbox FOR UPDATE SKIP LOCKED, publica a Kafka, marca publicat_en."""
    ...
    return 0


def bucle() -> None:
    while True:
        lease = client.lease(TTL_SEGONS)
        if not intentar_ser_lider(lease):
            lease.revoke()
            esperar_que_quedi_lliure()
            continue
        print(f"[{JO}] SOC LÍDER del relay outbox")
        try:
            while True:
                publicar_pendents()
                resposta = lease.refresh()              # keep-alive: si falla, hem perdut el lideratge
                if not resposta or resposta[0].TTL <= 0:
                    raise RuntimeError("no he pogut renovar el lease")
                time.sleep(1)
        except Exception as e:
            print(f"[{JO}] deixo de ser líder: {e}")
        finally:
            try:
                lease.revoke()                          # alliberar com més aviat millor perquè un altre prengui el relleu
            except Exception:
                pass


if __name__ == "__main__":
    bucle()

Com es comporta amb tres rèpliques de comandes:

Les tres arrenquen i executen intentar_ser_lider. etcd, via Raft, processa les tres transaccions en un ordre total; la primera veu version == 0 i crea la clau; les altres dues veuen que ja existeix i passen a esperar_que_quedi_lliure, bloquejades en un watch (sense sondeig).
La líder publica cada segon i renova el lease. Si es torna a desplegar o mor netament, revoke esborra la clau a l'instant; si mor de cop (kill -9, node caigut), la clau desapareix quan el lease expira, com a màxim 10 segons després.
El watch de les altres dues rep el DeleteEvent, i totes dues tornen a intentar intentar_ser_lider; exactament una guanya. El relay ha estat aturat entre 0 i 10 segons: els esdeveniments s'acumulen a outbox (no es perd res) i es publiquen en ordre en reprendre.

Hi ha una subtilesa que convé entendre bé. Si la líder queda aïllada d'etcd (partició) però continua viva i connectada a PostgreSQL i Kafka, el seu lease expirarà sense que el pugui renovar, una altra instància prendrà el lideratge, i durant uns segons hi podria haver dos relays publicant: la nova i l'antiga, que encara no sap que ha perdut. El refresh que falla i atura el bucle acota aquesta finestra, però no l'elimina (entre l'últim refresh amb èxit i l'expiració hi ha fins a 10 segons). Aquest és el problema clàssic dels locks distribuïts i té dos remeis: acceptar la finestra perquè els consumidors són idempotents (el nostre cas: 02-05 ja ens protegeix de duplicats) o fer servir un token de tancat (fencing token): la mod_revision que etcd assigna a la clau del líder, monòtonament creixent, s'inclou a cada UPDATE outbox ... WHERE publicat_en IS NULL AND lider_revisio <= %s, de manera que la base de dades rebutgi les escriptures d'un líder antic. Els locks distribuïts i el fencing reapareixeran a 07-03 en parlar de failover.

Errors Comuns i Consells

Implementar el consens a mà. Paxos i Raft semblen curts sobre el paper i són traïdors en codi (els mateixos autors de Raft mantenen una llista d'errors comuns en implementacions publicades). Fes servir etcd, ZooKeeper o Consul, o una biblioteca madura, i dedica l'esforç a l'aplicació.
Clúster de coordinació amb un nombre parell de nodes. Quatre nodes toleren una fallada, igual que tres, però amb més cost i més probabilitat que una fallada passi. Fes servir 3 o 5.
Fer servir el magatzem de coordinació com a base de dades. etcd té un límit pràctic d'uns pocs GB i cada escriptura passa per Raft i per fsync a la majoria. Desar-hi posicions de furgonetes el col·lapsaria en minuts.
Un lock distribuït sense token de tancat en operacions no idempotents. Si l'efecte protegit pel lock no tolera un executor antic, l'expiració del lease no n'hi ha prou; cal tancar al recurs (la base de dades, el magatzem) amb la revisió del lease.
Timeouts d'elecció massa curts. Si el timeout d'elecció és de l'ordre de la latència de xarxa, qualsevol congestió provoca eleccions contínues (el líder no arriba a enviar batecs a temps). Raft recomana que el temps de batec sigui un ordre de magnitud menor que el timeout d'elecció, i aquest un ordre de magnitud menor que el temps mitjà entre fallades.
Confondre "majoria dels configurats" amb "majoria dels vius". La majoria és sempre sobre el nombre total de nodes del clúster, no sobre els que responen. Un clúster de 5 amb 3 caiguts no pot elegir líder amb "2 de 2 vius": no hi ha majoria, i això és correcte (hi podria haver altres 3 vius a l'altre costat d'una partició elegint el contrari).
Consell: en depurar un sistema basat en Raft, mira els termes. Un terme que creix ràpidament vol dir eleccions contínues: xarxa inestable, timeouts mal ajustats o un node amb la CPU sobrecarregada.
Consell: documenta quines decisions de Quilòmetre Zero passen per consens (lideratge de relays i planificadors, configuració) i quines no (tota la dada de negoci), i per què. És la llista que un nou membre de l'equip necessita abans de tocar etcd.

Exercicis

Exercici 1: Paxos amb missatges perduts a la fase 1

Amb la simulació de l'apartat 5, configura la xarxa perquè a la ronda A es perdin els accept de relay-1 a a1 i a3 (només a2 accepta), i a la ronda B es perdi el prepare de relay-2 precisament a a2. Quin valor proposa relay-2 a la fase 2 i quin valor acaba elegit? Es viola l'acord? Executa la ronda C i explica l'estat final.

Exercici 2: Dividir vots a Raft

Modifica la simulació de l'apartat 7 perquè els tres nodes tinguin el mateix log (índex 5) i perquè el rang de timeouts sigui molt estret, uniform(0.150, 0.151). Executa-la diverses vegades i descriu què passa als primers termes. Es viola alguna vegada la seguretat (dos líders al mateix terme)? Què es viola? Torna al rang original i compara.

Exercici 3: Dissenyar l'ús d'etcd

Quilòmetre Zero necessita que el servei repartiment executi un únic planificador que assigni comandes a repartidors cada 30 segons, i que a més tots els nodes de repartiment coneguin la llista de mercats actius (Girona, Lleida, Tarragona, València) que un administrador pot canviar. Dissenya les claus d'etcd, indica quines primitives faries servir per a cada necessitat (lease, transacció, watch) i explica què passa pas a pas si el node planificador queda aïllat d'etcd durant 25 segons amb un lease de 10. Necessites token de tancat? Justifica-ho.

Solucions

Solució 1:

Ronda A: relay-1 obté tres promeses (n=11), però només a2 accepta (11, 'relay-1'): no hi ha majoria, no hi ha valor elegit. Ronda B: relay-2 envia prepare(12) a a1 i a3 únicament (el d'a2 es perd); tots dos responen promise sense proposta acceptada, cosa que és majoria (2 de 3). Com que cap promesa no inclou res, relay-2 proposa el seu propi valor 'relay-2'. A la fase 2 l'accepten els tres: a2 també, perquè mai no va prometre res més gran que 11 i un accept(12) supera aquesta promesa (un acceptor no necessita haver rebut el prepare per acceptar; només necessita no haver promès un número més gran). 'relay-2' queda elegit i l'antiga (11, 'relay-1') d'a2 queda sobreescrita: mai no va formar part d'una majoria, així que no importava. Ronda C: relay-1 fa prepare(21) als tres, els tres informen de (12, 'relay-2'), i relay-1 adopta 'relay-2' i el confirma amb n=21. Estat final: tots amb (21, 'relay-2'). L'acord es conserva: el valor elegit a B és el que es confirma a C. És el cas simètric de l'apartat 5: allà la proposta parcial de relay-1 va "sobreviure" perquè l'únic acceptor que la tenia era a la majoria de promeses de relay-2; aquí no hi era i es va descartar. Tots dos desenllaços són correctes, perquè en cap dels dos casos el valor parcial havia estat elegit.

Solució 2:

Amb timeouts gairebé iguals, els tres nodes esgoten el termini pràcticament alhora i es presenten al mateix terme; cadascun es vota a si mateix i, com que només hi ha un vot per terme, cap no arriba a dos vots: vots dividits. Tots reinicien el termini (de nou gairebé igual) i repeteixen al terme següent, i així diverses vegades; els termes creixen ràpidament sense líder. En algun moment les petites diferències de latència (l'uniform(0.002, 0.010) de la xarxa) fan que un candidat demani el vot abans que un altre s'hagi presentat, i guanya. Mai no hi ha dos líders al mateix terme (la seguretat es manté: un vot per terme i majoria), però es viola temporalment la vivacitat: el sistema triga molt a decidir. Amb el rang original (150-300 ms), la probabilitat que dos nodes expirin a la mateixa finestra de latència és petita i l'elecció acostuma a resoldre's al primer o segon terme. És la demostració empírica de per què Raft fa servir timeouts aleatoris i de com l'aleatorietat esquiva FLP a la pràctica.

Solució 3:

Claus: /km0/lider/planificador-repartiment (valor: identitat de la instància, amb lease de 10 s) i /km0/config/mercats-actius (valor JSON ["girona","lleida","tarragona","valencia"], sense lease: és configuració persistent).

Primitives: per al planificador, el mateix esquema de l'apartat 10: lease + transacció version == 0 + watch de l'esborrat; el líder executa l'assignació cada 30 s i renova el lease cada 3 s. Per als mercats, cada node de repartiment fa un get en arrencar i un watch permanent sobre la clau; l'administrador escriu amb un put normal (o amb una transacció condicionada a mod_revision per evitar trepitjar canvis concurrents); el watch lliura el nou valor a tots els nodes en mil·lisegons, sense sondeig.

Aïllament de 25 s: t=0, última renovació amb èxit. t≈3, el refresh falla; el bucle del líder ha d'aturar la planificació immediatament (no continuar "per si de cas"). t=10, el lease expira a etcd, la clau s'esborra, les altres instàncies reben el DeleteEvent i una guanya. t=25, l'antic líder recupera la connexió, intenta renovar un lease que ja no existeix, passa a esperar_que_quedi_lliure i es queda com a seguidor. Finestra perillosa: entre t=0 i t≈3 l'antic líder encara es creu líder legítimament, però com que no hi ha nou líder fins a t=10, no hi ha dos planificadors alhora sempre que l'antic s'aturi en fallar el refresh. Si l'antic no comprovés el refresh (o si una assignació ja en curs triga més que el TTL restant), sí que podria solapar-se amb el nou.

Token de tancat: l'assignació d'una comanda a un repartidor no és idempotent per naturalesa (dos planificadors podrien assignar la mateixa comanda a furgoneta-3 i a una altra furgoneta). És prudent incloure la mod_revision de la clau del líder a l'escriptura de l'assignació (UPDATE comandes_repartiment SET repartidor = %s, lider_revisio = %s WHERE id = %s AND (lider_revisio IS NULL OR lider_revisio <= %s)), de manera que una assignació d'un líder antic sigui rebutjada per la base de dades. Alternativament, fer l'assignació idempotent per comanda (una sola fila d'assignació per comanda amb INSERT ... ON CONFLICT DO NOTHING, com a 02-05) elimina la necessitat del token per a aquest cas concret, encara que no evitaria que dos planificadors competissin per assignar al mateix repartidor més de les seves 8 comandes.

Conclusió

El consens és el problema que diversos nodes decideixin un únic valor complint acord, validesa i terminació, i aquesta lliçó l'ha resolt als tres nivells anunciats. FLP ens va recordar que en un sistema asíncron no es pot garantir la terminació, i vam veure que la resposta de la indústria és separar seguretat (sempre) de vivacitat (quan la xarxa es comporta): amb majories de 2f + 1 nodes, timeouts i aleatorietat. Paxos resol el consens d'un valor amb proposers, acceptors i learners en dues fases, i la seva regla central (adoptar el valor ja acceptat amb número més alt) és el que va fer que relay-2, a la simulació, acabés elegint relay-1; Multi-Paxos l'estén a un log, deixant buits que cada implementació omple. Raft cobreix aquests buits amb termes, elecció per timeouts aleatoris, replicació de log amb commit per majoria i la restricció que només pot ser líder qui té el log al dia, i la simulació amb asyncio va mostrar node-3 denegat dues vegades pel seu log endarrerit, el líder node-1 caient i node-2 prenent el relleu en uns 335 ms, amb el terme saltant de 2 a 4. El consens bizantí, amb 3f + 1 nodes i PBFT, queda per a quan els participants no confien entre ells, que no és el cas de Quilòmetre Zero. I el primer ús pràctic ha estat concret: etcd amb un lease i una transacció compare-and-swap garanteix que només una instància del relay outbox publica, amb el matís del token de tancat per a la finestra en què un líder aïllat encara no sap que ha deixat de ser-ho.

Ja sabem anomenar les garanties (03-01), triar què sacrificar davant d'una partició (03-02) i fer que un grup de nodes es posi d'acord (03-03). El que encara no hem fet és moure les dades de debò: com arriba una fila inserida al primari de km0_comandes a la seva rèplica, què es perd si el primari mor abans que hi arribi, què passa quan dues regions accepten escriptures alhora, i com funcionen els quòrums de lectura i escriptura amb què Cassandra i DynamoDB ofereixen consistència ajustable sense un líder. És el tema de la lliçó següent, Replicació de Dades, on a més muntarem una rèplica PostgreSQL real al docker-compose.yml de Quilòmetre Zero i la veurem arribar tard.

Algorismes de Consens

Contingut

El problema del consens

Per què és difícil: FLP i la sortida pràctica

Per a què es fa servir el consens

Paxos: rols, fases i números de proposta

Simulació: Paxos amb dos proposers en conflicte

Raft: termes, elecció de líder i log replicat

Termes i estats

Elecció de líder

Replicació del log

Seguretat

Simulació: elecció de líder a Raft i caiguda del líder

Consens bizantí: PBFT en una pàgina

Taula comparativa: Paxos, Raft i PBFT

Sistemes que l'implementen i el seu ús a Quilòmetre Zero: `etcd` i el relay outbox

El problema de Quilòmetre Zero

Errors Comuns i Consells

Exercicis

Exercici 1: Paxos amb missatges perduts a la fase 1

Exercici 2: Dividir vots a Raft

Exercici 3: Dissenyar l'ús d'etcd

Solucions

Conclusió

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

Algorismes de Consens

Contingut

El problema del consens

Per què és difícil: FLP i la sortida pràctica

Per a què es fa servir el consens

Paxos: rols, fases i números de proposta

Simulació: Paxos amb dos proposers en conflicte

Raft: termes, elecció de líder i log replicat

Termes i estats

Elecció de líder

Replicació del log

Seguretat

Simulació: elecció de líder a Raft i caiguda del líder

Consens bizantí: PBFT en una pàgina

Taula comparativa: Paxos, Raft i PBFT

Sistemes que l'implementen i el seu ús a Quilòmetre Zero: etcd i el relay outbox

El problema de Quilòmetre Zero

Errors Comuns i Consells

Exercicis

Exercici 1: Paxos amb missatges perduts a la fase 1

Exercici 2: Dividir vots a Raft

Exercici 3: Dissenyar l'ús d'etcd

Solucions

Conclusió

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

Sistemes que l'implementen i el seu ús a Quilòmetre Zero: `etcd` i el relay outbox