System Design · Module 4

Transactions, Indexes, and the Relational/NoSQL Split

A transaction's isolation level decides which of another transaction's half-finished writes you are allowed to see; an index decides whether reading one row costs a lookup or a scan; a data model decides whether "one write" means one row, one versioned cell, or one opaque blob. This module derives all three from the papers that made the canonical, opposite choices — Bigtable and Spanner keeping general transactions and Dynamo deliberately throwing them away — so that after it, "ACID" or "eventually consistent" on a product page tells you exactly which guarantee was kept and which was traded for availability.

Course 35 min read 7 sources As of 2026-09-17 Prerequisite: Module 3
One write, four independent questions this module answers WRITE (key, value) Isolation level which concurrent writes can this transaction see? (§2) Commit protocol how does it become durable on every machine at once? (§3) Index structure does a later read cost a lookup or a scan? (§4) Data model what shape does the stored record take? (§5, §6)
Figure 1. The same write raises four independent design questions this module answers in order. Bigtable3 and Spanner6 answer all four by keeping general transactions and a strict isolation guarantee; Dynamo7 answers all four by rejecting general transactions and strict isolation in exchange for availability.

1. ACID: what each guarantee actually constrains

"ACID (Atomicity, Consistency, Isolation, Durability) is a set of properties that guarantee that database transactions are processed reliably"7 — that is Amazon's own one-line gloss, from the paper that goes on to reject three of the four letters for its own key-value store. The acronym is old and the individual letters are unevenly interesting to an engineer who already reasons about consistency across GPUs and KV caches for a living.

Atomicity means a transaction's writes either all happen or none do; there is no state in which a caller can observe half of a multi-key update. Durability means that once a transaction is acknowledged as committed, it survives a crash — normally by fsyncing a write-ahead log before acknowledging. Neither of these is where systems disagree: every system in this module, including Dynamo, gives you atomicity and durability for whatever unit of write it accepts. Consistency, in the ACID sense, is the weakest letter of the four — it just means the database will not let a transaction leave application-level invariants (foreign keys, uniqueness constraints) violated, which is a property of the schema and the transaction logic, not something a storage engine implements on its own.

Isolation is where all of the real engineering, and all of the real disagreement, lives. It answers one question: while transaction A is in progress, what is transaction B allowed to see of A's uncommitted or concurrently-committing state? The strongest possible answer — serializability, meaning the system behaves as if every transaction ran alone, one after another, in some order — is expensive to implement and expensive to run. Every isolation level weaker than serializable is a deliberate, named trade of some of that guarantee for throughput or latency, and the entire relational-versus-NoSQL argument in this module's "Where experts disagree" section is really an argument about how much of that trade is worth making and where.

2. The isolation-level ladder

Database vendors have offered isolation levels weaker than full serializability since at least the 1995 ANSI SQL-92 standard, and the standard's own definitions turned out to be broken. The paper that fixed them — Berenson, Bernstein, Gray, Melton, and the O'Neils, writing while at Microsoft, Sybase, and UMass Boston — showed that the ANSI phenomena "fail to characterize several popular isolation levels, including the standard locking implementations of the levels," and introduced a fourth phenomenon (dirty write) plus a new isolation type, snapshot isolation, that the standard did not anticipate at all1. That 1995 taxonomy is still the one every mainstream database documents its isolation levels against, including PostgreSQL's own manual today2, so it is the right place to start rather than treating "read committed" and "serializable" as folklore terms.

2.1 The four phenomena an isolation level can forbid

The paper defines phenomena as action subsequences across two transactions T1 and T2, written in a shorthand where w1[x] means "T1 writes x," c1 means "T1 commits," and a1 means "T1 aborts"1:

  • P0 — Dirty write. T1 modifies x; T2 modifies x again before T1 commits or aborts. If either rolls back, it is unclear which value is correct1.
  • P1 — Dirty read. T1 modifies x; T2 reads that same x before T1 commits or aborts, so T2 may read a value that never actually existed once T1 rolls back1.
  • P2 — Fuzzy (non-repeatable) read. T1 reads x; T2 modifies or deletes x and commits; if T1 rereads x it gets a different, or missing, value1.
  • P3 — Phantom. T1 reads a set of rows matching a predicate; T2 inserts or updates a row that now also matches, and commits; T1's repeated query returns a different set1.

Dirty writes (P0) are forbidden at every isolation level any serious database ships — allowing them would mean two uncommitted transactions could interleave writes to the same row and leave a value nobody actually wrote — so P0 is really a floor rather than a distinguishing feature1. The three levels this module's figure puts on a ladder differ in which of P1, P2, and P3 they still allow, plus a fifth phenomenon the 1995 paper had to invent to describe the level in the middle.

2.2 Read committed, snapshot isolation, serializable

