Proposal to Integrate SIEVE Eviction Algorithm

[yazhuo]

Hi there,

Our team (@1a1a11a) has developed a new cache eviction algorithm, called SIEVE. It’s simple, efficient, and scalable.

Why SIEVE could be a great addition:

• Simplicity: Integrating SIEVE is straightforward, usually needing to change less than 20 lines of code on average.
• Efficiency: On skewed workloads, which are typical in web caching scenarios, SIEVE is top-notch.
• Cache Primitive: SIEVE is not just another algorithm; it's a primitive that could enhance or replace LRU/FIFO queues in advanced systems like LeCaR, TwoQ, ARC, and S3-FIFO.

Welcome to dive into the details on our website sievecache.com and on our SIEVE blog.

We would love to explore the possibility of integrating SIEVE into theine. We believe it could be a beneficial addition to the library and the community.

Looking forward to your feedback!

[Yiling-J]

@yazhuo I like SIEVE's simplicity as a replacement of LRU. As you may know, W-TinyLFU has a window LRU and a main SLRU, have you tried to replace any of them with SIEVE and test throughput and hit ratio?

[yazhuo]

@Yiling-J Thanks for quick response. We have considered the case of raplacing any of the LRU in W-TinyLFU with SIEVE, but we think this will not yield optimal results.

Both W-TinyLFU and SIEVE achieve quick demotion, as discussed in our HotOS paper. TinyLFU uses a 1% window LRU for quick demotion of unpopular items, while SIEVE uses a moving hand to quickly demote unpopular objects at the head of the queue. Replacing LRU in TinyLFU with SIEVE would result in too aggressive demotion.

SIEVE's mechanism for quick demotion is remarkably simple, yet effective. While SIEVE stands out for its simplicity and state-of-the-art efficiency, this simplicity comes with certain trade-offs, such as a lack of scan resistance.

[Yiling-J]

@yazhuo from blog post, "However, we find that SIEVE sometimes shows a miss ratio higher than LRU. The primary reason for this discrepancy is that SIEVE is not scan-resistant.", I think LRU is not scan-resistant? I'm interested in the performance of SIEVE for LRU friendly workloads. W-TinyLFU is more a framework not an implementation. You have a window cache, a main cache and a compare function, when cache is full, you compare two entries from main and window using that function. If SIEVE always outperform LRU/SLRU, I thinks it still worth a a try to use SIEVE as window/main cache in W-TinyLFU

[1a1a11a]

Hi @Yiling-J, sorry for the confusion. Here the "scan-resistant" refers to not being able to cache potential popular objects mixed in the scan. This happens when the hand moves to the head of the queue, new objects are immediately evicted if not re-accessed. There are ways to mitigate this, but it will introduce parameters and make it more complex. This version of SIEVE is simple, but not robust towards the wide range of possible workloads. As a result, whether SIEVE outperforms LRU depends on workloads. In our experience, SIEVE significantly outperforms LRU on web workloads, but on block IO workloads, SIEVE can be much worse than LRU algorithm.

I am not aware of strict definition of LRU-friendly workloads, do you have a reference or workload that you would like us to test on?

It is hard to guess the performance of TinyLFU with SIEVE, I will come back with some results in a few days.

But my conjecture is the improvement will be small. The key secret behind S3-FIFO, SIEVE, TinyLFU, LIRS, ARC and many others is the ability to quickly remove new and unpopular objects. Since the window in W-TinyLFU already performs this quick demotion, I would not expect significant further gains.

[Yiling-J]

@1a1a11a Thanks for the explanation, I mean LRU is not "scan-resistant" either. If none of them is "scan-resistant", i'm wondering why SIEVE sometimes shows a miss ratio higher than LRU on some block cache workloads.

My thought when I saw this issue is if I can replace SLRU in W-TinyLFU with SIEVE, but as you said "SIEVE can be much worse than LRU algorithm", that might not be a good choice.

[1a1a11a]

Sorry for the confusion. We used "scan-resistant" to mean other things --- considering a sequence of requests with no future requests (or future requests are very far in the future), we call these "scan requests". However, the number of objects accessed in the scan may not be larger than the cache size. If there are popular objects mixed in the "scan requests", then LRU can keep them in the cache, but SIEVE cannot. That's why SIEVE can be worse than LRU. Let me know if this part is still not clear. I can create an example.

