LFU and ARC

The article on the LRU cache had one day of the Kennedy Space Center web server: 13 July 1995, the day Discovery launched. Here is the whole week, from Monday the 10th to Sunday the 16th: 538,838 requests to 4258 pages and images. Let us compare three eviction rules: LRU evicts what has gone longest without a request, LFU what was requested least often, and ARC decides by itself which to trust more.

Switch to “13 July”. Over one day LFU beats LRU: with a hundred places 79.99% hits against 77.37%, and with 25 places 59.5% against 48.6%. Over the week the picture is the reverse: LRU catches 68.65% of requests, LFU 61.89%, and it falls behind as early as Tuesday. With a hundred places ARC is better than both over the week (73.13%) and over the day (80.53%); only on the day with 25 places is LFU slightly ahead, 59.48% against 59.32%. The dashed line is Belady’s rule, which knows the future: 81.87% over the week. ARC comes closest to it.

The idea

A cache has two signs that a page will be needed again: it was asked for recently, and it was asked for often. LRU looks only at the first, LFU only at the second, and each loses where the other matters. ARC keeps both groups, pages asked for once and those asked for at least twice, and remembers the numbers of pages recently evicted from each group. If an evicted “fresh” page is asked for again, the fresh group has too little room; if an evicted “frequent” one, the frequent group. The boundary between the groups moves by itself.

Why does frequency help at all? A web server log has pages that are always asked for: the logo, the home page, the countdown clock. They are worth keeping in the cache even if the last request was a minute ago and many one-off requests to old archives have gone by in that minute. LRU gives a place to each one-off request and evicts the logo for it; LFU will never evict the logo. But “never” has a price, and the week shows it.

LFU in O(1)

Each page in the cache has a counter: how many times it was asked for since it got there. The page with the smallest counter is evicted, and among equal ones the one gone longest without a request. The smallest can be found with a heap in O(log c), but there is a faster way: buckets. Bucket f holds the pages with counter f, ordered by last access. A hit moves a page from bucket f to the end of bucket f + 1, and the first page of the smallest bucket is evicted. The number of this bucket need not be searched for: a new page comes with counter 1, so after a miss the smallest counter is 1, and after a hit it shifts only if the minimum bucket became empty, and then it becomes one larger. Each operation is O(1); this is how Ketan Shah, Anirban Mitra and Dhruv Matani described it in 2010.

Now about the price. Look at what is happening in LFU in the middle of the week.

In LFU almost all places are taken by pages with counters in the hundreds and thousands. All new pages jostle for the one remaining place: a newcomer comes with counter 1, and the next newcomer evicts it before it can collect a second request. The listing counts: on Sunday evening only one of LFU’s hundred places is taken by a page with a count below four. Among the old-timers is the countdown image /shuttle/countdown/count.gif with a count of 296: on Sunday, three days after the launch, nobody asked for it. This is freezing: the counters remember the past, and the cache stops keeping up with what is asked for now.

It is treated in two ways. The first is ageing: from time to time halve all the counters, so that yesterday’s merits melt away. Redis does this in the allkeys-lfu policy: a key has an approximate counter of a few bits that grows ever more slowly, and it decreases if the key has not been touched for a long time. The second is not to let frequency decide everything: keep a separate window for newcomers where they can build up a count. How many places to give the window is a question without one answer for all logs. ARC answers it by itself.

ARC: two halves and ghosts

ARC keeps two LRU lists in the cache. T1 holds the pages asked for once since they got into the cache; T2 those asked for at least twice. A second hit moves a page from T1 to T2. Together T1 and T2 take at most c places, and the boundary between them is set by the target size of T1, the number p.

