BDCode: An erasure code algorithm for big data storage systems

doi:10.3969/j.issn.0253-2778.2016.03.003

Abstract

Abstract: An optimized algorithm, based on erasure coding technology towards the big data storage system that contains a lot of data, was proposed. By studying existing coding technologies and big data systems, this algorithm, named BDCode (big data code) can not only protect system reliability, but also improve the security and the utilization of storage space. Due to the high reliability and space saving rate of coding technology, coding mechanisms were introduced into big data systems. The storage nodes are divided into many virtual nodes to realize load balancing. By setting different virtual nodes’ storage groups for different codec servers , ensure system availability. And by using the parallel decoding computing of the nodes and the block of data, we can be ensured the recovery efficiency of the system can be proved when data is corrupted. Additionally, different users setting different coding parameters can improve the robustness of big data storage systems. We configured various data block m and calibration block k to improve the utilization rate in the quantitative experiments. The results show that parallel decoding speed can be nearly two times faster than the past serial decoding speed. The encoding efficiency with BDCode coding is， on average, 36.1% higher than using CRS and 58.2% higer than using RS coding. The decoding rate by using BDCode averages 19.3% higher than using CRS and 33.1% higher than using RS.

Key words: distributed storage system, erasure coding, big data, robustness, availability, cloud storage

CLC Number:

TP311

YIN Chao, WANG Jianzong, LV Haitao, CUI Zongmin, CHENG Lianglun, LI Tongfang, LIU Yan. BDCode: An erasure code algorithm for big data storage systems[J]. Journal of University of Science and Technology of China, 2016, 46(3): 188-199.

References

［1］
MORRIS R J T, TRUSKOWSKI B J. The evolution of storage systems[J]. IBM Systems Journal, 2003, 42(2): 205-217.
[2] WANG Y, KAPRITSOS M, REN Z, et al. Robustness in the Salus scalable block store[C]// Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation. Lombard, USA: ACM Press, 2013: 357-370.
[3] LI Y, DHOTRE N, OHARA Y, et al. Horus: Fine-grained encryption-based security for large-scale storage[C]// Proceedings of the 11th USENIX Conference on File and Storage Systems. San Jose, USA: IEEE Press, 2013: 147-160.
[4] TIWARI D, BOBOILA S, VAZHKUDAI S S, et al. Active flash: Towards energy-efficient, in-situ data analytics on extreme-scale machines[C]// Proceedings of the 11th USENIX Conference on File and Storage Systems. San Jose, USA: IEEE Press, 2013: 119-132.
[5] WILKES J, GOLDING R, STAELIN C, et al. The HP AutoRAID hierarchical storage system[J]. ACM Transactions on Computer System, 1996, 14(1): 108-136.
[6] GHEMAWAT S, GOBIOFF H, LEUNG S T. File and storage systems: The Google file system[C]// Proceedings of the 9th ACM Symposium on Operating Systems Principles. Bolton Landing, USA: IEEE Press, 2003: 29-43.
[7] SHVACHKO K, KUANG H, RADIA S, et al. The Hadoop distributed file system[C]// Proceedings of Symposium on Mass Storage Systems & Technologies. Incline Village, USA: IEEE Press, 2010: 1-10.
[8] Amazon simple storage service (S3)[EB/OL]. http://www.amazon.com/s3.
[9] WEIL S A, BRANDT S A, MILLER E L, et al. Ceph: A scalable, high-performance distributed file system[C]// Proceedings of the 7th Conference on Operating Systems Design and Implementation. Seattle, USA: ACM Press, 2006: 307-320.
[10] BLOMER J, KALFANE M, KARP R, et al. An XOR-based erasure-resilient coding scheme[R]. Technical Report TR-95-048, International Computer Science Institute, 1995.
[11] PLANK J S. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems[J]. Software-Practice & Experience, 1997, 27(9): 995-1012.
[12] STOICA I, MORRIS R, KARGER D, et al. Chord: A scalable peer-to-peer lookup service for Internet applications[J]. Proceedings of the ACM SIGCOMM Computer Communication Review, 2001, 31(4): 149-160.
[13] Meister D, Brinkmann A. dedupv1: Improving deduplication throughput using solid state drives (SSD)[C]// Proceedings of the 26th Symposium on Mass Storage systems and Technology. Incline Village, NV: IEEE, 2010: 1-6.
[14] XIA M Y, SAXENA M, BLAUM M et al. A tale of two erasure codes in HDFS[C]// Proceedings of the 13th USENIX Conference on File and Storage Technologies. Santa Clara, USA: ACM Press, 2015: 213-226.
[15] FAN B, TANTISIRIROJ W, XIAO L, et al. Diskreduce: RAID for data-intensive scalable computing[C]// Proceedings of the 4th Annual Workshop on Petatascale Data Storage. Portlang, USA: ACM Press, 2009: 6-10.
[16] VENKATARAMANI V, AMSDEN Z, BRONSON N, Get al. Tao: How Facebook serves the social graph[C]// Proceedings of the ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2012: 791-792.
[17] NISHTALA R, FUGAL H, GRIMM S, et al. Scaling memcache at Facebook[C]// Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, USA: ACM Press, 2013: 385-398.
[18] Google-GFS2 Colossus [EB/OL]. http://www.quora.com/Colossus-Google- GFS2" Google, 2012.
[19] TAMO I, BARG A. A family of optimal locally recoverable codes[J]. IEEE Transactions on Information Theory , 2014, 60(8): 4661-4676.
[20] FENG G L, DENG R H, BAO F, et al. New efficient MDS array codes for RAID part I: Reed-Solomon-like codes for tolerating three disk failures[J]. IEEE Transactions on Computers, 2005, 54(9):1071-1080.
[21] HAFNER J L. WEAVER Codes: Highly fault tolerant erasure codes for storage systems[C]// Proceedings of the 4th USENIX Conference on File and Storage Technology. San Francisco, USA: ACM Press, 2005: 211-224.
[22] HAFNER J L. HoVer erasure codes for disk arrays[C]// International Conference on Dependable Systems and Networks. Philadelphia, USA: IEEE Press, 2006: 217-226.
[23] XU L H, BRUCK J. X-Code: MDS array codes with optimal encoding[J]. IEEE Transactions on Information Theory, 1999, 45(1): 272-276.
[24] YIN C, XIE C S, WAN J G, et al. BMCloud: Minimizing repair bandwidth and maintenance cost in cloud storage[J]. Mathematical Problems in Engineering, 2013, 2013(6): 1-11.
[25] RASHMI K V, NAKKIRAN P, WANG J Y, et al. Having your cake and eating it too: Jointly optimal erasure codes for I/O, storage, and network-bandwidth[C]// Proceedings of the 13th USENIX Conference on File and Storage Technologies. Santa Clara, USA: ACM Press, 2015: 81-94.
[26] STRZELCZAK P, ADAMCZYK E, HERMAN-IZYCKA U, et al. Concurrent Deletion in a Distributed Content-Addressable Storage System with Global Deduplication[C]// Proceedings of the 11th USENIX Conference on File and Storage Technologies. 2013: 161-174.
[27] FU M, FENG D, HUA Y, et al. Design Tradeoffs for data deduplication performance in backup workloads[C]// Proceedings of the 13th USENIX Conference on File and Storage Technologies. Santa Clara, USA: ACM Press, 2015: 331-344.
[28] REED I S, SOLOMON G. Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics, 1960, 8(2): 300-304.

