Concepts
Distributed transactions with snapshot isolation on storage with row-only atomicity (Percolator)
Intuition
Imagine a giant spreadsheet that many people edit at the same time, where the only guarantee is that each row, on its own, changes all at once. To change several rows as if they were one, you stick a reservation note on each of them and pick one of the notes as the main one; only when all rows are reserved do you flip the main note, and it is that flip that makes the change take effect for everyone. Anyone who only wants to read looks at the spreadsheet as it was at a fixed instant, so they never see half of the change; and if whoever was making the change disappears midway, the main note shows anyone else whether the change took effect or not.
How it works
Bigtable only offers atomicity within a single row, so Percolator, a client library, adds multi-row and multi-table transactions with snapshot isolation. For transactions, each Percolator column uses three Bigtable columns (data, lock and write; the paper also lists notify and ack, used by observers), with cells versioned by timestamp; an oracle provides strictly increasing timestamps, and each transaction reads at a start timestamp and writes at a later commit timestamp. Writes are buffered until commit, which is two-phase and client-coordinated: in the prewrite, the transaction tries to lock all written cells, picks one of them as the primary, and aborts if it finds a write record later than its start timestamp or any lock; otherwise it writes the data and the lock, and each secondary lock stores the location of the primary. In the second phase, it obtains the commit timestamp and replaces the primary's lock with a write record that points to the data, and this swap, done in a Bigtable row transaction, is the commit point; it then does the same on the secondaries. Because any timestamp represents a consistent snapshot, reads don't need to acquire locks: a Get() only checks whether there is a lock in the snapshot's visible range and, if there is, waits; otherwise, it reads the latest visible write. If the client crashes in the middle of a commit, another transaction that runs into the abandoned lock inspects the primary: if it has already become a write record, it rolls the commit forward; otherwise, it rolls back, which is safe because the primary is always committed first and because both cleanup and commit must modify the primary, each inside a Bigtable row transaction, so only one of the two succeeds. If two concurrent transactions write to the same cell, at most one commits, but this is snapshot isolation and not serializability, so it is subject to write skew. There is no central transaction manager or global deadlock detector, and lazy lock cleanup can delay a commit by tens of seconds.
In practice
The paper applies this technique to Google's indexer, where invariants across many rows (such as URL duplicates and link inversion) must be maintained while new pages arrive. It makes sense to choose it when you need cross-row atomicity on a store that scales a lot but only has per-row atomicity, the workload tolerates higher latency, and write skew doesn't threaten the invariants. The cost is measured in the paper: a single-cell write, the worst-case overhead for Percolator, has an overhead of about four times over plain Bigtable in a benchmark with a single tablet server, cached data, and batching optimizations turned off, not counting the cost of getting timestamps from the oracle, because of the extra commit operations (read to check locks, write the lock, and then remove it), of which the read is the most expensive.
Use it in a design
Practice the cases that rely on this concept in the System Design school.