CAREER: Coding Theory for Efficient Data Centers via Redundancy Adaptation

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.