Network-aware storage repairs

• US 10,140,172 B2
• Filed: 08/31/2016
• Issued: 11/27/2018
• Est. Priority Date: 05/18/2016
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sipos, Marton Akos, Gahm, Joshua, Venkat, Narayan
• Primary Examiner(s): Butler, Sarai E
• Application Number:
  US15/253,346
• Publication Number:
  US 20170337097A1
• Time in Patent Office: 818 Days
• Field of Search: 714 37
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence

Abstract

In an example, there is disclosed a computing apparatus, having one or more logic elements, including at least one hardware logic element, comprising a network-aware data repair engine to compute a feasible repair log for n fragments of an original data structure, comprising: receiving a predictive failure scenario; identifying at least one repair ξ_i for the failure scenario; determining that ξ_i is feasible; and logging ξ_i to a feasible repair log. When a node failure occurs, a network cost may be computed for each repair in the feasible repair log, and an optimal repair may be selected.

Claims

1. A computing apparatus, comprising:

one or more logic elements, including at least one hardware logic element, comprising a network-aware data repair engine to compute a feasible repair log for n fragments of an original data structure, comprising;

receiving a predictive failure scenario;

identifying at least one repair ξ

_i for the predictive failure scenario;

determining that ξ

_i is a feasible repair to the predictive failure scenario; and

logging ξ

_i to a feasible repair log only if ξ

_i is (a) determined to be a feasible repair to the predictive failure scenario and (b) potentially a lowest-cost repair;

wherein ξ

_i is not logged in the feasible repair log if ξ

_i is not determined to be a feasible repair or ξ

_i is not a potentially a lowest-cost repair option.

2. The computing apparatus of claim 1, wherein the n fragments of the original data structure comprise an erasure encoded transformation.

3. The computing apparatus of claim 2, wherein determining that ξ

_i is feasible comprises determining that ξ

_i retains the maximum distance separating (MDS) property.

4. The computing apparatus of claim 1, wherein the network-aware data repair engine is further to react to a failure event, comprising:

computing a network cost for at least two repairs ξ

of the feasible repair log; and

selecting an optimal repair ξ

_o.

5. The computing apparatus of claim 4, wherein selecting the optimal repair comprises identifying a repair with a least weighted network cost.

6. The computing apparatus of claim 1, wherein the network-aware data repair engine is to determine that a repair is a potentially lowest-cost repair, comprising sorting surviving nodes in increasing order of repair bandwidth and assigning more fragment transfers to less costly nodes.

7. The computing apparatus of claim 1, wherein the network-aware data repair engine is to operate on random linear network codes (RLNC) and is to determine that a repair is a potentially lowest-cost repair, comprising considering only repairs wherein a total bandwidth transferred by any L nodes is equal to a size of fragments to be used in the repair.

8. The computing apparatus of claim 1, wherein the computing apparatus is a predictive repair appliance.

9. A method of performing network-aware data repairs to compute a feasible repair log for n fragments of an original data structure, comprising:

receiving a predictive failure scenario;

identifying at least one repair ξ

_i for the predictive failure scenario;

determining that ξ

_i is a feasible repair to the predictive failure scenario; and

logging ξ

_i to a feasible repair log only if ξ

_i is (a) determined to be a feasible repair to the predictive failure scenario and (b) potentially a lowest-cost repair;

wherein ξ

_i is not logged in the feasible repair log if ξ

_i is not determined to be a feasible repair or ξ

_i is not a potentially a lowest-cost repair option.

10. The method of claim 9, wherein the n fragments of the original data structure comprise an erasure encoded transformation.

11. The method of claim 10, wherein determining that ξ

_i is feasible comprises determining that ξ

_i retains the maximum distance separating (MDS) property.

12. The method of claim 9, further comprising:

computing a network cost for at least two repairs ξ

of the feasible repair log; and

selecting an optimal repair ξ

_o.

13. The method of claim 12, wherein selecting the optimal repair comprises identifying a repair with a least weighted network cost.

14. The method of claim 9, wherein the network-aware data repair engine is to determine that a repair is a potentially lowest-cost repair, comprising sorting surviving nodes in increasing order of repair bandwidth and assigning more fragment transfers to less costly nodes.

15. The method of claim 9, wherein the network-aware data repair engine is to operate on random linear network codes (RLNC) and is to determine that a repair is a potentially lowest-cost repair, comprising considering only repairs wherein a total bandwidth transferred by any L nodes is equal to a size of fragments to be used in the repair.

16. One or more tangible, non-transitory computer-readable storage mediums having stored thereon executable instructions for performing network-aware data repairs to predictively compute a feasible repair log for n fragments of an original data structure, comprising:

receiving a predictive failure scenario;

identifying at least one repair ξ

_i for the predictive failure scenario;

determining that ξ

_i is a feasible repair to the predictive failure scenario; and

logging ξ

_i to a feasible repair log only if ξ

_i is (a) determined to be a feasible repair to the predictive failure scenario and (b) potentially a lowest-cost repair;

wherein ξ

_i is not logged in the feasible repair log if ξ

_i is not determined to be a feasible repair or ξ

_i is not a potentially a lowest-cost repair option.

17. The one or more tangible, non-transitory computer-readable storage mediums of claim 16, wherein the n fragments of the original data structure comprise an erasure encoded transformation.

18. The one or more tangible, non-transitory computer-readable storage mediums of claim 17, wherein determining that ξ

_i is feasible comprises determining that ξ

_i retains the maximum distance separating (MDS) property.