Latches vs Locks: Protecting the Tree vs Protecting Data

Open the Postgres source code and search for the word lock. You will find at least four different things called locks, three of which are not locks in the sense the rest of this chapter cares about. There is LWLock, which is a lightweight lock — a latch, really, under a different name. There is HeavyweightLock, which is the one that protects a row for the duration of a transaction. There is the buffer pool's content_lock on each frame — also a latch. There is advisory locking, predicate locking, row-level pinning — every one of them is called a lock somewhere, and half of them are not what a textbook means by lock.

This chapter is about pulling the two real concepts apart and putting each one in its place. You have a B+ tree from chapter 23 and a buffer pool from chapter 24. You are about to let more than one thread use them at the same time. Two mechanisms are about to show up, and you need to know which is which before the first race condition ruins an afternoon.

Same word, two jobs

Consider one SQL statement from the database's point of view.

UPDATE accounts SET balance = balance - 100 WHERE id = 17;

Under the hood, this expands into roughly the following sequence. Find row 17 in the accounts table. Read its balance. Compute the new balance. Write it back. Commit the transaction.

"Find row 17" is a B+ tree lookup. The tree has a root page, a second-level internal page, a third-level internal page, and a leaf page. The thread has to read those four pages. If any of those pages is being modified right now by another thread — perhaps a concurrent insert that is splitting a leaf — the reading thread must not see the page mid-modification. That protection is the job of a latch. The latch is acquired when the thread pins the page in the buffer pool, held for as long as the thread is reading bytes out of the page, and released as soon as the thread moves on to the next page. Total lifetime: a few microseconds.

"Compute the new balance. Write it back. Commit" is a logical transaction. The user expects that no other transaction's update to row 17 can interleave with this one in a way that violates isolation — if two users simultaneously deduct 100 from an account that starts at 500, the result had better be 300, not 400. That protection is the job of a lock on row 17. The lock is acquired the first time the transaction touches the row, held for the entire duration of the transaction, and released only at commit (or rollback). Total lifetime: the length of the transaction — usually milliseconds, sometimes many seconds, occasionally minutes.

Two different mechanisms, guarding two different kinds of invariant. The latch is there so that the bytes of a B+ tree page cannot be read while they are being written; without it, a reader could see a key listed twice (because the writer is halfway through a split), or segfault trying to follow a freshly rewritten pointer. The lock is there so that two users' transactions cannot interleave in a way that violates their intuition about what the balance should be.

Why do we need both? A lock on row 17 held from the start of the transaction to COMMIT keeps other transactions out of row 17 — but while this transaction is descending the tree to find row 17, what keeps the tree itself consistent against a different transaction that is inserting row 4,900,000 at the same time? That different transaction may be splitting the very same internal node this transaction is currently traversing. The lock on row 17 says nothing about the internal node — which is a purely physical object the user cannot even reference. A second, much shorter, much lower-level mechanism is needed for that: the latch. Latches protect physical data structures; locks protect logical data. The two populations do not overlap.

Four axes of difference

Pull the two mechanisms apart along four axes and the distinction clarifies fast.

The rows that deserve unpacking are the middle three: API, modes, deadlock treatment.

API. A latch is code you write inside the storage engine. Every function that reads a page starts with page.latch(SHARED) and ends with page.unlatch() — the bracket is tight around the critical section. The B+ tree's own implementer writes these calls; the user, the SQL planner, the application code never see them. A lock is the opposite: the transaction manager acquires a lock on row 17 implicitly, the moment the executor reads or writes row 17, and releases it implicitly at COMMIT. The user's SQL never says LOCK row 17; the lock manager sees the UPDATE and synthesises the lock. (SQL does let you name locks with SELECT ... FOR UPDATE or LOCK TABLE, but these are the transaction manager's API exposed to the user, not the storage engine's latch API.)

Modes. Latch modes are almost always binary — shared (many readers, no writer) or exclusive (one writer, no readers). That is enough because the critical section is tiny; adding more modes buys no useful compatibility. Lock modes are a zoo, because the critical section is an entire transaction and there are many distinct scenarios to optimise for. S and X are the base. U (update) is "I am going to read then write" — compatible with other readers but conflicts with another U or X; it avoids a two-phase upgrade from S to X that is a deadlock magnet. IS (intent-shared) and IX (intent-exclusive) are hierarchical locks that live on tables and ranges to say "I hold S or X on some row inside here, do not place an X lock on the whole table". The hierarchy — database, table, page, row, with intent locks on the upper levels — lets a single lock table hold locks of very different granularities without enumerating them.

