Utilizing multiple dispersal algorithms to encode data for storage in a dispersed storage network

• US 10,423,362 B2
• Filed: 09/13/2016
• Issued: 09/24/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., Volvovski, Ilya, Wozniak, Ethan S.
• Primary Examiner(s): Mehrmanesh, Elmira
• Application Number:
  US15/263,810
• Publication Number:
  US 20170153821A1
• Time in Patent Office: 1,106 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/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 first dispersed storage and task (DST) processing unit operates to store data as one or more first sets of encoded data slices in a set of storage units utilizing a first information dispersal algorithm having a first decode threshold number and determine whether to store the data as one or more second sets of encoded data slices in the set of storage units utilizing a second IDA having a second decode threshold number. When determined to store the data as the one or more second sets of encoded data slices, the first DST processing unit further operates to encode the data utilizing the second IDA to produce the one or more second sets of encoded data slices, and facilitate storage of the one or more second sets of encoded data slices in at least a subset of the set of storage units.

Claims

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

performing, via the processing system, a first information dispersal algorithm (IDA) having a first decode threshold number on a data segment to produce a first set of encoded data slices of the data segment;

storing the first set of encoded data slices in a set of storage units;

determining, via the processing system, whether to store the data segment as a second set of encoded data slices in the set of storage units utilizing a second IDA having a second decode threshold number;

when determined to store the data segment as the second set of encoded data slices, performing, via the processing system, the second IDA on the data segment to produce the second set of encoded data slices; and

facilitating, via the processing system, storage of the second set of encoded data slices in at least a subset of the set of storage units;

wherein a second DST processing unit responds to an access request for the data segment by identifying the second set of encoded data slices based on an identifier of the data segment, retrieving, when the second decode threshold number of encoded data slices of the second set of encoded data slices are available, the second decode threshold number of encoded data slices of the second set of encoded data slices and utilizing the second IDA to disperse storage error decode the second decode threshold number of encoded data slices of the second set of encoded data slices to recover the data segment; and

wherein the second DST processing unit retrieves the first decode threshold number of encoded data slices of the first set of encoded data slices for decoding utilizing the first IDA to recover the data segment when the second decode threshold number of encoded data slices of at least one of the second set of encoded data slices are unavailable.

2. The method of claim 1 wherein the second DST processing unit identifies the second set of encoded data slices based on the identifier of the data segment by converting the identifier of the data segment to a source name of the second set of encoded data slices utilizing a deterministic function.

3. The method of claim 1 wherein the first set of encoded data slices includes a first IDA width number of encoded data slices, and wherein the first decode threshold number of the first set of encoded data slices is required to recover the data segment using the first IDA, and wherein the first decode threshold number is greater than half of the first IDA width number.

4. The method of claim 3 wherein the second set of encoded data slices includes a second IDA width number of encoded data slices, and wherein the second decode threshold number of the second set of encoded data slices is required to recover the data segment using the second IDA, and where the second decode threshold number is less than or equal to half of the second IDA width number.

5. The method of claim 1 wherein determining whether to store the data segment as the second set of encoded data slices is based on one or more of:

a data size of the data segment, a data type of the data segment, an expected access frequency level of the data segment, a data consistency requirement, a request, a predetermination, or an interpretation of system registry information.

6. The method of claim 1 wherein the first decode threshold number is greater than the second decode threshold number.

7. A processing system of a first dispersed storage and task (DST) 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 a first information dispersal algorithm (IDA) having a first decode threshold number on a data segment to produce a first set of encoded data slices of the data segment;

store the first set of encoded data slices in a set of storage units;

determine whether to store the data segment as a second set of encoded data slices in the set of storage units utilizing a second IDA having a second decode threshold number;

when determined to store the data segment as the second set of encoded data slices, perform, via the processing system, the second IDA on the data segment to produce the second set of encoded data slices; and

facilitate storage of the second set of encoded data slices in at least a subset of the set of storage units;

