One Flipped Bit, Gossiped Everywhere — JavaScript Bug Hunt

Briefing

Modelled on the Amazon S3 outage of 20 July 2008. S3's servers shared system state with each other through a gossip protocol. Amazon's post-mortem found that a single bit had been corrupted in some of those messages; S3 checksummed much of its traffic but not this internal state, so the corrupted value was accepted and passed on server to server. The state could not be repaired while running, and S3 had to be taken down and its gossip state cleared, which took several hours. Amazon added checksums to that state afterwards.

gossip.js merges a peer's server-state message into a node: each entry carries a status and a version, and newer versions win — so a flipped high bit in a version makes a bogus entry win everywhere.

Fix applyGossip to verify the message before merging anything.

Bug report

BUG-S3-0720 · Priority: Critical · Reported by: storage on-call

applyGossip(node, message) — message is { from, state, checksum }:

• if message.checksum is not a number equal to checksum.of(message.state), the message is dropped: node.state is unchanged, node.rejected increases by 1, and the call returns false
• otherwise each entry is merged (an entry with a higher version replaces the node's copy; unknown servers are added) and the call returns true

A node must therefore never relay state it received corrupted.

Observed: one message with version 3 flipped to 1027 marked a healthy server "down" on every node in the cluster within minutes.

Logs

[gossip] node-b <- node-a s1 status=down version=1027 (had up@3)
[gossip] node-c <- node-b s1 status=down version=1027
[gossip] 100% of nodes report s1 down; request routing degraded

The code as shipped

src/gossip/gossip.js (editable)

var checksum = require("./checksum");

// Merges a peer's view of server state into this node.
exports.applyGossip = function (node, message) {
  var incoming = message.state;
  Object.keys(incoming).forEach(function (id) {
    var mine = node.state[id];
    var theirs = incoming[id];
    if (!mine || theirs.version > mine.version) {
      node.state[id] = { status: theirs.status, version: theirs.version };
    }
  });
  return true;
};

Read-only context: src/gossip/checksum.js, src/gossip/cluster.js.