Risk based rebuild of data objects in an erasure coded storage system

• US 10,514,984 B2
• Filed: 02/26/2016
• Issued: 12/24/2019
• Est. Priority Date: 02/26/2016
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Slik, David Anthony, Jaffer, Shehbaz, Subbiah, Sethuraman, Smith, Keith Arnold, Yasa, Giridhar Appaji Nag, Kathpal, Atish
• Primary Examiner(s): Leibovich, Yair
• Application Number:
  US15/055,484
• Publication Number:
  US 20170249213A1
• Time in Patent Office: 1,397 Days
• Field of Search: 714 624
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes

Abstract

A rebuild node of a storage system can assess risk of the storage system not being able to provide a data object. The rebuild node(s) uses information about data object fragments to determine health of a data object, which relates to the risk assessment. The rebuild node obtains object fragment information from nodes throughout the storage system. With the object fragment information, the rebuild node(s) can assess object risk based, at least in part, on the object fragments indicated as existing by the nodes. To assess object risk, the rebuild node(s) treats absent object fragments (i.e., those for which an indication was not received) as lost. When too many object fragments are lost, an object cannot be rebuilt. The erasure coding technique dictates the threshold number of fragments for rebuilding an object. The risk assessment per object influences rebuild of the objects.

Claims

1. A computer implemented method comprising:

transmitting requests to a plurality of storage nodes of a storage system to obtain from the storage nodes indications of availability of constituent fragments of a first data object, wherein the first data object is divided into the constituent fragments stored in the storage system according to an erasure coding technique;

quantifying a first risk of losing capability to rebuild the first data object based on the indications of the availability of the constituent fragments of the first data object for rebuilding the first data object according to the erasure coding technique; and

in response to the quantified first risk exceeding a first threshold, prioritizing rebuild of the first data object by the storage system according to the quantified first risk.

2. The method of claim 1, wherein the quantified first risk is determined from a set of discrete degrees of risk.

3. The method of claim 1, wherein quantifying the first risk of losing capability to rebuild the first data object further comprises:

determining a count of the indications of availability of constituent fragments for the first data object; and

computing a risk value as a function of the count of the indications of availability of constituent fragments and a minimum number of constituent fragments to rebuild the first data object according to the erasure coding technique.

4. The method of claim 1, wherein quantifying the first risk of losing capability to rebuild the first data object is further based on fragment health related information for a storage device of the storage system on which one or more of the constituent fragments are stored.

5. The method of claim 1, wherein quantifying the first risk of losing capability to rebuild the first data object is further based on computed risk coefficients for the constituent fragments of the first data object based on fragment health related information for a storage device of the storage system on which one or more of the constituent fragments are stored.

6. The method of claim 1, wherein quantifying the first risk of losing capability to rebuild the first data object is further based on heath related information for network elements of the storage system pertaining to the first data object.

7. The method of claim 1 further comprising quantifying a second risk for a second data object in response to a determination that the quantified first risk for the first data object exceeds a second threshold.

8. The method of claim 1 further comprising obtaining constituent fragments corresponding to a second data object while quantifying the first risk of losing capability to rebuild the first data object.

9. The method of claim 1, wherein the obtained indications of the availability of constituent fragments comprise object identifiers and a count of the availability of constituent fragments at corresponding storage nodes.

10. The method of claim 1 wherein the obtaining the availability of the constituent fragments and the quantifying of the first risk of losing capability to rebuild the first data object occur within a set of storage nodes assigned to a region of a namespace encompassing the first data object.

11. The method of claim 1, wherein requesting the rebuild of the first data object comprises submitting a request to retrieve the first data object.

12. The computer implemented method of claim 1 further comprising:

re-quantifying the first risk when a constituent fragment of the first data object is updated.

13. One or more non-transitory machine-readable media including program code for data object rebuild according to an erasure code of a storage system, the program code configured to:

in response to receipt of indications of availability of data object fragments for data object rebuild from a plurality of storage nodes of the storage system, quantify risks of losing a capability to rebuild each of one or more of data objects corresponding to the data object fragments based on a count of data object fragments indicated as available for rebuild of a corresponding data object relative to a minimum number of data object fragments according to the erasure code;

prioritize rebuild of the data objects based on the quantified risks of the data objects; and

initiate rebuild, within a background execution space, of the data objects according to the prioritization.

14. The one or more non-transitory machine-readable media of claim 13 further comprising program code configured to periodically obtain the indications of availability of data object fragments from the plurality of storage nodes.

15. The one or more non-transitory machine-readable media of claim 13, wherein the program code configured to quantify risks based on a count of data object fragments is further based on health related information of the data object fragments received from the plurality of storage nodes.

16. The one or more non-transitory machine-readable media of claim 13, wherein the program code configured to quantify risks is further configured to re-quantify the quantified risks of the data objects when one or more data object fragments of the data objects is updated.

17. An apparatus comprising:

a hardware processor; and

a machine-readable medium including program code executable by the processor to cause the apparatus to,

obtain, from a plurality of storage nodes of a storage system, indications of availability of constituent fragments for data objects, wherein each of the data objects is divided into constituent fragments stored in the storage system according to an erasure coding technique;

for each of the data objects, quantify risk of losing capability to rebuild the respective data object based on the indications of availability of the constituent fragments for the respective data object;

compute a risk value as a function of a count of available constituent fragments and a minimum number of constituent fragments to rebuild each data object according to the erasure coding technique; and

request rebuild of those of the data objects with a corresponding risk value that exceeds a threshold such that the rebuild of the data objects is prioritized according to the corresponding risk.

18. The apparatus of claim 17, wherein the quantified risk of losing capability is determined from a set of discrete degrees of risk.

19. The apparatus of claim 17, wherein the machine-readable medium including program code configured to quantify risk of losing capability to rebuild the respective data object based on the indications of availability of the constituent fragments is further based on fragment health related information obtained from at least one storage device storing the constituent fragments.

20. The apparatus of claim 17 wherein the program code executable by the process to cause the apparatus to compute the risk value further comprises re-compute the risk value for each data object when a constituent fragment of a respective data object is updated.