Why network partitions are the hard part of distributed systems

Modern applications are built from many components that exchange messages over an asynchronous, unreliable network. That makes understanding a distributed system's reliability largely a question of shared state: nodes must agree on what happened. "Did my write succeed?" "Is that value visible to others?" "Will this data survive a failure?" The answers depend on the consistency and durability guarantees the system provides, and those guarantees get complicated when the network misbehaves.

Consider what a write to a replicated system actually promises. Depending on the database and its configuration, a write might be visible to everyone immediately, visible only to your connection now and to others later, or merely causally connected to some future state. Durability has similar shades of meaning: a write might survive a single node failure, a full power loss, or the destruction of an entire datacenter, given time to replicate. These properties are hard enough to reason about on a healthy network. They become far trickier when the network is dropping or delaying messages.

What a partition really means

Formal models of distributed systems often assume an asynchronous network, one that can arbitrarily duplicate, drop, delay, or reorder messages. That sounds like a pessimistic assumption, but real IP networks exhibit all of these failure modes, so the theoretical limits of asynchrony apply to practical systems too.

TCP masks much of this chaos at the transport layer. Sockets provide ordered, reliable delivery: messages arrive without duplication or reordering. But TCP cannot eliminate arbitrary delays, and a distributed system that waits forever on a delayed message will simply lock up. Since nodes have finite memory and need latency bounds, we introduce timeouts. When a message doesn't arrive in time, the connection is closed and the read() call fails.

That brings us to the fundamental problem of the partition: from inside the system, a node cannot distinguish between a slow peer and a dead one. All knowledge of other nodes passes through the network itself. When a partition occurs, no node can know whether the others are alive, whether they received a message, or whether they tried to respond. After the network heals, the nodes must reconnect and reconstruct what happened, often from an inconsistent state.

Many systems respond to partitions by entering a degraded mode. The CAP theorem states that during a partition you can have consistency (linearizability for a read-write register) or availability, but not both. That's a theoretical bound; in practice, some databases don't even meet CAP's terms and simply drop data.

Building a test cluster

You don't need exotic hardware to experiment with partitions. A five-node cluster of Ubuntu 12.10 machines virtualized with LXC works fine, as do real machines or cloud instances. Name the nodes n1 through n5 and add them to /etc/hosts on the nodes and on your client machine. The cluster configuration and test code are available in the Jepsen repository on GitHub.

To orchestrate commands across the cluster, the setup uses Salticid, configured via ~/.salticidrc to point at the Jepsen config. That configuration defines a :jepsen group with hosts n1 through n5, using the default user and password for the nodes. (Change those if your nodes are reachable from the public internet.)

Several Salticid roles are predefined. The base role provides basic OS functions like base.reboot and base.shutdown. The jepsen role defines the partition scenarios:

  • jepsen.partition causes nodes n1 and n2 to drop IP traffic from n3, n4, and n5, by manipulating iptables rules.
  • jepsen.status reports the current network state.
  • jepsen.heal resets iptables to its defaults, ending the partition.

Beyond hard partitions, the config can simulate degraded networks. Using tc on the eth0 interface, jepsen.slow adds latency and jepsen.flaky probabilistically drops messages. These conditions reproduce timing-dependent bugs in replication and other distributed algorithms that a clean partition might not trigger.

A workload for detecting inconsistency

Testing how a system behaves under partition requires a workload that can expose disagreement between the database and its clients. The Jepsen test app does this with a simple pattern: several clients write integers to a list in the database. With five clients, client 0 writes 0, 5, 10, and so on; client 1 writes 1, 6, 11, etc.

Each write is recorded as either acknowledged by the database or errored. At the end of the run, the test fetches the full set of values and compares it against the record. If an acknowledged write is missing, or an unacknowledged write appears, the system behaved inconsistently: the client and database disagreed about what happened.

The Clojure implementation lives in the Jepsen repo. The application protocol and the parallel runner are in jepsen/src/jepsen/set_app.clj, with database-specific implementations in separate files such as src/jepsen/riak.clj, pg.clj, and redis.clj. Running the code requires a JVM and Leiningen 2.

With this setup, the series walks through each database in turn, inducing partitions during the workload and observing how the system's guarantees hold up when messages are dropped and nodes cannot agree on the state of the world.