LRU cache

On 13 July 1995 at 9:41 in the morning local time the shuttle Discovery lifted off from the Kennedy Space Center. That day the centre’s web server took more requests than on any other day of the surviving July log: 134 thousand, twice an ordinary day. The log for that day has 128,932 successful requests to 2230 different pages and images: the countdown clock, the launch page, the NASA logo. If you keep the hundred most recently needed files in memory and throw out the one that has gone longest without being accessed, how many requests will do without reading from disk?

A cache of a hundred pages, less than a twentieth of everything asked for that day, catches 77.37% of requests. The FIFO rule, which throws out whoever came first, catches 71.20% with the same hundred, and Belady’s rule, which knows the future and throws out the page needed latest, 86.96%. Nobody gets above the dashed line: the 2230 first requests to each page are misses at any size, and the ceiling is 98.27%. Switch to War and Peace: the words of the novel as a stream of accesses repeat less often, and the curve rises more slowly.

The idea

The cache holds up to k elements and answers each access with “present” or “absent”. When there is no room and a new one arrives, out goes the one that has gone longest without being accessed. For this to cost O(1), two structures are needed at once: a dictionary “key → node” finds an element in one step, and a doubly linked list keeps the elements in order of last access, the fresh at the front, the stale at the back. A hit takes a node out of the middle of the list and puts it at the front; a miss with a full cache removes a node from the back. Both are a few pointers.

This rule is called LRU, least recently used. Why this one, the log suggests: if a page has just been accessed, it will most likely be accessed again. The countdown clock script was requested 6199 times that day, the small NASA logo 12,066 times: it was on almost every page. Where this closeness in time comes from and how processor caches use it is told in the course chapter on caches, and the eviction of memory pages in the chapter on virtual memory. Here: how to build LRU, how good it is and where it breaks.

A dictionary and a list

A dictionary alone is not enough: it will find a page but will not say which one is the stalest; you would have to store the time of access and search for the minimum on each eviction, O(k). A list alone is not enough either: it knows the order, but to find a page in it you have to walk it, O(k) again. Together they cover each other’s weaknesses: the dictionary stores not the page itself but a reference to its node in the list. Below are thirty consecutive requests from the middle of that day.

The list is doubly linked for a reason: to take a node out of the middle, you have to join its neighbours, and for that the node must know both. In a singly linked list you would have to search for the previous node by walking. It is convenient to have a sentinel node that closes the list into a ring: then “first” is the sentinel’s right neighbour, “last” its left, and insertion and deletion have no special cases for an empty list or for the edges.

With these four places, the thirty requests give 17 hits. Change the capacity: with three places the countdown clocks, cdt_clock.pl and cdt_main.pl, push each other out more often. In Python a ready-made cache is the decorator functools.lru_cache. In CPython it is written in C, and the fallback version in Python that sits next to it shows the structure clearly: a dictionary and a circular doubly linked list with a sentinel. Its relative collections.OrderedDict has move_to_end and popitem(last=False), which are exactly the two actions of LRU. Go’s standard library has no cache, but it has container/list, and a cache is assembled from it and an ordinary map.

How much worse it is than the ideal

Belady’s rule, evicting the page that will be needed latest, is the best possible, but it requires knowing the future. On a recorded log the future is known, and Belady’s rule serves as a ruler: with a hundred pages LRU misses on 22.63% of requests, Belady on 13.04%. This is not a random gap but a guarantee.

With h = k the ratio is k: a weak guarantee, and on specially chosen requests, such as a circular walk over pages slightly more than the cache holds, LRU really does miss every time. But give LRU twice as much room as the ruler, and the ratio does not exceed two. On the NASA log LRU with two hundred pages missed 19,249 times, and Belady with a hundred 16,813: 1.14 times as often against a guarantee of 1.98. Sleator and Tarjan showed that the same holds for FIFO too, and this explains why all sensible eviction rules are close in practice: the theorem measures the worst case, and real logs do not come anywhere near it.

All sizes in one pass

The LRU curve in the first scene is computed for all 2230 sizes at once, not by 2230 simulations. This is possible thanks to a property proved in the course chapter on virtual memory: the contents of an LRU cache with k places are always contained in the contents of a cache with k + 1 places. So one can keep a single “stack” of all pages in order of last access, and a cache with k places is always its top k pages.

A page’s position in this stack before it is accessed is its stack distance: how many distinct pages were asked for since last time. A cache with k places hits exactly when the distance is less than k. One pass over the log collects a histogram of distances, and its cumulative sums are the hit rate for every size. The method was described by R. L. Mattson, J. Gecsei, D. R. Slutz and I. L. Traiger of IBM in 1970: from one record of a program’s accesses, in one pass, they obtained the behaviour of memory of any size.

