Cache Coherence (MESI)

Your laptop almost certainly has four or more CPU cores. Each core has its own private cache — a tiny, blazing-fast memory that holds copies of recently used data. Without caches, cores would stall waiting for main memory hundreds of times per second, and the chip would be far slower.

But that speed comes with a hidden problem. If Core 0 reads a variable $x$ into its cache and Core 1 also reads $x$ into its own cache, both are holding a copy. Now Core 0 writes a new value to $x$. Core 1 still sees the old value. The two caches disagree — and programs that depend on shared data will compute wrong answers.

This is the cache coherence problem: how do you keep every core's cached copy of shared memory consistent, without destroying the performance advantage caches provide in the first place?

The dominant answer, used in virtually every x86 and ARM chip shipped in the last four decades, is the MESI protocol — a state machine named after its four states: Modified, Exclusive, Shared, and Invalid.

The demo below simulates two cores sharing a single memory address. Each core has its own cache slot. Use the buttons to issue Read and Write operations from either core, and watch the MESI state of each cache slot update in real time.

<!-- {{c_html_desc}} -->
<div class="scene">
  <div class="core-box" id="core0">
    <div class="core-label">{{label_core0}}</div>
    <div class="cache-slot" id="slot0">
      <div class="slot-label">{{label_cache}}</div>
      <div class="slot-state" id="state0">I</div>
      <div class="slot-value" id="val0">—</div>
    </div>
    <div class="btn-row">
      <button id="r0" type="button">{{btn_read0}}</button>
      <button id="w0" type="button">{{btn_write0}}</button>
    </div>
  </div>

  <div class="bus-area">
    <div class="bus-label">{{label_bus}}</div>
    <div class="bus-line">
      <div class="bus-msg" id="busmsg"></div>
    </div>
    <div class="mem-box">
      <div class="mem-label">{{label_mem}}</div>
      <div class="mem-val" id="memval">0</div>
    </div>
  </div>

  <div class="core-box" id="core1">
    <div class="core-label">{{label_core1}}</div>
    <div class="cache-slot" id="slot1">
      <div class="slot-label">{{label_cache}}</div>
      <div class="slot-state" id="state1">I</div>
      <div class="slot-value" id="val1">—</div>
    </div>
    <div class="btn-row">
      <button id="r1" type="button">{{btn_read1}}</button>
      <button id="w1" type="button">{{btn_write1}}</button>
    </div>
  </div>
</div>

<div class="log-area">
  <div class="log-hdr">{{label_log}}</div>
  <div id="log"></div>
