This survey paper focuses on erasure coding techniques utilized on distributed storage systems such as RAID. There is a specific emphasis on Reed-Solomon codes due to their ubiquity within distributed storage systems. Advances in coding techniques have substantial impacts on the cost and performance of storage systems. Several methods of utilizing Reed-Solomon codes are examined for their various efficiencies in computational complexity.
References
[1] U. S. D. of Commerce, “U.S. Census Bureau News- Quarterly Retail E-Commerce Sales 2nd Quarter 2021,” U.S. Department of Commerce, type, August 19, 2021.
[2] R. W. Hamming, “Error detecting and error correcting codes,” The Bell System Technical Journal, vol. 29, no. 2, pp. 147–160, 1950, doi: 10.1002/j.1538-7305.1950.tb00463.x.
[3] P. Ruan et al., Blockchains vs. Distributed Databases: Dichotomy and Fusion. 2021.
[4] M. Xia, M. Saxena, M. Blaum, and D. A. Pease, “A Tale of Two Erasure Codes in HDFS,” in 13th USENIX Conference on File and Storage Technologies (FAST 15), Feb. 2015, pp. 213–226. [Online]. Available: [here]
[5] M. Blaum, J. Brady, J. Bruck, and J. Menon, “EVENODD: An Optimal Scheme for Tolerating Double Disk Failures in RAID Architectures,” SIGARCH Comput. Archit. News, vol. 22, no. 2, pp. 245–254, Apr. 1994, doi: 10.1145/192007.192033.
[6] I. S. Reed and G. Solomon, “Polynomial Codes Over Certain Finite Fields,” Journal of the Society for Industrial and Applied Mathematics, vol. 8, no. 2, pp. 300–304, 1960, [Online]. Available: [here]
[7] J. S. Plank, “A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems,” Software – Practice & Experience, vol. 27, no. 9, pp. 995–1012, Sep. 1997.
[8] J. Blomer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, and D. Zuckerman, “An XOR-Based Erasure-Resilient Coding Scheme,” Oct. 1999.
[9] F. Mattoussi, V. Roca, and B. Sayadi, “Complexity comparison of the use of Vandermonde versus Hankel matrices to build systematic MDS Reed-Solomon codes,” in 2012 IEEE 13th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), 2012, pp. 344–348. doi: 10.1109/SPAWC.2012.6292924.
[10] J. S. Plank and M. Blaum, “Sector-Disk (SD) Erasure Codes for Mixed Failure Modes in RAID Systems,” ACM Transactions on Storage, vol. 10, no. 1, Jan. 2014, doi: 10.1145/2560013.
[11] J. S. Plank, K. M. Greenan, and E. L. Miller, “Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions,” Feb. 2013.
[12] J. S. Plank and C. Huang, Tutorial: Erasure Coding for Storage Applications. San Jose: Slides presented at FAST-2013: 11th Usenix Conference on File and Storage Technologies, 2013.
[13] Q. Liu, D. Feng, J. Hong, Y. Hu, and T. Jiao, “Z Codes: General Systematic Erasure Codes with Optimal Repair Bandwidth and Storage for Distributed Storage Systems,” in 2015 IEEE 34th Symposium on Reliable Distributed Systems (SRDS), 2015, pp. 212–217. doi: 10.1109/SRDS.2015.18.
[14] A. Fikes, “Storage Architecture and Challenges,” 2010.
[15] Dikang Gu Peter Knowles and G. J. Chen, Saving capacity with HDFS RAID. 2014.
[16] C. Huang et al., “Erasure Coding in Windows azure storage,” Jun. 2012, USENIX ATC 2012 (Winner of the Best Paper Award). [Online]. Available: [here]
[17] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The Google File System,” in Proceedings of the 19th ACM Symposium on Operating Systems Principles, 2003, pp. 20–43.
[18] “Rethinking Erasure Codes for Cloud File Systems: Minimizing I/O for Recovery and Degraded Reads,” Feb. 2012. [Online]. Available: [here]
[19] O. 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 Proceedings of the 10th USENIX Conference on File and Storage Technologies, 2012, p. 20.
[20] K. Rashmi, P. Nakkiran, J. Wang, N. B. Shah, and K. Ramchandran, “Having Your Cake and Eating It Too: Jointly Optimal Erasure Codes for I/O, Storage, and Network-bandwidth,” in 13th USENIX Conference on File and Storage Technologies (FAST 15), Feb. 2015, pp. 81–94. [Online]. Available: [here]
[21] I. Tamo and A. Barg, “A Family of Optimal Locally Recoverable Codes,” IEEE Transactions on Information Theory, vol. 60, no. 8, pp. 4661–4676, 2014, doi: 10.1109/TIT.2014.2321280.
[22] A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, “A Survey on Network Codes for Distributed Storage,” Proceedings of the IEEE, vol. 99, no. 3, pp. 476–489, 2011, doi: 10.1109/JPROC.2010.2096170.
[23] N. Tang and Y. Lin, “Fast Encoding and Decoding Algorithms for Arbitrary (n,k) Reed-Solomon Codes Over \mathbbF2^m ,” IEEE Communications Letters, vol. 24, no. 4, pp. 716–719, 2020, doi: 10.1109/LCOMM.2020.2965453.
[24] J. S. Plank and L. Xu, “Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Network Storage Applications,” in Fifth IEEE International Symposium on Network Computing and Applications (NCA’06), 2006, pp. 173–180. doi: 10.1109/NCA.2006.43.
Leave a Reply