Removing the coordinator: Percolator and Calvin

How can a transaction resolve with no coordinator, or need no vote at all?

Percolator-style timestamps

Percolator is the system Google built for incremental updates of its search index. Its setting is instructive: Bigtable, the underlying store, offered atomicity for a single row only, and Google needed transactions across rows. That is the object-store situation of Transaction mechanics at a different scale, and the recipe is the same: find the one atomic primitive and build everything on it.

The mechanism. A global timestamp oracle (a service that hands out increasing numbers) issues monotonic start and commit timestamps. Each row has extra columns for a lock and a write record.

1. Prewrite (the prepare): for each row, atomically check that no conflicting write happened since start_ts and that no lock exists, then write the value and a lock.
2. One row is chosen as the primary. Every other row's lock points at it.
3. Commit is a single-row atomic write of the primary's write record. The transaction is committed the instant that one row's write lands. The secondaries are cleaned up afterwards, asynchronously.

What makes this structurally different from Paxos-commit. Paxos-commit makes the decision-holder highly available. Percolator deletes the decision-holder by storing the decision in the data itself, on a row that any interested reader must already consult. A reader that meets a secondary lock follows the pointer to the primary and settles the outcome on its own: roll forward if the primary committed; roll back, after a lock timeout, if it did not. The client that drives the transaction can die forever and the transaction still resolves, because resolution is done by whoever cares next. No coordinator exists, so there is no coordinator to block on.

Three ways to resolve the blocking problem

This is the compression to carry out of this article:

1. Make the decision-holder fault-tolerant (Paxos-commit, Spanner). Price: consensus latency.
2. Make the decision discoverable by anyone (Percolator, TiDB). Price: a timestamp oracle and cleanup done by readers.
3. Make the decision unnecessary (Calvin, below). Price: access sets known in advance.

The costs of Percolator

• The timestamp oracle is a global serialization point. It works only because timestamp allocation is tiny and can be batched (a fixed per-operation cost derives a natural batch size).
• Read latency has a tail set by abandoned transactions, because readers do the cleanup.
• Writes are amplified: lock, data, write record, then cleanup writes.
• It provides snapshot isolation, not serializability, which is often glossed over.

Percolator was built for incremental index maintenance, a throughput workload where seconds of latency were acceptable. It is evidence for a mechanism, not a recommendation for OLTP (online transaction processing: many small, fast transactions).

---

Deterministic distributed transactions (Calvin)

This belongs directly opposite 2PC, not as an aside, because it is an alternative resolution, not an optimization.

2PC exists to discover whether any participant wants to abort for a local, nondeterministic reason (a full disk, a lock timeout). Remove the nondeterminism and there is nothing to vote about. Calvin agrees the global order of transactions first, through a replicated sequencer (a component that puts all incoming transactions into one agreed order, in batches). Then each partition executes its own slice of each transaction in that order. No participant can abort for a reason the others do not already know, because every outcome is a deterministic function of an agreed input. No vote, no prepare, no in-doubt window, and no coordinator to block on. The blocking problem is not mitigated. It is dissolved.

The costs are the ones that Multiversion and optimistic schemes derived for deterministic execution, now with a distributed payoff:

• Read and write sets must be known before execution. The escape is reconnaissance and validate (run a cheap pre-read to guess the sets, then check at execution time), and that quietly brings back optimistic concurrency control.
• The sequencer is a global ordering point. It bounds throughput and adds batching latency.
• Interactive transactions (a client sends statements one by one) are impossible.