5 ms·

It's only four more years before the patent on adaptive replacement caching expires. Then we can use it in memcached ...

ksec 8y ago
Serious ? Doesn't ZFS already uses it?
- ebikelaw 8y ago
  Sun licenses the patent and has related patents on the same thing. Sun provides an implementation under the CDDL license. ZFS on Linux is distributed under the CDDL. Linux is distributed under the GPL for which no patent holders have granted permission to use the patented inventions. Many other implementations exist including one under the Apache license and one under the Mozilla license that I found in two seconds on github. The whole thing is a mess.
IcePic 8y ago
I think there's only a part of ARC that was patented so if you ran the lists differently, you could basically use the double-list idea where you move entities back and forth between them as long as the lists aren't of the same kind.
- logophobia 8y ago
  I basically used a memory-weighted variant of the ARC algorithm, sufficiently different so that the patent doesn't cover it. I imagine there are quite a couple of variants of ARC you can use without violating the patent.
zaarn 8y ago
There is CAR which has almost the same performance and no patent. You can use that.
- eternalban 8y ago
  Why not just use LRU?
  - Symmetry 8y ago
    Performance. The Wikipedia page on cache policies is pretty good. https://en.wikipedia.org/wiki/Cache_replacement_policies#Clock_with_adaptive_replacement_(CAR) https://en.wikipedia.org/wiki/Cache_replacement_policies#Clo...
    - eternalban 8y ago
      Wiki says "Substantially" better than LRU but actual results seem to show performance converging to same levels the larger the cache gets. (See page 5.) https://dbs.uni-leipzig.de/file/ARC.pdf https://dbs.uni-leipzig.de/file/ARC.pdf [p.s. there is also the matter of the (patterns in the) various trace runs. Does anyone know where these traces can be obtained?]
      - ebikelaw 8y ago
        All caches have equal hit rates in the limit when the size of the cache approaches infinity. For finite caches, ARC often wins. In practical experience I've found that a weighted ARC dramatically outperformed LRU for DNS RR caching, in terms of both hit rate and raw CPU time spent per access. This is because it was easy to code an ARC cache that had lock-free access to frequently referenced items; once an item had been promoted to T2 no locks were needed for most accesses. With LRU it's necessary to have exclusive access to the entire cache in order to evict something and add something else. Of course there are more schemes than just LRU and ARC, and one can try to employ lock-free schemes more than I'm willing to do. This is just my experience.
        NovaX 8y ago
        ARC often wins against LRU, but there is a lot of left on the table compared to other policies. That's because they do capture some frequency, but not very well imho. You can mitigate the exclusive lock using a write-ahead log approach [1] [2]. Then you record events into ring buffers, replay in batches, and have an exclusive tryLock. This works really well in practice and lets you do much more complex policy work without much less worry about concurrency. [1] http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html http://highscalability.com/blog/2016/1/25/design-of-a-modern... [2] http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-09-1.pdf http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/pap...
ec109685 8y ago
That’s unfortunate. It’s a natural architecture you stumble into when you have a two tier cache (was doing this 10 years ago when we had a memory mapped cache and a secondary spinning disk cache for a popular website).
NovaX 8y ago
Thankfully there are better algorithms that are not encumbered. ARC is fairly memory hungry and requires a large cache to be effective. It is not as scan resistant and does not capture frequency as well as many believe. LIRS or TinyLFU based policies are what new implementations should be based on. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency

ksec 8y ago

Serious ? Doesn't ZFS already uses it?

ebikelaw 8y ago
Sun licenses the patent and has related patents on the same thing. Sun provides an implementation under the CDDL license. ZFS on Linux is distributed under the CDDL. Linux is distributed under the GPL for which no patent holders have granted permission to use the patented inventions. Many other implementations exist including one under the Apache license and one under the Mozilla license that I found in two seconds on github. The whole thing is a mess.

IcePic 8y ago

I think there's only a part of ARC that was patented so if you ran the lists differently, you could basically use the double-list idea where you move entities back and forth between them as long as the lists aren't of the same kind.

logophobia 8y ago
I basically used a memory-weighted variant of the ARC algorithm, sufficiently different so that the patent doesn't cover it. I imagine there are quite a couple of variants of ARC you can use without violating the patent.

zaarn 8y ago

There is CAR which has almost the same performance and no patent. You can use that.

eternalban 8y ago
Why not just use LRU?
- Symmetry 8y ago
  Performance. The Wikipedia page on cache policies is pretty good. https://en.wikipedia.org/wiki/Cache_replacement_policies#Clock_with_adaptive_replacement_(CAR) https://en.wikipedia.org/wiki/Cache_replacement_policies#Clo...
  - eternalban 8y ago
    Wiki says "Substantially" better than LRU but actual results seem to show performance converging to same levels the larger the cache gets. (See page 5.) https://dbs.uni-leipzig.de/file/ARC.pdf https://dbs.uni-leipzig.de/file/ARC.pdf [p.s. there is also the matter of the (patterns in the) various trace runs. Does anyone know where these traces can be obtained?]
    - ebikelaw 8y ago
      All caches have equal hit rates in the limit when the size of the cache approaches infinity. For finite caches, ARC often wins. In practical experience I've found that a weighted ARC dramatically outperformed LRU for DNS RR caching, in terms of both hit rate and raw CPU time spent per access. This is because it was easy to code an ARC cache that had lock-free access to frequently referenced items; once an item had been promoted to T2 no locks were needed for most accesses. With LRU it's necessary to have exclusive access to the entire cache in order to evict something and add something else. Of course there are more schemes than just LRU and ARC, and one can try to employ lock-free schemes more than I'm willing to do. This is just my experience.
      - NovaX 8y ago
        ARC often wins against LRU, but there is a lot of left on the table compared to other policies. That's because they do capture some frequency, but not very well imho. You can mitigate the exclusive lock using a write-ahead log approach [1] [2]. Then you record events into ring buffers, replay in batches, and have an exclusive tryLock. This works really well in practice and lets you do much more complex policy work without much less worry about concurrency. [1] http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html http://highscalability.com/blog/2016/1/25/design-of-a-modern... [2] http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-09-1.pdf http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/pap...

ec109685 8y ago

That’s unfortunate. It’s a natural architecture you stumble into when you have a two tier cache (was doing this 10 years ago when we had a memory mapped cache and a secondary spinning disk cache for a popular website).

NovaX 8y ago

Thankfully there are better algorithms that are not encumbered. ARC is fairly memory hungry and requires a large cache to be effective. It is not as scan resistant and does not capture frequency as well as many believe. LIRS or TinyLFU based policies are what new implementations should be based on. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency