One Flipped Bit, Gossiped Everywhere

Medium

· Backend

Incident

SEV-1

BUG-S3-0720

Priority: Critical · reported by storage on-call

Time to fix: 20 min

Failing checks on the shipped build

  • a message corrupted in transit is dropped

    expected false but got true

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

Inspired by

Amazon S3 · 2008

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.

Code map

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;
};

Sign in to edit the file, run the tests and submit a fix

A free account — no card, no trial clock. You come straight back here.

One Flipped Bit, Gossiped Everywhere — JavaScript Bug Hunt

Modelled on the Amazon S3 outage of 20 July 2008. S3's servers shared system state with each other through a gossip protocol.

  • Language: JavaScript
  • Layer: Backend
  • Difficulty: Medium
  • Concepts: Networking, Consistency, Validation
  • Modelled on: Amazon S3 · 2008
  • Visible tests: a valid message is merged; a message corrupted in transit is dropped
  • Reward: 50 XP for a complete fix

Incident

  • Severity: SEV-1 (priority: Critical)
  • Ticket: BUG-S3-0720
  • Reported by: storage on-call
  • Time to fix: 20 minutes, the target for a medium incident

Failing checks on the shipped build

  • a message corrupted in transit is dropped — expected false but got true

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

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.

Open the hunt to start the incident clock, edit the files, run the visible tests and submit against the hidden ones, then write the root cause down. More JavaScript bug hunts.