Cache Coherence and Consistency Models

Both coherence and consistency answer one question — when does a write to one copy of a datum become visible to a reader holding a different copy — but they answer it at two scales that are physically and architecturally different, and conflating them is the single most common mistake on this topic.

Cache coherence is a hardware property of one machine: multiple CPU cores each cache the same memory line, and a snooping protocol on the shared bus (or a directory) keeps their private L1/L2 copies in lockstep with sub-microsecond latency and a hardware guarantee of a single global order per address. Consistency models live in the distributed world: replicas sit behind a network with milliseconds of latency and the ever-present risk of a partition, so a protocol you design decides how stale a reader may be. Coherence is essentially "strong consistency that the silicon gives you for free"; distributed consistency is the menu you get when the network takes that guarantee away.

Two problems, one vocabulary

Keep the row "strongest achievable" in mind: on a single die the hardware simply is coherent, so there is no weaker mode to choose. Across a network, the instantaneous "strict consistency" of textbooks requires a global clock and zero-latency broadcast — physically unbuildable — so the real strong option is linearizability (every operation appears to take effect at a single instant between its call and return, in real-time order).

Coherence mechanism: write-invalidate vs write-update

When a core writes a line another core has cached, the protocol must do one of two things. Write-invalidate (used by essentially every modern CPU) sends a single small "invalidate" signal that kills every other copy; the writer then owns the line exclusively and future writes to it are free until someone else reads. Write-update (write-broadcast) instead ships the new value to every sharer so their copies stay warm. Invalidate spends a reader miss later but keeps the bus quiet during write bursts; update keeps readers hot but floods the bus with data on every write. The trace below follows MESI — the four line states Modified, Exclusive, Shared, Invalid — under write-invalidate.

Reading the trace

Three things worth internalizing. (a) At step 1 C0 gets Exclusive, not Modified — it hasn't written yet, but because no one else has the line it can later write silently (E→M with no bus traffic), which is why E exists as a distinct state. (b) At step 3 the write needs a Read-For-Ownership (BusRdX) even though C0 already had the value in S — the cost of a write is dominated by the invalidate round-trip, not by fetching data. (Protocols with an upgrade transaction send BusUpgr here — an invalidate-only message with no data transfer, since C0 already holds the bytes; BusRdX is the general request-for-ownership that also fetches data. Either way the cost is the invalidation round-trip.) (c) At step 3 main memory is stale (0) while C0 holds the truth (5); that's write-back caching, and it's why step 4 forces C0 to flush before C1 can be satisfied. Under write-update instead, step 3 would broadcast the value 5 into C1's line in place, so C1 would stay in S=5 and step 4 would be a plain hit — no miss, but every write pays a full-line broadcast.

Distributed consistency models, from strongest to weakest

Each model is defined by what histories it forbids. Stronger models forbid more anomalies and cost more coordination.

• Strict (instantaneous): a write is visible to every replica the moment it happens. Requires a shared global clock and zero-latency propagation — a theoretical yardstick, never buildable across a network.
• Linearizable (the real "strong"): every operation appears atomic and respects real-time order — if write A finishes before read B starts, B sees A. Cost: a majority quorum round-trip per operation and unavailability during partitions. Real systems: etcd, ZooKeeper, Consul, Spanner (Raft/ZAB/TrueTime).
• Sequential: all replicas agree on one interleaving of operations, and each process's own operations keep their program order — but that global order need not match wall-clock (a write may "appear" to happen later than it really did). Cheaper than linearizable because no real-time constraint. Classic hardware/theory model; rare as a named database SLA.
• Causal: only operations with a happens-before relationship are ordered everywhere; concurrent operations may be seen in different orders by different replicas. Preserves cause→effect (you never see a reply before its post) without any global agreement. Real systems: MongoDB causal-consistent sessions, Azure Cosmos DB (a named level), COPS.
• Eventual: replicas converge "eventually" if writes stop; meanwhile any order — including reply-before-post — is legal. Cheapest, always-available (AP). Real systems: DynamoDB (default), Cassandra, Riak, DNS.

Worked interleaving

Alice posts a comment A on replica R1. Bob, reading from R2 after replication delivers A, replies with B = "agreed!" — so B causally depends on A. Now a third reader Carol on R3 pulls updates. If the store is only eventually consistent and B's replication packet happens to arrive before A's (different network paths, no ordering guarantee), Carol sees "agreed!" attached to a post that doesn't exist yet — the anomaly in the lower timeline. Under causal consistency each write carries dependency metadata (a version vector), so R3 buffers B until A has been applied, and Carol always sees A first. Notice what causal does not buy you: if Alice and a spammer post two unrelated comments concurrently, different readers may still see them in different orders — that's legal, because they are not causally related. To force one global order you must climb all the way to linearizable and pay the quorum tax.

