Rebuilding slices in a dispersed storage network

• US 10,387,080 B2
• Filed: 10/25/2018
• Issued: 08/20/2019
• Est. Priority Date: 11/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Dhuse, Greg R., Horan, Scott M., Khadiwala, Ravi V., Leggette, Wesley B., Motwani, Manish, Resch, Jason K., Viraraghavan, Praveen, Volvovski, Ilya, Vossberg, Trevor J., Wozniak, Ethan S.
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US16/170,106
• Publication Number:
  US 20190065070A1
• Time in Patent Office: 299 Days
• Field of Search: None
• 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/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2211/1007 Addressing errors, i.e. silent errors in RAID, e.g. sector slipping and addressing errors
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 2212/403 Error protection encoding, e.g. using parity or ECC codes
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 : Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0665 : at area level, e.g. provisioning of virtual or logical volumes
• 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
• CPC Class Codes: G06F 9/4881 : Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5083 : Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H03M 13/1105 : Decoding
• CPC Class Codes: H03M 13/1515 : Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 : using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H03M 13/616 : Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H03M 13/6502 : Reduction of hardware complexity or efficient processing
• CPC Class Codes: H04L 2101/604 : Address structures or formats
• CPC Class Codes: H04L 61/457 : containing identifiers of data entities on a computer, e.g. file names
• CPC Class Codes: H04L 63/101 : Access control lists [ACL]
• 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 method for use in a dispersed storage network operates to select a recovery of selected ones of one or more first sets of encoded data slices in response to detecting a storage error associated with the selected ones of the one or more first sets of encoded data slices; issue requests for a second decode threshold number of encoded data slices of selected ones of one or more second sets of encoded data slices corresponding to the selected ones of the one or more first sets of encoded data slices; decode the second decode threshold number of encoded data slices to produce recovered data in response to receiving the second decode threshold number of encoded data slices; encode the recovered data utilizing first IDA parameters associated with the first IDA to produce one or more rebuilt encoded data slices corresponding to the selected ones of the one or more first sets of encoded data slices; and facilitate storage of the one or more rebuilt encoded data slices.

Claims

1. A method for execution by a processing system of a dispersed storage and task (DST) integrity processing unit that includes a processor, the method comprises:

detecting a storage error associated with selected ones of one or more first sets of encoded data slices, wherein data is stored as the one or more first sets of encoded data slices in a plurality of dispersed storage and task execution (DSTE) units, the one or more first sets of encoded data slices encoded utilizing a first information dispersal algorithm (IDA) having a first decode threshold number, wherein the data is also stored as one or more second sets of encoded data slices in a subset of the plurality of DSTE units, the one or more second sets of encoded data slices encoded utilizing a second IDA having a second decode threshold number;

issuing requests for a second decode threshold number of encoded data slices of selected ones of the one or more second sets of encoded data slices corresponding to the selected ones of the one or more first sets of encoded data slices;

decoding the second decode threshold number of encoded data slices to produce recovered data in response to receiving the second decode threshold number of encoded data slices;

encoding the recovered data utilizing first IDA parameters associated with the first IDA to produce one or more rebuilt encoded data slices corresponding to the selected ones of the one or more first sets of encoded data slices; and

facilitating storage of the one or more rebuilt encoded data slices.

2. The method of claim 1 further comprising:

identifying that the data is also stored as the one or more second sets of encoded data slices in the subset of the plurality of DSTE units.

3. The method of claim 1 further comprising:

identifying that the second decode threshold number is less than the first decode threshold number.

4. The method of claim 1 wherein issuing the requests for the second decode threshold number of encoded data slices includes identifying one or more of the subset of the plurality of DSTE units, generating read slice requests, and sending the read slice requests to the one or more of the subset of the plurality of DSTE units.

5. The method of claim 1 wherein decoding the second decode threshold number of encoded data slices includes identifying second IDA parameters for the second decode threshold number of encoded data slices, the IDA parameters corresponding to the second IDA, and dispersed storage error decoding the second decode threshold number of encoded data slices utilizing the second IDA parameters to produce the recovered data.

6. The method of claim 1 wherein encoding the recovered data includes identifying the first IDA parameters and utilizing the first IDA parameters to produce the rebuilt encoded data slice.

7. The method of claim 1 wherein facilitating the storage of the rebuilt encoded data slice includes identifying one or more of the plurality of DSTE units associated with the selected ones of the one or more first sets of encoded data slices and sending the rebuilt encoded data slice to the one or more of the plurality of DSTE units for storage.

8. A processing system of a first dispersed storage and task (DST) integrity processing unit comprises:

at least one processor;

a memory that stores operational instructions, that when executed by the at least one processor cause the processing system to perform operations including;