Read committed is the weakest level anyone still uses in production; it forbids P0 and P1 (you never see another transaction's uncommitted writes) but allows P2 and P3. PostgreSQL, where read committed is the default, states this precisely: "a SELECT query... sees only data committed before the query began; it never sees either uncommitted data or changes committed by concurrent transactions during the query's execution"2 — but that promise is re-evaluated every single statement, not once per transaction, which is exactly why two SELECTs five milliseconds apart in the same transaction can return different rows for the same predicate.

Snapshot isolation is the interesting middle rung, and it is not one of the four ANSI levels at all — it is the isolation type the 1995 paper defined specifically because several real systems (Oracle among them) were shipping something the ANSI phenomena could not describe1. Under snapshot isolation, "each transaction reads data from a snapshot of the (committed) data as of the time the transaction started, called its Start-Timestamp... A transaction running in Snapshot Isolation is never blocked attempting a read"1. On commit, the transaction is assigned a Commit-Timestamp and succeeds only if no other transaction with a commit timestamp inside its own execution interval wrote any of the same data — a rule the paper calls first-committer-wins, and which is exactly what eliminates the lost-update phenomenon (P4)1. PostgreSQL implements its REPEATABLE READ level with this exact mechanism — "The Repeatable Read isolation level is implemented using a technique known in academic database literature... as Snapshot Isolation"2 — and surfaces first-committer-wins as an explicit client-visible error: ERROR: could not serialize access due to concurrent update2.

Serializable forbids everything: the system "emulates serial transaction execution for all committed transactions; as if transactions had been executed one after another, serially, rather than concurrently"1. PostgreSQL implements this with predicate locks that "determine when a write would have had an impact on the result of a previous read from a concurrent transaction, had it run first," aborting the offending transaction with ERROR: could not serialize access due to read/write dependencies among transactions2 rather than blocking it up front. The cost is real: every serializable transaction now carries the bookkeeping to detect these dependencies and a nonzero abort-and-retry rate under contention, which is the whole reason the two weaker rungs below it exist commercially.

2.3 The anomaly each rung still permits

The reason snapshot isolation is genuinely dangerous rather than merely "a bit weaker than serializable" is write skew, a fifth phenomenon the same authors had to add later to describe it: "Suppose T1 reads x and y, which are consistent with a constraint C(), and then T2 reads x and y, writes x, and commits. Then T1 writes y. If there were a constraint between x and y, it might be violated"1. Concretely: two doctors on call for the same ward each independently check "is at least one of us still on call?", both see "yes, the other one is," and both remove themselves — the invariant ("at least one doctor on call") is violated even though neither transaction ever wrote a row the other one wrote. Snapshot isolation cannot see this, because P2 requires a shared write and A5B does not involve one: "Clearly neither A5A nor A5B could arise in histories where P2 is precluded, since both A5A and A5B have T2 write a data item that has been previously read by an uncommitted T1"1 — write skew reads two rows and writes only one each, so no dirty-write detection ever fires. The two isolation levels are formally incomparable: "REPEATABLE READ »« Snapshot Isolation"1 — snapshot isolation forbids phantoms (P3) that PostgreSQL's REPEATABLE READ still allows in the ANSI sense, but permits write skew that a lock-based REPEATABLE READ does not.

Isolation-level ladder from read committed to serializable, with the anomaly each rung still permits increasing isolation strength, increasing coordination cost → Read committed re-checks committed data every statement Snapshot isolation one snapshot for the whole transaction Serializable behaves as if transactions ran one at a time still allows: fuzzy read, phantom, write skew still allows: write skew (A5B) allows: nothing
Figure 2. The three rungs, each defined by which of P1–P3 and write skew it still permits, per the ANSI-critique paper's own phenomena and PostgreSQL's implementation of them12. Snapshot isolation sits strictly above read committed on some axes but is incomparable with lock-based repeatable read on phantoms1.
Table 1. Which anomalies each isolation level still permits, by the ANSI-critique paper's phenomena (broad interpretation) and PostgreSQL's documented behavior12.
Isolation levelDirty write (P0)Dirty read (P1)Fuzzy/non-repeatable read (P2)Phantom (P3)Lost update (P4)Write skew (A5B)
Read committedNot possibleNot possiblePossiblePossiblePossiblePossible
Snapshot isolationNot possibleNot possibleNot possibleNot possibleNot possiblePossible
SerializableNot possibleNot possibleNot possibleNot possibleNot possibleNot possible

Lost update (P4) is the case where "T1 reads a data item and then T2 updates the data item (possibly based on a previous read), then T1 (based on its earlier read value) updates the data item and commits" — T2's update is silently overwritten and disappears even though T2 committed cleanly1. Read committed permits it outright. Snapshot isolation eliminates it as a side effect of first-committer-wins, not as a separately implemented check: "forbidding P2 also precludes P4, since w2[x] comes after r1[x] and before T1 commits or aborts"1 — which is exactly why P4 is a useful anomaly for telling read committed and snapshot isolation apart even though neither the ANSI standard nor a casual reading of "isolation levels" would predict that a single mechanism (blocking a second writer to an already-read row) closes two named anomalies (P4 and, separately, most instances of P2) at once.

2.4 What the levels look like as actual locks

Read committed and serializable are not just abstract permission tables — most production databases implement them as concrete lock durations, and the ANSI-critique paper tabulates exactly which locks: read committed takes well-formed write locks of long duration plus read locks of only short duration (released immediately after each statement), while serializable adds long-duration read locks and long-duration read predicate locks, held until commit, which is what makes it able to detect a phantom insert that would have matched an earlier query's predicate1. The paper also names the level PostgreSQL's serializable sits directly below: cursor stability, which "extends READ COMMITTED locking behavior for SQL cursors by adding a new read action for FETCH... requiring that a lock be held on the current item of the cursor," specifically to close the lost-update case for whichever single row a cursor currently points at, without paying for full repeatable-read locking on every row a transaction touches1. Locking is not the only implementation strategy — PostgreSQL's serializable level uses predicate tracking (Serializable Snapshot Isolation) rather than predicate locking in the classical sense2 — but the lock-duration framing is still the fastest way to build intuition for why stronger levels cost more: every level up the ladder either holds a lock longer or widens what it locks from an item to a predicate.

3. Two-phase commit: making a distributed write atomic

Isolation answers what one machine shows to concurrent readers. Two-phase commit (2PC) answers a completely different question: when a single transaction touches data on N different machines, how do all N agree on commit or abort as one atomic unit, given that any of them can crash mid-transaction? Gray and Lamport's 2004 Microsoft Research paper — later published in ACM Transactions on Database Systems — gives the cleanest formal treatment of both the classic protocol and its limitation5.

3.1 The protocol and its cost

Each participant, called a resource manager (RM), moves through four states: working, prepared, committed, aborted. The protocol's two safety requirements are simple to state: "it is impossible for one RM to be in the committed state and another to be in the aborted state," and "an RM can enter the committed state only after all RMs have been in the prepared state"5. A transaction manager (TM) coordinates: an RM that wants to commit enters prepared and tells the TM; once the TM has heard prepared from every RM, it enters committed itself and tells everyone to commit5.

The cost is countable exactly. For N resource managers, the failure-free path is: the initiating RM sends Prepared to the TM (1 message); the TM sends Prepare to the other N−1 RMs (N−1 messages); each replies Prepared (N−1 messages); the TM sends Commit to all N (N messages). "Thus, in the normal case, the RMs learn that the transaction has been committed after four message delays. A total of 3N−1 messages are sent"5. If the TM is co-located with the initiating RM, as is typical, two of those messages are free and the count drops to 3N−3 over three message delays5. Messages are not the only cost: "the two-phase commit protocol incurs the delays associated with writes to stable storage: the write by the first RM to prepare, the writes by the remaining RMs when they prepare, and the write by the TM when it makes the commit decision. This can be reduced to two write delays by having all RMs prepare concurrently"5 — every one of those writes is an fsync-class durability barrier, which is why 2PC's real latency floor is normally the stable-storage write path, not the network round trip.

Table 2. Two-phase commit's message and delay cost as a function of participant count N, from the protocol's own accounting5.
Participants (N)Messages (3N−1)Messages, TM co-located (3N−3)Message delays
3864 (3 co-located)
514124 (3 co-located)
1029274 (3 co-located)
Two-phase commit sequence diagram: coordinator against three resource managers, failure-free case TM (coordinator) RM1 RM2 RM3 Prepared (RM1 entered prepared) Prepare Prepared (from RM2, RM3) if TM fails here: all RMs are "prepared" but none knows commit or abort — blocked Commit (only once TM heard Prepared from all) 4 delays, 3N−1 msgs
Figure 3. The failure-free sequence for N=3: RM1 volunteers Prepared, the TM asks the rest to prepare, and only after every RM has replied Prepared does the TM broadcast Commit. The shaded band marks the protocol's one structural weakness, described next5.

3.2 The blocking problem

Two-phase commit's failure mode is exact and unavoidable within the protocol as stated: "if the TM fails right after every RM has sent a Prepared message, then the other RMs have no way of knowing whether the TM committed or aborted the transaction"5. Every RM is holding locks on its own share of the data, cannot unilaterally decide to abort (another RM's peer might have already been told to commit), and cannot decide to commit either — so it blocks until an operator manually restarts or reroutes the coordinator. Gray and Lamport are explicit that ad hoc fixes ("three-phase commit" protocols that elect a new TM) have never been rigorously shown correct: "we know of none that provides a complete algorithm proven to satisfy a clearly stated correctness condition"5.