On the NASA log half of all hits fall at distances below 26, which is why the curve shoots up so steeply on the left. A simple walk down the stack costs 101.8 steps per repeated access on average. If there are millions of pages, the stack is walked differently: the distance is the number of pages whose last access happened between two accesses to ours, and it is counted by a Fenwick tree over moments of time in O(log n). That is how the curve in the scene is computed; the article’s second problem has to be solved the same way.

Code

An LRU cache on a dictionary and a circular list with a sentinel in Python and on a map and container/list in Go, and next to it FIFO and Belady’s rule on the same day of the log. Belady’s rule is written on a heap of moments of next access with lazy deletion of stale entries.

The second listing is Mattson’s method: a stack in order of access, a histogram of distances, the hit rate for all sizes and a check by direct simulation.

What it costs

The memory is the dictionary and k nodes, each with two pointers. “On average” comes from the dictionary: a hash table answers in O(1) on average. The measurement: a cache with k places on random requests to 2k keys, about half of them hits. Two series: LRU on a single list in order of access (find the key, take it out, append at the end) and a dictionary with a list.

With ten places a single list holds its own: in Go a slice of ten numbers is five times faster than a map with a list, in Python only twice as slow. Further on, the linear work takes its toll: with a hundred thousand places the list is 1300 times slower in Python and 200 times slower in Go. For a cache of a dozen entries anything will do; a cache of hundreds of thousands of entries is impossible without a dictionary.

Where LRU goes wrong

A circle slightly larger than the cache. A program that walks in a circle over k + 1 pages misses on LRU every time: the page needed is always the one just evicted. This weak spot can be seen in the widget of the chapter on caches, and it is exactly what the worst case of the theorem exploits.

A one-off scan. A large sequential pass, a backup, a search engine crawler going over a site, a full read of a table, fills the cache with pages that will not be needed again and pushes out everything useful. After the pass the cache fills up again from scratch. PostgreSQL protects itself like this: a large sequential scan gets a small ring of buffers, 256 KB for reading a table, and spins in it without touching the rest of the cache.

Frequency against recency. LRU remembers only the last access: a page asked for a thousand times a day loses to one asked for once a minute ago. Rules that take frequency into account too, LFU, 2Q, ARC, are covered in the article LFU and ARC.

The price of precision. Moving a node on every access is expensive when there are billions of accesses a second or when two pointers per element are too much. So systems more often use approximations. Many operating systems and PostgreSQL use a “clock”: one bit or a small counter per page and a hand going round (how it works is in the chapter on virtual memory); the first scene shows that the clock keeps almost level with LRU. Redis in allkeys-lru mode keeps no order at all: when memory runs short, it takes a few random keys, five by default, and evicts the stalest of them, and since version 3.0 it also keeps a pool of good candidates; the documentation explains the choice by the fact that exact LRU costs more memory. In the Linux kernel pages long lived on two lists, active and inactive, and version 6.1 brought the multi-generational LRU developed at Google.

History

In 1966 László Bélády of IBM published a large comparison of page replacement rules for a machine with virtual memory and described the unattainable best rule: evict whatever will be needed latest (more in the course chapter). In 1970 Mattson, Gecsei, Slutz and Traiger, in the IBM Systems Journal, introduced stack algorithms, which include both LRU and Belady’s rule, and showed how to get the behaviour of memory of any size in one pass over a record of accesses. In 1985 Daniel Sleator and Robert Tarjan proved in Communications of the ACM that LRU and FIFO are at most k/(k − h + 1) times worse than Belady’s rule, and that no better can be guaranteed. This comparison of an algorithm that does not know the future with one that does began the competitive analysis of online algorithms; the name itself appeared in 1988.

The log on which the scenes and listings run was collected by Jim Dumoulin of the Kennedy Space Center, and Martin Arlitt and Carey Williamson put it into the open Internet Traffic Archive: it is one of the six logs on which they looked for common patterns in web server load for a 1996 paper. The client addresses are kept in the log, but the archive asks that nothing be analysed beyond the general picture of the traffic; here there are no addresses at all, and search queries and user names in paths are replaced by numbers.

Problems

In the first you have to write an O(1) cache and run the same day of the NASA server and large logs through it, where a slow cache will not make it in time. In the second you have to say for each cache size how many requests it will catch, in one pass, like Mattson, but faster than by walking down the stack.