Cache Coherence at Scale - NUMA & Directory Protocols

By the end of this lesson, you will be able to...

• Trace how placement changes the path of a read or ownership transfer on a multi-socket machine.

• Explain why directory metadata can replace broad coherence broadcasts with targeted messages.

• Design a locality experiment from a cross-socket performance symptom.

Idea in one sentence: Large coherent machines preserve shared memory across physical distance, so data placement and selective coordination determine how much that illusion costs.

Core Insight

Imagine a worker on socket A allocating a queue. Later, the scheduler runs its busiest consumer on socket B.

The program still sees ordinary shared memory. The queue still works. Yet p99 latency rises when the consumer moves to B.

The small-machine model says:

Memory is shared, and MESI keeps the caches coherent, so placement should not change much.

Correctness is not the same as uniform cost. On a multi-socket system, a core may be closer to one memory controller and farther from another. Moving write ownership across sockets also uses the interconnect. The same load or store can follow a different physical path depending on where the thread, memory page, and current cache-line owner are located.

Scale turns coherence into a topology problem.

A Simplified NUMA Machine

NUMA means Non-Uniform Memory Access. The logical address space is shared, but access cost depends on placement.

Use this teaching model:

Socket A                                 Socket B
+-------------------+                   +-------------------+
| cores and caches  |                   | cores and caches  |
| memory controller |                   | memory controller |
+---------+---------+                   +---------+---------+
          |                                       |
      local memory A ===== interconnect ===== local memory B

A core on socket A usually reaches memory attached to A through a shorter local path than memory attached to B. A remote access still uses the shared-memory abstraction, but it consumes interconnect bandwidth and often takes longer.

Three locations now matter:

• where the thread runs;
• where the memory page was allocated;
• where a writable cache line is currently owned.

They can disagree. A thread may run on B, access a page allocated near A, and request a line currently modified in A's cache hierarchy.

This does not mean a NUMA machine is literally a distributed software system. The hardware provides stronger and faster mechanisms. The analogy is narrower: distance, ownership, and placement have become observable costs.

First Touch Creates a Placement Hypothesis

Many operating systems use policies in which the node that first faults or touches a page influences its physical allocation, subject to system and process policy. Treat that as a hypothesis to verify on the target platform, not a universal language guarantee.

Consider this sequence:

1. initialization thread on A allocates and writes a 4 GB working set
2. worker threads later run mostly on B
3. workers repeatedly read and update that working set

The program's ownership model says “B owns this work now.” Physical placement may still say “the pages live near A.” The workers pay remote access until pages move, policy changes, or work moves closer to the data.

Possible responses include:

• initialize data on the node that will use it;
• bind or prefer allocation on selected nodes;
• keep worker placement near the relevant pages;
• interleave pages when broad access matters more than strict locality;
• shard work and data by NUMA node.

Each response trades locality against flexibility. Hard binding can improve the common path but leave one node overloaded while another is idle.

Coherence Has a Fanout Problem

The previous lesson used two cores. A writer invalidated one other shared copy. Now imagine many cache agents across several cores or sockets.

A simple snooping model makes coherence requests broadly visible. Every participant observes a request and decides whether it holds the line. This can be attractive in a small enough design because lookup is distributed and the protocol is conceptually direct.

As the participant count and topology grow, broad notification consumes bandwidth even when most caches do not hold the line.

The scaling question becomes:

How can the system contact the caches that matter
without asking every cache about every line?

A Directory Tracks Who Matters

A directory-based protocol stores metadata about a cache line's coherence state. A simplified entry may identify:

• an owner when one cache has the modified line;
• a set or representation of sharers;
• whether memory or another cache can supply current data.

Suppose line L is shared by A and C. B does not hold it.

Directory for L:
  state: shared
  sharers: A, C

When D requests write ownership, the directory can target A and C:

D requests L for writing
  -> directory finds sharers A and C
  -> invalidations go to A and C
  -> acknowledgements return
  -> directory records D as owner
  -> D may modify L

B receives no coherence message for L because the directory has no evidence that B holds it.

This is the trade-off:

broad snooping
  spends communication to avoid explicit per-line sharer lookup

directory coordination
  spends metadata and lookup complexity to target communication

Directories themselves must scale. An exact bit per possible sharer can consume substantial metadata in a many-core system. Real designs use different encodings, hierarchy, sparse representations, or filters. The lesson's durable model is selective coordination, not one universal directory layout.

Check: What does a directory save when only two of sixty-four cache agents hold a line?

Think first, then reveal.

Answer: It can direct invalidation or ownership messages toward the actual sharers instead of making every agent process a broad request. It pays for that selectivity with directory metadata and lookup work.

The Directory Is a Map, Not Necessarily the Data

It is easy to imagine the directory as one enormous cache that stores every current line. That is the wrong abstraction. The directory's essential job is to record enough coherence information to route the next action.

Consider three simplified cases for line L:

The exact data path depends on the machine. The stable reasoning pattern is that metadata answers “who must participate?” A directory that says B owns a modified copy prevents the system from returning an older memory value as though it were current.

This creates its own engineering pressures. Directory lookup adds latency. Sharer representations consume space. A hot directory slice can become a concentration point. Hierarchical systems may need several lookups as a request crosses topology levels.