Their own fix, Paxos Commit, replaces the single TM with 2F+1 coordinators running Paxos consensus on each RM's commit/abort vote, making progress as long as F+1 of them are alive; classic 2PC is exactly the F=0 special case of that algorithm5. This is precisely the shape of Spanner's answer, described next: rather than trusting one fragile coordinator process, replicate the coordinator's decision itself via a consensus protocol.

3.3 Spanner: two-phase commit over Paxos groups, made externally consistent

Spanner runs a transaction across directories — buckets of contiguous keys — each replicated by its own Paxos group with a long-lived leader6. A multi-group read-write transaction is 2PC with every RM's log and every TM's log itself replicated by Paxos, which is what removes the single-point-of-failure coordinator that blocks classic 2PC: "it begins two-phase commit. The client chooses a coordinator group and sends a commit message to each participant's leader with the identity of the coordinator... A non-coordinator-participant leader first acquires write locks. It then chooses a prepare timestamp... and logs a prepare record through Paxos"6. Because that prepare record is itself Paxos-replicated, losing the leader of a participant group does not lose the fact that it prepared — a new leader in the same Paxos group can be elected and continue.

Spanner adds one more thing 2PC alone does not give you: an externally-consistent commit timestamp, using the TrueTime API's bounded clock uncertainty. "The coordinator leader ensures that clients cannot see any data committed by Ti until TT.after(si) is true," where si is the chosen commit timestamp — a rule called commit wait6. Because TrueTime keeps clock uncertainty "generally less than 10ms" globally6, commit wait typically costs on the order of twice that uncertainty and overlaps with the Paxos communication the commit already needs, so in practice it adds little beyond the consensus round trip already paid6. Read-write transactions also use wound-wait locking at each participant leader to avoid deadlock among concurrent transactions competing for the same rows6. The result is a system that gives every multi-row, multi-datacenter transaction the same serializable, externally-consistent guarantee a single-machine relational database gives a single-row update — at the cost of a consensus round trip and a commit-wait stall on every write.

