One Commit Point

Why NoSQL exists: ACID, the single commit point, and every way a system can move it, drop it, or rebuild it

CS 4140 — Software Engineering

2026-11-20

One question, a dozen answers

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.

Part 0 — The Promise

A commit point is one decision, made once

The problem

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.

Having it twice is the problem

The problem

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.

A transaction is the unit these promises are about

The mechanism

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.

ACID is four promises about one transaction

The mechanism
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.

Write-ahead logging is how one node keeps all four

The mechanism

The mechanism is old and unglamorous: append the intent, then apply it later.

  1. append the new values to the log
  2. fsync the log — this is the commit record
  3. apply to the data pages at leisure, in log order
  4. after a crash, replay the log from the last checkpoint
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.

Part I — Why It Does Not Distribute

Two writers, two orders, one row

The problem

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.

The only fix is coordination, and it costs latency or availability

The trade

Eager: agree before committing

  • distributed locking, or consensus (Paxos, Raft)
  • synchronous replication to a quorum
  • correct, and it pays a round trip on every commit
  • loses availability when the network does

Lazy: commit locally, replicate later

  • fast, and available during a partition
  • replicas diverge during normal operation
  • conflicts and stale reads become possible
  • this is not ACID any more

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.

The fork: converge later, or wait for a majority

The trade

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.

CAP is about what you do during a partition

The trade
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.

CAP’s C is not ACID’s C

The trade

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.

R + W > N is the whole dial

The mechanism

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.

Part II — Sharding

Sharding answers a different question: who owns this key

The problem

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.

The join is the casualty, and it takes ACID’s C with it

The bill

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.

How would you fix it?

The bill

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.

Part III — Cassandra, the AP Answer

Cassandra is what you build when you accept the trade

The promise

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.

It is a table, but not the table you mean

The mechanism

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.

  • the partition key decides which node owns the row
  • inside a partition, rows are ordered by the clustering columns
  • cells are sparse — different rows may hold different columns

You design the table around the query, not the entity.

Writes are cheap because the log is the table

The mechanism

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.

Two axes, and neither is the other

The mechanism

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.

Consistency is a value the client passes per query

The mechanism
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.

The same architecture, two philosophies

The trade
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.

A dead replica is a replica-group problem

The mechanism

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.

Three transaction mechanisms, none of them general

The mechanism
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.

There are no joins, only denormalized tables

The bill

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.

The transfer it cannot do

The evidence

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.

How it fails each letter

The bill
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.

Part IV — The Precision Beat

“Partially ACID” is not a category

The claim

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:

  • partition-level atomicity
  • row-level isolation
  • local (per-replica) durability
  • and an explicit refusal of the global “C”

That is a precise claim about four separate things. “Partially ACID” is a sentence that sounds like one thing.

ACID never required relations

The claim

The first misconception to clear: ACID is not a relational feature.

  • A, I and D are properties of a write mechanism. They do not know what your data means, and they do not need a schema.
  • There is no contradiction in a non-relational system providing some of them. Many do.
  • The relational model and ACID grew up together, which is a fact about history, not about logic.

ACID has nothing to do with relational algebra.

But “C” needs machinery only a relational engine has

The claim

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:

  1. a join-capable engine — to evaluate a predicate across entities
  2. one commit point — to make the whole check atomic

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.

The precise sentence

The claim

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.

Part V — The Shapes

If you gave up joins and transactions, do you still need a table?

The turn

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 document is the aggregate

The promise

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.

The commit point moved into the document

The mechanism

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.

“Schemaless” means the schema moved into the application

The bill
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.

One data model, three coordination choices

The trade
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.

CouchDB: replication is the primary constraint

The evidence

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.

RavenDB: ACID documents, eventual indexes

The evidence

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.

The shape that refuses to give up the join

The evidence

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.

An index is a bet about the next query

The mechanism

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.

Blob is the floor, not the destination

The bill

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.

Below the blob is a value that may not be there

The bill

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.

Part VI — The Capstone

Distributed ACID is possible if you pay coordination on every commit

The turn

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:

  • split the data into shards (ranges or tablets)
  • make each shard a consensus group with a leader
  • commit across shards with two-phase commit
  • get the order from a timestamp authority

That is two round trips before the client is told the write succeeded — on every commit, for the life of the system.

The commit point came back, but not to the same place

Where the order comes from

Both systems pay for coordination. They disagree about where the order lives:

  • TiDB asks one authority for a timestamp, and the decision is the primary lock of a two-phase commit. The order comes from outside the transaction.
  • YugabyteDB orders writes with a hybrid logical clock and records one status per transaction. The order comes from inside it.

Same question as slide 5 — where does the order come from? — and two different answers.

“ACID” here still means a point on a spectrum

The claim

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:

what it buys

ACID transactions, horizontal scale and geo-replication in one system.

what it charges

A round trip on every commit, and two more distributed components to operate.

Part VII — The Meta

The systems you can study are the systems you can run

The claim

There is a pattern, and you have already watched it once this hour.

  • The bait. Open core until the cloud provider arrives, then the licence moves. Elasticsearch became OpenSearch, Redis became Valkey, and the fork is the same fork twice.
  • The free sample. Oracle’s catalogue is the oldest version of this: MySQL, Berkeley DB, Java. Free to learn on, expensive to build on, and the interesting internals sit behind a support contract. Do not take even the free samples from Oracle.
  • The tell. A managed service can be excellent and still be unlearnable. You cannot read the code, so its “design trade-off” is a marketing claim rather than a fact you can check.

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.

Wrap

The design space, in one picture

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.

Five things to remember

  1. ACID is cheap because one node owns the commit point, and that is the thing that does not distribute.
  2. W + R > N is the whole dial — strong consistency without a master, at an explicit price.
  3. The join is what pays for sharding, and losing it loses the machinery that made “C” checkable.
  4. “Partially ACID” is not a category. Name the guarantee and its scope.
  5. The document is an aggregate, not a format — the commit point moved, it did not disappear.

Where this goes

  • This lecture was about one question and the five answers to it.
  • What it did not cover: streams (the commit point is an offset), vector stores (a blob with one index bolted on), and time series (wide-column with time as the clustering key). Each is a shape or a variation; none changes the question.
  • For the project: the default is still Postgres, and now you can say why. Reach for something else when you can name the cost you are choosing to pay.