PAPERS-15-005 · Paper — Percolator — Distributed Transactions at Scale

The paper

Percolator — Distributed Transactions at Scale, by Google researchers (including James C. Corbett and others), published in 2011 at OSDI, is a landmark because it showed how to add ACID transactions to a massive key‑value store and fundamentally changed web indexing at Google.

Before this paper

Before Percolator, Google rebuilt its web index only in huge batch MapReduce jobs, so a newly crawled page could take a long time to appear in search results. Incremental updates required multi‑row transactions, but Bigtable, the underlying storage, did not provide them. This limitation forced the index to be refreshed wholesale rather than continuously. The lack of cross‑row ACID support was a major scalability wall.

The key idea

The key insight of Percolator is to layer cross‑row, cross‑table ACID transactions with snapshot isolation on top of Bigtable, using a lightweight two‑phase commit protocol and a global timestamp oracle, plus a notification system that turns batch pipelines into incremental ones. This lets the search index be updated incrementally instead of being rebuilt from scratch.

How it works

Percolator adds special lock and write columns to each Bigtable row. A client first writes a lock record with a globally increasing timestamp obtained from a dedicated timestamp oracle. In the prepare phase it writes tentative values to the write columns while holding the lock. After all participants are prepared, the client issues a commit that writes a commit timestamp, making the tentative writes visible to readers that use snapshot isolation. Observers watch the commit timestamps and trigger downstream computation, so changes propagate incrementally. The whole process trades a small amount of latency per transaction for massive throughput across many machines.

See it — transactions over a big table

flowchart LR
  A["Update index<br/>incrementally"] --> B["Multi-row ACID<br/>transactions"]
  B --> C["Snapshot isolation<br/>via timestamps"]
  C --> D["Notifications<br/>trigger work"]

What they showed

The authors demonstrated that Percolator let Google move web indexing from periodic batch jobs to continuous incremental updates, cutting the average age of documents in the index dramatically.

What it changed

Percolator showed that real transactions could be bolted onto a scale‑out key‑value store, influencing later systems such as Apache Omid and TiKV. It changed the field by proving that strong consistency and high throughput are compatible at web scale, and it inspired transaction layers in many modern distributed databases. Next: Spanner.

The one-line takeaway

Strong, low‑latency transactions can be built on top of a massive key‑value store to enable continuous, incremental processing at web scale.

Read it / meet it

Reading the original Percolator paper gives a clear view of how Google solved its indexing bottleneck and introduced a new transaction model. Its legacy lives on in today’s distributed databases that offer transactional APIs over key‑value storage.