Triple parity encoding to facilitate data recovery
View Patent ↗Examples are disclosed for facilitating recovery from failures associated with a storage array having a plurality of storage devices.
1. A method to facilitate data recovery of a storage array, comprising:
organizing a plurality of storage devices into stripes according to a striping scheme;
determining first and second row parities and first and second diagonal parities according to the striping scheme;
implementing a first row-diagonal parity (RDP) scheme that utilizes one or more row parity values associated with the first row parities and one or more diagonal parity values associated with the first diagonal parities; and
implementing a second RDP scheme that utilizes one or more diagonal parity values associated with the second diagonal parities and one or more row parity values associated with the second row parities.
2. The method of claim 1 , wherein the plurality of storage devices includes n data storage devices, wherein n=p−1 and p includes a prime number greater than 3.
3. The method of claim 2 , further comprising:
dividing each of the plurality of storage devices into chunks; and
wherein the striping scheme includes organizing a same number of chunks in each of the plurality of storage devices, wherein each of the plurality of storage devices are striped into (p−1) 2 chunks.
4. The method of claim 3 , wherein the determining the first row parities and the second row parities according to the striping scheme includes the first row parities and the second row parities being separately defined based, at least in part, on determined first row parities and determined second row parities that separately include (p−1) 2 rows.
5. The method of claim 4 , wherein the determining the first diagonal parities along the first diagonal parity sets include the first diagonal parities being defined based, at least in part, on the first diagonal parity sets wrapping around within (p−1) 2 rows, wherein the chunks belonging to a respective first diagonal parity set of a given stripe are stored in the given stripe.
6. The method of claim 5 , wherein the determining the second diagonal parities along the second diagonal parity sets include the second diagonal parities being defined based, at least in part, on the second diagonal parity sets partially wrapping around within the (p−1) 2 rows, wherein the chunks belonging to a respective second diagonal parity set of a given stripe are stored in the given stripe.
7. The method of claim 3 , wherein each of the plurality of storage devices are striped according to a Redundant Array of Independent Disks (RAID) scheme.
8. The method of claim 1 , wherein the plurality of storage devices includes at least one of a hard disk drive, a solid state disk drive, a direct access storage device, magnetic tape, bubble memory, optical storage media, electronic random access or a digital versatile disk.
9. The method of claim 1 , wherein failures associated with the data recovery include a combination of failures in one or more of the plurality of storage devices or checksum errors associated with the one or more of the plurality of storage devices.
10. An apparatus, comprising:
a recovery manager configured to:
organize a plurality of storage devices into stripes according to a striping scheme;
determine first and second row parities and first and second diagonal parities according to the striping scheme;
implement a first row-diagonal parity (RDP) scheme that utilizes one or more row parity values associated with the first row parities and one or more diagonal parity values associated with the first diagonal parities; and
implement a second RDP scheme that utilizes one or more diagonal parity values associated with the second diagonal parities and one or more row parity values associated with the second row parities.
11. The apparatus of claim 10 , wherein the plurality of storage devices includes n data storage devices, wherein n=p−1 and p is a prime number greater than 3.
12. The apparatus of claim 10 , wherein the recovery manager is further configured to:
divide each of the plurality of storage devices into chunks; and
wherein the striping scheme includes organizing a same number of chunks in each of the plurality of storage devices, wherein each of the plurality of storage devices are striped into (p−1) 2 chunks.
13. The apparatus of claim 12 , wherein the determining the first row parities and the second row parities according to the striping scheme includes the first row parities and the second row parities being separately defined based, at least in part, on determined first row parities and determined second row parities that separately include (p−1) 2 rows.
14. The apparatus of claim 13 , wherein the determining the first diagonal parities along the first diagonal parity sets include the first diagonal parities being defined based, at least in part, on the first diagonal parity sets wrapping around within (p−1) 2 rows, wherein the chunks belonging to a respective first diagonal parity set of a given stripe are stored in the given stripe.
15. The apparatus of claim 14 , wherein the determining the second diagonal parities along the second diagonal parity sets include the second diagonal parities being defined based, at least in part, on the second diagonal parity sets partially wrapping around within the (p−1) 2 rows, wherein the chunks belonging to a respective second diagonal parity set of a given stripe are stored in the given stripe.
16. The apparatus of claim 12 , wherein each of the plurality of storage devices are striped according to a Redundant Array of Independent Disks (RAID) scheme.
17. The apparatus of claim 10 , wherein the plurality of storage devices includes at least one of a hard disk drive, a solid state disk drive, a direct access storage device, magnetic tape, bubble memory, optical storage media, electronic random access or a digital versatile disk.
18. The apparatus of claim 10 , wherein failures associated with the data recovery include a combination of failures in one or more of the plurality of storage devices or checksum errors associated with the one or more of the plurality of storage devices.
19. A system to facilitate data recovery of a storage array, comprising:
a plurality of data storage devices, a first row parity storage device, a second row parity storage device, a first diagonal parity storage device and a second diagonal parity storage device; and
a recovery manager configured to:
organize the plurality of storage devices into stripes according to a striping scheme;
determine first and second row parities and first and second diagonal parities according to the striping scheme;
implement a first row-diagonal parity (RDP) scheme that utilizes one or more row parity values associated with the first row parities and one or more diagonal parity values associated with the first diagonal parities; and
implement a second RDP scheme that utilizes one or more diagonal parity values associated with the second diagonal parities and one or more row parity values associated with the second row parities.
20. The system of claim 19 ,
wherein the determining the first row parities and the second row parities according to the striping scheme includes the first row parities and the second row parities being separately defined based, at least in part, on determined first row parities and determined second row parities that separately include (p−1) 2 rows; and
wherein the determining the first diagonal parities along the first diagonal parity sets include the first diagonal parities being defined based, at least in part, on the first diagonal parity sets wrapping around within (p−1) 2 rows, wherein the chunks belonging to a respective first diagonal parity set of a given stripe are stored in the given stripe.