Deadlock treatment. This is the sharpest contrast, and the one that drives the design of latch crabbing below.

A lock deadlock is unavoidable in the general case. Two transactions each hold one lock and want the other's. The system has no way to prevent it a priori — the lock acquisitions are driven by the user's SQL, which the database has no control over. So it lets deadlocks happen and detects them: a wait-for graph is maintained, a cycle detector runs periodically (or on-demand when a wait times out), and when a cycle is found, one transaction is chosen as the victim and aborted; its locks are released; the surviving transaction proceeds. Detection costs CPU and the victim loses work, but it is tractable because transaction starts are rare enough (thousands per second, not millions) that the graph is small.

A latch deadlock cannot be tolerated at all. Latches are held in the nanosecond-to-microsecond window; any deadlock detector that runs at that scale would cost more than the latches it protects. So latches use lock-ordering — a strict global rule about the order in which any two latches may be acquired, enforced by convention. In a B+ tree the rule is: latches are always acquired top-down, never bottom-up. Any thread that wants to latch the root and then a leaf acquires the root first. Any thread that wants to latch a leaf and then a parent never does. If the rule is followed, a cycle is structurally impossible: there is no pair of latches A and B where one thread holds A and wants B while another holds B and wants A, because top-down means the order (A, B) is always the same across all threads. The rule is cheap (free at runtime) and leaves no room for dynamic detection — it is enforced at code review.

Why does lock-ordering work for latches but not for transaction-level locks? Because the storage engine's code paths are small, well-known, and owned by the database implementer. The set of pages a single storage-engine call touches is bounded and can be arranged in a global order by construction. A transaction, on the other hand, runs arbitrary user SQL — which rows it touches is data-dependent and not known until runtime. There is no way to enforce a global order over "row 17 and row 92" because neither the user nor the database knows ahead of time which one the transaction will see first. So transaction locks get deadlock detection; latches get discipline.

Latch crabbing — the minimum set of latches

Here is the specific algorithm that makes the top-down ordering rule work in a B+ tree under concurrent reads and writes. It is called latch crabbing (or latch coupling), and the name comes from how a crab walks along a branch — two claws at a time, one foot always holding on.

The problem. A thread is inserting key 20 into a B+ tree. It descends from the root to the leaf. At the leaf, it may need to split. If the split happens, it needs to modify the parent — promoting the median into the parent's key list. If the parent overflows, it needs to modify the grandparent. In the worst case the cascade reaches the root. While this is happening, the thread must hold exclusive latches on every node from the leaf up to the point where the cascade stops, because any concurrent reader that visited those nodes mid-split would see a half-written key list.

The naive solution is: on descent, take an exclusive latch on every node you pass. Hold them all the way to the leaf. If the leaf splits, cascade up; when the cascade stops, release everything. This is correct. It is also catastrophically bad for concurrency: the root is latched exclusively for the entire duration of every insert, so only one insert at a time makes progress. The root becomes the bottleneck for a thousand-thread workload.

The crabbing solution is: release the parent's latch as soon as you know the current node is safe — where safe means "this insert cannot possibly propagate a split up past this node."

Formally, on the descent, a node is safe for an insert if it has at least one free slot (so even if every descendant splits, the new key fits here without overflowing). A node is safe for a delete if it has more than the minimum number of keys (so even if a descendant underflows and merges, this node will still be above the minimum). If the current node is safe, you can release every latch you are holding on its ancestors — because whatever happens below cannot travel up past a safe node. If it is not safe, you must hold the ancestor's latch, because a cascade might reach it.

The algorithm, in pseudocode:

# Crabbing descent for an insert. Latches acquired in EXCLUSIVE mode since we are modifying.