Pitfalls

• False sharing (coherence's silent tax): two threads write two different variables that land on the same 64-byte cache line. Every write invalidates the other core's line even though the data are logically independent, generating a storm of BusRdX traffic and killing scaling. Fix: pad/align hot per-thread counters to their own line (e.g. Java @Contended, C alignas(64)).
• Assuming write-update is used: engineers reason "the other core has the new value." No — real CPUs invalidate, so the other core takes a coherence miss and reloads. Producer/consumer ping-pong on one line is far more expensive than it looks.
• Treating eventual as "a few milliseconds late": under partition or GC pause it can be seconds or worse, and there is no ordering. Read-your-own-writes breaks — a user updates their profile, refreshes, sees the old value.
• Last-Writer-Wins silently drops data: the most common eventual conflict resolver keeps the write with the higher timestamp and discards the other. Two concurrent legitimate updates → one is lost forever, with no error. Prefer CRDTs or explicit merge for anything you can't afford to lose (carts, counters).
• Calling linearizability "strict/strong" and promising instant global visibility: across regions it still costs a majority-quorum RTT and goes unavailable in a partition (CP side of CAP). If your latency SLA is 10 ms cross-continent, linearizable is off the table.
• Applying a distributed model where you needed coherence (or vice-versa): reaching for version vectors to fix a same-machine data race, or expecting hardware to keep two servers' caches coherent. They are different layers.

When to use which — and the trade-offs

Coherence: write-invalidate vs write-update

Choose write-invalidate (the default) when writes come in bursts or one core does a run of writes before another reads (the common case). You gain: one tiny invalidate message regardless of line size, and free follow-up writes once the line is Modified. You pay: the next reader eats a coherence miss. Prefer write-update only under tight producer→consumer sharing where a reader reads between nearly every write (a hot flag polled by many cores) — you keep readers warm, but pay a full-line broadcast on every write and risk saturating the interconnect, which is why virtually no modern CPU ships pure write-update.

Consistency: how a senior engineer picks a level

• Linearizable when correctness of a shared invariant is non-negotiable: leader election, distributed locks, config/service discovery, account balances, unique-ID/inventory decrement. Signal: "a stale read causes a double-spend / split-brain." Cost vs alternatives: highest latency, CP unavailability under partition.
• Causal when you need cause→effect preserved (threads, feeds, collaborative editing, session read-your-writes) but can tolerate concurrent items in any order. Signal: "anomalies are embarrassing, not catastrophic; I want availability." Cost vs eventual: dependency metadata (version vectors) and buffering; cost vs linearizable: cannot enforce global invariants.
• Eventual when availability and write throughput dominate and stale/anomalous reads are cheap to tolerate or fix: DNS, view/like counts, shopping carts (with CRDT merge), CDN edge state. Signal: "I must serve during a partition and converge later." Cost: lost-update via LWW, no read-your-writes, user-visible surprises.

Rule of thumb: start eventual, promote to causal the moment a user can observe a broken cause/effect, and reserve linearizable for the handful of keys that guard a hard invariant. Paying quorum latency on every key "to be safe" is the classic over-engineering trap.

Takeaways

• Coherence (one machine, hardware, nanoseconds, always strong) and consistency (many nodes, your protocol, milliseconds, a spectrum) are different problems that share vocabulary — name which one you mean.
• Real CPUs use write-invalidate MESI: a write's cost is the invalidate/RFO round-trip, not the data fetch, and E→M lets an exclusive owner write for free. False sharing is the bug this creates.
• Distributed "strict" consistency is unbuildable; linearizability is the real strong option and it costs quorum latency plus partition unavailability.
• Causal consistency buys you cause→effect (no reply-before-post) without global coordination; eventual buys availability but can lose data via last-writer-wins. Pick the weakest model that still forbids the anomaly you actually care about.

Sources: Hennessy & Patterson, Computer Architecture: A Quantitative Approach (MESI/MOESI, snooping and directory coherence, false sharing); Culler, Singh & Gupta, Parallel Computer Architecture (write-invalidate vs write-update trade-offs); Tanenbaum & van Steen, Distributed Systems and Kleppmann, Designing Data-Intensive Applications (consistency models, linearizability, causal and eventual, LWW/CRDTs); Herlihy & Wing on linearizability; Lamport on sequential consistency; the COPS paper and Azure Cosmos DB / MongoDB documentation for real causal-consistency systems; Amazon Dynamo paper for eventual consistency. Re-authored / deepened for this guide.