Research On Erasure Codes For Distributed Secure Storage System

The rapid expansion of the Internet and the increasingly wide of informationtechnology,the demand for data storage becomes higher and higher.Disk capac-ity is not able to meet the demand of people's daily needs.This demands thatthe reliability storage system with connection ways between storage devices isprovided for all kinds of users. Distributed storage technology is a good methodto solve the problems of decentralization of storage devices,Parallel I/O,high e?-ciency of protocol.But as the number of severs increases,the chance of losing dataunacceptably increases.Loss of data can occur due to sever being down,humanmistakes,a network connection being faulty, accidental data erasure, maliciousintentional physical file destruction or the nature disasters. Proper data redun-dancy is necessary to ensure data availability and high reliability for distributedstorage systems.Proper data placements based on erasure codes are one of the most impor-tant components for a highly available data storage system. It becomes an urgenttask how to design erasure codes with good erasure recover, very e?cient lineartime encoding and erasure recover algorithms for distributed storage systems withhigh reliability and availability. This dissertation systematically investigates era-sure codes in distributed storage system. The author' s novel viewpoints andbreakthroughs are presented in this dissertation. The main achievements con-tained in this dissertation are as follows:1. Three types of erasure codes in distributed storage systems are systemat-ically researched. Array erasure codes,Reed Solomon(RS) codes,Low-Density Parity-Check(LDPC) codes are mainly introduced.Aiming at dif-ferent encoding properties and combination with structures and propertiesin distributed storage system, the principles for erasures codes and someconsiderations of proper data placements in distributed storage systems aregiven.2. A class of new binary Maximum Distance Separable (MDS) array codescalled V Codes is proposed , V Codes are have perfect properties:(i)a sim-ple geometrical structure ,allowing simple erasure-decoding and error-decoding algorithms.(ii)MDS property, A rigorous theoretical prove ofminimum column distance 3 is given. (iii)optimal encoding prop-erty ,i.e..the number of the parity bits that are a?ect by change of a singleinformation bit is minimal. (iiii)optimal length and optimal decod-ing, fast decoding algorithms of single burst column error and double col-umn erasure errors are presented. And V codes,EVENODD codes, ReedSolomon (RS) codes, are compared and analyzed.3. Based on Blaum codes,a new class of e?cient array codes for multi-ple data columns failures is introduced,which is an extension of thegeneralized EVENODD code and called (m + p,m)XEOD codes.An al-gebraic representation and a simple geometrical structureof the(m + p,m)XEOD codes are described. The encoding properties are ana-lyzed.4. Based on the XEOD codes' algebraic representation,it is proven that the(m+3,m)XEOD codes are of minimum column distance 4,i.e.,MDSproperty. By introducing eliminant functions,a very fast and simple de-coding procedure of recovering up to 3 data column losses is presented, and it has the lowest complexity among all known schemes. And ane?cient decoding algorithm of recovering up to 4 data column lossesfor array codes in (m+4,m)XEOD codes and in (m+5,m)XEOD codesis proposed,A rigorous theoretical prove of the decoding algorithm basedon eliminant functions is given. The decoding algorithm of recovering upto p data column losses in (m + p,m)XEOD codes is shown.5. The distribution matrix based on Vandermonde matrices is analyzed,a classof optimizing Vandermonde binary array codes is given. And a method toevaluating good matrices is proposed,The performance of encoding usingall manners of Vandermonde codes is optimal. the original Vandermondecodes are improved.6. According to the encoding performance of three new array codes,typicalapplications in distributed storage systems are discussed. V codes,XEODcodes,optimizing Vandermonde binary array codes can be used e?ectivelyto achieve the reliability and e?cient of distributed storage systems...