1a1a11a

9 ms·

31.
by 1a1a11a 3y ago
1. I wrote a bit on how to implement lock-free FIFO queues here https://blog.jasony.me/system/cache/2023/12/28/fifo , let me know if any part is not clear or not correct. Moving an object from the sm
32.
by 1a1a11a 3y ago
I like the discussions with you. I have a few comments and questions. 1. why does it require multiple atomic operations at each insert? Our implementation in cachelib only used one CAS operation. I will get back to you with an illustration.
33.
by 1a1a11a 3y ago
Hi Alexey, I was referring to the bug you fixed two weeks ago. This comment was for the weird results that Ben's cited. I apologize here because I did not check the commit carefully, and I thought you had not updated the results (beca
34.
by 1a1a11a 3y ago
There are some difference, the most notable one is that 2Q evicts all objects from the small queue (does not move to the large LRU).
35.
by 1a1a11a 3y ago
Hi falsandru, I do not know where you can the feeling that S3-FIFO is not loop-resistant, can you elaborate more? There is an adversarial pattern where each object is only requested twice, and the second request comes very late (out of the
36.
by 1a1a11a 3y ago
Hi Ben, "I have not seen anything novel in this or their previous works and find their claims to be easily disproven" is a big statement. We evaluated over 6000 workloads from 14 sources (Meta, Twitter, Microsoft, Wikipedia, VMWar
37.
by 1a1a11a 3y ago
Sorry. TTL is not an eviction policy, as the others pointed out, you need an eviction algorithm to decide which objects to keep in the cache when it is full. Your mindset is about a key-value store, not kv cache, which is always full. I ag
38.
by 1a1a11a 3y ago
You evaluated a single trace (from twenty years ago) and claimed that S3-FIFO is worse; why not show more traces? Most of the traces we used are open-source and can be found here. https://github.com/Thesys-lab/sosp23-s3
39.
FIFO queues are all you need for cache eviction(s3fifo.com)
6 points by 1a1a11a 3y ago|0 comments
40.
by 1a1a11a 3y ago
Have you experienced workload changes that caused an algorithm to be less effective? I am happy to learn about it. From my experience and study of traces collected in the past, I haven't seen such cases. Of course, there is diurnal ch
41.
by 1a1a11a 3y ago
Hi Ben, can you provide more details about shifting workload? Every algorithm has weakness, and finding it in the complex algorithms is often harder --- however, this does not mean simple algorithm is bad. I like W-TinyLFU, it has a slightl
42.
by 1a1a11a 3y ago
I agree with you. Any eviction algorithm would have an adversarial workload, so a simpler algorithm is better because you know what the workload was and whether it happens in production; on the other end, the complicated one only makes this
43.
by 1a1a11a 3y ago
This is very helpful (for someone who has never worked on Darwin)! The algorithm uses two FIFO lists with a "visited" bit (lazy promotion), and is a great idea! There are two differences between what is described and our algorit
44.
by 1a1a11a 3y ago
Consider the the request sequence you gave a, a, b, b, c, c, d, d ... and a cache size of 2, when the first c arrives, the cache is in the following state (left is head and right is the tail, inserted at the head): b(1) a(1) and it will t
45.
by 1a1a11a 3y ago
Yes, in the worst case, it would need O(n) to evict, and it can hurt tail latency, but it only happens once in a while in the worst case because each time when an object is checked, the bit is set to 1. I don't understand the O(n*m) a
46.
by 1a1a11a 3y ago
This is common confusion. It is O(n) where n is the number of objects, but LRU is O(m) where m is the number of requests, which is often more than the number of objects :)
47.
by 1a1a11a 3y ago
This is interesting! Do you have a good reference?
48.
by 1a1a11a 3y ago
Implementing 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
49.
by 1a1a11a 3y ago
BTW, the 1% queue in LIRS makes it similar to W-TinyLFU (but less robust than W-TinyLFU)
50.
by 1a1a11a 3y ago
Aha, 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 othe
51.
by 1a1a11a 3y ago
Yes, 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. :
52.
by 1a1a11a 3y ago
Yes! 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 :)
53.
by 1a1a11a 3y ago
The 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 :)
54.
by 1a1a11a 3y ago
Do 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
55.
by 1a1a11a 3y ago
ARC 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
56.
by 1a1a11a 3y ago
Thank 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 smal
57.
by 1a1a11a 3y ago
There are two things. One is reinsertion or lazy promotion as you described, which is used to keep popular objects (reinserted objects have the bit reset to 0, so it won't be infinite loop). And it performs fewer work than LRU because
58.
by 1a1a11a 3y ago
slides here https://jasony.me/slides/hotos23-qdlp.pdf
59.
FIFO can be Better than LRU [pdf](jasony.me)
93 points by 1a1a11a 3y ago|49 comments
60.
by 1a1a11a 3y ago
A 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 ou

More ›