Distributed rebuilding of data in a dispersed storage network

• US 9,900,387 B2
• Filed: 08/18/2017
• Issued: 02/20/2018
• Est. Priority Date: 01/28/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Vas, Sebastien, Resch, Jason K.
• Primary Examiner(s): Faal, Baboucarr
• Application Number:
  US15/681,026
• Publication Number:
  US 20170346901A1
• Time in Patent Office: 186 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A technique of rebuilding encoded data slices in a dispersed storage network when detecting a plurality of encoded data slices that require rebuilding, as may occur upon failure of a memory device storing the encoded data slices. A plurality of rebuilding resources capable for use to rebuild the plurality of data slices are determined and, based on one or more attributes associated with the determination, a rebuilding task is apportioned. The resulting rebuilding assignments are allocated to the plurality of rebuilding resources to rebuild the encoded data slices. The allocation of the rebuilding assignments permits more than one rebuilding resource and associated distributed storage units to rebuild the encoded data slices.

Claims

1. A method comprises:

storing a plurality of encoded data slices in a memory device of a first storage unit of a set of storage units of a dispersed storage network (DSN), wherein each encoded data slice of the plurality of encoded data slices is a dispersed storage error encoded portion of a respective segment of a data object;

determining that the stored plurality of encoded data slices require rebuilding;

determining, by the first storage unit, to rebuild the stored plurality of encoded data slices in a distributed manner;

identifying at least two additional storage units of the set of storage units having rebuilding resources;

allocating rebuilding assignments among the at least two additional storage units for generating a rebuilt plurality of encoded data slices corresponding to the stored plurality of encoded data slices, including assigning a rebuilding assignment of the rebuilding assignments to one of the at least two additional storage units based on a pillar number of an encoded data slice of the stored plurality of encoded data slices;

sending the rebuilding assignments to the at least two additional storage units;

receiving, in response to the rebuilding assignments, the rebuilt plurality of encoded data slices; and

storing the rebuilt plurality of encoded data slices in the first storage unit.

2. The method of claim 1, wherein the determining that the stored plurality of encoded data slices require rebuilding is based on at least one of:

receiving a message from a storage integrity processor of the DSN;

or

detecting a failure or reliability issue regarding the memory device of the first storage unit.

3. The method of claim 1, wherein the determining to rebuild the stored plurality of encoded data slices includes determining that a number of encoded data slice errors meets a rebuilding error threshold value.

4. The method of claim 1, wherein the determining to rebuild the stored plurality of encoded data slices in a distributed manner is based, at least in part, on an estimate of the load to rebuild the stored plurality of encoded data slices by the first storage unit.

5. The method of claim 1, wherein the determining to rebuild the stored plurality of encoded data slices in a distributed manner is based on one or more of:

a number of encoded data slices that require rebuilding, a storage unit loading indicator, a storage unit capacity indicator, a rebuilding error threshold, an error list, a number of errors, a comparison of the number of errors to the rebuilding error threshold, a command, a message, a local storage unit query, or a storage unit query.

6. The method of claim 1, wherein identifying at least two additional storage units of the set of storage units having rebuilding resources includes:

identifying candidate rebuilding resources of the at least two additional storage units of the set of storage units; and

selecting two or more rebuilding resources from the candidate rebuilding resources based on one or more of;

a storage unit availability, a storage unit capacity indicator, a storage unit loading indicator, a storage unit proximity to the first storage unit, a storage unit storage set affiliation, a system module availability indicator, a query, a list, a predetermination, a message, or a command.

7. The method of claim 1, wherein allocating rebuilding assignments further includes one or more of:

assigning the rebuilding assignment of the rebuilding assignments to one of the at least two additional storage units based on performance capabilities of the one of the at least two additional storage units;

or

assigning the rebuilding assignment of the rebuilding assignments to one of the at least two additional storage units based on the one of the at least two additional storage units being collocated in a site with the first storage unit.

8. The method of claim 1, wherein generating the rebuilt plurality of encoded data slices comprises:

requesting, by a rebuilding resource of one of the at least two additional storage units, a decode threshold number of encoded data slices of a set of encoded data slices associated with an encoded data slice of the stored plurality of encoded data slices;

receiving the decode threshold number of encoded data slices;

decoding the decode threshold number of encoded data slices to recover a data segment;

dispersed storage error encoding the recovered data segment to produce a set of rebuilt encoded data slices;

selecting a rebuilt encoded data slice of the set of rebuilt encoded data slices as a rebuilt version of the encoded data slice of the stored plurality of encoded data slices; and

sending the rebuilt encoded data slice to the first storage unit for storage therein.

9. The method of claim 1, wherein storing the rebuilt plurality of encoded data slices in the first storage unit includes:

storing, by the first storage unit, the rebuilt plurality of encoded data slices in a new memory device or another memory device of the first storage unit.

10. A non-transitory computer readable memory comprises:

a first memory section that stores operational instructions that, when executed by a processing unit of a dispersed storage network (DSN), causes the processing unit to detect a failed memory device of a plurality of memory devices of a first storage unit of a set of storage units of the DSN, wherein;

each storage unit of the set of storage units includes a plurality of memory devices and a processing module;

the processing module includes a rebuilding resource;

a data object is divided into a plurality of data segments;

a data segment of the plurality of data segments is dispersed storage error encoded into a set of encoded data slices;

the first storage unit stores first encoded data slices of a plurality of sets of encoded data slices corresponding to the data object; and

