Lec 10 Index Concurrency Control

0. Study Map

This lecture is about one practical question: how do we let many workers touch the same index without corrupting it?

Structure / Pattern	Why Concurrency Is Hard	Standard Fix
Hash table lookup/insert	Workers touch shared buckets	Latch at table/page/slot granularity
B+Tree search/update	Traversal can race with split/merge	Latch crabbing (coupling)
Leaf-to-leaf scan	Traversal is no longer strictly top-down	No-wait sibling latch protocol

Complexity Cheat Sheet

Let:

n = number of indexed entries
f = effective fanout of the B+Tree
h = tree height, so h = O(\log_f n)

Structure / Operation	Expected Complexity	Worst / Important Caveat
Hash table lookup	`O(1)`	`O(n)` under extreme collision/pathology
Hash table insert	`O(1)` amortized	resize requires global coordination
B+Tree point lookup	`O(h) = O(\log_f n)`	one latch per level on the path
B+Tree insert/delete	`O(h)` common case	split/merge can cascade up to `O(h)` levels
Leaf range scan	`O(h + \#leaf\_pages\_touched)`	sibling-latch restarts can add retries

1. Correctness: Locks vs. Latches

Concurrency control in a DBMS has two different goals:

Logical correctness: a worker sees the data it is supposed to see.
Physical correctness: the internal representation of the structure stays valid.

This lecture focuses on latches, not transaction locks.

Aspect	Locks	Latches
Protect	Logical database contents	In-memory DBMS data structures
Held by	Transactions	Workers / threads
Lifetime	Transaction duration	Critical section / operation duration
Modes	Shared / exclusive / intention…	Usually read / write
Deadlock handling	Detection + resolution	Mostly avoidance by coding discipline

Latch Modes

Read latch: many readers can hold it together.
Write latch: only one worker can hold it, and no readers may coexist.

2. Latch Design and Implementations

Design Goals

A good latch should have:

small memory footprint
fast uncontended path
decentralized management
minimal OS/system-call overhead

Common Implementations

Test-and-Set Spin Latch

Extremely fast in the uncontended case.
Usually implemented with a single atomic instruction.
Bad under contention because workers keep spinning and bouncing cache lines.
Not cache-friendly and not OS-friendly.

Compare-and-Swap (CAS)

CAS is the hardware primitive behind many latch implementations:

compare memory location M with expected value V
if equal, install new value V'
otherwise fail and retry or fall back

Blocking OS Mutex

Simple programming model.
Better behaved than pure spinning when contention is high.
But lock/unlock is more expensive and may involve the OS.

Reader-Writer Latch

Allows concurrent readers.
Useful for tree traversals where reads are common.
More metadata and queue management are needed.
Must avoid reader or writer starvation.

3. Hash Table Latching

Hash tables are comparatively easy to latch:

workers move in one direction through the structure
they usually touch only one page or slot at a time
deadlocks are therefore much less likely

If the DBMS must resize the table, it usually takes a global write latch on the whole table.

Granularity Choices

Approach	Idea	Benefit	Cost
Global latch	One latch protects entire table	Simple	Terrible concurrency
Page/block latch	One latch per page/bucket block	Good compromise	Workers still block on hot pages
Slot latch	One latch per slot	Highest concurrency	More metadata / bookkeeping

Practical Takeaway

Use coarse latches when implementation simplicity matters.
Use page or slot latches when bucket contention dominates.
Keep resize rare because it needs a global critical section.

4. Why B+Tree Concurrency Is Harder

A B+Tree has two simultaneous problems:

two workers may modify the same node at once
one worker may traverse the tree while another splits or merges nodes

That second problem is what makes B+Tree latching harder than hash-table latching.

5. Latch Crabbing / Coupling

The standard protocol is latch crabbing:

Latch the parent.
Latch the child.
Release the parent once the child is known to be safe.

Safe Node

A node is safe if the current update will not force structural change:

