CS PAPERS · DEEP READ · PAPER 21
Peng & Dabek · Google · OSDI 2010
In 2010, two Google engineers (Peng and Dabek) built a system called Percolator and used it to rebuild Google's search index. In one sentence: it changed how a freshly-crawled web page reaches search results — from "wait for the whole batch to be recomputed" to "one page in, update it right away." After it shipped, the average age of documents in search results dropped by half — the web got fresher, faster.
Before this, Google used its previous workhorse, MapReduce: treat all of the billions of web pages as one giant pot, cook the whole pot at once, and produce a new index. The problem — change a single page and you still have to re-cook the entire pot. A full pass over the web took days, so an article you posted today might not be searchable for several days. The only way to speed it up was to re-cook the whole pot more often, which was far too expensive.
Percolator's idea: when one page changes, update only the small part that depends on it, and leave the billions of unchanged pages alone. That is "incremental processing" — like adding one ladle to a soup instead of pouring it out and reboiling.
This was hard to do before because of two obstacles, and Percolator supplies exactly the two missing pieces:
Updating a page often means changing several records at once (this word points at that document, that document's rank, its backlinks…). If the machine crashes halfway, the index becomes a half-new, half-old mess. Percolator wraps those scattered changes in a "transaction": either they all take effect, or it's as if nothing happened — never a half-baked state.
How does it guarantee all-or-nothing? Picture moving house: you put a sticky note on every box to lock it, and you designate one "master box" as the master switch. Only when the master box's note is flipped does the whole move count as "officially done"; until then, anyone looking sees "not moved yet." So even if the power dies mid-move, others see the master box unflipped and know this move doesn't count. One atomic little action decides the fate of a whole pile of changes.
The index is a chain: page content changes → recompute its keywords → keywords change → update the inverted list… Percolator adds a set of "triggers": you watch a kind of data, and the moment it's written, the system automatically wakes up a piece of logic you wrote to follow up, which may trigger the next link — like changing one cell in Excel and watching every formula that depends on it recompute in a cascade. A handful of changes "percolate" through the whole index on their own — which is exactly where the name Percolator comes from.
Google used it to replace the old MapReduce indexing pipeline (the new system is known as Caffeine). Processing the same number of pages, the average freshness of search results roughly doubled — what you just posted becomes searchable sooner. One honest cost: this "always up to date" isn't free — compared with MapReduce sweeping the whole pot smoothly, Percolator does dozens of scattered reads and writes for every document it updates, so it burns more machines. Google traded resources for freshness because the trade was worth it.
Percolator turned Google's search index from "recompute the whole batch, days behind" into "one page in, update it now." It does this with two things: wrapping scattered changes in an "all-or-nothing" transaction (using one "master lock" as the master switch), plus a trigger system where "something changes → whatever depends on it is auto-notified to follow up." Freshness doubled; the price is more machines.
Want to see how it builds transactions on Bigtable with timestamps and a "primary lock," and how observers cascade? → Switch to the deep read
Percolator adds two things on top of Bigtable — cross-row, cross-table ACID transactions (snapshot isolation) and an observer / notification mechanism — to convert Google's web indexing from "rebuild the whole thing with MapReduce" into "incremental processing: one document in, update only the affected part." The resulting system (known as Caffeine) cut the average age of documents in search results by about 50% at the same throughput.
Authors Daniel Peng and Frank Dabek, Google, published at OSDI 2010. It builds directly on Google's "old three" — sitting on top of Bigtable (storage) and replacing the MapReduce-based (batch) indexing pipeline — and uses a lightweight lock service akin to Chubby (Paper 20) for failure detection. It is counted among Google's "new three" (alongside Pregel and Dremel). It moved "large-scale distributed transactions" from an academic "can't be done efficiently" to industrial reality, and directly inspired later distributed databases like TiDB / TiKV, whose transaction models are essentially copied from Percolator.
Google's web index is fundamentally a pipeline: crawl a page → extract content, compute PageRank, cluster and dedup → update the inverted index. Before 2010 this ran as batch MapReduce: feed in the entire web repository of the moment (tens of PB), run a chain of MapReduce jobs, and emit a whole new index.
The pain is the granularity of batch: MapReduce insists on scanning the entire input. Even if only a tiny fraction of pages actually changed this round, you still have to reprocess the whole repository — because one new page can shift other pages' ranks and cluster memberships, so batch can't "compute only the affected part." The result: a page took a full re-run (on the order of days) to go from crawled to live in the index. Updating faster meant re-running the full batch more often — prohibitively expensive.
So why not just use a database and fire a transaction that touches a few rows per page? Because of scale: no DBMS of the era could sustain that volume of random read/write throughput across thousands of machines. The problem becomes: on storage that can take the scale (Bigtable), can we supply the two capabilities that "update only the affected part" needs — multi-row transactions, and a "who changed, notify whom" trigger?
Incremental processing is, at heart: maintain a pile of interdependent data, and when an upstream item changes, "percolate" that change downstream. Doing this needs two things: multi-row transactions — an update usually must change several places consistently, and mustn't crash halfway (or the index becomes garbage); and notifications — you must know "what got dirty, which computation to wake next," or you're back to "scan everything to find the changes." Percolator layers exactly these two onto Bigtable.
Bigtable only guarantees single-row atomicity. To do cross-row, cross-table ACID, Percolator gives each data column a few extra "metadata" columns, storing lock and version info right inside Bigtable, then strings them into transactions with a two-phase commit protocol. Three columns are central:
data: the cell's actual value at a given timestamp. Bigtable natively keeps multiple versions by timestamp.lock: marks "an uncommitted transaction is holding this cell." Among all cells a transaction writes, one is designated the "primary lock," the rest are "secondary" locks, each recording where the primary lives.write (the commit point): a pointer to the timestamp of the committed data version. Reads only honor write — data with no write record is invisible to readers.Each transaction takes two timestamps from a global service, the timestamp oracle: start_ts at the beginning, commit_ts at commit. A read returns "the latest committed version with timestamp < start_ts" — that forms its consistent snapshot. A write happens in two phases:
data (stamped with start_ts). Before locking, check two things: is there a write record committed after start_ts (yes = write-write conflict, abort); is another transaction's lock still present (yes = lock contention, back off and retry).write record (pointing at start_ts) and erase the primary lock. This step is the transaction's "moment of taking effect": once the primary commits, the transaction counts. Then, at leisure, roll each secondary lock forward into a write record.The magic is the "primary lock as master switch": a transaction may touch dozens of cells, but whether it counts is decided by a single atomic action — "did the primary cell turn into a write record." If a client crashes after committing the primary but before cleaning up secondaries, those secondary locks linger, but any other transaction that stumbles on one will follow the address it records to inspect the primary: primary already committed → help commit this secondary too (roll-forward); primary still locked / rolled back → clear this secondary (roll-back). To decide whether the client is really dead, it uses a Chubby-like lightweight lock service plus a timeout. So there's no dedicated transaction manager — cleanup is lazy and decentralized, done in passing by later transactions.
Snapshot isolation requires timestamps to be strictly increasing. Percolator uses a dedicated timestamp oracle service to hand them out. It doesn't write to disk per request — too slow; instead it batch-writes "the highest number allocated so far" to stable storage once, then serves numbers purely from memory within that range, replying to a batch of requests at a time. Thanks to batching, a single machine can dispense about 2 million timestamps per second, enough for the whole cluster. (It's a centralized component, but its state is tiny and replicable, and after batching it isn't a bottleneck.)
Transactions alone aren't enough for incremental work: you still need to know "which data got dirty, which computation to wake." Percolator adds observers to columns: a programmer registers "when these columns are written, run this logic"; when a column is written, a mark is placed in its notify column. A pool of standing worker processes randomly scan for these notification marks, and on a hit run the matching observer code — which in turn writes other columns and triggers the next round of notifications, cascading onward. Like changing one Excel cell and watching dependent formulas recompute in a chain. To prevent repeated firing and infinite loops, Percolator guarantees each notification triggers an observer at most once (deduped via an ack column). This "write → notify → observer → write again" chain is the engine that "incrementally percolates changes through the index" — hence the name Percolator.
Percolator shipped as Google's web indexing system Caffeine, replacing the previous MapReduce-based batch indexing. The paper's headline result: at the same document count / same throughput, it lowered the average age of documents in search results by about 50% — roughly doubling freshness. The system runs across thousands of machines managing petabytes; the timestamp oracle reaches ~2 million timestamps per second on a single machine. The authors are candid about the cost: versus MapReduce's efficient sequential scan, Percolator does dozens of random Bigtable reads/writes per document, so its resource efficiency is markedly lower — an explicit machines-for-freshness trade.
Its significance has two layers. First, engineering: it proved that "on storage that can take the scale, add cross-row transactions + incremental notifications" is a viable path, giving Google search a freshness that was previously impossible. Second, and more lasting — it turned the "timestamp + lock columns + primary-lock 2PC" style of distributed transaction into a reproducible engineering template. Later open-source distributed databases TiKV / TiDB essentially copied Percolator's transaction model (start_ts / commit_ts, primary lock, lazy cleanup), and systems like CockroachDB were influenced by it. Many of today's "transactions across nodes" systems carry Percolator's DNA. It is also the paper in Google's "new three" that brought strongly consistent transactions back to large-scale systems — paving the way for Spanner (globally consistent transactions) two years later.
① In one sentence: add "cross-row ACID transactions + observer notifications" on top of Bigtable to turn Google's web indexing from a full MapReduce rebuild into incremental processing.
② The pain: MapReduce reprocesses the whole repository even to change one page, so new pages take days to enter the index; and no DBMS could do random transactions at that scale.
③ Transaction mechanism: give each column data/lock/write metadata columns; two-phase commit — prewrite locks (one primary, rest secondary), commit atomically turns the primary lock into a write record (the moment of effect), then cleans up secondaries; reads honor only write, so half-finished state is invisible.
④ Snapshot isolation: transactions take start_ts / commit_ts from the timestamp oracle, read a consistent snapshot, check write-write conflicts on write; the oracle batch-dispenses ~2M/sec on one machine.
⑤ Fault tolerance: no dedicated transaction manager — locks left by a crash are lazily rolled forward / back by later transactions following secondary → primary, with a Chubby-like service plus timeout deciding death.
⑥ Notification mechanism: observers register on columns; write → mark notify → workers randomly scan → run observer → write again, cascading changes through the index; each notification fires at most once (ack dedup) to avoid loops.
⑦ Results: shipped as the Caffeine indexing system, cutting average document age by ~50% (2× freshness) at the same throughput; the cost is dozens of random ops per document and low resource efficiency.
⑧ Impact: made "timestamp + primary-lock 2PC" a distributed-transaction template, directly inspiring TiKV / TiDB; paved the way for Spanner's globally consistent transactions. Limits: SI only (write skew), high per-transaction latency, timestamp oracle as a logical single point.