Spanner also has a lock-free path that ties directly back to §2: a read-only transaction is explicitly described as "a kind of transaction that has the performance benefits of snapshot isolation... reads in a read-only transaction execute at a system-chosen timestamp without locking, so that incoming writes are not blocked"6. Where read-write transactions pay two-phase commit and commit wait, read-only transactions simply pick a safe timestamp (the last committed write's timestamp, or the current TrueTime bound if reads span multiple Paxos groups) and read a consistent snapshot from any sufficiently up-to-date replica — the same underlying idea the ANSI-critique paper's snapshot isolation names, now made externally consistent by TrueTime rather than by a local start-timestamp16. General transactions also buy Spanner something Bigtable's schema changes cannot get: "Bigtable supports atomic schema changes in one datacenter, but its schema changes block all operations," whereas "a Spanner schema-change transaction is a generally non-blocking variant of a standard transaction... schema changes across thousands of servers can complete with minimal disruption to other concurrent activity"6 — a concrete case where paying for general transactions removes an operational limitation (blocking schema changes) that the weaker, single-row model cannot express a fix for at all.

4. Turning a scan into a lookup: B-tree vs LSM-tree

An index exists so that finding one row costs a lookup instead of a scan of everything. The two dominant on-disk shapes for that lookup structure — B-tree and log-structured merge-tree (LSM-tree) — differ in exactly one design decision: whether an update touches the existing on-disk page in place, or is deferred and later merged in from scratch.

4.1 The B-tree: in-place update, one random page per write

A B-tree stores one entry per indexed row in sorted order across fixed-size pages, with directory pages above pointing down to the leaf that holds a given key range. Updating an indexed row means reading the leaf page that currently holds (or should hold) that key, modifying it in place, and writing the whole page back — normally one random disk read plus one random disk write per insert, once the working set exceeds available buffer memory. The LSM-tree paper that motivates the alternative states the practical consequence bluntly: because B-tree updates are random and page-granular, "standard disk-based index structures such as the B-tree will effectively double the I/O cost of the transaction to maintain an index such as this in real time, increasing the total system cost up to fifty percent"4.

4.2 The LSM-tree: memtable, immutable segments, background merge

O'Neil, Cheng, Gawlick, and O'Neil's 1996 paper proposes deferring and batching index changes instead. A two-component LSM-tree keeps a small, entirely memory-resident tree, C0, and a much larger disk-resident tree, C1: "the memory resident C0 tree has no I/O cost... whenever the C0 tree as a result of an insert reaches a threshold size near the maximum allotted, an ongoing rolling merge process serves to delete some contiguous segment of entries from the C0 tree and merge it into the C1 tree on disk"4. The rolling merge always reads and writes multi-page blocks (256 KB blocks are the paper's own figure) rather than single random pages, and "new leaf nodes are written to a different... free area on disk," never overwriting the old blocks in place, which is where the "log-structured" half of the name comes from — it deliberately borrows the never-overwrite discipline of the Log-Structured File System4. Because merges move sequential multi-page blocks instead of one random page at a time, the same number of logical inserts costs vastly fewer disk-arm seeks.

