Optimizing rebuilds when using multiple information dispersal algorithms

• US 10,241,695 B2
• Filed: 11/16/2016
• Issued: 03/26/2019
• Est. Priority Date: 12/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Wozniak, Ethan S.
• Primary Examiner(s): McMahon, Daniel F.
• Application Number:
  US15/352,950
• Publication Number:
  US 20170192692A1
• Time in Patent Office: 860 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 12/0684 with feedback, e.g. presence or absence of unit detected by addressing, overflow detection
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• 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 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• 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/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0652 : Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0653 : Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0659 : Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0661 : Format or protocol conversion arrangements
• 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: 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: H04L 43/0852 : Delays
• CPC Class Codes: H04L 43/0876 : Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/0888 : Throughput
• CPC Class Codes: H04L 43/16 : Threshold monitoring
• 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

Systems and methods for rebuilding encoded data slices in a dispersed storage network (DSN). In an embodiment, a data segment is dispersed storage error encoded using first dispersal parameters and differing second dispersal parameters to produce a first set of encoded data slices and a second sets of encoded data slices for storage in the DSN. A storage error is identified involving an encoded data slice of the first set of encoded data slices. When a first decode threshold number associated with the first dispersal parameters is greater than a second decode threshold number associated with the second dispersal parameters, a second decode threshold number of encoded data slices of the second set of encoded data slices is retrieved. The retrieved slices are decoded to recover the data segment, which is then re-encoded using the first dispersal parameters to generate a rebuilt encoded data slice corresponding to the storage error.

Claims

1. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the DSN storing a first set of encoded data slices and a second set of encoded data slices, wherein a data segment is dispersed storage error encoded using first dispersal parameters and differing second dispersal parameters to produce, respectively, the first and second sets of encoded data slices, the method comprising:

identifying a storage error associated with storage in the DSN of a first encoded data slice of the first set of encoded data slices;

in response to identifying the storage error, determining that a first decode threshold number associated with the first dispersal parameters is greater than a second decode threshold number associated with the second dispersal parameters;

obtaining, from storage of the DSN, a second decode threshold number of encoded data slices of the second set of encoded data slices;

generating, by the one or more processing modules, a rebuilt encoded data slice associated with the first encoded data slice using the second decode threshold number of encoded data slices; and

storing the rebuilt encoded data slice associated with the first encoded data slice.

2. The method of claim 1, wherein the first set of encoded data slices is stored in a first set of dispersed storage units and the second set of encoded data slices is stored in a second set of dispersed storage units.

3. The method of claim 2, wherein the first set of dispersed storage units include a first number of dispersed storage units corresponding to a first information dispersal algorithm width number of the first dispersal parameters and the second set of dispersed storage units include a second number of dispersed storage units corresponding to a second information dispersal algorithm width number of the second dispersal parameters.

4. The method of claim 3, wherein the first information dispersal algorithm width number of the first dispersal parameters is greater than the first decode threshold number and the second information dispersal algorithm width number of the second dispersal parameters is greater than the second decode threshold number.

5. The method of claim 3, wherein generating a rebuilt encoded data slice associated with the first encoded data slice using the second decode threshold number of encoded data slices further comprises dispersed storage error decoding, by the one or more processing modules, the second decode threshold number of encoded data slices using the second dispersal parameters to produce a recovered data segment.

6. The method of claim 5, further comprising dispersed storage error encoding, by the one or more processing modules, the recovered data segment using the first dispersal parameters.

7. The method of claim 1, wherein identifying a storage error associated with a first encoded data slice of a first set of encoded data slices further comprises interpreting list slice responses, interpreting an error message and interpreting a read slice response.

8. The method of claim 1, further comprising issuing, by the one or more processing modules, read slice requests for the second decode threshold number of encoded data slices.

9. The method of claim 1, wherein storing the rebuilt encoded data slice associated with the first encoded data slice further comprises identifying, by the one or more processing modules, a storage unit associated with the storage error and identifying another storage unit with favorable capacity and performance for storage of the rebuilt encoded data slice.

10. A dispersed storage integrity processing unit for use in a dispersed storage network, the dispersed storage network including a first set of dispersed storage units storing a first set of encoded data slices and a second set of dispersed storage units storing a second set of encoded data slices, wherein a data segment is dispersed storage error encoded using first dispersal parameters and differing second dispersal parameters to produce, respectively, the first and second sets of encoded data slices, the dispersed storage integrity processing unit comprising:

a communications interface;

a memory; and

a computer processor;

where the memory includes instructions for causing the computer processor to;

identify a storage error associated with a first encoded data slice of the first set of encoded data slices;

in response to identifying the storage error, determine that a first decode threshold number associated with the first dispersal parameters is greater than a second decode threshold number associated with the second dispersal parameters;

obtain, via the communications interface, a second decode threshold number of second encoded data slices of the second set of encoded data slices;

generate a rebuilt encoded data slice associated with the first encoded data slice using the second decode threshold number of second encoded data slices; and

issue, via the communications interface, a write slice request to store the rebuilt encoded data slice associated with the first encoded data slice.

11. The dispersed storage integrity processing unit of claim 10, wherein the first set of encoded data slices is stored in a first information dispersal algorithm width number of the first set of dispersed storage units and the second set of encoded data slices is stored in a second information dispersal algorithm width number of the second set of dispersed storage units.

12. The dispersed storage integrity processing unit of claim 11, wherein the first information dispersal algorithm width number is greater than the first decode threshold number and the second information dispersal algorithm width number is greater than the second decode threshold number.

13. The dispersed storage integrity processing unit of claim 12, wherein the first information dispersal algorithm width number is greater than the second information dispersal algorithm width number.

14. The dispersed storage integrity processing unit of claim 12, wherein the memory further comprises instructions for causing the computer processor to dispersed storage error decode the second decode threshold number of second encoded data slices using the second dispersal parameters to produce a recovered data segment.

15. The dispersed storage integrity processing unit of claim 14, wherein the memory further comprises instructions for causing the computer processor to dispersed storage error encode the recovered data segment using the first dispersal parameters.

16. The dispersed storage integrity processing unit of claim 10, wherein the memory further comprises instructions for causing the computer processor to interpret list slice responses, interpret an error message and interpret a read slice response.

17. The dispersed storage integrity processing unit of claim 10, wherein the memory further comprises instructions for causing the computer processor to issue read slice requests for the second decode threshold number of second encoded data slices.

18. The dispersed storage integrity processing unit of claim 10, wherein the memory further comprises instructions for causing the computer processor to identify a storage unit associated with the storage error and identify another storage unit with favorable capacity and performance.

19. A dispersed storage network comprising:

a first set of dispersed storage units storing a first set of encoded data slices, wherein a data segment is dispersed storage error encoded using first dispersal parameters to produce the first set of encoded data slices;

a second set of dispersed storage units storing a second set of encoded data slices, wherein the data segment is dispersed storage error encoded using second dispersal parameters to produce the second set of encoded data slices; and

a disperse storage integrity processing unit including;

a communications interface;

a memory; and

a computer processor;

where the memory includes instructions for causing the computer processor to;

identify a storage error associated with a first encoded data slice of the first set of encoded data slices;

determine that a first decode threshold number associated with the first dispersal parameters is greater than a second decode threshold number associated with the second dispersal parameters;

obtain, via the communications interface, a second decode threshold number of second encoded data slices of the second set of encoded data slices;

generate a rebuilt encoded data slice associated with the first encoded data slice using the second decode threshold number of second encoded data slices; and

store the rebuilt encoded data slice associated with the first encoded data slice.

20. The dispersed storage network of claim 19, wherein the first set of encoded data slices is stored in a subset of the first set of dispersed storage units and the second set of encoded data slices is stored in a subset of the second set of dispersed storage units.