So “use a directory” does not remove coherence cost. It changes the scaling strategy from broad observation to routed coordination. That is beneficial when avoiding irrelevant participants is worth the metadata and routing machinery.

Separate Page Distance from Line Ownership

A remote-looking latency symptom can have two related but distinct causes.

Remote page placement means the worker often reaches memory attached to another node. This is especially visible when the working set misses the caches or streams through large regions.

Remote line ownership means another cache currently holds the writable or modified line. Even if the page's home memory is local, a writer may need to coordinate across the interconnect to obtain ownership from a remote core.

Use two contrasting access patterns:

Pattern A: B streams once through pages allocated near A
Pattern B: A and B alternately update one small shared queue line

Pattern A emphasizes where pages and memory controllers are located. Pattern B may fit almost entirely in caches, yet still pay repeated cross-socket ownership transfers. Both consume the interconnect, but the best fixes differ.

For pattern A, first-touch placement, binding, interleaving, or moving computation closer to data may help. For pattern B, changing page placement alone may do little; sharding the writable metadata or changing the communication pattern targets the repeated handoff.

Do not reduce both symptoms to “NUMA is slow.” Name which path you think is expensive, then choose a measurement and intervention that can distinguish it from the other path.

A Cross-Socket Ownership Trace

Return to the queue allocated near socket A. The queue's head and tail share frequently written metadata. Consumers now run on both sockets.

starting state:
  pages allocated near A
  hot queue line owned by a core on A

step 1:
  B consumer updates the queue
  -> ownership request crosses the interconnect
  -> directory or coherence fabric finds current owner/sharers
  -> remote copies are invalidated or downgraded

step 2:
  A producer updates the same line
  -> ownership moves back toward A

result:
  queue remains correct
  useful work now includes repeated cross-socket coordination

The visible symptom may be lock contention, but the mechanism also includes location. One shared queue can combine software waiting with cache-line movement and remote memory access.

Sharding the queue by NUMA node changes the common path:

A workers mostly update A-local queue metadata
B workers mostly update B-local queue metadata
occasional balancing crosses the boundary

The design has not removed coordination. It has moved it from every operation to less frequent balancing.

Check: Why might a single global queue look acceptable on one socket but degrade sharply on two?

Think first, then reveal.

Answer: The second socket adds physical distance and can make hot writable lines cross the interconnect. More workers add contenders while the global metadata remains one ownership bottleneck.

Build a Locality Experiment

Do not diagnose NUMA from machine size alone. Compare controlled placements.

For the queue service, run the same representative workload in three configurations:

1. threads and memory unconstrained;
2. threads and their queue shard kept on one NUMA node;
3. per-node shards with occasional cross-node balancing.

Collect:

• throughput and p99 latency;
• remote versus local memory evidence available on the platform;
• inter-socket or cache-to-cache traffic when measurable;
• lock or queue contention;
• CPU utilization per node;
• queue imbalance and work-stealing frequency.

Interpret the whole result. Lower remote access with severe queue imbalance is not automatically a win. Locality is useful when it improves the user-facing or workload objective without creating a worse saturation point.

Trade-offs and Limits

NUMA-aware placement reduces distance on the common path, but it constrains scheduling and allocation. Per-node sharding reduces shared writes, but it adds balancing and can make capacity uneven. Directory protocols reduce unnecessary fanout, but they consume metadata, storage, and protocol complexity.

These costs belong in the same result: locality without enough usable balance can simply move the bottleneck.

Hardware details differ. Some systems use directory-like structures, snoop filters, hierarchical coherence, or protocol variants beyond the simple model here. Software also has limited control over exact cache-line placement.

Use this lesson to form testable hypotheses:

• “the pages are remote from the worker”;
• “the hot line is moving across sockets”;
• “global sharing costs more than per-node balancing.”

Then use platform-specific counters, placement tools, and benchmarks to decide whether the hypothesis matters.

Practice: Change One Placement Rule

A four-node server processes independent tenant partitions. Threads are scheduled freely, and one initialization thread allocates every partition. The system has balanced CPU usage but high remote-memory traffic and unstable p99 latency.

Propose one placement change and one failure boundary.

Model answer: Allocate or migrate each tenant's hot partition near the workers that normally process it, and prefer running those workers on the same node. Compare remote-access evidence and p99 before and after. Keep a bounded rebalance path because strict affinity can overload one node; abort or relax placement if queue age diverges across nodes even while remote traffic falls.

Resources

• [BOOK] A Primer on Memory Consistency and Cache Coherence — Focus: Study directory coherence as a selective scaling mechanism beyond the stable MESI states.
• [DOC] Linux Kernel: NUMA Memory Policy — Focus: Connect placement hypotheses to task, VMA, and shared-memory policies.
• [DOC] numactl Manual — Focus: See concrete controls for binding, preferred nodes, and interleaving.

Key Takeaways

• Coherent shared memory preserves correctness, not uniform access cost.
• Thread location, page placement, and cache-line ownership can point to different NUMA nodes.
• Directory protocols trade metadata and lookup work for targeted coherence messages.
• Locality experiments must measure both remote cost and the imbalance introduced by placement constraints.