Memory Hierarchies and Distributed State

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

• Trace a file-backed memory access through virtual mapping, resident memory, a possible storage read, and later reuse.

• Explain why locality, working set, and memory pressure determine whether a process waits or keeps making progress.

• Separate an operating-system cache from a distributed cache while reusing the same diagnostic questions: where is the copy, what is authoritative, and what happens on a miss?

Idea in one sentence: Fast memory helps only when the data a program needs is already nearby or likely to be reused; otherwise each miss moves work to a slower, scarce layer.

Core Insight

An indexing process scans a large local file after a restart. Its source code has mapped the file into its virtual address space and now reads the next record. The code looks ordinary:

record = mapped_index[offset]

It is tempting to call this “a memory read” and stop there. That model works while the needed data is already resident and recently used. It breaks after a restart, after memory pressure has reclaimed old file pages, or when the scan jumps randomly through a file too large to keep close.

The stronger model is a hierarchy of places and costs. The CPU can use data very quickly when it is in its nearby hardware caches. The process can address a much larger virtual range, but the relevant page must be backed by usable physical memory. For a file-backed mapping, Linux can keep file data in the page cache in RAM; if the needed data is absent there, the kernel may need storage I/O before the access can complete. Exact cache levels, page sizes, replacement policy, and implementation details vary by machine and operating system. The diagnostic shape is stable: identify which layer has the needed data, which layer must supply it on a miss, and what scarce resource is under pressure.

The Small Situation: A Warm Scan Becomes a Slow Scan

Assume the index file is 8 GiB and the process reads 64 KiB ranges in increasing offset order. These numbers are illustrative.

process P -> virtual mapping -> kernel-managed file pages in RAM -> local SSD

The first run after a restart is slower. A teammate suggests more CPU because P is using little CPU while the scan stalls. That is a reasonable guess when computation is the limiting resource. Here it is incomplete: low CPU use can mean the process is waiting for data movement, not that it has spare useful work.

The visible evidence might look like this:

09:00  process starts; mapped index exists
09:01  scan throughput: 90 MiB/s; storage reads are high
09:03  scan throughput: 900 MiB/s; storage reads fall
09:05  a second sequential pass stays near 900 MiB/s

These values are a teaching trace, not a measurement from a particular host. They suggest a correction: the mapping itself did not place all 8 GiB in the CPU's fastest storage. The early pass had to establish useful resident pages; later accesses reused data that was already closer. A CPU upgrade may change some cost, but it does not by itself explain the transition from storage activity to reuse.

Virtual Address Is Permission to Address, Not a Promise of Immediate Data

In plain English:

A process can be allowed to refer to a range of addresses before every referenced byte is ready in physical memory.

In this scenario:

mapped_index[offset] refers to a location in P's file mapping. The mapping tells the kernel what file range the address represents. It does not guarantee that the required page is already resident in RAM.

Technical name:

mmap() creates a mapping in the calling process's virtual address space. On Linux, a file mapping is initialized from a file range; accessing it may later require the memory-management system to make the relevant page available.

This is a deliberately simplified teaching model. The CPU's translation hardware, page tables, kernel memory-management code, filesystem, and device driver cooperate in the real path. We do not need their implementation details to make a good diagnosis. We need to distinguish three facts that source code often merges into one word, “memory”:

The Mechanism Step by Step

Return to the first access to a file region that is no longer resident. This trace is illustrative and deliberately avoids claiming one universal kernel implementation.

starting state
  P has a valid file mapping for the index
  P reaches offset 2 GiB
  the relevant file page is not currently resident in RAM

1. address access
  P executes an instruction that reads mapped_index[offset]

2. missing resident page
  hardware and the kernel's memory-management path discover that P cannot complete this access from its current resident mapping

3. find backing data
  the kernel identifies the file-backed range; if no usable cached page exists, it asks the storage path to read it

4. wait and useful work elsewhere
  P waits for the required data while the scheduler can run another runnable task

