3 ms·
One thing I've seen is that a weighted LRU is usually slightly better for unpredictable workloads. i.e. it will never evict high use cache data when there's a f
by falcolas 10y ago
One thing I've seen is that a weighted LRU is usually slightly better for unpredictable workloads. i.e. it will never evict high use cache data when there's a flurry of one-off traffic that would normally start evicting a normal LRU cache, and even a 2 random LRU scheme.
This is particularly relevant for databases and keeping rows in memory.
The algorithm is something like "add two weight when an item is used, and decay one from every item every second, evict items under pressure from the lowest weight to the highest."
- rozim 10y agoWell, 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 10y 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 10y 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 10y 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 10y agoWhen you're referring to innovation, you're talking about everything. I'm referring to software.
- stilldontcount 10y agoIt's relatively impolite to tell someone what they meant
- true_religion 10y 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 10y agoPostgreSQL uses ARC (actually 2Q which is very similar), and they worked around the patent.
- Cyph0n 10y agoLooks like they just combined LRU + LFU + a victim cache. Or is there something more insightful about its design?
- logophobia 10y 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 10y 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 10y agodito for 2Q: http://www.tedunangst.com/flak/post/2Q-buffer-cache-algorithm http://www.tedunangst.com/flak/post/2Q-buffer-cache-algorith...
- jayd16 10y 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 10y 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...