System Design · Module 3
Replication and Partitioning: Making One Dataset Look Like Many Machines
Every storage system that outgrows one disk makes two decisions independently: how many copies of each piece of data exist, and which machine is responsible for which slice of the key space. This module derives both from the systems that made the canonical choices — GFS's leased primary, Dynamo's quorum and consistent hash ring, Bigtable's split tablets — so that after it you can name which scheme any storage paper is using and predict its consistency and availability consequences before reading the paper's own consistency section.
1. Two decisions every storage system makes
A single machine with a single disk needs neither replication nor partitioning: one copy of the data exists, and that one machine owns all of it. The moment a dataset outgrows one machine — because it no longer fits, or because one machine cannot serve the request rate, or because you cannot tolerate the data disappearing when that one disk dies — you are forced to make two decisions, and the systems literature is unusually consistent about the fact that they are separate decisions with separate failure modes4.
1.1 Replication: how many copies, and who accepts writes
Replication asks: how many machines hold a copy of a given piece of data, and when a write arrives, which of those machines is allowed to accept it and in what order does it get applied everywhere else? The two dominant answers in this module are leader-based (one machine, the leader or primary, decides the order of writes for a given piece of data; the rest apply that order) and quorum-based / leaderless (any sufficiently large subset of the replica set can accept a write, and conflicting versions are reconciled later)4. GFS and Bigtable answer this with leases (Section 2); Dynamo answers it with a tunable read/write quorum (Section 3). The two answers trade off almost exactly the way you would guess from an ML-serving background: a single leader per shard gives you a total order for free but makes that shard unavailable for writes whenever the leader is unreachable; a quorum gives you availability during a failure but makes you deal with the fact that two clients may now have written two different values for the same key at the same time.
1.2 Partitioning: which machine owns which slice
Partitioning (also called sharding) asks a completely different question: given that the whole key space is too large or too hot for one machine, which contiguous or hashed slice of that key space does each machine own? The two dominant answers here are range partitioning (each machine owns a contiguous range of the sort order — row keys "aaron" through "berger", say) and hash partitioning (each machine owns a range of hash-function output, so keys that are lexicographically adjacent are scattered across machines)4. Bigtable answers this with range-partitioned tablets that split as they grow (Section 4); Dynamo answers it with hash partitioning via a consistent-hash ring (Section 3.2). Range partitioning keeps related keys together, which is what makes range scans over row keys cheap; hash partitioning spreads load evenly and destroys locality on purpose, which is what makes hot-key skew rare.
The reason this module treats replication and partitioning as one topic rather than two is that every real system answers both questions at once, and the two answers are usually coupled by the same mechanism. In GFS, a chunk (the unit of partitioning — each 64 MB chunk is a distinct piece of the file's key space) is also the unit of replication: the master grants a lease over one chunk to one chunkserver, and that decision is simultaneously "who owns this slice of the file" and "who orders writes to the N copies of it"1. In Dynamo, the consistent-hash ring simultaneously decides which node is the coordinator for a key (partitioning) and which N-1 successor nodes on the ring hold the other replicas (replication)3. In Bigtable, a tablet is a partitioning unit (a row range) whose replication is delegated entirely downward to the GFS files it is built on, so Bigtable's own contribution to this module is exclusively about partitioning — range partitioning, tablet splitting, and rebalancing — while its replication story is literally GFS's story one layer down2.
Module 4 builds transactions and indexes on top of whichever replication and partitioning scheme is already in place — a B-tree index or an LSM-tree is a local data structure on one partition, and a cross-row transaction has to somehow span multiple partitions and their replicas. Module 5 revisits the consistency consequences of the leader-based-versus-quorum-based choice in more formal terms (linearizability, CAP, PACELC). This module stays at the mechanism level: what a lease actually does, what a quorum actually guarantees, and what a hash ring or a tablet split actually looks like when you draw it.
2. Leader-based replication and lease-based ordering: GFS
The Google File System stores hundreds of terabytes across thousands of disks on over a thousand machines, accessed concurrently by hundreds of clients1. Files are divided into fixed-size chunks identified by a 64-bit chunk handle; GFS chose a chunk size of 64 MB, "much larger than typical file system block sizes," and each chunk is replicated on multiple chunkservers — three replicas by default, though an application can request a different replication level for a given region of the namespace1. A single master holds all metadata (the file and chunk namespaces, the file-to-chunk mapping, and the current location of every chunk's replicas) but deliberately never sits on the data path: "clients never read and write file data through the master... clients interact with the master for metadata operations, but all data-bearing communication goes directly to the chunkservers"1. That separation of a metadata-only master from a many-chunkserver data plane is the single design decision this section is really about: it is what makes leader election per-chunk cheap enough to redo constantly.
2.1 The write path: leases, primaries, and secondaries
GFS needs a consistent mutation order across a chunk's replicas, and it gets one from a lease rather than from a fully general consensus protocol run per write. "The master grants a chunk lease to one of the replicas, which we call the primary. The primary picks a serial order for all mutations to the chunk. All replicas follow this order when applying mutations. Thus, the global mutation order is defined first by the lease grant order chosen by the master, and within a lease by the serial numbers assigned by the primary"1. Once a chunkserver holds the primary lease for a chunk, the master's job is done for that chunk until the lease needs renewing or revoking — it does not adjudicate every mutation, which is exactly why a single master can serve as the metadata authority for an entire multi-thousand-machine cluster without becoming a bottleneck.
Figure 2 walks the seven numbered steps GFS's own paper uses to describe a write1. Two things are worth noticing in the mechanism, not just the sequence. First, control and data are deliberately decoupled: the client pushes the actual bytes to all replicas first, along a chain picked to keep each hop on the "closest" unfilled machine in the network topology, and only afterward sends a small control message telling the primary to assign a serial number and apply the write1. This lets GFS fully utilize each machine's outbound bandwidth by pipelining the transfer over TCP rather than fanning the same bytes out from one sender to three receivers. Second, the primary is not asked to do anything at all until every replica has already acknowledged receiving the data — it only assigns order and applies locally, then forwards the write request (not the data, which already arrived) to the secondaries.
- Lease query. The client asks the master which chunkserver holds the current lease for the chunk and where the other replicas are.
- Lease grant returned. The master replies with the primary's identity and the secondaries' locations; the client caches this.
- Data pushed, control deferred. The client pushes the write's data to all replicas along a pipelined chain, independent of which one is primary; each chunkserver buffers it in an LRU cache.
- Write request. Once every replica has acknowledged the data, the client sends the actual write request to the primary only.
- Serial order assigned and forwarded. The primary assigns a serial number to this and any other concurrently buffered mutations, applies it locally, then forwards the write (not the data) to all secondaries.
- Secondaries apply in that order. Each secondary applies mutations in the exact serial-number order the primary assigned, then acknowledges.
- Reply. The primary replies to the client. If any replica reports an error, the client retries steps 3–7; a failure is never allowed to leave the chunk silently inconsistent without the client's knowledge1.
2.2 What a lease buys over an indefinite lock
A lease is a lock with a clock attached, and the clock is what makes it cheap to administer at scale. GFS's lease "has an initial timeout of 60 seconds. However, as long as the chunk is being mutated, the primary can request and typically receive extensions from the master indefinitely. These extension requests and grants are piggybacked on the HeartBeat messages regularly exchanged between the master and all chunkservers"1. Three consequences follow directly from that sentence. First, the master does not need a dedicated RPC to keep a lease alive — the piggyback on an already-scheduled heartbeat means lease renewal costs essentially nothing extra on the wire. Second, because a lease has a bounded lifetime rather than being held until explicitly released, the master can always safely grant a new lease to a different replica once the old one's 60 seconds run out, even if it has completely lost contact with the old primary — a lock with no expiry would force the master to either wait indefinitely for a graceful release or risk two primaries disagreeing about serial order at once. Third, "the master may sometimes try to revoke a lease before it expires (e.g., when the master wants to disable mutations on a file that is being renamed)... even if the master loses communication with a primary, it can safely grant a new lease to another replica after the old lease expires"1. This is a direct, load-bearing instance of the time-bounded-alternative-to-a-lock pattern that recurs throughout the systems in this course — Module 6 covers the same primitive again for Spanner's spanserver leader leases and Chubby.
2.3 Atomic record append: a partitioning-aware write primitive
GFS's ordinary write lets the client pick the offset; its record append operation, by contrast, lets the client specify only the data, and "GFS appends it to the file at least once atomically (i.e., as one continuous sequence of bytes) at an offset of GFS's choosing and returns that offset to the client"1. This exists because concurrent regular writes to the same byte range are not serializable — the region can end up with data fragments interleaved from multiple clients — whereas concurrent appends only need GFS to guarantee that each individual append lands somewhere as one unbroken unit, not that appends land in a particular relative order. This is precisely the primitive hundreds of concurrent producer processes need when merging results into one shared file or feeding one shared producer-consumer queue without a separate distributed lock manager1. Note the price: append is "at-least-once," so GFS may insert padding and duplicate a record on retry after a failed mutation, and it is the application's job — using embedded checksums and unique record identifiers — to detect and skip duplicates on read1. Module 7 revisits record append at the file-system layer in more detail (it is that module's, not this one's, main GFS topic); here the relevant point is narrower: record append is what "the partition's owner picks a serial position for you" looks like when the client cannot know the position in advance because other writers are appending concurrently.
2.4 The arithmetic of replicating a write across the network
GFS's own paper gives a simple closed-form estimate for how long it takes to push a write of B bytes out to R replicas once the pipelined chain in Figure 2 (step 3) is running at full speed:
$$ t_{\text{ideal}} = \frac{B}{T} + R\,L $$where T is the per-machine network throughput and L is the one-hop network latency1. The first term is the time to push B bytes through one link at rate T; the second term accounts for the fact that the write has to hop through R machines in series (client → replica 1 → replica 2 → … ), and each hop adds one latency L before that machine can start forwarding. GFS states its own network links "are typically 100 Mbps (T) and L is far below 1 ms"1, so for a 1 MB write to 3 replicas:
$$ t_{\text{ideal}} = \frac{1\text{ MB}}{100\text{ Mbps}} + 3 \times (<1\text{ ms}) \approx 80\text{ ms} + \text{(well under 3 ms)} \approx 80\text{ ms} $$which matches the paper's own stated result exactly: "1 MB can ideally be distributed in about 80 ms"1. The instructive part of this arithmetic is which term dominates: at 100 Mbps, moving the bytes themselves (the B/T term, roughly 80 ms for 1 MB) costs roughly 25–80× more than the added round-trip latency of chaining through three machines instead of one (RL, well under 3 ms total). That is why GFS bothers to pipeline the transfer along a chain sized to the network topology rather than worrying about the extra hop count from a star topology to a chain — bandwidth, not hop latency, is the binding constraint on a 100 Mbps commodity network, and the design optimizes accordingly.
3. Quorum-based replication and partitioning: Dynamo
Dynamo is Amazon's key-value store built for services — the shopping cart is the paper's running example — that "require that they can always write to and read from its data store, and that its data needs to be available across multiple data centers"3. Rather than a single primary per shard, Dynamo makes every one of a key's N replicas potentially able to accept a write, and resolves whatever conflicts that creates after the fact. Amazon's own justification is explicit: "Dynamo targets the design space of an 'always writeable' data store... experience at Amazon has shown that data stores that provide ACID guarantees tend to have poor availability"3. This is the module's other pole from GFS's leased primary, and Section 5's disagreement treats the trade-off directly.
3.1 N, R, W, and the quorum condition
Every key in Dynamo is configured with three small integers: N, the number of nodes that replicate it; R, the minimum number of nodes that must respond to a get() for it to succeed; and W, the minimum number of nodes that must respond to a put() for it to succeed3. The paper is direct about the consequence of that knob: "setting R and W such that R + W > N yields a quorum-like system... the latency of a get (or put) operation is dictated by the slowest of the R (or W) replicas. For this reason, R and W are usually configured to be less than N, to provide better latency"3. Why does R + W > N matter specifically, rather than just "R and W are both large"? Because it is exactly the condition that forces every read quorum to overlap every write quorum by at least one node — the general result behind the paper's quorum-like claim.
Take any set of N replicas. A write quorum is some subset of size W; a read quorum is some subset of size R. If the two subsets were disjoint, together they would use at most N distinct nodes, so:
$$ W + R \le N \quad \text{(if disjoint)} $$Contrapositive: if W + R > N, the two subsets cannot be disjoint — they must share at least
$$ \text{overlap} \ge W + R - N $$nodes. For Dynamo's own worked example of N = 33 with W = 2 and R = 2: W + R − N = 2 + 2 − 3 = 1, so any write quorum and any read quorum are guaranteed to share at least one node — the node that has the latest acknowledged write is always one of the nodes a subsequent read consults. This is the entire mechanical content of "quorum consistency": it does not require a leader, only arithmetic on set sizes. It also explains why W = 1 is dangerous for durability but attractive for availability: "applications that need the highest level of availability can set W to 1, which ensures that a write is accepted as long as a single node in the system has durably written the key to its local store"3 — but with W = 1 and R = 1 against N = 3, W + R − N = −1, so overlap is no longer guaranteed at all, and a read can miss the one node that has the newest value.
- Request arrives. The client's
put()reaches the coordinator — the first reachable node among the top N = 3 nodes on the key's preference list (Section 3.2). - Coordinator writes locally and stamps a version. It generates a new vector-clock entry for itself, e.g.
[(Sx,5)], and commits the value locally — this is the coordinator's own contribution toward W. - Fan-out to the remaining replicas. The coordinator sends the value and its vector clock to the other N − 1 = 2 nodes in the preference list, in parallel, over the network's own topology (no forced chain, unlike GFS's pipelined push).
- Return once W acks are in. With W = 2, the coordinator's own local write plus the first remote acknowledgment (N2, here) already satisfy the quorum; it replies success to the client immediately. N3's acknowledgment is not on the critical path — it still applies the write, just after the client has already moved on3.
put() with N = 3, W = 2: the coordinator's local write plus one remote acknowledgment is sufficient to return success, and every version carries an explicit vector-clock tag rather than a single serial number3.3.2 Consistent hashing with virtual nodes
Dynamo needs an answer to "which node is responsible for key k" that survives nodes joining and leaving without reshuffling the whole key space, and it gets one from consistent hashing: "the output range of a hash function is treated as a fixed circular space or 'ring'... each node in the system is assigned a random value within this space which represents its position on the ring. Each data item identified by a key is assigned to a node by hashing the data item's key to yield its position on the ring, and then walking the ring clockwise to find the first node with a position larger than the item's position"3. The principled advantage over, say, hashing a key modulo the current node count is exactly the incremental-scalability property: "the principle advantage of consistent hashing is that departure or arrival of a node only affects its immediate neighbors [on the ring]; other nodes remain unaffected"3.
The basic version of the scheme has two real problems in production, and Dynamo names both plainly: "the random position assignment of each node on the ring leads to non-uniform data and load distribution [and it] is oblivious to the heterogeneity in the performance of nodes"3. Its fix is virtual nodes: "instead of mapping a node to a single point in the circle, each node gets assigned to multiple points in the ring... Effectively, when a new node is added to the system, it is assigned multiple positions (henceforth, 'tokens') in the ring"3. A physical machine's capacity is now expressed as a token count rather than as a fixed share of the ring, which buys three things at once: uneven load from a departed or failed node "is evenly dispersed across the remaining available nodes"; a newly joined node "accepts a roughly equivalent amount of load from each of the other available nodes"; and a more powerful physical machine can simply be assigned more tokens than a weaker one3.
One more piece of vocabulary matters for the rest of this module: the preference list, "the list of nodes that is responsible for storing a particular key"3. Because virtual nodes can put more than one of a physical machine's tokens among a key's first N ring successors, Dynamo constructs the preference list by "skipping positions in the ring to ensure that the list contains only distinct physical nodes"3 — the coordinator in Figure 3 is simply the first reachable node on this list.
3.3 Vector clocks: tracking concurrent writes without a single winner
A leaderless, always-writeable store cannot use "whoever the leader accepted last" as its notion of the newest version, because there is no leader. Dynamo instead tags every version of an object with a vector clock: "a list of (node, counter) pairs... one can determine whether two versions of an object are on parallel branches or have a causal ordering, by examining their vector clocks. If the counters on the first object's clock are less-than-or-equal to all of the nodes in the second clock, then the first is an ancestor of the second and can be forgotten. Otherwise, the two changes are considered to be in conflict and require reconciliation"3.
The paper's own example is worth tracing exactly because it shows both cases — clean succession and real conflict — with the same object: a client writes an object handled by node Sx, producing D1([Sx,1]); the same node handles an update, producing D2([Sx,2]), which descends cleanly from D1. Now two different servers each handle a subsequent update to D2 without seeing each other's write — node Sy produces D3([Sx,2],[Sy,1]) and node Sz produces D4([Sx,2],[Sz,1]). Neither clock dominates the other, so a read returns both D3 and D4 as unreconciled siblings; the client (or the application's own merge logic, e.g. "union the cart contents") reconciles them, and node Sx writes back the merged result as D5([Sx,3],[Sy,1],[Sz,1]), whose clock dominates both parents3. Because write coordination under failures may be handled by nodes outside the normal top-N preference list, vector clocks can otherwise grow without bound; Dynamo bounds this with a truncation scheme that drops the oldest (node, counter) pair once the clock exceeds a threshold of about ten pairs, at the cost of occasionally being unable to determine ancestry precisely — the paper reports this has not been a problem in production3.
3.4 Sloppy quorums, hinted handoff, and Merkle-tree anti-entropy
A strict quorum enforced against a fixed set of N nodes would make Dynamo unavailable exactly when one of those specific nodes is unreachable — precisely the failure mode Dynamo was built to survive. Its fix is to relax which nodes count: "all read and write operations are performed on the first N healthy nodes from the preference list, which may not always be the first N nodes encountered while walking the consistent hashing ring"3 — a sloppy quorum. If a node that would normally hold a replica is temporarily down, the write goes to the next healthy node in the list instead, tagged with a hint identifying the node it was meant for: "the replica sent to [the substitute] will have a hint in its metadata that suggests which node was the intended recipient... nodes that receive hinted replicas keep them in a separate local database that is scanned periodically. Upon detecting that [the original node] has recovered, [the substitute] will attempt to deliver the replica to [it]"3 — hinted handoff. This buys temporary-failure tolerance essentially for free; it says nothing about what happens if a node's local disk is lost permanently, hint and all.
For that case Dynamo runs an anti-entropy protocol using Merkle trees, independent of any single request's read/write path: "a Merkle tree is a hash tree where leaves are hashes of the values of individual keys. Parent nodes higher in the tree are hashes of their respective children... each branch of the tree can be checked independently without requiring nodes to download the entire tree or the entire data set... if the hash values of the root of two trees are equal, then the values of the leaf nodes in the tree are equal and the nodes require no synchronization. If not, it implies that the values of some replicas are different... the process continues until it reaches the leaves of the trees, at which point the hosts can identify the keys that are 'out of sync'"3. Each node keeps one Merkle tree per key range it hosts, so two replicas can compare a single root hash and, on mismatch, walk down only the branches that actually differ rather than transferring or re-hashing the whole range.
3.5 Gossip-based membership and failure detection
Dynamo deliberately avoids any centralized registry for who is currently in the ring: "membership and failure detection: gossip-based membership protocol and failure detection [preserves] symmetry and avoids having a centralized registry for storing membership and node liveness information"3. Ring membership changes (an administrator explicitly adding or removing a node) are themselves gossiped rather than pushed from one authority: "a gossip-based protocol propagates membership changes and maintains an eventually consistent view of membership. Each node contacts a peer chosen at random every second and the two nodes efficiently reconcile their persisted membership change histories"3. The same peer-to-peer exchange also carries a ring checksum so that a node can detect a divergent view of the token-to-node mapping without a separate protocol. This is a genuinely different answer to "how does the system learn who is up" than GFS's or Bigtable's: those systems route liveness through a single authority (the master, or Chubby) precisely because they already have one for other reasons; Dynamo has no such authority by design and would undermine its own decentralization goal by introducing one just for membership.
4. Range vs. hash partitioning, and who rebalances: Bigtable
Bigtable's data model is "a sparse, distributed, persistent multi-dimensional sorted map" indexed by (row:string, column:string, time:int64) → string2, and it is the sortedness — not the replication — that this section is about: "Bigtable maintains data in lexicographic order by row key. The row range for a table is dynamically partitioned. Each row range is called a tablet"2. This is range partitioning by construction: a tablet owns every row key between two boundaries, and rows that sort near each other end up on the same machine. Bigtable's own replication story, by contrast, is not really Bigtable's story at all — the tablet's data lives in immutable SSTable files on GFS, replicated exactly as Section 2 described, at whatever replication factor the underlying GFS namespace region is configured for2. Bigtable's actual engineering effort goes into range partitioning at the tablet layer, and into using Chubby (Module 6's topic) only to elect a single active master and to store bootstrap, schema, and ACL metadata2 — not into re-deriving replication.
4.1 Tablets, and why range partitioning is the right default for this workload
"A Bigtable cluster stores a number of tables. Each table consists of a set of tablets, and each tablet contains all data associated with a row range. Initially, each table consists of just one tablet. As a table grows, it is automatically split into multiple tablets, each approximately 100–200 MB in size by default"2. A tablet server "typically" manages somewhere between ten and a thousand tablets2, and read/write requests for a tablet's rows are handled entirely by that tablet's server: clients never route data through the master, so "the master is lightly loaded in practice" — its job is metadata and load balancing, not serving2.
The reason to choose range partitioning here rather than hashing the row key is the same reason GFS chose contiguous chunks over scattering a file's bytes: Bigtable's own examples (Webtable's reversed-domain row keys, timestamped versions of a page) are built around efficient scans over a lexicographic range — "clients can exploit this property... rows are ordered by row key" for co-locating related data2. A hash-partitioned Bigtable would destroy exactly the locality that makes those scans a single sequential read instead of N random reads scattered across the cluster.
4.2 Dynamic tablet splitting and reassignment
Bigtable's master does not decide when to split a tablet — the tablet server does, unilaterally, because it is the one that can see the tablet growing past its size threshold in real time: "the set of existing tablets only changes when a table is created or deleted, two existing tablets are merged... or an existing tablet is split into two smaller tablets. The master is able to keep track of these changes because it initiates all but the last. Tablet splits are treated specially since they are initiated by a tablet server. The tablet server commits the split by recording information for the new tablet in the METADATA table. When the split has committed, it notifies the master"2. If that notification is lost — because the tablet server or the master died — "the master detects the new tablet when it asks a tablet server to load the tablet that has now split. The tablet server will notify the master of the split, because the tablet entry it finds in the METADATA table will specify only a portion of the tablet that the master asked it to load"2 — the split is self-healing even if the direct notification never arrives, because the METADATA table itself is the durable record of ground truth, and the master eventually reconciles against it.
Finding a tablet at all requires locating it, and Bigtable does this with a three-level hierarchy "analogous to that of a B+-tree": a Chubby file points at the location of a special root tablet, which is never itself split and holds the location of every METADATA tablet, each of which in turn holds the locations of a set of user tablets2. "With a modest limit of 128 MB METADATA tablets, our three-level location scheme is sufficient to address 234 tablets (or 261 bytes in 128 MB tablets)"2 — roughly 1.8×1019 bytes of addressable data from a scheme whose first two levels a client keeps cached and rarely needs to re-walk: "if the client's cache is empty, the location algorithm requires three network round-trips... If the client's cache is stale, the location algorithm could take up to six round-trips"2.
METADATA table first and the master learns of it second, so the master's tablet-location hierarchy stays correct even if the direct notification is lost2.4.3 Range vs. hash partitioning: the trade-off
GFS/Bigtable's range partitioning and Dynamo's hash partitioning are not competing implementations of the same idea; they are the right answer to two different access patterns. Table 1 makes the trade-off explicit.
| Property | Range partitioning | Hash partitioning |
|---|---|---|
| Key locality | Preserved — adjacent keys land on the same partition | Destroyed on purpose — adjacent keys scatter across the ring |
| Efficient range scan | Yes — a scan over a row-key range touches a small, contiguous set of tablets2 | No — a range scan touches almost every node |
| Hot-key skew risk | Higher — a popular contiguous key range (e.g. sequential-timestamp keys) can overload one tablet | Lower — a hash spreads sequential or skewed keys uniformly |
| Rebalancing trigger | Size- or load-triggered split of one tablet, initiated by the tablet server itself2 | Membership-triggered: node join/leave reassigns only the ring's adjacent arcs3 |
| Rebalancing granularity | Per-tablet (~100–200 MB default), independently reassignable2 | Per-virtual-node token, evenly dispersed across remaining nodes3 |
| Who decides where a key lives | A lookup through a location hierarchy (Chubby file → root tablet → METADATA tablet)2 | A hash function, computed locally by any client with the ring's token map — zero-hop lookup3 |
| Representative system | Bigtable, HBase | Dynamo, Cassandra, DynamoDB |
Table 2 pulls the module's three systems into one place, replication and partitioning together, so the two axes from Figure 1 are visible as a single reference.
| Dimension | GFS | Bigtable | Dynamo |
|---|---|---|---|
| Unit of partitioning | 64 MB chunk1 | Tablet, ~100–200 MB, row-range2 | Ring position (virtual-node token)3 |
| Partitioning scheme | Sequential chunking of one file | Range (lexicographic row key)2 | Hash (consistent hashing)3 |
| Replication factor | 3 (default)1 | Inherited from GFS (default 3)1 | N, configured per instance3 |
| Who orders writes | Leased primary chunkserver1 | Single tablet server per tablet (no cross-replica ordering at this layer)2 | Any reachable node in the top-N preference list3 |
| Concurrent-write resolution | Serialized by primary; concurrent successes leave region "consistent but undefined"1 | Single-row atomic read-modify-write only, no cross-row transactions2 | Vector clocks; application/client reconciles siblings3 |
| Rebalancing unit | Chunk migration between chunkservers, master-directed1 | Tablet split (server-initiated) or master-directed load balancing2 | Ring token reassignment on membership change3 |
| Membership authority | Single master | Chubby (5-replica Paxos lock service)2 | Gossip, no central authority3 |
The pattern in Table 2's "who orders writes" row is the module's central claim in condensed form: GFS and Bigtable both put exactly one machine in charge of ordering writes to a given slice of data — a leased primary chunkserver, or a single tablet server for reads and writes to that tablet's rows — while Dynamo lets any of a key's top-N replicas coordinate, and pays for that flexibility with vector clocks and application-level reconciliation instead of a total write order. Neither answer is more "correct" in the abstract; Section 5 makes the trade-off explicit.
Where experts disagree
Every design choice in this module ultimately serves one of two philosophies about what a storage system should sacrifice first when a network partition, a slow disk, or a datacenter failure forces a choice. Bigtable and Dynamo are not just two systems with two different partitioning schemes; they are the two camps' flagship examples, and Google itself later built a third system, Spanner, specifically to leave Bigtable's camp for the other one. Module 5 formalizes this as PACELC and Module 39 revisits it as a still-open frontier question; here it is worth stating in full at the mechanism level this module has actually built.
Pay the latency cost for synchronous, strongly-consistent replication
Google's Spanner team, built as Bigtable's explicit successor for exactly this reason5
Bigtable's own designers report that despite its popularity, "we have also consistently received complaints from users that Bigtable can be difficult to use for some kinds of applications: those that have complex, evolving schemas, or those that want strong consistency in the presence of wide-area replication... many applications at Google have chosen to use Megastore because of its semi-relational data model and support for synchronous replication, despite its relatively poor write throughput"5. Spanner's answer is to run two-phase commit over many Paxos-replicated groups and use the TrueTime API to assign globally meaningful, externally-consistent commit timestamps, accepting real latency (commit-wait bounded by clock uncertainty, and cross-datacenter round trips for the commit protocol) in exchange for transactions that behave exactly like a single-machine database's, at global scale5. Bigtable's own single-row-only transaction model — "Bigtable does not currently support general transactions across row keys"2 — is precisely the limitation this position rejects as too weak once an application's correctness depends on more than one row.
- Application code does not need to reason about conflicting versions, reconciliation logic, or read-repair; the database enforces one global order.
- Cross-row and cross-datacenter invariants (a ledger balance, a unique username) are enforceable directly rather than through eventual convergence.
- Commit latency is bounded below by real network round trips across Paxos groups and by TrueTime's clock-uncertainty commit-wait, which cannot be hidden behind a cache the way a single-node latency can.
- A partitioned minority of replicas becomes unavailable for both reads and writes on that data until quorum is restored — the system chooses consistency over availability during a partition by construction.
Never reject a write; always be available
Amazon's Dynamo team, building for shopping-cart-class services that must accept writes through any failure3
Dynamo's designers reach the opposite conclusion from the same industry experience: "experience at Amazon has shown that data stores that provide ACID guarantees tend to have poor availability. This has been widely acknowledged by both the industry and academia"3. Dynamo is explicitly "always writeable" — a write is accepted as long as a single reachable node can durably store it, sloppy quorums and hinted handoff route around any unreachable replica rather than blocking, and the cost of that availability is paid later, by the application, in the form of vector-clock conflicts it must reconcile on read3. The justification is business-specific and explicit in the paper: for a shopping cart, "an add-to-cart operation can never be forgotten or rejected," and losing a customer's cart update is a worse outcome than momentarily serving a stale or divergent one3.
- Write availability survives node failures, network partitions, and even whole-datacenter outages, because no quorum of any fixed set of nodes is required to be reachable.
- Read and write latency stay low and predictable — R and W are deliberately configured below N specifically to avoid waiting on the slowest replica3.
- Concurrent writes to the same key can produce real, application-visible divergent versions that something — the client or a merge function — must reconcile; this is not a corner case but Dynamo's normal operating mode under contention or partition.
- There is no built-in cross-key transaction of any kind; every invariant spanning more than one key is the application's problem, not the store's.
Both positions are correct descriptions of what they optimize for, and the right choice is a property of the workload, not a universal ranking. For state where a merge function is a legitimate answer to "what happens when two writers disagree" — carts, session data, view counters, presence — Dynamo's model wins outright: the availability it buys is real, the reconciliation cost is bounded and well understood (vector clocks plus a small, ten-pair truncation bound3), and paying two-phase-commit latency for every write of this kind would be a strictly worse trade. For state where two writers disagreeing is not a mergeable event — a funds transfer, a seat allocation, a unique-username registration — Spanner's model wins outright, because the "reconciliation" a Dynamo-style store would produce (present both versions to the application) is not a coherent answer for a debit that must not be double-spent. Google's own trajectory through this course's sources is itself evidence for the assessment rather than against it: Bigtable shipped first with the weaker, cheaper model, real application teams hit the limits documented in the Spanner paper's own introduction5, and only then did Google build Spanner — the industry converged toward "use the strong, expensive model specifically where the workload needs it" rather than toward either extreme being globally correct. What would settle any residual argument is not more benchmarks of either system in isolation, but a workload-by-workload audit of which invariants an application actually enforces versus which ones it silently pushes to an eventual, out-of-band repair step it doesn't call reconciliation — Section 4's finding that Bigtable itself delegates its replication story to GFS rather than reinventing it is a reminder that most systems are honest hybrids, not pure instances of either camp.
What is changing
The three mechanisms in this module — GFS's lease, Dynamo's ring and vector clocks, Bigtable's tablet split — are each two decades old 123, and the field's own reference textbook is itself mid-revision: the second edition of Designing Data-Intensive Applications, published February 2026, restructures the replication and partitioning material that the first edition (2017) had already made canonical, reflecting continued movement toward letting an operator configure consistency and partitioning strategy per table or per region rather than picking one dogmatic answer for an entire system4. What has not changed is the vocabulary: every modern system that offers a per-key or per-table consistency knob is still describing that knob in terms of leader-based versus quorum-based replication and range versus hash partitioning, the same two independent axes Figure 1 opened with.
References
- paperGhemawat, S., Gobioff, H., Leung, S-T. The Google File System. SOSP '03, 2003. https://research.google.com/archive/gfs-sosp2003.pdf. Accessed 2026-09-17. Used for: single-master architecture, 64 MB chunk size and metadata budget (§2.5–2.6), lease-based mutation ordering and write control/data flow (§3.1–3.2, Fig. 1–2), atomic record append (§3.3), and the B/T + RL transfer-time arithmetic (§3.2).
- paperChang, F., Dean, J., Ghemawat, S., et al. Bigtable: A Distributed Storage System for Structured Data. OSDI '06, 2006. https://www.usenix.org/legacy/event/osdi06/tech/chang/chang.pdf. Accessed 2026-09-17. Used for: the (row, column, timestamp) data model (§2), tablet definition and default 100–200 MB split size (§5, §5.1), tablet-server-initiated splitting and METADATA-table commit (§5.2), the three-level tablet-location hierarchy and 2^34-tablet addressing arithmetic (§5.1), Chubby's role and single-row-only transactions (§3–4).
- paperDeCandia, G., Hastorun, D., Jampani, M., et al. Dynamo: Amazon's Highly Available Key-value Store. SOSP '07, 2007. https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf. Accessed 2026-09-17. Used for: the always-writeable design goal (§2.3), N/R/W quorum configuration (§2.3, §4.5), consistent hashing and virtual nodes/tokens (§4.2, Fig. 2), preference lists, vector clocks and the D1–D5 reconciliation example (§4.4, Fig. 3), sloppy quorum and hinted handoff (§4.6), Merkle-tree anti-entropy (§4.7), and gossip-based membership (§4.8).
- textbookKleppmann, M., Riccomini, C. Designing Data-Intensive Applications. 2nd ed., O'Reilly Media, 2026. https://www.oreilly.com/library/view/designing-data-intensive-applications/9781098119058/. Accessed 2026-09-17. Used for: the general framing of replication and partitioning as two independent decisions, and the leader-based/leaderless and range/hash partitioning vocabulary (chapter numbers not cited directly — 2nd-edition table of contents was not accessible for confirmation at time of writing).
- paperCorbett, J.C., Dean, J., Epstein, M., et al. Spanner: Google's Globally-Distributed Database. OSDI '12, 2012. https://research.google.com/archive/spanner-osdi2012.pdf. Accessed 2026-09-17. Used for: the "Where experts disagree" section only — Spanner's own account of application-team complaints about Bigtable's consistency model and Megastore's synchronous-replication trade-off (§1).