Cache Coherence Protocol (Cache Coherence, MESI)
1. Overview
A. Definition
Cache Coherence is the property that, even when multiple processors (cores) each hold a copy of the same memory block in their own private cache, any core that reads the block observes the single most recently written value; the state machine that enforces this in hardware is the cache coherence protocol. Its representative implementation is the MESI protocol, which manages each cache line in one of four states: Modified, Exclusive, Shared, and Invalid.
The essence of cache coherence is "hiding the contradictions created by replicating data in many places for performance." In a multicore system each core keeps its own L1/L2 cache to reduce memory access latency. But if two cores have loaded the same variable x into their caches and one core updates x, the other core's cache is left with a stale value. Without a protocol the contradiction arises that "core B still reads x as 0 even though core A already changed it to 1." The cache coherence protocol invalidates or updates the other copies at the moment a write occurs, preserving for software the illusion of "a single shared memory with no caches."
Why exactly four states is also explained by design logic. The key attributes to distinguish for a cache line are three: "is it valid," "do I hold it alone (exclusive)," and "is it the same as memory (clean)." If not valid it is Invalid; if valid, sole, and clean it is Exclusive; if valid and sole but dirty it is Modified; and if valid but shared (clean) with another cache it is Shared — four combinations arise naturally. The leaner MSI cannot separately express "sole clean" and thus triggers unnecessary invalidations, while the richer MOESI/MESIF add states to express extra attributes (the "supplier responsible for a shared dirty block" or the "designated responder"). In short, the size of the state set is the result of a cost-benefit judgment about "how fine a distinction to track in hardware in order to save traffic."
A concept that must be distinguished here is coherence versus consistency (memory consistency model). Coherence is a local property dealing with the order and visibility of writes to a "single address," while consistency is a global rule (e.g., Sequential Consistency, TSO) specifying in what order accesses to "several different addresses" are observed. That is, MESI guarantees coherence, but the reordering problem between different variables remains the domain of memory barriers and the consistency model. In a professional-engineer answer, not confusing the two is essential.
B. Background and Necessity
In the single-core era there was only one cache, so it was enough to manage the single problem that "the cache value and the memory value may differ" (the inconsistency caused by write-back). But from the mid-2000s, as clock-speed gains hit the wall of power and heat (the Power Wall), the axis of performance scaling shifted from "one faster core" to "many cores," and every server, PC, and smartphone became multicore. Once giving each core a private cache became universal, copies of the same data scattered across many caches became constant, and a hardware mechanism to manage this without contradiction became essential.
Cache coherence is also intertwined with the cache's write policy (write-back/write-through). Most modern caches use write-back, which does not reflect a write to memory immediately but records it only in the cache and writes it back later; this greatly reduces memory traffic but creates the state where "only the cache holds the latest value" (M in MESI). Therefore the coherence protocol must arrange that when some core requests that block, the cache holding the latest value responds rather than memory. With write-through, memory is always current so this coordination is simple, but it overconsumes memory bandwidth; coherence management grew complex as the price of choosing write-back for performance.
This necessity is directly tied to real-world performance. For example, in a multithreaded program, when threads update a shared counter or contend for a lock variable, the cache line endlessly bounces among cores — cache line ping-pong — and latencies of tens to hundreds of cycles repeat. The coherence protocol is at once a safeguard that guarantees correctness and a performance factor whose traffic cost determines the ceiling of parallel scalability. Thus engineers designing high-performance servers, in-memory DBMSs, lock-free data structures, and HPC kernels must understand how the protocol works and lay out data to avoid false sharing.
2. Structure of the Cache Coherence Problem and Requirements
The multicore memory hierarchy, as below, consists of "per-core private caches + a shared LLC (Last-Level Cache) + main memory," and the coherence protocol operates at the layer that coordinates copies among the private caches.
flowchart TB
subgraph Chip["Multicore processor"]
C0["Core 0"] --> L10["L1/L2 private cache"]
C1["Core 1"] --> L11["L1/L2 private cache"]
C2["Core 2"] --> L12["L1/L2 private cache"]
L10 --- BUS["Coherence interconnect<br/>(shared bus / ring / mesh)"]
L11 --- BUS
L12 --- BUS
BUS --- LLC["Shared L3(LLC)<br/>+ snoop filter/directory"]
end
LLC --- MEM[("Main memory(DRAM)")]
style Chip fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
style LLC fill:#fef7e0,stroke:#f9ab00,stroke-width:2px
In the figure above, the placement of the snoop filter/directory drawn together with the shared L3 (LLC) matters. Many commercial CPUs design the LLC as inclusive, so that any line in an upper private cache must also exist in the LLC. Then a presence bit — indicating "which core holds this line in its private cache" — is attached to each LLC line, so the LLC in effect doubles as an on-chip directory and snoop filter. Thanks to this, snoops arriving from outside or inter-core requests can be delivered only to the core holding the line rather than broadcast to all cores. However, the inclusive form carries a back-invalidation cost — when a line is evicted from the LLC, the copies in upper caches must be invalidated too — so designs that combine a non-inclusive form with a separate snoop filter are increasingly common.
The conditions a coherence protocol must satisfy are usually summarized in three. The first is write propagation, meaning one core's write result must eventually be reflected in another core's read. The second is write serialization, meaning all writes to the same address must appear to all cores in the same order. If core A wrote x=1 then x=2 in order, no other core may experience the reversal of seeing 2 and then 1. The third is returning the latest value, meaning a read must return the value of "the last completed write."
As a concrete example, consider two cores handling a shared variable flag (initial value 0). For core A to write flag=1, it must first own the line in a writable state. If core B held the same line for reading, A's write request invalidates B's copy; later, when B reads flag again, a cache miss occurs and it fetches the latest value, 1, from A (or memory). Thus the three-beat sequence "write → invalidate other copies → reload" achieves write propagation and serialization at once. The important point is that this entire process is invisible to software; the programmer merely reads and writes memory. Because hardware is responsible for correctness, multicore programming is possible, but the fact that the invalidation traffic behind it is passed on as a performance cost is something a performance engineer must always be aware of.
The boundary between coherence and consistency becomes clearer with a concrete reordering example. Consider the typical flag pattern where core A writes data=42 then ready=1, and core B checks ready==1 then reads data. MESI guarantees "a single latest value" for data and ready each, but it does not guarantee that A's writes to the two variables appear in the same order to B. Under a weak memory model (e.g., ARM), B may observe ready=1 first yet still read the old value of data, so the order must be enforced with a memory barrier or a release/acquire atomic operation. Thus, if one trusts coherence alone and overlooks consistency, hard-to-reproduce bugs that "fail only occasionally" arise, so clearly recognizing the division of roles between the two concepts is the starting point of parallel programming.
The policies that achieve these conditions fall broadly into two branches. Write-invalidate invalidates all other copies just before a write so that the writing core becomes the sole owner; nearly all commercial processors today adopt it. Write-update broadcasts the written value to the other copies to update them, but when there are many sharers the bus traffic is excessive, so it is rarely used in modern systems. For example, in a producer-consumer pattern where only one side writes and the other reads immediately, update can be advantageous, but in general workloads where the writing core changes frequently, invalidate is overwhelmingly more efficient in traffic terms and has effectively become the standard.
3. Protocol Classification: Snooping vs. Directory-Based
Depending on "who delivers coherence traffic and how," protocols are divided into snooping and directory-based. Because this choice greatly changes performance and scalability depending on core count and interconnect structure, the design trade-offs must be understood together with their reasons.
The snooping (snoopy) approach has all caches constantly monitor a shared bus (or a broadcast-capable interconnect), and when some core posts a read/write request for a particular address, each cache itself checks whether it holds that block and changes its state. With no central manager, implementation is simple and latency is short, but because every request must be broadcast to all caches, bus bandwidth saturates as core count grows. It therefore suits small- to medium-scale (a few to a few tens of cores) systems, and real commercial chips place a snoop filter to reduce bandwidth waste, so snoops are not sent to caches that cannot possibly hold the block.
The directory-based approach places, for each memory block, a directory that records "which node/cache holds a copy of that block," and the core needing to write queries the directory and sends invalidation messages selectively only to the sharers. With no broadcast, it scales even to large NUMA/manycore systems of hundreds to thousands of cores, but the added indirect step of a directory lookup increases latency and the directory storage space (block count × node count bits) becomes overhead. Today's large server CPUs commonly mix the two approaches, handling within a socket by snooping/ring-mesh and between sockets by directory/snoop filter — a hybrid structure.
| Category | Snooping | Directory |
|---|---|---|
| Delivery | Full broadcast | Selective send to sharers only |
| Interconnect | Shared bus/ring | Scalable mesh/crossbar |
| Scalability | A few to tens of cores | Hundreds to thousands of cores |
| Latency | Short (direct monitoring) | Relatively long (via directory) |
| Overhead | Bus bandwidth saturation | Directory storage |
| Example | Desktop/small servers | Large NUMA/HPC/manycore |
For example, a 2-socket x86 server ties the cores within a socket with a ring/mesh coordinated by a snoop filter, and between sockets it uses directory-like information over UPI/Infinity Fabric to suppress unnecessary cross-socket snoops. By contrast, HPC nodes on the scale of thousands of cores or multi-chip GPU configurations make a directory-based approach effectively mandatory.
A numeric sense of scalability also matters. In pure broadcast snooping, when there are N cores a single write request must in principle be delivered to all N caches, so coherence traffic grows in proportion to (or more than) core count. It is manageable at 8 cores, but at 64 or 128 the interconnect saturates with requests, creating the paradox that "adding cores actually makes it slower." The directory approach mitigates this by sending messages only to the sharer set, but in exchange it must store a sharer bitmap per block, increasing memory overhead. So large systems save space with a sparse directory that tracks only the blocks actually loaded into caches, rather than all blocks, or with a hierarchical directory. This trade — "reduce traffic and you use more storage; save storage and accuracy (tracking precision) drops" — is the essential tension of coherence hardware design.
4. MESI States and Transitions
The representative of invalidate-based snooping is MESI, in which each cache line holds one of four states. The state transition diagram below shows how a line moves around according to its own core's reads/writes (PrRd/PrWr) and other cores' requests observed on the bus (BusRd/BusRdX).
stateDiagram-v2
[*] --> Invalid
Invalid --> Exclusive: PrRd / no other copy
Invalid --> Shared: PrRd / other copy exists
Invalid --> Modified: PrWr / BusRdX
Exclusive --> Modified: PrWr / no bus traffic
Exclusive --> Shared: observe other core BusRd
Exclusive --> Invalid: observe other core BusRdX
Shared --> Modified: PrWr / invalidate others via BusRdX
Shared --> Invalid: observe other core BusRdX
Modified --> Shared: other core BusRd / share after write
Modified --> Invalid: other core BusRdX / perform write-back
Modified (M) is the state where only this cache holds the copy and it is more recent (dirty) than main memory. Since the block is in no other cache it can be freely read and written, but when this line is replaced or another core requests it, it must maintain coherence by writing back to memory or handing the data directly to the requester (cache-to-cache transfer).
Exclusive (E) is the state where only this cache holds the copy but its value equals memory (clean). The value of the E state lies in write optimization. Since it is already confirmed as the sole owner, when writing to this block there is no need to invalidate other caches, so it can transition directly to M with no bus traffic. Had there been no E state (the MSI protocol), even writing to data read alone would require sending an unnecessary invalidation broadcast; in the common "read and immediately write" pattern, E removes this waste and raises performance.
Note that the E state is especially effective in workloads where data sharing is rare. In the typical application where a single thread handles most data alone, nearly all lines are loaded as E and no invalidation traffic occurs on writes, so bus usage drops noticeably compared with MSI. Conversely, in workloads with frequent sharing the benefit of E shrinks, and in that case MOESI's O or MESIF's F complements it by reducing traffic in shared situations. Thus the utility of the state set depends on the sharing characteristics of the workload, so processor designers choose a protocol based on the representative workload of their target market.
Shared (S) is the state where several caches jointly hold the same clean copy. Reading is free, but to write, one must first invalidate all other sharers with a BusRdX (or Upgrade) request to monopolize ownership, then transition to M. Invalid (I) is the state where there is no copy, or it is stale and unusable, so to access it one must fetch it again from memory or another cache.
Let us trace how these states actually move in one scenario. Starting from a state where no one holds a line (I), when core 0 first reads that block, there is no other copy so it is loaded in the E state. If core 0 then writes immediately, it rises to M with no bus traffic. Next, when core 1 reads the same block, a BusRd is observed, and core 0 supplies its M line to core 1 (cache-to-cache) while both caches drop to S. When core 1 writes to the block again, it invalidates (I) core 0's S copy via BusRdX and itself becomes M. In effect "ownership" has moved from core 0 to core 1, and if the two cores repeatedly write in alternation, the line endlessly ping-pongs between the two sides in the M state, causing severe latency. Being able to picture this flow in your head lets you quantitatively explain why contention over shared data erodes parallel performance.
One thing to add is that the textbook's four stable states (M/E/S/I) are a conceptual model, and real hardware implementations have many transient states in which a line dwells while a request travels the bus. Examples include the intermediate state while awaiting a response after sending an Upgrade request to rise from S to M, and the state during handing an M line to another core. These transient states are needed to serialize, without contradiction, the race in which two cores simultaneously seek ownership of the same line, and for this reason the actual number of states in commercial coherence protocols reaches dozens and becomes a subject of formal verification. In an answer, mentioning the structure of "four stable states + many transient states" can demonstrate the depth of your understanding.
The variants extending MESI each target a specific inefficiency. MOESI adds the Owned (O) state, allowing a dirty block to be shared with other caches without immediately writing it back to memory (the owner bears responsibility for supplying the latest value). This reduces write-back traffic and is adopted by the AMD line. MESIF adds the Forward (F) state, designating that only "one" of several sharers responds to a request (supplies data), thereby eliminating multiple-response collisions (the Intel line). Thus the additional states all arise from the same motive of reducing a specific kind of traffic — either "unnecessary memory write-back" or "redundant responses" — and the difference is the choice of "which cost to reduce first."
| State | Valid | Matches memory | Shareable with other caches | Action on write |
|---|---|---|---|---|
| Modified | O | Mismatch(dirty) | X(sole) | Immediately possible |
| Exclusive | O | Match(clean) | X(sole) | Transition to M with no traffic |
| Shared | O | Match(clean) | O | Transition to M after invalidation |
| Invalid | X | - | - | Reload required |
5. Deep Dive: False Sharing and Recent Trends
The most practical reason to understand the coherence protocol is the performance trap called false sharing. Cache coherence operates not at byte granularity but at the granularity of a cache line (typically 64 bytes). Therefore, even if two different threads handle logically entirely different variables, if those variables happen to be placed in the same 64-byte line, one thread's write invalidates the other thread's line and ping-pong occurs. For example, even if a per-core counter array long cnt[N] is placed contiguously and each core increments only its own index, several counters are bound into one line, and even though there is no real sharing, extreme coherence traffic arises. In measurements, such code is often several to tens of times faster when each counter is padded to the cache line size (alignas(64)), and this is a key tuning point of high-performance parallel code.
Gauging the cost of false sharing in cycles makes clear why it is fatal. An L1 cache hit usually finishes in a few cycles, but fetching a line that another core holds in the M state — a remote HITM (Hit-Modified) — takes tens to hundreds of cycles. If the sockets differ, it also traverses the cross-socket interconnect, so the cost grows larger. In code where four threads each increment, hundreds of millions of times per second, different counters bound into one line, every increment triggers a line-ownership transfer and is effectively serialized, incurring tens of times the latency compared with a cache hit. Conversely, separating the counters into different lines lets each core monopolize its own line in the M state and update it with no bus traffic, so it scales near-linearly. This phenomenon — the same algorithm differing by tens of times from a single data layout — most dramatically demonstrates the proposition that, in the multicore era, "hardware determines correctness, data layout determines performance."
This principle is reflected throughout real industrial codebases. The Linux kernel extensively uses per-CPU variables that keep an independent copy per core to fundamentally avoid shared writes and the coherence traffic they cause, aggregating statistics and counters per core and summing only on read. In Java, the @Contended annotation (JEP 142) pads hot fields to cache-line boundaries to prevent false sharing, and the ring buffer of the high-performance messaging library LMAX Disruptor is famous for padding its sequence counters to eliminate producer-consumer false sharing. Thus the principle "reduce sharing, and for unavoidable sharing separate the lines" is a staple of performance design that recurs across all layers — OS, runtime, and library.
The cost of locks and atomic operations is also explained by the coherence protocol. Acquiring a compare-and-swap or a spinlock requires monopolizing the lock-variable line in a writable state (M), so when many cores contend for one lock, that line moves among the cores as if in a stampede. This is why traditional spinlocks slow sharply with core count, and it is also the background to the emergence of queue-based locks such as MCS locks and ticket locks, designed to spin on a per-core local variable. In short, understanding that cache coherence traffic lies at the bottom of the phenomenon "locks are slow" lets you choose remedies such as contention mitigation (sharding, backoff, local aggregation) on a principled basis.
Among recent trends, first, memory expansion/sharing based on CXL (Compute Express Link) draws attention. The CXL.cache/CXL.mem protocols extend hardware coherence between the CPU and accelerators/external memory pools, aiming at a structure where a device coherently caches host memory or where a memory pool is coherently accessed by multiple hosts. This is an attempt to broaden the coherence domain, traditionally confined within a socket, to the package and rack level, and it dovetails with the data-center demand to flexibly redistribute memory among servers through memory disaggregation and pooling. However, as the coherence scope broadens, remote access latency and the difficulty of managing coherence traffic grow together, so careful tiered design is required about which data to place under coherent sharing. Second, with chiplet and manycore trends sharply increasing the number of nodes within a single package, pure broadcast snooping reaches its limits, and directory/snoop filter with mesh interconnect is becoming the standard. Third, in GPU and heterogeneous computing, a design issue is how far hardware guarantees the coherence scope of CPU-GPU unified memory (e.g., a unified virtual address space) and from where it is left to software synchronization. Fourth, as coherence traffic accounts for a substantial portion of performance and power, research into scalable directories (sparse/hierarchical directory) and coherence-domain partitioning continues. Fifth, hardware transactional memory (HTM) leverages the tracking ability of the coherence protocol to support lock-free synchronization, having hardware detect conflicts among cache lines read and written in a transaction region and roll back on conflict. This shows the trend of the coherence mechanism extending beyond mere correctness guarantees into base infrastructure for concurrency control.
What these trends have in common is that "in an era when cores and memory explode in number, rather than pushing full hardware coherence as is, the scope is intelligently regulated." The center of gravity is shifting from the dense coherence of a traditional single server to "selective coherence" that tiers the scope across socket, package, and rack and hands some to software, and the designer must analyze the sharing pattern of the workload to judge up to which tier to place hardware coherence.
6. Considerations and Implications
In sum, the cache coherence protocol is "an invisible contract that underpins the floor of multicore performance." The implications derived from a professional-engineer perspective are as follows.
First, one must reason by separating the hardware guarantee of correctness from the software responsibility for performance. MESI guarantees coherence (latest-value visibility for a single address), but ordering between different variables is the domain of the memory consistency model and barriers. In subtle synchronization such as lock-free code or double-checked locking, the misconception that "barriers are unnecessary because coherence is guaranteed" leads to fatal bugs. From a professional-engineer perspective, the ability to design and review by separating the two layers is required.
Second, one must adopt as a design principle that data layout is a decisive variable of performance. Avoiding false sharing (separating/padding hot variables), aligning thread and data locality (NUMA-aware placement), and minimizing shared writes (per-core local aggregation then merge) govern parallel scalability. As a trade-off, padding increases memory usage, so judgment is needed to apply it selectively to hot data where contention is actually severe.
Third, tuning must be varied according to per-architecture characteristics (MESI/MESIF/MOESI, snooping vs. directory). Even for identical code, coherence traffic patterns differ by Intel (MESIF) vs. AMD (MOESI), socket count, and SNC setting. In performance profiling, one must observe not only cache misses but also coherence-related counters (e.g., remote HITM, cross-socket traffic) together, finding the cause of bottlenecks in cross/shared traffic.
Fourth, from a scalability perspective, the coherence domain must be regulated at the design level. As cores, sockets, and accelerators grow, full hardware coherence surges in cost, so deliberately narrowing the coherence scope or substituting software — as with CXL, distributed shared memory, or message passing (MPI) — is valid. In future heterogeneous and pooled-memory environments, "up to where to bind with hardware coherence and from where to separate with explicit synchronization" is poised to become a key decision of system architecture, and as related technologies NUMA locality optimization, memory barriers/atomic operations, and transactional memory must be considered together.
Fifth, one must recognize the side effects of coherence mechanisms from a security and reliability standpoint too. Cache state transitions and the access-latency differences they cause become measurable signals and can become the basis for cache side-channel attacks that infer another core's memory access patterns (e.g., Flush+Reload, measurement based on coherence traffic). Also, the coherence protocol makes multicore concurrency bugs hard to debug, because low-reproducibility race conditions reveal themselves only under specific core placement and timing. From a professional-engineer perspective, considering the balance between performance optimization and security/verifiability, one must include constant-time implementation of sensitive operations and systematic concurrency testing (model checking, stress testing) in the design.
References
- Hennessy & Patterson, "Computer Architecture: A Quantitative Approach" (Chapter on Multiprocessors and Cache Coherence)
- Sorin, Hill, Wood, "A Primer on Memory Consistency and Cache Coherence", Morgan & Claypool — https://doi.org/10.2200/S00346ED1V01Y201104CAC016
- Intel, "Intel 64 and IA-32 Architectures Software Developer's Manual, Vol. 3A" — https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
- CXL Consortium, "Compute Express Link Specification" — https://computeexpresslink.org/
In one line: The cache coherence protocol (MESI) manages copies of the same block scattered across caches with a Modified·Exclusive·Shared·Invalid state machine to guarantee in hardware the visibility of "a single latest value," and the choice of snooping vs. directory and the avoidance of false sharing govern multicore performance and scalability.