The key is two “ghost” lists, B1 and B2. They hold not pages but only the numbers of pages recently evicted from T1 and T2. A number takes a few bytes, a page kilobytes, so remembering c more numbers is almost free. The ghosts are a memory of mistakes. If a request came for a number in B1, the cache recently evicted a page asked for once, and it has been asked for again. Had T1 had more places, this would have been a hit; so p grows. A request for a number in B2 means a frequent page was evicted in vain, and p decreases. The step is larger the smaller the ghost list the request fell into: a rare hit in a small list is a strong argument.

A place is freed like this: if T1 has more than p pages, the oldest of T1 goes to B1, otherwise the oldest of T2 goes to B2. There is a subtlety for a request from B2 when |T1| = p: then T1 gives up the place too; the full rules are in the article’s second problem.

Over the week of the NASA log ARC keeps p at about seven: of a hundred places, seven for pages asked for once and ninety-three for repeated ones. The stream, as LFU showed, likes frequency, but with no places at all for newcomers, as in LFU, the cache freezes. ARC found this balance by itself, without tuning, and over the week it is 4.5 percentage points better than LRU and 11 better than LFU. The middle scene shows it: ARC’s orange T1 cells on the left change all the time, the blue T2 ones more slowly, while in LFU one last place flickers.

Hence the resistance to scans. When a crawler goes once over all the pages of a site, each of them lands in T1 and displaces only T1; the T2 pages that are asked for all the time are not touched. In LRU such a pass sweeps out the whole cache.

Code

LRU on an ordered dictionary, LFU on counter buckets, ARC with four lists and Belady’s rule, on the day of 13 July and on the whole week, with hit shares by day. At the end the listing looks into LFU’s cache on Sunday evening and prints ARC’s mean p by day.

What it costs

All three working rules are O(1) per request, and the difference between them is not in speed but in hits. Four and a half percentage points between ARC and LRU this week are 24 thousand requests that did not reach the disk, and eleven points between ARC and LFU about 60 thousand. ARC pays with memory for the ghosts and with each operation touching two or three lists instead of one.

Where it works

ZFS. The ZFS file system cache is called just that, ARC; the source code cites the paper of Megiddo and Modha and lists the differences: blocks there are of different sizes, from 512 bytes to 128 KB, and as many blocks have to be evicted as the new one needs.

PostgreSQL. In version 8.0 the buffer cache worked by ARC. A patent application by IBM had been filed on the algorithm, and in 8.0.2 it was replaced with the similar and slightly simpler 2Q, which had been published earlier. In 8.1 the buffer manager was rewritten to use a “clock”, a single hand that goes round the buffers and decreases their usage counts. This scheme needs fewer locks than ARC, and on multiprocessor machines that turned out to matter more.

Redis. The allkeys-lfu policy appeared in version 4.0. To avoid storing an honest counter, Redis keeps in each key an approximate Morris counter, which grows with a probability that falls as it grows, and decreases it over time.

Caffeine. The Java cache is built on W-TinyLFU by Gil Einziger, Roy Friedman and Ben Manes: a small LRU window for newcomers, and the decision whether to admit a newcomer in place of the eviction candidate is made by an approximate frequency counter based on a Count-Min Sketch. This is the same treatment of freezing as in ARC: newcomers have a place of their own, and frequency only decides who stays for long.

History

The idea of taking into account more than the last access appeared in databases. In 1993 Elizabeth O’Neil, Patrick O’Neil and Gerhard Weikum proposed LRU-K: evict the page whose K-th access from the end was the longest ago. In 1994 Theodore Johnson and Dennis Shasha described 2Q: new pages first live in a short queue and pass into the main one only if asked for again. Both rules need parameters tuned to the load. Nimrod Megiddo and Dharmendra Modha presented ARC at the FAST conference in 2003; it tunes its own parameter and runs in O(1). By their measurements it is almost as good as the same rule with the best fixed p, chosen in hindsight for the log, and noticeably beats LRU.

Problems

The first problem is LFU in O(1) and its eviction queue on a real log. The second is ARC by all the rules, including the subtle places where it is easy to go wrong.