Threshold computing in a distributed computing system

• US 9,817,701 B2
• Filed: 01/12/2017
• Issued: 11/14/2017
• Est. Priority Date: 12/12/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Dhuse, Greg R., Gladwin, S. Christopher, Grube, Gary W., Leggette, Wesley B., Motwani, Manish, Resch, Jason K., Shirley, Jr., Thomas F., Volvovski, Ilya
• Primary Examiner(s): KIM, TAE K
• Application Number:
  US15/405,203
• Publication Number:
  US 20170123856A1
• Time in Patent Office: 306 Days
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• 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 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/2058 using more than 2 mirrored copies
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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/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/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• 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 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/5083 : Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H03M 13/09 : Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• 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 63/0428 : wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/06 : for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/08 : for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/10 : for controlling access to devices or network resources
• CPC Class Codes: H04L 67/04 : specially adapted for terminals or networks with limited capabilities; specially adapted for terminal portability
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1017 : based on a round robin mechanism
• 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]
• CPC Class Codes: H04L 67/303 : Terminal profiles
• CPC Class Codes: H04L 67/60 : Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

A computing device includes an interface configured to interface and communicate with a dispersed storage network (DSN), a memory that stores operational instructions, and a processing module operably coupled to the interface and memory such that the processing module, when operable within the computing device based on the operational instructions, is configured to perform various operations. The computing device selects a subset of the other computing devices to perform a computing task on a data object. The computing device determines processing parameters of the data and determines task partitioning. The computing device also processes the data based on processing parameters to generate data slice groupings and partitions the task based on the task partitioning to generate partial tasks. The computing device obtains and processes at least the decode threshold number of the plurality of partial results generated by the subset of the other computing devices to generate a result.

Claims

1. A computing device comprising:

an interface configured to interface and communicate with a dispersed or distributed storage network (DSN);

memory that stores operational instructions; and

a processing module operably coupled to the interface and to the memory, wherein the processing module, when operable within the computing device based on the operational instructions, is configured to;

determine capability levels of a plurality of other computing devices;

select, based on the capability levels of a plurality of other computing devices, a subset of the plurality of other computing devices to perform a computing task on a data object, wherein the data object is segmented into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce a set of encoded data slices (EDSs), wherein the set of EDSs are distributedly stored among a plurality of storage units (SUs), wherein a decode threshold number of EDSs are needed to recover the data segment, wherein a read threshold number of EDSs provides for reconstruction of the data segment, and wherein a write threshold number of EDSs provides for a successful transfer of the set of EDSs from a first at least one location in the DSN to a second at least one location in the DSN;

determine processing parameters of the data based on a number of the subset of the plurality of other computing devices;

determine task partitioning based on the subset of the plurality of other computing devices, the processing parameters, and a threshold computing parameter;

process the data based on processing parameters to generate data slice groupings;

partition the task based on the task partitioning to generate partial tasks;

transmit the partial tasks and the data slice groupings respectively to the subset of the plurality of other computing devices to be executed respectively by the subset of the plurality of other computing devices to generate a plurality of partial results;

when the decode threshold number of the plurality of partial results is generated by the subset of the plurality of other computing devices and available as indicated by at least the write threshold number of the subset of the plurality of other computing devices, obtain at least the decode threshold number of the plurality of partial results; and

process the at least the decode threshold number of the plurality of partial results to generate a result.

2. The computing device of claim 1, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

select, based on the capability levels of a plurality of other computing devices, the subset of the plurality of other computing devices to perform a computing task on the data object based on at least one of comparing an amount of data associated with the data object received to a data threshold, a partial task type, task execution resource availability, or a task schedule.

3. The computing device of claim 1, wherein the threshold computing parameter includes at least one of a decode threshold number of computing devices, a pillar width number of computing devices, or a task redundancy requirement number of computing devices to execute an identical partial task.

4. The computing device of claim 1, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

determine whether the decode threshold number of the plurality of partial results is generated by the subset of the plurality of other computing devices and available based on at least one of receiving a partial result from at least one of the subset of the plurality of other computing devices, receiving a partial result status from the at least one of the subset of the plurality of other computing devices, a query operation to the at least one of the subset of the plurality of other computing devices, retrieving a partial result from the at least one of the subset of the plurality of other computing devices, or a comparison of a number of partial results to the decode threshold number.

5. The computing device of claim 1, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

decode the at least the decode threshold number of the plurality of partial results to generate the result.

6. The computing device of claim 1, wherein the computing device is located at a first premises that is remotely located from at least one SU of the plurality of SUs within the DSN.

7. The computing device of claim 1 further comprising:

a SU of the plurality of SUs within the DSN, a wireless smart phone, a laptop, a tablet, a personal computers (PC), a work station, or a video game device.

8. The computing device of claim 1, wherein the DSN includes at least one of a wireless communication system, a wire lined communication systems, a non-public intranet system, a public internet system, a local area network (LAN), or a wide area network (WAN).

9. A computing device comprising:

an interface configured to interface and communicate with a dispersed or distributed storage network (DSN);

memory that stores operational instructions; and

a processing module operably coupled to the interface and to the memory, wherein the processing module, when operable within the computing device based on the operational instructions, is configured to;

determine capability levels of a plurality of other computing devices;

