JP6396849B2 - Generator matrix configuration apparatus and generator matrix configuration method - Google Patents

Description

  The present invention relates to a generator matrix configuration device and a generator matrix configuration method for configuring an irregular generator matrix for encoding data in a distributed storage system.

  With the recent increase in video quality and the amount of data handled by applications, the scale of storage required to provide video services has expanded, and the use of cloud storage that can optimize the scale of hardware according to demand has advanced. It is out. Storage systems are required to have high availability and long-term durability, but it is known that the reliability of multiple disk failures is reduced in a system that performs redundancy by RAID (Redundant Array of Independent Disk) due to an increase in disk capacity. (For example, refer nonpatent literature 1). Therefore, a redundancy technique for improving the reliability against a plurality of failures has been studied.

  Currently, HADOOP (registered trademark) employs a method of storing three times as many copies for ensuring redundancy. However, in order to achieve high availability by replication, it is necessary to increase the number of replicas, and the capacity efficiency of the storage is lowered, so that it is not economical to apply to a large-scale storage system. With the background of increased disk capacity and higher performance of computing resources, attention is focused on a redundancy method with high storage capacity efficiency using erasure correction codes. It is known that by applying an erasure correction code, durability and availability equivalent to duplication can be realized at a significantly lower network cost and storage cost (for example, see Non-Patent Document 2), and dispersion using an erasure correction code Storage service is provided.

  In CLEVERSAFE (registered trademark), distributed storage is made redundant by using an encoding technique based on a Reed-Solomon code (RS code) (for example, see Non-Patent Document 3). In the case of an RS code, which is a non-systematic code, data is restored by collecting k pieces of data obtained by dividing the data into k pieces and collecting k pieces of the n pieces. In this case, the storage capacity utilization efficiency is high, but the problem is that the total amount of data sent from other disks at the time of recovery of the failed disk becomes large, or the calculation amount related to recovery increases because the calculation of Galois field is required. is there. Therefore, a regenerated code (MBR code) that can minimize the amount of communication necessary for repairing the failed disk has been proposed (see, for example, Non-Patent Document 4).

  The MBR code is a code that minimizes the total amount of data that is sent to reconfigure the node in the regenerated code, and an MSR code that optimizes the utilization efficiency of storage capacity has also been proposed. However, there is a problem that the number of nodes increases in the regenerated code, and a pyramid code in which the number of helper nodes that send data at the time of disk restoration is minimized has been proposed (for example, see Non-Patent Document 5). However, since these are codes based on a dense matrix, there is a problem that the amount of calculation accompanying encoding is large.

  On the other hand, there has been proposed a Flat XOR code in which the calculation load is suppressed by encoding using an XOR operation (see, for example, Non-Patent Document 6). However, in the Flat XOR code such as HD Combination codes, the configuration of the generator matrix is limited, and the communication amount at the time of disk restoration has not been optimized. In view of this, a method has been proposed in which the communication amount is reduced by a Flat XOR code using a generation matrix having an irregular structure (see, for example, Non-Patent Document 7). However, to date, the non-regular configuration of Flat XOR code that minimizes the amount of communication is limited to a range of possible code lengths of up to several tens, and there is a problem that it cannot be applied to a storage system with a large number of distributions. .

J. et al. Resch, I. et al. Volvoski, “Reliability models for high fault-tolerant storage systems,” arXiv Computer Science Distributed, Parallel Computing, and Cluster Computing. 2013. W. Hakim, J .; D. Kubiatowitz, “Erasure coding vs. replication: a quantitative comparison,” IPTPS Proceedings, Cambridge, USA, Mar. 2002. H. Lahkar, M .; C. R, “Towards high security and fault tolerant dispersed storage system with optimized information dispersal algorithm, and“ Individual Journal of Revolution ”. 2 Issue 3, July 2014. A. G. Dimakis, P.A. B. Godfrey, Y .; Wu, M .; Wainwright, K.M. Ramchandran, “Network coding for distributed storage systems,” IEEE Trans. Information Theory, Sept. 2010. C. Huang, M .; Chen, J. et al. Li, “Pyramid codes: flexible schemes to trade space for access efficiency, Reliable data storage systems, and“ Sixth IEEE International Symposium. ” K. Greenan, X. et al. Li, W .; J. et al. J, “Flat XOR-based erase codes in storage systems: Constructions, effective recovery, and tradeoffs,” Mass Storage Systems, 10I, E. Yoshida Yui, Toshimura Yoshihide, Shirai Daisuke, Fujii Tatsuya, “Irregular composition of erasure correction codes based on Flat XOR to reduce the amount of communication for distributed storage systems,” 2014 Shingaku Sodai (Basic / Boundary) , Tokyo, Japan, Sept. 2014.

  The Flat XOR code applied to the conventional storage system does not minimize the amount of communication required for repairing the failed disk. Therefore, the amount of communication can be reduced by performing decoding using the recovery equation algorithm using a generation matrix having an irregular configuration with biased row weights.

