Latches Versus Locks
A latch is a lightweight in memory lock held only for the duration of a page operation. It differs from a database lock, which protects logical data for a whole transaction. Latches protect the physical page structure from concurrent corruption.
The Hazard
While one thread descends to insert a key, another thread might split a page on the path. Without coordination a reader could follow a pointer that is being rewritten and land in the wrong place.
Latch Crabbing
To traverse safely, threads use latch crabbing, also called latch coupling.
- Acquire a latch on the child before releasing the latch on the parent.
- Release the parent latch once the child is known to be safe, meaning it will not split or merge on this operation.
- For writes, hold ancestor latches until it is clear no split will propagate up to them.
This grips the tree hand over hand, like a crab, so a thread never lets go of one page until it holds the next.
Reducing Contention
Because top level pages are crossed by every traversal, holding their latches long hurts throughput. Releasing them as early as safety allows keeps the hot upper levels free.
Key idea
Latch crabbing locks a child before unlocking its parent and releases ancestors as soon as a page is proven safe, letting many threads traverse a B tree without corruption.