6 ms·
FIFO can be Better than LRU [pdf]
- singron 3y agoBeating plain LRU isn't very interesting, but they also evaluated a bunch of other algorithms (e.g. ARC) and concluded that it performed better than those as well. I know the ARC paper discusses that other algorithms are often better if properly tuned, although ARC is usually consistently decent in a variety of situations without tuning. It would be awesome to have a new algorithm in that space.
- 1a1a11a 3y agoARC is good overall, but we find that when evaluating on such a large dataset (over 5000 traces), the adaptive algorithm in ARC is not robust, sometimes the recency queue is small, while sometimes it is too large. If we think closely, why does "moving one space from recency queue to frequency queue upon a hit on the frequency ghost" make sense? Should we distinguish the hit on the beginning of ghost LRU and the tail of LRU? The implicit parameters may not be reasonable in some cases. But overall, ARC is a good algorithm, just not perfect yet. :)
- tedunangst 3y agoLazy promotion and quick demotion sound similar to what's done in 2Q. https://www.vldb.org/conf/1994/P439.PDF https://www.vldb.org/conf/1994/P439.PDF
- 1a1a11a 3y agoYes! TwoQ is very similar to the FIFO-LP-QD, but we show that we need a smaller queue. This paper is to inspire people to investigate other lazy promotion and quick demotion technique :)
- anotherhue 3y agoMight I also recommend: Bryan Cantrill on ARC: A Self-Tuning, Low Overhead Replacement Cache [PWL SF] 10/2017 https://www.youtube.com/watch?v=F8sZRBdmqc0 https://www.youtube.com/watch?v=F8sZRBdmqc0
- NovaX 3y agoThe LIRS papers do a good job of taking different workload patterns, such as loop and zig-zag and mixing multiple patterns together, to validate that their algorithm is robustly good as a general purpose cache. This seems to take traces with similar workload patterns that are distinguished by their excessive size to assert the algorithm's quality. When papers do this it looks good from an academic sense, but it is frustrating from an industry perspective because the workload may not be known upfront or the one must cherry-pick an algorithm for a bespone, consistent pattern. I find it more interesting when algorithm designers try to stress their work and discuss how/why it fails or succeeds. That gives more confidence to those of us who want to implement and use the work in a practical setting.
- 1a1a11a 3y agoThe large datasets from 2007 to 2020 cover a variety of workload patterns. If you have a workload that you would like to try out, our code and data are all open-sourced. Also feel free to drop us an email :)
- 1a1a11a 3y agoBTW, the 1% queue in LIRS makes it similar to W-TinyLFU (but less robust than W-TinyLFU)
- NovaX 3y agoYou have a large corpus of similar workload patterns. Simply using a 750GB trace or many samples from a cluster of machines doing the same work does not make it a meaningful variety. It would be reasonable to have also tested with the traces that your comparison algorithms used, which shows your implementations are valid and how they differ on those authors terms. Skipping that may come across as cherry-picking because I find that QDLP under performs by -20% in zigzag, -15% in DS1, -33% in blockchain mining. Your algorithm is good in specific cases, like many others are, but there are many real workloads where it is not usable.
- vlasky 3y agoI wonder how difficult it would be to enhance Redis to support FIFO with Lazy Promotion and Quick Demotion.
- 1a1a11a 3y agoImplementing FIFO-Reinsertion should be easy, adding quick demotion would take some efforts. FIFO-Reinsertion also allows Redis to avoid random sampling and better handle TTLs
- vlovich123 3y agoI wonder why all these papers ignore comparison against W-TinyLFU. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency Shows that it really outperforms ARC as well and they also have an optimal oracle version that they evaluate against to show how much room there is left (admittedly the oracle version itself implies you’re picking some global criterion to optimize but that’s trickier when in reality there are multiple axes along which to optimize and you can’t simultaneously do well across all of them). Also the lack of evaluation of the cache strategy against shifting workloads is also problematic.
- gridspy 3y agoIt's mentioned in the paper, since W-TinyLFU is a means of qualifying things prior to going in the cache. That process is called QD in TFA. They refer to the W-TinyLFU paper as reference 34. > Moreover, admission algorithms, e.g., TinyLFU [ 33, 34], Bloom Filter [18, 54 ], probabilistic [ 15] and ML-based [ 35] admission algorithms, can be viewed as a form of QD — albeit some of them are too aggressive at demotion (rejecting objects from entering the cache).
- 1a1a11a 3y agoThank you! Yes, W-TinyLFU is very good, we have a follow up on this. But we find that the adaptive frequency in W-TinyLFU is less robust than using a static FIFO (yeah, I know this is surprising). And also the 1% LRU is sometimes too small. But I admit that W-TinyLRU is very good among all state-of-the-arts (but not as good as the FIFO+LP+QD), especially when you consider the scalability issue.
- vlovich123 3y agoYeah, I’d love to see a comparison against W-TinyLRU, particularly across many more evaluation axes eg what happens when traffic patterns shift, what if you want to better balance QoS between customers, etc etc etc.
- 3y ago
- almost_usual 3y agoThis just sounds like a variation of 2Q?
- 1a1a11a 3y agoYes, FIFO-LP-QD is similar with a smaller queue and uses FIFO only. But goal is to 1 inspire other lazy promotion and quick demotion technique, and 2 show that FIFO-Reinsrtion is better than LRU and there is no reason to use LRU any more. :)
- flopriore 3y agoWhat about Belady's anomaly?
- 1a1a11a 3y agoAha, there is someone care about this! We dis study this, we found that on the over 5000 traces, belady's anomaly is very common! Our new algorithm does not have the least anomalies, CLOCK and LIRS have the least, but compared to other algorithms, it has smaller number of anomalies.
- ojosilva 3y agoI've spent the last month or so working on a write-behind cache in both Rust and Zig, with a RAM + Disk component, similar to what a OS kernel memory page swap does, but at the app level and key-value-oriented. My experience trying out cache algorithms is that they are all very generic, cache benchmarks are typically based on random distributions or on web-request datasets (twitter, CDNs, ...) that may not match your use case. Mine is about caching data stream transformations with specific ORDER BYs. Hits may come at a very wide point in time and LFU ended-up working better for me. Also your eviction policy choice is very important like number of items or RAM use (my case). So don't go running to the latest "benchmark proven" cache algorithm paper without weighting in your specific needs.
- 1a1a11a 3y agoDo you mind sharing more details on the time length of workloads in your benchmark? Are you using LRU with no aging? Drop me an email if you would like to chat more juncheny@cs.cmu.edu
- 1a1a11a 3y agoA recent study on over 5000 (key-value, block, object) cache traces from 2007 to 2020 shows that FIFO-Reinsertion is not only faster and more scalable, it is also more efficient (has a lower miss ratio). Maybe it is time to drop LRU from our classroom?
- 1a1a11a 3y agoslides here https://jasony.me/slides/hotos23-qdlp.pdf https://jasony.me/slides/hotos23-qdlp.pdf
- ramses0 3y agoRough Summary: Start with a dumb-cache using "FIFO" (first in/first out) Keep track of anything with "hits" while in the cache (simple boolean/bitmap instead of complicated locks/data structures) Re-insert "hit" items when they would normally be evicted/age out (Lazy Promotion). BTW, also have a mini-cache in front of the main cache (10% of cache size) which tries to "drop off quickly" (effectively: must have a "hit" within first 10% of being cached). BTW, also keep track of a "ghost cache" ("hits only", not contents??) for the duration of the overall FIFO-cache, and use that to guide eviction/re-insertion. I'm a little bit unclear on this aspect, but it seems like an "obvious in retrospect" set of guidance.
- gridspy 3y agoUseful summary. Made me want to read about the ghost cache. The cache layout is: Probationary 10% + Traditional 90% (of memory). The idea is that most items are not requested again prior to dropping out of probationary and so don't take up space and process in the Traditional Cache. Some infrequently used items however would remain inside the Traditional cache but never make it through the probationary cache. So a small "ghost" cache is used to specifically detect these items rejected from the Probationary cache. Next time we go to fetch a ghost item they go directly into the Traditional cache. The ghost cache is just storing metadata (pointers essentially).
- firstlink 3y agoWhat's the eviction rule from the ghost cache, though? Does it share an eviction queue with the Traditional cache?
- gridspy 3y agoIt is the same size as the traditional cache, but it is also a FIFO. Naturally it doesn't need to worry about tracking access, since the moment the ghost cache is "hit" the relevant memory location is loaded into the traditional cache and the ghost cache entry becomes irrelevant. So I guess that means the ghost cache could just be a queue.
- 3y ago