Generating a parallel recovery plan for a data storage system

1. A method of identifying a parallel recovery plan for a data storage system, comprising:

identifying base recovery plans for symbols of an erasure code implemented across a plurality of storage devices in a data storage system;

generating a list of first recovery plans for a first symbol based on the base recovery plans;

combining selected first recovery plans from the list to generate a set of parallel recovery plans to reconstruct a failed storage device; and

evaluating the set of parallel recovery plans based on a performance metric to identify a preferred parallel recovery plan to reconstruct the failed storage device.

2. The method as recited in claim 1 , further comprising: providing a structure of the erasure code, wherein identification of the base recovery plans is based on the provided structure.

3. The method as recited in claim 1 , wherein generating the list of recovery plans comprises:

providing a first base recovery plan for a first symbol;

identifying a second symbol of the erasure code in the first base recovery plan;

substituting a second base recovery plan associated with the second symbol for the second symbol in the first base recovery plan to generate a recovery plan; and

adding the recovery plan to the list of recovery plans.

4. The method as recited in claim 1 , wherein the performance metric is maximum speedup with minimal load.

5. The method as recited in claim 1 , wherein the recovery plans for the first symbol are conditioned on loss of other symbols of the erasure code.

6. The method as recited in claim 1 , further comprising:

generating a list of recovery plans for a second symbol of the erasure code; and

combining selected recovery plans for the first symbol with selected recovery plans for the second symbol to generate multi-parallel recovery plans, wherein a multi-parallel recovery plan includes a selected recovery plan for the first symbol and a selected recovery plan for the second symbol.

7. A method of generating a list of recovery plans for a symbol of an erasure code, comprising:

providing a structure of an erasure code having a plurality of symbols implemented across a plurality of storage devices;

generating base recovery plans for the symbols based on the structure; and

for each base recovery plan for a first symbol,

identifying a second symbol in the base recovery plan;

identifying a second base recovery plan for the second symbol that does not depend on the first symbol;

substituting the second base recovery plan for the second symbol in the base recovery plan for the first symbol to generate a recovery plan; and

adding the recovery plan to a list of recovery plans.

8. The method as recited in claim 7 , further comprising conditioning the recovery plans for the first symbol on loss of another symbol of the erasure code.

9. The method as recited in claim 7 , wherein the symbols comprise data symbols and parity symbols, and wherein generating the base recovery plans for a data symbol comprises identifying odd sets of parity symbols connected to the data symbol.

10. The method as recited in claim 9 , wherein the structure is one of a Tanner graph and a generator matrix.

11. A method of selecting a parallel recovery plan to reconstruct a failed data storage device, comprising:

generating a list of recovery plans for a symbol of an erasure code having a plurality of symbols implemented across a plurality of storage devices;

combining recovery plans from the list to generate a set of parallel recovery plans to reconstruct a failed storage device;

filtering from the set of parallel recovery plans those parallel recovery plans that exceed a bottleneck bound; and

evaluating the filtered set of parallel recovery plans to identify a preferred parallel recovery plan to reconstruct a failed storage device.

12. The method as recited in claim 11 , wherein generating a list of recovery plans comprises:

identifying base recovery plans;

generating recovery plans based on the base recovery plans; and

filtering, from the list, any recovery plan having a number of symbols that exceeds a predefined threshold.

13. The method as recited in claim 11 , wherein the filtered set of parallel recovery plans is evaluated based on at least one of speedup and load to identify a preferred parallel recovery plan.

14. The method as recited in claim 11 , wherein the erasure code is an XOR-based erasure code.