# EC-Kad: An Efficient Data Redundancy Scheme for Cloud Storage
## 3 Cloud Storage System Model Based on Erasure Code
### Data Encoding Storage and Recovery  
Erasure coding is for encoding the original data file into a data stream (including multiple coded data blocks), and the original data file is obtained after the receiver reconstructs the minimum required number of data blocks they obtained. The loss of encoded data blocks during transmission is independent of each of them. The cloud storage system based on erasure codes is shown in Figure 2 below.  
Figure 1: A simple cloud storage system model.  
For the data file \(F\), the erasure code is performed first, and then the encoded data blocks are distributed to each storage node n, as shown in Figure 2. If one of the four storage nodes fails and does not work, the minimum number of data blocks can be taken from the remaining storage nodes for decoding, thereby obtaining the data file f required by the terminal node. At the same time, the data block on the normal storage node can be encoded to recover the data block on the error node or transfer to other storage nodes.  
In order to ensure high availability of data and low consumption of storage space, we need to adjust the redundancy factor when erasing the code. If the redundancy factor is too large, then the storage space will be consumed excessively, and if the redundancy factor is too small, then the availability will be reduced.  
The \(k\) original data blocks are encoded to generate \(k+m\) data blocks, and then the \(k+m\) data blocks are stored on multiple storage nodes in the cloud storage system, where \(m\) of them are redundant data blocks but have fault tolerance capability and \(k\) data blocks have the function of restoring data; that is, for any data block no more than \(m\) that is lost, these \(k\) data blocks can restore them to the original data. The encoder is implemented through the multiplication operation of the generating matrix (\(C\)) and vector group (\(F\)). Here, \(C\) is a matrix of \(k+m\) rows and \(K\) columns, and \(F(F_{1},F_{2},F_{3},\ldots,F_{k})\) is a vector group composed of original data blocks of the same size.  
The linear operation of the finite field is the core operation of the encoder, and thus constructing the finite field is the first step in the encoding process. Taking the finite field \(GF(2^{w})\) as an example, \(w\) is the word length, and the numerical value can be selected according to the size of the data block. Each element in the finite field can be represented as a \(w\)-bit binary number. For this, \(w=8\) is commonly used in storage systems, corresponding to 1 byte of data, and \(GF(2^{w})\) has 256 elements in all. Then, we can construct an irreducible polynomial of a degree \(w\). For example, in \(GF(2^{w})\), a commonly used polynomial is \(x^{8}+x^{4}+x^{3}+x^{2}+1\). Each element in the field \(GF(2^{w})\) is represented by a polynomial with a degree less than \(w\) (e.g., \(w=8\)), and the coefficients are either zero or one. For instance, the element 0\(XFF\) corresponds to the polynomial \(x^{7}+x^{6}+\ldots+x+1\), while the element 0X03 corresponds to the polynomial \(x+1\). When performing element operations, the rules are as follows. Addition is performed by adding the polynomial coefficients of bitwise modulo 2 (XOR operation). Multiplication involves polynomial multiplication followed by reduction modulo for an irreducible polynomial to simplify the result.  
For construction of the encoder, a Cauchy matrix [36] is used as the source matrix of the generation matrix. The Cauchy matrix has good properties over the finite fields, ensuring  
Figure 2: Cloud storage model based on erasure codes.  
that the generated encoding matrix has maximum reversibility and can efficiently recover the original data during decoding. The specific implementation process is as follows.