Method of, and apparatus for, layout rectification of erasure encoded storage systems

• US 9,405,623 B2
• Filed: 09/25/2013
• Issued: 08/02/2016
• 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
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US14/037,075
• Publication Number:
  US 20150089282A1
• Time in Patent Office: 1,042 Days
• Field of Search: 711/114, 711/151, 711/154, 711/170, 712/10, 712/17, 712/210, 714/6.2, 714/6.22, 714/756, 714/770, 714/784
• US Class Current: 1/1
• 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 comprising:

detecting a loss of configuration metadata for a redundant array of independent disks (RAID), the configuration metadata providing a format of stripe units stored in data storage devices of the RAID;

reading raw data stored in the RAID, the raw data comprising message data and checksum data;

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

solving said set of linear equations with the computing device; and

recovering the configuration metadata from the solved set of linear equations.

2. The method of claim 1, wherein a matrix equation is formed based on said set of linear equations, said matrix equation comprising a matrix based on said raw data, the matrix being inverted to obtain a set of coefficients that recover the configuration data of said RAID array.

3. The method of claim 2, wherein the configuration metadata comprises a checksum basis vector used to generate one of said checksums comprising said checksum data.

4. The method of claim 3, further comprising repeating the reading, defining, solving, and recovering steps to generate further checksum basis vectors for further checksums, each checksum basis vector being used to generate one of said checksums.

5. The method of claim 4, wherein each checksum basis vector is verified using a geometric series subsequent to solving the set of linear equations.

6. The method of to claim 4, wherein the RAID array comprises a plurality of stripe groups, each stripe group comprising a plurality of the stripe units, the configuration metadata comprising a stripe unit size of one of the plurality of stripe units.

7. The method of claim 6, wherein the configuration metadata comprises a unit mapping strategy, the method further comprising:

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

identifying the stripe unit size based on said change in codeword permutation;

obtaining said unit mapping strategy based on said plurality of checksum basis vectors and said stripe unit size by recovering the position of said stripe units within an array from said checksum basis vectors; and

repeating the recovering step for multiple sequential stripe groups to obtain the unit mapping strategy.

8. The method of claim 1, wherein the configuration metadata comprises a stripe group width, a number of message data units per stripe, a number of checksum data units per stripe, and a symbol size, the configuration metadata determined empirically prior to the reading step.

9. The method of claim 1, wherein the configuration metadata comprises a plurality of parameters relating to a layout of said RAID.

10. The method of claim 9, further comprising verifying data consistency across the entire RAID subsequent to the recovering step.

11. The method of claim 10, further comprising bringing the RAID online with the recovered configuration metadata.

12. The method of claim 1, wherein a RAID hardware controller recovers the configuration metadata and the RAID is erasure encoded.

13. The method of claim 12, wherein the RAID hardware controller reads data from and stores data to at least one storage device.

14. The method of claim 1, wherein a non-transitory computer usable storage medium of the RAID stores a computer program product executed by a programmable processing apparatus to recover the configuration metadata.

15. A method comprising:

detecting a loss of configuration metadata for a redundant array of independent disks (RAID), the configuration metadata providing a format of stripe units stored in data storage devices of the RAID;

reading raw data stored in the RAID, the raw data comprising message data and checksum data;

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

solving said set of linear equations with the computing device;

recovering the configuration metadata from the solved set of linear equations;

utilizing 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; and

writing said codeword to said RAID said basis root being greater than one for all checksums.

16. The method of claim 15, wherein further comprising:

translating said message data using an involuntary function to generate translated message data and translated checksum information;

writing untranslated message data to said RAID; and

writing translated checksum data to said RAID.

17. A method comprising:

detecting a loss of configuration metadata for a redundant array of independent disks (RAID), the configuration metadata providing a distribution, number, and size of stripe units stored in data storage devices of the RAID;

reading raw data stored in the RAID, the raw data comprising message data and checksum data;

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

solving said set of linear equations with the computing device;

recovering the configuration metadata from the solved set of linear equations.

18. The method of claim 17, further comprising:

utilizing 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; and

writing said codeword to said RAID.

19. The method of 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. The method of claim 19, wherein the w-bit basis root comprises an 8, 16 or 32 bit basis root.