Method and apparatus for distributed storage integrity processing

• US 10,387,256 B2
• Filed: 06/02/2017
• Issued: 08/20/2019
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Dhuse, Greg, Baptist, Andrew, Mark, Zachary J., Resch, Jason K., Volvovski, Ilya
• Primary Examiner(s): Truong, Loan L. T.
• Application Number:
  US15/612,243
• Publication Number:
  US 20170270003A1
• Time in Patent Office: 809 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 11/2056 by mirroring
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• 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]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A distributed storage integrity system in a dispersed storage network includes a scanning agent and a control unit. The scanning agent identifies an encoded data slice that requires rebuilding, wherein the encoded data slice is one of a plurality of encoded data slices generated from a data segment using an error encoding dispersal function. The control unit retrieves at least a number T of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function. The control unit is operable to reconstruct the data segment from at least the number T of the encoded data slices and generate a rebuilt encoded data slice from the reconstructed data segment. The scanning agent is located in a storage unit and the control unit is located in the storage unit or in a storage integrity processing unit, a dispersed storage processing unit or a dispersed storage managing unit.

Claims

1. A storage integrity processing unit in a distributed storage network, comprises:

a rebuild queue including non-transitory memory that stores a plurality of identifications of data slices that require rebuilding; and

at least one rebuild module utilizing processing hardware operable to;

select one of the plurality of identifications of data slices from the rebuild queue based on a priority of a selected data slice associated with the select one of the plurality of identifications of data slices, wherein the selected data slice is one of a number of a plurality of encoded data slices of an encoded data segment;

reconstruct the encoded data segment from at least a threshold number of the number of the plurality of encoded data slices of the encoded data segment to generate a reconstructed data segment; and

generate a rebuilt encoded data slice corresponding to the selected data slice from the reconstructed data segment.

2. The storage integrity processing unit of claim 1, further comprising:

a network interface for interfacing with a plurality of storage units in the distributed storage network; and

at least one scanning agent operable to;

scan an address range of encoded data slices stored in the plurality of storage units;

identify an encoded data slice having an address within the address range that requires rebuilding to generate an identified data slice.

3. The storage integrity processing unit of claim 2, wherein the address range of encoded data slices corresponds to a portion of a virtual DSN (dispersed storage network) addressing space.

4. The storage integrity processing unit of claim 3, wherein the portion of the virtual DSN addressing space is a portion of a user vault, wherein the user vault includes a virtual DSN address space associated with a user device.

5. The storage integrity processing unit of claim 3, wherein the portion of the virtual DSN addressing space corresponds to a portion of at least one pillar of a user vault, wherein the user vault includes a virtual DSN address space associated with a user device and wherein a number of pillars of the user vault equals the number of encoded data slices of an encoded data segment for the user vault set in accordance data storage parameters and an error coding scheme.

6. The storage integrity processing unit of claim 1, wherein the at least one rebuild module is further operable to:

determine a slice name of the identified data slice, wherein the slice name includes a vault identifier that identifies a user vault from a physical address table; and

store the slice name of the identified slice in the rebuild queue as one of the plurality of identifications of data slices that require rebuilding.

7. The storage integrity processing unit of claim 1, wherein the encoded data segment is one of a plurality of encoded data segments of a data object and wherein the priority is associated with the data object.

8. The storage integrity processing unit of claim 7, wherein the priority associated with the data object includes at least one of:

a priority indicator for the data object, a priority indicator of a user associated with the data object, a priority indicator for a data object type, or a priority indicator based on a data slice age.

9. The storage integrity processing unit of claim 1, wherein the threshold number corresponds to a threshold number of the number of the plurality of encoded data slices needed to reconstruct the encoded data segment based on an error encoding dispersal function, wherein the number of the plurality of encoded data slices of the encoded data segment is equal to a threshold number of the number of the plurality of encoded data slices.

10. The storage integrity processing unit of claim 9, wherein the rebuild module is operable to reconstruct the encoded data segment from at least the threshold number of the plurality of encoded data slices of by:

decoding at least the threshold number of the plurality of encoded data slices using a decoding matrix in accordance with an error encoding dispersal function.

11. The storage integrity processing unit of claim 10, wherein the rebuild module is operable to decode at least the threshold number of the plurality of encoded data slices using a decoding matrix by:

deslicing at least the threshold number of the plurality of encoded data slices to generate a portion of an encoded data segment; and

multiplying the portion of the encoded data segment with the decoding matrix, wherein the decoding matrix is an MxR matrix, wherein the decoding matrix includes a number R of rows equal to the number of the plurality of encoded data slices and includes a number M of columns equal to the threshold number of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function.

12. A device in a dispersed storage network comprising:

a network interface for interfacing with a plurality of storage units in the dispersed storage network; and

at least one scanning agent utilizing processing hardware operable to;

identify an encoded data slice having an address within an address range that requires rebuilding to generate an identified data slice, wherein the identified data slice is one of an X number of a plurality of encoded data slices of an encoded data segment;

at least one rebuild module operable to;

reconstruct the encoded data segment from at least a threshold number T of the X number of the plurality of encoded data slices of the encoded data segment to generate a reconstructed data segment; and

generate a rebuilt encoded data slice corresponding to the identified data slice from the reconstructed data segment.

13. The device of claim 12, wherein the address range corresponds to a portion of a virtual DSN (dispersed storage network) addressing space.

14. The device of claim 13, wherein the portion of the virtual DSN addressing space is a portion of a user vault, wherein the user vault includes a virtual DSN address space associated with a user device.

15. The device of claim 13, wherein the portion of the virtual DSN addressing space corresponds to a portion of at least one pillar of a user vault, wherein the user vault includes a virtual DSN address space associated with a user device and wherein a number of pillars of the user vault equals the X number of encoded data slices of an encoded data segment for the user vault set in accordance data storage parameters and an error coding scheme.

16. The device of claim 12, wherein the at least one scanning agent is further operable to:

determine a slice name of the identified data slice, wherein the slice name includes a vault identifier that identifies a user vault; and

store the slice name of the identified slice in a rebuild queue as one of a plurality of identifications of data slices that require rebuilding.

17. A method in a device, comprising:

identifying an encoded data slice having an address within an address range stored in one of a plurality of storage units that requires rebuilding to generate an identified data slice, wherein the identified data slice is one of an X number of a plurality of encoded data slices of an encoded data segment;

reconstructing the encoded data segment from at least a threshold number T of the X number of the plurality of encoded data slices of the encoded data segment to generate a reconstructed data segment; and

generating a rebuilt encoded data slice corresponding to the identified data slice from the reconstructed data segment; and

storing the rebuilt encoded data slice in the one of the plurality of storage units.

18. The method of claim 17, wherein the address range of encoded data slices corresponds to a portion of a virtual DSN addressing space.

19. The method of claim 18, wherein the portion of the virtual DSN addressing space is a portion of a user vault, wherein the user vault includes a virtual DSN address space associated with a user device.

20. The method of claim 18, wherein the portion of the virtual DSN addressing space corresponds to a portion of at least one pillar of a user vault, wherein the user vault includes a virtual DSN address space associated with a user device and wherein a number of pillars of the user vault equals the X number of encoded data slices of an encoded data segment for the user vault set in accordance data storage parameters and an error coding scheme.