A Distributed Storage Algorithm Based on Cauchy RS Code

Abstract:

Data fault tolerance is a key technology in the field of distributed storage. In this paper, an algorithm to encode massive amounts of data and then distribute storage these data on each node in the data center is proposed, aiming at coping with the serious challenges in the protection of data fault tolerance. The method converts multiplication operation in Cauchy RS coding into a binary multiplication through the transition on bit operation, so that the entire operation on RS encoding is converted to an operation containing only simple XOR operator. The experiment proves that the method is better than the copy and the original RS coding in the data encoding efficiency. Furthermore, it saves the storage space and promotes the application of erasure codes strongly in distributed storage field.

• Periodical: Applied Mechanics and Materials (Volumes 336-338)
• Pages: 2188-2194
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.336-338.2188
• Online since: July 2013
• Authors: Xing Gao, Min Li, Juan Juan Huang, Bing Chang Liu
• Keywords: Cauchy RS Encoding, Distributed Storage, Fault Tolerance

References

[1] Dean J. Experiences with MapReduce, an abstraction for large-scale computation. In: Proc. of the PACT 2006. Seattle: ACM Press, 2006. 16−20.

[2] Rizzo L. Effective erasure codes for reliable computer communication protocols. Computer Communication Review, 1997, 27(2): 24− 36.

DOI: 10.1145/263876.263881

[3] J. Plank and L. Xu, Optimizing Cauchy Reed-Solomon codes for fault-tolerant network storage applications, IEEE International Symposium on Network Computing and Applications, (2006).

DOI: 10.1109/nca.2006.43

[4] James S. Plank. A Tutorial on Reed–Solomon Coding for Fault-Tolerance in RAID-like Systems [J]. SOFTWARE—PRACTICE AND EXPERIENCE, SEPTEMBER 1997, VOL. 27(9), 995–1012.

DOI: 10.1002/(sici)1097-024x(199709)27:9<995::aid-spe111>3.0.co;2-6

[5] Reed I S, Solomon G. Polynomial codes over certain finite fields [J]. Journal of Society for Industrial and Applied Mathematics, 1960, 8(2): 300-304.

DOI: 10.1137/0108018

[6] Mu Jianjun, Lu Chengye, Wang Xinmei. About The Research and Progress On Erasure code[J]. Journal of Electronics & Information Technology, 2002, 09: 1276-1281.

[7] Roth R M. Lempel A. On MDS codes via Cauchy matrices [J]. IEEE Trans on Information Theory, 1989, 35(6): 1212-1319.

DOI: 10.1109/18.45291

[8] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1977, Chapter 11.

[9] J. Plank. Y. Ding. Note: Correction to the 1997 tutorial on Reed-Solomon Coding [J]. Software & Practice Experience, February 2005. 35(2): 189-194.

DOI: 10.1002/spe.631

[10] J. Plank, Luo J, Schuman C, et al. A performance evaluation and examination of open-source erasure coding library for storage [C]. Proc of the 7th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2009: 253-266.

[11] Xiangxue Li, Qingji Zheng, Haifeng Qian, Dong Zheng, Jianhua L, Toward optimizing cauchy matrix for cauchy reed-solomon code, Communications Letters, IEEE , vol. 13, no. 8, pp.603-605, August (2009).

DOI: 10.1109/lcomm.2009.090988

[12] Khan, R. Burns, J. Plank, W. Pierce, and C. Huang, Rethinking Erasure Codes for Cloud File Systems: Minimizing I/O for Recovery and Degraded Reads, in FAST, (2012).