CAREER: Coding Theory for Efficient Data Centers via Redundancy Adaptation

在当今信息时代，数据在社会和经济中扮演着越来越重要的角色。因此，大规模数据存储系统-以持久和可访问的方式存储数据的系统-是作为基于因特网的服务的骨干的关键基础设施组成部分。这些系统中存储数据的设备经常出现故障。为了确保设备发生故障时数据不会丢失，存储系统以冗余方式存储数据。这种增加的冗余消耗额外的存储空间，因此直接转化为资源和能量消耗的增加。根据存储设备的故障率配置冗余量。已经观察到这些故障率随时间显著变化，因此动态地使冗余级别适应观察到的故障率提供了显著节省存储空间的机会。然而，在当今的存储系统中的常规冗余自适应消耗过高的资源量。该项目将开发一个理论框架来研究存储系统中的冗余自适应，建立对资源开销的基本限制，并设计实用的算法来实现有效的冗余自适应。通过解决与存储系统的资源、成本和能源效率相关的基础和算法问题，该项目直接有助于确保数据基础设施的可扩展性和可持续性。该项目还将通过研究生和本科生的课程模块，为K-12学生和教师专门设计的模块，以及研究人员和行业从业者会议上的教程，产生重大的教育和推广影响。将开展定向努力，促进STEM教育和指导本科生的多样性。大规模存储系统通常采用擦除码来增加冗余。虽然使冗余适应于观察到的故障率已被证明是有希望的，但擦除编码存储系统中的这种适应需要将已经编码的数据从一种代码转换为另一种代码。传统代码下的这种代码转换消耗了大量的集群资源，例如访问、磁盘I/O和网络带宽。该项目的总体目标是通过冗余适应开发信息和编码理论工具和原则，以提高数据中心的资源和能源效率，沿着以大数据系统为中心的教育和推广工作。具体而言，该项目旨在（1）设计一个信息理论框架来研究代码转换，（2）建立相关资源开销的基本限制，（3）开发一个存储代码的统一理论来设计实用代码。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

In the present information age, data plays an ever important role in society and the economy. Large-scale data-storage systems---systems that store data in a durable and accessible manner---are thus a critical infrastructure component serving as the backbone for Internet based services. The devices on which data is stored in these systems often fail. To ensure that data is not lost when devices fail, storage systems store data in a redundant fashion. This added redundancy consumes additional storage space and thus directly translates to an increase in the consumption of resources and energy. The amount of redundancy is configured based on the failure rates of storage devices. These failure rates have been observed to vary significantly over time, and hence dynamically adapting the redundancy level to observed failure rates provides an opportunity for significant storage space savings. Conventional redundancy adaptation in today's storage systems, however, consumes prohibitively high amount of resources. This project will develop a theoretical framework to study redundancy adaptation in storage systems, establish the fundamental limits on resource overhead, and design practical algorithms to enable efficient redundancy adaptation. By addressing the foundational and algorithmic questions related to the resource, cost and energy efficiency of storage systems, the project directly contributes to ensuring the scalability and sustainability of data infrastructure. This project will also have significant educational and outreach impact via course modules for graduate and undergraduate students, specially designed modules for K-12 students and teachers, and tutorials at conferences for researchers and industry practitioners. Directed efforts will be undertaken for promoting diversity in STEM education and in mentoring undergraduate students. Large-scale storage systems typically employ erasure codes for adding redundancy. While adapting redundancy to observed failure rates has been shown to be promising, such adaptation in erasure-coded storage systems require converting already encoded data from one code to another. Such code conversion under traditional codes consume prohibitively large amounts of cluster resources such as accesses, disk I/O, and network bandwidth. The overarching goal of this project is to develop information- and coding-theoretic tools and principles for resource and energy efficiency in data centers via redundancy adaptation, along with educational and outreach efforts centered around big-data systems. Specifically, the project aims to (1) design an information-theoretic framework to study code conversion, (2) establish fundamental limits on associated resource overhead, and (3) develop a unified theory for storage codes to design practical codes.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.