[
https://issues.apache.org/jira/browse/KUDU-613?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15234284#comment-15234284
]
Ben Manes commented on KUDU-613:
--------------------------------
[TinyLFU|http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html]
provides [near optimal|https://github.com/ben-manes/caffeine/wiki/Efficiency]
hit rates and is very simple to implement. Instead of ghost entries (like ARC),
it more compactly retains history by using a frequency sketch as an admission
filter. It augments an existing policy (like LRU) by comparing the candidate
and victim, and retains the one with the highest frequency. The frequencies are
aged (halving the counters) by sampling at a rate of 10x the cache's size. The
Java implementation, [Caffeine|https://github.com/ben-manes/caffeine], shows
how it can be made concurrent using the write-ahead log trick to record &
replay events.
> Scan-resistant cache replacement algorithm for the block cache
> --------------------------------------------------------------
>
> Key: KUDU-613
> URL: https://issues.apache.org/jira/browse/KUDU-613
> Project: Kudu
> Issue Type: Improvement
> Components: perf
> Affects Versions: M4.5
> Reporter: Andrew Wang
>
> The block cache currently uses LRU, which is vulnerable to large scan
> workloads. It'd be good to implement something like 2Q.
> ARC (patent encumbered, but good for ideas):
> https://www.usenix.org/conference/fast-03/arc-self-tuning-low-overhead-replacement-cache
> HBase (2Q like):
> https://github.com/apache/hbase/blob/master/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/LruBlockCache.java
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
