Topic 9 — Concurrency: Latches, Lock-Free & Epochs
Scaling across cores is where the hardest bugs and the biggest wins live. Topic 8 asked “who sees what” for transactions; this topic asks the same question for NANOSECONDS: two threads, one cache line, who wins?
Budget: ~12 h. Order: §1 vocabulary → §2 memory ordering → §3 latch protocols → §4 reclamation → §5 code → experiments → M9.
The problem, measured (bench lanes 1 and 2, provided — run today)
cargo run --release --bin false_sharing and --bin scaling:
8 threads, 5M increments each, each on its OWN counter
packed 202.7 ms 197.4 M inc/s
pad64 20.4 ms 1957.6 M inc/s
pad128 11.4 ms 3502.9 M inc/s
Mops/s total, 90/10 read/write, keyspace 100000
impl 1t 2t 4t 8t 16t
global 8.65 5.32 2.84 2.86 2.96
sharded 11.63 8.40 8.66 11.22 12.65
crossbeam 4.21 9.07 14.39 14.82 19.28
The global mutex gets 2.9× slower as you add cores. Not “fails to scale” — negative: 8.65 Mops/s on one thread, 2.96 on sixteen. The cores spend their time moving the lock’s cache line between caches and parking each other rather than doing work, and that line shape (peak at one thread, decay after) is the single most useful signature to recognise in production, because it means the fix is never “add threads”.
The counter table is the same physics one level down: three layouts where every
thread owns its own counter and touches nobody else’s, spanning 17.8×. pad64
— a hand-written #[repr(align(64))], the textbook “pad to one cache line”
advice — is still 1.8× off pad128, because M-series coherence granularity is
128 B. Crossbeam’s CachePadded already knows this: it is
repr(align(128)) on x86-64 and aarch64 (crossbeam-utils/src/cache_padded.rs
lines 70–77 and 87–94, at the pinned revision), because Sandy Bridge onwards
prefetches 64-byte lines in pairs. It is the 64-byte assumption in your own
head, not the crate’s, that this lane is testing.
And note which structure is slowest single-threaded: crossbeam’s lock-free set, at 4.21 vs the mutex’s 8.65. Atomics and epoch bookkeeping cost real sequential performance to buy a slope. That trade is the topic.
1. Latches vs locks (say it right)
| lock (topic 8) | latch (this topic) | |
|---|---|---|
| protects | logical content (rows, predicates) | physical structure (a node, a page) |
| held for | a transaction (seconds) | a critical section (nanoseconds) |
| deadlock | detected/resolved | must be IMPOSSIBLE by ordering |
| implemented by | lock manager table | atomics in the object itself |
Everything in this topic is latches. The three escalation rungs:
mutex/rwlock → optimistic (version check) → lock-free (CAS)
block on conflict restart on conflict never block; help
postgres LWLock LeanStore HybridLatch (T6) RocksDB memtable,
+ OLC B-trees crossbeam SkipSet
2. Memory ordering in one table (Rust atomics)
| Ordering | Guarantee | When you reach for it |
|---|---|---|
Relaxed | atomicity only, no ordering | counters, stats |
Acquire (loads) | later reads/writes can’t move before it | reading a “ready” flag |
Release (stores) | earlier reads/writes can’t move after it | publishing a “ready” flag |
AcqRel | both, for RMW ops | CAS that links a node |
SeqCst | one global order of all SeqCst ops | when you can’t prove less is enough |
The publication idiom that everything below builds on:
writer: node.data = 42; (plain writes)
list.next.store(node, Release); ← publish
reader: let n = list.next.load(Acquire); ← subscribe
n.data // guaranteed to see 42
memgraph’s fully_linked.store(true, memory_order_release) and RocksDB’s
CASNext are both exactly this idiom. x86 gives you Acquire/Release for
free (TSO); ARM (this Mac!) does not — wrong orderings that “pass” on
x86 crash on the M-series. Test here.
3. Latch protocols for trees & lists
- Latch coupling (topic 3’s B-trees): hold parent, grab child, release parent. Correct, but every traversal WRITES the latch cache line — root’s line ping-pongs between all cores. Read-scaling: none.
- Optimistic latch coupling (OLC, Leis): version counter per node. Readers read version → read node → re-check version; restart if changed. Writers latch + bump. Reads write NOTHING shared. This was LeanStore’s HybridLatch (topic 6) — same trick, now you study it as a protocol.
- Lock-free: no latch at all; every mutation is one CAS that either lands or retries. The hard part is never the CAS — it’s DELETION (§4) and multi-pointer updates (the skiplist’s towers, Bw-tree’s SMOs).
4. The reclamation problem (the actual boss fight)
Lock-free reads mean a reader may hold a pointer to a node you just
unlinked. free() it and the reader explodes. Options:
epoch-based (crossbeam, this topic's build)
┌────────────────────────────────────────────────────┐
│ global epoch E ────────► 3 garbage bags: E, E-1, E-2│
│ reader: pin() → local epoch = E │
│ writer: unlink node → defer_destroy into bag E │
│ advance: only when ALL pinned locals reached E │
│ free bag E-2: nobody can still see its nodes │
└────────────────────────────────────────────────────┘
hazard pointers: per-reader "I'm reading THIS ptr" slots — O(readers)
scan per free, but bounded garbage (epochs can be wedged by one stall)
accessor ids (memgraph): each accessor gets a monotonic id; a retired
node waits until all accessors older than the retire-time are gone —
epoch flavor with txn-scoped pins
RCU/QSBR (kernel): quiescent states instead of pins
Trade to internalize: epochs make READS free (one pin per operation, no per-pointer traffic) but garbage unbounded under a stalled reader. Hazard pointers invert it. Databases almost always pick epochs — readers outnumber stalls.
5. Bw-tree: the cautionary tale
ICDE’13: a fully lock-free B-tree — updates are DELTA RECORDS prepended by CAS onto a mapping table entry; splits are multi-step state machines. SIGMOD’18 (“…More Than Just Buzz Words”) rebuilt it honestly: delta chains wreck cache locality, consolidation needs tuning, and a well-built OLC B+tree beats it on almost every workload. Lesson: optimistic latches + epochs is the pragmatic frontier; fully lock-free indexes are usually a research flex. (Read both; guide: reading-bwtree.md.)
6. False sharing (the silent 10×)
Two ATOMICS in one 64B/128B cache line = every write invalidates the other
core’s line even though the data is “independent”. redis padded its
per-thread used_memory counters (topic 6); you’ll measure the effect in
false_sharing.rs (M-series lines are 128B — check both alignments).
7. Code to read (guides in this dir)
| Guide | What you’ll trace |
|---|---|
| reading-postgres-lwlock.md | One word, one CAS, one queue: postgres’s production rwlock |
| reading-crossbeam-epoch.md | Epoch reclamation: the GC that makes lock-free reads free |
| reading-concurrent-skiplists.md | Two concurrent skiplists: CAS vs lazy locking |
| reading-bwtree.md | Bw-tree vs OLC: why lock-free lost to optimistic latches |
8. Experiments (experiments/)
src/concurrent_set.rs— YOU make topic 2’s skiplist concurrent: lock-free insert/contains/remove over crossbeam-epoch. Tests fix the contract (disjoint-key races, same-key races → exactly one winner, remove-under-readers doesn’t UAF).src/bin/scaling.rs— provided: 1→16 threads, 90/10 read/write mix:Mutex<BTreeSet>vs 16-shard mutex vs crossbeamSkipSet(reference) vs yours. The mutex line runs today; predict the shapes first.src/bin/false_sharing.rs— provided, runs now: packed vs padded atomic counters, 8 threads. Predict the ratio on this M-series Mac.
9. M9 checklist (capstone)
- threadpool.rs: fixed pool, work queue, no per-query spawn. Compare against the reference’s design (steal or not? — recall the Glommio/tokio trade from topic 7)
- single-writer/multi-reader graph: readers pin an epoch + version (M8’s snapshot), writer publishes new matrix versions with Release
- parallel query execution over read snapshots — where does GraphBLAS’s own parallelism meet the pool? (One pool, not two — decide who owns the threads)
- contention profile: Instruments “System Trace”/cachegrind stand in for perf c2c on macOS; find one false-sharing line in your code