Introduction

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.

Try It

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.

<!-- Percolator 2PC demo: Begin → Prewrite → Commit → Cleanup -->
<div class="layout">
  <div class="controls">
    <p class="hint">Step through a Percolator transaction: <b>Begin</b> gets a start timestamp, <b>Prewrite</b> locks all rows (primary first), <b>Commit</b> writes the commit record and releases the primary lock, then <b>Cleanup</b> releases secondary locks.</p>
    <div class="oracle-box">
      <span class="oracle-label">Timestamp oracle:</span>
      <span id="ts-display" class="ts-val">—</span>
    </div>
    <div class="btns">
      <button id="btn-begin" type="button">1. Begin</button>
      <button id="btn-prewrite" type="button" disabled>2. Prewrite</button>
      <button id="btn-commit" type="button" disabled>3. Commit</button>
      <button id="btn-cleanup" type="button" disabled>4. Cleanup</button>
      <button id="btn-reset" type="button" class="ghost">Reset</button>
    </div>
    <div id="status" class="status"></div>
    <div id="log" class="log"></div>
  </div>
  <div class="kv-panel">
    <h3 class="panel-title">Key-Value Store</h3>
    <table id="kv-table">
      <thead>
        <tr>
          <th>Row key</th>
          <th>data</th>
          <th>lock</th>
          <th>write</th>
        </tr>
      </thead>
      <tbody id="kv-body"></tbody>
    </table>
  </div>
</div>

/* Layout and styling for the Percolator demo */
* { 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; }
/* KV table styling */
.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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Percolator-style 2-phase commit over a tiny in-memory KV store
// Three rows: one primary, two secondaries — same structure as the paper

const ROWS = [
  { key: 'page:google.com', isPrimary: true,  oldVal: 'rank=5',  newVal: 'rank=7' },
  { key: 'page:maps.google.com', isPrimary: false, oldVal: 'rank=3',  newVal: 'rank=4' },
  { key: 'page:mail.google.com', isPrimary: false, oldVal: 'rank=4',  newVal: 'rank=4' }
];

// Transaction state machine: idle → begun → prewrote → committed → done
let state = { phase: 'idle', startTs: null, commitTs: null, ts: 10 };
// In-memory KV store: each row has data, lock, write columns
let kv = ROWS.map(r => ({ key: r.key, data: r.oldVal, lock: '', write: '' }));

const $ = id => document.getElementById(id);
const btns = { begin: $('btn-begin'), prewrite: $('btn-prewrite'), commit: $('btn-commit'), cleanup: $('btn-cleanup'), reset: $('btn-reset') };

function setEnabled(map) {
  // Enable/disable buttons based on current phase
  Object.entries(btns).forEach(([k, el]) => { el.disabled = !(map[k]); });
}

function setStatus(txt, cls) {
  const el = $('status'); el.textContent = txt; el.className = 'status ' + (cls || '');
}

function log(msg) {
  // Append a line to the transaction log
  const el = $('log');
  const line = document.createElement('div');
  line.textContent = msg;
  el.appendChild(line);
  el.scrollTop = el.scrollHeight;
}

function renderKV(highlightKeys) {
  // Render the KV table, optionally highlighting rows that just changed
  const tbody = $('kv-body'); tbody.innerHTML = '';
  kv.forEach((row, i) => {
    const tr = document.createElement('tr');
    if (ROWS[i].isPrimary) tr.className = 'primary-row';
    if (highlightKeys && highlightKeys.includes(row.key)) tr.className += ' highlight';
    tr.innerHTML =
      `<td>${row.key}</td>` +
      `<td class="cell-data">${row.data}</td>` +
      `<td class="cell-lock">${row.lock}</td>` +
      `<td class="cell-write">${row.write}</td>`;
    tbody.appendChild(tr);
  });
}

function updateTsDisplay() {
  $('ts-display').textContent = state.ts;
}

// Phase 1: ask the timestamp oracle for a start timestamp
function doBegin() {
  state.phase = 'begun';
  state.startTs = ++state.ts;
  state.commitTs = null;
  updateTsDisplay();
  log(fmt('▶ Begin Ts= %startTs%', { startTs: state.startTs }));
  setStatus('Transaction started — ready to prewrite.', 'info');
  setEnabled({ prewrite: true, reset: true });
  renderKV();
}

// Phase 2: lock all rows (primary first), write tentative values
function doPrewrite() {
  state.phase = 'prewrote';
  state.commitTs = ++state.ts;
  updateTsDisplay();
  // Lock and write primary row first
  kv[0].data = ROWS[0].newVal + '@' + state.commitTs;
  kv[0].lock = fmt('primary@%commitTs%', { commitTs: state.commitTs });
  log(fmt('🔒 Prewrite primary lock on %key%', { key: kv[0].key }));
  // Lock and write each secondary row
  for (let i = 1; i < kv.length; i++) {
    kv[i].data = ROWS[i].newVal + '@' + state.commitTs;
    kv[i].lock = fmt('secondary→%key%@%commitTs%', { key: ROWS[0].key, commitTs: state.commitTs });
    log(fmt('🔒 Prewrite secondary lock on %key%', { key: kv[i].key }));
  }
  setStatus('All rows locked — ready to commit.', 'info');
  setEnabled({ commit: true, reset: true });
  renderKV(kv.map(r => r.key));
}

// Phase 3: write commit record on primary, clear primary lock — this is the atomic commit point
function doCommit() {
  state.phase = 'committed';
  // Single atomic write: write record + unlock primary
  kv[0].write = fmt('committed@%commitTs%→data@%commitTs%', { commitTs: state.commitTs });
  kv[0].lock = '';
  log(fmt('✅ Commit point — primary lock cleared on %key% Tc=%commitTs%', { key: kv[0].key, commitTs: state.commitTs }));
  setStatus('Committed! Primary lock gone — transaction is durable.', 'ok');
  setEnabled({ cleanup: true, reset: true });
  renderKV([kv[0].key]);
}

// Phase 4: asynchronously clear secondary locks (can be deferred)
function doCleanup() {
  state.phase = 'done';
  for (let i = 1; i < kv.length; i++) {
    kv[i].write = fmt('committed@%commitTs%→data@%commitTs%', { commitTs: state.commitTs });
    kv[i].lock = '';
    log(fmt('🧹 Cleanup secondary lock on %key%', { key: kv[i].key }));
  }
  setStatus('Done. All locks cleaned up.', 'ok');
  setEnabled({ reset: true });
  renderKV(kv.slice(1).map(r => r.key));
}

function doReset() {
  state = { phase: 'idle', startTs: null, commitTs: null, ts: state.ts };
  kv = ROWS.map(r => ({ key: r.key, data: r.oldVal, lock: '', write: '' }));
  $('log').innerHTML = '';
  $('ts-display').textContent = '—';
  setStatus('', '');
  setEnabled({ begin: true });
  renderKV();
}

btns.begin.addEventListener('click', doBegin);
btns.prewrite.addEventListener('click', doPrewrite);
btns.commit.addEventListener('click', doCommit);
btns.cleanup.addEventListener('click', doCleanup);
btns.reset.addEventListener('click', doReset);

// Initialize: only Begin is enabled at start
setEnabled({ begin: true });
renderKV();
Result
Console

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.

The Real Complexity

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 TsT_s when it begins and a commit timestamp Tc>TsT_c > T_s when it commits. Because Ts<TcT_s < T_c, a reader at TsT_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 TcT_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 TcT_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(n2)O(n^2) work that simply does not scale to billions of rows.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/percolator/Content licensed under CC BY-NC 4.0.