Further, when a Flat XOR code having a code length n, a division number k, and a column weight w is configured, when a code matrix of a Flat XOR code is searched when the code length is large, k types are selected from combinations of n−k and w. A combination explosion occurs and the code cannot be determined with a feasible calculation time for a number of divisions other than k = _n−k C _w . In this case, the generation matrix of the Flat XOR code has a regular configuration in which the row weight and the column weight are constant, and a generation matrix having a non-regular configuration with a small calculation load / communication amount cannot be configured.

  Therefore, an object of the present invention is to make it possible to construct a non-regular configuration generator matrix of a Flat XOR code even with a large code length of about n = 100.

  In the present invention, 1 is regularly arranged in a partial region of the generator matrix, and the restriction of searching the remaining region is provided.

Specifically, the generator matrix construction device according to the present invention is:
A zero matrix creation unit that creates a zero matrix based on the number of data divisions and the number of disks storing data;
A predetermined row configuration unit that arranges “1” or “0” in each column of the predetermined row so that the number of “1” arranged in each column has a constant value in the predetermined row in the zero matrix;
Arranged in all rows, is the value obtained by subtracting the predetermined value from the minimum distance of the code in which the number is predetermined in the "1" to place in each column, and a "1", except for the predetermined row before Symbol zero matrix A matrix configuration unit that arranges “1” or “0” in each column of all rows except the predetermined row so that the combination of rows to be different is different for each column;
Is provided.

In the generator matrix configuration device according to the present invention, when the predetermined row is 2 or more, the matrix configuration unit arranges “1” in a plurality of columns in all rows except the predetermined row in the zero matrix. If the combination of the same, "1" is as combinations of different row disposed at the predetermined row in the column between the "1" or "0" in each column of all rows except the predetermined row You may arrange.

Specifically, the generator matrix construction device according to the present invention is:
A zero matrix creation unit that creates a zero matrix based on the number of data divisions and the number of disks storing data;
Specific row configuration in which “1” or “0” is arranged in each column of the specific one row so that the number of “1” arranged in the row is equal to or greater than a certain value in the specific row in the zero matrix And
For the column in which “1” is arranged in the specific row, the number of “1” s to be arranged in each column in all rows except the specific row in the zero matrix is a predetermined code. The value obtained by subtracting 1 from the minimum distance , and “1” or “0” in each column of all rows except the specific one row so that the combination of rows in which “1” is arranged is different for each column. Place and
Regarding the column in which “0” is arranged in the specific row, the number of “1” arranged in each column is the minimum distance of the code in all the rows except the specific row in the zero matrix. It becomes equal, and "1" so that the combination of rows to place differs for each row, and the matrix component to place "1" or "0" in each column in every row except the particular one line ,
Is provided.

In the generator matrix configuration device according to the present invention, the zero matrix has the number of columns equal to the number of data divisions , and is equal to the number of parity disks obtained by subtracting the number of data divisions from the number of disks storing data. You may have the number of rows .

Specifically, the generator matrix construction method according to the present invention is:
A generator matrix configuration method executed by a generator matrix configuration apparatus,
Creating a zero matrix based on the number of data divisions and the number of disks storing the data; and
A predetermined row configuration step of arranging “1” or “0” in each column of the predetermined row so that the number of “1” arranged in each column has a constant value in the predetermined row in the zero matrix;
Arranged in all rows, is the value obtained by subtracting the predetermined value from the minimum distance of the code in which the number is predetermined in the "1" to place in each column, and a "1", except for the predetermined row before Symbol zero matrix A matrix construction step of arranging “1” or “0” in each column of all rows except the predetermined row so that the combination of rows to be different is different for each column;
Execute.

