Storage controller, data processing chip, and data processing method

• US 10,210,044 B2
• Filed: 05/11/2018
• Issued: 02/19/2019
• Est. Priority Date: 12/24/2016
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Zeng, Yanxing, Shen, Jianqiang, Wang, Gongyi, Zhang, Jinyi, Lv, Wen
• Primary Examiner(s): Bryan, Jason B
• Application Number:
  US15/977,794
• Publication Number:
  US 20180260276A1
• Time in Patent Office: 284 Days
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: G11C 29/88 with partially good memories
• CPC Class Codes: H03M 13/11 using multiple parity bits
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes

Abstract

This application discloses a storage controller. When running, the storage controller encodes, according to a check matrix, K to-be-coded data chunks obtained from a client, to generate two check chunks. In this way, if any chunk is damaged subsequently, the damaged chunk may be recovered by using the check matrix and an undamaged chunk.

Claims

1. A first storage controller, comprising:

a processor; and

a non-transitory memory;

wherein the first storage controller is comprised in a storage system, the storage system comprises at least one storage device, a first storage device of the at least one storage device comprises the first storage controller and a first storage medium, each storage device of the at least one storage device comprised in the storage system comprises a storage controller and a storage medium, and each storage device of the at least one storage device comprised in the storage system is configured to connect with any other storage device comprised in the storage system;

wherein the processor is configured to execute a program in the non-transitory memory to;

receive to-be-written data;

divide the to-be-written data into K to-be-coded data chunks, wherein each data chunk of the K to-be-coded data chunks comprises R data code blocks, (R+1) is a prime number, and (R+1)>

K;

generate a first check chunk and a second check chunk according to a check matrix and the K to-be-coded data chunks, wherein each of the first check chunk and the second check chunk respectively comprises R check code blocks;

create a chunk group, wherein the chunk group comprises the K to-be-coded data chunks, the first check chunk, and the second check chunk; and

store each data chunk in the chunk group into the first storage medium, and store each check chunk in the chunk group into a second storage medium;

wherein the check matrix comprises 2*R rows and (K+2)*R columns, each column of the check matrix corresponds to one code block, each row of the check matrix corresponds to one exclusive OR equation the (K*R+1)^th column to the ((K+1)*R)^th column of the check matrix form a chunk column set of the first check chunk, and the ((K+1)*R+1)^th column to the ((K+2)*R)^th column of the check matrix form a chunk column set of the second check chunk;

wherein the check matrix is a standard check matrix H, or the check matrix is obtained after N exchange operations are performed on the standard check matrix H, wherein N≥

1, and the N exchange operations are each an exchange of any two chunk column sets;

wherein, for each value of i and each value of j, coordinates in the standard check matrix H corresponding to the following first relations are set to be 1;

when i<

j,

H[i+1][j*R+(R−

j+i)mod R+1], and

H[R+i+1][(j+1)*R−

(R−

j+i)mod R];

or

when i>

j,

H[i+1][j*R+(R−

1−

j+i)mod R+1], and

H[R+i+1][(j+1)*R−

(R−

1−

j+i)mod R]; and

wherein 2*R≥

i≥

1, (K+2)*R≥

j≥

1, and coordinates in the in the standard check matrix H that do not correspond to the first relations are set to be o.

2. The first storage controller according to claim 1, wherein the ((k−

1)*R+1)^th column to the (k*R)^th column of the check matrix form a chunk column set of the k^th data chunk in the K to-be-coded data chunks, wherein K≥

k≥

1, the ((k−

1)*R+1)^th column to the (k*R)^th column of the check matrix respectively correspond to the R data code blocks of the k^th data chunk in the K to-be-coded data chunks, the (K*R+1)^th column to the ((K+1)*R)^th column of the check matrix respectively correspond to the R check code blocks of the first check chunk, and the ((K+1)*R+1)^th column to the ((K+2)*R)^th column of the check matrix respectively correspond to the R check code blocks of the second check chunk; and

wherein there are three coordinates of 1 in a D^th row of the check matrix, wherein the D^th row is any row of the check matrix, and an exclusive OR operation is performed on any two of three code blocks corresponding to the coordinates of 1 in the D^th row of the check matrix, based on the OR equation of the D^th row, to obtain a code block that does not participate in this exclusive OR operation and that is in the three code blocks corresponding to the coordinates of 1 in the D^th row of the check matrix.

