Page Faults, Swapping and the Page Cache

The first time Lantern answers a query after the search server starts, it reads postings from its 1.8 GB index file on the solid-state drive. A minute later the same query never touches the drive. Nothing in Lantern's code changed. The kernel kept the file's pages in RAM that nothing else wanted, and the second read became a memory copy.

Follow a page between disk and memory and three things appear: the fault that brings it in, the cache that keeps it, and the collapse when a machine needs more pages than it has. Together they explain "the second run is always faster", and the server that is up, answering pings, and useless.

The Page Fault

When an access finds no valid translation in the page table, the processor traps into the kernel, through the fault door of this chapter's first topic. The kernel then decides what the access was. A minor fault finds the page already in RAM, or needs no read at all: the first touch of freshly allocated memory, a copy-on-write break, or a file page that is cached but not yet mapped into this process. A minor fault costs on the order of a microsecond.

A major fault needs the page from storage, and it costs what the device costs, from the latency ladder in Chapter 4: tens of microseconds up to about a hundred from a solid-state drive, and 5 to 10 milliseconds from a spinning disk. Only an access to an address the process never had a right to is an error, and that one ends the process with a segmentation fault.

The page is already in RAM, or is fresh memory→Map it: minor fault, about 1 µs

The page is on storage: a file or swap→Read it: major fault, tens of µs to 10 ms

The address was never valid for this process→Kill the process: the only error

The Page Cache

Every ordinary file read goes through RAM that the kernel manages, and the pages stay there after the read. The next read of the same data, by the same process or any other, is a copy from memory instead of a device read. The cache grows into all the memory that processes are not using and shrinks when they need it back, evicting the pages that have not been used recently. The kernel's eviction is an approximation of the least-recently-used idea that Chapter 5 builds with a linked list.

Writes land in the page cache too. The page is marked dirty, the write returns, and the kernel writes the page to the device later, typically seconds later. That delay is the gap the last topic of this chapter is about.

Memory-Mapped Files

A program can also map a file into its address space, so that the file's pages appear as ordinary memory at some range of addresses. The first touch of each page is a fault that pulls the page from the page cache, or from the disk if it is not cached yet, and maps it. After that the file is read as memory: no system call per access and no second copy inside the process.

Several processes mapping the same file share one set of physical pages, the page-cache frames themselves. Five processes reading a gigabyte file this way hold one gigabyte of it in RAM between them, not five.

Lantern's Index in the Cache

Lantern's 1.8 GB index file fits comfortably in the page cache of its 8 GB server. Parsed into Python lists and dictionaries it would not fit at all. A record id stored in the file as a 4-byte integer becomes, in Python, a 28-byte integer object plus an 8-byte pointer to it in the list that holds it, as Chapter 5 shows. That is 36 bytes instead of 4, about nine times larger, and nine times 1.8 GB is around 16 GB for the postings alone.

So Lantern maps the file. Every worker process reads postings straight from the one cached copy, and the kernel keeps the hot pages resident because the workers keep touching them. There is one visible side effect. For a while after the 02:00 rebuild, the old index file and the new one are both in the page cache, so the footprint briefly nears 3.6 GB until the old file's pages age out.

The Working Set and Thrashing

A program's working set is the set of pages it touches in a short window. While the working sets of everything running fit in RAM together, major faults are rare, and memory behaves like memory. When they stop fitting, the kernel must evict pages that are needed again moments later, or push process memory out to swap, and nearly every access becomes a major fault.

A machine in that state runs hundreds to thousands of times slower than normal, because RAM answers in about a hundred nanoseconds and a solid-state drive in tens of microseconds up to a hundred. It spends its time moving pages back and forth and does almost no useful work. This is thrashing. From outside, the machine is up, answers pings and shows a busy disk, and every request times out.

Cold Caches and Memory Budgets

A benchmark's second run reads from the page cache and its first did not, so the faster number is the misleading one. A database, a search index or a build cache is fast because its hot pages are resident. A restart, a move to a fresh machine, or a large file copy that pushes those pages out makes it slow for minutes, until the cache is warm again, and that is when traffic after a failover arrives.

The same mechanism sets the memory budget. A server needs RAM for its working set, not for its whole data set, plus headroom for everything else that runs. To watch faults, swap and the page cache on a real machine, see Linux Deep Dive, chapters Storage and Disks and Performance and Troubleshooting.