Caches, Virtual Memory, and the Page Cache

This page explains, in plain terms, how a computer moves data around while a program runs. You don't need any of it to write q, but it explains almost every "why is this fast?" and "where did my memory go?" question in kdb+.

There are four ideas:

1. The memory hierarchy: data lives in several places, from tiny and fast to huge and slow.
2. CPU caches: why reading data in order is so much faster than jumping around.
3. Virtual memory and pages: how the operating system (OS) gives each program its own view of memory, and loads data only when it is used.
4. The page cache: how the OS keeps recently read file data in spare RAM, shared by every program.

1. The Memory Hierarchy

A computer can hold data in several places. The closer a place is to the CPU, the faster it is to read, but the less it can hold:

A useful way to picture it is a person working at a desk:

RAM loses its contents when the machine restarts. Disks keep them, which is why databases ultimately live on disk.

The rest of this page, and most of kdb+'s design, is about two things: avoiding trips down the hierarchy, and making each trip count.

2. CPU Caches

The CPU can only work on data that is in its caches. When it needs a value that isn't there (a cache miss), it waits while the value is fetched from RAM, which takes about 100 times longer than reading the L1 cache.

Two facts about caches matter most:

• Data moves in blocks of 64 bytes, called cache lines. Ask for one 8-byte float and the CPU fetches the whole 64-byte line it sits in: that float and 7 of its neighbours.
• The CPU spots patterns. When a program reads memory in order, the CPU starts fetching the next cache lines before they are asked for (this is called prefetching).

So reading values that sit next to each other is cheap, and jumping around is expensive:

See It in q

This runs the same work twice: it reads all 10 million values of a float vector and adds them up. The only difference is the order of the reads:

n:10000000
v:n?100.0                 / 10 million random floats: 80 MB
inOrder:til n             / indexes 0 1 2 3 …
shuffled:neg[n]?n         / the same indexes, shuffled
\t:5 sum v inOrder
\t:5 sum v shuffled

\t:5 runs an expression 5 times and reports the total time in milliseconds. On the server this site runs on, the in-order version took about 130 ms and the shuffled version about 700 ms: 5 times slower, for exactly the same values. Your numbers will be different, but the gap should be clear.

Try the same with a vector small enough to fit in the cache, and the difference disappears:

small:1000?100.0          / 8 KB: fits in the L1 cache
smallInOrder:til 1000
smallShuffled:neg[1000]?1000
\t:10000 sum small smallInOrder
\t:10000 sum small smallShuffled

Why This Matters for kdb+

kdb+ stores each column of a table as a vector: all the values of the column, one after another in memory. When a query computes avg price, it streams through the price vector from start to end, using every byte of every cache line and letting the CPU prefetch ahead. That's a large part of why q is fast at analytics.

A row-by-row layout would interleave price with every other column, so most of each cache line would hold data the query doesn't need.

3. Virtual Memory and Pages

Every Program Gets Its Own Map

A program never sees the computer's real memory directly. Instead, the OS gives each program its own private, made-up set of addresses, its virtual address space. When q reads "address 1,000,000", the OS quietly looks up where that really is.

The lookup works on fixed-size chunks called pages. On most Linux machines a page is 4 KB:

getconf PAGESIZE    # prints 4096

For every page a program uses, the OS records where its data really is, in a lookup table called the page table. A page can be:

• in RAM, in one of the physical memory slots (called frames);
• in a file on disk, not yet loaded; or
• not in use at all.

This one level of indirection makes three things possible:

• Programs can't see each other's memory. Each one has its own map.
• The OS can move data around (or out of RAM altogether) without the program noticing, because the program only ever uses its own addresses.
• A file can be given addresses before it is loaded. This is memory mapping, the subject of the next section. An 800 GB file can be given 800 GB of addresses on a machine with 16 GB of RAM, because addresses are just entries in a table, not memory.

Page Faults

When a program reads an address whose page isn't in RAM yet, the CPU stops and hands control to the OS. This is called a page fault. Despite the name, it isn't an error: it's the normal way data gets loaded.

There are two kinds, and the difference between them is the difference between a fast and a slow query:

• A minor fault is cheap. The data is already in RAM (in the page cache, below), so the OS only has to update the page table.
• A major fault is slow. The data has to be read from disk first.

4. The Page Cache

Reading from disk is slow, so the OS keeps a copy of recently read file data in RAM. This store is called the page cache. It has three important properties:

1. It uses RAM that would otherwise sit empty. When programs need more memory, the OS shrinks the cache and hands the memory over.
2. It is shared by the whole machine. If one q process reads part of a file, a second q process reading the same part gets it straight from RAM.
3. It is invisible to programs. No program asks for it: every ordinary file read and every memory-mapped file goes through it automatically.

That second chart is why "free" memory figures are misleading. On a Linux machine that has been running a while, free -h usually shows very little memory "free" and a lot in "buff/cache". That's healthy: the "available" column is the one to watch.

free -h

Cold and Warm Queries

This explains a common puzzle. Run a query against a historical database (HDB) once, and it might take 2 seconds. Run it again and it takes 0.2 seconds.

• The first run was cold: the data had to come from disk (major faults).
• The second run was warm: the data was already in the page cache (minor faults, or none at all).

If you're timing queries, run them more than once, and say whether you measured a cold or a warm run. A query that is fast only when warm may be slow in production, after a restart or when other data has pushed it out of the cache.

Reading Memory Numbers

Different tools count memory in different ways, which is the source of a lot of confusion:

The Memory Mapping section shows these numbers changing in a real experiment, and Garbage Collection explains why heap can stay high after used falls.

Quick Reference