Journal of Computer Science and Technology ›› 2018, Vol. 33 ›› Issue (6): 1140-1151.doi: 10.1007/s11390-018-1877-5

Special Issue: Computer Architecture and Systems

• Computer Networks and Distributed Computing • Previous Articles     Next Articles

CRL: Efficient Concurrent Regeneration Codes with Local Reconstruction in Geo-Distributed Storage Systems

Quan-Qing Xu1, Senior Member, IEEE, Member, CCF, ACM, Wei-Ya Xi2, Khai Leong Yong2, Chao Jin3   

  1. 1. Institute of High Performance Computing, Agency for Science, Technology and Research, Singapore 138632, Singapore;
    2. Data Storage Institute, Agency for Science, Technology and Research, Singapore 138632, Singapore;
    3. Institute for Infocomm Research, Agency for Science, Technology and Research, Singapore 138632, Singapore
  • Received:2017-07-20 Revised:2018-09-11 Online:2018-11-15 Published:2018-11-15
  • About author:Quan-Qing Xu received his Ph.D. degree in computer science from Peking University, Beijing, in 2009. He obtained the award of Excellent Ph.D. Graduate because of his excellent performance at Peking University, Beijing. He is a research scientist at Institute of High Performance Computing (IHPC), Agency for Science, Technology and Research (A*STAR), Singapore. He received Best Paper Award at Data Storage Institute in 2013 and Best Paper Award of MUE-15 in 2015. His research interests mainly include blockchain, Internet of Things, distributed systems, and cloud storage. He is a senior member of IEEE, and a member of CCF and ACM.

As a typical erasure coding choice, Reed-Solomon (RS) codes have such high repair cost that there is a penalty for high reliability and storage efficiency, thereby they are not suitable in geo-distributed storage systems. We present a novel family of concurrent regeneration codes with local reconstruction (CRL) in this paper. The CRL codes enjoy three benefits. Firstly, they are able to minimize the network bandwidth for node repair. Secondly, they can reduce the number of accessed nodes by calculating parities from a subset of data chunks and using an implied parity chunk. Thirdly, they are faster than existing erasure codes for reconstruction in geo-distributed storage systems. In addition, we demonstrate how the CRL codes overcome the limitations of the Reed Solomon codes. We also illustrate analytically that they are excellent in the trade-off between chunk locality and minimum distance. Furthermore, we present theoretical analysis including latency analysis and reliability analysis for the CRL codes. By using quantity comparisons, we prove that CRL(6, 2, 2) is only 0.657x of Azure LRC(6, 2, 2), where there are six data chunks, two global parities, and two local parities, and CRL(10, 4, 2) is only 0.656x of HDFS-Xorbas(10, 4, 2), where there are 10 data chunks, four local parities, and two global parities respectively, in terms of data reconstruction times. Our experimental results show the performance of CRL by conducting performance evaluations in both two kinds of environments:1) it is at least 57.25% and 66.85% more than its competitors in terms of encoding and decoding throughputs in memory, and 2) it has at least 1.46x and 1.21x higher encoding and decoding throughputs than its competitors in JBOD (Just a Bunch Of Disks). We also illustrate that CRL is 28.79% and 30.19% more than LRC on encoding and decoding throughputs in a geo-distributed environment.

Key words: concurrent regeneration code; local reconstruction; geo-distributed storage system;