4.3 Bigtable's concrete implementation: memtable, SSTables, three kinds of compaction

Bigtable is a direct, production implementation of the same idea, and its paper is precise about the mechanism where the LSM-tree paper is more abstract. Writes are committed to a per-tablet-server commit log first; "of these updates, the recently committed ones are stored in memory in a sorted buffer called a memtable; the older updates are stored in a sequence of SSTables"3. An SSTable is Bigtable's disk-resident, immutable, sorted file format, read in 64 KB blocks with an in-memory block index3. Bigtable names three distinct compactions rather than one generic merge:

  • Minor compaction. "When the memtable size reaches a threshold, the memtable is frozen, a new memtable is created, and the frozen memtable is converted to an SSTable and written to GFS. This... shrinks the memory usage of the tablet server, and... reduces the amount of data that has to be read from the commit log during recovery if this server dies"3.
  • Merging compaction. Because unchecked minor compactions would eventually require a read to merge an unbounded number of SSTables, Bigtable "periodically" merges "the contents of a few SSTables and the memtable, and writes out a new SSTable," bounding read fan-in3.
  • Major compaction. "A merging compaction that rewrites all SSTables into exactly one SSTable... produces an SSTable that contains no deletion information or deleted data," which is what actually reclaims space and physically erases deleted or overwritten data — important for services with a data-deletion obligation3.

Reads merge the memtable and every relevant SSTable on the fly, since both are already sorted3, which is the same principle the LSM-tree paper describes as searching C0 then C1 for an exact-match find4. Merging multiple SSTables per read is the LSM-tree's structural read-amplification tax on top of a B-tree's single-structure lookup, and Bigtable's paper is explicit about the mitigation: "a read operation has to read from all SSTables that make up the state of a tablet. If these SSTables are not in memory, we may end up doing many disk accesses. We reduce the number of accesses by allowing clients to specify that Bloom filters should be created for SSTables... Our use of Bloom filters also implies that most lookups for non-existent rows or columns do not need to touch disk"3 — a probabilistic, in-memory pre-check that turns "which of these k SSTables might contain this key" from k disk seeks into a handful of memory lookups plus, typically, one real seek for the SSTable that actually has the data.

B-tree in-place write path versus LSM-tree deferred write path B-tree Write(key, value) Write-ahead log (durability) random-access read leaf page(cache miss → 1 disk seek) modify in place, write page back(1 more disk seek) LSM-tree Write(key, value) Write-ahead / commit log memtable (memory, sorted)no I/O cost frozen → SSTable (minor compaction)background merge → new sequential file
Figure 4. B-tree updates cost one random read plus one random write per insert once the page is off the hot buffer path4. LSM-trees absorb the write in memory for free and defer the disk cost to a background, sequential merge — Bigtable's memtable/SSTable/compaction pipeline is exactly this mechanism34.
Worked derivation: why a secondary B-tree index doubled disk cost in the LSM-tree paper's own example

The LSM-tree paper motivates itself with a modified TPC-A benchmark: 1,000 transactions per second, each writing a 50-byte row to a fast-growing History table, with a secondary B-tree index on Account-ID‖Timestamp needed to answer recent-activity queries efficiently4.

Without the index, the base workload already needs about 2,000 I/Os per second (roughly one read plus one write per transaction against the Account table), which at the paper's assumed nominal rate of "about 40 I/Os per second" per disk arm requires 50 disk arms4:

$$ \frac{2000\ \text{I/Os/s}}{40\ \text{I/Os/s per arm}} = 50\ \text{disk arms} $$

Adding the secondary index changes this because "the entries in the B-tree are generated 1000 per second, and assuming a 20 day period of accumulation... 576,000,000 entries on 9.2 GBytes of disk, or about 2.3 million pages... Since transactional Acct-ID values are randomly chosen, each transaction will require at least one page read from this index and, in the steady state a page write as well"4 — because the index pages are far larger than memory and accessed at effectively random key values, none of them stay buffer-resident, so every transaction now costs one more random read and one more random write:

$$ 1000\ \text{TPS} \times 2\ \text{I/Os/transaction} = 2000\ \text{additional I/Os/s} \implies \frac{2000}{40} = 50\ \text{more disk arms} $$

