4 ms·

https://news.ycombinator.com/item?id=36434358 https://news.ycombinator.com/item?id=36434358 Note that S3-FIFO has no loop resistance. Nevertheless, the result

https://news.ycombinator.com/item?id=36434358 https://news.ycombinator.com/item?id=36434358 Note that S3-FIFO has no loop resistance. Nevertheless, the result that this library is functioning in a loop indicates that some important changes have been made. Also, the result that Ristretto, which has loop resistance, is not functioning in a loop is clearly an anomaly and likely not being measured correctly. Ristretto's benchmark results on S3, DS1, and OLTP differ markedly from the official ones (https://github.com/dgraph-io/ristretto https://github.com/dgraph-io/ristretto). Otter's benchmark results are quite suspicious.

NovaX 3y ago
I think you may be right. The library author said he made many changes because implementing the eviction policy following the paper's design was pretty awful. > First, I tried to implement cache on hash table and lock free queues, as the authors wrote. I was annoyed, s3-fifo was indeed many times faster than lru cache implemented on hash table with global mutex, but still lost to ristretto and theine, which use bp-wrapper techniques. The profiler also showed that it was the eviction policy that was spending the bulk of the time. And I was only able to beat ristretto and theine after rewriting the implementation using bp-wrapper. > In summary, I completely disagree about the scalability advantage of S3-FIFO over the other policies > Though to be honest, what was causing the hit ratio to go down in DS1 I still don't understand https://github.com/Yiling-J/theine-go/issues/29#issuecomment-1841356725 https://github.com/Yiling-J/theine-go/issues/29#issuecomment...
medler 3y ago
Could you share some pointers where I can read more on “loop resistance?” Does that just refer to whether it does well on a looping access pattern?
- senderista 3y ago
  The usual phrase is "scan resistance", which is especially important for databases. A pure LRU policy does poorly on scans; LFU does better but performs worse than LRU on other workloads. The original ARC paper[0] has a good discussion of the tradeoffs. [0] https://www.usenix.org/legacy/events/fast03/tech/full_papers/megiddo/megiddo.pdf https://www.usenix.org/legacy/events/fast03/tech/full_papers...
  - falsandtru 3y ago
    Scan resistance and loop resistance are completely different. They are also distinguished in the papers. Note that ARC has scan resistance but no loop resistance.
    - medler 3y ago
      None of the papers linked above or linked in the GitHub repo mention “loop resistance.”
    - senderista 3y ago
      Not completely different; they're both sequential access patterns and equivalent whenever the loop size exceeds cache size.
      - falsandtru 3y ago
        Not equivalent completely. Scan is a one-time access, so it never hits in scanning. Loop is multi-time accesses, so it can get many hits in looping if it has loop resistance. No hits on scan resistance in looping. Over.
        falsandtru 3y ago
        I am disgusted by people who are repulsed by even the correction of a complete error. They must have bad grades in college. From now on, we have no choice but to leave it alone even if a false rumor is spread.
- falsandtru 3y ago
  Sometimes referred to as tolerance. There is no established terminology, so the only way to find out is to use scan or loop as keywords.
  - someplaceguy 3y ago
    So why did you say S3-FIFO has no loop resistance (or loop tolerance)?
    - falsandtru 3y ago
      There is an established benchmark for testing loop resistance (GLI, Loop). S3-FIFO has not passed this test. And I have already confirmed that S3-FIFO does not pass the test.
      - someplaceguy 3y ago
        The design of S3-FIFO seems to imply it should handle all loops less than 90% of the cache size pretty well, perhaps even up to 100%. Did you figure out why it did not pass the test? Was there a bug in the implementation, perhaps? Also, where can I find the benchmark you speak of? My web search did not find anything.
        falsandtru 3y ago
        My implementation is reviewed and linked from the official S3-FIFO page. https://s3fifo.com https://s3fifo.com A benchmark is as follows. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency I can't deal with you any longer. Over.
        NovaX 3y ago
        /u/someplaceguy, Those LIRS traces, along with many others, are available at this page [1]. I did a cursory review using their traces with Caffeine's and the author's simulators to avoid bias or a mistaken implementation. In their target workloads Caffeine was on par or better [2]. I have not seen anything novel in this or their previous works and find their claims to be easily disproven, so I have not implement this policy in Caffeine’s simulator yet. [1]: https://github.com/ben-manes/caffeine/wiki/Simulator https://github.com/ben-manes/caffeine/wiki/Simulator [2]: https://github.com/1a1a11a/libCacheSim/discussions/20 https://github.com/1a1a11a/libCacheSim/discussions/20
