An Adaptive Replacement Cache Written in Go | Hacker News Reader

An Adaptive Replacement Cache Written in Go

github.com

42 pointsblubbi25 comments

ARC (adaptive replacement cache) is the best generic caching strategy I know of, but the patent status is problematic.

https://en.wikipedia.org/wiki/Adaptive_replacement_cache

  In 2006, IBM was granted a patent for the adaptive replacement cache policy.

http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=...

IBM's patent will take quite a while to expire. It's truly a shame this can't be used by operating system page cache policy because of patents.

Holy crap, that's the reason this algorithm isn't all over the place? That seriously irks me, and this one seems like a great patent to look for either Tesla-esque giveaway or just invalidation (EFF, anybody?).

Smart generic caching could do so much for the global infrastructure with all the data we move around these days.

While the patent may be annoying, in practice there are a number of other cache replacement algorithms and mechanisms that are just as effective as ARC. The tradeoffs inherent in cache replacement algorithms means there are numerous ways of achieving approximately equivalent results. ARC is not a globally optimal design or anything like that.

In that sense, the patent is kind of worthless. Anyone that knows what they are doing can design around it with no loss of functionality or efficiency. A lot of sophisticated systems end up designing custom algorithms tuned for the use case anyway.

The link to http://www.varlena.com/GeneralBits/96.php from that Wikipedia page was an interesting read.

Had implemented this for a grad school project long time back. We had compared the complexity and effectives of this algorithm and compared it with lru, by the end the results of both were comparable unless in certain special conditions arc works well, whereas lru fails like a virus scan etc. But the simplicity of lru triumphs. For anyone interested, here's a paper which was an assigned reading for the project - http://www.cs.cmu.edu/~15-440/READINGS/megiddo-computer2004....

(Outperforming LRU with an Adaptive Replacement Cache Algorithm)

Reply on news.ycombinator.com