Saltar a contenido

Infection Style Dissemination

SWIM elimina la necesidad de multicast/broadcast piggybackeando los updates en los mensajes ping/ack del failure detector. La propagación se modela como un proceso epidémico (Bailey 1975): después de λ · log(N) rounds, una update ha alcanzado N - N^(-(2λ-2)) miembros — coverage casi total con λ constante pequeño. Coverage exponencial, network overhead amortizado a cero, robustez nativa contra packet loss.

El insight central

"The augmented SWIM protocol eliminates the use of an external multicast primitive altogether. It does so by piggybacking the information to be disseminated on the ping, ping-req and ack messages generated by the failure detector protocol."

Consecuencia: la dissemination tiene costo marginal cero en mensajes — los pings ya iban a salir igual.

Solo crece el payload de cada ping (típicamente 15 B → 135 B en el experimento del paper, máximo 6 updates piggybackeados por mensaje).

Modelo matemático (Bailey 1975)

El paper aplica el modelo clásico de epidemias homogéneamente mixtas:

"The relation between the (expected) number of infected members x(t) (initially 1) and time t, under a contact rate of β per time unit, is obtained as: x(t) = N / (1 + (N-1) · e^(-β·N·t))."

Para SWIM con período de protocolo como unidad de tiempo:

  • β = (1/(N-1)) · 2 (cada miembro contacta 2 peers por período: 1 ping outgoing + 1 ack incoming).
  • Después de λ · log(N) rounds: x = N - N^(-(2λ-2)) miembros infectados.
λ Miembros NO infectados después de λ·log(N) rounds Coverage
1 N 0%
2 N^(-2) ≈ 100% para N=100
3 N^(-4) 99.999999% para N=100

"Setting λ to a small constant suffices to disseminate the epidemic reliably - this is true even at small group sizes, as borne out by our experiments in Section 5."

Buffer de updates

Cada miembro mantiene un buffer de updates pendientes con un counter local por elemento:

"The local count specifies the number of times the element has been piggybacked so far by Mi, and is used to choose which elements to piggyback next. Each element is piggybacked at most λ · log(N) times."

Política de selección cuando el buffer no cabe en un ping:

"If the size of this buffer is larger than the maximum number of elements that can be piggybacked on a single ping message (or ack), elements that have been gossiped fewer times are preferred."

Razón: prefer "younger" updates garantiza que toda update infecte al menos algunos miembros antes de que la rate de cambios la sature. Si después la rate baja, la propagación termina por gossip natural.

Dual list (alive vs failed)

"Our implementation of this protocol maintains two lists of group members - a list of members that are not yet declared as failed in the group, and a second list of members that have failed recently."

"Currently, an equal number of buffer of elements is chosen from these two lists for piggybacking, but the scheme could be generalized to adapt to relative variations in process join, leave and failure rates."

Implicación: una muerte y un join concurrentes se propagan a la misma velocidad — el detector no prioriza un evento sobre el otro.

Robustez

"These analyses also show that the infection style of dissemination is resilient to process failures and loss of messages within the network, much like the contagiousness of epidemics."

Por qué resiste packet loss: - Cada update se envía λ · log(N) veces a peers distintos. - Para que la update se pierda totalmente, los λ · log(N) peers receptores tienen que fallar simultáneamente. - Probabilidad de pérdida total ≈ qF^(λ·log(N)) — desvanece exponencialmente.

Por qué resiste process failures: - Los receptores siguen propagando aunque el sender muera. - Una vez que > log(N) miembros tienen la update, la propagación es autosostenida.

Comparación con multicast

Aspecto IP Multicast SWIM Infection-style
Network load adicional N mensajes/update 0 mensajes/update (piggyback)
Reliability Best-effort (drops silenciosos) Exponencial coverage
Latency Single round trip O(log N) rounds
Habilitado en práctica Raramente (admins lo bloquean) Siempre funciona
Configuración network Requerida (multicast routing) Ninguna (UDP unicast)

"Hardware multicast and IP multicast are available on most networks and operating systems, but are rarely enabled, e.g., for administrative reasons."

Esta es la razón pragmática por la que infection-style se impuso: es el único que funciona en redes reales sin coordinación con el ops team.

Resultado experimental del paper

"The median latency of dissemination is always only a few protocol periods, and appears to rise slowly with group size (recall the analysis of Section 4.1 predicted a logarithmic variation of the average infection time with group size)."

Para Camunda con gossipInterval = 250 ms y gossipFanout = 2, un cluster de 15 brokers (Intuit) propaga una update en ~log2(15) × 250ms = ~1 segundo. Confirma el modelo.

Aplicación al MVP

Single-node: skip totalmente.

Sin cluster, no hay nada que disseminar.

Multi-node sobre Postgres: alternativa LISTEN/NOTIFY

En lugar de gossip epidémico, Postgres ofrece LISTEN/NOTIFY que hace broadcast nativo a connected clients:

LISTEN cluster_membership;
NOTIFY cluster_membership, '{"event":"member_died","node":"broker-3"}';
Aspecto LISTEN/NOTIFY Infection-style
Latency <100ms O(log N) × interval
Reliability Best-effort si client desconectado en momento de notify Exponencial coverage
Ordering Per-channel ordered No-orden
Costo 1 conn extra por cada listener 0 conn
Funciona offline Sí (clients re-leen state al reconectar) Sí (gossip se cura)

Recomendación MVP: usar LISTEN/NOTIFY con un table-based source of truth. Cuando un node se cae, pg_stat_activity permite detectarlo. Es mucho más simple que implementar SWIM custom.

Cuándo migrar a infection-style

  • Si vas a > 50 nodes (LISTEN/NOTIFY genera carga creciente en el primary).
  • Si necesitas operar geo-distribuido sin un primary central.
  • Si tu workload tiene altísima rate de membership changes (auto-scaling agresivo).

Cross-refs