Specifically, the generator matrix construction method according to the present invention is:
A generator matrix configuration method executed by a generator matrix configuration apparatus,
Creating a zero matrix based on the number of data divisions and the number of disks storing the data; and
Specific row configuration in which “1” or “0” is arranged in each column of the specific one row so that the number of “1” arranged in the row is equal to or greater than a certain value in the specific row in the zero matrix Steps,
For the column in which “1” is arranged in the specific row, the number of “1” s to be arranged in each column in all rows except the specific row in the zero matrix is a predetermined code. The value obtained by subtracting 1 from the minimum distance , and “1” or “0” in each column of all rows except the specific one row so that the combination of rows in which “1” is arranged is different for each column. Place and
Regarding the column in which “0” is arranged in the specific row, the number of “1” arranged in each column is the minimum distance of the code in all the rows except the specific row in the zero matrix. It becomes equal, and "1" so that the combination of rows to place differs for each column, a matrix arrangement step of placing the "1" or "0" in each column in every row except the particular one line ,
Execute.

  Since the present invention can construct a non-regular configuration generator matrix of a Flat XOR code even with a large code length of about n = 100, it is smaller than a code using a sparse matrix in a multi-point distributed storage system. Redundancy is performed with a calculation load, and the communication amount and the calculation amount at the time of disk restoration can be reduced as compared with the regular Flat XOR code and the RS code.

1 shows an outline of a code configuration device according to an embodiment. An example of the generator matrix G configured by the first configuration method is shown. An example of the generator matrix G configured by the second configuration method is shown. An example of the generator matrix G configured by the third configuration method is shown. An example of a set RE of repair formulas when I = 1 is shown. An example of selecting a row when I = 2 is shown. An example of a set RE of repair formulas when I = 2 is shown. An example of row selection when I = 3 is shown. An example of a set RE of repair formulas when I = 3 is shown. The comparison result of the average traffic of the Flat XOR code of the irregular structure which concerns on Example 1 and the Flat XOR code of the regular structure which concerns on a comparative example is shown. The comparison result of the traffic of the Flat XOR code of the irregular structure which concerns on Example 1, and RS code which concerns on a comparative example is shown. The comparison result of the XOR calculation frequency of the Flat XOR code | symbol of the irregular structure which concerns on Example 2, and RS code | cord | chord concerning a comparative example is shown. The comparison result of the average traffic of the Flat XOR code of the irregular structure which concerns on Example 2, and RS code which concerns on a comparative example is shown. 10 shows comparison results of the number of XOR calculations between a non-regular configuration Flat XOR code according to Example 3 and a regular configuration Flat XOR code according to a comparative example. The comparison result of the average traffic of the Flat XOR code of the irregular structure which concerns on Example 3, and the Flat XOR code of the regular structure which concerns on a comparative example is shown.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. In addition, this invention is not limited to embodiment shown below. These embodiments are merely examples, and the present invention can be implemented in various modifications and improvements based on the knowledge of those skilled in the art. In the present specification and drawings, the same reference numerals denote the same components.

  Since the conventional Flat XOR code needs to select a generator matrix from the number of matrices that select k types from the combination of (n−k) and w, and a combination explosion occurs when the code length is large, the possible code length Was limited. The invention according to the present embodiment makes it possible to construct a non-regular configuration generation matrix G of Flat XOR codes with a wide range of division numbers when the code length is large. As a result, the invention according to this embodiment is limited to the problem of regularly arranging 1 p in each column in a partial region of the generator matrix and placing wp 1s in the remaining region. Allows searching.

  The storage system according to the present embodiment includes an encoding device, a plurality of disks, and a decoding device. FIG. 1 shows an outline of an encoding apparatus according to this embodiment. The encoding device 10 encodes data to be made redundant. The plurality of disks 20 store data to be made redundant. A decoding device (not shown) uses the irregular generator matrix G to restore data stored in a plurality of disks.

  The encoding device 10 includes a data dividing unit 11, an encoding unit 12, and a data distribution unit 13. The data dividing unit 11 divides data to be redundant into k pieces. The encoding unit 12 encodes the data divided into k pieces using the generation matrix G having a non-regular configuration, and encodes n pieces of data including (n−k) redundant data and k pieces of data. Generate data. The data distribution unit 13 transmits the n pieces of data encoded by the encoding unit 12 to each disk 20.

  The encoding device may be realized by causing a computer to function as each functional unit. In this case, each configuration is realized by a CPU (Central Processing Unit) in the encoding apparatus executing a computer program stored in a storage unit (not shown). Although FIG. 1 shows the case where the number of disks 20 is equal to the number of encoded data to be generated, the number of disks 20 and the number of encoded data to be generated may not be the same. For example, it is conceivable to use a plurality of encoded data on each distributed disk. The disks 20 may be arranged geographically distributed and connected by a network.

(Generator matrix construction device)
The encoding unit 12 according to the present embodiment functions as a generator matrix configuration device and configures a generator matrix G having a non-regular configuration. In this embodiment, the total number of disks constituting the storage system is n equal to the code length, the number of data divisions is k, the number of parity disks is nk, and the minimum code distance is w. Let Z be a zero matrix of nk rows and k columns.

