Why NoSQL exists: ACID, the single commit point, and every way a system can move it, drop it, or rebuild it
2026-11-20
NoSQL is not a family of products. It is a family of answers to one question: where is the commit point, and who pays for it?
| where the commit point is | the system | what it charges |
|---|---|---|
| one node | Postgres | horizontal write scale |
| nowhere: converge later | CouchDB, Riak | conflicts to reconcile |
| a dial you turn per query | Cassandra | joins, cross-partition work |
| a majority, every commit | HBase, YugabyteDB, TiDB | latency |
| gone: no promise made | memcached | the value may not be there |
Every system in this lecture is one of those five answers, and every one of them is software you can download and read. That last part is not a neutral fact about the software market, and slide 41 comes back to it.
A commit point is the single instant at which a set of writes becomes, together, visible, durable and ordered — and there is exactly one of them per transaction.
In Postgres you can point at it. COMMIT appends a commit record to the write-ahead log and fsyncs it. Before that record exists, no reader sees anything. After it, every reader sees all of it.
Durability on many machines is easy — copy the bytes. What is hard is one decision out of many independent ones.
Neither node is broken. Each one did exactly what it was asked. The system now has two truths and no undo.
That is the challenge, and it is not storage or throughput: it is a single decision, made once, when the deciders cannot see each other.
BEGIN, statements, then COMMIT or ABORT. The unit is a set of writes with one outcome, not a write.
Worth saying early, because the rest of the lecture keeps using it: a single-row write is a transaction of size one. “Single-row atomicity” is a much smaller promise than “atomicity” sounds, and the difference matters in Part III.
| the promise | a property of | |
|---|---|---|
| A | the whole set lands, or none of it does | the mechanism |
| I | concurrent transactions do not see each other’s uncommitted work | the mechanism |
| D | once the commit record is on disk, a crash does not undo it | the mechanism |
| C | the transaction moves the data from one valid state to another | the data model |
Read the first three with the word “transaction” in front: the transaction is atomic, isolated and durable. C is different: it is a statement about invariants you declared — keys, foreign keys, checks.
It only means anything if something declared them. Park that; it is all of Part IV.
The mechanism is old and unglamorous: append the intent, then apply it later.
fsync the log — this is the commit record| the log is | because |
|---|---|
| the order | pages are updated in log order, and only in that order |
| the durability record | the commit record is on disk before the client hears yes |
| the recovery plan | replay is the repair, and it needs no coordination |
One artifact does all three jobs. That is why a single node gets A, I and D almost for free — and why the commit record is the commit point.
Let more than one node accept writes and you immediately get conflicting concurrent transactions: two inserts on one key, two updates to one row, two transactions that each assume they are the only writer.
Last-write-wins is not a fix. It is a policy for choosing which write to throw away, and it has to be chosen per column, by somebody, before the first conflict arrives.
Eager: agree before committing
Lazy: commit locally, replicate later
Maintaining ACID across multi-master replication is “virtually impossible” with any semblance of performance.
ACID is not hard because Postgres is old. It is hard because one global commit point does not scale across writers without paying for coordination.
Path A gives up “the latest write”. Path B gives up “the fast write”. There is no third path — only different prices for the same two.
| the guarantee | what it means here | |
|---|---|---|
| C | linearizability | every read returns the latest completed write |
| A | availability | every request gets a non-error response |
| P | partition tolerance | not a knob: a property of the network |
So “pick two of three” is the wrong sentence. P was never optional. The choice is only what you do while a partition is happening — which is the fork from the previous slide, now with its formal name: Path A is AP, Path B is CP.
The shared letter is a coincidence of vocabulary, and it is the most misread coincidence in the field.
| what it actually is | about | |
|---|---|---|
| CAP’s C | linearizability | one operation, in real time |
| ACID’s C | declared invariants hold | the whole data set |
| ACID’s I | isolation; serializable at its strongest | one transaction |
Serializability is not linearizability. Together they are strict serializability, which is what the systems in Part VI actually aim at.
Which gives the sharp result: a system can be CP and still violate ACID’s C — because ACID’s C needs invariants to exist and machinery to check them. CAP constrains replication during a partition. ACID constrains what a transaction promises. Different questions.
With N copies, require W acknowledgements to write and R replicas to read. If W + R > N, the write set and the read set cannot miss each other, so every read touches at least one replica holding the latest write.
Six of the nine settings work. The other three are not broken — they are Path A with extra steps.
Replication copies the same rows. Sharding splits them: a key function decides which node owns which rows, so capacity and write throughput grow with the number of machines.
It does not make anything consistent. It makes a different problem: every question that used to span the table now spans the network.
An invariant that spans two entities needs both entities in one place, at the same moment, with a decision about both. Shard the rows apart and you have removed the place.
This is the hinge of the lecture: losing the join is not a convenience loss. It is the loss of the mechanism that made “C” checkable.
Four answers, and only the first is cheap:
| answer | when you pay | what it does |
|---|---|---|
| co-locate | design time | shard both tables on the join key |
| denormalize | write time | store the answer, so no join happens |
| broadcast | query time | copy the small side to every node |
| shuffle | query time | re-partition both sides by the join key |
A query optimizer chooses between the last two. A designer chooses the first once, and gets one chance to choose the shard key. Denormalizing is Cassandra’s answer, and it is the next part.
The best cross-shard join is the one you designed away.
Cassandra is leaderless, partitioned and replicated, and it refuses cross-partition coordination by design: no distributed joins, no cross-partition transactions, no foreign keys.
| it gives you | it charges you |
|---|---|
| linear write scaling | no joins, ever |
| a per-query consistency dial | no cross-partition transactions |
| no single point of failure | no ad-hoc queries: the table is the query |
That is the whole bargain. Everything after this is Cassandra living with it.
Not a document store with columns instead of JSON, and not a blob store. It is a partition-addressed, sorted, wide-column engine: a two-dimensional key-value store.
You design the table around the query, not the entity.
A write appends to the commit log and to an in-memory memtable, and is acknowledged. The memtable flushes to an immutable SSTable; compaction merges them in the background.
Nothing is read before it is written. The bill arrives later: a read for one key may have to look in four places before compaction, and compaction itself steals I/O from the foreground.
Partitioning decides who owns the key. Replication decides how many copies exist and how many must agree. The quorum question, R + W > M, is asked inside one replica set — never globally.
Say “many partitions, each replicated M times”. The number of partitions is a function of your data, not a setting.
| level | what the coordinator waits for | when you would choose it |
|---|---|---|
ONE |
one replica | speed, and you can live with staleness |
QUORUM |
a majority of replicas | the default answer for strong reads |
ALL |
every replica | almost never: one dead node stops you |
LOCAL_QUORUM |
a majority in this datacenter | multi-region, without cross-region waits |
The dial is per operation, set by the client. The same table can be read strongly for a checkout and weakly for a dashboard.
| Dynamo-style | Raft-style | |
|---|---|---|
| who chooses the quorum | the client, per query | the system, per shard |
| examples | Cassandra, Riak | HBase, YugabyteDB, TiDB |
| what it buys | tunable latency | one isolation level, always |
| what it charges | you must know each query’s needs | coordination on every commit |
Same two axes — partitioning and replication. The difference is whether the trade is a runtime dial or a design-time commitment.
Three mechanisms, one idea: the group converges without a global decision. Hinted handoff covers a dead node, read repair fixes a laggard on the read path, and anti-entropy repair compares the whole set in the background.
| mechanism | scope | atomic | isolated | what it costs |
|---|---|---|---|---|
| logged batch | one partition | yes | no | all statements must share a partition key |
| lightweight transaction | one partition | yes | yes, one row | four round trips, and no batches |
| Accord | many partitions | yes | yes | newer, and a layer on top of the design |
A batch is atomic but not isolated: concurrent operations interleave. A lightweight transaction is isolated but cannot be combined with a batch, because its isolation requirement is exactly what a batch does not provide.
You cannot perform joins in Cassandra. If you have designed a data model and find that you need something like a join, you’ll have to either do the work on the client side, or create a denormalized second table that represents the join results for you.
That is the official position, and it is not a limitation to be worked around. It is the fourth answer from slide 17 — denormalize — taken as the default: one table per query pattern, with the data duplicated so that every query is a single-partition read.
The bill is redundancy and write amplification. The payment buys you this: no query ever coordinates across nodes.
Two accounts, two partitions, one invariant: the total does not change. 100 + 50 = 150 before, 80 + 70 = 150 after — and 80 + 50 = 130 is a row this system can produce.
The third row is reachable. If a write succeeds on some replicas and fails on others at QUORUM, the client is told it failed — and nothing undoes the replicas that succeeded. There is no cluster-spanning undo log to undo it with.
| letter | at what scope | what it actually offers |
|---|---|---|
| A | one partition | a single row, or one batch, is all-or-nothing |
| I | one row | no reader sees a half-written row; nothing else is isolated |
| D | one replica | the local write survives a crash; there is no cluster-wide commit |
| C | — | declined: no cross-partition invariants, so nothing to enforce |
Not uniform across the four letters. Three of them are delivered at a scope much smaller than the word suggests, and the fourth is not delivered at all.
ACID is a property of a transaction. A transaction satisfies the set or it does not. There is no 50% transaction, and no formal object called “partially ACID”.
What Cassandra offers is a specific subset of guarantees:
That is a precise claim about four separate things. “Partially ACID” is a sentence that sounds like one thing.
The first misconception to clear: ACID is not a relational feature.
ACID has nothing to do with relational algebra.
In the relational world, “consistency” is declarative, global invariants: primary keys, foreign keys, checks, and the structure itself. The database can enforce them because it has two things:
Remove both, as slide 11 did, and you have removed the enforcement machinery, not just the syntax for declaring it.
The relational model does not define ACID. It makes the “C” tractable.
Cassandra does not offer “partial ACID”. It offers a specific subset of transactional guarantees, and explicitly declines the global “C” — because enforcing that “C” needs joins to evaluate the predicate, keys to declare it, and one commit point to make it atomic.
Without those, “consistency” collapses into a different promise: if you wait and reconcile, replicas converge.
That is a real guarantee. It is not the same guarantee, and it is the one worth writing down.
Cassandra’s answer is yes — but a table redefined. Not a normalized relation with invariants, but a query-shaped, denormalized partition: a pre-joined materialized view, keyed by access pattern.
Which raises the next question honestly:
If the unit is no longer a row in a relation but an aggregate fetched by key, why impose a schema at all?
That question opens the rest of the lecture.
The defining property of a document store is not the format. It is that a whole nested structure is one addressable, atomically mutable value — this order, three line items and all, totalling 75.75, in one read and one write.
And the structural reason is the one from slide 11: you gave up the join, so you gave up reassembling a relation at read time. The document store’s answer is do not decompose in the first place.
Document databases did not abandon ACID. They moved the commit point to the document: a single-document write is atomic and usually durable.
What you lose is cross-document atomicity — unless the system added it later, at a price. The design rule that follows is short:
If two pieces of data must be updated atomically, they belong in the same document.
And the failure mode is worth naming: if the boundary is wrong, you find out when you need a multi-document transaction — and at that point you are running a document database as a worse relational database.
| schema-on-write | schema-on-read | |
|---|---|---|
| who checks the shape | the database, at insert | the application, on read |
| malformed data | rejected | stored |
| a change of shape | a migration | a code path |
The tell that this is a real cost: every mature document store re-added validation. CouchDB has validate_doc_update functions that run on write and reject by throwing.
What you actually get is schema drift: several historical shapes coexisting in one collection, with the compatibility logic living in the application.
| coordination | consistency | what it proves | |
|---|---|---|---|
| HBase | master and region servers, on HDFS | strong by default | the model does not force AP |
| Cassandra | leaderless, quorum per query | a dial | the model does not force strong |
| Riak | leaderless, no quorum | CRDTs merge | convergence without agreement |
All three are wide-column. They sit on opposite sides of the fork. The data model does not pick the consistency choice — and that is the most useful thing the family can teach.
Riak is also the third answer to divergence: not quorum, not a revision tree, but data types that merge.
Every replica accepts writes; replication is pairwise, resumable and bidirectional, with no primary. Because concurrent edits are normal, a document carries a revision tree, not a version number — and the loser of a merge is retained, not deleted, and readable as a conflict.
PouchDB is the same protocol in a browser: the client is a genuine replica, not a cache.
The honest counterexample to “documents cannot do ACID”. RavenDB provides multi-document transactions by default, not as an opt-in bolt-on.
And then the second, more interesting decision: its indexes are non-transactional and eventually consistent by design.
| consistency | what it means | |
|---|---|---|
| the documents | strong | a transaction is a transaction |
| a query served from an index | eventual | it may not see the write you just committed |
RavenDB decomposes consistency into document consistency and index freshness. That is a genuinely different decomposition, and it is worth knowing that somebody made it.
A graph store is what you build when the join is the thing you will not give up. Index-free adjacency stores the relationship itself as a record holding pointers, so a traversal is a pointer chase rather than a series of index lookups.
The join is materialised at write time. The bill: a traversal crosses partitions by nature, so partitioning a graph is the hard part, and deep traversal does not scale out the way a partition-key read does.
A CouchDB view is an incrementally maintained materialised view: a map function runs over every document, its output is sorted into a persistent B-tree, and queries are range scans over that order.
An inverted index answers a different question: term to postings, optimised for “the best few, in any order”. A write touches many postings, so writes are expensive and reads are flexible — the inverse of the wide-column model.
Both are bets that the next query looks like the last one.
A blob store maps (bucket, key) to an opaque byte sequence. The value is never queried or indexed, only stored and retrieved whole, and a partial update is usually impossible — you replace the object.
That is not a failure. It is the correct design for backups, media and data-lake payloads. But it is also the bottom of a spectrum of access depth, and every step up buys query surface and costs coordination or structure.
The cheapest answer to “where is the commit point” is there isn’t one, and there was never a promise. That is memcached: no durability, no replication, no transactions. The client hashes a key to a server, and the entry can vanish.
Valkey sits one rung up and is the more instructive case: one node holds the commit point, replicas are asynchronous, so a failover can lose a write — and WAIT is the quorum dial at miniature scale.
A cache is not a degenerate database. It is a deliberate refusal to promise something it would have to keep.
YugabyteDB and TiDB do the thing slide 7 said was “virtually impossible”: they keep serializable-ish transactions across machines. The trick is not a better algorithm, it is paying the price consistently:
That is two round trips before the client is told the write succeeded — on every commit, for the life of the system.
Both systems pay for coordination. They disagree about where the order lives:
Same question as slide 5 — where does the order come from? — and two different answers.
YugabyteDB defaults to serializable. TiDB defaults to repeatable read, because it is MySQL-compatible and that is what MySQL means.
Both “pay for ACID” and still disagree about what it buys — which is exactly what Part IV said would happen: there is no monolith, only a specific point in a spectrum of guarantees.
And the currency is still the same one:
ACID transactions, horizontal scale and geo-replication in one system.
A round trip on every commit, and two more distributed components to operate.
There is a pattern, and you have already watched it once this hour.
Every diagram in this lecture came from documentation and source you can read. That is not a neutral fact about the software market. It is a fact about which part of the market you can learn from.
The two axes are the two questions this lecture asked: where the commit point is, and how much structure the store understands.
Read the vertical spread: at almost every rung there are systems on both sides of the fork. That is the claim the whole lecture has been building — the data model does not pick the coordination. And note the empty corner: nobody pays consensus for a blob.
W + R > N is the whole dial — strong consistency without a master, at an explicit price.CS 4140 · One Commit Point