Distributed Databases: Sharding & CAP Theorem

Curriculum Capstone

When data scale outgrows the storage, CPU, and memory bounds of any single physical server, databases must partition their records across a distributed cluster of independent nodes. In this tenth and concluding installment of the Database Systems curriculum, we explore distributed data architectures: Horizontal Sharding, Consistent Hashing, distributed transaction coordination via Two-Phase Commit (2PC), the fundamental physics of the CAP Theorem & PACELC Model, and the modern NewSQL Revolution.

1. Horizontal Partitioning & Consistent Hashing

Sharding divides a massive database into smaller, faster, and more manageable discrete sub-databases called shards, distributed across distinct physical hardware servers:

Range-Based Partitioning

Assigns contiguous ranges of shard keys to specific nodes (e.g., Shard A: User IDs 1–1,000,000; Shard B: 1,000,001–2,000,000). Highly efficient for range queries, but prone to catastrophic write hotspots when monotonically increasing keys (such as timestamps or auto-increment IDs) hit only the newest shard.

Hash-Based Sharding & Consistent Hashing

Maps keys to shards using a cryptographic hash: $Node = ext{hash}(key) \pmod N$. Naïve modulo hashing causes massive data reshuffling whenever $N$ changes. Consistent Hashing maps both servers and keys to a $2^{32}$ circular ring. When a server joins or leaves the cluster, only $K/N$ keys need migration on average, while virtual nodes ensure uniform load distribution across heterogeneous hardware.

2. Distributed Transactions: Two-Phase Commit (2PC)

When a single transaction modifies rows located on multiple distributed shards, achieving atomicity across unreliable networks requires a specialized coordination protocol:

The Two Phases of 2PC

Phase 1 (Prepare Phase): The coordinator sends a PREPARE message to all participating shard nodes. Each participant executes the transaction locally, writes redo/undo logs to non-volatile disk, holds exclusive locks, and replies with VOTE_COMMIT or VOTE_ABORT.

Phase 2 (Commit Phase): If all participants vote commit, the coordinator writes a commit record to its log and broadcasts GLOBAL_COMMIT. If any node votes abort or times out, the coordinator broadcasts GLOBAL_ABORT.

The 2PC Blocking Hazard: If the coordinator node crashes during Phase 2 after participants have voted, participants remain indefinitely blocked, unable to release locks or determine transaction fate until the coordinator recovers.

3. The CAP Theorem & The PACELC Framework

Formulated by Eric Brewer in 2000 and formally proven by Seth Gilbert and Nancy Lynch in 2002, the CAP Theorem proves that a distributed data store can guarantee at most two of three properties simultaneously:

Consistency (Linearizability)

Every read receives the most recent write or an error. All nodes see the exact same data at the exact same instant in time.

Availability

Every non-failing node returns a non-error response for every request, without guaranteeing that it contains the most recent write.

Partition Tolerance

The system continues to operate despite an arbitrary number of messages being dropped or delayed by the network between nodes.

Because physical network partitions (fiber cuts, router reboots) are unavoidable in distributed hardware, a system must always maintain Partition Tolerance (P). Thus, when a partition occurs, an architect must choose between CP (sacrificing availability to maintain absolute consistency) or AP (returning stale data to preserve 100% uptime).

Daniel Abadi extended this into the PACELC Model: In a system that has Partitions, one must trade off Availability vs. Consistency; Else (when the network is running normally), one must trade off Latency vs. Consistency.

4. The NewSQL Revolution: Spanner & CockroachDB

For years, software engineering assumed an inescapable dichotomy between single-node ACID relational databases and eventually consistent NoSQL clusters. NewSQL systems shatter this compromise:

Google Cloud Spanner: Achieves globally distributed external consistency (strict serializability) at global scale using the TrueTime API, which bounds clock uncertainty ($\epsilon pprox 1 ext{ms}$) via synchronized atomic clocks and GPS receivers across worldwide datacenters.
CockroachDB: Implements Raft consensus per range and Hybrid Logical Clocks (HLC) to deliver horizontally scalable SQL with complete serializable ACID guarantees without requiring specialized satellite hardware.

Curriculum Complete!

You have journeyed from the theoretical foundations of ANSI-SPARC schemas and relational algebra, through the internal mechanics of slotted pages, B+ trees, and ARIES recovery, to global distributed NewSQL architectures. You now possess an end-to-end engineering mastery of modern database systems.