Saltar a contenido

Incarnation Numbers

Para resolver conflictos cuando un nodo es repetidamente Suspected → Alive → Suspected (network blips), SWIM usa incarnation numbers: cada miembro mantiene un counter que él mismo incrementa cuando recibe un Suspect sobre sí mismo. Las preference rules (Alive vs Suspect vs Confirm) se aplican respecto a la incarnation. Es el mismo mecanismo que las destination sequence numbers de AODV. Sin esto, una vieja update Suspect podría "matar" a un nodo que ya rejuveneció.

El problema

"However, a member might be suspected and unsuspected multiple times during its lifetime. These multiple versions of Suspect and Alive messages (all pertaining to the same member Mj) need to be distinguished through unique identifiers."

Sin incarnation numbers, el cluster sufre:

  1. Nodo Mj sufre un GC pause de 8 segundos.
  2. Mi lo marca Suspect, dissemina Suspect Mi:Mj.
  3. Mj se recupera, ve la suspicion, dissemina Alive Mj:Mj.
  4. La update Alive propaga; Mj queda como vivo.
  5. Pero: el Suspect original sigue propagándose en el background. Algún miembro Mk recibe Alive primero y luego Suspect. Sin manera de distinguirlas, Mk re-marca Mj como Suspect.
  6. Loop infinito de Suspect ↔ Alive.

La solución

"These identifiers are provided by using a virtual incarnation number field with each element in the membership lists. Incarnation numbers are global. A member Mj's incarnation number is initialized to 0 when it joins the group, and it can be incremented only by Mj, when it receives information (through the Dissemination Component) about itself being suspected in the current incarnation - Mj then generates an Alive message with its identifier and an incremented incarnation number."

Reglas:

  1. Solo el propio miembro incrementa su incarnation — nadie más puede.
  2. Trigger del incremento: recibir un Suspect sobre sí mismo.
  3. Inicialización: 0 cuando un nodo se une al grupo.
  4. Propagación: incarnation viaja con cada Suspect/Alive/Confirm message.

Preference rules (override semantics)

Verbatim del paper:

Alive {Mj, inc=i} overrides:
  - Suspect {Mj, inc=j}, where j < i
  - Alive   {Mj, inc=j}, where j < i

Suspect {Mj, inc=i} overrides:
  - Suspect {Mj, inc=j}, where j < i
  - Alive   {Mj, inc=j}, where j <= i

Confirm {Mj, inc=i} overrides:
  - Alive   {Mj, inc=j}, any j
  - Suspect {Mj, inc=j}, any j

Observaciones críticas:

  • Alive con incarnation i NO sobrescribe Suspect con incarnation i — solo j < i. Razón: el nodo debe haber incrementado su incarnation en respuesta al Suspect. Si llega un Alive con la misma incarnation, no es respuesta válida.
  • Suspect con incarnation i SÍ sobrescribe Alive con incarnation i (j <= i). Razón: prevenir que un nodo "se rejuveneza solo" sin incrementar incarnation.
  • Confirm ignora incarnation: una vez declarado Confirmed (después de timeout en Suspect), nunca se rejuvenece. El nodo tiene que volver a unirse desde 0.

Analogía con AODV

"The reader familiar with ad-hoc routing protocols such as AODV will notice the similarity between their use of destination sequence numbers and our incarnation number scheme."

AODV (Ad-hoc On-demand Distance Vector routing, Perkins-Royer 1999): cada nodo destino mantiene un sequence number que incrementa antes de cada route discovery. Routes con sequence number mayor son preferidas. Mecanismo idéntico a las incarnation numbers de SWIM, aplicado a routing en vez de membership.

Es una instancia del patrón general "versionado monotónico controlado por el sujeto del state", también visto en: - MVCC (Multi-Version Concurrency Control): timestamp por transacción. - Vector clocks (Lamport): version vector por nodo. - CRDT counter: incremento monotónico per-node. - DNS SOA serial: zone version controlada por el primary.

Ejemplo end-to-end

T=0:  Mj.inc = 5, ALIVE
T=1:  Mj sufre GC pause de 8 segundos
T=2:  Mi → ping(Mj) → timeout
T=3:  Mi → ping-req(Mj) → 2 peers también timeout
T=4:  Mi marca Mj.SUSPECT con inc=5
      Mi dissemina "Suspect {Mj, inc=5}"
T=5:  Gossip propaga "Suspect {Mj, inc=5}"
      Mk recibe → marca Mj.SUSPECT(5)
T=9:  Mj sale del GC pause
T=10: Mj recibe gossip "Suspect {Mj, inc=5}"
      Mj.inc++ → inc=6
      Mj dissemina "Alive {Mj, inc=6}"
T=11: Mi recibe "Alive {Mj, inc=6}"
      6 > 5, override → Mj.ALIVE(6)
T=12: Mk recibe "Alive {Mj, inc=6}"
      6 > 5, override → Mj.ALIVE(6)
T=13: Tarde, Mp recibe "Suspect {Mj, inc=5}" (gossip atrasado)
      5 < 6, NO override (Mp ya tiene Mj.ALIVE(6))
      Mensaje descartado

Sin incarnation numbers, T=13 habría re-marcado a Mj como Suspect, generando un flap.

Implicación: Confirm es definitivo

Un nodo declarado Confirm no puede "rejuvenecerse" incrementando su incarnation:

"Confirm {Mj, inc=i} overrides Alive/Suspect of any j"

Si Mj se recupera después de Confirm, debe rejoin el cluster (como nuevo nodo, incarnation 0). Esto es deliberado: - Los demás miembros ya hicieron rebalance asumiendo que Mj está muerto (ej: re-eligieron leaders Raft, redistribuyeron jobs). - Aceptar la "vuelta" de Mj con su antigua identidad podría romper invariantes (split-brain).

Aplicación al MVP

Si usas Postgres como source of truth

incarnation es trivial:

CREATE TABLE cluster_members (
  node_id UUID PRIMARY KEY,
  incarnation BIGINT NOT NULL DEFAULT 0,
  status TEXT NOT NULL CHECK (status IN ('ALIVE', 'SUSPECT', 'CONFIRMED_DEAD')),
  last_seen TIMESTAMPTZ NOT NULL,
  ...
);

-- Cuando un nodo se ve marcado Suspect:
UPDATE cluster_members
  SET incarnation = incarnation + 1,
      status = 'ALIVE',
      last_seen = now()
  WHERE node_id = $self_id;

La consistencia de Postgres elimina los conflictos: solo el propio nodo puede UPDATE su row (vía RLS o app-level check).

Si implementas gossip custom

Las preference rules son mecánicas — copiar la tabla del paper textualmente. Errores comunes:

  • Olvidar el <= en la regla "Suspect overrides Alive of same inc" → flapping.
  • Permitir que cualquier miembro incremente la incarnation de otros → un attacker puede revivir nodos muertos.
  • No persistir la incarnation localmente → restart pierde el version counter, abre window de override por mensajes viejos.

Cross-refs