Adaptive Online Cache Capacity Optimization via Lightweight Working Set Size...
summary
Cuki is a tiny, thread-safe cuckoo-style sketch that estimates working set size and item-repetition ratio online for variable-size objects, with provable error bounds and an optimistic aging concurrency strategy. It outperforms four prior algorithms by over an order of magnitude in accuracy, generates MRCs with ~73% better accuracy while using less memory, and plugs into Alluxio/Presto; end-to-end results show 79% latency reduction for table queries and ~29% higher file-read throughput.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:28Cache capacity challenges
- 2:50Working set size estimation
- 3:56Limitations of existing approaches
- 5:18Cookie data structure design
- 7:50Cookie operations: insertion and aging
- 9:17Concurrency control in Cookie
- 10:19Adaptive cache tuning with Cookie
- 11:46Cookie estimation accuracy
- 12:52Working set accumulation in Cookie
- 13:56Energy performance in Presto
- 15:05File reading performance
- 15:50MRC accuracy comparison
- 16:51Presto system improvements
- 17:36Optimizing cache capacity
- 18:00Summary
related talks
18mCuckoo for Clients: Disaggregated Cuckoo Hashing
20mMitigating Asymmetric Read and Write Costs in Cuckoo Hashing for Storage Systems
20mSymbiosis: The Art of Application and Kernel Cache Cooperation
22mOSCA: An Online-Model Based Cache Allocation Scheme in Cloud Block Storage Systems
25mMemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing
16mKVCache Cache in the Wild: Characterizing and Optimizing KVCache Cache at a...
28mOptimizing Latency-Sensitive Queries for Presto at Facebook
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures