STORAGE CODES FOR DATA RECOVERY

• US 20120173932A1
• Filed: 12/31/2010
• Published: 07/05/2012
• Est. Priority Date: 12/31/2010
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Li, Jin, Huang, Cheng, Cadambe, Viveck
• Granted Patent: US 8,645,799 B2
• Time in Patent Office: Days
• US Class Current: 714/42
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A random permutation code is described which provides efficient repair of data nodes. A specific implementation of a permutation code is also described, followed by description of a MISER-Permutation code. Finally, an optimal repair strategy is explained that involves an iterative process of downloading the most effective available parity data, updating costs of remaining parity data, and repeating until the data is recovered.

Claims

1. A method of recovering data, the method comprising:

maintaining data storage units and parity storage units, where the parity storage units store parity data computed from a group of data stored in the data storage units; and

when a storage unit comprising either a first data storage or a first parity storage unit becomes unavailable, reading recovery data and using the recovery data to fully recover the data that was stored on the unavailable storage unit, wherein the recovery data consists of a portion of data in a combination of the data storage units and the parity storage units excluding the unavailable storage unit, and wherein the amount of data stored by the combination, in aggregate, is less than the amount of data in the group of data.

2. A method according to claim 1, wherein the data storage units and parity storage units comprise respective disk drives.

3. A method according to claim 1, further comprising transposing two sub-units of parity data.

4. A method according to claim 3, further comprising multiplying one of the sub-units by an integer.

5. A method according to claim 4, further comprising XOring the two sub-units of parity data with two other sub-units of parity data.

6. A method according to claim 1, wherein the parity storage units are computed using an (n,k) code, and wherein each storage unit is divided into (n−

k)̂

k pieces.

7. A method according to claim 6, wherein repair of a single data storage unit requires only 1/n−

k of the pieces of corresponding parity storage units.

8. A method according to claim 7, wherein all of the pieces of the corresponding parity storage units cover the failed node.

9. A method according to claim 8 wherein each storage unit has a same amount of storage space subjected to the method.

10. One or more computer-readable storage media storing information to enable one or more computing devices to perform a process, the process comprising:

maintaining a plurality of nodes comprised of 2k parity nodes and 3k data nodes, wherein each of data node consists of k̂

2 data storage units, and wherein each of parity node consists of k̂

2 parity storage units; and

recovering a first data node when the first data node fails or is disabled, the recovering comprising reading no more than k data storage units per data node and/or parity node.

11. One or more computer-readable storage media according to claim 10, wherein the parity nodes are computed using a combination of a left code and a right code, each comprising a (2k, k) codes, the computing the parity nodes comprising:

constructing a (2k, k) erasure code with minimum repair cost, in which each data node consists of k data storage units, and each parity node consists of k parity storage units; and

recovering a first data node failure comprising reading one data storage unit per data node and/or parity node;

dividing each storage unit in the above (2k,k) code further into k sub units, whereby each data node and parity node consists of a total of k̂

2 storage units; and

transposing the right code of the (2k,k) code and XORing the storage units of a parity node to form the storage unit in the parity node with a (3k, 2k) code.

12. One or more computer-readable storage media according to claim 10, wherein given n total storage units, the erasure code has a repair bandwidth of

13. One or more computer-readable storage media according to claim 10, wherein, given n total storage units, a parity node is repairable with an amount of

14. One or more computer-readable storage media according to claim 10, wherein recovering the failed or disabled data node comprises:

reading k storage units in a parity node that is used by (2k,k) code,

reading k storage units in the a node that is used by (2k,k) code in a same left/right half,

reading k storage units in the data node in the different left/right half that is associated with the k storage units in the accessed parity node.

15. One or more computer-readable storage media according to claim 11, wherein the (3k, 2k) code comprises a Miser-Permutation code.

16. A method to identify a reduced cost repair strategy for any given linear erasure code, the method comprising:

maintaining data storage units and parity storage units, where the parity storage units store parity data computed from a group of data stored in the data storage units through the linear erasure code;

identifying a plurality of data nodes and parity nodes, each data node storing multiple data storage units, and each parity node storing multiple parity storage units;

when a data node becomes unavailable, identifying multiple data storage units thereof that consequently are unavailable; and

identifying a minimal repair set of data storage units on still-available data storage nodes and parity storage units that reduces a cost of repairing the unavailable data node.

17. A method according to claim 16, wherein identifying the minimal repair set comprises:

initializing the minimal repair set to be empty;

assigning a recovery cost for each of the parity storage units, where each parity storage unit'"'"'s cost represents an amount of additional corresponding data storage units that would need to be accessed to recover the unavailable data storage unit;

identifying a parity storage unit with a lowest recovery cost;

adding the identified parity storage unit and its corresponding data storage units to the recovery set; and

for at least parity storage units and data storage units not previously added to the recovery set, updating their corresponding recovery costs based on the recovery set.

18. A method according to claim 16, wherein a breadth-first search is performed to identify the minimal repair set, by:

building a tree of recovery costs starting at a root of the tree, which has an empty recovery set and a recovery cost of zero;

adding a new node to an interim leaf node of the tree by adding a parity storage unit and its corresponding data storage units to the recovery set of the leaf node, and adding the number of corresponding data storage units and the parity storage unit as additional cost to the recovery cost of the new node;

setting the new node as a terminal leaf node if all unavailable data storage units are recovered, and otherwise setting the new node as an interim tree node; and

searching the tree to find a leaf node having a minimal repair cost.

19. A method according to claim 18, further comprising pruning the tree so that interim nodes with high repair costs are pruned from further evaluation.

20. A method according to claim 16, further comprising, wherein when one or more parity nodes fails:

a reduced cost repair strategy is identified by rewriting the linear erasure code and using the failed parity node as the original data, and substituting a same number of data nodes as parity nodes; and

identifying a minimal repair set of data storage units and parity storage units that reduces the repair cost of the failed data nodes and parity nodes.