[KUDU-613] Scan-resistant cache replacement algorithm for the block cache

• Type: Improvement
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Affects Version/s: M4.5
• Component/s: perf
• Labels: performance roadmap-candidate
• Target Version/s: Backlog
• Assignee: Mahesh Reddy
• Reporter: Andrew Wang
• Created: 11/Feb/15 21:44
• Updated: 10/Nov/23 06:27

Description

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

Issue Links

• is duplicated by: KUDU-767 Un-cached reads should not bump blocks to front of LRU list
• is duplicated by: KUDU-2707 Improve the performance of the block cache under contention
• is related to: IMPALA-10481 Lack of TServer affinity in remote Kudu scans results in bad OS buffer cache behavior on tablet servers
• is related to: KUDU-2707 Improve the performance of the block cache under contention
• relates to: KUDU-1502 Block cache with churn burns lots of CPU in MemTracker consume and release