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

缓存系统是Internet数据基础设施的核心组件。它们支持对快速但有限的缓存空间的低成本访问，缓存空间存储从存储在慢速持久介质中的大量数据记录中提取的流行数据项的选择性子集。缓存系统极大地提高了各种服务的性能，例如，信息检索、数据分析、社交网络和电子商务。缓存系统已经被广泛部署，但需要有效地扩展以支持新兴的大数据应用。为了更好地为缓存系统上的多个数据请求流提供服务，一个基本问题是，缓存空间是应该集中在一起共同为这些流提供服务，还是应该分开为它们单独提供服务。虽然基于系统的方法已经产生了良好的直觉和一阶解决方案，但重要的是要发展新的理论来提供缓存网络的定量表征，从而导致最优或接近最优的解决方案。该项目将为新兴数据处理系统中的缓存系统提供急需的理论基础，并制定具体计划将理论结果转化为实际实施。这项研究将在下列相互关联的重点领域进行。(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.