def insert_crabbing(tree, key, value):
    held = []                          # stack of latched nodes, root at bottom
    node = tree.root
    latch_X(node); held.append(node)

    while not node.is_leaf:
        # pick child that covers key
        i = route(node, key)
        child = node.children[i]
        latch_X(child)

        if is_safe_for_insert(child):
            # child will absorb any split from below; ancestors are no longer at risk
            for a in held:
                unlatch(a)
            held = [child]
        else:
            held.append(child)

        node = child

    # node is the leaf; it is latched X (added to `held` on its iteration).
    # Modify the leaf; if it splits, the cascade walks back up `held` modifying
    # each ancestor under its already-held X latch, and stops at the first safe one.
    do_insert_and_cascade(held, key, value)
    for a in held:
        unlatch(a)

def is_safe_for_insert(node):
    # safe = even after a worst-case insert, this node will not overflow
    return len(node.keys) < node.max_keys

Read it carefully. The held stack never gets longer than the number of consecutive unsafe ancestors. In the common case where the leaf's parent has at least one free slot, held shrinks to a single element after the first descent step that finds a safe child — and from then on the thread holds exactly one latch at a time (the current node). A concurrent thread inserting into a different subtree hits no contention whatsoever.

Reads get the simpler version, because reads never modify the tree: a reader latches the root shared, descends to the child, latches the child shared, releases the root, and so on. The held stack has at most two elements — parent and current — at any instant, no matter what. For reads, crabbing is simply "hold your grip until you have latched the next rung". This is why concurrent reads on a B+ tree are essentially free: every reader holds two shared latches at a time, on different nodes, non-conflicting.

The B-link variant. Even crabbing has a worst case: a write that cascades to the root holds latches on every level. The B-link tree of Lehman and Yao (1981) eliminates this by adding a right-sibling pointer to every level and a high key on every node. A reader that arrives at a node whose high key is now too low (because a concurrent split has moved their target to the right sibling) simply follows the right-sibling pointer — without needing to hold the parent's latch to confirm. This lets writers split without latching the parent up front; the parent gets updated later, lazily. Every serious production B+ tree — Postgres, SQL Server, InnoDB — is a B-link variant, and the trick that makes it work is exactly this: a latch-free way to recover when the shape changes under you.

                   [17]
              /          \
          [7 | 11]     [23 | 31]
         /    |    \    /   |    \
      [3,5] [7,9,11] [13,15] [17,19,21] [23,25,29] [31,37,41]

Common confusions

• "Postgres calls them lightweight locks (LWLocks), not latches." Same thing. The Postgres source calls its page-level mutexes LWLock and its transaction-level locks Lock or HeavyweightLock. The terminology predates the latch/lock standardisation in academic writing. When you read a Postgres commit message about "taking a buffer lock", that is a latch — microsecond-scale, released at the end of a critical section. The confusingly-named function is LockBuffer(buf, BUFFER_LOCK_SHARE); internally it is a LWLockAcquire call. InnoDB is cleaner: it calls them latch and lock respectively and has done so since early MySQL.

• "Is mutex the same as latch?" Close enough to use interchangeably in most contexts. Strictly, a mutex is a specific OS primitive (a pthread_mutex, a Windows CRITICAL_SECTION), while a latch is any short-lifetime exclusion mechanism the database implements, often using an atomic CAS instead of a full mutex for speed. A database latch may be implemented as a spinlock for uncontended cases and upgrade to a futex-based mutex under contention. Either way: a latch is a mutex, philosophically.

• "Are locks held on the index or on the data?" Both, usually. A transaction that updates row 17 typically takes an X lock on the row (logical lock) and, during the descent to find row 17, latches each index page it touches (physical latch). Some workloads add index locks — a row lock on the index entry itself — which matter for the phantom read problem: a range predicate like WHERE age > 30 could match a newly inserted row that was not visible at query start unless the index entries are locked too. Predicate locks are the elegant but expensive answer; Postgres solves phantoms via MVCC snapshots instead, which sidesteps the whole question.

• "If the buffer pool pin count is zero, does that mean no latch is held?" The pin count and the latch are independent. A pin prevents eviction — it says "I have a pointer into this frame, do not move it" — but does not exclude other threads from also pinning the same frame. A latch excludes. A thread typically pins a frame first, then latches it (S or X), does work, unlatches, unpins. Under light concurrency, some engines collapse pin-and-S-latch into a single operation; under heavy concurrency, keeping them separate lets many threads hold a pin while only one holds an X latch.

