It is such as shame: we tell you that we are writing a paper on this exact topic and you created a GitHub and advertises everywhere
81 karma · joined March 10, 2016
I would expect at least 10s if not 100s TB/s from a cluster of 7500 servers with SSDs, what is the bottleneck?
Implementation can be found https://github.com/1a1a11a/libCacheSim/blob/develop/libCache...
> a lot of these practical details have never been written down a far as I can tell, it is passed along as lore and beer convos
I wish the valuable knowledge could be written down and shared.
Yup, I am on the same page as you, after seeing the many state-of-the-art having similar miss ratios, I am inclined to think we are close to the maximum possible hit ratio bounded by the limited information from the request history (information theory).
Yes, SIEVE does not adapt to miss ratio, but it adapts to the inherent popularity in the workloads. You can see the evidence in the results.
The first point is probably true for most research in computer systems. Different systems have different constraints that make a simple design very complex or not possible.
Can you elaborate on the second point more? It feels to me that S3-FIFO is optimized for latency, throughput, and scalability than existing algorithms (e.g., with multiple LRU queues).
At first, I thought FIFO-Merge keeping objects in the insertion order (FIFO) helps the eviction because I mostly worked with Twitter data in which popularity decay is common.
But later when I evaluated more traces (including block I/O workloads), it turned out that quickly evicting new objects (quick demotion) is the source of a low miss ratio. That's why we wrote these papers.
Interested readers are welcome to read more of related work 1. FIFO can be better than LRU, the power of lazy promotion and quick demotion https://dl.acm.org/doi/pdf/10.1145/3593856.3595887
2. FIFO queues are all you need for cache eviction https://dl.acm.org/doi/10.1145/3600006.3613147
This would help with the implementation with a circular buffer. But for now, let's decouple the algorithm from the implementation.
> we can make Insert and Hand be the same slot
This is just CLOCK algorithm. It is easy to implement with a circular buffer. But the change we made deliberately improves the miss ratio significantly.
Sorry for the hyped language. If my guess is correct, the blog was "polished" by ChatGPT, and the intention was to "polish" the English. The paper has more content and should be read more seriously.
We will fix the animation error and update the writing shortly. Thank you for the feedback!
Regarding some of the complaints on SIEVE performance. Here are some more results that I ran for other purposes. https://observablehq.com/@1a1a11a/sieve-miss-ratio-plots
I haven't had time to add other algorithms to the plot, but they are often similar to or worse than TinyLFU (I did not pick TinyLFU to compare deliberately; I happen to have the figures on hand). While the results do not include byte miss ratio, which is important in some use cases, they are better than the results already shown.
We acknowledge that
* SIEVE may not work well on some block I/O workloads (this has been the statement in our writing from the beginning). However, SIEVE works well on large multi-tenanted block I/O workloads (see the Tencent and Alibaba figure in the link). For web workloads, SIEVE shows consistently good results.
* As the author, when I look at this algorithm. My own feeling is that SIEVE may not be robust because it keeps evicting new objects when the hand moves to the head, effectively behaving as MRU. However, our large evaluations showed that modern workloads have certain properties that enable SIEVE to achieve a low miss ratio. We are still investigating this property and how to model it. If someone is interested, feel free to shoot me an email.
* implementing SIEVE with a log-structured design or circular buffer is not trivial, but we had a design called Segcache (https://segcache.com), which runs a constrained version of SIEVE. In simple libraries, linked list implementation should be easy, and one can check the examples on the website.
2. I am not criticizing the design decision in Caffeine. It is good because most people just don't need crazy scalability (>16 threads) or do not run it at such high throughput. I understand that critical operations are not lost. But the promotions are lost under contention, which makes comparison unfair. S3-FIFO is still the same algorithm under contention, but The W-TinyLFU in Caffeine becomes FIFO under high contention. I do not think that it can claim a low miss ratio and good scalability at the same time. The relationship is rather a low miss ratio OR good scalability. But as I mentioned, it does not matter for most use cases, and the design is elegant.
3. skipped
4. It is true that if one wants to port a lock-based new algorithm, it would require extra effort. But I guess this is a decision you have to make: only support lock-free eviction algorithms (FIFO-based) or support more algorithms with locks. But I do want to mention that S3-FIFO is not the only lock-free algorithm and there are and will be more.
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. Maybe you can show me something I missed.
2. I like the bp-wrapper idea. It is intuitive and can be used with most/all algorithms. Batching does reduce/amortize the overhead of locking for LRU-based algorithms. But IIRC, all the promotions are still serialized. Because the promotions are still protected by the lock, and only one core can promote objects at the same time. Caffeine achieves amazing scalability because it drops all the elements that need to be updated/promoted under high contention, which means it effectively becomes a FIFO. I don't think this is the correct way to claim good scalability.
3. "reading with frequency update on hot entries can have a bad effect on performance" I don't understand this. The frequency of hot entries should quickly reach 1 (if using a one-bit counter) or 3 (if using a two-bit counter) and will not be updated anymore. Why would read and update conflict?
4. Yes, implementing get and set with locking is trivial; adding support for delete requires a bit of work (10s lines) but should be manageable. But why would lock-free queues make other features hard to implement? Can you give an example?
Can you clarify what you disagree about on lock-free queues? Do you mean that S3-FIFO cannot be implemented without locks?