Percolator: Distributed Transactions Without a Transaction Server

Classic two-phase commit needs a coordinator — a process that remembers, across crashes, which transactions were told to commit. Coordinators are painful: they're state you must replicate, a liveness dependency for every participant, and the reason "2PC blocks" became folklore. Percolator, built at Google to incrementally update the search index, asked a sharper question: what if the data store itself kept all the transaction state, and any client could finish (or abort) any other client's crashed transaction just by reading it? The design — snapshot isolation over Bigtable with locks stored as columns — is the ancestor of TiDB and TiKV's transaction layer, and it's the cleanest case study in decentralizing commit.

Ingredients

A Bigtable-like store providing single-row atomic read-modify-write (that's all — no multi-row operations), and a timestamp oracle (TSO): a service handing out strictly increasing timestamps (a counter batching allocations — millions/sec from one node — with its own failover story). Every transaction gets start_ts at begin and commit_ts at commit; versions of data are written at these timestamps (MVCC).

Each logical column gets three physical columns: data (values by timestamp), lock (in-flight transaction markers), and write (commit records mapping commit_ts → start_ts — "the version written at start_ts became visible at commit_ts").

The protocol: 2PC where the coordinator is a row

Prewrite (phase one): pick one written cell as the primary — this cell will be the commit point. For every cell in the write set, atomically check-and-write: no conflicting lock, no write committed after our start_ts → write the value at start_ts into data and a lock (pointing at the primary) into lock. Any check fails → abort, clean up.

Commit (phase two): get commit_ts from the TSO. Then, on the primary cell only, in one single-row atomic op: verify our lock still exists, replace it with a write record at commit_ts. That single-row operation is the entire commit decision. If it succeeds, the transaction is committed — everywhere, logically — even though the secondary cells still carry locks. Secondaries are then cleaned up lazily: their locks swapped for write records, asynchronously, by anyone.

prewrite:  lock all cells (each points at primary), values at start_ts
commit:    atomic swap on PRIMARY: lock -> write@commit_ts   <- the commit point
           secondaries: cleaned up lazily, by anyone, later

Crash recovery without a recovery service

A client dies mid-transaction, leaving locks behind. A later reader hits one of those locks and must decide: in-flight, committed-but-uncleaned, or dead? It follows the lock's pointer to the primary:

• Primary lock still there → the transaction never committed. The reader may abort it (remove the primary lock) after a timeout/TTL check — and once the primary lock is gone, the transaction can never commit.
• Primary shows a write record → the transaction did commit. The reader rolls the secondary forward (installs its write record) and proceeds.

Every observer reaches the same verdict because the verdict is a fact stored in one cell, readable and CAS-able by anyone. No coordinator log, no blocking on a dead process — the "coordinator state" that makes 2PC scary became a row with single-row atomicity, and recovery became a pure function of visible data. That is the transferable idea, and it's worth stating exactly that way in an interview.

What you get and what it costs

Snapshot isolation: reads at start_ts see the state as of that timestamp — consistent, lock-free reads of committed data (readers do wait on in-flight locks below their timestamp — that wait is what makes the snapshot honest). Write-write conflicts are detected at prewrite (first committer wins; the loser retries). SI's known hole — write skew (two transactions each read what the other writes, both commit, invariant dies) — is the follow-up question to expect; the fixes are SELECT FOR UPDATE-style lock-the-read (materialize the conflict) or the SSI machinery Postgres uses.

Costs, honestly: each transaction pays multiple round trips (prewrite per shard + TSO + primary commit) — throughput-oriented, latency-mediocre, which suited an indexing pipeline and suits OLTP-at-scale (TiDB) with batching. Lazy cleanup means readers occasionally do repair work on the hot path. The TSO is a real dependency (single point for ordering — batched, replicated, but say it: Percolator centralizes time instead of commit state, a much easier thing to make highly available). Long transactions hold locks long — the design wants short transactions and gets grumpy otherwise.

Interview probe	Answer sketch
vs Spanner?	Spanner: consensus groups + 2PC across them + TrueTime → external consistency, interactive latency. Percolator: client-driven 2PC over MVCC + TSO → SI, higher latency, no special clocks. Different hardware bets, same "make commit a single atomic fact" instinct
Why is the primary special?	It serializes the commit decision into one CAS-able cell — exactly one place where "did T commit" has an answer
Lock TTLs vs live slow clients?	Heartbeat on the primary lock (TiKV's approach); cleanup requires TTL expiry, so a slow-but-alive client isn't murdered mid-commit
Read-only transactions?	Free: take a start_ts, read the snapshot — the whole point of MVCC underneath

The design lesson to bank: any distributed protocol's dangerous state is whatever must survive a crash. Move that state into the storage system as ordinary, atomically-swappable data, and recovery stops being a special mode — it's just another reader.