(A) First configuration method of non-regular generator matrix G in a fully searchable range When the code length n is small to some extent and k search is possible for all combinations in which k types are selected from combinations of nk and w, A zero matrix Z of k−n rows and n columns is created, and a row value corresponding to a combination searched for each column of Z is set to 1. Among the constructed matrices, a matrix capable of repairing an arbitrary f column {f = 1, 2,..., W} is set as a generation matrix G, and a generation matrix having the smallest average traffic is selected.

FIG. 2 shows an example of the generator matrix G configured by the first configuration method. The case where n = 16, k = 10, and w = 3 is shown. For each column of the generator matrix, the combination of selecting w rows from nk rows is a combination of rows in which 1 is arranged in the column. When n−k = 6 and w = 3, the number of one arrangement pattern in each column is _n−k C _{w as} shown in the figure, and there are 20 types. Since the generation matrix is configured by selecting k columns from the 20 arrangement patterns, the number of possible generation matrix candidates is ₂₀ C _k . Since k = 10, the number of possible generation matrix candidates is 184756. When f = 2, the matrix (1) and the matrix (184756) which are two generation matrix candidates among them are the generation matrix G.

(B) Second configuration method of non-regular generator matrix G in a range where full search is impossible When code length n is large, the number of k types to be selected from the combination of n−k and w becomes very large. A matrix cannot be constructed using the first construction method of the matrix G. Therefore, the generation matrix is divided into two regions, and the search range is restricted by assigning column weights, thereby forming a non-regular generation matrix. Specifically, the non-regular generator matrix G is constructed by the following procedure.

  Specifically, the encoding unit 12 includes a zero matrix creation unit that executes a zero matrix creation step, a predetermined row configuration unit that executes a predetermined row configuration step, and a matrix configuration unit that executes a matrix configuration step. . Step S101 is executed in the zero matrix creation step, steps S102 and S103 are executed in the predetermined row configuration step, and steps S104 and S105 are executed in the matrix configuration step.

  Step S101: A zero matrix Z of nk rows and k columns is created.

  For example, when n = 16, k = 10, and w = 3, the zero matrix Z has 6 rows and 10 columns as shown in FIG.

Step S102: In order to give bias to the row weights, the row weights from the first row to the x-th row are set as p, and all [x, p] satisfying Expression 1 are obtained.
(Equation 1)
_{x C p × n-k-} x C w-p ≧ k ( Equation 1)
However, x> p.

  For example, when n = 16, k = 10, and w = 3, the combinations of [x, p] are [1,1], [2,1], [4,2], [5,2], [6 , 3]. In the case of [1, 1], the first row is designated, and in the case of [2, 1], the second row is designated.

Step S103: A matrix in which 1 is arranged in the range from the first row to the x-th row of Z so as to have the column weight p is defined as Z3. _The row which becomes 1 in each column is determined by the combination of _x C _p .

For example, assume that the column weight is p = 1.
When x = 1, “1111111111” is arranged in the first row as indicated by Z31.
When x = 2, as shown in Z32, “1010101010” is arranged in the first row, and “0101010101” is arranged in the second row.

Step S104: 1 is arranged by the following method so that the column weight wp is in the range from the x + 1th row to the nk row of Z3. _In the case of nk _−xC wp ≦ k, 1 in each column in the range from the first column to the _{nk−xC wp} row by the combination of _{nk−xC wp} Place the matrix B to determine the rows _{to, r (n-k-x} C w-p) +1 row _{2r (n-k-x C} w-p) B into th column r columns {r = 1 , 2,..., X−1} and put the matrix B _r that is circulated. When the total number of Br columns exceeds k, k columns are randomly selected and arranged in the first to kth columns of Z3.

For example, if the column weight p = 1, w = 3, so the column weight w−p is 2.
When x = 1, two “1” s are arranged in each column from the second row to the sixth row as indicated by Z41.
When x = 2, as shown in Z42, two “1” s are arranged in each column from the third row to the sixth row in order from the first column. At this time, the combination in which two “1” s are arranged in each column ends in the sixth column. In this case, each column from the second row to the sixth row is different from the seventh column so that the combination of the arrangement of “1” in the first row and the second row is different from the first column to the sixth column. Two “1” s are arranged in each.

  Step S105: A matrix that can repair an arbitrary f {f = 1, 2,..., W} column in the constructed matrix is set as a generation matrix G. For example, both Z41 and Z42 are the generator matrix G.

  As described above, the non-regular generation matrix G can be configured by using the second configuration method of the generation matrix G. In the present embodiment, an example in which the “predetermined row” is the first row and the second row is shown, but the “predetermined row” may be an arbitrary row after the second row.