</div>
<div class="btns-bottom">
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_desc}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a2233; background: #f6f8fb; }
.scene { display: flex; align-items: flex-start; gap: 10px; justify-content: center; padding: 14px 8px 6px; flex-wrap: wrap; }
.core-box { background: #fff; border: 1.5px solid #c5d3e0; border-radius: 12px; padding: 10px 12px; min-width: 130px; display: flex; flex-direction: column; align-items: center; gap: 8px; }
.core-label { font-weight: 700; font-size: .85rem; color: #1d3557; }
.cache-slot { background: #edf2f7; border: 1.5px solid #b0c4d8; border-radius: 8px; padding: 6px 14px; text-align: center; min-width: 100px; }
.slot-label { font-size: .7rem; color: #5a7088; text-transform: uppercase; letter-spacing: .05em; margin-bottom: 2px; }
.slot-state { font-size: 1.5rem; font-weight: 900; letter-spacing: .05em; transition: color .3s; }
.slot-value { font-size: 1rem; font-weight: 600; color: #2d6a4f; min-height: 1.4em; }
.state-M { color: #e63946; }
.state-E { color: #0077b6; }
.state-S { color: #2a9d8f; }
.state-I { color: #adb5bd; }
.btn-row { display: flex; gap: 6px; }
button { font: 600 13px system-ui; padding: .38rem .75rem; border: 1.5px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; transition: background .15s; }
button:hover { background: #2a4a7f; }
button.ghost { background: #fff; color: #1d3557; }
button.ghost:hover { background: #e8eef4; }
.bus-area { display: flex; flex-direction: column; align-items: center; gap: 6px; padding-top: 28px; min-width: 100px; }
.bus-label { font-size: .7rem; color: #5a7088; text-transform: uppercase; letter-spacing: .05em; }
.bus-line { width: 4px; height: 70px; background: #b0c4d8; border-radius: 2px; position: relative; }
.bus-msg { position: absolute; left: 50%; transform: translateX(-50%); top: 50%; background: #e63946; color: #fff; font-size: .65rem; font-weight: 700; padding: 2px 5px; border-radius: 4px; white-space: nowrap; opacity: 0; transition: opacity .3s; }
.bus-msg.visible { opacity: 1; }
.mem-box { background: #fff; border: 1.5px solid #a8c4de; border-radius: 8px; padding: 5px 14px; text-align: center; }
.mem-label { font-size: .7rem; color: #5a7088; text-transform: uppercase; letter-spacing: .05em; }
.mem-val { font-size: 1.1rem; font-weight: 700; color: #1d3557; }
.log-area { margin: 4px 10px 0; background: #fff; border: 1px solid #d1dce8; border-radius: 8px; max-height: 120px; overflow-y: auto; padding: 6px 10px; }
.log-hdr { font-size: .72rem; color: #5a7088; text-transform: uppercase; letter-spacing: .05em; margin-bottom: 4px; }
#log { font-size: .8rem; line-height: 1.6; color: #1a2233; }
.log-entry { padding: 1px 0; border-bottom: 1px solid #f0f4f8; }
.log-entry:last-child { border-bottom: none; }
.btns-bottom { display: flex; justify-content: center; padding: 8px; }

// Code not found

Notice what happens when one core writes while the other holds a Shared copy: the writing core's cache transitions to Modified and the other core's copy is immediately Invalidated — it must fetch the new value before its next read. This ping-pong between cores is called cache-line bouncing, and it is the hidden performance cost every parallel programmer must respect.

The MESI protocol assigns one of four states to every cache line on every core:

• Modified (M) — this core has the only valid copy, and it has been written. Main memory is stale. Before another core can read this line, the modified core must write back the value.
• Exclusive (E) — this core has the only copy, and it matches main memory. No write-back needed yet; a local write promotes it to M cheaply.
• Shared (S) — two or more cores hold a read-only copy that matches main memory. Any write from any core will invalidate all other copies.
• Invalid (I) — this cache slot holds no useful data. The next access is a cache miss.

The transitions are the heart of the protocol. A write from Core 0 sends an invalidation message on the interconnect bus (or directory) to every core holding an S copy, forcing them to I. The next time those cores read the address, they take a cache miss and fetch the fresh value — from Core 0's cache or from main memory after Core 0 has written back.

The performance trap: false sharing. Two cores can thrash the protocol even when they are writing different variables, if those variables happen to sit in the same 64-byte cache line. Core 0's write invalidates Core 1's copy of the whole line, even though Core 1's variable was never touched. This is false sharing, and it can make a parallel program slower than its single-threaded counterpart.

The cost grows with core count. On a chip with $n$ cores all writing to the same line, the bus traffic is $O(n)$ invalidations per write — exactly the kind of contention that prevents linear scaling even on embarrassingly parallel workloads.

Cache coherence is invisible when it works — and brutally visible when it doesn't:

• Parallel programming: false sharing is a classic performance bug. The fix — padding data structures so hot variables land on different cache lines — can yield 10× speedups without changing any algorithm.
• Lock-free data structures: algorithms that avoid mutexes still depend on coherence to see each other's writes in a timely way. Memory barriers (fence instructions) tell the CPU not to reorder stores across critical points.
• Weak memory models: ARM and RISC-V processors implement relaxed coherence — cores may observe each other's writes in different orders unless explicit barriers are used. Writing correct lock-free code requires understanding the underlying memory model.
• GPU computing: GPUs have thousands of cores but weaker coherence guarantees. Shared memory within a thread-block is coherent; across blocks, explicit synchronization is required.
• Non-Uniform Memory Access (NUMA): in multi-socket servers, coherence traffic crossing between sockets is especially expensive; data placement strategies aim to minimize cross-socket invalidations.

Understanding cache coherence connects directly to topics like load balancing and non-convex optimization: any parallel algorithm that shares writable state must budget for coherence overhead or it will not scale.

The MESI protocol is one of the quiet triumphs of computer architecture: a four-state machine, running in hardware at billions of events per second, that makes every shared-memory parallel program correct by default. You never call a function to keep caches in sync — the hardware does it for you.

But the protocol has a price. Every write to a shared cache line sends invalidation messages across the chip. False sharing punishes programmers who don't think about data layout. And at high core counts, coherence traffic becomes a bottleneck as real as any algorithm's asymptotic complexity.

Knowing this, you can make better decisions: pad your data structures, avoid unnecessary sharing, choose the right memory ordering. The four letters M-E-S-I are small, but what they guard is the difference between a parallel program that scales and one that doesn't.