6 ms·
Well, once you go down this path you gotta consider ARC: https://en.wikipedia.org/wiki/Adaptive_replacement_cache https://en.wikipedia.org/wiki/Adaptive_replace
by rozim 9y ago
Well, once you go down this path you gotta consider ARC: https://en.wikipedia.org/wiki/Adaptive_replacement_cache https://en.wikipedia.org/wiki/Adaptive_replacement_cache
as I believe it is designed to be scan-resistant.
- logophobia 9y agoWhich is, unfortunately, patented: http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=6996676.PN.&OS=PN/6996676&RS=PN/6996676 http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=....
- takeda 9y agoHmm given that patents span for 20 years, and that's essentially forever in computer world, once this patent expires it probably will be worthless. In a world where advances are built on top of other advancements, patents just stifle innovation.
- noonewhocounts 9y agoAnd yet innovation proceeds at a pace unmatched in history, and is so commonplace it gets dismissed as not counting when it's not a revolutionary breakthrough.
- takeda 9y agoWhen you're referring to innovation, you're talking about everything. I'm referring to software.
- stilldontcount 9y agoIt's relatively impolite to tell someone what they meant
- true_religion 9y agoI'd disagree. There's a common saying that the great companies of today are made by someone trawling the forgotten CS papers of the 1980s, and implementing them to solve problems that didn't exist then. Also this patent expires in 8 years. Will we still need caches in 8 years? Why yes we will!
- olavgg 9y agoPostgreSQL uses ARC (actually 2Q which is very similar), and they worked around the patent.
- Cyph0n 9y agoLooks like they just combined LRU + LFU + a victim cache. Or is there something more insightful about its design?
- logophobia 9y agoIt keeps a history of evicted keys. If there's a miss, it knows if the miss was in the lfu or lru part, and it tunes the ratio of space allocated to the lru and lfu part of the cache.
- Cyph0n 9y agoHmm, that sounds pretty cool. The history part is exactly a victim cache, so it seems like the size tuning is what's novel.
- mtanski 9y agodito for 2Q: http://www.tedunangst.com/flak/post/2Q-buffer-cache-algorithm http://www.tedunangst.com/flak/post/2Q-buffer-cache-algorith...
- jayd16 9y agoI was going to joke about how we need generational LRUs and here I see a comment about ARC. I guess its not about ref counts though.
- NovaX 9y agoARC has modest scan resistance due to a limited history. Like LRU, it suffers from cache pollution. See the glimpse trace for this workload type [1]. LIRS and TinyLFU make better use of their history to filter out low value items early. The fundamental difference in their designs is starting point: LIRS starts from LRU and infers recency, whereas TinyLFU starts from frequency and infers recency. There is work on an Adaptive TinyLFU that mimics LRU by using an admission window, sampling the hit rate, and using hill climbing to adjust the region sizes to best fit the workload. [1] https://github.com/ben-manes/caffeine/wiki/Efficiency#glimpse https://github.com/ben-manes/caffeine/wiki/Efficiency#glimps...