Locks and latches: the distinction that has to come first
Why does every database need two protection mechanisms, and where do phantoms come from?
Why does every database have two protection mechanisms instead of one?
The answer is duration.
- A transaction lasts an unbounded time. It may wait for a disk, for the network, even for a human clicking a button.
- A data-structure modification lasts a tiny and bounded time. Splitting an index node takes a few hundred nanoseconds.
Anything held for an unbounded time must be tracked. You need to detect cycles among holders, release everything if the transaction aborts, and answer the question "who holds this?". Tracking means a lock manager: a hash table keyed by item, where each lock entry is roughly 100 bytes (the mode, the list of owners, the queue of waiters) and acquiring one takes 100–200 ns.
Anything held for nanoseconds cannot afford tracking, because the bookkeeping would cost more than the operation it protects. A latch is one word of memory and one CAS, about 20 ns when uncontended, with no metadata at all.
Why this is not a style choice: do the arithmetic. A four-level B-tree (index) descent under logical locking would allocate one lock entry per level, so four lock entries per read. A point lookup that returns a 200-byte tuple would create 4 × 100 = 400 bytes of lock-manager state. The metadata outweighs the data. So the physical structure must have its own, untracked protocol. An untracked protocol cannot detect deadlock, so it must prevent deadlock by construction, with a fixed global order of acquisition. That is exactly what latch coupling is.
| Locks | Latches | |
|---|---|---|
| Held by | Transactions | Threads |
| Protect | Logical contents (rows, ranges) | Physical structures (index nodes, buffers) |
| Duration | The whole transaction (unbounded) | Nanoseconds |
| Tracked? | Yes, in the lock manager | No |
| Deadlock | Detected | Prevented by ordering |
| Rollback | Released and undone on abort | Cannot roll back |
Where the two protocols meet, badly: phantoms
Consider a logical lock on "all rows where salary > 100000". You cannot put a lock on rows that do not exist yet. But inserting a row is a physical structure modification, protected by latches and invisible to the lock manager.
A phantom is a row that appears (or disappears) between two reads of the same predicate inside one transaction. This is exactly what happened to Tomas's count(*): 41, then 43. Every fix for phantoms (predicate locks, next-key locks, SSI's SIREAD locks, all explained below) is an attempt to make a physical event visible to the logical protocol.
Index concurrency: how the physical side stays safe
Because phantoms live at this seam, we need to see how index structures are protected. Three approaches:
- Latch coupling (also called crabbing). To go down the tree, take the child's latch before releasing the parent's, like a crab moving one leg at a time. The "safe node" optimization releases all ancestors as soon as the current node is known not to split (it has room), because then no change can climb back up.
- Optimistic lock coupling (used in ART, OLFIT and the Bw-tree). Instead of latching, read a version counter on the node, do the work, then re-validate that the counter did not change. This is OCC applied one level down, which shows that the choice between optimism and pessimism is scale-free: it appears at every size.
- B-link trees. Add a right-link from every node to its right neighbour, so that a node split is legal even in its half-finished state. A reader who arrives at a stale node simply follows the link. This is the "make the intermediate state legal instead of preventing it" move. You will see the same idea again in data types that merge without coordination (CRDTs, mentioned in Multiversion and optimistic schemes).
Duration decides mechanism: anything held longer than it costs to track must be tracked, and phantoms live in the seam between the tracked and the untracked.