"This addition of 2000 I/Os per second to the 2000 I/Os already needed for updating the Account table, requires a purchase of an additional 50 disk arms, doubling our disk requirements"4 — 50 arms becomes 100 arms, purely to keep one secondary index up to date in place. That doubling, not an abstract complexity argument, is the concrete economic case the LSM-tree — and by extension Bigtable's SSTable design — was built to eliminate.

5. Three shapes for the same byte: data models compared

Once you have picked an isolation level and an index structure, you still have to decide what a single stored record looks like. The three canonical answers in this course are the relational normalized row, Bigtable's versioned sparse map, and Dynamo's opaque blob.

5.1 The relational row: schema-enforced, normalized, joinable

A relational row is a fixed set of typed columns, enforced by a schema declared before any data is written; a row referencing another table's row does so via a foreign key, and the two rows are typically stored separately, to be recombined on read via a join. Normalization exists to avoid storing the same fact twice — an address lives in one place, referenced by every order that ships to it — at the cost of needing a join (or, in a distributed system, a cross-partition read) to reassemble a full picture.

5.2 Bigtable's (row, column, timestamp) sparse map

Bigtable's entire data model is one sentence: "A Bigtable is a sparse, distributed, persistent multidimensional sorted map. The map is indexed by a row key, column key, and a timestamp; each value in the map is an uninterpreted array of bytes... (row:string, column:string, time:int64) → string"3. Three consequences follow directly. First, rows are kept in lexicographic order and dynamically range-partitioned into tablets, so choosing row keys that sort the way you want to scan — Bigtable's own example reverses domain names so com.cnn.www sorts next to other cnn.com pages — is a first-class schema decision, not an afterthought3. Second, columns are grouped into column families, which must be declared ahead of time and are "the basic unit of access control," but "any column key within the family can be used" without pre-declaring it, and a table can have an effectively unbounded number of distinct column keys even though the number of families should stay small — "in the hundreds at most"3. A column key is written as family:qualifier (e.g., an anchor: family holding one column per distinct referring URL, the qualifier itself being data)3. Third, every cell holds multiple timestamped versions rather than one — Bigtable timestamps are 64-bit integers, assignable by the system as real time in microseconds or explicitly by the client, and per-column-family garbage-collection policy decides how many versions or how much time's worth to retain3. This is a schema for a table that is sparse (most row/column combinations simply do not exist) and versioned (a "cell" is really a small time series), which a fixed-width relational row cannot represent without a separate history table.

5.3 Dynamo's opaque blob behind a key

Dynamo goes the other direction entirely: "Dynamo targets applications that need to store objects that are relatively small (usually less than 1MB)"7 and gives every one of them the same interface — get(key) and put(key, context, object) — with no columns, no families, no schema of any kind visible to the store7. "State is stored as binary objects (i.e., blobs) identified by unique keys. No operations span multiple data items and there is no need for relational schema"7. Everything about the object's internal structure — which fields it has, how they are versioned, how two concurrently written versions get merged — is the application's problem, not the store's; Dynamo's own paper is explicit that this is a deliberate simplification driven by observing that "a significant portion of Amazon's services can work with this simple data model and do not need any relational schema"7.

Three data-model layouts side by side: relational table, Bigtable cell map, Dynamo key-value blob Relational row id | name | addr_id 7 | Aman | 42 addr_id | city 42 | ... fixed columns, join to related table Bigtable cell com.cnn.www contents: t6 contents: t5 contents: t3 anchor:cnnsi: t9 sparse cells, versioned by timestamp Dynamo key-value key: cart-9182 opaque blob< 1MB, no schema store never inspects the value
Figure 5. The same fact stored three ways: a normalized relational row that joins to a related table; a Bigtable cell addressed by (row, column, timestamp) with several live versions3; a Dynamo key mapped to one opaque, unversioned-by-the-store blob7.
Table 3. Data model comparison across the three canonical shapes37.
DimensionRelationalBigtableDynamo
Unit of storagetyped row across declared columnscell keyed by (row, column, timestamp)3opaque blob keyed by a single key7
Schemadeclared and enforced before writecolumn families declared; qualifiers free-form3none visible to the store7
Versioningnone built in (needs a history table)every cell holds N timestamped versions3none in the store; app must version if needed
Transaction scopearbitrary rows/tables (engine-dependent)single row only3single key only7
Typical value sizerow-sized (bytes-KB)cell-sized, compressed in locality groups3< 1 MB blob7
Canonical use caseinvariants across entities (ledgers, inventory)web index, time-series-like sparse data3shopping cart, session state7

6. Single-row atomicity vs. general transactions: the Dynamo bet

Bigtable and Dynamo both stop short of Spanner's fully general, cross-partition, serializable transaction — but they stop at different places, and the difference is the crux of this module's disagreement section.

