We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 33 Issue 6
November  2018
Turn off MathJax
Article Contents
Abstract
References
Supplements
Quan-Qing Xu, Wei-Ya Xi, Khai Leong Yong, Chao Jin. CRL: Efficient Concurrent Regeneration Codes with Local Reconstruction in Geo-Distributed Storage Systems[J]. Journal of Computer Science and Technology, 2018, 33(6): 1140-1151. DOI: 10.1007/s11390-018-1877-5
Citation: Quan-Qing Xu, Wei-Ya Xi, Khai Leong Yong, Chao Jin. CRL: Efficient Concurrent Regeneration Codes with Local Reconstruction in Geo-Distributed Storage Systems[J]. Journal of Computer Science and Technology, 2018, 33(6): 1140-1151. DOI: 10.1007/s11390-018-1877-5
shu

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

  • 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

More Information
  • Author Bio:

    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.

  • Received Date: July 19, 2017
  • Revised Date: September 10, 2018
  • Published Date: November 14, 2018
    Abstract
  • 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.
    • FullText(HTML)
    • References (21)
  • [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.
    • Relative Articles
  • Supplements (1)

  • Others

Catalog

    Get Citation
    PDF
    XML
    Article views (18) PDF downloads (509) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return