someplaceguy 3y ago
S3-FIFO has scan resistance. What do you mean by "loop resistance" and why do you say S3-FIFO doesn't have it?
maypok86 3y ago
1. Unfortunately, ristretto has been showing hit ratio around 0 on almost all traces for a very long time now and the authors don't respond to this in any way. Vitess for example has already changed it to another cache. Here are two issues about it: https://github.com/dgraph-io/ristretto/issues/346 https://github.com/dgraph-io/ristretto/issues/346 and https://github.com/dgraph-io/ristretto/issues/336 https://github.com/dgraph-io/ristretto/issues/336. That is, ristretto shows such results even on its own benchmarks. You can see it just by running hit ratio benchmarks on a very simple zipf distribution from the ristretto repository: https://github.com/dgraph-io/ristretto/blob/main/stress_test.go#L53 https://github.com/dgraph-io/ristretto/blob/main/stress_test.... On this test I got the following: stress_test.go:75: actual: 0.07, optimal: 0.68 2. Yes, otter contains a number of changes to the algorithm that in my opinion improve it. For example, S3-FIFO in otter does not have a worst case time complexity equal to O(n), there O(1). 3. But the fact that S3-FIFO performs worse on DS1 than LRU sounds very doubtful. It sounds more like a bug in the implementation, since even on the caffeine simulator S3-FIFO wins. linked.Lru 20.24 % product.Caffeine 45.82 % sampled.sampled.Lru 20.55 % two-queue.Qdlp 30.73 %
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 small queue). But such a pattern is very rare (if it ever exists at all), and other algorithms, such as TinyLFU, also suffer from this access pattern. You claimed that you verified it, but there is no evidence given so far except on the single trace, which S3-FIFO is indeed worse. Frankly speaking, I don't understand why you get irritated by other users in this post.

NovaX 3y ago

I think you may be right. The library author said he made many changes because implementing the eviction policy following the paper's design was pretty awful. > First, I tried to implement cache on hash table and lock free queues, as the authors wrote. I was annoyed, s3-fifo was indeed many times faster than lru cache implemented on hash table with global mutex, but still lost to ristretto and theine, which use bp-wrapper techniques. The profiler also showed that it was the eviction policy that was spending the bulk of the time. And I was only able to beat ristretto and theine after rewriting the implementation using bp-wrapper. > In summary, I completely disagree about the scalability advantage of S3-FIFO over the other policies > Though to be honest, what was causing the hit ratio to go down in DS1 I still don't understand https://github.com/Yiling-J/theine-go/issues/29#issuecomment-1841356725 https://github.com/Yiling-J/theine-go/issues/29#issuecomment...

medler 3y ago

Could you share some pointers where I can read more on “loop resistance?” Does that just refer to whether it does well on a looping access pattern?

senderista 3y ago
The usual phrase is "scan resistance", which is especially important for databases. A pure LRU policy does poorly on scans; LFU does better but performs worse than LRU on other workloads. The original ARC paper[0] has a good discussion of the tradeoffs. [0] https://www.usenix.org/legacy/events/fast03/tech/full_papers/megiddo/megiddo.pdf https://www.usenix.org/legacy/events/fast03/tech/full_papers...
- falsandtru 3y ago
  Scan resistance and loop resistance are completely different. They are also distinguished in the papers. Note that ARC has scan resistance but no loop resistance.
  - medler 3y ago
    None of the papers linked above or linked in the GitHub repo mention “loop resistance.”
  - senderista 3y ago
    Not completely different; they're both sequential access patterns and equivalent whenever the loop size exceeds cache size.
    - falsandtru 3y ago
      Not equivalent completely. Scan is a one-time access, so it never hits in scanning. Loop is multi-time accesses, so it can get many hits in looping if it has loop resistance. No hits on scan resistance in looping. Over.
      - falsandtru 3y ago
        I am disgusted by people who are repulsed by even the correction of a complete error. They must have bad grades in college. From now on, we have no choice but to leave it alone even if a false rumor is spread.