wherein a second DST processing unit responds to an access request for the data segment by identifying the second set of encoded data slices based on an identifier of the data segment, retrieving, when the second decode threshold number of encoded data slices of the second set of encoded data slices are available, the second decode threshold number of encoded data slices of the second set of encoded data slices and utilizing the second IDA to disperse storage error decode the second decode threshold number of encoded data slices of the second set of encoded data slices to recover the data segment; and

wherein the second DST processing unit retrieves the first decode threshold number of encoded data slices of the first set of encoded data slices for decoding utilizing the first IDA to recover the data segment when the second decode threshold number of encoded data slices of at least one of the second set of encoded data slices are unavailable.

8. The processing system of claim 7 wherein the second DST processing unit identifies the second set of encoded data slices based on the identifier of the data segment by converting the identifier of the data segment to a source name of the second set of encoded data slices utilizing a deterministic function.

9. The processing system of claim 7 wherein the first set of encoded data slices includes a first IDA width number of encoded data slices, and wherein the first decode threshold number of the first set of encoded data slices is required to recover the data segment using the first IDA, and wherein the first decode threshold number is greater than half of the first IDA width number.

10. The processing system of claim 9 wherein the second set of encoded data slices includes a second IDA width number of encoded data slices, and wherein the second decode threshold number of the second set of encoded data slices is required to recover the data segment using the second IDA, and where the second decode threshold number is less than or equal to half of the second IDA width number.

11. The processing system of claim 7 wherein determining whether to store the data segment as the second set of encoded data slices is based on one or more of:

a data size of the data segment, a data type of the data segment, an expected access frequency level of the data segment, a data consistency requirement, a request, a predetermination, or an interpretation of system registry information.

12. The processing system of claim 7 wherein the first decode threshold number is greater than the second decode threshold number.

13. 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 first dispersed storage and task (DST) processing unit of a dispersed storage network (DSN) that includes a processor and a memory, causes the processing system to;

perform a first information dispersal algorithm (IDA) having a first decode threshold number on a data segment to produce a first set of encoded data slices of the data segment;

store the first set of encoded data slices in a set of storage units;

determine whether to store the data segment as a second set of encoded data slices in the set of storage units utilizing a second IDA having a second decode threshold number;

when determined to store the data segment as the second set of encoded data slices, performing, via the processing system, the second IDA on the data segment to produce the second set of encoded data slices; and

facilitate storage of the second set of encoded data slices in at least a subset of the set of storage units;

wherein a second DST processing unit responds to an access request for the data segment by identifying the second set of encoded data slices based on an identifier of the data segment, retrieving, when the second decode threshold number of encoded data slices of the second set of encoded data slices are available, the second decode threshold number of encoded data slices of the second set of encoded data slices and utilizing the second IDA to disperse storage error decode the second decode threshold number of encoded data slices of the second set of encoded data slices to recover the data segment; and

wherein the second DST processing unit retrieves the first decode threshold number of encoded data slices of the first set of encoded data slices for decoding utilizing the first IDA to recover the data segment when the second decode threshold number of encoded data slices of at least one of the second set of encoded data slices are unavailable.

14. The non-transitory computer readable storage medium of claim 13 wherein the second DST processing unit identifies the second set of encoded data slices based on the identifier of the data segment by converting the identifier of the data segment to a source name of the second set of encoded data slices utilizing a deterministic function.

15. The non-transitory computer readable storage medium of claim 13 wherein the first set of encoded data slices includes a first IDA width number of encoded data slices, and wherein the first decode threshold number of the first set of encoded data slices is required to recover the data segment using the first IDA, and wherein the first decode threshold number is greater than half of the first IDA width number.

16. The non-transitory computer readable storage medium of claim 15 wherein the second set of encoded data slices includes a second IDA width number of encoded data slices, and wherein the second decode threshold number of the second set of encoded data slices is required to recover the data segment using the second IDA, and where the second decode threshold number is less than or equal to half of the second IDA width number.

17. The non-transitory computer readable storage medium of claim 13 wherein determining whether to store the data segment as the second set of encoded data slices is based on one or more of:

a data size of the data segment, a data type of the data segment, an expected access frequency level of the data segment, a data consistency requirement, a request, a predetermination, or an interpretation of system registry information.