• "Why do I never see latches in SQL error messages but I see 'deadlock detected' all the time?" Because latches deadlock-prevent by construction — the top-down ordering rule makes cycles structurally impossible, so there is nothing to report. Locks deadlock-detect at runtime, so when a cycle shows up the DBMS must pick a victim and tell somebody. The rare latch error you do see — latch contention timeout in Oracle, buffer lock wait in Postgres pg_stat — is not a deadlock but a symptom of a different pathology: a thread that crashed holding a latch, or a thread that is genuinely stuck inside a critical section due to a bug.

• "Do MVCC databases not need locks?" MVCC (multi-version concurrency control) replaces read locks with snapshot reads — each transaction sees a consistent view of the database as of its start time, so it never needs to lock rows to read them. But writes still need mutual exclusion: two transactions updating the same row must serialise somehow. So MVCC databases (Postgres, Oracle, MySQL with InnoDB) still have row-level X locks for writes. They also still have latches for the index and buffer pool, exactly as described above — MVCC is orthogonal to the physical concurrency of the tree.

Going deeper

If the distinction is clear — latches guard physical pages for microseconds, locks guard logical rows for a transaction — here are the advanced topics the rest of the field has written papers about.

Lock-free B-tree variants (the Bw-tree)

Microsoft Research's Bw-tree (Levandoski, Lomet, Sengupta, 2013) removes page-level latches entirely. The core idea: a page is a chain of delta records ending in a base page, and modifications are applied by prepending a new delta to the chain with a single atomic compare-and-swap. The page table maps page ids to the physical address of the head of the chain; updating a page is a single CAS of the head pointer. Readers walk the chain applying deltas on the fly. Periodically a background thread consolidates a chain into a new base page.