Bigtable keeps single-row atomicity and nothing more: "Bigtable supports single-row transactions, which can be used to perform atomic read-modify-write sequences on data stored under a single row key. Bigtable does not currently support general transactions across row keys, although it provides an interface for batching writes across row keys at the clients"3. That single-row guarantee is not a compromise forced by scale; it is a direct consequence of the data model — because Bigtable already routes any operation touching one row key to exactly one tablet server, giving that operation full atomicity costs nothing extra in coordination. The batching interface is explicitly not the same guarantee: it lets a client send several row updates in one RPC, but each row's mutation is still independently atomic, not jointly atomic with the others.

Dynamo goes one full step further and refuses isolation guarantees altogether, by design rather than as an implementation gap: "Dynamo does not provide any isolation guarantees and permits only single key updates"7. There is no read-modify-write sequence exposed at all — a client reads a key's current version(s), computes a new value in the application, and writes it back, and if another client wrote concurrently, both versions are kept and handed to the next reader to reconcile (Module 3 already covers the vector-clock mechanics behind that reconciliation). This is the direct, load-bearing consequence of Dynamo's stated design target: "Dynamo targets the design space of an 'always writeable' data store (i.e., a data store that is highly available for writes)"7. A write is never rejected because of a concurrent write, a network partition, or a node failure — the price is that the store cannot promise you saw the latest value, or that no one else is writing at the same time as you.

Where experts disagree

Every system in this module had the option to build general, ACID, cross-key transactions and chose not to, except Spanner, which built them anyway at a specific, measured cost. That is not an accident of engineering taste — it reflects genuinely different priors about which failure is worse: a transaction that silently corrupts a cross-entity invariant, a write that gets rejected when a customer is trying to complete a purchase, or the cost of building and maintaining a layer above the storage engine to handle everything the engine itself declines to guarantee.

Keep general transactions and strict isolation

Spanner's design team6, and implicitly the entire relational-database tradition that the ANSI-SQL isolation critique1 and PostgreSQL's serializable implementation2 serve

Cross-entity invariants — double-entry bookkeeping, inventory counts, seat allocation — are exactly the class of bug that weak isolation lets through silently (write skew, phantom, lost update), and those bugs are far more expensive to find and fix after the fact than the latency cost of paying for real consensus and commit wait on every write. Spanner's own thesis is that at global scale, this is achievable: "the first system to distribute data at global scale and support externally-consistent distributed transactions"6.

  • Correctness by construction: the application never has to reason about which anomalies its isolation level still permits.
  • Proven to scale globally — Spanner shards across datacenters worldwide, not just one cluster6.
  • Simpler application code: no merge functions, no reconciliation logic, no vector clocks to interpret.
  • Every write pays a consensus round trip (Paxos) plus commit-wait, typically on the order of TrueTime's uncertainty bound6.
  • A write can be rejected or delayed if a participant Paxos group cannot reach a majority — availability is not unconditional.
  • 2PC over Paxos groups is a materially more complex implementation than a leaderless key-value store.

Reject general transactions and isolation, keep the store always writeable

Dynamo's design team at Amazon7, and the Dynamo-lineage systems (Cassandra, Riak, Voldemort, DynamoDB) that inherited its model

For the specific class of service Dynamo was built for, a rejected write is worse than a temporarily inconsistent read: "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"7. A shopping cart that refuses an add-to-cart during a network blip loses a sale outright; a shopping cart that accepts the write and merges two concurrent versions later loses nothing. Dynamo's own conflict-resolution discussion frames this explicitly as a choice about who resolves conflicts and when, favoring resolving them on read so that writes are never rejected7.

  • A write is never rejected for concurrency or partition reasons — availability is unconditional for writes7.
  • No coordinator, no consensus round trip, no single point of blocking on the write path.
  • Symmetric, decentralized design scales incrementally, one node at a time7.
  • No cross-key atomicity at all — an application that actually needs it (a ledger, an inventory count) gets no help from the store.
  • Conflict resolution (merge logic) becomes the application's permanent responsibility, not a one-time cost.
  • "No isolation guarantees" is easy to violate accidentally if an engineer assumes single-key semantics extend to a multi-key workflow.

Give every row free atomicity, solve nothing beyond it

Bigtable's design team3 — a pragmatic middle position between Spanner's and Dynamo's

