Collaborative Research: CNS Core: Medium: Learning to Cache and Caching to Learn in High Performance Caching Systems

缓存是云计算和内容分发的基础，对它们支持的大量应用程序和服务非常重要。缓存算法的关键性能指标是其快速而准确地了解不断变化的受欢迎程度分布的能力。然而，使用解释受欢迎程度变化的真实世界痕迹的实证研究与假设固定受欢迎程度的分析性绩效分析结果之间存在严重脱节。这个项目的一个基本目标是开发一种基于在线学习和强化学习的方法，用于缓存算法设计，并提供可证明的性能保证。这使得可以针对各种应用环境定制的缓存算法的系统设计成为可能。这些算法的使用案例是支持大规模云应用和服务的高性能缓存网络。对高性能缓存系统的仿真以利用和经验性地评估开发的在线学习算法支持这一目标，并为开发的方法提供了现实环境。这一结果还将提升内容分发平台的表现。与此同时，该项目开发了与机器学习领域相关的基本理论，特别是与在线学习有关的理论。该项目旨在优化利用本地可用内存和缓存的计算资源，同时通过快速和准确地学习内容受欢迎程度来确保可证明的良好性能。这需要几个数学工具的结合来分析在线学习算法，以及强大的系统开发技能来使算法成为现实。该项目在两个主要主题中解决了这些关键挑战。第一个主题着重于系统地设计缓存网络中的分布式在线学习，使用协作过滤来分布式识别流行内容，并使用多代理强化学习来联合学习和内容放置。第二个主题侧重于使用第一个主题中开发的算法构建高性能缓存系统，并量化算法对现实世界应用程序的影响，例如开源电子商务网站Hipster Shop和Spark数据分析作业管道。该项目的直接影响是创建适用于云计算和内容分发网络的高性能缓存方案。本项目还提出了在线学习的基本理论。该项目包括一个专注于机器学习和缓存的教育计划，以及以夏令营和高中生研讨会的形式进行的推广。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Caching is fundamental to cloud computing and content distribution, and is important to the vast number of applications and services they support. Crucial performance metrics of a caching algorithm are its ability to quickly and accurately learn a changing popularity distribution. However, there is a serious disconnect between empirical studies using real-world traces that account for popularity changes, and analytical performance analysis results that assume a fixed popularity. A basic goal of this project is to develop a methodology based on online learning and reinforcement learning for caching algorithm design with provable performance guarantees. This enables the systematic design of caching algorithms that can be tailored to a variety of application contexts. The use-case of these algorithms is in high performance caching networks that support large-scale cloud applications and services. Emulation of high-performance caching systems to leverage and to empirically evaluate the online learning algorithms developed supports this goal, and provides a real-world context for the methodology developed. The results will also enhance the performance of content distribution platforms. At the same time the project develops fundamental theories that pertain to the area of machine learning, specifically to online learning. This project aims at optimally utilizing locally available memory and computing resources of caches, while ensuring provably good performance via fast and accurate learning of content popularity. This requires the conjunction of several mathematical tools to analyze online learning algorithms, as well as strong systems development skills to make the algorithms a reality. The project addresses these key challenges in two main themes. The first theme focuses on systematic design of distributed online learning in networks of caches using collaborative filtering for distributed identification of popular content, and multi-agent reinforcement learning for joint learning and content placement. The second theme focuses on building high performing caching systems using the algorithms developed in the first theme, and quantifying the impacts of the algorithms on real-world applications such as Hipster Shop, an open-source e-commerce website, and Spark data-analytics job pipelines. The immediate impact of this project is in creating high performance caching schemes that apply to cloud computing and content distribution networks. This project also advances the fundamental theory of online learning. The project includes an education plan focusing on machine learning and caching, and outreach in the form of summer camps and seminars for high school students.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.