Distributed Systems Fundamentals & Core Invariants

Target Concept: Core distributed computing theories, models, failure modes, and concurrency paradigms expected in Amazon SDE II (L5) and Senior SDE (L6) system design interviews.

1. The Core Theorems: CAP & PACELC

A. CAP Theorem in Practice

In an asynchronous network where network partitions ($P$) are an unavoidable physical reality, a distributed storage system can guarantee at most one of:

• Consistency ($C$): Every read receives the most recent write or an error (Linearizability).
• Availability ($A$): Every non-failing node returns a non-error response for every request, without guaranteeing it contains the most recent write.

Synthesizing vector architecture diagram...

Start at the top: a network partition has split the nodes. Now the system must choose what a node does when it cannot reach the others. Take the CP branch and it refuses or errors on requests it cannot confirm are up to date, as Raft, etcd, ZooKeeper and Aurora's write quorum do; the minority side becomes unavailable, but nobody reads stale or conflicting data. Take the AP branch and every node keeps answering with what it has, as DynamoDB by default, Cassandra and Route 53 do, and replicas reconcile after the partition heals. Neither is better in general: choose CP for money, locks and inventory counts, and AP for carts, feeds and DNS, where a slightly stale answer beats no answer.

Real-World Interview Nuance (The AWS Reality)

• No Pure "CA" Systems: A network partition is not a design choice; it is a physical condition caused by fiber cuts, switch failures, or GC pauses. Systems claiming to be "CA" simply crash or become completely unavailable when a partition occurs.
• Granular CAP: Systems are rarely globally $CP$ or $AP$. For example, Amazon DynamoDB allows the caller to choose per read operation:
  • ConsistentRead: false (default) $\rightarrow$ $AP$ behavior (returns from nearest storage replica with 1 read capacity unit for 4KB, latency $<5\text{ms}$).
  • ConsistentRead: true $\rightarrow$ $CP$ behavior (queries leader/quorum replica, costs 2 read capacity units, guarantees linearizability).

B. PACELC Theorem (The Latency Dimension)

The CAP theorem only describes behavior during a network partition. But partitions are rare (typically $<0.1\%$ of normal operating time). What happens during normal operation?

The PACELC Theorem extends CAP:

2. Partitioning, Sharding & Consistent Hashing

When data or throughput exceeds the physical limits of a single machine (CPU, RAM, disk I/O, network bandwidth), the dataset must be partitioned.

A. Partitioning Strategies

Synthesizing vector architecture diagram...

1. Range Partitioning:
   • Keys are sorted and partitioned into continuous ranges (e.g., timestamps, alphabetical user IDs).
   • Pro: Efficient range queries (SELECT * WHERE timestamp BETWEEN t1 AND t2).
   • Con (Hotspots): Sequential writes (e.g., current timestamp) bombard a single shard while others sit idle.
2. Hash Partitioning (Modulo Sharding):
   • $\text{Shard} = \text{hash}(\text{key}) \pmod N$.
   • Pro: Uniform data distribution across $N$ nodes.
   • Con (Resharding Catastrophe): If $N$ changes to $N+1$, nearly $100\%$ of keys hash to different nodes, requiring a massive cluster rebalance.
3. Consistent Hashing with Virtual Nodes:
   • Maps both nodes and keys to a continuous $2^{32}-1$ or $2^{128}-1$ hash ring.
   • A key belongs to the first node encountered clockwise on the ring.
   • Virtual Nodes (Vnodes): Each physical node is assigned 100–300 virtual positions on the ring.
   • Trade-off Resolution: When a node is added or removed, only $\frac{K}{N}$ keys must migrate (where $K$ is total keys, $N$ is number of nodes), and Vnodes ensure the migrated load is evenly distributed across all remaining nodes rather than overloading a single neighbor.