Erasure Coding for Cloud Storage

As more and more data moves to the cloud, data replication has become prohibitively costly and there is an acute need for efficient, fault-tolerant schemes for data storage. Coding theory offers solutions for fault-tolerant storage that are potentially far more efficient than replication. At the same time, the cloud storage setting presents some unique challenges that traditional error-correcting codes do not handle. There have been some novel solution concepts proposed to address these challenges (such as Regenerating Codes and Locally Repairable Codes).

In this talk we will describe the challenges, both theoretical and practical, in designing efficient erasure coding schemes for cloud storage. Our case study will be Locally Repairable Codes, or LRCs, that were first deployed by Azure Storage in 2012, resulting in tremendous savings in hardware costs, and have since been deployed in other Microsoft products. These codes are inspired by Locally Testable and Locally Decodable codes from theoretical computer science, and provide efficient recovery (independent of the code length) for typical failure scenarios.

This talk is based on joint work with collaborators from MSR and the Azure storage team. No prior background will be assumed.

Speaker: Parikshit Gopalan, Microsoft