The problem why SIEVE is that when the hand moves to the head (see the figure on https://sievecache.com), all new objects are immediately evicted (effectively MRU) until a new object that are accessed twice with no new object in between. However, we find that in web workloads, if a newly inserted object is hot, it is common to two requests for the object. That's why SIEVE is good.

For block workloads, this pattern is less common and SIEVE can be worse than LRU. However, when coupled with W-TinyLFU, the bad part may change because all new objects are kept in the window for at least some time, and SIEVE may be a suitable algorithm for the main cache.

I am running a few large simulations, I will add results when the experiment finishes.

[1a1a11a]

Hi @Yiling-J, I have all the results here, it includes modern traces from the past few years, and the old (>20 years old) ARC traces as a reference.

We usually evaluate a large range (from 0.01% to 80% of the number of objects in the trace) of cache sizes, so we observe that many algorithms can be worse than LRU, so worse than LRU is not limited to SIEVE, but also TinyLFU.

To clarify my statement, our version of TinyLFU does not include the adaptive window with hill climbing.

Here is a short summary of our observation (see the figures here)

1. TinyLFU-SIEVE is better than TinyLFU-LRU most of the time, but both can be much worse than TinyLFU-SLRU (e.g., tencentPhoto). Sometimes TinyLFU-SIEVE is better than TinyLFU-SLRU (e.g., wikiUpload). In summary, the only reason one may want to replace the SLRU in TinyLFU with SIEVE is when one needs lock-free reads.
2. TinyLFU-SLRU can be slightly worse than LRU (e.g., tencentPhoto), and TinyLFU-LRU can be much worse than LRU (e.g., metaKV, alibabaBlock). Note that, we used a large range of cache sizes, so it is not rare to see TinyLFU-SLRU worse than LRU. For example, on the old ARC traces (OLTP), when the cache size is large, TinyLFU-SLRU is worse. This can also be seen in the figure on the otter's homepage, however, this figure cuts off the cache size at 2000.
3. S3-FIFO and SIEVE sometimes can be worse than TinyLFUs on the old ARC traces (e.g., DS1 and S3), but not always worse (e.g., P3 and OLTP). They are also good on modern tencentBlock and alibabaBlock traces. This is partially because the old traces are shor, and the lack of adaptivity making them worse.
4. SIEVE itself on web workloads and multi-tenanted block workloads are good, but on small and old block traces, it can be worse than LRU in a some cases.

[1a1a11a]

Oh, I forgot to mention I treated all objects to have unit size, if we use variable sizes, then a size-aware algorithms often achieve significantly lower request miss ratio. But SIEVE often achieve the lowest byte miss ratio.

And if one looks for a trace where TinyLFU is worse than LRU and S3-FIFO, the metaCDN trace is a good one.

[Yiling-J]

@1a1a11a thanks for the detailed results, it's a bit mystery why TinyLFU LRU/SIEVE's miss ratio is so high on TencentPhoto trace, but TinyLFU SLRU version is not that bad.

Are your team working on adding adaptive W-TinyLFU to benchmarks? caffeine's adaptive approach is changing window size. because window is LRU, I'm also interested what will happen if replace that with SIEVE. (An alternative approach is changing the compare function from compare(freq(keyA), freq(keyB)) to compare(freq(keyA)+adaptive_coefficient, freq(keyB)) and hill climbing that coefficient, in this way you don't need a window to make TinyLFU adaptive)

[1a1a11a]

We may add the adaptive version at some point, but may require a while. At this time, I am just using the version from Caffeine and I get similar results on these workloads. Results attached.

## MetaCDN 
╔════════════════════════════════════════════════╤══════════╤═══════════╤════════════╤════════════╤════════════╤════════════╤════════════╤══════════╤═════════════╤═══════════╗
║ Policy                                         │ Hit Rate │ Miss Rate │ Hits       │ Misses     │ Requests   │ Evictions  │ Admit rate │ Adaption │ Steps       │ Time      ║
╠════════════════════════════════════════════════╪══════════╪═══════════╪════════════╪════════════╪════════════╪════════════╪════════════╪══════════╪═════════════╪═══════════╣
║ adaptive.Arc                                   │ 64.69 %  │ 35.31 %   │ 29,513,611 │ 16,109,695 │ 45,623,306 │ 15,749,695 │            │ -19.00 % │ 45,623,306  │ 32.20 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ irr.Lirs                                       │ 63.65 %  │ 36.35 %   │ 29,039,410 │ 16,583,896 │ 45,623,306 │ 16,223,896 │            │          │ 55,682,848  │ 30.84 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Fifo                                    │ 63.54 %  │ 36.46 %   │ 28,988,988 │ 16,634,318 │ 45,623,306 │ 16,274,318 │            │          │ 74,612,294  │ 23.38 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Fifo_TinyLfu                            │ 33.84 %  │ 66.16 %   │ 15,436,660 │ 30,186,646 │ 45,623,306 │ 29,826,646 │ 0.01 %     │          │ 61,059,966  │ 24.08 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Lru                                     │ 64.24 %  │ 35.76 %   │ 29,310,680 │ 16,312,626 │ 45,623,306 │ 15,952,626 │            │          │ 74,933,986  │ 27.64 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Lru_TinyLfu                             │ 51.01 %  │ 48.99 %   │ 23,271,539 │ 22,351,767 │ 45,623,306 │ 21,991,767 │ 6.46 %     │          │ 68,894,845  │ 26.27 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Sieve                                   │ 64.62 %  │ 35.38 %   │ 29,483,823 │ 16,139,483 │ 45,623,306 │ 15,779,484 │            │          │ 49,847,299  │ 23.16 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sampled.sampled.Hyperbolic_TinyLfu             │ 56.24 %  │ 43.76 %   │ 25,657,157 │ 19,966,149 │ 45,623,306 │ 19,606,149 │ 9.62 %     │          │ 202,472,498 │ 53.87 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.FullySegmentedWindowTinyLfu (1%)        │ 61.62 %  │ 38.38 %   │ 28,112,852 │ 17,510,454 │ 45,623,306 │ 17,150,454 │ 5.27 %     │          │ 45,623,306  │ 38.84 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.HillClimberWindowTinyLfu (indicator 1%) │ 62.02 %  │ 37.98 %   │ 28,295,625 │ 17,327,681 │ 45,623,306 │ 16,967,681 │ 3.00 %     │ -1.00 %  │ 45,623,306  │ 53.38 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.HillClimberWindowTinyLfu (simple 1%)    │ 61.64 %  │ 38.36 %   │ 28,121,008 │ 17,502,298 │ 45,623,306 │ 17,142,298 │ 4.34 %     │ 40.00 %  │ 45,623,306  │ 35.35 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.S4WindowTinyLfu (1%)                    │ 61.88 %  │ 38.12 %   │ 28,231,910 │ 17,391,396 │ 45,623,306 │ 17,031,396 │ 5.54 %     │          │ 45,623,306  │ 36.48 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.WindowTinyLfu (1%)                      │ 61.83 %  │ 38.17 %   │ 28,207,857 │ 17,415,449 │ 45,623,306 │ 17,055,449 │ 5.23 %     │          │ 45,623,306  │ 38.76 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ two-queue.S3Fifo                               │ 65.15 %  │ 34.85 %   │ 29,721,976 │ 15,901,330 │ 45,623,306 │ 16,408,414 │            │          │ 63,448,906  │ 39.98 s   ║
╚════════════════════════════════════════════════╧══════════╧═══════════╧════════════╧════════════╧════════════╧════════════╧════════════╧══════════╧═════════════╧═══════════╝

## TencentPhoto size 1m

╔════════════════════════════════════════════════╤══════════╤═══════════╤═════════════╤═════════════╤═════════════╤═════════════╤════════════╤══════════╤═════════════╤═══════════╗
║ Policy                                         │ Hit Rate │ Miss Rate │ Hits        │ Misses      │ Requests    │ Evictions   │ Admit rate │ Adaption │ Steps       │ Time      ║
╠════════════════════════════════════════════════╪══════════╪═══════════╪═════════════╪═════════════╪═════════════╪═════════════╪════════════╪══════════╪═════════════╪═══════════╣
║ adaptive.Arc                                   │ 63.40 %  │ 36.60 %   │ 184,912,313 │ 106,752,644 │ 291,664,957 │ 105,752,644 │            │ -50.00 % │ 291,664,957 │ 4.173 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Fifo                                    │ 58.25 %  │ 41.75 %   │ 169,901,830 │ 121,763,127 │ 291,664,957 │ 120,763,127 │            │          │ 461,566,787 │ 2.751 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Fifo_TinyLfu                            │ 18.87 %  │ 81.13 %   │ 55,045,745  │ 236,619,212 │ 291,664,957 │ 235,619,212 │ 0.82 %     │          │ 346,710,702 │ 3.035 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Lru                                     │ 62.13 %  │ 37.87 %   │ 181,224,461 │ 110,440,496 │ 291,664,957 │ 109,440,496 │            │          │ 472,889,418 │ 3.861 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Lru_TinyLfu                             │ 55.48 %  │ 44.52 %   │ 161,826,012 │ 129,838,945 │ 291,664,957 │ 128,838,945 │ 10.20 %    │          │ 453,490,969 │ 3.944 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Sieve                                   │ 65.10 %  │ 34.90 %   │ 189,865,953 │ 101,799,004 │ 291,664,957 │ 100,799,005 │            │          │ 332,560,280 │ 2.806 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.HillClimberWindowTinyLfu (indicator 1%) │ 57.91 %  │ 42.09 %   │ 168,906,484 │ 122,758,473 │ 291,664,957 │ 121,758,473 │ 6.91 %     │ 7.00 %   │ 291,664,957 │ 5.203 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.HillClimberWindowTinyLfu (simple 1%)    │ 58.80 %  │ 41.20 %   │ 171,509,117 │ 120,155,840 │ 291,664,957 │ 119,155,840 │ 7.23 %     │ 32.00 %  │ 291,664,957 │ 4.464 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.S4WindowTinyLfu (1%)                    │ 50.47 %  │ 49.53 %   │ 147,190,948 │ 144,474,009 │ 291,664,957 │ 143,474,009 │ 7.27 %     │          │ 291,664,957 │ 4.655 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.WindowTinyLfu (1%)                      │ 48.33 %  │ 51.67 %   │ 140,950,452 │ 150,714,505 │ 291,664,957 │ 149,714,505 │ 6.04 %     │          │ 291,664,957 │ 4.716 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢
║ two-queue.S3Fifo                               │ 66.33 %  │ 33.67 %   │ 193,462,517 │ 98,202,440  │ 291,664,957 │ 102,377,186 │            │          │ 441,864,249 │ 4.285 min ║
╚════════════════════════════════════════════════╧══════════╧═══════════╧═════════════╧═════════════╧═════════════╧═════════════╧════════════╧══════════╧═════════════╧═══════════╝

## MetaKV size 510000
╔════════════════════════════════════════════════╤══════════╤═══════════╤═════════════╤════════════╤═════════════╤════════════╤════════════╤══════════╤═════════════╤═══════════╗
║ Policy                                         │ Hit Rate │ Miss Rate │ Hits        │ Misses     │ Requests    │ Evictions  │ Admit rate │ Adaption │ Steps       │ Time      ║
╠════════════════════════════════════════════════╪══════════╪═══════════╪═════════════╪════════════╪═════════════╪════════════╪════════════╪══════════╪═════════════╪═══════════╣
║ adaptive.Arc                                   │ 94.79 %  │ 5.21 %    │ 162,371,704 │ 8,919,433  │ 171,291,137 │ 8,400,317  │            │ -50.00 % │ 171,291,137 │ 52.61 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Fifo                                    │ 93.86 %  │ 6.14 %    │ 160,780,986 │ 10,510,151 │ 171,291,137 │ 9,991,035  │            │          │ 332,072,123 │ 35.99 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Fifo_TinyLfu                            │ 71.37 %  │ 28.63 %   │ 122,250,816 │ 49,040,321 │ 171,291,137 │ 48,521,205 │ 0.01 %     │          │ 293,541,953 │ 41.63 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Lru                                     │ 94.64 %  │ 5.36 %    │ 162,103,048 │ 9,188,089  │ 171,291,137 │ 8,668,973  │            │          │ 333,394,185 │ 50.45 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Lru_TinyLfu                             │ 90.68 %  │ 9.32 %    │ 155,331,977 │ 15,959,160 │ 171,291,137 │ 15,440,044 │ 10.39 %    │          │ 326,623,114 │ 52.69 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ linked.Sieve                                   │ 94.98 %  │ 5.02 %    │ 162,699,446 │ 8,591,691  │ 171,291,137 │ 8,072,576  │            │          │ 176,467,047 │ 33.68 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.HillClimberWindowTinyLfu (indicator 1%) │ 94.42 %  │ 5.58 %    │ 161,739,880 │ 9,551,257  │ 171,291,137 │ 9,032,141  │ 4.94 %     │ 19.00 %  │ 171,291,137 │ 1.351 min ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.HillClimberWindowTinyLfu (simple 1%)    │ 94.45 %  │ 5.55 %    │ 161,789,394 │ 9,501,743  │ 171,291,137 │ 8,982,627  │ 8.57 %     │ 31.00 %  │ 171,291,137 │ 55.07 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.S4WindowTinyLfu (1%)                    │ 93.96 %  │ 6.04 %    │ 160,938,713 │ 10,352,424 │ 171,291,137 │ 9,833,308  │ 12.87 %    │          │ 171,291,137 │ 56.24 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ sketch.WindowTinyLfu (1%)                      │ 93.82 %  │ 6.18 %    │ 160,707,662 │ 10,583,475 │ 171,291,137 │ 10,064,359 │ 11.01 %    │          │ 171,291,137 │ 59.01 s   ║
╟────────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢
║ two-queue.S3Fifo                               │ 95.17 %  │ 4.83 %    │ 163,012,996 │ 8,278,141  │ 171,291,137 │ 9,292,304  │            │          │ 185,168,089 │ 42.85 s   ║
╚════════════════════════════════════════════════╧══════════╧═══════════╧═════════════╧════════════╧═════════════╧════════════╧════════════╧══════════╧═════════════╧═══════════╝

[1a1a11a]

I don't know why TinyLFU-LRU and TinyLFU-SIEVE are not good on the Tencent workload, I will investigate later. You proposal is similar to greedy-dual policies, e.g., GDSF, but of course they are not the same,

One potential problem with compare(freq(keyA)+adaptive_coefficient, freq(keyB)) is that when the adaptive_coefficient is large (e.g., >1), most objects will enter cache; however if it is small, e.g., <1, it rejects all one-hit wonders, and we have observed that bloom filter-LRU often can have high miss ratios. Let me know if I misunderstand this.
But I like your proposal to make the adaptive part better, maybe we could collaborate to make eviction algorithms better and more useful.

BTW, one problem with adaptive algorithms is how fast to adapt, and I do not have a good solution. Especially after evaluating over 6000 traces, existing solutions all seem broken to me. (of course, S3-FIFO is also broken, but at least it is easier to understand...)

EDIT: your proposal may work well in block IO cache workloads, where scans are often phased. Need to think more, this is definitely an interesting idea.

[ben-manes]

When I try running the traces (datasets), it is clear that the hill climber is not reacting fast and strongly enough to correct for the recency bias in the trace to make up for the bad initial configuration. The starting configuration is set to 1% for the admission window, but if starting at 10-30% then it matches S3-FIFO (which is set to 10% for its admission's small queue). I ran the traces with percent-main = [0.99, 0.90, 0.80, 0.70, 0.5, 0.3, 0.1] to see multiple outputs for the tinylfu based caches. This is easy to see in the MetaCDN sample above because Lru_TinyLfu has no admission window (0%), underperforms Lru, and the static 1% window in WindowTinyLfu has a significant jump towards LRU (but not enough). Unfortunately the HillClimberWindowTinyLfu is simply unable to figure it out on the trace, so only an oracle giving it a better start position corrects it.

The optimal region sizes is very workload dependent as unfortunately there is no universal starting position that is good at all workloads. If one is optimizing for a very important workload, like a cdn, then is makes sense to tune the parameters upfront based on trace data. Here a moderately sized admission window is important due to the recency with one-hit wonders. In many other cases, like analytics, a very small admission window is critical due to being an MRU-biased workload. The 1% is simply an artifact of what workloads are more often used with Caffeine and Java, but another ecosystems will have a user base with primarily different workloads where another initial setting makes more sense.

The open question is then how to improve the hill climber to be more effective in more workloads. Currently we use a simple climber that monitors the hit rate over a sample period, makes a guess to grow or shrink the region size, turns around if the hit rate worsened, decays the step size to eventually converge. This has the flaw that (a) it randomly guesses the initial direction, (b) it reacts slowly to avoid noise, and (c) the initial step size is an arbitrary heuristic. One improvement might be to use a small sample period with large steps (for high momentum) that ages to a large sample period with small steps ( converge at fine tuned setting). Another idea could be to incorporate ghost entries to hint towards a direction and, perhaps, even the magnitude of change (a form of urgency to reset the sample period or step size).

/cc @jbduncan, @maypok86 per other threads

[ben-manes]

I'd also recommend including product.Caffeine in the list of evaluations. For example, in your tencentPhoto.txt it achieves 64.52 % compared to S3Fifo's 66.33 %. Offhand I am unsure why that differed from the 1% hill climber, but there are so many details to juggle that I am not entirely surprised that it differed from the reference. That seems to match closer in all of your samples, so the difference is much less pronounced.

TencentPhoto: size 1m

``` ╔══════════════════════════════════════════════╤══════════╤═══════════╤═════════════╤═════════════╤═════════════╤═════════════╤════════════╤══════════╤═════════════╤═══════════╗ ║ Policy │ Hit Rate │ Miss Rate │ Hits │ Misses │ Requests │ Evictions │ Admit rate │ Adaption │ Steps │ Time ║ ╠══════════════════════════════════════════════╪══════════╪═══════════╪═════════════╪═════════════╪═════════════╪═════════════╪════════════╪══════════╪═════════════╪═══════════╣ ║ adaptive.Arc │ 63.40 % │ 36.60 % │ 184,912,313 │ 106,752,644 │ 291,664,957 │ 105,752,644 │ │ -50.00 % │ 291,664,957 │ 5.973 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ greedy-dual.Gdsf │ 65.01 % │ 34.99 % │ 189,611,768 │ 102,053,189 │ 291,664,957 │ 101,053,189 │ 100.00 % │ | | 7.729 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ irr.ClockPro │ 64.31 % │ 35.69 % │ 187,576,905 │ 104,088,052 │ 291,664,957 │ 103,088,052 │ | | 291,664,957 │ 1.496 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ irr.Frd │ 64.66 % │ 35.34 % │ 188,598,040 │ 103,066,917 │ 291,664,957 │ 102,066,917 │ | │ 355,086,500 │ 1.362 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ irr.Lirs │ 63.92 % │ 36.08 % │ 186,431,305 │ 105,233,652 │ 291,664,957 │ 104,233,652 │ │ │ 350,484,279 │ 5.735 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ linked.Lru │ 62.13 % │ 37.87 % │ 181,224,461 │ 110,440,496 │ 291,664,957 │ 109,440,496 │ │ │ 472,889,418 │ 4.262 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ linked.Lru_TinyLfu │ 55.48 % │ 44.52 % │ 161,826,012 │ 129,838,945 │ 291,664,957 │ 128,838,945 │ 10.20 % │ │ 453,490,969 │ 5.234 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ linked.SegmentedLru │ 65.37 % │ 34.63 % │ 190,647,816 │ 101,017,141 │ 291,664,957 │ 100,017,141 │ │ | 291,664,957 │ 1.236 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ linked.Sieve │ 65.10 % │ 34.90 % │ 189,865,953 │ 101,799,004 │ 291,664,957 │ 100,799,005 │ | | 332,560,280 │ 1.195 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ opt.Clairvoyant │ 74.61 % │ 25.39 % │ 217,622,956 │ 74,042,001 │ 291,664,957 │ 73,042,001 │ ║ | | 4.907 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ product.Caffeine │ 64.52 % │ 35.48 % │ 188,194,637 │ 103,470,320 │ 291,664,957 │ 102,470,320 │ │ │ │ 7.457 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 1%) │ 58.80 % │ 41.20 % │ 171,509,117 │ 120,155,840 │ 291,664,957 │ 119,155,840 │ 7.23 % │ 32.00 % │ 291,664,957 │ 5.139 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 10%) │ 59.00 % │ 41.00 % │ 172,073,687 │ 119,591,270 │ 291,664,957 │ 118,591,270 │ 6.20 % │ 21.00 % │ 291,664,957 │ 5.115 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 20%) │ 60.95 % │ 39.05 % │ 177,781,806 │ 113,883,151 │ 291,664,957 │ 112,883,151 │ 5.49 % │ 57.00 % │ 291,664,957 │ 5.180 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 30%) │ 61.62 % │ 38.38 % │ 179,714,245 │ 111,950,712 │ 291,664,957 │ 110,950,712 │ 4.92 % │ 55.00 % │ 291,664,957 │ 4.992 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 50%) │ 62.34 % │ 37.66 % │ 181,833,392 │ 109,831,565 │ 291,664,957 │ 108,831,565 │ 3.77 % │ 40.00 % │ 291,664,957 │ 5.066 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 70%) │ 62.55 % │ 37.45 % │ 182,441,448 │ 109,223,509 │ 291,664,957 │ 108,223,509 │ 2.60 % │ 24.00 % │ 291,664,957 │ 5.042 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 90%) │ 62.30 % │ 37.70 % │ 181,707,922 │ 109,957,035 │ 291,664,957 │ 108,957,035 │ 1.31 % │ 7.00 % │ 291,664,957 │ 4.771 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (1%) │ 48.33 % │ 51.67 % │ 140,950,452 │ 150,714,505 │ 291,664,957 │ 149,714,505 │ 6.04 % │ │ 291,664,957 │ 5.671 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (10%) │ 55.28 % │ 44.72 % │ 161,219,888 │ 130,445,069 │ 291,664,957 │ 129,445,069 │ 5.81 % │ │ 291,664,957 │ 5.292 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (20%) │ 57.37 % │ 42.63 % │ 167,320,770 │ 124,344,187 │ 291,664,957 │ 123,344,187 │ 5.42 % │ │ 291,664,957 │ 5.184 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (30%) │ 58.65 % │ 41.35 % │ 171,072,704 │ 120,592,253 │ 291,664,957 │ 119,592,253 │ 5.01 % │ │ 291,664,957 │ 5.130 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (50%) │ 60.56 % │ 39.44 % │ 176,636,245 │ 115,028,712 │ 291,664,957 │ 114,028,712 │ 4.16 % │ │ 291,664,957 │ 5.073 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (70%) │ 61.77 % │ 38.23 % │ 180,175,949 │ 111,489,008 │ 291,664,957 │ 110,489,008 │ 3.07 % │ │ 291,664,957 │ 5.211 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (90%) │ 62.24 % │ 37.76 % │ 181,540,314 │ 110,124,643 │ 291,664,957 │ 109,124,643 │ 1.32 % │ │ 291,664,957 │ 5.162 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ two-queue.TwoQueue │ 64.67 % │ 35.33 % │ 188,625,267 │ 103,039,690 │ 291,664,957 │ 90,265,113 │ │ │ 291,664,957 │ 1.458 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ two-queue.S3Fifo │ 66.33 % │ 33.67 % │ 193,462,517 │ 98,202,440 │ 291,664,957 │ 102,377,186 │ │ │ 441,864,249 │ 4.171 min ║ ╚══════════════════════════════════════════════╧══════════╧═══════════╧═════════════╧═════════════╧═════════════╧═════════════╧════════════╧══════════╧═════════════╧═══════════╝ ```

MetaCDN: size 360000

``` ╔══════════════════════════════════════════════╤══════════╤═══════════╤════════════╤════════════╤════════════╤════════════╤════════════╤══════════╤════════════╤═════════╗ ║ Policy │ Hit Rate │ Miss Rate │ Hits │ Misses │ Requests │ Evictions │ Admit rate │ Adaption │ Steps │ Time ║ ╠══════════════════════════════════════════════╪══════════╪═══════════╪════════════╪════════════╪════════════╪════════════╪════════════╪══════════╪════════════╪═════════╣ ║ adaptive.Arc │ 64.69 % │ 35.31 % │ 29,513,611 │ 16,109,695 │ 45,623,306 │ 15,749,695 │ │ -19.00 % │ 45,623,306 │ 10.42 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ greedy-dual.Gdsf │ 64.72 % │ 35.28 % │ 29,528,728 │ 16,094,578 │ 45,623,306 │ 15,734,578 │ 100.00 % │ │ │ 49.04 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ irr.ClockPro │ 63.86 % │ 36.14 % │ 29,135,562 │ 16,487,744 │ 45,623,306 │ 16,127,744 │ 45,623,306 │ | │ 7.480 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ irr.Frd │ 65.30 % │ 34.70 % │ 29,791,675 │ 15,831,631 │ 45,623,306 │ 15,471,631 │ | | 56,070,652 │ 5.684 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ irr.Lirs │ 63.65 % │ 36.35 % │ 29,039,410 │ 16,583,896 │ 45,623,306 │ 16,223,896 │ │ │ 55,682,848 │ 11.62 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ linked.Lru │ 64.24 % │ 35.76 % │ 29,310,680 │ 16,312,626 │ 45,623,306 │ 15,952,626 │ │ │ 74,933,986 │ 8.726 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ linked.Lru_TinyLfu │ 51.01 % │ 48.99 % │ 23,271,539 │ 22,351,767 │ 45,623,306 │ 21,991,767 │ 6.46 % │ │ 68,894,845 │ 9.601 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ linked.SegmentedLru │ 64.00 % │ 36.00 % │ 29,198,257 │ 16,425,049 │ 45,623,306 │ 16,065,049 │ │ │ 45,623,306 │ 9.524 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ linked.Sieve │ 64.62 % │ 35.38 % │ 29,483,823 │ 16,139,483 │ 45,623,306 │ 15,779,484 │ | | 49,847,299 │ 3.013 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ opt.Clairvoyant │ 70.87 % │ 29.13 % │ 32,334,511 │ 13,288,795 │ 45,623,306 │ 12,928,795 │ │ │ │ 23.37 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ product.Caffeine │ 63.84 % │ 36.16 % │ 29,125,603 │ 16,497,703 │ 45,623,306 │ 16,137,703 │ │ │ │ 17.14 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 1%) │ 61.64 % │ 38.36 % │ 28,121,008 │ 17,502,298 │ 45,623,306 │ 17,142,298 │ 4.34 % │ 40.00 % │ 45,623,306 │ 11.07 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 10%) │ 62.31 % │ 37.69 % │ 28,428,514 │ 17,194,792 │ 45,623,306 │ 16,834,792 │ 4.99 % │ 12.00 % │ 45,623,306 │ 11.31 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 20%) │ 64.35 % │ 35.65 % │ 29,357,710 │ 16,265,596 │ 45,623,306 │ 15,905,596 │ 4.59 % │ 21.00 % │ 45,623,306 │ 11.30 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 30%) │ 64.33 % │ 35.67 % │ 29,348,432 │ 16,274,874 │ 45,623,306 │ 15,914,874 │ 4.25 % │ 9.00 % │ 45,623,306 │ 11.43 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 50%) │ 64.52 % │ 35.48 % │ 29,437,772 │ 16,185,534 │ 45,623,306 │ 15,825,534 │ 3.19 % │ -11.00 % │ 45,623,306 │ 11.46 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 70%) │ 64.47 % │ 35.53 % │ 29,411,418 │ 16,211,888 │ 45,623,306 │ 15,851,888 │ 2.06 % │ -11.00 % │ 45,623,306 │ 11.95 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 90%) │ 64.33 % │ 35.67 % │ 29,350,381 │ 16,272,925 │ 45,623,306 │ 15,912,925 │ 1.07 % │ 7.00 % │ 45,623,306 │ 10.99 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.WindowTinyLfu (1%) │ 61.83 % │ 38.17 % │ 28,207,857 │ 17,415,449 │ 45,623,306 │ 17,055,449 │ 5.23 % │ │ 45,623,306 │ 20.07 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.WindowTinyLfu (10%) │ 63.78 % │ 36.22 % │ 29,100,656 │ 16,522,650 │ 45,623,306 │ 16,162,650 │ 5.33 % │ │ 45,623,306 │ 17.94 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.WindowTinyLfu (20%) │ 64.30 % │ 35.70 % │ 29,334,327 │ 16,288,979 │ 45,623,306 │ 15,928,979 │ 4.88 % │ │ 45,623,306 │ 16.45 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.WindowTinyLfu (30%) │ 64.51 % │ 35.49 % │ 29,430,737 │ 16,192,569 │ 45,623,306 │ 15,832,569 │ 4.35 % │ │ 45,623,306 │ 18.10 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.WindowTinyLfu (50%) │ 64.63 % │ 35.37 % │ 29,487,416 │ 16,135,890 │ 45,623,306 │ 15,775,890 │ 3.18 % │ │ 45,623,306 │ 14.06 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.WindowTinyLfu (70%) │ 64.55 % │ 35.45 % │ 29,447,737 │ 16,175,569 │ 45,623,306 │ 15,815,569 │ 1.94 % │ │ 45,623,306 │ 13.05 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ sketch.WindowTinyLfu (90%) │ 64.35 % │ 35.65 % │ 29,356,778 │ 16,266,528 │ 45,623,306 │ 15,906,528 │ 0.67 % │ │ 45,623,306 │ 13.42 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ two-queue.TwoQueue │ 65.02 % │ 34.98 % │ 29,666,494 │ 15,956,812 │ 45,623,306 │ 14,883,561 │ 45,623,306 │ │ │ 6.012 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼────────────┼────────────┼────────────┼────────────┼────────────┼──────────┼────────────┼─────────╢ ║ two-queue.S3Fifo │ 65.15 % │ 34.85 % │ 29,721,976 │ 15,901,330 │ 45,623,306 │ 16,408,414 │ │ │ 63,448,906 │ 11.50 s ║ ╚══════════════════════════════════════════════╧══════════╧═══════════╧════════════╧════════════╧════════════╧════════════╧════════════╧══════════╧════════════╧═════════╝ ```

MetaKV: size 510000

``` ╔══════════════════════════════════════════════╤══════════╤═══════════╤═════════════╤════════════╤═════════════╤════════════╤════════════╤══════════╤═════════════╤═══════════╗ ║ Policy │ Hit Rate │ Miss Rate │ Hits │ Misses │ Requests │ Evictions │ Admit rate │ Adaption │ Steps │ Time ║ ╠══════════════════════════════════════════════╪══════════╪═══════════╪═════════════╪════════════╪═════════════╪════════════╪════════════╪══════════╪═════════════╪═══════════╣ ║ adaptive.Arc │ 94.77 % │ 5.23 % │ 162,327,504 │ 8,963,633 │ 171,291,137 │ 8,453,633 │ │ -50.00 % │ 171,291,137 │ 30.22 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ greedy-dual.Gdsf │ 94.86 % │ 5.14 % │ 162,491,092 │ 8,800,045 │ 171,291,137 │ 8,290,045 │ 100.00 % │ │ │ 2.389 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ irr.ClockPro │ 94.89 % │ 5.11 % │ 162,542,994 │ 8,748,143 │ 171,291,137 │ 8,238,143 │ | | 171,291,137 │ 12.93 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ irr.Frd │ 95.17 % │ 4.83 % │ 163,020,534 │ 8,270,603 │ 171,291,137 │ 7,760,603 | | │ 175,615,199 │ 10.07 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ irr.Lirs │ 94.91 % │ 5.09 % │ 162,578,267 │ 8,712,870 │ 171,291,137 │ 8,202,870 │ │ │ 175,235,415 │ 30.89 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ linked.Lru │ 94.61 % │ 5.39 % │ 162,058,417 │ 9,232,720 │ 171,291,137 │ 8,722,720 │ │ │ 333,349,554 │ 32.05 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ linked.Lru_TinyLfu │ 90.60 % │ 9.40 % │ 155,192,267 │ 16,098,870 │ 171,291,137 │ 15,588,870 │ 10.17 % │ │ 326,483,404 │ 30.77 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ linked.SegmentedLru │ 94.83 % │ 5.17 % │ 162,441,054 │ 8,850,083 │ 171,291,137 │ 8,340,083 │ │ │ 171,291,137 │ 33.31 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ linked.Sieve │ 94.96 % │ 5.04 % │ 162,658,331 │ 8,632,806 │ 171,291,137 │ 8,122,807 | | │ 176,597,773 │ 4.007 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ opt.Clairvoyant │ 96.36 % │ 3.64 % │ 165,058,215 │ 6,232,922 │ 171,291,137 │ 5,722,922 │ | | │ 1.095 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ product.Caffeine │ 94.74 % │ 5.26 % │ 162,278,007 │ 9,013,130 │ 171,291,137 │ 8,503,130 │ │ │ │ 38.48 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 1%) │ 94.41 % │ 5.59 % │ 161,720,114 │ 9,571,023 │ 171,291,137 │ 9,061,023 │ 8.62 % │ 38.00 % │ 171,291,137 │ 31.25 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 10%) │ 94.81 % │ 5.19 % │ 162,401,872 │ 8,889,265 │ 171,291,137 │ 8,379,265 │ 9.02 % │ 31.00 % │ 171,291,137 │ 30.79 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 20%) │ 94.64 % │ 5.36 % │ 162,106,017 │ 9,185,120 │ 171,291,137 │ 8,675,120 │ 10.08 % │ -10.00 % │ 171,291,137 │ 35.79 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 30%) │ 94.82 % │ 5.18 % │ 162,423,771 │ 8,867,366 │ 171,291,137 │ 8,357,366 │ 8.06 % │ 19.00 % │ 171,291,137 │ 32.95 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 50%) │ 94.80 % │ 5.20 % │ 162,383,209 │ 8,907,928 │ 171,291,137 │ 8,397,928 │ 6.00 % │ 1.00 % │ 171,291,137 │ 42.70 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 70%) │ 94.69 % │ 5.31 % │ 162,200,292 │ 9,090,845 │ 171,291,137 │ 8,580,845 │ 4.29 % │ 1.00 % │ 171,291,137 │ 44.85 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 90%) │ 94.70 % │ 5.30 % │ 162,214,214 │ 9,076,923 │ 171,291,137 │ 8,566,923 │ 4.38 % │ -26.00 % │ 171,291,137 │ 33.31 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (1%) │ 93.75 % │ 6.25 % │ 160,582,336 │ 10,708,801 │ 171,291,137 │ 10,198,801 │ 10.66 % │ │ 171,291,137 │ 41.98 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (10%) │ 94.70 % │ 5.30 % │ 162,205,147 │ 9,085,990 │ 171,291,137 │ 8,575,990 │ 11.74 % │ │ 171,291,137 │ 41.49 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (20%) │ 94.83 % │ 5.17 % │ 162,430,918 │ 8,860,219 │ 171,291,137 │ 8,350,219 │ 10.48 % │ │ 171,291,137 │ 44.35 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (30%) │ 94.87 % │ 5.13 % │ 162,508,780 │ 8,782,357 │ 171,291,137 │ 8,272,357 │ 9.48 % │ │ 171,291,137 │ 43.47 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (50%) │ 94.84 % │ 5.16 % │ 162,455,920 │ 8,835,217 │ 171,291,137 │ 8,325,217 │ 7.08 % │ │ 171,291,137 │ 33.64 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (70%) │ 94.75 % │ 5.25 % │ 162,295,503 │ 8,995,634 │ 171,291,137 │ 8,485,634 │ 4.42 % │ │ 171,291,137 │ 32.08 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ sketch.WindowTinyLfu (90%) │ 94.66 % │ 5.34 % │ 162,142,128 │ 9,149,009 │ 171,291,137 │ 8,639,009 │ 1.51 % │ │ 171,291,137 │ 33.03 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ two-queue.TwoQueue │ 95.05 % │ 4.95 % │ 162,819,240 │ 8,471,897 │ 171,291,137 │ 6,883,197 │ | | 171,291,137 │ 16.36 s ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼────────────┼─────────────┼────────────┼────────────┼──────────┼─────────────┼───────────╢ ║ two-queue.S3Fifo │ 95.14 % │ 4.86 % │ 162,966,103 │ 8,325,034 │ 171,291,137 │ 9,352,297 │ │ │ 185,302,972 │ 23.83 s ║ ╚══════════════════════════════════════════════╧══════════╧═══════════╧═════════════╧════════════╧═════════════╧════════════╧════════════╧══════════╧═════════════╧═══════════╝

[ben-manes]

The difference between Caffeine and the reference implementation is due to the added jitter on admission. This allows 1% of the warm candidates to enter the main cache instead of being rejected by a hot victim. When added to the reference then the hit rate was similar to Caffeine's, 64.80 vs 64.52 above. That 0.3% gain versus Caffeine is because the references uses an ideal 4-bit CountMin sketch whereas Caffeine's is cache-line optimized at the cost of increased collision error.

That change increases the hit rate by 7%. The problem with the reference's admission is explained by @1a1a11a in the S3-FIFO paper as too strict (p. 8),

Second, when the cache is full, TinyLFU compares the least recently used entry from the window LRU and main SLRU, then evicts the less frequently used one. This allows TinyLFU to be more adaptive to different workloads. However, if the tail object in the SLRU happens to have a very high frequency, it may lead to the eviction of an excessive number of new and potentially useful objects.

Caffeine uses jitter to protect the cache from adversarial workloads which might exploit the deterministic choice to force excessive evictions.

The historic usage is retained in a compact popularity sketch, which uses hashing to probabilistically estimate an item's frequency. This exposes a flaw where an adversary could use hash flooding [4] to artificially raise the frequency of the main space's victim and cause all candidates to be rejected. In the worst case, by exploiting hash collisions, an attacker could cause the cache to never hit and hold only worthless items, resulting in a denial-of-service attack against the underlying resource. This is mitigated by introducing jitter, allowing candidates that are at least moderately popular to have a small, random chance of being admitted. This causes the victim to be evicted, but in a way that marginally impacts the hit rate.

Jitter: admission code

```java /** The minimum popularity for allowing randomized admission. */ static final int ADMIT_HASHDOS_THRESHOLD = 6; /** * Determines if the candidate should be accepted into the main space, as determined by its * frequency relative to the victim. A small amount of randomness is used to protect against hash * collision attacks, where the victim's frequency is artificially raised so that no new entries * are admitted. * * @param candidateKey the key for the entry being proposed for long term retention * @param victimKey the key for the entry chosen by the eviction policy for replacement * @return if the candidate should be admitted and the victim ejected */ @GuardedBy("evictionLock") boolean admit(K candidateKey, K victimKey) { int victimFreq = frequencySketch().frequency(victimKey); int candidateFreq = frequencySketch().frequency(candidateKey); if (candidateFreq > victimFreq) { return true; } else if (candidateFreq >= ADMIT_HASHDOS_THRESHOLD) { // The maximum frequency is 15 and halved to 7 after a reset to age the history. An attack // exploits that a hot candidate is rejected in favor of a hot victim. The threshold of a warm // candidate reduces the number of random acceptances to minimize the impact on the hit rate. int random = ThreadLocalRandom.current().nextInt(); return ((random & 127) == 0); } return false; } ```

Jitter: Hit rates

``` ╔══════════════════════════════════════════════╤══════════╤═══════════╤═════════════╤═════════════╤═════════════╤═════════════╤══════════╤═════════════╤═══════════╗ ║ Policy │ Hit Rate │ Miss Rate │ Hits │ Misses │ Requests │ Evictions │ Adaption │ Steps │ Time ║ ╠══════════════════════════════════════════════╪══════════╪═══════════╪═════════════╪═════════════╪═════════════╪═════════════╪══════════╪═════════════╪═══════════╣ ║ sketch.HillClimberWindowTinyLfu (simple 1%) │ 64.80 % │ 35.20 % │ 189,011,054 │ 102,653,903 │ 291,664,957 │ 101,653,903 │ 28.00 % │ 291,664,957 │ 2.211 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 10%) │ 65.02 % │ 34.98 % │ 189,627,018 │ 102,037,939 │ 291,664,957 │ 101,037,939 │ 21.00 % │ 291,664,957 │ 2.158 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 20%) │ 64.97 % │ 35.03 % │ 189,491,086 │ 102,173,871 │ 291,664,957 │ 101,173,871 │ 23.00 % │ 291,664,957 │ 2.117 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 30%) │ 64.78 % │ 35.22 % │ 188,934,498 │ 102,730,459 │ 291,664,957 │ 101,730,459 │ 23.00 % │ 291,664,957 │ 2.151 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 50%) │ 64.10 % │ 35.90 % │ 186,954,204 │ 104,710,753 │ 291,664,957 │ 103,710,753 │ 20.00 % │ 291,664,957 │ 2.206 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 70%) │ 63.53 % │ 36.47 % │ 185,285,035 │ 106,379,922 │ 291,664,957 │ 105,379,922 │ -12.00 % │ 291,664,957 │ 2.145 min ║ ╟──────────────────────────────────────────────┼──────────┼───────────┼─────────────┼─────────────┼─────────────┼─────────────┼──────────┼─────────────┼───────────╢ ║ sketch.HillClimberWindowTinyLfu (simple 90%) │ 62.72 % │ 37.28 % │ 182,930,581 │ 108,734,376 │ 291,664,957 │ 107,734,376 │ -14.00 % │ 291,664,957 │ 2.134 min ║ ╚══════════════════════════════════════════════╧══════════╧═══════════╧═════════════╧═════════════╧═════════════╧═════════════╧══════════╧═════════════╧═══════════╝ ```

[1a1a11a]

Oh, I was not aware of product.caffeine (I thought it is the same as the daptive version and did not evaluate it). I like the jitter idea!

[ben-manes]

fyi, I added the jitter to the simulator with the same configuration as the library. That can be disabled or reconfigured (docs). I think its okay to be enabled by default even though it wasn't described in a paper, but we can flip it off if anyone disagrees.

tiny-lfu.jitter {
  # When enabled an otherwise rejected candidate has a random chance of being admitted
  enabled = true
  # The threshold frequency of a warm candidate to give it a random admission
  threshold = 6
  # The admission probability
  probability = 0.0078125
}

[1a1a11a]

It is great to know that you found that the cause! Adding Jitter looks good to me, is it better to update the name to reflect jitter? I shall add this version of TinyLFU to libCacheSim. BTW, the parameters seem arbitrary to me. Maybe there is a better way to automatically set them.

[ben-manes]

Adding Jitter looks good to me, is it better to update the name to reflect jitter?

sure, I'll play with the naming to see if I can make it clearer.

~Another approach that may solve this better is to reorder the victim in the probation space instead of reusing it (per Gil via Ohad's size-aware TinyLFU paper). That might be too dependent on the choice of the main space's eviction policy, e.g. it might not be ideal if a plain LRU instead of SLRU and is unnecessary for Ristretto which uses sampled Lfu. That victim reordering idea avoids longer chains of rejections and increased the hit rate by 0.6%. Unfortunately that is a bit too small for me to put in the effort of a full regression analysis to safely change the policy to explore algorithm improvements.~ That reordering harmed Lirs loop, so jitter remains the best solution.

I wish we had the foresight to have identified the hot victim problem so that workarounds were evaluated and discussed. Its unfortunately left to tribal knowledge within various implementation docs. This trace is really interesting as it is the first time that I've seen it in practice.

BTW, the parameters seem arbitrary to me. Maybe there is a better way to automatically set them.

definitely, and actually as 100% is better on this workload. That makes sense, it's not too bad of a tradeoff to admit a warm candidate over a hot victim that has low recency. At the time I wanted something small and (rand & 127) == 0 is a cheap version that is close to a 1% via (rand % 100) == 0. I set the config probability to the same value just to line it up with what is currently being used.

I shall add this version of TinyLFU to libCacheSim.

Thanks!