DragonFlydb: Cache Design

It seems odd that the article doesn't mention Redis's LFU mode which improved on LRU since about 5+ years ago.

Dash sounds super interesting. I hadn&#x27;t heard of that until now.<p>If 2Q sounds interesting see also the TinyLFU paper[0]. TinyLFU is the strategy used by Ristretto, the Go LFU cache used by Dgraph, Vitess, and SpiceDB. In the introduction of the paper it lists related works including 2Q and nice high level descriptions of alternatives.<p>[0]: <a href="https:&#x2F;&#x2F;www.cs.technion.ac.il&#x2F;~gilga&#x2F;TinyLFU_PDP2014.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.technion.ac.il&#x2F;~gilga&#x2F;TinyLFU_PDP2014.pdf</a>

Very cool.<p>Other similar and interesting non-LRU caches:<p>MySQL <a href="https:&#x2F;&#x2F;medium.com&#x2F;@arpitbhayani&#x2F;what-makes-mysql-lru-cache-scan-resistant-a73364f286d7" rel="nofollow">https:&#x2F;&#x2F;medium.com&#x2F;@arpitbhayani&#x2F;what-makes-mysql-lru-cache-...</a><p>Intel Sandy Bridge+ <a href="https:&#x2F;&#x2F;blog.stuffedcow.net&#x2F;2013&#x2F;01&#x2F;ivb-cache-replacement&#x2F;" rel="nofollow">https:&#x2F;&#x2F;blog.stuffedcow.net&#x2F;2013&#x2F;01&#x2F;ivb-cache-replacement&#x2F;</a>

HN post from 3 months ago with 350+ comments.<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=31560547" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=31560547</a>

To me, 2Q reminded me a lot of the ARC, Adaptive Replacement Cache[1], as I know it from ZFS.<p>Mixing frequency of access with time of access seems to be a requirement for any cache that sees a mixed workload. On that note, has anyone tried frecency[2] for caching? I never gotten around to testing it myself and can&#x27;t decide if it&#x27;d do a good job or not.<p>[1]: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Adaptive_replacement_cache" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Adaptive_replacement_cache</a><p>[2]: <a href="https:&#x2F;&#x2F;wiki.mozilla.org&#x2F;User:Jesse&#x2F;NewFrecency?title=User:Jesse&#x2F;NewFrecency" rel="nofollow">https:&#x2F;&#x2F;wiki.mozilla.org&#x2F;User:Jesse&#x2F;NewFrecency?title=User:J...</a>

MySQL approximates a hacky version of a similar idea with the bufferpool (newest additions don&#x27;t go to the top of the LRU so they age out faster if not re-accessed) to avoid random full table scans from thrashing the cache:<p><a href="https:&#x2F;&#x2F;dev.mysql.com&#x2F;doc&#x2F;refman&#x2F;5.7&#x2F;en&#x2F;innodb-performance-midpoint_insertion.html" rel="nofollow">https:&#x2F;&#x2F;dev.mysql.com&#x2F;doc&#x2F;refman&#x2F;5.7&#x2F;en&#x2F;innodb-performance-m...</a>

Redis has LFU, implemented many years ago.