The result is a latch-free B-tree where insert, delete, and lookup use only atomic operations — no mutexes, no spin locks, no latch contention at all. The tradeoff is a more complex memory reclamation scheme (since old deltas and pages cannot be freed until no reader is still walking them — epoch-based reclamation does the job) and a harder-to-analyse performance profile under heavy write contention. The Bw-tree ships in Microsoft Hekaton (SQL Server's in-memory OLTP engine) and in a few research systems; it has not displaced latch-based B-trees in general-purpose databases, partly because the implementation complexity is substantial and partly because latch-based B-link trees already scale to hundreds of cores on modern hardware.

Latch-free indexes more broadly

Beyond the Bw-tree, the concurrent-indexes literature has explored:

• Optimistic lock coupling (OLC): every node has a version counter incremented on every modification. Readers descend without taking any latches, then validate the version counter at the end — if it changed, retry. Writers still take X latches but release them in crab-coupling fashion. OLC halves latch overhead on read-heavy workloads and is used in HyPer and Umbra.
• Read-copy-update (RCU): readers never synchronise with writers; writers create a new version, atomically publish it, and wait for all pre-existing readers to finish (an "RCU grace period") before freeing the old version. Used in the Linux kernel's directory cache and some in-memory indexes. Not a good fit for disk-resident trees because the write path is I/O-bound, so the grace period is too long.
• Hardware transactional memory (HTM): Intel TSX (now largely deprecated) let you wrap short critical sections in XBEGIN/XEND and the CPU would roll back on conflict. Used in some research databases but never became mainstream, partly because of hardware bugs that disabled TSX on several CPU generations.

PostgreSQL's SLRU buffers and content locks

Postgres's concurrency layer is instructive to read because it has evolved in the open over thirty years.

• LWLock: Postgres's general-purpose latch. Hundreds of them exist as named globals (WALInsertLock, ProcArrayLock, CommitTsLock); each lock has a shared/exclusive mode and queues waiters via semaphores. In 2014–2016, several of these locks were rewritten to use atomics and lock-free queues, unblocking scalability above 64 cores.
• Buffer content lock: every frame in the buffer pool has an LWLock attached — the content lock — that a thread takes before reading or writing the page's contents. This is the concrete latch every page access goes through.
• Buffer header lock: a separate, even-shorter spinlock protecting the frame's metadata (pin count, flags). Held for nanoseconds.
• SLRU caches: Postgres's clog, subtrans, multixact, and commit-ts caches are simple LRU ring buffers of small (8 KiB) pages, separate from the main buffer pool. Each SLRU bank has its own LWLock. Under write contention on multixact commits, SLRU LWLock contention was a notorious bottleneck for years; it has been progressively partitioned.
• Heavyweight lock manager: a separate data structure, LockMgr, that handles transaction-level locks. Partitioned into 16 hash buckets for scalability. Supports the full mode hierarchy (S, X, IS, IX, U, SIX). This is where row-level deadlock detection lives.

Reading the Postgres source for two hours will teach you more about concurrent databases than a semester of lectures. Start with src/backend/storage/lmgr/lwlock.c and src/backend/storage/buffer/bufmgr.c.

Hierarchical locks and the intention protocol

When a transaction wants to lock an entire table — for ALTER TABLE, or because the query planner proved that no finer granularity will be correct — you would naively scan every row and take a row lock on each. On a billion-row table this is absurd. The answer is hierarchical locking: the lock manager recognises a hierarchy (database → table → page → row), and a table-level X lock implicitly covers every row below it.

The subtlety: a transaction that wants a row lock inside that table must somehow announce its intention to the table level, so that a later transaction trying to take a table X lock knows to wait. This is the job of intent locks: IX (intent-exclusive) on the parent, then X on the child. Compatibility rules: two IX locks on the same table are compatible (both intentions coexist); an X on the table conflicts with any IX or IS below. The cost is one extra lock acquisition per level of the hierarchy, but the benefit is that coarse-grained locks become possible without quadratic work.

All major relational DBMSes implement this — DB2, SQL Server, Oracle, Postgres. The hierarchy is usually three or four levels deep; the compatibility matrix is a 6×6 table that every database textbook reprints.

Where this leads next

You now have a mental model for concurrent access to a B+ tree: latches for the physical structure, locks for the logical data, crabbing for the descent. What happens when a thread is mid-split, holding an X latch on a leaf with the right half already written to its new page but the parent's pointer not yet updated, and the power goes out?

The latch evaporates with the process, leaving the disk with a torn state: a page that is not a valid B+ tree node because it is half-way through a transformation. Every modification that takes more than one disk write — every split, every merge, every delete that cascades — has a window where the on-disk tree is temporarily not a tree at all. The buffer pool can hide this window from concurrent readers using latches, but the disk cannot hide it from a crash.

The answer is the write-ahead log: before a modification touches any page, write a record describing the intended change to a sequential log file, and fsync the log. If the crash happens during the modification, the log tells us how to finish (redo) or undo the operation on recovery. The WAL is the subject of the next chapter, and it is the mechanism by which the on-disk tree becomes as concurrent-safe across crashes as latches made it concurrent-safe across threads.

• Torn writes and the need for a log — chapter 29: why the atomic unit of a disk write is not the same as the atomic unit of a B+ tree operation, what a torn 4 KiB write looks like, and why the write-ahead log is the only known durable answer.

After that, Build 4 closes with the full WAL-protected B+ tree; Build 5 rebuilds it with ARIES-style recovery; Build 7 puts transactions and isolation on top of both. The latch/lock distinction from this chapter shows up at every layer — the names of the mechanisms change, but the two time scales never do.

References

1. Philip L. Lehman, S. Bing Yao, Efficient Locking for Concurrent Operations on B-Trees, ACM TODS (1981) — the B-link tree paper; the canonical solution to concurrent B-tree access.
2. Goetz Graefe, A Survey of B-Tree Locking Techniques, ACM TODS (2010) — a comprehensive survey of latch and lock protocols for B-trees, including crabbing, B-link, and their modern variants.
3. Justin J. Levandoski, David B. Lomet, Sudipta Sengupta, The Bw-Tree: A B-Tree for New Hardware Platforms, ICDE (2013) — the latch-free B-tree used in SQL Server Hekaton.
4. Viktor Leis, Michael Haubenschild, Thomas Neumann, Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method, IEEE Data Engineering Bulletin (2019) — the OLC paper behind HyPer and Umbra's concurrency.
5. Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques (1992), chapters 7–8 — the textbook treatment of latches, locks, and the hierarchical lock protocol.
6. PostgreSQL source tree, src/backend/storage/lmgr/ and src/backend/storage/buffer/ — a production implementation of everything in this chapter, exhaustively commented.