6 ms·
Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
- boyter 8y agoLove reading this. It has always been one of those interesting things I kept in the back of my mind in my day to day. I was very excited when I actually got to implement it on a real world project. I was writing a scale out job which used ffmpeg to make clips of video files. To speed it up I kept the downloaded files (which could be 150 GB in size) as a local cache. Quite often a clip is made of the same file. When the disk was full (there was a separate disk for download and clip output) selected two of the downloaded files randomly and deleted the older one. Loop till there was enough disk space, or no files. It's something I thought I would never actually get to implement in the real word, and thus far is working very well, the caching speeds things up and the eviction seems to avoid too many cache misses.
- zodvik 8y ago2-random was also used in this HDFS change - https://issues.apache.org/jira/browse/HDFS-8131 https://issues.apache.org/jira/browse/HDFS-8131. Default block placement policy chose datanodes randomly for new blocks. This change selects 2 datanodes randomly and picks the one with lower used disk space.
- p1necone 8y agoThe article never explains what the difference between 2-random and pseudo 2-random is, does anyone know?
- j16sdiz 8y agoPseudo 2-Random use Pseudo LRU. Check the Wikipedia for Pseudo LRU. It is a tree algorithm for tracking the approximate last use time.
- vesinisa 8y agoInteresting read, but I wish he'd explain how 2-random and LRU differ better. In a nutshell, LRU tracks the time when a cache item was last accessed and always discards the oldest item. 2-random also tracks the age of all cache items, but when discarding picks two random items and discards the oldest of those two.
- wizeman 8y agoIt doesn't discard the oldest item, it discards the item that was least recently used/accessed (LRU, like the name says). To see the difference more clearly, note that the oldest item can in fact be the most recently used one.
- iampims 8y agoIt’s also working very well for load-balancing. https://brooker.co.za/blog/2012/01/17/two-random.html https://brooker.co.za/blog/2012/01/17/two-random.html
- kazinator 8y ago> 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 is favorable when there exists "locality of reference"; that's what it's predicated upon. All of the replacement policy choices are only substitutes for a "magic oracle": a replacement strategy which can peer into the future and know which items will be accessed soonest. With a magic oracle, we can not only retain those items in the cache in preference to other items, to great advantage, but we can automatically prefetch the correct items that are not yet in the cache but are about to be accessed. In general, randomized algorithms provide a defense against situations in which things don't work out according to the best case assumptions. For instance, they help defend against tickling worst cases in algorithms (e.g. sorting) that have good average-case behavior.
- carlmr 8y ago>>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. Wouldn't they perform equally well in this case? There's no advantage in LRU, but also no disadvantage if they're really unpredictably random.
- adrianN 8y agoA random strategy has less overhead than LRU because there is no bookkeeping.
- dan-robertson 8y agoThis argument does not apply to the OP as it does not account for any bookkeeping. I think an actual answer is more complicated and will entirely depend on the definition of “random access pattern.”
- kccqzy 8y agoRandomization can really do wonders at times. There are some algorithms for which the most efficient algorithm is essentially using randomness in a clever way. The Miller–Rabin primality test comes to mind. Or the randomized minimum cut problem. And even when deterministic algorithms have the same big-O asymptotic complexity as randomized algorithms, the randomized ones often perform better due to simpler code. Treap vs red-black tree is a classic example.
- npstr 8y agoAn algorithm that's more optimal than LRU on most workloads is Window TinyLFU. Some nice simulations and graphs can be found here: https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency
- Scaevolus 8y agoLHD 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.nsdi.lhd.pdf https://www.cs.cmu.edu/~beckmann/publications/papers/2018.ns...
- 6keZbCECT2uB 8y agoI 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 preferable which uses an array to approximate node based structures. ARC and LIRS have CAR and CLOCK-Pro respectively to simulate them. CAR is vulnerable to re-use distances near the boundary of the cache size. [1] CLOCK-Pro is widely used, notably in Linux VM. [1] https://www.slideshare.net/huliang64/clockpro https://www.slideshare.net/huliang64/clockpro
- NovaX 8y agoNaming aside, the structure is <LRU | LFU filter | LRU>. 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-2979e380-3141-11e9-91b3-00002a3cc80b.png https://user-images.githubusercontent.com/378614/52891655-29...
- 8y ago
- Labo333 8y agoThe experiments are interesting but they never explained what the strategies are. It's OK for LRU and FIFO but certainly not for 2-random!
- antirez 8y agoNote 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 such limits because it attempts to measure the actual access frequency (smoothed by time) of an object, and uses that as prediction of the future frequency.
- hinkley 8y agoI 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.
- pvorb 8y agoCaffeine, a caching library for Java, has a nice write-up on more advanced cache eviction strategies. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency
- harryf 8y agoWorth reading http://open-zfs.org/wiki/Performance_tuning http://open-zfs.org/wiki/Performance_tuning about the Adaptive Replacement Cache algorithm ( https://en.m.wikipedia.org/wiki/Adaptive_replacement_cache https://en.m.wikipedia.org/wiki/Adaptive_replacement_cache ) which is less vulnerable to cache flushes than LRU
- shereadsthenews 8y agoThe 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.
- NovaX 8y agoCan 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.
- shereadsthenews 8y agoYou 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.
- NovaX 8y agoThat 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.
- okl 8y ago> If you have a tight loop, LRU is going to be perfect as long as the loop fits in cache, but it's going to cause a miss every time if the loop doesn't fit. A random eviction policy degrades gracefully as the loop gets too big. That's the key take-away from my experience with optimizing control loops for microcontrollers with small caches. As soon as your loop is too bit, your code suddenly runs at a hundredth of the speed.
- eternalban 8y agoI am not sure I understand what you mean by the size of the "loop". Conventional LRU uses linked-lists and when the LL no longer fits in the L1/L2 caches, you will see the performance hit you mention (given that accessing the associated LL node and reordering the list will most likely result in two cache misses). Try libclc [1] for a compact segmented cache of n 64B containers that exactly fit a cache line, with each container having its own eviction policy. The overhead of LRU per container (of 7 data lines) is 9.14 bits/entry and the same cache line access will give you both the data lines and the LRU order. [1]: https://github.com/alphazero/libclc https://github.com/alphazero/libclc
- blattimwind 8y ago> Conventional LRU uses linked-lists and when the LL no longer fits in the L1/L2 caches He refers to the LRU-like policy of the I/D cache itself.
- eternalban 8y agoGot it. Thanks for the clarification.
- porpoisely 8y agoIt goes beyond microcontrollers to every step up the chain. You want to optimize you system to hit the cache at every level as much as possible. The processor and its cache. The database and its cache. Web servers and their cache. Because going outside of the cache at any level usually incurs a performance hit orders of magnitude worse.
- drallison 8y agoIt would be interesting to compare the behavior of real workloads with different cache protocols. In a "real workload" the sequence of reads and writes to memory (and the cache) come from a multiplicity of independent processes functioning co-sequentially with some distribution of lifetimes of cache ownership. In many cases, the caches will be in a non-equilibrium state and behaving badly.
- phyzome 8y agoNote that Redis's LRU algorithm is randomized: https://redis.io/topics/lru-cache https://redis.io/topics/lru-cache > The reason why Redis does not use a true LRU implementation is because it costs more memory. ...but it sounds like it wouldn't necessarily be totally desirable to use true LRU anyhow. :-)
- known 8y agoRandom boosting could have saved Mars pathfinder https://en.wikipedia.org/wiki/Priority_inversion https://en.wikipedia.org/wiki/Priority_inversion