More Like this

1. Caching with Delayed Hits

   https://doi.org/10.1145/3387514.3405883  

   Atre, Nirav; Sherry, Justine; Wang, Weina; Berger, Daniel S. (July 2020, SIGCOMM)

   Caches are at the heart of latency-sensitive systems. In this paper, we identify a growing challenge for the design of latency-minimizing caches called delayed hits. Delayed hits occur at high throughput, when multiple requests to the same object queue up before an outstanding cache miss is resolved. This effect increases latencies beyond the predictions of traditional caching models and simulations; in fact, caching algorithms are designed as if delayed hits simply didn't exist. We show that traditional caching strategies -- even so called 'optimal' algorithms -- can fail to minimize latency in the presence of delayed hits. We design a new, latency-optimal offline caching algorithm called belatedly which reduces average latencies by up to 45% compared to the traditional, hit-rate optimal Belady's algorithm. Using belatedly as our guide, we show that incorporating an object's 'aggregate delay' into online caching heuristics can improve latencies for practical caching systems by up to 40%. We implement a prototype, Minimum-AggregateDelay (mad), within a CDN caching node. Using a CDN production trace and backends deployed in different geographic locations, we show that mad can reduce latencies by 12-18% depending on the backend RTTs. 

   more » « less
2. Packet Chasing: Spying on Network Packets over a Cache Side-Channel

   https://doi.org/10.1109/ISCA45697.2020.00065  

   Taram, Mohammadkazem; Venkat, Ashish; Tullsen, Dean (May 2020, International Symposium on Computer Architecture)

   null (Ed.)

   This paper presents Packet Chasing, an attack on the network that does not require access to the network, and works regardless of the privilege level of the process receiving the packets. A spy process can easily probe and discover the exact cache location of each buffer used by the network driver. Even more useful, it can discover the exact sequence in which those buffers are used to receive packets. This then enables packet frequency and packet sizes to be monitored through cache side channels. This allows both covert channels between a sender and a remote spy with no access to the network, as well as direct attacks that can identify, among other things, the web page access patterns of a victim on the network. In addition to identifying the potential attack, this work proposes a software-based short-term mitigation as well as a light-weight, adaptive, cache partitioning mitigation that blocks the interference of I/O and CPU requests in the last-level cache. 

   more » « less
3. Learning to Cache and Caching to Learn: Regret Analysis of Caching Algorithms

   https://doi.org/10.1109/TNET.2021.3105880  

   Bura, Archana; Rengarajan, Desik; Kalathil, Dileep; Shakkottai, Srinivas; Chamberland, Jean-Francois (January 2021, IEEE/ACM Transactions on Networking)

   null (Ed.)

   Crucial performance metrics of a caching algorithm include its ability to quickly and accurately learn a popularity distribution of requests. However, a majority of work on analytical performance analysis focuses on hit probability after an asymptotically large time has elapsed. We consider an online learning viewpoint, and characterize the ``regret'' in terms of the finite time difference between the hits achieved by a candidate caching algorithm with respect to a genie-aided scheme that places the most popular items in the cache. We first consider the Full Observation regime wherein all requests are seen by the cache. We show that the Least Frequently Used (LFU) algorithm is able to achieve order optimal regret, which is matched by an efficient counting algorithm design that we call LFU-Lite. We then consider the Partial Observation regime wherein only requests for items currently cached are seen by the cache, making it similar to an online learning problem related to the multi-armed bandit problem. We show how approaching this ``caching bandit'' using traditional approaches yields either high complexity or regret, but a simple algorithm design that exploits the structure of the distribution can ensure order optimal regret. We conclude by illustrating our insights using numerical simulations. 

   more » « less
4. Improving Cache Performance for Large-Scale Photo Stores via Heuristic Prefetching Scheme

   https://doi.org/10.1109/TPDS.2019.2902392  

   Zhou, Ke; Sun, Si; Wang, Hua; Huang, Ping; He, Xubin; Lai, Ran; Li, Wenyan; Liu, Wenjie; Yang, Tianming (April 2019, IEEE Transactions on Parallel and Distributed Systems)

   Photo service providers are facing critical challenges of dealing with the huge amount of photo storage, typically in a magnitude of billions of photos, while ensuring national-wide or world-wide satisfactory user experiences. Distributed photo caching architecture is widely deployed to meet high performance expectations, where efficient still mysterious caching policies play essential roles. In this work, we present a comprehensive study on internet-scale photo caching algorithms in the case of QQPhoto from Tencent Inc., the largest social network service company in China. We unveil that even advanced cache algorithms can only perform at a similar level as simple baseline algorithms and there still exists a large performance gap between these cache algorithms and the theoretically optimal algorithm due to the complicated access behaviors in such a large multi-tenant environment. We then expound the reasons behind this phenomenon via extensively investigating the characteristics of QQPhoto workloads. Finally, in order to realistically further improve QQPhoto cache efficiency, we propose to incorporate a prefetcher in the cache stack based on the observed immediacy feature that is unique to the QQPhoto workload. The prefetcher proactively prefetches selected photos into cache before are requested for the first time to eliminate compulsory misses and promote hit ratios. Our extensive evaluation results show that with appropriate prefetching we improve the cache hit ratio by up to 7.4%, while reducing the average access latency by 6.9% at a marginal cost of 4.14% backend network traffic compared to the original system that performs no prefetching. 

   more » « less
5. Why increasing the hit ratio can hurt cache throughput

   https://doi.org/10.1007/s11134-026-09986-1  

   Qiu, Ziyue; Yang, Juncheng; Harchol-Balter, Mor (June 2026, Queueing Systems)

   Abstract Software caches are an intrinsic component of almost every computer system. Consequently, caching algorithms, particularly eviction policies, are the topic of many papers. Most of these prior papers evaluate the caching algorithm based on itshit ratio, namely the fraction of requests that are found in the cache, as opposed to disk. The “hit ratio” is viewed as a proxy for traditional performance metrics like system throughput or response time. Intuitively, it makes sense that a higher hit ratio should lead to higher throughput (and lower response time), since more requests are found in the cache (low access time) as opposed to the backend storage (high access time). This paper challenges this intuition. We show that increasing the hit ratio can actuallyhurtthe throughput (and response time) for many caching algorithms. Specifically, higher hit ratios can lead to contention on the hit path, resulting in lower throughput. This is relevant in light of recent caching systems papers that have noticed that many LRU-based eviction policies can suffer from high contention and thus have aimed at developing solutions that reduce lock contention. Our paper provides a methodological framework to precisely determine where the contention is and how the hit ratio affects this. In particular, we are able to pinpoint the exact hit ratio beyond which throughput degrades, across a wide variety of eviction algorithms. Our investigation follows a three-pronged approach involving (i) queueing modeling and analysis, (ii) simulation to validate the accuracy of the queueing model, and (iii) implementation and measurement. We also show that the phenomenon of decreasing throughput at higher hit ratios is likely to be more pronounced in future systems, where the trend is toward faster disks and more cores per CPU. 

   more » « less