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

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

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.