Latch Coupling and Deadlock Avoidance in the Buffer Pool

A storage engine’s in-memory structures are read and written by dozens of threads, and the primitive that protects them is not the transaction lock manager. Transaction locks are held for the duration of a transaction, are tracked in a table keyed by row or table, are subject to deadlock detection, and may be held across I/O. Latches are held for the duration of an in-memory operation, are usually embedded in the structure they protect, are never waited on for long, and must be released before any I/O is issued. Mixing the two, or using one where the other is needed, produces either a performance collapse or a deadlock that no detector can resolve.

Two primitives, two lifetimes

The distinction is worth stating as a rule because it determines the shape of every code path. A transaction lock protects a logical resource — a row, a table, a key range — and exists so that the transaction’s effects are serializable. It may be held for seconds, across network round trips and disk reads. A latch protects a physical structure — the bytes of a page, the buckets of a hash table, a pointer in a tree — and exists so that concurrent readers and writers do not observe a partially updated structure.

The lifetime rule follows: a latch must never be held across an I/O operation. A thread that holds a page latch and issues a read blocks every other thread that needs that page, for a duration measured in microseconds on flash and milliseconds on rotating media. If the read itself needs the buffer pool, and the pool needs the hash-table latch, and the hash-table latch is held by a thread waiting for the page latch, the result is a deadlock that involves no transaction at all.

Engines enforce this by structuring every page access as: latch, examine, decide, copy what is needed into local storage, unlatch, then do I/O. The copy is the price of the rule, and it is why page-oriented engines copy tuples out of pages rather than returning pointers into them. A pointer into a page is valid only while the latch is held, and almost no caller can keep a latch held for its whole lifetime.

Lock coupling on a descent

The B-tree descent is the place where the latch protocol is most visible, because the naive version deadlocks. Thread A latches the root, finds the child, and tries to latch the child. Thread B has latched the child — perhaps to split it — and now needs the root to insert a separator. Each holds what the other needs.

Lehman and Yao’s protocol removes the need for a thread to ever latch a page above the one it currently holds. Each page carries a right-link and a high key, and the descent works like this: latch the current page, read the child pointer, latch the child, then release the current page. The two latches are held simultaneously only for the duration of the handoff — that is lock coupling — and the order is always parent before child, never the reverse.

A split under this protocol is a sequence of steps that never requires going back up:

1. Latch the full page exclusively.
2. Allocate a new page, latch it, copy the upper half, set its high key and right-link to the current page’s right neighbour.
3. Set the current page’s right-link to the new page, and lower its high key.
4. Release the new page and the current page.
5. Later, in a separate operation, insert the separator and pointer into the parent.

Step 5 is the concession. The parent is not latched during the split, so the tree is temporarily in a state where a search that descends through the parent will not find the new page. The high key and right-link make that state recoverable: a search that lands on the current page and finds the search key above the high key follows the right-link to the new page. The structure is always searchable; it is only the parent’s pointer that lags.

/* Lock coupling: at most two latches held, always parent then child. */
node_t *descend(node_t *root, key_t k) {
    node_t *cur = root;
    latch_shared(cur);
    while (!is_leaf(cur)) {
        node_t *next = child_for(cur, k);   /* may be stale under a concurrent split */
        latch_shared(next);
        latch_release(cur);                 /* handoff complete; no going back */
        cur = next;
        while (cur->high_key < k) {         /* split moved our target rightwards */
            node_t *right = cur->right_link;
            latch_shared(right);
            latch_release(cur);
            cur = right;
        }
    }
    return cur;
}

The inner loop is what makes the protocol correct rather than merely deadlock-free. Without it, a search that read the parent before the split would descend to a page that no longer contains the key and would report a false negative. With it, the search repairs itself by following links, and the repair costs one extra latch acquisition in the rare case.

Optimistic descent and the read-mostly case

Lock coupling still acquires a latch at every level, which is two atomic operations and two potential cache-line transfers per level. For a read-mostly index, most of that work is unnecessary: the page contents do not change between the read of the child pointer and the latch of the child.

Several engines therefore offer an optimistic protocol. The reader reads the child pointer and a version counter from the page without latching, latches the child, and then re-reads the parent’s version counter. If it is unchanged, the pointer was stable and the descent continues. If it changed, the reader restarts from the parent. The version counter is incremented on every modification and is typically a 64-bit word to avoid wraparound in practice.

The benefit is that the common case takes one latch per level instead of two, and the parent latch is never contended. The cost is a restart path that must be correct, and the restarts are frequent enough under heavy insert load that the optimistic path can be slower than lock coupling. This is why engines tend to make the choice per operation — optimistic for lookups, pessimistic for modifications — rather than globally.

Partitioning the buffer pool

The buffer pool’s hash table is the other concentration of contention. Every page access begins with a lookup, so the table’s lock is acquired at the rate of the workload’s page accesses, and a single lock over a table with thousands of buckets becomes the engine’s hottest cache line.

The standard fix is partitioning: the table is split into N independent sub-tables, each with its own lock and its own bucket array, and a page identifier is assigned to a partition by hashing its high bits. A thread contends only with threads touching pages in the same partition. With N equal to the number of cores or a small multiple, the contention probability drops by roughly a factor of N, and the hash-table lock stops appearing in profiles.

Partitioning has three consequences that are easy to overlook. The replacement policy now operates per partition, so the clock hand sweeps each partition independently and a globally hot page in a cold partition is not protected by the global access pattern. The free-frame list must be shared, which reintroduces a global structure — usually as a lock-free stack or a per-partition free list with stealing. And a page’s partition is fixed by its identifier, so a workload that concentrates on a narrow key range concentrates on a few partitions, which defeats the partitioning exactly when the contention is highest.

Deadlock among latches

Latch deadlocks are rare but real, and they are not handled by the transaction deadlock detector, which does not know about latches. Three patterns produce them.

The first is lock-order inversion between two structures, such as the buffer pool hash table and the free-frame list, taken in different orders by the miss path and the eviction path. The remedy is a documented global order and a rule that no path takes them in the other order.

The second is a page-level cycle created by a transaction that needs two pages. An update that moves a tuple from page A to page B holds a latch on A and needs one on B, while another transaction does the reverse. Ordering page latches by ascending page identifier prevents the cycle, at the cost of forcing a specific acquisition order that may not match the traversal order.

The third is the interaction with transaction locks: a thread holds a row lock and waits for a page latch held by a thread that is waiting for the row lock. This is a genuine deadlock across two subsystems, and the only reliable defence is that latches are never held while waiting for a lock. The rule is easy to state and easy to violate in a code path that takes a lock inside a page-level callback.

Measuring contention rather than guessing

The observable signature of latch contention is not low throughput but non-linear scaling: doubling the threads does not double the work, and the per-operation cost rises with concurrency. The measurement that identifies it is the time a thread spends spinning or waiting on a latch, attributed to the specific latch, which requires instrumenting each latch rather than aggregating.

Two counters per latch suffice: the number of times it was acquired without contention, and the number of times a thread had to wait. The ratio is the contention rate, and the absolute wait time tells whether it matters. A latch with a high contention rate and negligible wait time is not a problem; a latch with a low rate and long waits indicates a thread holding it across something slow, which is a bug rather than a tuning issue.

The mechanisms described here sit underneath the page replacement policy in buffer pool frames and pinning, and the split operation whose cost they govern is analyzed in B-tree page splits. A latch held too long also lengthens the window in which a page cannot be evicted, which is the pin-pressure failure mode described there.