Percolator

Every time you search on Google you get results that were crawled, indexed, and ranked just seconds or minutes ago. That near-real-time freshness did not come for free. For years, Google's web-crawl pipeline was a batch job: crawl the web, process everything offline, swap in the new index every few days. Pages changed faster than the pipeline could keep up.

In 2010, engineers Daniel Peng and Frank Dabek published Percolator, a system that replaced the batch pipeline with incremental updates. The key insight: wrap every tiny update — re-index one changed page, propagate one link change — in a full ACID transaction layered on top of the existing distributed key-value store (Bigtable). No locks held across machines for long, no coordinator bottleneck, yet every reader sees a consistent snapshot of the entire index.

The mechanism that makes it all work is called snapshot isolation with two-phase commit: a simple timestamp oracle hands every transaction a globally unique timestamp, and two carefully chosen key-value writes (a lock row and a write row) implement commit atomically.

The demo below animates a single Percolator transaction updating three key-value rows. Each row has three column families: data (the actual value), lock (the 2PC lock), and write (committed timestamps). Step through each phase to see how the timestamp oracle and the primary-lock pattern guarantee atomicity without a central coordinator.

<!-- {{c_html_intro}} -->
<div class="layout">
  <div class="controls">
    <p class="hint">{{hint_para}}</p>
    <div class="oracle-box">
      <span class="oracle-label">{{oracle_label}}</span>
      <span id="ts-display" class="ts-val">—</span>
    </div>
    <div class="btns">
      <button id="btn-begin" type="button">{{btn_begin}}</button>
      <button id="btn-prewrite" type="button" disabled>{{btn_prewrite}}</button>
      <button id="btn-commit" type="button" disabled>{{btn_commit}}</button>
      <button id="btn-cleanup" type="button" disabled>{{btn_cleanup}}</button>
      <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
    </div>
    <div id="status" class="status"></div>
    <div id="log" class="log"></div>
  </div>
  <div class="kv-panel">
    <h3 class="panel-title">{{kv_title}}</h3>
    <table id="kv-table">
      <thead>
        <tr>
          <th>{{col_key}}</th>
          <th>{{col_data}}</th>
          <th>{{col_lock}}</th>
          <th>{{col_write}}</th>
        </tr>
      </thead>
      <tbody id="kv-body"></tbody>
    </table>
  </div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #1a1a2e; margin: 0; font-size: 14px; }
