Improving the Update Complexity of Locally Repairable Linear Block Codes in Distributed Storage Systems

Abstract

Distributed and cloud storage systems are used to reliably store large-scale data. Erasure codes have been recently proposed and used in real-world distributed and cloud storage systems such as Google File System, Microsoft Azure Storage, and Facebook HDFS-RAID, for reliable data storage. Conventional erasure codes, however, are not suitable for distributed storage systems, as they cause significant repair bandwidth and disk I/O. As a solution, a class of erasure codes called locally repairable codes (LRCs) have been proposed. Using LRCs repairing a failed storage nodes requires access to only a small number of available nodes. This property of LRCs results in a relatively low bandwidth and disk I/O operations for repairing a failed node. In this thesis, we study update complexity of LRCs. Update complexity of an erasure code is a measure of the computation, I/O and networking costs associated with updating an information block in a distributed storage system. LRCs with low update complexities are desirable. In this thesis, we derive lower bounds on update complexity of an important class of LRCs. Then, we propose a new set of LRCs, and, using the bound, we show that our designed codes have either optimal or near-optimal update complexities. Interestingly, our proposed codes improve update complexity without sacrificing important code parameters such as minimum distance, rate, or locality.