Insert: safe means the node will not split.
Delete: safe means the node will not merge / underflow.

If a node can hold at most m keys, then the usual textbook-safe conditions are:

\[ \text{Insert safe} \iff \text{occupancy} < m \]

\[ \text{Delete safe} \iff \text{occupancy} > \left\lceil \frac{m}{2} \right\rceil \]

Real systems may replace the half-full rule with a merge threshold, but the idea is the same: safe means no structural change is needed.

Search Protocol

For Find:

Start at the root.
Acquire a read latch on the child.
Release the parent.
Repeat until the target leaf.

This gives concurrency because readers do not keep the whole path latched.

Complexity:

\[ O(h) = O(\log_f n) \]

because the worker only walks one root-to-leaf path.

Insert/Delete Protocol

For writes:

Start at the root with write latches as needed.
Move down to the child.
If the child is safe, release ancestor latches.
Keep the latches you still need for nodes that may split or merge.

This is the pessimistic but safe version.

Common-case complexity is still:

\[ O(h) \]

but the update may also trigger up to O(h) node splits/merges in the worst case because structural changes can cascade to the root.

6. Better B+Tree Latching

The lecture points out a bottleneck: many updates begin by taking a write latch on the root.

That is wasteful because most inserts/deletes only change a leaf and do not trigger split/merge.

Optimistic Protocol

Use a two-stage idea:

Traverse like a search with read latches.
At the leaf, upgrade to / acquire a write latch.
If the leaf is safe, finish there.
If the leaf is not safe, release latches and restart with the pessimistic write-latch protocol.

This improves throughput because the common case never holds the root in write mode for long.

You can think of the optimistic algorithm as:

common case: one root-to-leaf traversal, about O(h)
wrong guess: one read-latch traversal plus one restarted write-latch traversal, still O(h) asymptotically but with roughly 2h path work

7. Leaf Node Scans

All previous examples are top-down. Range scans break that assumption because they move from one leaf to its sibling.

That introduces a new problem:

worker T1 may hold a write latch on one leaf during delete/merge
worker T2 may hold a read latch and want to step sideways to the sibling
if sibling latching waits blindly, the code can deadlock

Required Rule

Sibling-latch acquisition for leaf scans must support no-wait mode.

If the next sibling latch is unavailable:

do not wait indefinitely
restart, abort, or otherwise recover in a way the data structure understands

This is a coding-discipline rule because latches generally do not provide the same deadlock machinery as locks.

If the scan returns k leaf pages after the initial search, then the traversal cost is roughly:

\[ O(h + k) \]

with the understanding that failed no-wait sibling acquisitions can force retries.

8. Cost Summary

Operation	Latch Pattern	Time / Path Cost	Main Risk
Hash table lookup	page/slot latch	expected `O(1)`	hot bucket contention
B+Tree search	read latches top-down	`O(\log_f n)`	none if path only goes downward
B+Tree insert/delete	pessimistic crabbing	`O(\log_f n)` common case	cascading split/merge
B+Tree insert/delete	optimistic first pass	`O(\log_f n)` common case	restart if leaf not safe
Leaf range scan	read latch + no-wait sibling	`O(\log_f n + k)`	deadlock if sibling waits are allowed

9. Write-Set Discipline

For B+Tree write operations, each worker keeps a private write-set of modified nodes during the operation.

Hold write latches on modified nodes until the operation finishes.
Never expose partial structural updates to other workers.
If a needed write latch cannot be acquired, roll back the modifications in the write-set and release latches.

This is the practical rule that turns “physical correctness” into something implementable.

10. Final Takeaways

Latches protect physical structure; locks protect logical database contents.
Hash tables are easier because access patterns are simpler and mostly one-directional.
B+Tree concurrency relies on latch crabbing and the notion of a safe node.
Optimistic tree latching is important because root write latches become a bottleneck.
Leaf scans need a no-wait sibling protocol, or the code will eventually deadlock.