Distributed Systems for Software Engineers (2026)

CAP theorem with a worked example: order-placement service

The 'pick two' framing is the first thing every interview candidate says and the first thing senior+ interviewers grade poorly. Eric Brewer himself walked the framing back in his 2012 IEEE article 'CAP Twelve Years Later' (computer.org/csdl/magazine/co/2012/02). The honest framing is: during a network partition, you pick consistency or availability; outside partition, you can have both, plus low latency.

Worked scenario: a multi-region order service.

You run an order-placement service in two regions, US-East and US-West, with synchronous replication between them. A network partition isolates US-West for 30 seconds.

Before partition:        After partition (US-West isolated):
[US-East]<==sync==>[US-West]   [US-East]   X   [US-West]
      |                  |             |             |
   [order DB]       [order DB]    [order DB]    [order DB]

CP choice (favor consistency): US-West rejects writes during the partition. Riders in California get 503 errors. The system is correct (no divergence) but unavailable in the West. This is what Spanner does with Paxos quorum: a write needs a majority of replicas; partitioned minorities can't write.

AP choice (favor availability): US-West accepts writes locally and reconciles when the partition heals. Two riders may book the last seat on the same flight; you get duplicate orders that need post-hoc resolution (last-writer-wins, or vector clocks + application-level merge). This is what Dynamo / Cassandra do.

The senior+ answer to 'CAP for an order service':

'Order placement is CP. Duplicate orders are worse than 30 seconds of unavailability — we'd rather a customer retry than have to reconcile two oversold orders. Reads of orders (status checks) are AP — slightly stale data is fine. So the system is mixed-consistency: writes route through a leader (CP), reads can hit any replica (AP). This is what CockroachDB and Spanner do; it's the right pattern for transactional workloads.'

Reference: DDIA ch. 9, p. 336-342, on the CAP confusion; Daniel Abadi's PACELC extension (cs-www.cs.yale.edu/homes/dna/papers/abadi-pacelc.pdf) which adds the 'else' clause: 'in absence of partition, choose between latency and consistency'. PACELC is the better mental model.

Raft consensus walked through on a 5-node cluster

Raft (raft.github.io/raft.pdf) is the consensus algorithm to learn deeply. etcd, Consul, CockroachDB, TiKV, and RethinkDB all use Raft in production. Paxos is theoretically equivalent but is what gets cited in academic papers; Raft is what gets implemented.

Setup: 5 nodes (N1..N5). One is leader; others are followers.

Step 1 — Initial state. N1 is leader. All 5 nodes have committed log entries [1: SET x=1, 2: SET y=2]. Term = 4.

N1 (leader, term=4)  [1:SET x=1, 2:SET y=2]
N2 (follower)        [1:SET x=1, 2:SET y=2]
N3 (follower)        [1:SET x=1, 2:SET y=2]
N4 (follower)        [1:SET x=1, 2:SET y=2]
N5 (follower)        [1:SET x=1, 2:SET y=2]

Step 2 — Client write. Client sends SET z=3 to N1.

1. N1 appends [3: SET z=3] to its local log (uncommitted).
2. N1 sends AppendEntries RPCs to N2..N5 with the new entry.
3. N2, N3, N4 ack; N5 is slow but will catch up.
4. N1 has a majority (itself + 3 = 4 of 5). It commits the entry locally and applies to state machine.
5. Client gets ack.
6. On the next AppendEntries (heartbeat), N1 tells followers 'commitIndex = 3'; they apply the entry to their state machines.

Step 3 — Leader fails. N1 crashes. Heartbeat timeouts (200ms by default in etcd) fire on N2..N5.

1. N3's election timer (randomized 150-300ms) fires first. N3 increments term to 5, votes for itself, sends RequestVote RPCs.
2. N2, N4, N5 all check: is N3's log at least as up-to-date as ours? Yes (everyone has the same log). Grant vote.
3. N3 has 4 votes (majority). Becomes leader for term 5.
4. N3 sends heartbeats. New leader is established within ~300-500ms total.

Step 4 — N1 recovers. N1 comes back online with term=4. N3's heartbeat arrives with term=5. N1 sees term > its own; steps down to follower; updates term to 5. Cluster is back to 5 nodes.