(C) Third Method of Constructing Non-Regular Generator Matrix G That Cannot Be Fully Searched A combination of [x, p] that satisfies the formula 1 in step S102 is [x, p] = [ In the case of only n−k, w], the number of combinations of _x C _p becomes large, and the matrix cannot be configured by the second configuration method of the generator matrix G. Therefore, the search range of the remaining n−k−1 rows is limited by configuring the row weight of the first row of the generation matrix to be equal to or greater than the average row weight, and the irregular generation matrix G is configured. Specifically, the non-regular generator matrix G is constructed by the following procedure.

  Specifically, the encoding unit 12 includes a zero matrix creation unit that executes a zero matrix creation step, a specific row configuration unit that executes a specific row configuration step, and a matrix configuration unit that executes a matrix configuration step. . Step S201 is executed in the zero matrix creation step, steps S202 and S203 are executed in the specific row configuration step, and steps S204 and S205 are executed in the matrix configuration step.

  Step S201: A zero matrix Z of nk rows and k columns is created.

  For example, when n = 16, k = 10, and w = 3, the zero matrix Z has 6 rows and 10 columns as shown in FIG.

Step S202: The average row weight E of the generator matrix is obtained by Equation 2.
(Equation 2)
E = w × k / (n−k) (Formula 2)

  For example, when n = 16, k = 10, and w = 3, E = 5.

