METHOD OF, AND APPARATUS FOR, LAYOUT RECTIFICATION OF ERASURE ENCODED STORAGE SYSTEMS

• US 20150089282A1
• Filed: 09/25/2013
• Published: 03/26/2015
• Est. Priority Date: 09/25/2013
• Status: Active Grant

• Current Assignee: Xyratex Technology Limited (Seagate Technology Holdings Plc)
• Original Assignee: Xyratex Technology Limited (Seagate Technology Holdings Plc)
• Inventors: TARANTA, Eugene Mathew II
• Granted Patent: US 9,405,623 B2
• Time in Patent Office: Days
• US Class Current: 714/6.24
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 13/1668 Details of memory controller
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

There is provided a method of recovering configuration metadata from an erasure encoded RAID array. The RAID array includes raw data including a plurality of codewords encoded using Reed-Solomon encoding. The codewords include message data and checksum data, and the configuration metadata includes parameters relating to the layout of the RAID array. The method includes reading, from the RAID array, raw data including message data and checksum data. Then a set of linear equations are defined using the message data and checksum data. The linear equations are then solved and then, from the solved linear equations, one or more parameters relating to the layout of the RAID array are determined.

Claims

1. A method for recovering configuration metadata from an erasure encoded RAID array, the RAID array comprising raw data comprising a plurality of codewords encoded using Reed-Solomon encoding, said codewords including message data and checksum data comprising a plurality of checksums, and said configuration metadata comprising parameters relating to the layout of said RAID array, the method comprising:

a) reading, from said RAID array, raw data comprising message data and checksum data;

b) defining, on a computing device, a set of linear equations using said message data and checksum data;

c) solving, on a computing device, said set of linear equations;

d) determining, from said solved linear equations, one or more parameters relating to the layout of said RAID array.

2. A method according to claim 1, wherein step b) comprises forming a matrix equation based on said set of linear equations, said matrix equation comprising a matrix based on said raw data;

step c) comprises inverting said matrix to obtain a set of coefficients; and

step d) comprises utilising said coefficients to obtain one or more parameters relating to the layout of said RAID array.

3. A method according to claim 2, wherein said one or more parameters relating to the layout of said RAID array comprises a checksum basis vector used to generate one of said checksums comprising said checksum data.

4. A method according to claim 3, further comprising repeating steps b) to d) to generate further checksum basis vectors for further checksums, each checksum basis vector being used to generate one of said checksums.

5. A method according to claim 4, wherein the method further comprises, subsequent to step c):

e) verifying each checksum basis vector using a geometric series.

6. A method according to claim 4, wherein the RAID array comprises a plurality of stripe groups, each stripe group comprising a plurality of stripe units, and said one or more parameters relating to the layout of said RAID array comprises the stripe unit size, the method further comprising:

f) iterating through said codewords to identify a change in codeword permutation; and

g) identifying the stripe unit size based on said change in codeword permutation.

7. A method according to claim 6, wherein said one or more parameters relating to the layout of said RAID array comprises the unit mapping strategy;

and the method further comprising;

h) obtaining said unit mapping strategy based on said plurality of checksum basis vectors and said stripe unit size by;

i) recovering the position of said stripe units within an array from said checksum basis vectors; and

j) repeating step i) for multiple sequential stripe groups to obtain the unit mapping strategy.

8. A method according to claim 1, wherein said one or more parameters relating to the layout of said RAID array comprise the stripe group width;

the number of message data units per stripe;

the number of checksum data units per stripe; and

the symbol size and wherein said parameters are determined empirically prior to step a).

9. A method according to claim 1, further comprising, subsequent to step d):

k) rebuilding said configuration metadata from the one or more determined parameters relating to the layout of said RAID array.

10. A method according to claim 9, further comprising, subsequent to step k):

l) verifying data consistency across the entire RAID array.

11. A method according to claim 10, further comprising, subsequent to step j):

m) bringing the RAID array online with said rebuilt configuration metadata.

12. A RAID hardware controller operable to recover configuration metadata from an erasure encoded RAID array, the controller being operable to carry out the steps of claim 1.

13. Data storage apparatus comprising at least one storage device and the controller of claim 12.

14. A non-transitory computer usable storage medium having stored thereon a computer program product executable by a programmable processing apparatus, comprising one or more software portions for performing a method according to claim 1.

15. A method of encoding data in an erasure encoded RAID array to facilitate recovery in the event of the loss of configuration metadata, the method comprising:

a) utilising Reed-Solomon encoding to encode message data and an array unique identifier to form a codeword comprising message data and checksum information comprising a plurality of checksums;

b) writing said codeword to said RAID array;

wherein in step a) said basis root is greater than one for all checksums.

16. A method according to claim 15, wherein step a) further comprises:

c) translating said message data using a involutary function to generate translated message data and translated checksum information; and

step b) further comprises

d) writing untranslated message data to said RAID array; and

e) writing translated checksum data to said RAID array.

17. A method of encoding data in an erasure encoded RAID array to facilitate recovery in the event of the loss of configuration metadata, the method comprising:

a) utilising Reed-Solomon encoding to encode message data to form a codeword comprising message data and checksum information comprising a plurality of checksums;

b) translating said message data using a involutary function to generate translated message data and translated checksum information;

c) writing untranslated message data to said RAID array; and

d) writing translated checksum data to said RAID array.

18. A method of encoding data in an erasure encoded RAID array to facilitate recovery in the event of the loss of configuration metadata, the method comprising:

a) utilising Reed-Solomon encoding to encode message data to form a codeword comprising message data and checksum information comprising a plurality of checksums, said message data being encoded using a w-bit basis root for the basis vector for the or each checksum, said w-bit basis root storing configuration parameters for said RAID array; and

b) writing said codeword to said RAID array.

19. A method according to claim 18, wherein said w-bit basis root for the basis vector comprises one or more configuration parameters selected from the list of:

CRC field;

number of checksums per stripe group;

stripe number;

array number; and

a first row of the unit mapping identifier.

20. A method according to claim 18, wherein the w-bit basis root comprises an 8, 16 or 32 bit basis root.