Data is at the heart of many of the services that society relies on. As a consequence, distributed storage systems (DSSs), which store data, are a fundamental part of most applications. Because of their essential role, these systems need to be extremely reliable. On top of this, DSSs need to be able to scale and grow incrementally to satisfy the increasing demand for storage. It is common for DSS deployments to be massive in size: just a single deployment can often store Petabytes of data and manage tens of thousands of disks. Supporting large-scale systems requires a large amount of resources (such as hardware, energy, physical space, and personnel) and results in significant capital and operating expenditures. For this reason, making these systems efficient is important as even small improvements can have a large impact.

DSSs commonly use erasure coding to tolerate failures. Typically, the operator of the DSS will choose the type of erasure code and its parameters based on the expected cluster conditions and their target metrics. However, cluster conditions are vastly heterogeneous and subject to significant variations across time. Current systems handle this by using extremely conservative amounts of redundancy and by relying on unplanned interventions, both of which are very costly. This thesis focuses on solving this problem by making DSSs more robust, by enabling them to automatically adapt to heterogeneity and variations across time and space.

The first part focuses on variations over time that affect the DSS. We propose convertible codes, a theoretical framework for studying code conversion, i.e. the process of converting already-encoded data into a different encoding. Using this framework, we derive lower bounds on the cost of conversion for multiple metrics and propose optimal code constructions. Additionally, we design two DSSs, named Pacemaker and Tiger, that manage data andcarefully choose when and how to convert data to guarantee a target level of reliability (in spite of the variations in the failure rate of disks) without overwhelming the cluster.

The second part focuses on heterogeneity across different parts of the DSS. We consider the setting of a geo-distributed storage system, where latencies between nodes vary significantly and the cost of sending data across the wide-area network (WAN) is important. We model the problem theoretically and study the tradeoff between storage overhead and WAN bandwidth usage. Using this model, we propose a construction for codes that jointly minimize storage overhead and WAN bandwidth usage. Finally, we use this theoretical framework to design and implement a strongly-consistent geo-distributed storage system that co-optimizes its erasure code and configuration to minimize cost.

310 pages

Thesis Committee:
Rashmi Vinayak (Chair)
Gregory R. Ganger
Ryan O'Donnell
Muriel Médard (Massachusetts Institute of Technology)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu