[jira] [Commented] (KUDU-613) Scan-resistant cache replacement algorithm for the block cache

["Ben Manes (JIRA)" <ji...@apache.org>]

    [ 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)