3. The first storage controller according to claim 1, wherein the processor is further configured to separately store the K to-be-coded data chunks, the first check chunk, and the second check chunk into K+2 storage media in the storage system in which the first storage controller is located.

4. The first storage controller according to claim 3, wherein the processor is further configured to:

when a storage medium in the (K+2) storage media is damaged, recover the damaged storage medium according to the check matrix, a data chunk that is stored on an undamaged storage medium in the (K+2) storage media, and the first check chunk or the second check chunk.

10. The first storage controller according to claim 1, the step of dividing comprises:

when a quantity of received to-be-written data reaches a preset value, divide the to-be-written data into K to-be-coded data chunks.

5. A data processing chip, comprising:

a circuit; and

an interface, configured to perform read and write operations;

wherein the data processing chip is comprised in a storage system, the storage system comprises at least one storage device, a first storage device of the at least one storage device comprises a first storage controller and a first storage medium, the first storage controller comprises the data processing chip, and each storage device of the at least one storage device comprised in the storage system comprises a storage controller and a storage medium;

wherein the circuit is configured to;

receive to-be-written data;

divide the to-be-written data into K to-be-coded data chunks, wherein each data chunk of the K to-be-coded data chunks comprises R data code blocks, (R+1) is a prime number, and (R+1)>

K;

generate a first check chunk and a second check chunk based on a check matrix and the K to-be-coded data chunks, wherein each of the first check chunk and the second check chunk respectively comprises R check code blocks;

create a chunk group, wherein the chunk group comprises the K data chunks, the first check chunk, and the second check chunk; and

store each data chunk in the chunk group into the first storage medium, and store each check chunk into a second storage medium;

wherein the check matrix comprises 2*R rows and (K+2)*R columns, each column of the check matrix corresponds to one code block, and each row of the check matrix corresponds to one exclusive OR equation, and wherein the (K*R+1)^th column to the ((K+1)*R)^th column of the check matrix form a chunk column set of the first check chunk, and the ((K+1)*R+1)^th column to the ((K+2)*R)^th column of the check matrix form a chunk column set of the second check chunk;

wherein the check matrix is a standard check matrix H, or the check matrix is obtained after N exchange operations are performed on the standard check matrix H, wherein N≥

1, and each of the N exchange operations is an exchange of any two chunk column sets;

wherein, for each value of i and each value of j, coordinates in the standard check matrix H corresponding to the following first relations are set to be 1;

when i<

j,

H[i+1][j*R+(R−

j+i)mod R+1], and

H[R+i+1][(j+1)*R−

(R−

j+i)mod R];

or

when i>

j,

H[i+1][j*R+(R−

1−

j+i)mod R+1], and

H[R+i+1][(j+1)*R−

(R−

1−

j+i)mod R]; and

wherein 2*R≥

i≥

1, (K+2)*R≥

j≥

1, and coordinates in the in the standard check matrix H that do not correspond to the first relations are set to be o.

6. The data processing chip according to claim 5, wherein the ((k−

1)*R+1)^th column to the (k*R)^th column of the check matrix form a chunk column set of the k^th data chunk in the K to-be-coded data chunks, wherein K≥

k≥

1, the ((k−

1)*R+1)^th column to the (k*R)^th column of the check matrix respectively correspond to the R data code blocks of the k^th data chunk in the K to-be-coded data chunks, the (K*R+1)^th column to the ((K+1)*R)^th column of the check matrix respectively correspond to the R check code blocks of the first check chunk, and the ((K+1)*R+1)^th column to the ((K+2)*R)^th column of the check matrix respectively correspond to the R check code blocks of the second check chunk; and

wherein there are three coordinates of 1 in a D^th row of the check matrix, wherein the D^th row is any row of the check matrix, and the circuit performs an exclusive OR operation on any two of three code blocks corresponding to the coordinates of 1 in the D^th row of the check matrix, based on the XOR equation of the D^th row to obtain a code block that does not participate in this exclusive OR operation and that is in the three code blocks corresponding to the coordinates of 1 in the D^th row of the check matrix.

7. The data processing chip according to claim 5, wherein the circuit is further configured to store the K to-be-coded data chunks, the first check chunk, and the second check chunk into a memory in the first storage controller, so that the first storage controller separately stores the K to-be-coded data chunks, the first check chunk, and the second check chunk into K+2 storage media in the storage system in which the first storage controller is located.

