Articles / Systems Programming

  • distributed-systems
  • gossip
  • go
  • tombstones
  • anti-entropy
  • debugging

Why Gossip Keeps Delivering Old News After a Partition Heals

You delete a key, the cluster agrees it is gone, and a week later it comes back. Nobody wrote it. A node that was cut off from the others simply rejoined and cheerfully told everyone what it remembered.

This is not a bug in gossip. It is gossip doing exactly what it was asked to do, with a merge rule that cannot tell old news from new. Let's look at the three places it goes wrong.

The merge rule is where the damage happens

Gossip itself only moves state around: each node picks a peer every so often and swaps what it knows. Whether the result is correct depends entirely on what a node does when two values disagree.

If the rule is "accept whatever I was just sent", a stale node that rejoins will overwrite fresh data on every peer it talks to. Within a few rounds the old value has spread across the cluster, and it looks just as legitimate as the real one.

Give every value a version, and make ties deterministic

The fix is to attach an ordering to each entry and only accept strictly newer ones. A per-key counter works if one node owns the key; otherwise you need a hybrid logical clock or version vectors.

type Entry struct {
	Value   string
	Version uint64 // bumped by the writer on every change
	Node    string // writer ID, used only to break ties
	Deleted bool
}

func (e Entry) newerThan(o Entry) bool {
	if e.Version != o.Version {
		return e.Version > o.Version
	}
	return e.Node > o.Node
}

func merge(local, remote map[string]Entry) {
	for k, r := range remote {
		if l, ok := local[k]; !ok || r.newerThan(l) {
			local[k] = r
		}
	}
}

The tie-break on Node matters more than it looks. Two nodes that write the same version concurrently must still converge on the same winner everywhere, or the cluster flaps forever.

Quick detour: why not just use timestamps?

Wall clocks are the obvious version number, and last-write-wins on timestamps is common. It is also fragile. A node whose clock runs five minutes fast will win every conflict for five minutes, and a node that was partitioned may have had its clock stepped by NTP in the meantime.

Hang on, that sounds like it breaks everything, so why do real systems use it? Because it is cheap, and for data where losing one concurrent write is acceptable it is fine. Just know that you are trading correctness for simplicity, and that skew silently picks the loser.

Deletes are the real trap

A delete cannot just remove the key. If node A deletes it and node B was unreachable, B still holds the old value. When B rejoins, A has nothing to compare against, so B's copy looks like a brand new key.

The standard answer is a tombstone: keep the entry, mark it Deleted: true and give it a higher version. Then the merge function above treats a delete like any other write, and B's old value loses.

func del(local map[string]Entry, key, self string) {
	old := local[key]
	local[key] = Entry{Version: old.Version + 1, Node: self, Deleted: true}
}

Tombstones have to outlive the longest partition

You cannot keep tombstones forever, so they get garbage collected after some grace period. If a partition lasts longer than that period, the tombstone is gone and the deleted key returns. The cluster has forgotten that it ever deleted it.

Cassandra has exactly this knob, gc_grace_seconds, and its documentation warns that a node down for longer than that must be repaired or rebuilt before rejoining. Whatever system you use, the rules are the same:

  • Set the tombstone lifetime comfortably longer than your worst realistic outage.
  • Refuse to let a node rejoin if it has been away longer than that, and make it resync from scratch.
  • Do not purge a tombstone until you have good reason to think every replica has seen it.

Rumour spreading has no memory of what it already told you

Many gossip designs push each update for a limited number of rounds, then stop, to save bandwidth. That is fine while everyone is reachable. Behind a partition, the rounds run out on one side before the other side can hear anything.

When the link returns, nobody has a reason to retell the news. Meanwhile the stale side may still be actively pushing its old rumour. Result: the two halves disagree and nothing prompts them to compare notes.

Anti-entropy is the repair loop

The cure is a slower background process that compares full state, not just recent updates. Each node periodically picks a peer and reconciles everything, usually by exchanging hashes first (a Merkle tree, or just a digest per range) and then only the differing keys.

  1. Pick a random peer every few seconds or minutes.
  2. Exchange a digest of your state.
  3. If the digests differ, exchange the differing entries.
  4. Run merge on what arrives, in both directions.

Because merge only accepts strictly newer entries, this is safe to run constantly. It is idempotent: replaying it changes nothing once the nodes agree.

How to check yours behaves

Test the ugly sequence on purpose. Partition a node, delete a key on the majority side, wait past your tombstone lifetime, heal the partition and see what happens. If the key returns, your grace period is shorter than your outage tolerance.

Then repeat with the partitioned node's clock set ten minutes ahead. If it wins conflicts it should not, your version scheme is leaning on wall time. Both tests take minutes to write and save you from a very confusing incident later.