detecting a storage error associated with selected ones of one or more first sets of encoded data slices, wherein data is stored as the one or more first sets of encoded data slices in a plurality of dispersed storage and task execution (DSTE) units, the one or more first sets of encoded data slices encoded utilizing a first information dispersal algorithm (IDA) having a first decode threshold number, wherein the data is also stored as one or more second sets of encoded data slices in a subset of the plurality of DSTE units, the one or more second sets of encoded data slices encoded utilizing a second IDA having a second decode threshold number;

issue requests for a second decode threshold number of encoded data slices of selected ones of the one or more second sets of encoded data slices corresponding to the selected ones of the one or more first sets of encoded data slices;

decode the second decode threshold number of encoded data slices to produce recovered data in response to receiving the second decode threshold number of encoded data slices;

encode the recovered data utilizing first IDA parameters associated with the first IDA to produce one or more rebuilt encoded data slices corresponding to the selected ones of the one or more first sets of encoded data slices; and

facilitate storage of the one or more rebuilt encoded data slices.

9. The processing system of claim 8 wherein the operations further include:

identifying that the data is also stored as the one or more second sets of encoded data slices in the subset of the plurality of DSTE units.

10. The processing system of claim 8 wherein the operations further include:

identifying that the second decode threshold number is less than the first decode threshold number.

11. The processing system of claim 8 wherein issuing the requests for the second decode threshold number of encoded data slices includes identifying one or more of the subset of the plurality of DSTE units, generating read slice requests, and sending the read slice requests to the one or more of the subset of the plurality of DSTE units.

12. The processing system of claim 8 wherein decoding the second decode threshold number of encoded data slices includes identifying second IDA parameters for the second decode threshold number of encoded data slices, the IDA parameters corresponding to the second IDA, and dispersed storage error decoding the second decode threshold number of encoded data slices utilizing the second IDA parameters to produce the recovered data.

13. The processing system of claim 8 wherein encoding the recovered data includes identifying the first IDA parameters and utilizing the first IDA parameters to produce the rebuilt encoded data slice.

14. The processing system of claim 8 wherein facilitating the storage of the rebuilt encoded data slice includes identifying one or more of the plurality of DSTE units associated with the selected ones of the one or more first sets of encoded data slices and sending the rebuilt encoded data slice to the one or more of the plurality of DSTE units for storage.

15. A non-transitory computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by a processing system of a dispersed storage network (DSN) that includes a processor and a memory, causes the processing system to perform operations that include;

detecting a storage error associated with selected ones of one or more first sets of encoded data slices, wherein data is stored as the one or more first sets of encoded data slices in a plurality of dispersed storage and task execution (DSTE) units, the one or more first sets of encoded data slices encoded utilizing a first information dispersal algorithm (IDA) having a first decode threshold number, wherein the data is also stored as one or more second sets of encoded data slices in a subset of the plurality of DSTE units, the one or more second sets of encoded data slices encoded utilizing a second IDA having a second decode threshold number;

issue requests for a second decode threshold number of encoded data slices of selected ones of the one or more second sets of encoded data slices corresponding to the selected ones of the one or more first sets of encoded data slices;

decode the second decode threshold number of encoded data slices to produce recovered data in response to receiving the second decode threshold number of encoded data slices;

encode the recovered data utilizing first IDA parameters associated with the first IDA to produce one or more rebuilt encoded data slices corresponding to the selected ones of the one or more first sets of encoded data slices; and

facilitate storage of the one or more rebuilt encoded data slices.

16. The non-transitory computer readable storage medium of claim 15 wherein the operations further include:

identifying that the data is also stored as the one or more second sets of encoded data slices in the subset of the plurality of DSTE units and identifying that the second decode threshold number is less than the first decode threshold number.

17. The non-transitory computer readable storage medium of claim 15 wherein the operations further include:

identifying one or more of the subset of the plurality of DSTE units, generating read slice requests, and sending the read slice requests to the one or more of the subset of the plurality of DSTE units.

18. The non-transitory computer readable storage medium of claim 15 wherein decoding the second decode threshold number of encoded data slices includes identifying second IDA parameters for the second decode threshold number of encoded data slices, the IDA parameters corresponding to the second IDA, and dispersed storage error decoding the second decode threshold number of encoded data slices utilizing the second IDA parameters to produce the recovered data.

19. The non-transitory computer readable storage medium of claim 15 wherein encoding the recovered data includes identifying the first IDA parameters and utilizing the first IDA parameters to produce the rebuilt encoded data slice.

20. The non-transitory computer readable storage medium of claim 15 wherein facilitating the storage of the rebuilt encoded data slice includes identifying one or more of the plurality of DSTE units associated with the selected ones of the one or more first sets of encoded data slices and sending the rebuilt encoded data slice to the one or more of the plurality of DSTE units for storage.