
Cache eviction: when are randomized algorithms better than LRU? (2014) - signa11
http://danluu.com/2choices-eviction/
======
ordinaryperson
Related: the author, Dan Luu has, IMHO, one of the best IT-related Twitter
feeds out there: [https://twitter.com/danluu](https://twitter.com/danluu)

Highly recommended.

------
falcolas
One thing I've seen is that a weighted LRU is usually slightly better for
unpredictable workloads. i.e. it will never evict high use cache data when
there's a flurry of one-off traffic that would normally start evicting a
normal LRU cache, and even a 2 random LRU scheme.

This is particularly relevant for databases and keeping rows in memory.

The algorithm is something like "add two weight when an item is used, and
decay one from every item every second, evict items under pressure from the
lowest weight to the highest."

~~~
rozim
Well, once you go down this path you gotta consider ARC:
[https://en.wikipedia.org/wiki/Adaptive_replacement_cache](https://en.wikipedia.org/wiki/Adaptive_replacement_cache)
as I believe it is designed to be scan-resistant.

~~~
logophobia
Which is, unfortunately, patented: [http://patft1.uspto.gov/netacgi/nph-
Parser?Sect1=PTO1&Sect2=...](http://patft1.uspto.gov/netacgi/nph-
Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=6996676.PN.&OS=PN/6996676&RS=PN/6996676).

~~~
takeda
Hmm given that patents span for 20 years, and that's essentially forever in
computer world, once this patent expires it probably will be worthless.

In a world where advances are built on top of other advancements, patents just
stifle innovation.

~~~
noonewhocounts
And yet innovation proceeds at a pace unmatched in history, and is so
commonplace it gets dismissed as not counting when it's not a revolutionary
breakthrough.

~~~
takeda
When you're referring to innovation, you're talking about everything. I'm
referring to software.

~~~
stilldontcount
It's relatively impolite to tell someone what they meant

------
jandrese
Are there any languages that allow you to give the compiler a hint that you're
about to grind over a gigantic dataset so don't bother to cache any of this
data because it won't be accessed again for a long time? It seems like it
could be helpful in keeping a big crunch from obliterating the cache
constantly. You might also be able to apply other optimizations, like
preloading the next data blocks so they're ready when the CPU rolls around.
Maybe compilers already do this behind the scenes?

~~~
dom0
Don't. Yes, there are instructions for this. No, don't use them, unless you
really exactly know what you are doing and optimizing towards a specific,
single µarch _only_ , otherwise they will invariably hurt performance, not
improve it.

Similarly explicit prefetching usually does not improve performance, but
reduces it.

(Non-temporal stores are quite a good example here, since a game engine used
them in a few spots until recently, causing not only worse performance on
Intel chips, but also heavily deteriorated performance on AMD's Zen µarch.
Removing them improved performance for all chips across the bank. Ouch!)

~~~
vvggff
Links, examples, tutorials?

------
SomewhatLikely
This 2 random cache scheme reminds me a lot of the 2 random load balancing
scheme laid out in "The Power of Two Choices in Randomized Load Balancing"
[https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis....](https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.pdf)
Which shows an exponential improvement in choosing the less loaded of two
randomly chosen servers over just random.

~~~
colonelxc
It is indirectly referenced near the bottom of the page, with a pointer to
[http://brooker.co.za/blog/2012/01/17/two-
random.html](http://brooker.co.za/blog/2012/01/17/two-random.html), which
references
[http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...](http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf)

------
j2kun
The "2 random choices" idea also shows up as a good idea in other settings,
such as load balancing for hashing. I wrote a writeup[1], but if you google
"power of two random choices" you'll see a lot of literature on it.

[1]: [https://jeremykun.com/2015/12/28/load-balancing-and-the-
powe...](https://jeremykun.com/2015/12/28/load-balancing-and-the-power-of-
hashing/)

------
krallja
Redis supports LRU and random eviction: [https://support.redislabs.com/hc/en-
us/articles/203290657-Wh...](https://support.redislabs.com/hc/en-
us/articles/203290657-What-eviction-policies-do-you-support-)

I wonder if it would be worth adding a k-random eviction strategy, for a
balance between the two.

~~~
antirez
Hello, now Redis (4.0, still in release candidate) supports LFU (Least
Frequently Used) which should work better in most cases since LRU also is also
just a way to approximate LFU, since the most frequently used items are often
the last recently used ones.

~~~
danbruc
_[...] since LRU also is also just a way to approximate LFU, since the most
frequently used items are often the last recently used ones._

That is not really true. LRU and LFU favor different items, LRU ones used
frequently in the short term, LFU ones used frequently in the long term. Only
under special circumstances does one approximate the other, for example if
your cache is large enough that LRU does not evict the most frequently used
items when many less frequently used items are placed in the cache before the
most frequently used items are accessed again, then LRU approximates LFU.

~~~
antirez
What I mean is that, the most frequently used objects, if accessed roughly
with an even period of time, tend to be also the least frequently used
objects, so if the accesses are very even LFU and LRU tend to be similar. For
uneven access patterns, they are different, but usually LRU is used because
access patterns are even so that it approximates LFU, since what we want to
have in cache is, without other application-specific clues, the objects that
we use more often. Knowing _exactly_ the access pattern one can use an
application-assisted strategy which is optimal, but without clues LRU adapts
well to different scenarios while LRU may fail in a catastrophic fashion.

Also note that your idea of LFU (in this context), from what you write, is
perhaps one that does not adapt over time. Redis LFU employs a decay strategy
so that the recent frequency is computed, not the whole-lifetime frequency of
access, so even short lived items accessed very frequently for some time, will
do well and will not get easily evicted.

Full story: [http://antirez.com/news/109](http://antirez.com/news/109)

~~~
danbruc
That is what I meant, under specific assumptions about the access pattern they
can show similar behavior. Classical LFU tracking the absolute frequency of
items will keep items that are used frequently in absolute terms but
infrequently in terms of the instantaneous frequency in the cache while LRU
will evict such items in favor of items with high instantaneous frequency.
Those two algorithms are in some sense two extremes, LRU cares about what is
most frequently used right now, LFU cares about what is most frequently used
over the entire lifetime of the cache.

The LFU variant you describe in the linked article is somewhere in the middle,
it tracks the absolute frequency of access just like classical LRU but then it
also decays this frequency and therefore turns it into something like a
weighted and averaged relative frequency. But it is, at least for me, hard to
tell what exactly the algorithm tracks, how the accesses are wighted over time
and therefore were exactly this falls on the spectrum between LRU and
classical LFU.

Algorithms like ARC and CAR also try to strike a balance between LRU and LFU
with the difference that they adaptively control where on the spectrum to
operate.

~~~
antirez
Yes, there is a tuning problem indeed. I made two parameters user-tunable (the
decay and the logarithm factor of the Morris counter), but tuning needs some
expertise. I've severe limitations on the number of bits I can use per object,
but depending on the user feedbacks I may try some auto-adaptive approach as
well in the future.

~~~
NovaX
I used hill climbing to tune TinyLFU. A larger admission window improves
recency-biased workloads, while a smaller improves for frequency. By sampling
the hit rate and making an initial adjustment, it can determine when to change
directions and hone in on the best configuration. Other than a small warm-up
penalty, it quickly optimizes itself.

------
danbruc
_[...] choosing the least recently used (LRU) is an obvious choice, since
you’re more likely to use something if you’ve used it recently._

There are many other cache replacement policies [1] and they can outperform
LRU especially if the quoted assumption is not true. It is for example quite
common to have two types of data, one is frequently reused over very long
periods, the other is reused over short periods after the first use. In those
cases a more complex policy like ARC or CAR can provide noticeable
improvements.

[1]
[https://en.wikipedia.org/wiki/Cache_replacement_policies](https://en.wikipedia.org/wiki/Cache_replacement_policies)

~~~
bnegreve
> There are many other cache replacement policies [1] and they can outperform
> LRU especially

The article is about CPU caches so speed and memory usage are very critical.

One of the main benefit of LRU is that it only needs one extra bit per cache
line.

~~~
flgr
> One of the main benefit of LRU is that it only needs one extra bit per cache
> line.

This might be well known, but why's that? I've recently seen a Go
implementation of LRU and it uses a lot of memory. Maybe this would allow us
to save some of that in a better implementation.

~~~
danbruc
Requiring only a single bit is only true for a two-way set associative cache,
i.e. the content stored at every memory address may only be cached in two
different cache slots. In this case you can simply flag the other
corresponding cache entry you did not access as least recently uses every time
you access a cache entry.

The implementation in software was probably fully associative, i.e. every item
can be cached in every slot. This requires a lot more memory and it is the
same for caches in processors, they require more additional bits and logic the
more freedom they have where to cache the content of every address.

To be more precise, you have to keep track of the order all cache entries were
accessed which requires at least about n * log(n) bits unless you only
implicitly store the access order by using something like move to front.

------
kazinator
LRU is predicated on locality of reference.

Ideally we could peer into a crystal ball and know which items are going to be
accessed in the near future and keep those in the cache at all costs. Since we
don't know that, we use a predictor based on past behavior. If past behavior
is random, then prediction is for shit. So we assume that behavior has
locality: something referenced recently is more likely to be referenced again
than something not referenced recently. Based on that guess, we sort things
from least recently used to most recently (or approximately sort, using aging
tricks to avoid actually sorting), and boot out the least recently used
entries.

If accesses are completely random, then the LRU selection is pure overhead. Or
worse; some patterns, like repeated sequential accesses of something large
through a small cache, are anti-locality. If we are accessing a big buffer in
a circle, then the next thing we are accessing at all times is _precisely_ the
least-recently used item that LRU wants to boot out.

For situations like that, caching mechanisms sometimes support some API for
providing a hint. "These memory locations are going to be needed soon". "This
memory mapped file is being sequentially accessed". And such.

------
SomewhatLikely
Another characteristic of the data which would make random particularly bad is
if reloading/recomputing the most popular items took significantly longer than
reloading unpopular items. This could be the case for instance if item data
size grew in proportion to popularity.

------
mapgrep
Dumb question, what is "2-random"?

~~~
sethammons
From the article:

...on real workloads, random tends to do worse than other algorithms. But what
if we take two random choices and just use LRU between those two choices? __

" 2-random" is his short hand for the above scenario.

[edit: formatting, I have no idea how to signify a quote; I don't want
preformatted because it makes a scroll box.]

~~~
AnimalMuppet
On HN, typically a quote is done like this:

> This is a quote. It won't become a scroll box, no matter how long it gets.
> It will just wrap to the next line. True, the next line won't begin with a
> ">" character, but the convention is that the whole paragraph is a quote if
> the first line begins with a ">".

------
PaulHoule
Often you can get away with dumping the whole cache when it fills up and
starting fresh.

~~~
Coding_Cat
that's a horrible pattern. As soon as you go 1 bit over your cache size in a
hot loop you'll have a 100% miss rate. (assuming each element is loaded once
in the hot loop).

~~~
rspeer
You don't use this pattern while looping. You use it while memoizing results
that you don't want to compute again.

Here's an example, in the Python package wordfreq [1]. When you look up word
frequencies, there's some normalization it has to do to your text. Some words
are very common, and it would be silly to normalize them repeatedly. So
frequency lookups are cached.

The cache dictionary has a maximum size of 100,000, so that exceptional or
malicious cases don't use up all your memory. It is extremely rare for text to
contain 100,000 distinct words, but if that happens, the cache gets full and
the entire thing is dropped. It will quickly be re-populated with common
words, of course.

Yes, you can make this perform horribly by looking up frequencies of ["zero",
"one", "two", "three", "four", ..., "one hundred thousand"] in a loop. That's
not realistic data.

Do you actually have a suggestion for how to do this faster? We benchmarked
this against other cache strategies (with smaller cache sizes so it would drop
sometimes) on realistic data. It's much faster than Python's LRU decorator,
for example.

[1]
[https://github.com/LuminosoInsight/wordfreq/blob/master/word...](https://github.com/LuminosoInsight/wordfreq/blob/master/wordfreq/__init__.py)

------
nsebban
When the cost of retrieving an item from your slower storage is pretty much
the same for every item, may it be old or new, small or big, popular or not.

------
pacificleo11
Ajax made predictive (random)prefetching mainstream .its only natural that
random eviction algorithm are coming along . when you pick one end of stick
you pick another too