()
()

[1]	Ling Huaze, Xue Kaiping, Wei David S.L., Li Ruidong. An efficient multi-user multi-keyword fuzzy search scheme over encrypted cloud storage [J]. Journal of University of Science and Technology of China, 2021, 51(7): 562-576.
[2]	Guo Shiwei, Wang Zhanfeng, Wu Yaohua. A manifold extended t-process regression [J]. Journal of University of Science and Technology of China, 2021, 51(5): 382-389.
[3]	HU Wanbao, HU Shuai, CHEN Wenwen, CUI Liangwu. Repairing multiple failures for algebraic geometry codes [J]. Journal of University of Science and Technology of China, 2020, 50(2): 140-145.
[4]	QIU Zhen, WANG Qiyuan, LIU Di, MENG Hongmin. A novel method for mining latent events based on scalable patterns [J]. Journal of University of Science and Technology of China, 2019, 49(7): 524-532.
[5]	CUI Wenquan, YU Demei, CHENG Haoyang. A non-iterative approach to kernel logistic regression for imbalanced data [J]. Journal of University of Science and Technology of China, 2019, 49(12): 965-973.
[6]	ZENG Weihui, LI Miao, ZHANG Jian, HUANG Xiaoping, WANG Jingxian, YUAN Yuan. Research on high-order residual convolution neural network for crop disease recognition application [J]. Journal of University of Science and Technology of China, 2019, 49(10): 781-790.
[7]	WANG Yongshuai, CHEN Zengqiang, SUN Mingwei, SUN Qinglin. Robust stability of reduced-order linear ADRC for first-order plants with large time-delay [J]. Journal of University of Science and Technology of China, 2019, 49(1): 55-62.
[8]	CHEN Feng, ZHANG Zhi, LI Qinjian, CHEN Yuqiang, CHEN Guoliang. Dynamic task scheduling algorithm of parallel computing for FCD big data [J]. Journal of University of Science and Technology of China, 2018, 48(9): 718-722.
[9]	CHEN Zhizhu, WANG Hongzhi, XIONG Feng, ZHANG Yice, GAO Hong, LI Jianzhong. Research on the auction strategies and pricing of big data [J]. Journal of University of Science and Technology of China, 2018, 48(6): 486-494.
[10]	WANG Jiayu, ZHANG Zhenyu, CHU Zheng, WU Xiaohong. A trajectory data density partition based distributed parallel clustering method [J]. Journal of University of Science and Technology of China, 2018, 48(1): 47-56.
[11]	XU Ziwei, WANG Peng, CHEN Zonghai. A two-stage feature selection method based on Fisher’s ratio and prediction risk for telecom customer churn prediction [J]. Journal of University of Science and Technology of China, 2017, 47(8): 686-694.
[12]	CHEN Zhenguo, TIAN Liqin, LIN Chuang. Data reliable assurance model of Internet of Things based on the trust evaluation of perceived source [J]. Journal of University of Science and Technology of China, 2017, 47(4): 297-303.
[13]	BU Yao, WU Bin, CHEN Yufeng, BAI Demeng. BDAP: A data mining platform based on Spark [J]. Journal of University of Science and Technology of China, 2017, 47(4): 358-368.
[14]	LI Huakang, LIU Pan, YANG Yitao, SUN Guozi. A cloud storage access scheme with security proxy based on attribute mapping node [J]. Journal of University of Science and Technology of China, 2017, 47(4): 304-310.
[15]	ZHANG Jingjing,YANG Yan*,WANG Hongjun, HAN Xiaotao,DENG Qiang. A novel voting method and parallel implementation for soft clustering [J]. Journal of University of Science and Technology of China, 2016, 46(3): 173-179.