Because every operation on a given row key is already routed to exactly one tablet server, making that operation atomic costs nothing extra in coordination — so Bigtable gives it away for free rather than treating it as a feature to price against availability3. But it stops there on principle, not on a roadmap: "Bigtable does not currently support general transactions across row keys"3, and the batching interface it does offer is explicitly not joint atomicity across rows. This is a bet that the single-row case is common enough (one web page's anchors, one user's session) to be worth optimizing for directly, while genuinely cross-entity invariants are rare enough, and hard enough to generalize correctly, to be left to a layer above (Megastore, then Spanner, at Google) rather than solved halfway inside the storage engine itself.

  • Atomicity that costs literally nothing, because it follows for free from the partitioning scheme already in place.
  • No consensus round trip, no commit-wait, no cross-partition coordination logic to get wrong.
  • Covers the empirically dominant case (one entity, one row) cleanly.
  • Punts every cross-entity invariant upward exactly like Dynamo does — it is a bigger atomic unit (one row's many columns) but the same shape of gap.
  • The batching interface is easy to mistake for cross-row atomicity when it provides none.
  • Applications that outgrow single-row atomicity have no in-storage escalation path; they must move to a different system (Megastore, Spanner) entirely.
Assessment

The right choice is a property of the invariant, not of scale or fashion. If a workload has a real cross-entity invariant that must never be violated even momentarily — money moving between two accounts, a seat that must not be sold twice, a schema change that must be atomic across thousands of servers — Spanner's bet is correct, and the commit-wait and consensus latency is the price of not having to write and audit reconciliation logic for every one of those invariants by hand. If a workload's "conflicts" have a well-defined application-level merge (union the items added to a cart, keep the highest bid, take the most recent write for a session token) and the true cost of an occasionally stale read is near zero, Dynamo's bet is correct, and paying for global consensus on every write would be waste with no corresponding correctness benefit. What would settle a specific case is not benchmarking the two designs against each other in the abstract, but writing down the invariant the application actually needs and checking whether it is expressible as a single-key operation — Bigtable's single-row transaction3 is already the empirically common special case where both camps agree, since it is atomic without needing coordination in either model.

References

  1. paperBerenson, H., Bernstein, P., Gray, J., Melton, J., O'Neil, E., O'Neil, P. A Critique of ANSI SQL Isolation Levels. ACM SIGMOD 1995 / Microsoft Research Technical Report MSR-TR-95-51. https://arxiv.org/abs/cs/0701157. Accessed 2026-09-17. Used for: P0-P3 phenomena definitions (§2), snapshot isolation definition and first-committer-wins (§4.2), write skew/A5B (§4.2), isolation-level incomparability (Remark 9).
  2. officialPostgreSQL Global Development Group. PostgreSQL 18 Documentation, §13.2 Transaction Isolation. Live documentation. https://www.postgresql.org/docs/current/transaction-iso.html. Accessed 2026-09-17. Used for: read committed/repeatable read/serializable implementation details, error messages, REPEATABLE READ implemented as snapshot isolation.
  3. paperChang, F., Dean, J., Ghemawat, S., Hsieh, W.C., Wallach, D.A., Burrows, M., Chandra, T., Fikes, A., Gruber, R.E. Bigtable: A Distributed Storage System for Structured Data. OSDI 2006. https://www.usenix.org/legacy/event/osdi06/tech/chang/chang.pdf. Accessed 2026-09-17. Used for: (row, column, timestamp) data model (§2), column families (§2), memtable/SSTable/compaction mechanics (§5.3), single-row transactions and no cross-row transactions (§3, §6).
  4. paperO'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 1996. https://www.cs.umb.edu/~poneil/lsmtree.pdf. Accessed 2026-09-17. Used for: B-tree I/O-doubling claim (§1), two-component C0/C1 LSM-tree mechanism and rolling merge (§2), TPC-A worked derivation (disk-arm doubling).
  5. paperGray, J., Lamport, L. Consensus on Transaction Commit. Microsoft Research Technical Report MSR-TR-2003-96, published in ACM Transactions on Database Systems 31(1), 2006. https://lamport.azurewebsites.net/video/consensus-on-transaction-commit.pdf. Accessed 2026-09-17. Used for: RM/TM state machine and safety requirements (§3.1), message/delay cost 3N-1 (§3.1, Table 2), the blocking problem (§3.2), Paxos Commit as the F=0 generalization.
  6. paperCorbett, J.C., Dean, J., Epstein, M., et al. Spanner: Google's Globally-Distributed Database. OSDI 2012. https://research.google.com/archive/spanner-osdi2012.pdf. Accessed 2026-09-17. Used for: 2PC over Paxos groups, prepare/commit record logging (§3.3), TrueTime commit wait (§3.3), wound-wait deadlock avoidance, external-consistency claim (disagreement section).
  7. paperDeCandia, G., Hastorun, D., Jampani, M., et al. Dynamo: Amazon's Highly Available Key-value Store. SOSP 2007. https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf. Accessed 2026-09-17. Used for: ACID definition (§1), always-writeable design target and rejection of isolation/general transactions (§6, disagreement section), key-value data model (§5.3).