CaCo: An Efficient Cauchy Coding Approach for Cloud Storage Systems
- 1 May 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 65 (2) , 435-447
Abstract
Users of cloud storage usually assign different redundancy configurations (i.e., $(k,m,w)$ ) of erasure codes, depending on the desired balance between performance and fault tolerance. Our study finds that with very low probability, one coding scheme chosen by rules of thumb, for a given redundancy configuration, performs best. In this paper, we propose CaCo, an efficient Cauchy coding approach for data storage in the cloud. First, CaCo uses Cauchy matrix heuristics to produce a matrix set. Second, for each matrix in this set, CaCo uses XOR schedule heuristics to generate a series of schedules. Finally, CaCo selects the shortest one from all the produced schedules. In such a way, CaCo has the ability to identify an optimal coding scheme, within the capability of the current state of the art, for an arbitrary given redundancy configuration. By leverage of CaCo's nature of ease to parallelize, we boost significantly the performance of the selection process with abundant computational resources in the cloud. We implement CaCo in the Hadoop distributed file system and evaluate its performance by comparing with “Hadoop-EC” developed by Microsoft research. Our experimental results indicate that CaCo can obtain an optimal coding scheme within acceptable time. Furthermore, CaCo outperforms Hadoop-EC by 26.68-40.18 percent in the encoding time and by 38.4-52.83 percent in the decoding time simultaneously.
Keywords
Funding Information
- National Natural Science Foundation of China (61170008, 61272055, 61433008, U1435216)
- National Grand Fundamental Research 973 Program of China (2014CB340402)
- National High Technology Research and Development Program of China (2013AA01A210)
This publication has 25 references indexed in Scilit:
- Optimal recovery of single disk failure in RDP code storage systemsACM SIGMETRICS Performance Evaluation Review, 2010
- Flat XOR-based erasure codes in storage systems: Constructions, efficient recovery, and tradeoffs2010
- T-Code: 3-Erasure Longest Lowest-Density MDS CodesIEEE Journal on Selected Areas in Communications, 2010
- Toward optimizing cauchy matrix for cauchy reed-solomon codeIEEE Communications Letters, 2009
- P-Code2009
- An efficient XOR-scheduling algorithm for erasure codes encoding2009
- X-code: MDS array codes with optimal encodingIEEE Transactions on Information Theory, 1999
- A high-performance, portable implementation of the MPI message passing interface standardParallel Computing, 1996
- EVENODD: an efficient scheme for tolerating double disk failures in RAID architecturesIEEE Transactions on Computers, 1995
- Polynomial Codes Over Certain Finite FieldsJournal of the Society for Industrial and Applied Mathematics, 1960