5. make the page usable
  the data becomes resident in RAM and P can resume the access

6. reuse
  a later nearby read may find the page in RAM and may also benefit from CPU-cache locality, avoiding the earlier storage wait

This is a page-fault-shaped event: the process touched a virtual address whose required page was not presently usable in its resident mapping. Not every page fault implies slow storage I/O. A needed page can already be in RAM through another mapping or cache state, and the exact accounting differs by operating system. The useful distinction is evidence-based: if storage activity and process waiting rise together, investigate the data path and memory pressure; if the data is resident but CPU time dominates, investigate computation or scheduling instead.

The mapping does not erase isolation. P has an address range it may use according to its mapping permissions, while the kernel mediates physical memory, file pages, and storage access. This continues the previous lessons' protected-progress model: the process asks to progress; the host decides what resource condition must be satisfied first.

Locality Turns a Small Fast Layer into Useful Capacity

The CPU and RAM cannot keep every byte equally close. A hierarchy works because programs often show locality:

• Temporal locality: data used recently is likely to be used again soon.
• Spatial locality: data near a recently used location is more likely to be used soon.

The sequential index scan has both. After P reads one record, it is likely to read a nearby record. The first access may establish useful state for the following accesses. A random lookup workload has a weaker version of this story: it may repeatedly touch a small hot subset, or it may jump across a working set too large for the available fast layers.

The working set is a teaching term for the data a workload needs actively enough that keeping it resident pays off. It is not a fixed property of the binary or of the file. It changes with the request mix, the scan pattern, and other processes competing for memory.

working set fits available RAM
  -> many useful pages stay resident
  -> fewer storage waits

working set exceeds available RAM
  -> old pages are reclaimed or displaced
  -> repeated accesses miss again
  -> more waiting and I/O pressure

This buys lower common-case latency, but it costs finite memory and makes performance sensitive to access pattern. A larger cache or more RAM helps when it holds data the workload will reuse. It does not turn a one-time random scan into a locality-rich workload, and it cannot make a slow backing device disappear.

A Worked Diagnosis: CPU Is Quiet, But the Host Is Busy

Suppose P's scan slows from 900 MiB/s to 35 MiB/s at the same time another batch job begins. An illustrative host view is:

Do not treat the table as proof from four metrics alone. It earns a next investigation: confirm that P is blocked or faulting on the mapped-file path, identify which workloads expanded the working set, and check whether the file pages are repeatedly being displaced. A CPU profile by itself would be a poor first tool because P is hardly running.

The immediate intervention depends on the constraint. If the batch job is an optional scan, staggering it may protect P's working set. If the index truly needs a larger active data set, more memory or a different data layout may help. If the access is random and the file is the wrong representation, changing the workload path can matter more than tuning eviction. These are situated choices, not a universal instruction to “add RAM.”

So far, we can explain a quiet CPU and a slow process without calling the process idle or broken. Its progress is waiting on a memory-and-storage condition. The next lesson will turn another scarce resource, CPU time, into an explicit scheduling policy.

Eviction, Readahead, and Their Boundaries

When RAM is scarce, the operating system must reclaim or evict some data to make room. It cannot know future accesses perfectly. Replacement mechanisms use observations and heuristics; they can make a good prediction for a repeated scan and a bad prediction for a random workload.

For sequential file access, operating systems may use readahead: request nearby file data before the program explicitly reaches it. On Linux, MAP_POPULATE for a file mapping can cause readahead and can reduce later blocking on page faults, but it is not a guarantee that every page is immediately available. This is a useful example of the trade-off:

readahead improves: fewer waits when the next access follows the prediction
readahead costs: memory and I/O for data that may never be used
readahead fails to help when: access jumps unpredictably or memory pressure displaces the prefetched pages
signal to watch: read pattern, storage activity, available memory, and useful throughput

