lowlatency · advanced

Cache Coherence & the MESI Protocol

Memory access is a steep hierarchy — L1 (~1ns) through L2 and L3 to DRAM (~100ns) — and caches transfer fixed 64-byte cache lines, so touching one byte pulls in its entire line. Because each core holds private caches, hardware needs a coherence protocol, MESI (with variants like MESIF/MOESI), which tracks every cached line per core in one of four states: Modified (the only, dirty copy), Exclusive (the only, clean copy), Shared (multiple clean copies), or Invalid (stale). The expensive operation is writing a line that other cores hold: the writer must obtain ownership through a Read-For-Ownership that invalidates every other copy, and if two cores keep writing the same line it ping-pongs between them, each write forcing an invalidate and refetch across the interconnect at a cost of tens to hundreds of cycles. This coherence traffic — not the instruction itself — is why contended atomics and locks are slow. The design rules for low latency follow directly: keep hot mutable data core-local, make shared data read-mostly (replicating Shared copies is cheap, writing them is not), pad independently-written fields onto separate 64-byte lines to avoid false sharing (where unrelated variables on one line bounce as if shared), and minimize shared writes and atomic contention.

The code

// Each core has private L1/L2; a shared L3; memory is far away.
// Caches move data in 64-byte CACHE LINES, not bytes.

// MESI: every cached line is in one of four states
//   Modified  — this core has the only, dirty copy
//   Exclusive — this core has the only, clean copy
//   Shared    — multiple cores have a clean copy
//   Invalid   — stale; must refetch

// A WRITE to a Shared line must invalidate every other copy first.

What this lesson walks through

1. 01Caches move 64-byte LINES, in four states
2. 02Writing a Shared line is expensive
3. 03Gotcha — false sharing ping-pongs the line
4. 04Designing for coherence

Each core has private caches; data moves in 64-byte cache lines. MESI tracks every cached line as Modified, Exclusive, Shared, or Invalid so all cores agree on what's current.