Along the Grand Canal stood nine imperial granaries. From Yuhang in the south to Tongzhou in the north, thousands of grain barges traversed the emerald waters, marshaling the realm’s grain taxes and commercial harvests.

Large transactions along the canal were never as simple as grain entering or leaving a single warehouse. A major merchant draft typically entangled several, or even all nine, storehouses: twenty thousand piculs of rice had to be debited across three southern granaries, while equivalent stores of wheat flour and fine salt were simultaneously credited across four northern depots.

By imperial decree, such cross-granary transfers had to “succeed as one or perish together”—if the southern silos surrendered their grain while the northern granaries failed to log delivery, merchants faced bankruptcy; if the northern granaries gained inventory without corresponding deductions from the south, tax magistrates sentenced the clerks for defrauding the imperial treasury.

In earlier years, the imperial court had attempted to prevent corruption by establishing a “Grand Register Pavilion” at the central headquarters in Huai’an.

Whenever a multi-granary transfer took place, the governor-general dispatched a chief commissary. This officer first sent carrier pigeons to the involved depots, ordering them to lock their sluices, tally current stock, and move the grain into temporary staging bays. Only after every warehouse replied that their holdings were securely sealed did the commissary dip his brush into vermillion ink and write upon the grand register in Huai’an: “Imperial Nine-Depot Transfer, Draft No. 700: Approved.” Only then did he dispatch riders bearing tokens to command the physical release.

This procedure appeared ironclad, yet it concealed a catastrophic hazard.

One harsh winter, a ferocious blizzard choked the confluence of the Yellow River and the Canal with jagged ice floes. A chief commissary, having just received confirmations that all nine depots had safely locked their staging bays, was struck down by a sudden violent fever at an overnight posthouse, falling unconscious.

In the biting cold, the warehouse keepers across nine garrisons waited. The release tokens never came. Because the staging bay gates were sealed with imperial wax, no keeper dared break them open. In the south, damp air threatened to rot mountains of rice; in the north, garrison troops faced starvation with locked storehouses in plain view. Fast couriers raced back and forth, only to report that the commissary lay in a coma and no subordinate had the statutory authority to touch the Grand Register.

For an entire month, essential stores remained frozen midway across nine garrisons. The commerce of the entire Grand Canal ground to a halt because a single official fell sick.

Old boatmen sighed along the docks: “We fear neither canal gale nor river surge; we fear only the one magistrate at headquarters collapsing. That Grand Pavilion commands nine warehouses, but when its desk jams, the whole realm turns into a headless snake.”

The governor-general posted an open bounty for a remedy. Soon, a veteran mathematician and logistics master who had served in both the Ministry of Revenue and merchant guilds stepped forward with the “Linked Anchor-Seal Method,” completely discarding the Grand Register Pavilion.

“From this day forth,” the master declared, “transfers along the canal require no resident mandarin guarding a central ledger. Let heaven and water keep the hour; let the nine granaries verify each other across the provinces.”

The brilliance of this new method rested on three interlocking rules:

First, The Celestial Sequence. At the northern terminus of the canal, a water-clock platform issued bronze tallies stamped with monotonically increasing sequence numbers. Any commissary initiating a transfer first obtained a “Commencement Tally” (start_ts) to establish the transaction’s baseline viewpoint.

Second, The Anchor and the Linked Auxiliaries. The commissary traveled to the participating depots. Rather than editing the primary ledger directly, he staged the grain inside a side bay and clamped a “Lead-Sealed Padlock” upon its latch.

Crucially, he divided the padlocks into two categories: among all the participating storehouses, he arbitrarily designated one storehouse as the Anchor (Primary), while treating all remaining depots as Auxiliaries (Secondaries).

At the Anchor granary, he hung a massive bronze “Anchor Lock,” stamped with the Commencement Tally and inscribed: “I am the primary anchor of this contract. All life and death hinge upon me.”

At each Auxiliary granary, however, the padlock bore a directive pointing outward: “I am an auxiliary lock. To discover my fate, make haste to the Anchor Granary at Garrison A and inspect the Master Seal!”

Third, Deciding Fate in a Single Stroke. Once all participating storehouses—both Anchor and Auxiliaries—had safely staged their goods and clamped their locks, the commissary requested one final token from the water-clock platform: the “Resolution Tally” (commit_ts).

The commissary was then required to visit only the Anchor Granary alone!

