CSR: NeTS: Small: Theoretical Foundations for Cache Networks: Performance Models, Algorithms, and Applications

缓存系统是互联网数据基础设施的核心组成部分。它们能够以低成本访问快速但有限的缓存空间，该缓存空间存储从存储在缓慢持久介质中的大量数据记录中提取的流行数据项的选择性子集。高速缓存系统极大地提高了例如信息检索、数据分析、社交网络和电子商务中的各种服务的性能。缓存系统已经被广泛部署，但需要有效地扩展以支持新兴的大数据应用程序。为了在高速缓存系统上更好地服务于多个数据请求流，一个基本问题是该高速缓存空间是否应该被池化在一起以联合地服务于这些流，或者被划分以单独地服务于它们。虽然基于系统的方法已经产生了良好的直觉和一阶的解决方案，重要的是，新的理论被开发，以提供一个定量表征的缓存网络，可以导致最佳或接近最佳的解决方案。该项目将为新兴数据处理系统中的缓存系统开发急需的理论基础，并计划将理论结果转化为实际实现。这项研究将在以下相互关联的方面进行。(1)描述竞争流在最近最少使用（LRU）缓存上的未命中率：将开发一个统一的理论框架来研究影响该高速缓存未命中率的关键因素，包括请求率、数据流行度、项大小和跨不同请求流的重叠数据项。新的见解将用于直接提高真实的缓存系统的性能。(2)优化服务器集群的数据缓存：这一重点研究了服务器是否应该集中在一起，以及如何优化不同服务器集群的大小，以及将多个缓存集群的数据请求路由到哪里。 数据缓存和作业调度的联合优化也将得到解决。 (3)从理论到实践的转化：利用开源项目Memcached、Redis、Hadoop、Spark和Tachyon，通过真实的实验来验证理论成果，并通过添加新模块和修改现有代码，将理论转化为工作系统，造福社会、产业和学术界。通过该项目开发的数学分析和新算法的见解预计将在提高缓存网络的性能方面发挥关键作用，例如，对于内存中的键值存储。它们可以为理论研究和实用技术做出贡献。一个具体的重点将弥合随机运筹学和计算机工程教育之间的传统分离。这项建议的研究成果将纳入一个新的研究生课程。其他更广泛的影响包括实际用例和技术转让的行业合作，本科生暑期课程，吸引女性和其他代表性不足的群体的战略，以及发展强大的研究实验室，使其也成为教学实验室。

Caching systems are a core component of Internet data infrastructures. They enable low-cost access to a fast, but limited cache space that stores a selective subset of popular data items drawn from a large collection of data records that are stored in slow, persistent media. Caching systems greatly improve the performance of various services in, for example, information retrieval, data analytics, social networks and e-commence. Caching systems are already widely deployed but need to scale efficiently to support emerging big data applications. To better serve multiple flows of data requests on a caching system, a fundamental question is whether the cache space should be pooled together to serve these flows jointly or be divided to serve them separately. While system-based approaches have yielded good intuition and first-order solutions, it is important that new theories be developed to provide a quantitative characterization of cache networks that can lead to optimal or near-optimal solutions. This project will develop a much-needed theoretical foundation for cache systems in emerging data processing systems, with concrete plans to transition the theoretical results into practical implementations. The research will be carried across the following interrelated thrusts. (1) Characterizing miss ratios of competing flows on least-recently-used (LRU) caching: A unified theoretical framework will be developed to investigate critical factors that impact the cache miss ratios, including request rates, data popularities, item sizes, and overlapped data items across different request flows. The new insights will be used to directly improve the performance of real caching systems. (2) Optimizing data caching for server clusters: this thrust investigates whether servers should be pooled together or not, and how to optimize the sizes of different server clusters as well as where to route data requests for multiple caching clusters. A joint optimization of data caching and job scheduling will also be addressed. (3) Transition from theories into practice: This thrust will leverage open source projects, Memcached, Redis, Hadoop, Spark and Tachyon, to validate the theoretical results by real experiments, and to transition theories into working systems by adding new modules and modifying existing code.This project may benefit society, industry and academia. The insights from the mathematical analysis and the new algorithms developed through this project are expected to play a key role in improving the performance of cache networks, for example, for in-memory key-value stores. They can contribute to both theoretical research and practical technologies. A specific focus will bridge the traditional separation between stochastic operations research and computer engineering education. The research results from this proposal will be integrated into a new graduate-level course. Other broader impacts include industry collaborations for practical use cases and technology transfer, undergraduate summer programs, strategies for engaging women and other under-represented groups, and the development of a strong research lab so that it is also a teaching lab.