Skip to content

CONCEPT Cited by 1 source

Fanout and cycle (gossip convergence)

Fanout and cycle are the two numeric knobs that control how fast a gossip protocol spreads a message across a cluster.

  • Fanout — how many peers each node contacts per gossip round.
  • Cycle — one round of gossip exchange (also called the gossip interval).

The convergence law

From sources/2023-07-16-highscalability-gossip-protocol-explained, the operational rule of thumb every gossip operator must know:

"cycles necessary to spread a message across the cluster = O(log n) to the base of fanout, where n = total number of nodes."

Formally: to blanket n nodes with fanout f, convergence takes on the order of log_f(n) rounds. Doubling the fanout roughly halves the number of rounds needed; doubling the node count adds only a fraction of a round.

Worked numbers (from the post)

  • n = 25,000 nodes, typical fanout ⇒ ~15 rounds to propagate a message.
  • Gossip interval = 10 ms ⇒ ~15 rounds × 10 ms = ~150 ms best case; with slight slack, the post's "big data center in roughly 3 seconds" datapoint.
  • n = 128 nodes case study — gossip uses <2% CPU, <60 KBps bandwidth — canonical "gossip is cheap at moderate scale" benchmark.

Choosing fanout

Fanout is the lever for trading rounds-to-convergence against per-round traffic.

Fanout Rounds for n=10k Per-node traffic Effect
2 ~13 Low Slow but cheap.
4 ~7 Low-medium Common default.
8 ~5 Medium Speeds convergence for large n.
log(n) ~constant High Best rounds, worst bandwidth.

In practice most implementations fix fanout at 3–5 — the sweet spot on the log curve.

Choosing cycle

Cycle sets the wall-clock latency floor of the protocol. A 10 ms cycle is aggressive (Cassandra historically defaulted to 1 second; SWIM implementations commonly use 200 ms–1 s).

"The usage of the gossip protocol results in increased latency because the node must wait for the next gossip cycle (interval) to transmit the message" (Source: sources/2023-07-16-highscalability-gossip-protocol-explained).

Performance metrics to track

From the post's §Gossip Protocol Performance:

  • Residue — nodes that still haven't received the message (should approach 0).
  • Traffic — average messages exchanged per pair of nodes (should stay low).
  • Convergence — how quickly each node receives the message.
  • Time average — average time for the cluster to absorb a message.
  • Time last — time for the last node to receive it (fat-tail latency).

Saturation point

Gossip's bounded per-node load breaks when "the amount of information that a node should gossip exceeds the bounded message size" — the effective fanout degrades and messages are truncated or deferred. The saturation point depends on (generation rate × message size) / (fanout × cycle). Past it, convergence falls off a cliff (Source: sources/2023-07-16-highscalability-gossip-protocol-explained §Bandwidth).

Seen in

Different sense: "fanout" in incremental indexing

Meta's Glean post (sources/2025-01-01-meta-indexing-code-at-scale-with-glean, 2024-12-19) uses "fanout" in a distinct sense — transitive dependency reach — not gossip convergence:

"in C++ if a header file is modified, we have to reprocess every source file that depends on it (directly or indirectly). We call this the fanout. So in practice the best we can do is O(fanout)."

Same word, different mechanism. In gossip, fanout is the per-round outbound degree each node picks; convergence is O(log_f(n)). In incremental indexing, fanout is a transitive closure — the set of files semantically affected by a change; per-diff indexing cost is bounded by fanout size. Both are legitimate uses of the term; the wiki treats the incremental-indexing variant under incremental indexing.

Last updated · 319 distilled / 1,201 read