Part of my notebook. Terse by design.

The eight fallacies

Every distributed systems bug traces back to believing one of these (Deutsch and Gosling, decades ago, still undefeated):

  1. The network is reliable
  2. Latency is zero
  3. Bandwidth is infinite
  4. The network is secure
  5. Topology doesn’t change
  6. There is one administrator
  7. Transport cost is zero
  8. The network is homogeneous

CAP, as used in real conversations

  • Consistency: every node returns the most recent data. Do all nodes see the data they’re supposed to?
  • Availability: the system always responds, even if some nodes are down (the data may be stale).
  • Partition tolerance: the system keeps operating through a network failure between nodes.

Under partition you pick:

  • CP: every request gets the latest data, but some requests get rejected during failures. Single-primary SQL setups behave this way.
  • AP: the system always answers, possibly with stale data. Cassandra, DynamoDB.

Which systems compromise where: CouchDB gives up consistency, MongoDB availability (during elections), classic relational databases partition tolerance. The theorem matters less than the follow-up question: partitions are rare, so what do you trade the rest of the time? Latency vs consistency (PACELC). Every synchronous replica you wait on buys consistency with latency.

Consistent hashing

The problem: serverIndex = hash(key) % N redistributes almost every key when N changes. Adding or removing one server reshuffles the world.

The fix: hash both objects and server names onto the same ring. An object belongs to the next server clockwise. When a server dies, only its keys move to the next server; everything else stays put (~1/N of keys move). To even out the distribution, each physical server appears on the ring many times as virtual nodes.

Who uses it: DynamoDB and Cassandra for data partitioning, Akamai for content distribution across edge servers, load balancers for persistent connection distribution.

References: this video and consistent hash rings, theory and implementation.

Distributed locking and fencing tokens

Condensed from Martin Kleppmann’s How to do distributed locking. The argument is his; the compression is mine.

First question: is the lock for efficiency (avoid duplicate work) or correctness (prevent data corruption)? The answer changes everything.

Efficiency: a single Redis node with SET key value NX PX ttl to acquire and an atomic delete-if-value-matches to release is fine. Document loudly that the lock is approximate and may occasionally fail. Don’t build a five-node cluster for this.

Correctness: the trap is that a client can acquire a lock, pause (GC, network delay, clock jump), have its lease expire, and then resume and write while another client holds the lock. The TTL doesn’t save you; the paused client doesn’t know it’s dead.

The fix is fencing tokens: the lock service hands out a strictly monotonically increasing number with each grant, and the storage system rejects writes carrying an older token than one it has already seen. With ZooKeeper, the zxid or znode version works as the token. Note this requires the storage side to participate; a lock service alone can’t be safe.

Why not Redlock: Redis’s five-node Redlock algorithm produces no fencing token, and its safety leans on timing assumptions (bounded network delay, bounded pauses, well-behaved clocks; Redis uses gettimeofday, which can jump). A good asynchronous-model algorithm guarantees safety regardless of timing and lets only liveness suffer; Redlock doesn’t clear that bar. For correctness, use ZooKeeper (via Curator recipes) or a database with real transactions, plus fencing tokens on every resource access.

Two-phase commit and its successors

2PC ensures atomicity across participants:

  • Phase 1 (prepare/voting): coordinator sends PREPARE; each participant executes locally and votes COMMIT or ABORT.
  • Phase 2 (decision): if all voted COMMIT, coordinator broadcasts COMMIT, else ABORT.

The weakness is blocking: a dead coordinator at the wrong moment leaves participants holding locks with no decision. Hence:

  • 3PC adds a pre-commit phase to reduce blocking.
  • Paxos/Raft-based commits (Spanner, etcd, CockroachDB) get non-blocking behavior through quorum agreement.
  • Sagas for long-running business transactions: a sequence of local transactions, each publishing an event that triggers the next, with compensating transactions to undo on failure. The microservices answer; more in design patterns.

2PC is a coordination pattern more than a product; you mostly meet it inside things (XA transactions, some distributed databases) rather than choosing it.

Patterns that keep showing up

  • Ambassador: sidecar proxy handling retries, logging, monitoring (Envoy in Kubernetes).
  • Circuit breaker: stop calling a failing dependency so it can recover; prevents cascade failures.
  • CQRS: separate write and read paths, scaled independently.
  • Event sourcing: the journal of events is the state; replay gives history (git is the intuition pump).
  • Leader election: exactly one node owns a task (etcd, ZooKeeper).
  • Pub/sub: the newspaper delivery model.
  • Sharding: split data across nodes; see databases.
  • Strangler fig: replace a legacy system block by block behind a facade instead of big-bang.

A classic: sort 1 TB with 1,000 nodes of 1.5 GB RAM

1 TB of 64-bit integers is ~125 billion numbers; each node holds ~187 million in memory. Total cluster RAM (1.5 TB) exceeds the data, so it fits, barely. The shape of the solution is external distributed sample sort:

  1. Local sort: each node sorts its own chunk in memory.
  2. Sample and pick splitters: each node contributes sample values; a coordinator sorts the samples and picks N-1 splitters defining N contiguous ranges.
  3. Shuffle: every node sends each of its values to the node owning that range. This is the expensive, all-to-all network phase.
  4. Merge: each node k-way-merges the sorted runs it received. Concatenating node outputs in range order gives the globally sorted result.

Miniature version to check intuition: 20 integers, 4 nodes, 5 per node. Sample the medians, splitters [22, 31, 63], shuffle, merge. Same algorithm, twelve orders of magnitude smaller.

Related: round-robin load balancing per layer adds variance in load; see the balls into bins problem.

Replica failover, concretely

MongoDB’s default configuration elects a new primary in under ~12 seconds (tunable via settings.electionTimeoutMillis; network latency stretches it). The sharp edge: writes the old primary accepted but never replicated get rolled back when it rejoins. If you can’t afford that, you need majority write concern and the latency bill that comes with it. Watch CPU (data falling out of memory), disk IOPS against provisioned limits, and connection counts; failovers are much worse on a struggling cluster.