Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

danluu.com

Post reply on HN
Print view View original

31–40 of 44 posts

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#31

Post by NovaX »

shereadsthenews wrote: post #28
harryf wrote: post #18

Worth reading http://open-zfs.org/wiki/Performance_tuning about the Adaptive Replacement Cache algorithm ( https://en.m.wikipedia.org/wiki/Adaptive_replacement_cache ) which is less vulnerable to cache flushes than LRU

The only big gain of ARC is the adaptive sizing. If you can live with static sizing you will do just as well with 2Q, which is not patented. I haven't used a true LRU in quite a while because the coordinated bookkeeping required is as disaster on multithreaded programs. ARC and 2Q can be largely lock-free.

Can you explain how ARC can be more easily lock-free than LRU? ARC has to coordinate 4 doubly-linked lists and a pivot on every access.

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#32

Post by NovaX »

6keZbCECT2uB wrote: post #17
Scaevolus wrote: post #13

Earlier quoted context omitted.

LHD is more optimal than LFU on most workloads. It's harder to implement, but more accurately computes the actual expected value of each cache item. https://www.cs.cmu.edu/~beckmann/publications/papers/2018.ns...

I glanced through the paper and didn't see a comparison to TinyLfu. Unfortunately, it seems to be a misleading name which would make one think it was simply an LFU algorithm. The description in caffeine seems to indicate that it's more of an LRU algorithm with an LFU admission heuristic. If the overhead of the cache itself is significant, as in kernel virtual memory management. A clock based algorithm is usually pref…

Naming aside, the structure is . The latest version of that is adaptive, where the front LRU may grow or shrink based on the workload. This allows the cache to mimic LRU for recency-skewed workloads (e.g. job queues) and LFU for frequency-skewed ones (e.g. loops). In a stress test, ARC and LIRS had 20% hit rate, Caffeine has 39.6%, and Optimal is 40.3%.

https://user-images.githubusercontent.com/378614/52891655-29...

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#33

Post by shereadsthenews »

NovaX wrote: post #31
shereadsthenews wrote: post #28

Earlier quoted context omitted.

The only big gain of ARC is the adaptive sizing. If you can live with static sizing you will do just as well with 2Q, which is not patented. I haven't used a true LRU in quite a while because the coordinated bookkeeping required is as disaster on multithreaded programs. ARC and 2Q can be largely lock-free.

Can you explain how ARC can be more easily lock-free than LRU? ARC has to coordinate 4 doubly-linked lists and a pivot on every access.

You can implement ARC that way and there is a Go library on GitHub that does, but that is not going to scale well. Normally you won't need to evict from the frequently-used list, and there is no need to maintain LRU order on that cache during access. One need only atomically update the access time of the entry and defer ordering until such a time as eviction is required. During an access only a read lock on that cache is needed. During eviction from frequently-used you need exclusive access to all four structures, but if you can arrange for that to be rare, you'll have uncontested read access to your hot items without the need to maintain the LRU property.

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#34

Post by NovaX »

shereadsthenews wrote: post #33
NovaX wrote: post #31

Earlier quoted context omitted.

Can you explain how ARC can be more easily lock-free than LRU? ARC has to coordinate 4 doubly-linked lists and a pivot on every access.

You can implement ARC that way and there is a Go library on GitHub that does, but that is not going to scale well. Normally you won't need to evict from the frequently-used list, and there is no need to maintain LRU order on that cache during access. One need only atomically update the access time of the entry and defer ordering until such a time as eviction is required. During an access only a read lock on that cach…

That certainly helps, though you assume strict LRU vs approximate ARC. One can of course use similar schemes on LRU (like memcached does) or sampling LRU, making it approximate but reducing the lock contention. The technique that I've used is to buffer and replay events against the policy, so that reads are just a CAS into a ring buffer and replaying is under performed under a non-blocking lock. That works well with any policy and extends to other features, like expiration.

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#35

Post by shereadsthenews »

NovaX wrote: post #34
shereadsthenews wrote: post #33

Earlier quoted context omitted.

You can implement ARC that way and there is a Go library on GitHub that does, but that is not going to scale well. Normally you won't need to evict from the frequently-used list, and there is no need to maintain LRU order on that cache during access. One need only atomically update the access time of the entry and defer ordering until such a time as eviction is required. During an access only a read lock on that cach…

That certainly helps, though you assume strict LRU vs approximate ARC. One can of course use similar schemes on LRU (like memcached does) or sampling LRU, making it approximate but reducing the lock contention. The technique that I've used is to buffer and replay events against the policy, so that reads are just a CAS into a ring buffer and replaying is under performed under a non-blocking lock. That works well with…

I think we'd definitely have things to discuss :-) It sounds like we agree there is rarely a good reason to maintain strict LRU property no matter what scheme or structure is being used.

BTW for expiration I have simply invalidated on next access. This seems to have worked well for me with DNS caching, for example, where basically you have three hot records (gmail.com, hotmail.com, yahoo.com) that expire every 5 seconds. In this case of course there is value in proactively refreshing cache entries with some probability proportional to the expiry time so you don't have thundering herds.

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#36

Post by NovaX »

