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.