Optimized distributed rebuilding within a dispersed storage network

• US 10,437,677 B2
• Filed: 12/14/2017
• Issued: 10/08/2019
• Est. Priority Date: 02/27/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Resch, Jason K.
• Primary Examiner(s): Rubin, Blake J
• Application Number:
  US15/842,768
• Publication Number:
  US 20180107549A1
• Time in Patent Office: 663 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• 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/065 Replication 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: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method includes performing, by a storage unit, a rebuild scanning function to identify an encoded data slice in need of rebuilding. The method further includes identifying, by the storage unit, storage units in the set of storage units storing encoded data slices of the set of encoded data slices that are usable for rebuilding the encoded data slice in need of rebuilding. The method further includes selecting, by the storage unit, one of the identified storage units to rebuild the encoded data slice in need of rebuilding based on a selection protocol. The method further includes sending, by the storage unit, a rebuild command to the one of the identified storage units regarding rebuilding the encoded data slice in need of rebuilding, wherein, in accordance with a rebuilding function, the one of the identified storage units rebuilds the encoded data slice in need of rebuilding.

Claims

1. A method comprises:

performing, by a storage unit of a dispersed storage network (DSN), a rebuild scanning function to identify an encoded data slice in need of rebuilding, wherein the encoded data slice in need of rebuilding is one encoded data slice of a set of encoded data slices, wherein a data segment of a data object is dispersed storage error encoded into the set of encoded data slices, wherein the set of encoded data slices is stored in a set of storage units of the DSN, and wherein a decode threshold number of encoded data slices of the set of encoded data slices is needed to recover the data segment;

identifying, by the storage unit, storage units in the set of storage units storing encoded data slices of the set of encoded data slices that are usable for rebuilding the encoded data slice in need of rebuilding to produce identified storage units;

selecting, by the storage unit, one of the identified storage units to rebuild the encoded data slice in need of rebuilding based on a selection protocol; and

sending, by the storage unit, a rebuild command to the one of the identified storage units regarding rebuilding the encoded data slice in need of rebuilding, wherein, in accordance with a rebuilding function, the one of the identified storage units rebuilds the encoded data slice in need of rebuilding.

2. The method of claim 1, wherein performing the rebuild scanning function comprises:

issuing, by the storage unit, listing requests to at least some storage units of the set of storage units, wherein a listing request of the listing requests is requesting a particular storage unit of the at least some of the storage units to provide a list of slice names and revision levels of encoded data slices that the particular storage unit is storing;

receiving, by the storage unit, list responses for the at least storage units, wherein a list response of the list responses includes a list of slice names and revision levels of encoded data slices stored by a corresponding one of the at least some storage units;

for the set of encoded data slices, comparing, by the storage unit, corresponding list entries of the list responses to identify the encoded data slice in need of rebuilding.

3. The method of claim 2, wherein the comparing list entries comprises:

determining that a current revision level list entry regarding the encoded data slice in need of rebuilding is blank; and

determining that current revision level list entries regarding other encoded data slices of the set of encoded data slices contain slice names and a corresponding current revision level.

4. The method of claim 2, wherein the comparing list entries comprises:

determining that a previous revision level list entry regarding the encoded data slice in need of rebuilding is blank; and

determining that previous revision level list entries regarding other encoded data slices of the set of encoded data slices contain slice names and a corresponding previous revision level.

5. The method of claim 2, wherein the identifying the identified storage units comprises:

determining that a list entry regarding the encoded data slice in need of rebuilding is blank;

determining that list entries regarding other encoded data slices of the set of encoded data slices contain slice names and a corresponding revision level; and

identifying the identified storage units as the storage units that provided the list entries regarding the other encoded data slices of the set of encoded data slices contain slice names and the corresponding revision level.

6. The method of claim 1, wherein the selecting the one of the identified storage units comprises at least one of:

selecting the one of the identified storage units based on the one of the identified storage units storing an encoded data slice that will be used in the rebuilding of the encoded data slice in need of rebuilding;

selecting the one of the identified storage units based on the one of the identified storage units storing current and previous revision levels of the encoded data slice that will be used in the rebuilding of the encoded data slice in need of rebuilding;

