Data storage system

• US 20070006019A1
• Filed: 08/31/2005
• Published: 01/04/2007
• Est. Priority Date: 01/07/2005
• Status: Abandoned Application

• Current Assignee: Promise Technology Incorporated
• Original Assignee: Promise Technology Incorporated
• Inventors: Chien, Hung-Ming
• Application Number:
  US11/217,054
• Publication Number:
  US 20070006019A1
• Time in Patent Office: Days
• US Class Current: 714/6
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A data storage system including an array of storage devices and a storage controller is provided. The array of storage devices is configured to store information in the form of a plurality of stripes. The storage controller is configured to write a plurality of code words forming each stripe to the array of storage devices. Each code word comprises a plurality of data blocks and at least one redundancy block. A redundancy check matrix is previously provided and one subset including any k columns of elements in the redundancy check matrix is invertible. The storage controller generates the redundancy block according to the plurality of data blocks and the redundancy check matrix. Once up to k storage devices among the array of storage devices are failed, the other un-failed storage devices and the redundancy check matrix are utilized to recover the failed storage devices.

Claims

1. In a data storage system, a redundancy check matrix with k rows and n columns of elements being previously provided, any sub-matrix comprising k columns of elements among the n columns of elements in the redundancy check matrix being invertible, k being a natural number and n being a natural number larger than k, said data storage system comprising:

an array of storage devices configured to store information in the form of a plurality of stripes; and

a storage controller coupled to the array of storage devices and configured to write a plurality of code words forming each stripe to the array of storage devices;

wherein said plurality of code words represents a systematic mapping of a plurality of data blocks according to the redundancy check matrix and comprises said plurality of data blocks and at least one redundancy block, and

wherein said storage controller comprises an encoder configured to generate said at least one redundancy block according to the plurality of data blocks and the redundancy check matrix in an encoding mode.

2. The data storage system of claim 1, wherein once up to k storage devices in the array of storage devices are failed, the data storage system recovers the code words in the failed storage devices based on the redundancy check matrix and the code words in the other un-failed storage devices.

3. The data storage system of claim 1, wherein the array of storage devices comprises a plurality of disk drives.

4. The data storage system of claim 1, wherein the array of storage devices comprises n storage devices, a first stripe in the array of storage devices comprises (n-k) subsets of data blocks (D₁, D₂, . . . , D_(n-k)) and k subsets of redundancy blocks (C₁, C₂, . . . , C_k) generated by the encoder, each subset is stored in one storage device in the array of storage device, respectively, the redundancy check matrix is:

5. The data storage system of claim 4, wherein the encoder generates the k subsets of redundancy blocks according to a generator matrix which is generated based on the redundancy check matrix and represented as:

6. The data storage system of claim 4, wherein a second stripe in the array of storage devices comprises n code words, each code word is stored in one storage device in the array of storage device, respectively, the storage controller further comprises a recovering module, once e code words (D_f1, D_f2, . . . , D_fe) among the n code words are failed, the recovering module recovers the e failed code words based on a recovery matrix and the other (n-e) un-failed code words (D_g—

₁, D<sub>g—

2</sub>, . . . , D<sub>g—

(n-e)</sub>), the recovery matrix is generated based on the redundancy check matrix and represented as;

7. The data storage system of claim 1, wherein the redundancy check matrix R is a Vandermonde matrix and represented as:

8. The data storage system of claim 7, wherein the array of storage devices comprises n storage devices, a first stripe in the array of storage devices comprises (n-k) subsets of data blocks (D₁, D₂, . . . , D_(n-k)) and k subsets of redundancy blocks (C₁, C₂, . . . , C_k) generated by the encoder, each subset is stored in one storage device in the array of storage device, respectively, the relation between the (n-k) subsets of data blocks and k subsets of redundancy blocks is:

9. The data storage system of claim 8, wherein the encoder generates the k subsets of redundancy blocks according to a generator matrix which is generated based on the Vandermonde matrix and represented as:

10. The data storage system of claim 7, wherein the array of storage devices comprises n storage devices, a second stripe in the array of storage devices comprises n code words, each code word is stored in one storage device in the array of storage device, respectively, the storage controller further comprises a recovering module, once e code words (D_f1, D_f2, . . . , D_fe) among the n code words are failed, the recovering module recovers the e failed code words based on a recovery matrix and the (n-e) un-failed code words (D_g—

₁, D<sub>g—

2</sub>, . . . , D<sub>g—

(n-e)</sub>), the recovery matrix is generated based on the Vandermonde matrix and represented as;

11. The data storage system of claim 1, wherein the redundancy check matrix R is a Vandermonde matrix and represented as:

12. The data storage system of claim 1, wherein the redundancy check matrix R is a Vandermonde matrix and represented as:

13. The data storage system of claim 1, wherein the redundancy check matrix R is generated according to a k-th order Reed-Solomon code generator polynomial, and the k roots of the generator polynomial are {1, a, a², . . . , a^k−

1}, wherein the coefficient field is GF(q^P), a is a primitive element of the coefficient field GF(q^P), q is a prime number, P is a positive integer, and the redundancy check matrix R is represented as;

14. The data storage system of claim 13, wherein the array of storage devices comprises n storage devices, a first stripe in the array of storage devices comprises (n-k) subsets of data blocks (D₁, D₂, . . . , D_(n-k)) and k subsets of redundancy blocks (C₁, C₂, . . . , C_k) generated by the encoder, each subset is stored in one storage device in the array of storage device, respectively, and the relation between the (n-k) subsets of data blocks and k subsets of redundancy blocks is:

15. The data storage system of claim 14, wherein the encoder generates the k subsets of redundancy blocks according to a generator matrix which is generated based on the redundancy check matrix and represented as:

16. The data storage system of claim 13, wherein the array of storage devices comprises n storage devices, a second stripe in the array of storage devices comprises n code words, each code word is stored in one storage device in the array of storage device, respectively, the storage controller further comprises a recovering module, once e code words (D_f1, D_f2, . . . , D_fe) among the n code words are failed, the recovering module recovers the e failed code words based on a recovery matrix and the (n-e) un-failed code words (D_g—

₁, D<sub>g—

2</sub>, . . . , D<sub>g—

(n-e)</sub>), the recovery matrix is generated based on the redundancy check matrix and represented as;

17. A method of generating k redundancy blocks (C₁, C₂, . . . , C_k) for (n-k) data blocks (D₁, D₂, . . . , D_(n-k)), k being a natural number, n being a natural number larger than k, a previously provided Vandermonde matrix (R) with k rows and n columns of elements being represented as:

18. The method of claim 17, wherein once up to k blocks among the (n-k) data blocks and the k redundancy blocks are failed, the method recovers the failed blocks based on the Vandermonde matrix and the other un-failed blocks.

19. A method of generating k redundancy blocks (C₁, C₂, . . . , C_k) for (n-k) data blocks (D₁, D₂, . . . , D_(n-k)), k being a natural number, n being a natural number larger than k, a redundancy check matrix (R) generated according to a k-th order Reed-Solomon code generator polynomial being previously provided, the k roots of the generator polynomial being {1, a, a², . . . , a^k−

1}, wherein the coefficient field is GF(q^P), a is a primitive element of the coefficient field GF(q^P), q is a prime number, P is a positive integer, the redundancy check matrix (R) with k rows and n columns of elements being represented as;

20. The method of claim 19, wherein once up to k blocks among the (n-k) data blocks and the k redundancy blocks are failed, the method recovers the failed blocks based on the redundancy check matrix and the other un-failed blocks.