Step S203: A matrix in which 1 column of the first row is arranged by a combination of _k C _W so that the row weight of the first row of Z becomes W {W = E + 1, E + 2,. And A set of columns in which 1 is arranged in the first row is A.

For example, when E = 5, the row weight W of the first row is W {6, 7, 8, 9, 10}.
When the row weight of the first row is W = 6, a combination of columns in which 1 is arranged in the first row is determined by _k C _w . For example, when A = {1, 2, 3, 4, 5, 6}, “1” is arranged from the first column to the sixth column of the first row as indicated by Z36. When the row weight of the first row is W = 7, a combination of columns in which 1 is arranged in the first row is determined by _k C _w . For example, when A = {1, 2, 3, 7, 8, 9, 10}, as shown in Z37, “1” is arranged from the first column to the third column of the first row, and one row “1” is arranged from the seventh column to the tenth column.

Step S204: 1 is arranged in the range from the second row of Z ′ to the nk row. The column included in A determines the row which becomes 1 by the combination of _n−k−1 C _w−1 . _{When n−k−1} C _w−1 > W, the W type is selected from the combination of n−k−1 and w−1, and each column is configured. For a column not included in A, a row that is 1 is determined by a combination of _n−k−1 C _w (FIG. 3). _{When n−k−1} C _w > k−W, k−W types are selected from combinations of n−k−1 and w to configure each column.

For example, when W = 6, as shown in Z46, “1” is arranged in the row determined by the combination of ₅ C ₂ from the first column to the sixth column included in A, and is not included in A From the seventh column to the tenth column, “1” is arranged in a row determined by the combination of ₅ C ₃ .
For example, when W = 7, as indicated by Z47, the first to third columns and the seventh to tenth columns included in A are “1” in the rows determined by the combination of ₅ C _2. And from the fourth column to the sixth column not included in A, “1” is arranged in a row determined by the combination of ₅ C ₃ .

  Step S205: A matrix that can repair an arbitrary f {f = 1, 2,..., W} column in the constructed matrix is set as a generation matrix G. For example, both Z46 and Z47 are the generator matrix G. A matrix having the smallest average traffic is selected from the generated generation matrices.

  As described above, the non-regular generation matrix G can be configured by using the third configuration method of the generation matrix G. In the present embodiment, an example in which “specific one line” is the first line is shown, but “specific one line” may be an arbitrary line after the second line.

(Decryption device)
The decoding apparatus horizontally connects a unit matrix of nk rows and nk columns to the generator matrix G to obtain a parity check matrix H.
(Equation 3)
H = [GI]

Let RE be a set of restoration formulas obtained by XOR of selected rows by selecting I {I = 1, 2,..., Nk} rows from nk rows of the parity check matrix H by the Recovery Equation Algorithm. In this embodiment, the total number of disks is n, the number of data divisions is k, the number of parity disks is nk, the minimum code distance is w, the number of simultaneous failed disks is f {f = 1, 2, 3}, Let F {F = F ₁ ,..., F _f } be a set of disks.

  FIG. 5 shows an example of a set RE of repair formulas when I = 1. In this embodiment, n = 16, k = 10, and w = 3, and the generator matrix G has 6 rows and 10 columns. In this case, a 6 × 6 unit matrix is connected horizontally to the generator matrix G.

  FIG. 6 shows an example of row selection when I = 2. FIG. 7 shows an example of a set RE of repair formulas when I = 2. When the first and second rows of the parity check matrix H are selected, as shown in the first row of FIG. 7, the parity check matrix H when I = 2 is 1 of the parity check matrix H shown in FIG. XOR for the second and second rows. Since there are 15 variations of row selection when I = 2, the parity check matrix H of I = 2 is 15 rows.

  FIG. 8 shows an example of row selection when I = 3. FIG. 9 shows an example of a set RE of repair formulas when I = 3. When the first, second and third rows of the parity check matrix H are selected, the parity check matrix H when I = 3 is 1 of the parity check matrix H shown in FIG. XOR of the second and third rows. Since there are 20 variations of row selection when I = 3, the parity check matrix H of I = 3 is 20 rows.

For f = 1, determined a set RE _F line the value of F ₁ row becomes 1 in collective RE repair type, a small line most row degree in the RE _F and repair formula F ₁ To do. For example, when the repair formula set RE is obtained as shown in FIG. 5, FIG. 7, and FIG. 9, in order to obtain the repair formula when the disk corresponding to the column 1 fails, first the value of the first column of the RE 1 = 1, 1, 2, 3 rows and I = 2 3, 4, 5, 7, 8, 9, 10, 11, 12 and I = 3 1, 8, 9, and RE _F pulled out a set of 13,14,15,16,17,18 line. Line weight of RE _F in turn is 11,5,5,8,8,8,8,8,8,8,9,8,7,7,7,9,9,9,9,9,9 Therefore, one of the second and third rows with I = 1 having the smallest row weight is set as a restoration formula. Assuming that the second row of I = 1 is a restoration formula, the columns with values of 1 are 1, 2, 3, 4 and 12, so the data of the disk corresponding to the 2nd, 3rd, 4th and 12th columns The data of the failed disk corresponding to the first column is repaired by XOR.

In the repair formula, the data of the failed disk F ₁ is repaired by XOR of the data stored in the disk corresponding to the column whose value is 1 except for the failed column F ₁ .
At this time, the value obtained by subtracting 1 corresponding to the failure column from the row weight of the restoration formula is the number of reference disks at the time of restoration, and the value obtained by subtracting 1 from the number of reference disks is the number of XORs at the time of restoration, the number of reference disks and the disk capacity. The product is the amount of communication necessary for restoration. Data stored in the failed disk is repaired by XOR calculation of the data of the disk corresponding to the row whose value is 1 in the repair formula.

For f = 2, obtains the _{F {F = F 1, F} 2} set RE _F line the value of _{F 1} row becomes 1, _{F 2} column value is 0 in the RE, most row small formula weighted and repair formula F _1. However, F ₁ and F ₂ may be interchanged. After repair the disk _{F 1,} as in the case of f = 1 obtains a repair disc _{F 2,} to repair the disk _{F 2.}

In the case of f = 3, a set of rows RE in which the value of the F _1st column of F {F = F ₁ , F ₂ , F ₃ } is 1 and the value of the F ₂ , F ₃ column is 0 in the RE. seeking _F, the most row weight small equations repair formula F _{1. However, F 1, F 2} and _{F 3} may be interchanged. After repair the disk _{F 1,} as in the case of f = 2 obtains the repair type _F 2, _{F 3,} to repair the disk _F 2, _{F 3.}

  For all combinations in which the f {f = 1, 2,..., W} disk fails among the n disks constituting the storage system, the recovery equation is obtained by the recovery equation algorithm, and decryption is performed by the Belief Propagation to restore the f disk. Calculate the average amount of traffic required.

  In addition, when one generation matrix G that minimizes the traffic is determined, it is recorded, and a repair formula is searched for in advance for each combination of failed disks, and a repair formula that minimizes the traffic is recorded. By doing so, it is possible to omit searching for a repair formula for each decoding.

[First embodiment]
As an example, an encoding method for reducing the amount of communication in the case where the number of disks n and the number of divisions k constituting the storage system are small and a combination of selecting k types from combinations of (nk) and w can be searched. Indicates.

  When redundancy is performed with the disk capacity 1 (TB), the total number of disks constituting the storage 12 ≦ n ≦ 24, the data division number 6 ≦ k ≦ 18, and the maximum simultaneous failure number w = 3, the code length n and the division number k The data is distributed and stored using the Flat XOR code having the column weight w (FIG. 1).

  A matrix with the smallest traffic is searched for in a non-regular Flat XOR code encoded using the generation matrix G configured according to the procedure of the first configuration method of the irregular generator matrix G described above (FIG. 2). ), The average communication amount weighted by the failure probability of the disk was compared with the case where the matrix having the smallest communication amount in the flat XOR code of the regular configuration was used.

  FIG. 10 shows a comparison result of the average communication amount with the flat XOR code having a regular configuration according to the present embodiment. The vertical axis represents the ratio of the average communication amount measured using the non-regular configuration Flat XOR code according to the present embodiment to the average communication amount measured using the regular configuration Flat XOR code. When the non-regular Flat XOR code according to the present embodiment is used, data can be protected with a smaller communication amount at any code length n.

  Further, FIG. 11 shows a comparison result of the traffic when the RS code is used. The vertical axis indicates the ratio of the average traffic volume measured using the Flat XOR code of the irregular configuration according to this embodiment to the average traffic volume measured using the Reed-Solomon code. When the non-regular Flat XOR code according to the present embodiment is used, data can be protected with a smaller communication amount at any code length n.

