Percolator Transaction Model

Percolator, originally described by Google for incremental web-index updates on Bigtable, structures each logical row into three column families: data (versioned values keyed by timestamp), lock (a write-intent marker), and write (a pointer to the committed data version). A transaction reads a consistent snapshot at a start_ts issued by a centralized Timestamp Oracle (TSO), buffers writes locally, then executes a two-phase commit: prewrite installs a lock and provisional data cell on every key touched, and commit resolves them, but only after one key — the primary — is committed first. Every secondary lock stores a pointer back to the primary, which is the linchpin of the entire crash-recovery model.

The critical design trick is that transaction atomicity does not depend on a separate coordinator process staying alive. If a client crashes mid-commit, any reader that later encounters a stale secondary lock does not block indefinitely — it inspects the primary lock’s status. If the primary committed, the reader rolls the secondary forward (completing the commit on the reader’s behalf); if the primary is still locked past a TTL, the reader treats the transaction as failed and rolls it back. This makes the protocol self-healing at read time, at the cost of every read potentially triggering lock-resolution side effects.

• Timestamp Oracle dependency: every transaction’s start and commit timestamps come from a single logical (though often batched/leased) service; it becomes a throughput ceiling and, if not made highly available, a correctness-critical SPOF.
• Lock GC: orphaned locks from crashed clients must be actively cleaned via TTL-based lease expiry, or long-lived scans stall behind them — this is functionally similar to a fencing mechanism but scoped per-key rather than per-resource.
• Write skew resistance: because reads snapshot at start_ts and commits are validated against the write column for conflicting later commits, the model gives Snapshot Isolation, not full serializability, unless additional read-set validation (as in TiDB’s optimistic model) is layered on top.
• Notification/observer chaining: the original paper pairs this with an observer framework so committed writes can trigger downstream incremental computation, which is largely orthogonal to the transaction core but was Percolator’s actual product goal.

Systems like TiDB adopted this model almost verbatim: TiKV stores the lock/write/data column families per key, and PD (Placement Driver) serves as the Timestamp Oracle, batching timestamp allocation to amortize the round trip. CockroachDB’s original transaction model was also heavily influenced by Percolator’s intent-record-and-resolve pattern before it evolved toward its own MVCC timestamp-cache design. The tradeoff engineers inherit from choosing this model is explicit: you get transactional semantics over a scale-out KV layer without rearchitecting storage, but you pay in commit latency (minimum two sequential RPC round trips per transaction) and in operational complexity around lock TTLs, oracle availability, and background lock-cleanup workers that must run continuously to prevent read-path stalls.

Understanding Percolator is essential when evaluating or operating any transactional database built as a layer atop a distributed KV store, because nearly every failure mode — phantom blocking reads, commit latency spikes, oracle throughput ceilings — traces back to this lock/timestamp architecture rather than to the underlying storage engine itself.