8. The data processing chip according to claim 7, wherein the circuit is further configured to:

when a storage medium in the (K+2) storage media is damaged, recover the damaged storage medium according to the check matrix, a data chunk that is stored on an undamaged storage medium in the (K+2) storage media, and the first check chunk or the second check chunk.

9. The data processing chip according to claim 5, wherein the data processing chip comprises a field-programmable gate array (FPGA).

11. A method comprising:

receiving, by a first storage controller, to-be-written data, wherein the first storage controller is comprised in a storage system, the storage system comprises at least one storage device, a first storage device of the at least one storage device comprises the first storage controller and a first storage medium, each storage device of the at least one storage device comprised in the storage system comprises a storage controller and a storage medium, and each storage device of the at least one storage device comprised in the storage system is configured to connect with any other storage device comprised in the storage system;

dividing, by the first storage controller, the to-be-written data into K to-be-coded data chunks wherein each data chunk of the K to-be-coded data chunks comprises R data code blocks, (R+1) is a prime number, and (R+1)>

K;

generating, by the first storage controller, a first check chunk and a second check chunk according to a check matrix and the K to-be-coded data chunks, wherein each of the first check chunk and the second check chunk respectively comprises R check code blocks;

creating, by the first storage controller, a chunk group, wherein the chunk group comprises the K to-be-coded data chunks, the first check chunk, and the second check chunk; and

storing, by the first storage controller, each data chunk in the chunk group into the first storage medium, and storing, by the first storage controller, each check chunk in the chunk group into a second storage medium;

wherein the check matrix comprises 2*R rows and (K+2)*R columns, each column of the check matrix corresponds to one code block, and each row of the check matrix corresponds to one exclusive OR equation, and wherein the (K*R+1)^th column to the ((K+1)*R)^th column of the check matrix form a chunk column set of the first check chunk, and the ((K+1)*R+1)^th column to the ((K+2)*R)^th column of the check matrix form a chunk column set of the second check chunk;

wherein the check matrix is a standard check matrix H, or the check matrix is obtained after N exchange operations are performed on a standard check matrix H, wherein N≥

1, and each of the N exchange operations is an exchange of any two chunk column sets;

wherein, for each value of i and each value of j, coordinates in the standard check matrix H corresponding to the following first relations are set to be 1;

when i<

j,

H[i+1][j*R+(R−

j+i)mod R+1], and

H[R+i+1][(j+1)*R−

(R−

j+i)mod R];

or

when i>

j,

H[i+1][j*R+(R−

1−

j+i)mod R+1], and

H[R+i+1][(j+1)*R−

(R−

1−

j+i)mod R]; and

wherein 2*R≥

i≥

1, (K+2)*R≥

j≥

1, and coordinates in the in the standard check matrix H that do not correspond to the first relations are set to be o.

12. The method according to claim 11, wherein the ((k−

1)*R+1)^th column to the (k*R)^th column of the check matrix form a chunk column set of the k^th data chunk in the K to-be-coded data chunks, wherein K≥

k≥

1, the ((k−

1)*R+1)^th column to the (k*R)^th column of the check matrix respectively correspond to the R data code blocks of the k^th data chunk in the K to-be-coded data chunks, the (K*R+1)^th column to the ((K+1)*R)^th column of the check matrix respectively correspond to the R check code blocks of the first check chunk, and the ((K+1)*R+1)^th column to the ((K+2)*R)^th column of the check matrix respectively correspond to the R check code blocks of the second check chunk; and

wherein there are three coordinates of 1 in a D^th row of the check matrix, wherein the D^th row is any row of the check matrix, and an exclusive OR operation is performed on any two of three code blocks corresponding to the coordinates of 1 in the D^th row of the check matrix, based on the OR equation of the D^th row, to obtain a code block that does not participate in this exclusive OR operation and that is in the three code blocks corresponding to the coordinates of 1 in the D^th row of the check matrix.

13. The method according to claim 11, further comprising:

separately storing the K to-be-stored data chunks, the first check chunk, and the second check chunk into (K+2) storage media in the storage system in which the first storage controller is located.

14. The method according to claim 13, further comprising:

when a storage medium in the (K+2) storage media is damaged, recovering the damaged storage medium according to the check matrix, a data chunk that is stored on an undamaged storage medium in the (K+2) storage media, and the first check chunk or the second check chunk.