[Second Embodiment]
Compared with RS code in a storage system that distributes and stores data at multiple points, where the number of disks n and the number of partitions k are large and it is not possible to search for all combinations in which k types are selected from the combinations of (n−k) and w Thus, an encoding method for reducing the communication amount will be described.

  When redundancy is performed with the disk capacity 1 (TB), the total number of disks constituting the storage 36 ≦ n ≦ 116, the data division number 20 ≦ k ≦ 100, and the maximum simultaneous failure number w = 3, the code length n and the division number k The data is distributed and stored using the Flat XOR code having the column weight w (FIG. 1).

  For each of the non-regular configuration Flat XOR code encoded using the generation matrix G configured according to the procedure of the second configuration method of the non-regular generation matrix G and the RS code, the number of failed disks f Each time, the average communication traffic weighted by the number of XOR calculations required for repair and the failure probability of the disk was calculated and compared.

  FIG. 12 shows a comparison result of the number of XOR calculations with the RS code. The vertical axis represents the ratio of the average number of XOR calculations when the non-regular configuration Flat XOR code according to the present embodiment is used to the average number of XOR calculations when the RS code is used.

  FIG. 13 shows a comparison result of the average traffic with the RS code. The vertical axis represents the ratio of the average traffic measured using the Flat XOR code of the irregular configuration according to the present embodiment to the average traffic measured using the RS code.

  As shown in FIGS. 12 and 13, it is understood that data can be protected with a smaller number of XOR calculations and communication traffic when using a code with a non-regular configuration.

[Third embodiment]
In a storage system in which data is distributed and stored at multiple points, the regular number of flats is used in the case where the number of disks n and the number of divisions k are large and it is impossible to search for all combinations in which k types are selected from the combinations of (n−k) and w. An encoding method for reducing the communication amount as compared with the XOR code will be described.

When redundancy is performed with the disk capacity 1 (TB), the total number of disks 26 ≦ n ≦ 130, the data division number 18 ≦ k ≦ 113, and the maximum simultaneous failure number w = 3, the code length n, the division number k, and the column weight w The non-regular configuration Flat XOR code is configured according to the procedure of the second configuration method of the non-regular configuration generator matrix G. At this time, the generation matrix of the flat XOR code having the regular configuration is determined in one way with the division number k = _n−k C _w .

In the case of using a non-regular configuration generator matrix G and a regular configuration generation matrix G of k = _n−k C _w , the average communication amount weighted by the number of XOR calculations necessary for repairing the f disk and the failure probability of the disk Compared.

  FIG. 14 shows a comparison result of the number of XOR calculations with a regular configuration Flat XOR code. The vertical axis indicates the ratio of the average number of XOR calculations when the non-regular configuration Flat XOR code according to the present embodiment is used to the average number of XOR calculations when the regular configuration Flat XOR code is used.

  FIG. 15 shows a comparison result of the average communication amount with the flat XOR code having a regular configuration. The vertical axis represents the ratio of the average communication amount measured using the non-regular configuration Flat XOR code according to the present embodiment to the average communication amount measured using the regular configuration Flat XOR code.

  As shown in FIGS. 14 and 15, by using a code with a non-regular configuration, data can be protected with a smaller number of XOR calculations and a smaller traffic than a code with a regular configuration when the code length is the same.

  As described above, by using the Flat XOR code encoded using the non-regular configuration generator matrix G according to the present embodiment, compared with the RS code and the regular Flat XOR code, the communication amount at the time of failure disk repair and A code that reduces the computational load can be configured. In addition, since the irregular code can be configured with a wide range of division numbers when the code length is up to about 100, where the irregular Flat XOR code could not be applied conventionally, the calculation load is suppressed in a storage system with a large number of distributions. The erasure correction code can be applied.

  In the present embodiment, an example in which the Flat XOR code is used in the encoding has been described. However, the present invention can be applied to any encoding using a generation matrix G having a non-regular configuration. For example, the present invention can also be applied to other systematic codes that can be encoded by XOR based on a sparse graph and decoded by Recovery Equation Algorithm. As such a systematic code, for example, an LDPC (Low Density Parity Check) code can be exemplified.

  The present invention can be applied to the information communication industry.