falsandtru 3y ago
Sometimes referred to as tolerance. There is no established terminology, so the only way to find out is to use scan or loop as keywords.
- someplaceguy 3y ago
  So why did you say S3-FIFO has no loop resistance (or loop tolerance)?
  - falsandtru 3y ago
    There is an established benchmark for testing loop resistance (GLI, Loop). S3-FIFO has not passed this test. And I have already confirmed that S3-FIFO does not pass the test.
    - someplaceguy 3y ago
      The design of S3-FIFO seems to imply it should handle all loops less than 90% of the cache size pretty well, perhaps even up to 100%. Did you figure out why it did not pass the test? Was there a bug in the implementation, perhaps? Also, where can I find the benchmark you speak of? My web search did not find anything.
      - falsandtru 3y ago
        My implementation is reviewed and linked from the official S3-FIFO page. https://s3fifo.com https://s3fifo.com A benchmark is as follows. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency I can't deal with you any longer. Over.
        NovaX 3y ago
        /u/someplaceguy, Those LIRS traces, along with many others, are available at this page [1]. I did a cursory review using their traces with Caffeine's and the author's simulators to avoid bias or a mistaken implementation. In their target workloads Caffeine was on par or better [2]. I have not seen anything novel in this or their previous works and find their claims to be easily disproven, so I have not implement this policy in Caffeine’s simulator yet. [1]: https://github.com/ben-manes/caffeine/wiki/Simulator https://github.com/ben-manes/caffeine/wiki/Simulator [2]: https://github.com/1a1a11a/libCacheSim/discussions/20 https://github.com/1a1a11a/libCacheSim/discussions/20

someplaceguy 3y ago

S3-FIFO has scan resistance. What do you mean by "loop resistance" and why do you say S3-FIFO doesn't have it?

maypok86 3y ago

1. Unfortunately, ristretto has been showing hit ratio around 0 on almost all traces for a very long time now and the authors don't respond to this in any way. Vitess for example has already changed it to another cache. Here are two issues about it: https://github.com/dgraph-io/ristretto/issues/346 https://github.com/dgraph-io/ristretto/issues/346 and https://github.com/dgraph-io/ristretto/issues/336 https://github.com/dgraph-io/ristretto/issues/336. That is, ristretto shows such results even on its own benchmarks. You can see it just by running hit ratio benchmarks on a very simple zipf distribution from the ristretto repository: https://github.com/dgraph-io/ristretto/blob/main/stress_test.go#L53 https://github.com/dgraph-io/ristretto/blob/main/stress_test.... On this test I got the following: stress_test.go:75: actual: 0.07, optimal: 0.68 2. Yes, otter contains a number of changes to the algorithm that in my opinion improve it. For example, S3-FIFO in otter does not have a worst case time complexity equal to O(n), there O(1). 3. But the fact that S3-FIFO performs worse on DS1 than LRU sounds very doubtful. It sounds more like a bug in the implementation, since even on the caffeine simulator S3-FIFO wins. linked.Lru 20.24 % product.Caffeine 45.82 % sampled.sampled.Lru 20.55 % two-queue.Qdlp 30.73 %

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 small queue). But such a pattern is very rare (if it ever exists at all), and other algorithms, such as TinyLFU, also suffer from this access pattern. You claimed that you verified it, but there is no evidence given so far except on the single trace, which S3-FIFO is indeed worse. Frankly speaking, I don't understand why you get irritated by other users in this post.