Before the eyes of the Anchor keeper, the commissary clicked open the bronze Anchor Lock, took up a vermillion brush, and carved deeply into the Anchor’s eternal stone ledger:

[Commencement No. X · Resolution No. Y · Anchor Contract Fulfilled]

The instant that inscription dried upon the stone and the Anchor Lock fell open—even though the eight auxiliary depots remained locked behind iron gates, even if the commissary slipped into the roaring canal and drowned the moment he walked out the door—the multi-granary transfer across all nine storehouses was irrevocably and eternally committed!

A junior clerk asked in dismay: “If the commissary drowns and the auxiliary depots remain locked, will we not plunge back into our old nightmare?”

The master laughed heartily: “It is night and day! The old nightmare occurred because the decision was imprisoned inside the living throat of one mandarin at headquarters. Today, the verdict is carved openly upon the granite of the Anchor Granary for the whole world to read!”

The following dawn, at a northern auxiliary depot, a merchant arrived to collect his grain, only to find the auxiliary padlock still hanging upon the gate and the commissary nowhere to be found.

The depot keeper did not panic. He leaned close to read the tag upon the lock: “Refer to Anchor Granary No. 2 at Yangzhou.” The keeper dispatched a carrier pigeon to check the stone stele at Yangzhou.

When the pigeon returned bearing word that Yangzhou’s stele was already carved with “Anchor Contract Fulfilled,” the northern keeper swung an iron axe, shattered the auxiliary padlock, transcribed the resolution tally into his own local ledger, and released the grain (roll forward).

Had the pigeon reported that Yangzhou’s stele was barren and the Anchor Lock had rusted away into dust, the keeper would have shattered the padlock just as readily, shoveled the staged grain back into general stock, and declared the transfer void (roll back).

Every passing merchant, every gatekeeper, every barge captain could verify the Anchor and complete the resolution with their own hands!

From that day forward, congestion vanished from the eight hundred miles of the Grand Canal. No matter how vast or intricate the transfer, it neither demanded approval from a central bureau nor feared the fragile mortality of traveling officials. The canal flowed unburdened, and nine provinces moved their wealth in effortless harmony.

—By now you’ve probably recognized it: this method of bounding visibility through celestial sequence numbers, anchoring global transactional fate within a single primary key, and enabling concurrent observers to lazily resolve secondary locks, is the celebrated distributed transaction protocol known as Google Percolator—introduced in 2010 and serving today as the architectural foundation of decentralized Two-Phase Commit (2PC) and Snapshot Isolation (SI) in modern NewSQL engines such as TiKV.

What it is

Google Percolator was introduced in 2010 by Daniel Peng and Frank Dabek in their OSDI paper, “Large-scale Incremental Processing Using Distributed Transactions and Notifications.” Designed to power Google’s web-search indexing pipeline, Percolator provided cross-row, cross-table ACID transactions with Snapshot Isolation (SI) over a non-transactional distributed key-value store (Bigtable), which natively supported only single-row atomic mutations.

Classic distributed Two-Phase Commit (2PC) relies on a centralized transaction coordinator. The coordinator must record global state transitions in persistent logs. If the coordinator crashes between the Prepare and Commit phases, participating nodes (cohorts) remain indefinitely blocked, unable to autonomously decide whether to commit or abort.

Percolator eliminates the centralized coordinator bottleneck through an elegant architectural inversion: it decentralizes transaction state into the data cells themselves and uses the atomic commitment of a single “Primary Lock” as the definitive commit point for the entire distributed transaction.

Under the hood, Percolator decomposes each cell into three distinct column families:

• data:start_ts: Stores the actual payload value, versioned by the transaction’s start timestamp start_ts.
• lock:start_ts: Holds active lock metadata. If present, it indicates an in-flight, uncommitted transaction is modifying the key.
• write:commit_ts: Records the committed transaction record, versioned by commit_ts. It stores a pointer back to start_ts, signaling to readers that the data version is officially visible.

The protocol executes in two phases:

1. Prewrite Phase:
   • The transaction client fetches a monotonically increasing start_ts from a centralized Timestamp Oracle (TSO).
   • Conflict check: For every key to be written, the client inspects the row. If any write record exists with $commit_ts > start_ts$ (write-write conflict) or if any lock exists at any timestamp (read-write conflict), the transaction aborts and retries.
   • Primary Key Designation: The client designates one arbitrary key from its write set as the Primary, treating all other keys as Secondaries.
   • Prewrite Primary: The client atomically writes data:start_ts and lock:start_ts into the Primary key (the lock designates itself as primary).
   • Prewrite Secondaries: The client writes data:start_ts and lock:start_ts for all remaining keys, embedding a pointer to the Primary key inside each secondary lock (primary_key).
