Selecting partial task resources in a dispersed storage network

• US 10,067,721 B2
• Filed: 09/14/2016
• Issued: 09/04/2018
• Est. Priority Date: 11/30/2015
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg R.
• Primary Examiner(s): Truong, Camquy
• Application Number:
  US15/265,245
• Publication Number:
  US 20170153915A1
• Time in Patent Office: 720 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 method for use in a dispersed storage network operates to identify a selected DSTE unit of a subset of DSTE units to perform one or more partial tasks of a task to be performed on at least one encoded data slice; issue the one or more partial tasks to the selected DSTE unit; receive one or more partial results from the selected DSTE unit, wherein the selected DSTE unit performs the one or more partial tasks on the at least one encoded data slice to produce the one or more partial results; and output a result based on the received one or more partial task.

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:

storing data as 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 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 information dispersal algorithm having a second decode threshold number;

identifying, via the processing system, a selected DSTE unit of the subset of DSTE units to perform one or more partial tasks of a task to be performed on at least one encoded data slice of the one or more second sets of encoded data slices;

issuing, via the processing system, the one or more partial tasks to the selected DSTE unit;

receiving, via the processing system, one or more partial results from the selected DSTE unit, wherein the selected DSTE unit performs the one or more partial tasks on the at least one encoded data slice to produce the one or more partial results; and

outputting, via the processing system, a result based on the received one or more partial task results;

wherein the each of the one or more first sets of encoded data slices includes a first information dispersal algorithm (IDA) width number of encoded data slices, and wherein the first decode threshold number of each of the one or more first sets of encoded data slices is required to recover the data using the first IDA, and wherein the first decode threshold number is greater than half of the first IDA width number.

2. The method of claim 1 wherein identifying the selected DTSE unit is based on one or more of:

an amount of data contained in one slice at the DSTE unit or DSTE unit availability information.

3. The method of claim 1 wherein identifying the selected DTSE unit is based on one or more of:

a task processing time requirement or a DSTE unit performance level.

4. The method of claim 1 wherein identifying the selected DTSE unit is based on one or more of:

an interpretation of system registry information or a predetermination.

5. The method of claim 1 wherein identifying the selected DTSE unit is based on a determination that the selected DSTE unit is available, that the at least one encoded data slice is stored at the selected DST unit and further that the at least one encoded data slice includes all the data for performing of the partial task.

6. The method of claim 1 wherein the each of the one or more second sets of encoded data slices includes a second IDA width number of encoded data slices, and wherein the second decode threshold number of each of the one or more second sets of encoded data slices is required to recover the data using the second IDA, and where the second decode threshold number is less than or equal to half of the second IDA width number.

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

at least one processor;

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

store data as 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 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 information dispersal algorithm having a second decode threshold number;

identify a selected DSTE unit of the subset of DSTE units to perform one or more partial tasks of a task to be performed on at least one encoded data slice of the one or more second sets of encoded data slices;

issue the one or more partial tasks to the selected DSTE unit;

receive one or more partial results from the selected DSTE unit, wherein the selected DSTE unit performs the one or more partial tasks on the at least one encoded data slice to produce the one or more partial results; and

output a result based on the received one or more partial task results;

wherein the each of the one or more first sets of encoded data slices includes a first information dispersal algorithm (IDA) width number of encoded data slices, and wherein the first decode threshold number of each of the one or more first sets of encoded data slices is required to recover the data using the first IDA, and wherein the first decode threshold number is greater than half of the first IDA width number.

8. The processing system of claim 7 wherein identifying the selected DTSE unit is based on one or more of:

an amount of data contained in one slice at the DSTE unit or DSTE unit availability information.

9. The processing system of claim 7 wherein identifying the selected DTSE unit is based on one or more of:

a task processing time requirement or a DSTE unit performance level.

10. The processing system of claim 7 wherein identifying the selected DTSE unit is based on one or more of:

an interpretation of system registry information or a predetermination.

11. The processing system of claim 7 wherein identifying the selected DTSE unit is based on a determination that the selected DSTE unit is available, that the at least one encoded data slice is stored at the selected DST unit and further that the at least one encoded data slice includes all the data for performing of the partial task.

12. The processing system of claim 7 wherein the each of the one or more second sets of encoded data slices includes a second IDA width number of encoded data slices, and wherein the second decode threshold number of each of the one or more second sets of encoded data slices is required to recover the data using the second IDA, and where the second decode threshold number is less than or equal to half of the second IDA width 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 dispersed storage network (DSN) that includes a processor and a memory, causes the processing system to;

store data as 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 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 information dispersal algorithm having a second decode threshold number;

identify a selected DSTE unit of the subset of DSTE units to perform one or more partial tasks of a task to be performed on at least one encoded data slice of the one or more second sets of encoded data slices;

issue the one or more partial tasks to the selected DSTE unit;

receive one or more partial results from the selected DSTE unit, wherein the selected DSTE unit performs the one or more partial tasks on the at least one encoded data slice to produce the one or more partial results; and

output a result based on the received one or more partial task results;

wherein the each of the one or more first sets of encoded data slices includes a first information dispersal algorithm (IDA) width number of encoded data slices, and wherein the first decode threshold number of each of the one or more first sets of encoded data slices is required to recover the data using the first IDA, and wherein the first decode threshold number is greater than half of the first IDA width number.

14. The non-transitory computer readable storage medium of claim 13 wherein identifying the selected DTSE unit is based on one or more of:

an amount of data contained in one slice at the DSTE unit or DSTE unit availability information.

15. The non-transitory computer readable storage medium of claim 13 wherein identifying the selected DTSE unit is based on one or more of:

a task processing time requirement or a DSTE unit performance level.

16. The non-transitory computer readable storage medium of claim 13 wherein identifying the selected DTSE unit is based on one or more of:

an interpretation of system registry information or a predetermination.

17. The non-transitory computer readable storage medium of claim 13 wherein identifying the selected DTSE unit is based on a determination that the selected DSTE unit is available, that the at least one encoded data slice is stored at the selected DST unit and further that the at least one encoded data slice includes all the data for performing of the partial task.

18. The non-transitory computer readable storage medium of claim 13

wherein the each of the one or more second sets of encoded data slices includes a second IDA width number of encoded data slices, and wherein the second decode threshold number of each of the one or more second sets of encoded data slices is required to recover the data using the second IDA, and where the second decode threshold number is less than or equal to half of the second IDA width number.