15. The method according to claim 11, wherein the dividing comprises:

when a quantity of received to-be-written data reaches a preset value, divide the to-be-written data into K to-be-coded data chunks.

16. A non-transitory computer-readable storage medium comprising instructions which, when executed by a first computer, cause the computer to:

receive to-be-written data;

divide the to-be-written data into K to-be-coded data chunks, wherein each data chunk of the K to-be-coded data chunks comprises R data code blocks, (R+1) is a prime number, and (R+1)>

K;

generate a first check chunk and a second check chunk according to a check matrix and the K to-be-coded data chunks, wherein each of the first check chunk and the second check chunk comprises R check code blocks;

create a chunk group, wherein the chunk group comprises the K to-be-coded data chunks, the first check chunk, and the second check chunk; and

store each data chunk in the chunk group into a first storage medium, and store each check chunk in the chunk group into a second storage medium;

wherein the first computer is comprised in a storage system, the storage system comprises at least one computer including the first computer, each computer comprises a storage controller and a storage medium, the first computer comprises a first storage controller and the first storage medium, and each computer comprised in the storage system is configured to connect with any other computer comprised in the storage system;

wherein the check matrix comprises 2*R rows and (K+2)*R columns, each column of the check matrix corresponds to one code block, and each row of the check matrix corresponds to one exclusive OR equation, and wherein the (K*R+1)^th column to the ((K+1)*R)^th column of the check matrix form a chunk column set of the first check chunk, and the ((K+1)*R+1)^th column to the ((K+2)*R)^th column of the check matrix form a chunk column set of the second check chunk; and

the check matrix is a standard check matrix H, or the check matrix is obtained after N exchange operations are performed on a standard check matrix H, wherein N≥

1, and each of the N exchange operations is an exchange of any two chunk column sets; and

wherein, for each value of i and each value of j, coordinates in the standard check matrix H corresponding to the following first relations are set to be 1;

when i<

j,

H[i+1][j*R+(R−

j+i)mod R+1], and

H[R+i+1][(j+1)*R−

(R−

j+i)mod R];

or

when i>

j,

H[i+1][j*R+(R−

1−

j+i)mod R+1], and

H[R+i+1][(j+1)*R−

(R−

1−

j+i)mod R]; and

wherein 2*R≥

i≥

1, (K+2)*R≥

j≥

1, and coordinates in the in the standard check matrix H that do not correspond to the first relations are set to be o.

17. The non-transitory computer-readable storage medium according to claim 16, wherein the ((k−

1)*R+1)^th column to the (k*R)^th column of the check matrix form a chunk column set of the k^th data chunk in the K to-be-coded data chunks, wherein K≥

k≥

1, the ((k−

1)*R+1)^th column to the (k*R)^th column of the check matrix respectively correspond to the R data code blocks of the k^th data chunk in the K data chunks, the (K*R+1)^th column to the ((K+1)*R)^th column of the check matrix respectively correspond to the R check code blocks of the first check chunk, and the ((K+1)*R+1)^th column to the ((K+2)*R)^th column of the check matrix respectively correspond to the R check code blocks of the second check chunk; and

wherein there are three coordinates of 1 in a D^th row of the check matrix, wherein the D^th row is any row of the check matrix, and an exclusive OR operation is performed on any two of three code blocks corresponding to the coordinates of 1 in the D^th row of the check matrix, based on the OR equation of the D^th row, to obtain a code block that does not participate in this exclusive OR operation and that is in the three code blocks corresponding to the coordinates of 1 in the D^th row of the check matrix.

18. The non-transitory computer-readable storage medium according to claim 16, further comprising:

separately storing the K to-be-coded data chunks, the first check chunk, and the second check chunk into (K+2) storage media in the storage system in which the first computer is located.

19. The non-transitory computer-readable storage medium according to claim 18, further comprising:

when a storage medium in the (K+2) storage media is damaged, recovering the damaged storage medium according to the check matrix, a data chunk that is stored on an undamaged storage medium in the (K+2) storage media, and the first check chunk or the second check chunk.

20. The non-transitory computer-readable storage medium according to claim 18, wherein the dividing comprises:

when a quantity of received to-be-written data reaches a preset value, divide the to-be-written data into K to-be-coded data chunks.