[1] Sathiamoorthy M, Asteris M, Papailiopoulos D S, Dimakis A G, Vadali R, Chen S, Borthakur D. XORing elephants:Novel erasure codes for big data. Proceedings of the VLDB Endowment, 2013, 6(5):325-336.
[2] Rashmi K V, Shah N B, Gu D, Kuang H, Borthakur D, Ramchandran K. A "hitchhiker's" guide to fast and efficient data reconstruction in erasure-coded data centers. In Proc. the 2014 ACM Conference on SIGCOMM, Aug. 2014, pp.331-342.
[3] Huang C, Simitci H, Xu Y, Ogus A, Calder B, Gopalan P, Li J, Yekhanin S. Erasure coding in windows Azure storage. In Proc. the 2012 USENIX Annual Technical Conference, Jun. 2012, pp.15-26.
[4] Qin A, Hu D M, Liu J, Yang W J, Tan D. Fatman:Building reliable archival storage based on low-cost volunteer resources. Journal of Computer Science and Technology, 2015, 30(2):273-282.
[5] Xu Q, Arumugam R V, Yong K L, Mahadevan S. Efficient and scalable metadata management in EB-scale file systems. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(11):2840-2850.
[6] Xu Q, Xi W, Yong K L, Jin C. Concurrent regeneration code with local reconstruction in distributed storage systems. In Advanced Multimedia and Ubiquitous Engineering, Park J J, Chao H C, Arabnia H, Yen N Y (eds.), Springer Berlin Heidelberg, 2016, pp.415-422.
[7] Dimakis A G, Godfrey B, Wu Y, Wainwright M J, Ramchandran K. Network coding for distributed storage systems. IEEE Transactions on Information Theory, 2010, 56(9):4539-4551.
[8] Gopalan P, Huang C, Simitci H, Yekhanin S. On the locality of codeword symbols. IEEE Trans. Information Theory, 2012, 58(11):6925-6934.
[9] Wu Y, Dimakis A G. Reducing repair traffic for erasure coding-based storage via interference alignment. In Proc. the 2009 IEEE International Symposium on Information Theory (ISIT), Jun. 2009, pp.2276-2280.
[10] Cook J D, Primmer R, de Kwant A. Compare cost and performance of replication and erasure coding. Hitachi Review, 2014, 63:304-310.
[11] Aslam C A, Guan Y L, Cai K. Edge-based dynamic scheduling for belief-propagation decoding of LDPC and RS codes. IEEE Trans. Communications, 2017, 65(2):525-535.
[12] Ford D, Labelle F, Popovici F I, Stokely M, Truong V, Barroso L, Grimes C, Quinlan S. Availability in globally distributed storage systems. In Proc. the 9th USENIX Symposium on Operating Systems Design and Implementation, Oct. 2010, pp.61-74.
[13] Weatherspoon H, Kubiatowicz J. Erasure coding vs. replication:A quantitative comparison. In Proc. the 1st International Workshop on Peer-to-Peer Systems, Mar. 2002, pp.328-338.
[14] Tian J, Yang Z, Dai Y. A data placement scheme with timerelated model for P2P storages. In Proc. the 7th IEEE International Conference on Peer-to-Peer Computing, Sept. 2007, pp.151-158.
[15] Huang Z, Jiang H, Zhou K, Wang C, Zhao Y. XI-code:A family of practical lowest density MDS array codes of distance 4. IEEE Trans. Communications, 2016, 64(7):2707-2718.
[16] Dimakis A G, Ramchandran K, Wu Y, Suh C. A survey on network codes for distributed storage. Proceedings of the IEEE, 2011, 99(3):476-489.
[17] Kermarrec A, Scouarnec N L, Straub G. Repairing multiple failures with coordinated and adaptive regenerating codes. In Proc. the 2011 International Symposium on Networking Coding, Jul. 2011.
[18] Shum K W, Hu Y. Exact minimum-repair-bandwidth cooperative regenerating codes for distributed storage systems. In Proc. the 2011 IEEE International Symposium on Information Theory Proceedings, Jul. 2011, pp.1442-1446.
[19] Li M, Lee P P C. STAIR codes:A general family of erasure codes for tolerating device and sector failures. ACM Transactions on Storage, 2014, 10(4):Article No. 14.
[20] Liu Q, Feng D, Hu Y, Shi Z, Fu M. High performance general functional regenerating codes with near-optimal repair bandwidth. ACM Transactions on Storage, 2017, 13(2):Article No. 15.
[21] Xu Q, Ng H W, Xi W, Jin C. Effective local reconstruction codes based on regeneration for large-scale storage systems. In Proc. the 2018 Future of Information and Communication Conference, Apr. 2018, pp.501-507.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved