Missing slice reconstruction in a dispersed storage network

• US 10,013,309 B2
• Filed: 08/17/2016
• Issued: 07/03/2018
• Est. Priority Date: 08/17/2016
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Cilfone, Bart R.
• Primary Examiner(s): Rizk, Sam
• Application Number:
  US15/238,791
• Publication Number:
  US 20180052734A1
• Time in Patent Office: 685 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 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/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of 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

Abstract

A method for execution by a processing system of a dispersed storage network includes receiving first slices encoded via a first information dispersal algorithm (IDA) in a response to an access request corresponding to an associated data object and determining when a number of the first slices is less than a read threshold corresponding to the first IDA and that the data object is also encoded into second slices via a second IDA. If so, the processing system identifies missing slices encoded via the first IDA corresponding to the access request; determines at least one of the second slices encoded via the second IDA corresponding to the missing slices; retrieves the at least one of the second slices; and generates the data object based on the first slices encoded via the first IDA and the at least one of the second slices encoded via the second IDA.

Claims

1. A method for execution by a processing system of a dispersed storage network (DSN) that includes a processor, the method comprises:

receiving first encoded data slices encoded via a first information dispersal algorithm in a response to an access request corresponding to an associated data object, wherein the first information dispersal algorithm includes a first pillar width and a first read threshold number of encoded data slices;

determining when a number of the first encoded data slices is less than the first read threshold number corresponding to the first information dispersal algorithm and that the data object is also encoded into second slices via a second information dispersal algorithm, wherein the second information dispersal algorithm includes a second pillar width and a second read threshold number of encoded data slices and wherein the first read threshold number and second read threshold number differ;

when the number of the first encoded data slices is less than the first read threshold and the data object is also encoded into the second slices via the second information dispersal algorithm;

identifying missing encoded data slices encoded via the first information dispersal algorithm corresponding to the access request;

determining at least one of the second encoded data slices encoded via the second information dispersal algorithm corresponding to the missing slices;

retrieving the at least one of the second encoded data slices; and

generating the data object based on the first encoded data slices encoded via the first information dispersal algorithm and the at least one of the second encoded data slices encoded via the second information dispersal algorithm.

2. The method of claim 1 wherein the access request corresponds to a read request for the data object and wherein the method further comprises generating a response to the read request that includes the data object.

3. The method of claim 1 wherein the method further comprises rebuilding the missing encoded data slices based on the at least one of the second encoded data slices.

4. The method of claim 1 wherein generating the data object includes reconstructing the missing encoded data slices based on the at least one of the second encoded data slices.

5. The method of claim 1, wherein the first encoded data slices are received from first storage units and the at least one of the second encoded data slices is retrieved from at least one second storage unit that differs from the first storage units.

6. The method of claim 1 wherein a number of the missing encoded data slices is greater than a number of the at least one of the second encoded data slices.

7. The method of claim 1 wherein a number of the missing encoded data slices is lesser than a number of the at least one of the second encoded data slices.

8. A processing system of a dispersed storage network 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;

receive first encoded data slices encoded via a first information dispersal algorithm in a response to an access request corresponding to an associated data object, wherein the first information dispersal algorithm includes a first pillar width and a first read threshold number of encoded data slices;

determine when a number of the first encoded data slices is less than the first read threshold corresponding to the first information dispersal algorithm and that the data object is also encoded into second encoded data slices via a second information dispersal algorithm, wherein the second information dispersal algorithm includes a second pillar width and a second read threshold number of encoded data slices and wherein the first read threshold number and second read threshold number differ;

when the number of the first encoded data slices is less than the first read threshold and the data object is also encoded into the second encoded data slices via the second information dispersal algorithm;

identify missing encoded data slices encoded via the first information dispersal algorithm corresponding to the access request;

determine at least one of the second encoded data slices encoded via the second information dispersal algorithm corresponding to the missing encoded data slices;

retrieve the at least one of the second encoded data slices; and

generate the data object based on the first encoded data slices encoded via the first information dispersal algorithm and the at least one of the second encoded data slices encoded via the second information dispersal algorithm.

9. The processing system of claim 8 wherein the access request corresponds to a read request for the data object and wherein the operational instructions, when executed by the at least one processor, cause the processing system to also generate a response to the read request that includes the data object.

10. The processing system of claim 8 wherein the operational instructions, when executed by the at least one processor, cause the processing system to also rebuild the missing encoded data slices based on the at least one of the second encoded data slices.

11. The processing system of claim 8 wherein generating the data object includes reconstructing the missing encoded data slices based on the at least one of the second encoded data slices.

12. The processing system of claim 8 wherein the first encoded data slices are received from first storage units and the at least one of the second encoded data slices is retrieved from at least one second storage unit that differs from the first storage units.

13. The processing system of claim 8 wherein a number of the missing encoded data slices is greater than a number of the at least one of the second encoded data slices.

14. The processing system of claim 8 wherein a number of the missing encoded data slices is lesser than a number of the at least one of the second encoded data slices.

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;

receive first encoded data slices encoded via a first information dispersal algorithm in a response to an access request corresponding to an associated data object, wherein the first information dispersal algorithm includes a first pillar width and a first read threshold number of encoded data slices;

determine when a number of the first encoded data slices is less than the first read threshold corresponding to the first information dispersal algorithm and that the data object is also encoded into second encoded data slices via a second information dispersal algorithm, wherein the second information dispersal algorithm includes a second pillar width and a second read threshold number of encoded data slices and wherein the first read threshold number and second read threshold number differ;

when the number of the first encoded data slices is less than the first read threshold and the data object is also encoded into the second encoded data slices via the second information dispersal algorithm;

identify missing encoded data slices encoded via the first information dispersal algorithm corresponding to the access request;

determine at least one of the second encoded data slices encoded via the second information dispersal algorithm corresponding to the missing encoded data slices;

retrieve the at least one of the second encoded data slices; and

generate the data object based on the first encoded data slices encoded via the first information dispersal algorithm and the at least one of the second encoded data slices encoded via the second information dispersal algorithm.

16. The non-transitory computer readable storage medium of claim 15 wherein the access request corresponds to a read request for the data object and wherein the operational instructions, when executed by the processing, causes the processing system to also generate a response to the read request that includes the data object.

17. The non-transitory computer readable storage medium of claim 15 wherein the operational instructions, when executed by the processing, causes the processing system to also rebuild the missing encoded data slices based on the at least one of the second encoded data slices.

18. The non-transitory computer readable storage medium of claim 15 wherein generating the data object includes reconstructing the missing encoded data slices based on the at least one of the second encoded data slices.

19. The non-transitory computer readable storage medium of claim 15 wherein the first encoded data slices are received from first storage units and the at least one of the second encoded data slices is retrieved from at least one second storage unit that differs from the first storage units.

20. The non-transitory computer readable storage medium of claim 15 wherein a number of the missing encoded data slices is different from a number of the at least one of the second encoded data slices.