the first storage unit stores the first encoded data slices in the failed memory device;

a second memory section that stores operational instructions that, when executed by the processing unit, causes the processing unit to determine to rebuild the first encoded data slices distributedly or locally with respect to the first storage unit;

a third memory section that stores operational instructions that, when executed by the processing unit, causes the processing unit to;

when determined to rebuild the first encoded data slices distributedly;

identify two or more rebuilding resources from the rebuilding resources of the set of storage units; and

allocate rebuilding assignments among the identified rebuilding resources for generating a rebuilt plurality of encoded data slices corresponding to the first encoded data slices, including assigning a rebuilding assignment of the rebuilding assignments to one of the identified rebuilding resources based on a pillar number of an encoded data slice of the first encoded data slices; and

a fourth memory section that stores operational instructions that, when executed by the identified rebuilding resources, causes the identified rebuilding resources to rebuild the first encoded data slices.

11. The non-transitory computer readable memory of claim 10 further comprises:

the second memory section further stores operational instructions that, when executed by the processing unit, causes the processing unit to determine to rebuild the first encoded data slices locally; and

a fifth memory section that stores operational instructions that, when executed by the processing unit, causes the first storage unit to;

request a decode threshold number of encoded data slices of a set of encoded data slices of the plurality of sets of encoded data slices associated with an encoded data slice of the first encoded data slices;

receive the decode threshold number of encoded data slices;

decode the decode threshold number of encoded data slices to produce a recovered data segment;

dispersed storage error encode the recovered data segment to produce a set of rebuilt encoded data slices;

select a rebuilt encoded data slice of the set of rebuilt encoded data slices as a rebuilt version of the encoded data slice of the first encoded data slices; and

store the rebuilt encoded data slice in a memory device of the first storage unit other than the failed memory device.

12. The non-transitory computer readable memory of claim 10, wherein the second memory section further stores operational instructions that, when executed by the processing unit, causes the processing unit to determine to rebuild the first encoded data slices distributedly or locally further by:

determining to rebuild distributedly when an estimate of the load to rebuild the first encoded data slices by the rebuilding resource of the first storage unit is above a threshold; and

determining to rebuild locally when the estimate of the load to rebuild is at or below the threshold.

13. The non-transitory computer readable memory of claim 10, wherein the second memory section further stores operational instructions that, when executed by the processing unit, causes the processing unit to determine to rebuild the first encoded data slices distributedly or locally based on one or more of:

a number of encoded data slices that require rebuilding, a storage unit capacity indicator, a rebuilding error threshold, an error list, a number of errors, a comparison of the number of errors to the rebuilding error threshold, or a storage unit query.

14. The non-transitory computer readable memory of claim 10, wherein the third memory section stores operational instructions that, when executed by the processing unit, causes the processing unit to identify the two or more rebuilding resources by:

identifying candidate rebuilding resources of the rebuilding resources of the set of storage units; and

selecting the two or more rebuilding resources from the candidate rebuilding resources based on one or more of;

a storage unit availability, a storage unit capacity indicator, a storage unit loading indicator, a storage unit proximity to a storage set indicator, a storage unit storage set, a query, a list, a predetermination, or a message.

15. The non-transitory computer readable memory of claim 10, wherein the third memory section stores operational instructions that, when executed by the processing unit, causes the processing unit to allocate rebuilding assignments by one or more of:

assigning the rebuilding assignment of the rebuilding assignments to one of the identified rebuilding resources based on performance capabilities of the one of the identified rebuilding resources;

or

assigning the rebuilding assignment of the rebuilding assignments to one of the identified rebuilding resources based on the one of the identified rebuilding resources being collocated in a site with the first storage unit.

16. The non-transitory computer readable memory of claim 10, wherein the fourth memory section further stores operational instructions that, when executed by one of the identified rebuilding resources, causes the one of the identified rebuilding resources to rebuild an encoded data slice of the first encoded data slices by:

requesting a decode threshold number of encoded data slices of a set of encoded data slices of the plurality of sets of encoded data slices regarding an encoded data slice of the first encoded data slices;

receiving the decode threshold number of encoded data slices;

decoding the decode threshold number of encoded data slices to recover a data segment;

dispersed storage error encoding the recovered data segment to produce a set of rebuilt encoded data slices;

selecting a rebuilt encoded data slice of the set of rebuilt encoded data slices as a rebuilt version of the encoded data slice of the first encoded data slices; and

sending the rebuilt encoded data slice to the first storage unit for storage therein.

17. The non-transitory computer readable memory of claim 10 further comprises:

a fifth memory section that stores operational instructions that, when executed by the processing unit, causes the processing unit to store rebuilt encoded data slices corresponding to the first encoded data slices in a memory device of the first storage unit other than the failed memory device.

18. The non-transitory computer readable memory of claim 10, wherein the first memory section further stores operational instructions that, when executed by the processing unit, causes the processing unit to detect the failed memory device of the first storage unit based one or more of:

determining that a calculated slice checksum for at least one encoded data slice of the first encoded data slices does not match a stored slice checksum;

a message from the first storage unit;

or

a query of the set of storage units when at least one storage unit of the set of storage units reports that there is at least one encoded data slice error.

19. The non-transitory computer readable memory of claim 10, wherein the first memory section further stores operational instructions that, when executed by the processing unit, causes the processing unit to determine slice names for the first encoded data slices.

20. The non-transitory computer readable memory of claim 10, wherein the processing unit is a storage integrity processing unit.