.layout { display: flex; flex-direction: column; gap: .8rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.5; }
.oracle-box { display: flex; align-items: center; gap: .5rem; margin-bottom: .5rem;
              background: #eef2ff; border: 1px solid #c7d2fe; border-radius: 8px; padding: .35rem .7rem; }
.oracle-label { font-size: .8rem; font-weight: 600; color: #4338ca; text-transform: uppercase; letter-spacing: .04em; }
.ts-val { font: 700 1.1rem ui-monospace, monospace; color: #1d3557; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; transition: opacity .15s; }
button:disabled { opacity: .35; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
button.primary { background: #4338ca; border-color: #4338ca; }
.status { font-weight: 600; font-size: .95rem; min-height: 1.4em; margin-bottom: .3rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.log { font-size: .78rem; color: #555; line-height: 1.7; max-height: 90px; overflow-y: auto;
       border-left: 3px solid #c7d2fe; padding-left: .5rem; }
/* {{c_css_table}} */
.panel-title { font-size: .85rem; font-weight: 700; margin: 0 0 .4rem; text-transform: uppercase;
               letter-spacing: .05em; color: #4338ca; }
#kv-table { width: 100%; border-collapse: collapse; font-size: .82rem; }
#kv-table th { background: #e8eef3; color: #1d3557; font-weight: 700; padding: .3rem .5rem;
               text-align: left; border: 1px solid #cdd9e3; }
#kv-table td { padding: .28rem .5rem; border: 1px solid #dde3eb; vertical-align: top; }
#kv-table tr.primary-row td:first-child { font-weight: 700; color: #4338ca; }
#kv-table td.cell-lock { color: #c92f3c; font-style: italic; font-size: .78rem; }
#kv-table td.cell-write { color: #0a7d33; font-size: .78rem; }
#kv-table td.cell-data { font-family: ui-monospace, monospace; }
#kv-table tr.highlight td { background: #fef9c3; transition: background .4s; }

// Code not found

Notice that Prewrite acquires a lock on the primary row first, then each secondary row — if the process crashes mid-way, any reader that finds a lock can check whether the primary lock is still there and decide whether to roll back or roll forward. Commit is just two writes: remove the primary lock and write the commit timestamp. Once the primary lock is gone, the transaction is durable even before the secondary locks are cleaned up.

Percolator's elegance comes from reducing the hardest part of distributed transactions — conflict detection and commit ordering — to a handful of column-family conventions:

• Timestamp oracle: a single server that hands out strictly increasing timestamps. Every transaction gets a start timestamp $T_s$ when it begins and a commit timestamp $T_c > T_s$ when it commits. Because $T_s < T_c$, a reader at $T_s$ can never see the writes of a transaction that started after it, giving snapshot isolation for free.
• Two phases of Percolator's commit:
  1. Prewrite: for each row being written, store the new value in the data column at $T_c$ and write a lock record in the lock column pointing back to the primary row. If any row already has a lock or a newer write, abort.
  2. Commit: write a write record on the primary row at $T_c$ pointing to the data, then delete the primary lock. This single atomic Bigtable write is the commit point — it cannot be split.
• Lock cleanup: if a transaction crashes after prewrite but before commit, its locks linger. Any later transaction that hits a stale lock checks the primary: if the primary lock is gone, the transaction committed and the cleaner can finish the secondary writes; if the primary lock is still there and old enough, the transaction can be rolled back by deleting all its locks.

The result is a system with no lock manager, no two-phase locking, and no central coordinator beyond the timestamp oracle — yet it provides the same guarantees as a classic serializable database for the incremental-indexing workload. The oracle is the only bottleneck, and Peng & Dabek showed it can serve tens of thousands of timestamps per second on a single machine.

Compare this to the naive alternative: global P vs NP-flavored brute-force conflict checking would require comparing every new write against every in-flight transaction — $O(n^2)$ work that simply does not scale to billions of rows.

Percolator's timestamp-oracle + column-family pattern became a blueprint for the next decade of distributed databases:

• Google Spanner (2012) generalizes Percolator's timestamp oracle to a globally distributed TrueTime clock, enabling external consistency across data centers.
• TiKV / TiDB (PingCAP) implements Percolator's exact 2PC protocol over RocksDB, making it the heart of one of the most widely used open-source HTAP databases.
• CockroachDB uses a closely related timestamp-based MVCC approach derived from the same ideas.
• Incremental pipelines everywhere: the notify-on-change model (an observer registers interest in a cell; Percolator triggers it on writes) is now the standard pattern for streaming data-processing systems like Apache Flink and Google Dataflow.

The core lesson — encode your concurrency protocol as data, not as a lock manager — is one of the most powerful ideas in systems design. It turns a hard distributed-coordination problem into a few carefully ordered key-value writes that any storage engine can handle.

Learn Percolator and you have understood the foundation shared by PageRank (which Percolator was originally built to re-compute incrementally) and modern cloud-native databases alike.

Percolator is a masterclass in reducing a hard problem to simpler primitives. The hard problem — keeping a petabyte-scale index consistent while thousands of workers update it in parallel — becomes tractable once you realize that snapshot isolation needs only two things: a source of ordered timestamps and an atomic "is the primary lock gone?" check.

Everything else — conflict detection, crash recovery, distributed atomicity — falls out of those two primitives and a disciplined column-family layout. The batch pipeline disappears; every crawled page flows through as an individual transaction, and the index is always fresh.

That is the promise Peng and Dabek delivered in 2010, and it is the same promise that powers distributed databases from San Francisco to Shanghai today — one timestamp at a time.