Do not promote a hint into a correctness mechanism. The process must still tolerate a later access that waits or fails. And do not equate a page-cache eviction with data loss: file-backed data still has its backing file, while the resident copy has been discarded or must be reloaded.

A Bounded Transfer: Distributed Caches Add Ownership and Freshness

An in-process cache, a shared Redis cache, and a CDN resemble the local hierarchy only in one useful way: a nearby copy can avoid a slower path, and misses can concentrate pressure on a deeper layer. They are not the same mechanism. A Linux page cache is host-managed RAM for file data; a distributed cache crosses process and network boundaries and can serve a copy that is stale relative to an authority.

When moving the model outward, add two questions:

Which layer is authoritative for this decision?
How stale may the nearby copy be?

For a profile image URL, a short-lived stale copy may be acceptable. For an account lock or authorization decision, the safer path may require fresher state or an authority check. The transfer is valuable only when it keeps this new ownership and freshness boundary visible; otherwise “cache hierarchy” becomes a misleading slogan.

Common Confusions

Confusion: A mapped file is entirely in RAM.

Why it is tempting: the program reads it through an address.

Better model: the mapping creates a virtual-address relationship. Individual accesses can still require resident pages and potentially storage I/O.

Confusion: Low CPU means the host is underused.

Why it is tempting: CPU percentage is easy to see.

Better model: a process can be waiting on page or I/O conditions while other resources are saturated. Pair CPU data with memory, storage, and process-state evidence.

Confusion: More cache is always faster.

Why it is tempting: a larger fast layer can hold more data.

Better model: extra capacity helps only when it retains reusable working-set data; it can still cost memory, I/O, and coordination.

Check Your Understanding

Check: A process has a valid file mapping, low CPU use, high storage reads, and a sharp drop in scan throughput after another memory-heavy job starts. Is CPU capacity the first conclusion?

Think first, then reveal.

Answer: No. The combined evidence suggests that resident data and the storage path deserve investigation first. Confirm the process's waiting or fault behavior and memory pressure before changing CPU capacity; CPU may matter elsewhere, but these signals do not establish it as the present bottleneck.

Practice: Choose the Next Evidence

An analytics service scans a local 12 GiB lookup file. After a deployment, request latency rises and CPU falls from 70% to 9%. Storage reads rise, available RAM falls, and the service's second pass over the same key range becomes much faster than the first.

What model explains the change, and what two observations would you collect before choosing a fix?

A good answer should mention:

• The deployment or competing load may have left useful file pages nonresident; early accesses took a slower miss path and later accesses reused resident data.
• Verify process waiting or fault behavior and correlate it with memory pressure and storage activity; inspect the competing workload's active data set as well.
• Do not assume that the mapping loaded the whole file or that low CPU proves spare host capacity.
• A remedy depends on the evidence: protect or enlarge the useful working set, stagger competing scans, change the access layout, or investigate the backing storage path.

Resources

• [BOOK] Operating Systems: Three Easy Pieces — Focus: Read the virtual-memory and paging chapters for working sets, locality, and the cost of a miss.
• [ARTICLE] Linux Memory Management Documentation — Focus: Locate the Linux concepts for virtual memory, demand paging, and memory-management observability.
• [ARTICLE] Linux mmap(2) Manual Page — Focus: Inspect file-backed mappings, page alignment, and the limits of mapping as a promise of residence.
• [ARTICLE/PAPER] Linux Readahead: Less Tricks for More — Focus: See how sequential access can motivate prefetching and why a prediction can be wrong.

Key Takeaways

• A virtual mapping lets a process address file data; it does not guarantee that every referenced page is already resident or fast.
• Locality makes fast layers useful because recently used or nearby data is often reused.
• Memory pressure can displace a working set and turn a previously fast path into waiting and storage I/O.
• Readahead and eviction are performance predictions with costs and limits, not correctness guarantees.
• Distributed caches reuse the miss-path idea but add authority and freshness questions that host page caching does not solve.