Telling a thousand servers something
A cluster has a thousand servers. One of them notices that a neighbour has died. Every server needs to hear about it.
The obvious design is a central coordinator that keeps the list and tells everyone. It works, until the coordinator is slow, overloaded, or is itself the server that died.
There is another way, and it comes from how rumours spread in an office. Nobody announces anything. One person tells another, those two each tell someone, and by lunch everyone knows.
The protocol
One server learns something
For example: "server 17 has stopped responding".
At regular intervals, it picks another server at random and tells it
Any server at all. No list of who has been told is kept.
Every server that knows does the same
Each one, every round, picks a random server and passes it on.
Repeat
Until everyone has heard.
That is a gossip protocol, sometimes called an epidemic protocol, because information spreads the way an infection does.
Start. 64 servers. One of them has just learned something: a setting changed, or a server died. There is no central list and no boss to announce it.
- Round
- 0
- Servers that know
- 1 / 64
- Messages that reached nobody new
- 0
Why it is so fast
Early on, almost every message reaches a server that had not heard. So the number of servers that know roughly doubles each round: 1, 2, 4, 8, 16.
Doubling is very fast.
| Servers | Rounds until all have heard, roughly |
|---|---|
| 64 | 11 |
| 1,000 | 17 |
| 1,000,000 | 35 |
A million servers, and everyone knows within a few dozen rounds. With one round per second, that is about half a minute. Multiplying the cluster by a thousand added only about twice as many rounds.
Why the end is slow
Watch the last rounds in the animation. Most servers already know, so most messages land on someone who has heard it before. The remaining few are only reached by luck.
That is why the totals in the table are a bit more than pure doubling would give. The spread has two phases: fast doubling to reach most servers, then a slower tail to catch the stragglers.
What makes it robust
Gossip looks wasteful. Many messages are repeats. That redundancy is exactly why it is hard to break.
- No server is special. There is no coordinator to fail. Any server can start a rumour and any server can pass it on.
- Lost messages do not matter. If one message is dropped, the same news will arrive from someone else a round later.
- Dead servers do not matter. A message sent to a dead server is wasted, and others carry on.
- The load is even. Each server sends one message per round, whether the cluster has ten members or a million.
Good at
- No central point to fail or overload
- Tolerates lost messages and crashed servers without special handling
- Each server does a small, fixed amount of work per round
- Scales to very large clusters
Where it bites
- Not instant: news takes a number of rounds to reach everyone
- For a while, different servers believe different things
- No guarantee about exactly when a particular server will hear
- Many messages are repeats
Agreeing in the end, not at once
During those rounds, some servers know and some do not. A system built on gossip accepts that. It promises that everyone will agree eventually, not at every instant. This is called eventual consistency.
So gossip is the right tool when being a few seconds out of date is harmless:
- Who is in the cluster. Which servers are alive, which have joined or left.
- Failure detection. Servers gossip about who they have heard from recently. If nobody has heard from a server for a while, it is declared dead.
- Spreading settings and summaries such as load figures.
It is the wrong tool for decisions that everyone must make identically at the same moment, such as who the leader is. Those need a majority vote.
Key takeaways
- In a gossip protocol, each server periodically tells one random server what it knows.
- The number of servers that know roughly doubles each round at first.
- A million servers hear the news in a few dozen rounds.
- There is no coordinator, and lost messages or dead servers do not stop the spread.
- Servers agree eventually, not instantly, so gossip suits membership and failure detection, not decisions that need exact agreement.