2. Commit Phase:
   • The client fetches a commit timestamp commit_ts from the TSO (guaranteed $commit_ts > start_ts$).
   • Atomic Primary Commit: The client atomically writes write:commit_ts and removes lock:start_ts on the Primary key.
   • The Irrevocable Commit Boundary: The exact instant the Primary’s write record lands, the entire transaction is permanently and irreversibly committed!
   • Asynchronous Secondary Rollout: The client proceeds to write write:commit_ts and clear locks on all Secondary keys. If the client crashes at this instant, the transaction remains fully committed.
3. Conflict Resolution & Lazy Roll-Forward (Resolve Locks):
   • When a concurrent reader or writer encounters a lingering secondary lock, it never blocks waiting for an external coordinator.
   • The reader follows the embedded pointer directly to the Primary key:
     • If the Primary key already contains a valid write:commit_ts, the transaction was committed. The reader proactively rolls the secondary lock forward (Roll Forward) by writing write:commit_ts and clearing the lock.
     • If the Primary key still holds an unexpired lock, the transaction is actively progressing, and the reader briefly backs off.
     • If the Primary key has no write record and its lock has expired or been cleaned up, the originator crashed prior to committing. The reader safely rolls back (Roll Back) the secondary key by erasing the dangling data and lock.

Why it matters

Percolator is a foundational milestone in distributed systems and modern database engineering:

1. Elimination of Coordinator Vulnerability: Traditional 2PC suffers from coordinator failover complexities, catastrophic split-brain hazards, and persistent blocking states. Percolator stores transaction metadata within the distributed storage layer itself, enabling distributed transactions to inherit the massive horizontal scalability and fault-tolerance of the underlying storage engine.
2. Lock-Free Reads under Snapshot Isolation: For read transactions querying at snapshot timestamp $T$, the reader only scans for write records where $commit_ts \le T$. Readers do not take shared locks and never block concurrent writers, providing exceptional throughput for high-concurrency read-heavy workloads.
3. The Blueprint for Modern NewSQL Engines: Modern distributed NewSQL databases such as TiDB (specifically its distributed storage layer, TiKV) adopted and refined Percolator as their foundational distributed transaction protocol. TiKV pairs Percolator with Raft consensus groups for local partition high availability and introduces optimizations such as 1PC (single-region fast path) and Async Commit to eliminate extra network round-trips. Understanding Percolator’s primary lock mechanism unlocks the core mechanics of modern cloud-native transactional databases.

Metaphor mapping

• Nine imperial granaries along the Grand Canal → Distributed storage nodes and partitions (Distributed Storage Nodes / Tablets)
• Grand Register Pavilion at Huai’an headquarters → Centralized transaction coordinator in traditional 2PC (Centralized 2PC Coordinator)
• Commissary falling into a coma freezing all nine depots → The blocking problem of 2PC when coordinator crashes (2PC Blocking Problem)
• Water-clock platform issuing sequential tallies → Monotonically increasing Timestamp Oracle (TSO)
• Commencement Tally (start_ts) → Transaction start timestamp (start_ts)
• Resolution Tally (commit_ts) → Transaction commit timestamp (commit_ts)
• Staging grain inside side bays during prewrite → Writing uncommitted payload into data column (data:start_ts)
• Clamping lead-sealed padlocks onto staging bays → Acquiring row-level locks during prewrite (lock:start_ts)
• Designating one Anchor Granary with a bronze Anchor Lock → Selecting an arbitrary key as the Primary Lock (Primary Key / Primary Lock)
• Auxiliary locks pointing back to the Anchor Granary → Secondary locks carrying pointers to the primary key (Secondary Lock with primary_key pointer)
• Carving vermillion inscription on Anchor stele and releasing Anchor Lock → Atomically writing write:commit_ts and clearing primary lock (Atomic Primary Commit)
• Transaction committed instantly even if commissary drowns → Irrevocable commit boundary anchored solely at the primary key (Primary Commit Boundary)
• Visiting merchants and keepers checking Anchor stele to cut auxiliary locks → Concurrent readers performing lazy roll-forward (Resolve Locks / Roll Forward)
• Clearing staged grain when Anchor stele is empty and lock rusted → Autonomous rollback of abandoned transactions (Roll Back)