Distributed rebuilding of data in a dispersed storage network

• US 9,774,680 B2
• Filed: 07/31/2014
• Issued: 09/26/2017
• Est. Priority Date: 01/28/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Vas, Sebastien, Resch, Jason K.
• Primary Examiner(s): Faal, Baboucarr
• Application Number:
  US14/447,909
• Publication Number:
  US 20140344646A1
• Time in Patent Office: 1,153 Days
• 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 data slices in a dispersed storage network when detecting a plurality of data slices that require rebuilding. A plurality of rebuilding resources capable for use to rebuild the plurality of data slices are determined and based on an attribute associated with the determination, a rebuilding task is apportioned and the apportioned tasks are assigned to the plurality of rebuilding resources to rebuild the data slices. The apportionment of the tasks permit more than one rebuilding resource and associated distributed storage unit to perform the rebuild of the data slices.

Claims

1. A method comprises:

detecting, by a first storage unit of a set of storage units of a dispersed storage network (DSN), a failed memory device of a plurality of memory devices of the first storage unit, 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 pluralities of sets of encoded data slices corresponding to a plurality of data objects as a first grouping of encoded data slices; and

the first storage unit stores a sub-group of the first grouping of encoded data slices in the failed memory device;

determining, by the first storage unit, to rebuild the sub-group of the first grouping of encoded data slices locally or distributedly, wherein the determination is based, at least in part, on an estimate of the load to rebuild the sub-group of the first grouping of encoded data slices by the first storage unit; and

when determined to rebuild the sub-group of the first grouping of encoded data slices distributedly;

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

allocating rebuilding assignments of the sub-group of the first grouping of encoded data slices among the identified rebuilding resources; and

rebuilding, by the identified rebuilding resources, the sub-group of the first grouping of encoded data slices.

2. The method of claim 1 further comprises:

when determined to rebuild the sub-group of the first grouping of encoded data slices locally;

requesting, by the rebuilding resource of the first storage unit for at least some other storage units of the set of storage units, a decode threshold number of encoded data slices of a set of encoded data slices of the pluralities of sets of encoded data slices regarding an encoded data slice of the sub-group of the first grouping of encoded data slices;

receiving the decode threshold number of encoded data slices;

decoding the decode threshold number of encoded data slices to produce a recovered 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 sub-group of the first grouping of encoded data slices; and

storing, by the first storage unit, the rebuilt encoded data slice.

3. The method of claim 1, wherein the determining to rebuild the sub-group of the first grouping of encoded data slices locally or distributedly further comprises:

determining to rebuild distributedly when the estimate of the load to rebuild is above a rebuilding loading threshold; and

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

4. The method of claim 1, wherein the determining to rebuild the sub-group of the first grouping of encoded data slices locally or distributedly is further 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 storage set query.

5. The method of claim 1, wherein identifying two or more rebuilding resources comprises:

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 unit storage set indicator, a storage unit storage set, system module availability indicator, a query, a list, a predetermination, a message, or a command.

6. The method of claim 1, wherein allocating rebuilding assignments comprises one or more of:

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 sub-group of the first grouping of encoded data slices;

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.

7. The method of claim 1, wherein the rebuilding an encoded data slice of the sub-group of the first grouping of encoded data slices comprises:

requesting, by a rebuilding resource of one of the two or more identified rebuilding resources, a decode threshold number of encoded data slices of a set of encoded data slices of the pluralities of sets of encoded data slices regarding an encoded data slice of the sub-group of the first grouping 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 sub-group of the first grouping of encoded data slices; and

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

8. The method of claim 1 further comprises:

storing, by the first storage unit, rebuilt encoded data slices corresponding to the sub-group of the first grouping of encoded data slices in a new memory device or another one of the plurality of memory devices of the first storage unit.

9. A computer readable memory comprises:

a first memory section that stores operational instructions that, when executed by a first storage unit of a set of storage units of a dispersed storage network (DSN), causes the first storage unit to;

detect a failed memory device of a plurality of memory devices of the first storage unit, 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 pluralities of sets of encoded data slices corresponding to a plurality of data objects as a first grouping of encoded data slices; and

the first storage unit stores a sub-group of the first grouping of encoded data slices in the failed memory device;

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

determine to rebuild the sub-group of the first grouping of encoded data slices locally or distributedly, wherein the determination is based, at least in part, on an estimate of the load to rebuild the sub-group of the first grouping of encoded data slices; and

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

when determined to rebuild the sub-group of the first grouping of encoded data slices distributedly;

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

allocate rebuilding assignments of the sub-group of the first grouping of encoded data slices among the identified rebuilding resources; 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 sub-group of the first grouping of encoded data slices.

10. The computer readable memory of claim 9 further comprises:

the second memory section further stores operational instructions that, when executed by the first storage unit, causes the first storage unit to determine to rebuild the sub-group of the first grouping of encoded data slices locally; and

a fifth memory section that stores operational instructions that, when executed by the first storage 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 pluralities of sets of encoded data slices regarding an encoded data slice of the sub-group of the first grouping of 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 sub-group of the first grouping of encoded data slices; and

store the rebuilt encoded data slice.

11. The computer readable memory of claim 9, wherein the second memory section further stores operational instructions that, when executed by the first storage unit, causes the first storage unit to determine to rebuild the sub-group of the first grouping of encoded data slices locally or distributedly further by:

determining to rebuild distributedly when the estimate of the load to rebuild is above a rebuilding loading threshold; and

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

12. The computer readable memory of claim 9, wherein the second memory section further stores operational instructions that, when executed by the first storage unit, causes the first storage unit to determine to rebuild the sub-group of the first grouping of encoded data slices locally or distributedly based on one or more of:

a number of 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 storage set query.

13. The computer readable memory of claim 9, wherein the third memory section stores operational instructions that, when executed by the first storage unit, causes the first storage unit to identify 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 unit storage set indicator, a storage unit storage set, system module availability indicator, a query, a list, a predetermination, a message, or a command.

14. The computer readable memory of claim 9, wherein the third memory section stores operational instructions that, when executed by the first storage unit, causes the first storage unit to allocate rebuilding assignments by one or more of:

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 sub-group of the first grouping of encoded data slices;

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.

15. The computer readable memory of claim 9, 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 sub-group of the first grouping of encoded data slices by:

requesting a decode threshold number of encoded data slices of a set of encoded data slices of the pluralities of sets of encoded data slices regarding an encoded data slice of the sub-group of the first grouping 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 sub-group of the first grouping of encoded data slices; and

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

16. The computer readable memory of claim 9 further comprises:

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

store rebuilt encoded data slices corresponding to the sub-group of the first grouping of encoded data slices in a new memory device or another one of the plurality of memory devices of the first storage unit.