CNS Core: Small: Caching with Delayed Hits

CNS 核心：小型：延迟命中缓存

• 批准号: 2007733
• 负责人: Justine Sherry
• 金额: $ 50万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007733&HistoricalAwards=false
• 关键词: CNS; Core; Small; Caching; Delayed

Caches are responsible for storing data close to where computer systems access them in order to make things faster. For example, when a user accesses a website, the web browser first checks the cache to see if the webpage files are already there; if not, the cache goes to the website servers, which takes longer. Unfortunately, caches are small and don’t have room to store everything. In order to make systems faster, this project’s goal is to decide what to store in the cache while accounting for "delayed hits", which occur when multiple requests happen for the same data back-to-back.This project will explore the impact of delayed hits on cache performance. Delayed hits occur when a request "misses" in the cache, and a second request occurs for the same object before the first request has returned from the backing store. The second hit does not have equal latency to a true "hit" nor a true "miss". Because caches assume that requests result in either a hit or a miss, caches do not achieve the best possible latency. This project will explore new caching algorithms to achieve better latency by taking delayed hits into account.The technical impact of this project will be to improve latencies for a broad range of computer systems that rely on caches, from key-value stores in data centers to web caches. Systems with very long latencies will benefit the most, leading to the hypothesis that one will see strong benefits for web caches in Internet-underserved regions which may be hundreds of miles from their nearest data center. This project will also impact education and broaden participation in computing by including undergraduate researchers in the research process.All simulators, scripts, and analysis resulting from this work will be uploaded to public repositories (http://www.github.com/cmu-snap) where they may be accessed by the public indefinitely.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

高速缓存负责将数据存储在计算机系统访问它们的位置附近，以便提高速度。例如，当用户访问网站时，Web浏览器首先检查缓存以查看网页文件是否已经在那里；如果没有，则缓存到网站服务器，这需要更长的时间。不幸的是，缓存很小，没有空间存储所有内容。为了让系统更快，这个项目的目标是决定在缓存中存储什么，同时考虑到当多个请求背靠背地发生相同数据时发生的“延迟命中”。本项目将探索延迟命中对缓存性能的影响。延迟命中发生在请求在高速缓存中“未命中”时，并且在第一个请求从后备存储器返回之前对同一对象发生第二个请求。第二次命中不具有与真正的“命中”或真正的“未命中”相同的等待时间。因为缓存假定请求会导致命中或未命中，所以缓存不会达到可能的最佳延迟。该项目将探索新的缓存算法，通过考虑延迟命中来实现更好的延迟。该项目的技术影响将是改善依赖缓存的广泛计算机系统的延迟，从数据中心的键值存储到Web缓存。延迟非常长的系统将受益最大，这导致人们将在互联网服务不足的地区看到网络缓存的巨大好处，这些地区可能距离他们最近的数据中心数百英里。该项目还将通过将本科研究人员纳入研究过程来影响教育和扩大对计算的参与。所有由这项工作产生的模拟器、脚本和分析将被上传到公共存储库(http://www.github.com/cmu-snap))，在那里公众可以无限期地访问它们。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Tackling heterogeneous traffic in multi-access systems via erasure coded servers

• DOI: 10.1145/3492866.3549713
• 发表时间: 2022-07
• 期刊: Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
• 作者: Tuhinangshu Choudhury;Weina Wang;Gauri Joshi

Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption

平均奖励的不安分强盗：打破统一的全球吸引子假设

• 发表时间: 2023
• 期刊: Advances in neural information processing systems
• 作者: Hong, Yige;Xie, Qiaomin;Chen, Yudong;Wang, Weina
• 通讯作者: Wang, Weina

Caching with Delayed Hits

• DOI: 10.1145/3387514.3405883
• 发表时间: 2020-07
• 期刊: Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication
• 作者: Nirav Atre;Justine Sherry;Weina Wang;Daniel S. Berger

Sharp waiting-time bounds for multiserver jobs

• DOI: 10.1145/3492866.3549717
• 发表时间: 2021-09
• 期刊: Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
• 作者: Yige Hong;Weina Wang

SurgeProtector: mitigating temporal algorithmic complexity attacks using adversarial scheduling

• DOI: 10.1145/3544216.3544250
• 发表时间: 2022-08
• 期刊: Proceedings of the ACM SIGCOMM 2022 Conference
• 作者: Nirav Atre;Hugo Sadok;Erica Chiang;Weina Wang;Justine Sherry