## 5 Efficient Data Recovery Method
### Matrix Recycle  
The decoding task that recovers lost data in EC is performed in the following order: data acquisition \(\rightarrow\) decoding matrix creation \(\rightarrow\) decoding process. Data acquisition refers to a step to read available data required for decoding. Decoding matrix creation refers to a step to create a decoding matrix required for decoding according to the EC setup and fault location. Finally, decoding refers to a step to perform decoding using the acquired data and decoding matrix. In particular, the required number of matrices for decoding differs according to EC attributes, such as EC, number of data divisions, number of created parities, and fault location and number. For example, if a single disk fault occurs in EC with four data cells and two parity cells in the EC-based HDFS using a single volume, the required number of matrices for decoding is six. Figure 16: Examples of sequential (**left**) and random (**right**) block placement disk fault. In Figure 17, cells D1 to D4 are data cells and P1 and P2 are parity cells. The red color indicates the fault location, and a total of six decoding matrices are required according to the fault location in a single fault. Table 3 presents the number of matrices occurring during multiple faults according to the K + M value. As presented in Table 3, as the K + M value increases, the number of used matrices increases. In particular, as the number of data divisions increases, the number of matrices increases exponentially. Thus, as the used EC volumes are various and the number of fault tolerances increases, the required number of decoding matrices increases. However, with the same fault attributes, the used matrices are the same. For example, for the same EC and the same fault index in multiple volumes with a 4 + 2 attribute, the used matrices are the same. That is, if the number of data divisions, the number of parities, erasure code, and stripe size are the same, even if the volume is different in the EC structure, then the used matrices are the same for the fault in the same location. Thus, this study minimizes the time to create matrices for decoding by recycling the matrices if the same fault attributes are found after registering the created matrices in the pool. Figure 18 shows the overall data structure used to recycle matrices. Figure 19 shows the data structure comprising the matrix. struct matrix_pool, which represents the overall structure, has struct ec_table consisting of encoding information and ma  
Figure 17: Case where matrices differ in a single fault. \begin{table}
\begin{tabular}{c c c} \hline \hline
**EC K + M Volume** & **M = 1** & **M = 2** \\ \hline K = 2 & 3 & 6 \\ K = 4 & 5 & 15 \\ K = 8 & 9 & 45 \\ K = 16 & 17 & 153 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Number of matrices required for decoding according to EC attributes. Figure 18: Data structure to compose the matrix. trix. struct ec_table contains struct dc_table consisting of decoding information and matrix, which are related to the corresponding encoding information. struct matrix_pool consists of ec_tables_count, which represents the number of ec_table, and ec_tables, which represent the list of ec_tables. In struct ec_table, the number of data divisions (ec_k), the number of parities (ec_m), the EC type to be used (ec_type), the striping size (ec_striping_size), and the encode matrix (ec_matrix) are required information for encoding, and the number of dc_tables (dc_tables_count) and the list of dc_tables (dc_tables) are decoding-related information. struct dc_table stores information and matrix required for decoding, which consists of information to check the fault location (err_hash) and related decoding matrix (dc_matrix). err_hash value in dc_table is a hash value calculated based on the fault count and location, which is used to identify whether the fault occurs in the same location. Figure 19 shows the matrix recycle step. When decoding is requested, ec_table, whose ec_k, ec_m, ec_type, and ec_stripe_size are the same in matrix_pool, is searched.