select, based on the capability levels of a plurality of other computing devices, a subset of the plurality of other computing devices to perform a computing task on a data object, wherein the data object is segmented into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce a set of encoded data slices (EDSs), wherein the set of EDSs are distributedly stored among a plurality of storage units (SUs), wherein a decode threshold number of EDSs are needed to recover the data segment, wherein a read threshold number of EDSs provides for reconstruction of the data segment, and wherein a write threshold number of EDSs provides for a successful transfer of the set of EDSs from a first at least one location in the DSN to a second at least one location in the DSN;

determine processing parameters of the data based on a number of the subset of the plurality of other computing devices;

determine task partitioning based on the subset of the plurality of other computing devices, the processing parameters, and a threshold computing parameter, wherein the threshold computing parameter includes at least one of a decode threshold number of computing devices, a pillar width number of computing devices, or a task redundancy requirement number of computing devices to execute an identical partial task;

process the data based on processing parameters to generate data slice groupings;

partition the task based on the task partitioning to generate partial tasks;

transmit the partial tasks and the data slice groupings respectively to the subset of the plurality of other computing devices to be executed respectively by the subset of the plurality of other computing devices to generate a plurality of partial results;

when the decode threshold number of the plurality of partial results is generated by the subset of the plurality of other computing devices and available as indicated by at least the write threshold number of the subset of the plurality of other computing devices, obtain at least the decode threshold number of the plurality of partial results; and

decode the at least the decode threshold number of the plurality of partial results to generate a result.

10. The computing device of claim 9, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

select, based on the capability levels of a plurality of other computing devices, the subset of the plurality of other computing devices to perform a computing task on the data object based on at least one of comparing an amount of data associated with the data object received to a data threshold, a partial task type, task execution resource availability, or a task schedule.

11. The computing device of claim 9, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

determine whether the decode threshold number of the plurality of partial results is generated by the subset of the plurality of other computing devices and available based on at least one of receiving a partial result from at least one of the subset of the plurality of other computing devices, receiving a partial result status from the at least one of the subset of the plurality of other computing devices, a query operation to the at least one of the subset of the plurality of other computing devices, retrieving a partial result from the at least one of the subset of the plurality of other computing devices, or a comparison of a number of partial results to the decode threshold number.

12. The computing device of claim 9 further comprising:

a SU of the plurality of SUs within the DSN, a wireless smart phone, a laptop, a tablet, a personal computers (PC), a work station, or a video game device.

13. The computing device of claim 9, wherein the DSN includes at least one of a wireless communication system, a wire lined communication systems, a non-public intranet system, a public internet system, a local area network (LAN), or a wide area network (WAN).

14. A method for execution by a computing device, the method comprising:

determining capability levels of a plurality of other computing devices;

selecting, based on the capability levels of a plurality of other computing devices, a subset of the plurality of other computing devices to perform a computing task on a data object, wherein the data object is segmented into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce a set of encoded data slices (EDSs), wherein the set of EDSs are distributedly stored among a plurality of storage units (SUs), wherein a decode threshold number of EDSs are needed to recover the data segment, wherein a read threshold number of EDSs provides for reconstruction of the data segment, and wherein a write threshold number of EDSs provides for a successful transfer of the set of EDSs from a first at least one location in a dispersed or distributed storage network (DSN) to a second at least one location in the DSN;

determining processing parameters of the data based on a number of the subset of the plurality of other computing devices;

determining task partitioning based on the subset of the plurality of other computing devices, the processing parameters, and a threshold computing parameter;

processing the data based on processing parameters to generate data slice groupings;

partitioning the task based on the task partitioning to generate partial tasks;

transmitting, via an interface configured to interface and communicate with the DSN, the partial tasks and the data slice groupings respectively to the subset of the plurality of other computing devices to be executed respectively by the subset of the plurality of other computing devices to generate a plurality of partial results;

when the decode threshold number of the plurality of partial results is generated by the subset of the plurality of other computing devices and available as indicated by at least the write threshold number of the subset of the plurality of other computing devices, obtaining at least the decode threshold number of the plurality of partial results; and

processing the at least the decode threshold number of the plurality of partial results to generate a result.

15. The method of claim 14 further comprising:

selecting, based on the capability levels of a plurality of other computing devices, the subset of the plurality of other computing devices to perform a computing task on the data object based on at least one of comparing an amount of data associated with the data object received to a data threshold, a partial task type, task execution resource availability, or a task schedule.

16. The method of claim 14, wherein the threshold computing parameter includes at least one of a decode threshold number of computing devices, a pillar width number of computing devices, or a task redundancy requirement number of computing devices to execute an identical partial task.

17. The method of claim 14 further comprising:

determining whether the decode threshold number of the plurality of partial results is generated by the subset of the plurality of other computing devices and available based on at least one of receiving a partial result from at least one of the subset of the plurality of other computing devices, receiving a partial result status from the at least one of the subset of the plurality of other computing devices, a query operation to the at least one of the subset of the plurality of other computing devices, retrieving a partial result from the at least one of the subset of the plurality of other computing devices, or a comparison of a number of partial results to the decode threshold number.

18. The method of claim 14 further comprising:

decoding the at least the decode threshold number of the plurality of partial results to generate the result.

19. The method of claim 14, wherein the computing device is a SU of the plurality of SUs within the DSN, a wireless smart phone, a laptop, a tablet, a personal computers (PC), a work station, or a video game device.

20. The method of claim 14, wherein the DSN includes at least one of a wireless communication system, a wire lined communication systems, a non-public intranet system, a public internet system, a local area network (LAN), or a wide area network (WAN).