selecting the one of the identified storage units based on the one of the identified storage units storing the encoded data slice that will be used in the rebuilding of the encoded data slice in need of rebuilding and based on the one of the identified storage units being in a site with another one of the identified storage units that stores another encoded data slice of the set of encoded data slices that will be used in the rebuilding of the encoded data slice in need of rebuilding; and

selecting the one of the identified storage units based on a pseudo random selection process.

7. The method of claim 1 further comprises:

sending, by the storage unit, identify of the identified storage units to assist the one of the identified storage units in the rebuilding of the encoded data slice in need of rebuilding.

8. A storage unit of a dispersed storage network (DSN), wherein the storage unit comprises:

an interface;

memory; and

a processing module operably coupled to the interface and to the memory, wherein the processing module is operable to;

perform a rebuild scanning function to identify an encoded data slice in need of rebuilding, wherein the encoded data slice in need of rebuilding is one encoded data slice of a set of encoded data slices, wherein a data segment of a data object is dispersed storage error encoded into the set of encoded data slices, wherein the set of encoded data slices is stored in a set of storage units of the DSN, and wherein a decode threshold number of encoded data slices of the set of encoded data slices is needed to recover the data segment;

identify storage units in the set of storage units storing encoded data slices of the set of encoded data slices that are usable for rebuilding the encoded data slice in need of rebuilding to produce identified storage units;

select one of the identified storage units to rebuild the encoded data slice in need of rebuilding based on a selection protocol; and

send, via the interface, a rebuild command to the one of the identified storage units regarding rebuilding the encoded data slice in need of rebuilding, wherein, in accordance with a rebuilding function, the one of the identified storage units rebuilds the encoded data slice in need of rebuilding.

9. The storage unit of claim 8, wherein the processing module is further operable to perform the rebuild scanning function by:

issue, via the interface, listing requests to at least some storage units of the set of storage units, wherein a listing request of the listing requests is requesting a particular storage unit of the at least some of the storage units to provide a list of slice names and revision levels of encoded data slices that the particular storage unit is storing;

receive, via the interface, list responses for the at least storage units, wherein a list response of the list responses includes a list of slice names and revision levels of encoded data slices stored by a corresponding one of the at least some storage units; and

for the set of encoded data slices, compare corresponding list entries of the list responses to identify the encoded data slice in need of rebuilding.

10. The storage unit of claim 9, wherein the processing module is further operable to compare the list entries by:

determining that a current revision level list entry regarding the encoded data slice in need of rebuilding is blank; and

determining that current revision level list entries regarding other encoded data slices of the set of encoded data slices contain slice names and a corresponding current revision level.

11. The storage unit of claim 9, wherein the processing module is further operable to compare the list entries by:

determining that a previous revision level list entry regarding the encoded data slice in need of rebuilding is blank; and

determining that previous revision level list entries regarding other encoded data slices of the set of encoded data slices contain slice names and a corresponding previous revision level.

12. The storage unit of claim 9, wherein the processing module is further operable to identify the identified storage units by:

determining that a list entry regarding the encoded data slice in need of rebuilding is blank;

determining that list entries regarding other encoded data slices of the set of encoded data slices contain slice names and a corresponding revision level; and

identifying the identified storage units as the storage units that provided the list entries regarding the other encoded data slices of the set of encoded data slices contain slice names and the corresponding revision level.

13. The storage unit of claim 8, wherein the processing module is further operable to select the one of the identified storage units by at least one of:

selecting the one of the identified storage units based on the one of the identified storage units storing an encoded data slice that will be used in the rebuilding of the encoded data slice in need of rebuilding;

selecting the one of the identified storage units based on the one of the identified storage units storing current and previous revision levels of the encoded data slice that will be used in the rebuilding of the encoded data slice in need of rebuilding;

selecting the one of the identified storage units based on the one of the identified storage units storing the encoded data slice that will be used in the rebuilding of the encoded data slice in need of rebuilding and based on the one of the identified storage units being in a site with another one of the identified storage units that stores another encoded data slice of the set of encoded data slices that will be used in the rebuilding of the encoded data slice in need of rebuilding; and

selecting the one of the identified storage units based on a pseudo random selection process.

14. The storage unit of claim 8, wherein the processing module is further operable to:

send, via the interface, identify of the identified storage units to assist the one of the identified storage units in the rebuilding of the encoded data slice in need of rebuilding.