10: Encoding device 11: Data dividing unit 12: Encoding unit 13: Data distributing unit 20: Disk

Claims (6)

A zero matrix creation unit that creates a zero matrix based on the number of data divisions and the number of disks storing data;
A predetermined row configuration unit that arranges “1” or “0” in each column of the predetermined row so that the number of “1” arranged in each column has a constant value in the predetermined row in the zero matrix;
Arranged in all rows, is the value obtained by subtracting the predetermined value from the minimum distance of the code in which the number is predetermined in the "1" to place in each column, and a "1", except for the predetermined row before Symbol zero matrix A matrix configuration unit that arranges “1” or “0” in each column of all rows except the predetermined row so that the combination of rows to be different is different for each column;
A generator matrix construction device comprising: When the predetermined row is 2 or more,
When the matrix configuration unit has the same combination of rows in which “1” is arranged in a plurality of columns in all rows except the predetermined row in the zero matrix, “1” in the predetermined row between the columns. Arrange “1” or “0” in each column of all rows except the predetermined row so that the combinations of the rows in which are arranged are different.
The generator matrix construction device according to claim 1. A zero matrix creation unit that creates a zero matrix based on the number of data divisions and the number of disks storing data;
Specific row configuration in which “1” or “0” is arranged in each column of the specific one row so that the number of “1” arranged in the row is equal to or greater than a certain value in the specific row in the zero matrix And
For the column in which “1” is arranged in the specific row, the number of “1” s to be arranged in each column in all rows except the specific row in the zero matrix is a predetermined code. The value obtained by subtracting 1 from the minimum distance , and “1” or “0” in each column of all rows except the specific one row so that the combination of rows in which “1” is arranged is different for each column. Place and
Regarding the column in which “0” is arranged in the specific row, the number of “1” arranged in each column is the minimum distance of the code in all the rows except the specific row in the zero matrix. It becomes equal, and "1" so that the combination of rows to place differs for each row, and the matrix component to place "1" or "0" in each column in every row except the particular one line ,
A generator matrix construction device comprising: The zero matrix, have equal number of columns to the number of divided data, and has a number of rows equal to the number of parity disks obtained from the number of disks for storing data by subtracting the number of divisions of the data, claims 1 to 3 The generator matrix construction device according to any one of the above. A generator matrix configuration method executed by a generator matrix configuration apparatus,
Creating a zero matrix based on the number of data divisions and the number of disks storing the data; and
A predetermined row configuration step of arranging “1” or “0” in each column of the predetermined row so that the number of “1” arranged in each column has a constant value in the predetermined row in the zero matrix;
Arranged in all rows, is the value obtained by subtracting the predetermined value from the minimum distance of the code in which the number is predetermined in the "1" to place in each column, and a "1", except for the predetermined row before Symbol zero matrix A matrix construction step of arranging “1” or “0” in each column of all rows except the predetermined row so that the combination of rows to be different is different for each column;
A generator matrix construction method for executing A generator matrix configuration method executed by a generator matrix configuration apparatus,
Creating a zero matrix based on the number of data divisions and the number of disks storing the data; and
Specific row configuration in which “1” or “0” is arranged in each column of the specific one row so that the number of “1” arranged in the row is equal to or greater than a certain value in the specific row in the zero matrix Steps,
For the column in which “1” is arranged in the specific row, the number of “1” s to be arranged in each column in all rows except the specific row in the zero matrix is a predetermined code. The value obtained by subtracting 1 from the minimum distance , and “1” or “0” in each column of all rows except the specific one row so that the combination of rows in which “1” is arranged is different for each column. Place and
Regarding the column in which “0” is arranged in the specific row, the number of “1” arranged in each column is the minimum distance of the code in all the rows except the specific row in the zero matrix. It becomes equal, and "1" so that the combination of rows to place differs for each column, a matrix arrangement step of placing the "1" or "0" in each column in every row except the particular one line ,
A generator matrix construction method for executing

Images