Hacker News Reader

Comment by rozim | Hacker News Reader

Well, once you go down this path you gotta consider ARC: https://en.wikipedia.org/wiki/Adaptive_replacement_cache as I believe it is designed to be scan-resistant.

View on HN

ARC 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#glimps...

Which is, unfortunately, patented: http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=....

Hmm 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.

I'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!

And 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.

When you're referring to innovation, you're talking about everything. I'm referring to software.

It's relatively impolite to tell someone what they meant

PostgreSQL uses ARC (actually 2Q which is very similar), and they worked around the patent.

Postgres doesn't use 2Q either, sorry. It's a simple clock-sweep approximated LRU implementation currently.

Nope, no arc there anymore. It got ripped out shortly after introduction due to IP concerns.

dito for 2Q: http://www.tedunangst.com/flak/post/2Q-buffer-cache-algorith...

I 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.

Looks like they just combined LRU + LFU + a victim cache. Or is there something more insightful about its design?

It 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.

Hmm, that sounds pretty cool. The history part is exactly a victim cache, so it seems like the size tuning is what's novel.

Reply on news.ycombinator.com