Distributed Data Storage Systems

Recent years have witnessed an incredible amount of user-generated content through applications such as social networks, blogs and multimedia-sharing services. The key challenge that research community as well as Industry is facing is to design a cost efficient storage system to cope with this data explosion. A Distributed Storage System (DSS) formed, by networking together a large number of, inexpensive and unreliable, storage devices provides one such alternative to store such a massive amount of data with high reliability and ubiquitous availability. Numerous examples of platforms that follow this principle exist today e.g., DHT, GFS, Hadoop etc.

In DSS individual disks being inexpensive are prone to failures. A high fault tolerance is achieved through redundancy either in the form of multiple ‘replicas’ or ‘coded packets’.

Can classical ‘Erasure Codes’ provide reliability in DSS? Although distributed storage systems have benefited largely from the past research in the area of coding for communication channels, there are several key aspects of a networked storage system that are not addressed in the classical coding theory. These nuances offer new challenges and exciting opportunities to system designers.

Repair: In a DSS, node failures result in loss of redundancy. In order to restore the state of high reliability and availability of data in the system, we need to add a new node and populate it with the lost redundancy, i.e., ‘Repair’.

A toy example of a repair efficient DSS code is shown in the video above.

We have also performed measurements from Facebook's Warehouse cluster about the (adverse) effects of using classical erasure codes on the network.

Challenges posed by repair in designing DSS: 1.Repair bandwidth: Amount of data downloaded to repair one unit of data. 2.Disk access: Number of disks accessed to repair one disk. 3.Readseek: Amount of data read for repair from each disk. 4.Computational Complexity for the repair process.

ScalingGrowth: In a DSS different files can have different popularity demands. An important question with this regard is, how to design a DSS that can scale in distributive fashion based on the popularity of files?

We address some of the issues mentioned above in the following works.

Publications

Journal

1. N. B. Shah, K. V. Rashmi, P. V. Kumar and K. Ramchandran, ‘‘Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions,” IEEE Transactions on Information Theory, April 2012.

2. N. B. Shah, K. V. Rashmi, P. V. Kumar and K. Ramchandran, ‘‘Distributed Storage Codes with Repair-by-Transfer and Non-achievability of Interior Points on the Storage-Bandwidth Tradeoff ,” accepted for publication in the IEEE Transactions on Information Theory, March 2012.

3. A. G. Dimakis, K. Ramchandran, Y. Wu, C. Suh, “A Survey on Network Codes for Distributed Storage,” Proceedings of the IEEE, vol. 99, March 2011.

4. C. Suh, K. Ramchandran, “Exact-Repair MDS Code Construction Using Interference Alignment,” IEEE Transactions of Information Theory, vol. 57, pp.1425-1442, March 2011.

5. A. G. Dimakis, P. B. Godfrey, Y. Wu, M. Wainwright and K. Ramchandran, ‘‘Network Coding for Distributed Storage Systems,” IEEE Transactions on Information Theory, vol. 56, pp. 4539-4551, 2010.

Conference

1. K. V. Rashmi, Nihar B. Shah, Dikang Gu, Hairong Kuang, Dhruba Borthakur, and Kannan Ramchandran, "A Solution to the Network Challenges of Data Recovery in Erasure-coded Distributed Storage Systems: A Study on the Facebook Warehouse Cluster,’’ USENIX HotStorage, San Jose, June 2013.

2. K. V. Rashmi, Nihar B. Shah and Kannan Ramchandran, “A Piggybacking Design Framework for Read-and Download-efficient Distributed Storage Codes,” IEEE International Symposium on Information Theory (ISIT), Istanbul, Jul. 2013.

3. K. V. Rashmi, Nihar B. Shah, Kannan Ramchandran, and P. Vijay Kumar, “Regenerating Codes for Errors and Erasures in Distributed Storage,” IEEE International Symposium on Information Theory (ISIT), Cambridge, Jul. 2012.

4. S. El Rouayheb and K. Ramchandran, ‘‘Fractional Repetition Codes for Repair in Distributed Storage Systems,” in the Proceedings of Allerton Conference on Communication, Control and Computation, 2010.

5. K. V. Rashmi, N. B. Shah, P. V. Kumar, K. Ramchandran, “Explicit and Optimal Exact-Regenerating Codes for the Minimum-Bandwidth Point in Distributed Storage,” in IEEE International Symposium on Information Theory (ISIT), 2010.

6. C. Suh and K. Ramchandran, ‘‘Exact-repair MDS codes for distributed storage using interference alignment,” in IEEE International Symposium on Information Theory (ISIT), 2010.

7. K. V. Rashmi, N. B. Shah, P. V. Kumar and K. Ramchandran, “ Explicit and Optimal Codes for Distributed Storage (invited),” Proc. IEEE Information Theory and Applications (ITA) Workshop, Feb. 2010.

8. K. V. Rashmi, N. B. Shah, P. V. Kumar and K. Ramchandran, ‘‘Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage,’’ in the Proceedings of Allerton Conference on Communication, Control and Computation, 2009.

9. Y. Wu, A.G. Dimakis, K. Ramchandran, ‘‘Deterministic regenerating codes for distributed storage,” in the Proceedings of Allerton Conference on Communication, Control and Computation, 2007(Invited).

10. A. G. Dimakis, P. B. Godfrey, M. J. Wainwright and K. Ramchandran, ‘‘Network Coding for Distributed Storage Systems,” IEEE Conference on Computer Communications. (INFOCOM), May 2007.

Preprints

1. C. Suh and K. Ramchandran, ‘‘On the existence of optimal exact-repair MDS codes for distributed storage,” submitted to the IEEE Transactions on Information Theory, May 2010 (arXiv: 1004.4663).