The split-vote scenario (why an even number of nodes is dangerous): in a 4-node cluster after leader failure, two nodes could vote for one candidate and two for another. No majority; no leader. The election retries with random timeouts until one wins. With 4 nodes, this can take multiple rounds; with 3 or 5 nodes, the math guarantees a majority on first try most of the time. Always size Raft clusters at 3, 5, or 7 nodes — odd numbers, never even.

Reference implementation to read: etcd's raft package (github.com/etcd-io/raft). 4000 lines of Go, well-commented, used in Kubernetes for cluster state. Reading the step function in raft.go is the highest-leverage hour of distributed-systems study.

Partitioning strategies: Spanner, DynamoDB, Cassandra compared

The three production patterns to know cold. DDIA chapter 6 (p. 199-228) walks all three; here's the senior+ summary with the tactical decision-tree.

Consistent hashing — the production technique used in DynamoDB and Cassandra. Naive hash partitioning (hash(key) % N) breaks when you add a node — every key remaps. Consistent hashing maps both nodes and keys onto a ring; adding a node only remaps keys near the new position.

# Pseudocode
class ConsistentHashRing:
    def __init__(self, nodes, vnodes_per_node=150):
        self.ring = {}  # hash_position -> node
        for node in nodes:
            for v in range(vnodes_per_node):
                pos = hash(f"{node}:{v}")
                self.ring[pos] = node
        self.sorted_positions = sorted(self.ring)

    def get_node(self, key):
        pos = hash(key)
        # Find first position >= pos in the ring (wrap around)
        idx = bisect.bisect(self.sorted_positions, pos) % len(self.sorted_positions)
        return self.ring[self.sorted_positions[idx]]

Virtual nodes (vnodes) prevent hot-spots when nodes have heterogeneous capacity. The Dynamo paper (Section 4.2, sosp.org/2007/papers/dynamo.pdf) explains why naive consistent hashing fails on heterogeneous clusters and how vnodes fix it.

Range partitioning — the Spanner / Bigtable pattern. Keys are sorted by primary key prefix; tablets (Bigtable) or splits (Spanner) cover contiguous key ranges. Splits are added or merged dynamically based on load.

Hot-spot mitigation:

