Graduate student Daniel Byrne, PhD in Computer Science, will present his final oral examination (defense) on May 14, 2024, a 9 am in Rekhi 214 and via Zoom online meeting. The title of Byrne’s defense is, “Model Guided Optimization for Key-Value Caches.”
Byrne is advised by Department of Computer Science faculty members Zhenlin Wang and Nilfer Onder.
Defense Abstract
Modern web services deploy key-value caches to store popular requests to backend systems. As such, how the cache stores data impacts both the cache miss ratio and throughput. Therefore, in this thesis, we introduce and apply cache modeling techniques to optimize the memory organization of a key-value cache to improve overall cache performance.
Specifically, we begin with a single-level key-value cache and use miss ratio curves to adjust the memory assigned to the residing applications dynamically. This leads to an improvement in miss ratio up to 25% over state-of-the-art techniques and an 8.8% improvement in cache throughput. We then consider the implications of memory reassignment for large cache deployments and introduce a faster mechanism that allows the cache to reach steady-state 53% faster. Our patch has been incorporated into the commonly used memcached system.
As key-value cache workloads grow in size, we introduce equations to model the behavior of multi-level caches equipped with DRAM and NVM memory for additional capacity. Given the performance disparity between typical DRAM and NVM mediums, we focus on the number of writebacks incurred from L1 to L2. We demonstrate that our closed-form model and trace-based model achieve a 3% error from a simulated two-level cache.
Finally, we introduce a novel mechanism for memory organization in a two-level key-value cache that considers whether data should be cached inclusively or exclusively with respect to the second level. Our algorithm, CLUsivity, partitions each class of objects in the cache as inclusive or exclusive and assigns the corresponding amount of DRAM and NVM memory that maximizes performance. Our results show that CLUsivity can improve overall cache throughput relative to an inclusive cache while maintaining a miss ratio comparable to an exclusive cache.