More Like this

1. Multi-Tenant In-memory Key-Value Cache Partitioning Using Efficient Random Sampling-Based LRU Model

   https://doi.org/10.1109/TCC.2023.3300889  

   Wang, Yuchen; Yang, Junyao; Wang, Zhenlin (August 2023, IEEE Transactions on Cloud Computing)

   In-memory key-value caches are widely used as a performance-critical layer in web applications, disk-based storage, and distributed systems. The Least Recently Used (LRU) replacement policy has become the de facto standard in those systems since it exploits workload locality well. However, the LRU implementation can be costly due to the rigid data structure in maintaining object priority, as well as the locks for object order updating. Redis as one of the most effective and prevalent deployed commercial systems adopts an approximated LRU policy, where the least recently used item from a small, randomly sampled set of items is chosen to evict. This random sampling-based policy is lightweight and shows its flexibility. We observe that there can exist a significant miss ratio gap between exact LRU and random sampling-based LRU under different sampling size $$K$$ s. Therefore existing LRU miss ratio curve (MRC) construction techniques cannot be directly applied without loss of accuracy. In this paper, we introduce a new probabilistic stack algorithm named KRR to accurately model random sampling based-LRU, and extend it to handle both fixed and variable objects in key-value caches. We present an efficient stack update algorithm that reduces the expected running time of KRR significantly. To improve the performance of the in-memory multi-tenant key-value cache that utilizes random sampling-based replacement, we propose kRedis, a reference locality- and latency-aware memory partitioning scheme. kRedis guides the memory allocation among the tenants and dynamically customizes $$K$$ to better exploit the locality of each individual tenant. Evaluation results over diverse workloads show that our model generates accurate miss ratio curves for both fixed and variable object size workloads, and enables practical, low-overhead online MRC prediction. Equipped with KRR, kRedis delivers up to a 50.2% average access latency reduction, and up to a 262.8% throughput improvement compared to Redis. Furthermore, by comparing with pRedis, a state-of-the-art design of memory allocation in Redis, kRedis shows up to 24.8% and 61.8% improvements in average access latency and throughput, respectively. 

   more » « less
2. Inferring Causal Relationships to Improve Caching for Clients with Correlated Requests: Applications o VR

   Bari, Agrim; Zhou, Yuqi; de_Veciana, Gustavo (July 2026, The 35th International Conference on Computer Communications and Networks (ICCCN 2026))

   Collaborative VR and social-metaverse applicationspresent a unique challenge for edge caching due to highly correlated client request patterns. Unlike typical web browsing whererequests are independent, VR users might navigate spaces in groups. This generates sequential “leader-follower” requests that defy the traditional Independent Reference Model (IRM) used to design most caches. In this paper, we introduce the Grouped Client Request Model to formally capture these dependencies between client requests. Our analysis shows that standard policies like Least Recently Used (LRU) fail to adapt to these dynamics, often evicting content right before a follower needs it. To solve this, we propose Least Following and Recently Used (LFRU), a policy that dynamically learns the causal relationships driving these request patterns. By prioritizing objects based on inferred dependencies rather than just recency, LFRU significantly improves the cache hit ratio. Evaluations using emulated VR traces show that, in structured following scenarios, LFRU achieves up to 2.9x higher hit ratios than LRU and 1.9x higher than LFU. 

   more » « less
3. Inferring Causal Relationships to Improve Caching for Clients with Correlated Requests: Applications to VR

   Bari, Agrim; Zhou, Yuqi; de_Veciana, Gustavo (July 2026, In Proc. 35th International Conference on Computer Communications and Networks (ICCCN), Honolulu, HI, USA. July 2026.)

   Collaborative VR and social-metaverse applications present a unique challenge for edge caching due to highly correlated client request patterns. Unlike typical web browsing where requests are independent, VR users might navigate spaces in groups. This generates sequential “leader-follower” requests that defy the traditional Independent Reference Model (IRM) used to design most caches. In this paper, we introduce the Grouped Client Request Model to formally capture these dependencies between client requests. Our analysis shows that standard policies like Least Recently Used (LRU) fail to adapt to these dynamics, often evicting content right before a follower needs it. To solve this, we propose Least Following and Recently Used (LFRU), a policy that dynamically learns the causal relationships driving these request patterns. By prioritizing objects based on inferreddependencies rather than just recency, LFRU significantly improves the cache hit ratio. Evaluations using emulated VR traces show that, in structured following scenarios, LFRU achieves up to 2.9! higher hit ratios than LRU and 1.9! higher than LFU. 

   more » « less
4. Asymptotic Miss Ratio of LRU Caching with Consistent Hashing

   https://doi.org/10.1109/INFOCOM.2018.8485860  

   Ji, Kaiyi; Quan, Guocong; Tan, Jian (April 2018, IEEE INFOCOM)

   To efficiently scale data caching infrastructure to support emerging big data applications, many caching systems rely on consistent hashing to group a large number of servers to form a cooperative cluster. These servers are organized together according to a random hash function. They jointly provide a unified but distributed hash table to serve swift and voluminous data item requests. Different from the single least-recently-used (LRU) server that has already been extensively studied, theoretically characterizing a cluster that consists of multiple LRU servers remains yet to be explored. These servers are not simply added together; the random hashing complicates the behavior. To this end, we derive the asymptotic miss ratio of data item requests on a LRU cluster with consistent hashing. We show that these individual cache spaces on different servers can be effectively viewed as if they could be pooled together to form a single virtual LRU cache space parametrized by an appropriate cache size. This equivalence can be established rigorously under the condition that the cache sizes of the individual servers are large. For typical data caching systems this condition is common. Our theoretical framework provides a convenient abstraction that can directly apply the results from the simpler single LRU cache to the more complex LRU cluster with consistent hashing. 

   more » « less
5. TRAGEN: a synthetic trace generator for realistic cache simulations

   https://doi.org/10.1145/3487552.3487845  

   Sabnis, Anirudh; Sitaraman, Ramesh K. (November 2021, Proceedings of the 21st ACM Internet Measurement Conference (IMC'21))

   Traces from production caching systems of users accessing con- tent are seldom made available to the public as they are considered private and proprietary. The dearth of realistic trace data makes it difficult for system designers and researchers to test and validate new caching algorithms and architectures. To address this key problem, we present TRAGEN, a tool that can generate a synthetic trace that is “similar” to an original trace from the production system in the sense that the two traces would result in similar hit rates in a cache simulation. We validate TRAGEN by first proving that the synthetic trace is similar to the original trace for caches of arbitrary size when the Least-Recently-Used (LRU) policy is used. Next, we empirically validate the similarity of the synthetic trace and original trace for caches that use a broad set of commonly-used caching policies that include LRU, SLRU, FIFO, RANDOM, MARKERS, CLOCK and PLRU. For our empirical validation, we use original request traces drawn from four different traffic classes from the world’s largest CDN, each trace consisting of hundreds of millions of requests for tens of millions of objects. TRAGEN is publicly available and can be used to generate synthetic traces that are similar to actual pro- duction traces for a number of traffic classes such as videos, social media, web, and software downloads. Since the synthetic traces are similar to the original production ones, cache simulations performed using the synthetic traces will yield similar results to what might be attained in a production setting, making TRAGEN a key tool for cache system developers and researchers. 

   more » « less