• Salt the prefix: if you partition by timestamp, prefix with a hash bucket so writes scatter (e.g., {0..9}#{timestamp} instead of {timestamp}).
• Composite keys: in DynamoDB, use a partition key that distributes well (user_id) and a sort key for ordering (event_time).
• Tablet splitting: Spanner splits a tablet when it exceeds 4GB (per the Spanner paper); the rebalancer redistributes splits across nodes.

The Foursquare 2010 outage (blog.foursquare.com/post/1346372637) is the canonical 'why range-based partitioning on monotonic keys fails' case study. They sharded MongoDB by user_id which grew monotonically; one shard hot-spotted to 200% memory utilization; the cluster failed over and chained the failure across all shards. 11-hour outage. Always cite this when an interviewer asks about range partitioning.

Replication: leader-follower vs leaderless, with quorum math

Three replication patterns. DDIA chapter 5, p. 152-184, is the canonical reference; this is the operational summary.

1. Leader-follower (Postgres, MySQL, MongoDB single-replica-set): writes go to leader; followers replicate (async or sync). Read-after-write consistency is easy on the leader; eventual on followers.

Client writes -> [Leader] --replicates--> [Follower 1]
                                            -> [Follower 2]
Client reads (latest) -> Leader
Client reads (eventual) -> any follower

Failure mode: leader crashes, followers must elect new leader. If replication was async, the new leader might be missing the last few committed writes. Data loss without explicit ack mode.

2. Multi-leader (CouchDB, multi-region MySQL with Galera): multiple leaders, each accepts writes. Replication is async; conflicts can occur and need application-level resolution (last-write-wins, CRDTs, or manual reconciliation). Used when low write latency in multiple regions matters more than consistency.

3. Leaderless (Dynamo, Cassandra, Riak): any replica can accept writes; reads query multiple replicas and pick the most recent (with timestamps or vector clocks). Quorum: writes go to W replicas, reads query R replicas; R + W > N guarantees overlap.

# Cassandra-style: N=3 replicas
W=ONE, R=ONE      -> eventual consistency, low latency
W=QUORUM, R=QUORUM -> W=2, R=2; overlap guaranteed; strong-ish
W=ALL, R=ONE       -> strong reads, low write availability (any one node down = no writes)

The hidden trap: Cassandra defaults to W=ONE for performance. A write that succeeds on one node, then that node crashes before replicating, is lost. For durability, set W=QUORUM at minimum. Aphyr's Jepsen analysis of Cassandra (jepsen.io/analyses/cassandra) walks two real failure modes; if you're using Cassandra in production, this is required reading.

Sloppy quorums and hinted handoff (Dynamo's failure-tolerance trick): if a 'home' replica is down, write to a temporary replica; when home recovers, the temp replica hands off the data. Improves availability under partial failure but breaks the R + W > N guarantee briefly.

Cross-service consistency: 2PC, Sagas, and the modern pattern

For cross-service transactions (e.g., 'place order' touches inventory + payments + shipping), two-phase commit (2PC) was the textbook answer for 30 years and is largely deprecated in 2026.

Why 2PC failed in production: the coordinator is a single point of failure. If the coordinator crashes after phase 1 (prepare) but before phase 2 (commit), participants are stuck holding locks indefinitely. DDIA ch. 9, p. 354-360, walks the failure mode in detail.

The Saga pattern (Garcia-Molina & Salem, 1987 — cs.cornell.edu/andru/cs711/2002fa/reading/sagas.pdf) is the modern replacement. A long-running transaction is decomposed into a sequence of local transactions, each with a compensating action.

# Order placement saga
T1: Reserve inventory   (compensate: release inventory)
T2: Charge payment      (compensate: refund payment)
T3: Ship order          (compensate: cancel shipment)

If T2 fails: run compensate-T1 (release inventory).
If T3 fails: run compensate-T2, then compensate-T1.

Two saga implementation patterns:

1. Choreography (event-driven): each service emits events; downstream services react. No coordinator. Hard to track what stage the saga is in.
2. Orchestration (workflow engine): a coordinator (Temporal, AWS Step Functions, Camunda) drives the saga. Easier to debug; introduces a coordination layer.

Production reference: Temporal (github.com/temporalio/temporal) is the dominant orchestration engine in 2026. Used by Stripe, Snap, and Uber for cross-service workflows.

The honest senior+ answer when an interviewer asks 'how do you ensure cross-service consistency?':

'Sagas with compensating transactions, orchestrated by Temporal or a similar workflow engine. Idempotent operations on each participant. Outbox pattern (microservices.io/patterns/data/transactional-outbox.html) for the event publishing — write event to local DB transactionally with the state change; an async worker publishes from the outbox. Avoid 2PC; the coordinator-failure case is unsolved.'

What to study and in what order

Empirical 12-week curriculum for senior+ distributed-systems interview readiness:

1. Weeks 1-3 — DDIA chapters 1-7 (Kleppmann). The foundational text; read it twice if you can. Make notes on partitioning (ch. 6), replication (ch. 5), transactions (ch. 7).
2. Weeks 4-5 — Raft paper + etcd implementation. Read the Raft paper (raft.github.io/raft.pdf, 14 pages); read the step function in etcd's raft.go.
3. Weeks 6-7 — Three foundational papers. Spanner (research.google/pubs/spanner-googles-globally-distributed-database-2/), Dynamo (sosp.org/2007/papers/dynamo.pdf), Bigtable (research.google/pubs/bigtable). Read for the trade-off articulation, not the implementation detail.
4. Weeks 8-9 — Aphyr's Jepsen analyses. Read jepsen.io/analyses for at least three databases (Cassandra, MongoDB, etcd). The 'consistency-during-partition' failure modes are what interviews probe.
5. Weeks 10-12 — Practical implementation. Build a toy distributed key-value store using Raft (etcd's raft library is the easiest path). MIT 6.824 labs (pdos.csail.mit.edu/6.824) are the canonical hands-on; the 4 labs cover MapReduce, Raft, fault-tolerant KV, sharded KV.

The book if you only read one: DDIA. Kleppmann's coverage is what every senior+ FAANG interview implicitly assumes. Reading it twice with notes is the highest-leverage investment.

The course if you take one: MIT 6.824 'Distributed Systems' (pdos.csail.mit.edu/6.824). Free online, video lectures, four substantive labs in Go. Worked-shipped completion of lab 2 (Raft) puts you ahead of ~90% of senior candidates.