Probabilistic Resource Sharing in Cloud Caches with Heterogeneous Object Sizes

In-memory key-value stores are critical caching infrastructure for numerous cloud services. Unlike traditional CPU caches that often assume uniform item sizes, cloud caches frequently handle heterogeneous-sized objects, introducing significant challenges in cache management, particularly in shared multi-tenant environments. Existing cache sharing solutions designed for uniform-sized objects are often not optimized for these scenarios.This paper presents a probabilistic cache sharing scheme that dynamically adapts eviction probabilities across different traffic classes based on their performance. Our approach redistributes cache space at eviction events, reclaiming space probabilistically from one class to serve the needs of another. Our scheme operates independently of the underlying per-class eviction policies and adapts to time-varying traffic patterns. We evaluate our approach using real-world traces with heterogeneous object sizes, demonstrating its effectiveness in dynamically allocating cache space and improving overall cache performance in shared environments.