shereadsthenews wrote: post #35
NovaX wrote: post #34

Earlier quoted context omitted.

That certainly helps, though you assume strict LRU vs approximate ARC. One can of course use similar schemes on LRU (like memcached does) or sampling LRU, making it approximate but reducing the lock contention. The technique that I've used is to buffer and replay events against the policy, so that reads are just a CAS into a ring buffer and replaying is under performed under a non-blocking lock. That works well with…

I think we'd definitely have things to discuss :-) It sounds like we agree there is rarely a good reason to maintain strict LRU property no matter what scheme or structure is being used. BTW for expiration I have simply invalidated on next access. This seems to have worked well for me with DNS caching, for example, where basically you have three hot records (gmail.com, hotmail.com, yahoo.com) that expire every 5 seco…

Yes, that would be fun. :)

For fixed expiration (e.g. 5 min TTL), I use time-bounded LRU queues. Then if the head item has not expired, its successors have not either. If it has, it is merely a poll.

For custom expiration (varies per-entry), I use a hierarchical timer wheel. This replaces sorting with hashing, with an amortized O(1) cost.

For refresh, that's when I do it on access since its being used. I keep a refresh timestamp and an expiration timestamp, so that a refresh can occur while the data is valid but aging, but a blocking load is required when its too stale (expired).

You might enjoy this slide deck of the ideas that I use: https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU...

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#37

Post by chacham15 »

kazinator wrote: post #8

> When Are Randomized Algorithms Better Than LRU? When the access pattern is random: recently used items are not more likely to be accessed than other items. Or worse: the access pattern is "anti-recent": items recently accessed are less likely to be accessed again than other items. This is undergraduate stuff I once had to know for exams in machine architectures and operating systems. The choice of LRU replacement i…

This comment is dangerously trivializing the problem. Even in cases where the access pattern is contiguous, not "anti-recent", etc. LRU can still fail to perform. For example, if you simply iterate over a contiguous list of 5 items with a cache size of 4, you will have a 0% hit rate with LRU. With 2 random, it would be > 0% because there is a chance you wouldnt evict the item in exactly the wrong time. The main takeaway from the article is that it is this mismatch between cache sizes which can cause problems and is evident by the data. In L1+L2 caches, LRU outperforms, but in L3 2-random outperforms because at that point, you are more likely to hit this exact case.

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#38

Post by hinkley »

antirez wrote: post #12

Note that LFU does not have the same limits and will adapt to access patterns that are pathological for LRU like circular accesses. LRU is an approximation of LFU based on the idea that last access time is related to the future access frequency of an object. The pathological cases where LRU fails and random eviction is better is related to the fact that such access patterns violate such premise. LFU does not have suc…

I have just started fiddling with treaps recently. Not applicable I suspect for a hardware cache but this thread has morphed a bit into conversations about software caches as well.

A treap is an unbalanced binary tree where the tree depth is proportional to the frequency of use to get fewer indirections per access (assuming an uneven distribution of lookups). Essentially it has a MFU or LFU queue built into it and now I'm curious about how it would behave as a cache data structure.

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#39

Post by stephen422 »

chacham15 wrote: post #37
kazinator wrote: post #8

> When Are Randomized Algorithms Better Than LRU? When the access pattern is random: recently used items are not more likely to be accessed than other items. Or worse: the access pattern is "anti-recent": items recently accessed are less likely to be accessed again than other items. This is undergraduate stuff I once had to know for exams in machine architectures and operating systems. The choice of LRU replacement i…

This comment is dangerously trivializing the problem. Even in cases where the access pattern is contiguous, not "anti-recent", etc. LRU can still fail to perform. For example, if you simply iterate over a contiguous list of 5 items with a cache size of 4, you will have a 0% hit rate with LRU. With 2 random, it would be > 0% because there is a chance you wouldnt evict the item in exactly the wrong time. The main takea…

Your loop example is more akin to the "anti-recent" pattern: the most recently accessed item will not be accessed again sooner than any of the four other items. Contiguous patterns may well be anti-recent, whether an access is "recent" or not should be considered in relation to the size of the cache.

Re: Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)

#40

Post by kazinator »

chacham15 wrote: post #37
kazinator wrote: post #8

> When Are Randomized Algorithms Better Than LRU? When the access pattern is random: recently used items are not more likely to be accessed than other items. Or worse: the access pattern is "anti-recent": items recently accessed are less likely to be accessed again than other items. This is undergraduate stuff I once had to know for exams in machine architectures and operating systems. The choice of LRU replacement i…

This comment is dangerously trivializing the problem. Even in cases where the access pattern is contiguous, not "anti-recent", etc. LRU can still fail to perform. For example, if you simply iterate over a contiguous list of 5 items with a cache size of 4, you will have a 0% hit rate with LRU. With 2 random, it would be > 0% because there is a chance you wouldnt evict the item in exactly the wrong time. The main takea…

Repeatedly iterating over a sequence items is in fact "anti-recent". Round-robin cycling is probably the simplest possible algorithm for accessing a set of items such that, at any time, the item that is accessed next is the one that was least recently visited. Proof: since that item was last visited, every other item in the set was visited.
Post reply on HN