Allocating resources for multi-phase, distributed computing jobs

• US 9,489,225 B2
• Filed: 01/15/2014
• Issued: 11/08/2016
• Est. Priority Date: 01/15/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Huang, Senhua, Dutta, Debojyoti, Marathe, Madhav, Nambiar, Raghunath
• Primary Examiner(s): DAO, THUY CHAN
• Application Number:
  US14/156,149
• Publication Number:
  US 20150199208A1
• Time in Patent Office: 1,028 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/44505 Configuring for program initiating, e.g. using registry, configuration files
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

In one embodiment, data indicative of the size of an intermediate data set generated by a first resource device is received at a computing device. The intermediate data set is associated with a virtual machine to process the intermediate data set. A virtual machine configuration is determined based on the size of the intermediate data set. A second resource device is selected to execute the virtual machine based on the virtual machine configuration and on an available bandwidth between the first and second resource devices. The virtual machine is then assigned to the second resource device to process the intermediate data set.

Claims

1. A method comprising:

receiving, at a computing device, data indicative of the size of an intermediate data set generated by a first resource device;

associating the intermediate data set with a virtual machine to process the intermediate data set;

determining a virtual machine configuration based on the size of the intermediate data set;

selecting a second resource device to execute the virtual machine based on the virtual machine configuration and on an available bandwidth between the first and second resource devices; and

assigning the virtual machine to the second resource device to process the intermediate data set, wherein the intermediate data set is generated by a mapper task executed within a virtual machine on the first resource device and the virtual machine assigned to the second resource device executes a reducer task to process the intermediate data set.

2. The method of claim 1, wherein determining the virtual machine configuration comprises:

determining, for each of a plurality of virtual machines, a virtual machine configuration such that the maximum computation time taken by any of the virtual machines in the plurality to process an intermediate data set is minimized.

3. The method of claim 2, wherein a maximum number of virtual machines in the plurality is limited by a preset parameter.

4. The method of claim 1, wherein the intermediate data set comprises one or more key/value pairs.

5. The method of claim 1, wherein the virtual machine configuration comprises at least one of a memory size or a processor speed.

6. The method of claim 1, further comprising:

receiving, at the device, an input data set; and

allocating a portion of the input data set to the first resource device to generate the intermediate data set.

7. The method of claim 1, wherein selecting the second resource device to execute the virtual machine comprises:

heuristically searching a set of resource devices eligible to process one or more intermediate data sets for a resource device having enough available resources to support the virtual machine configuration; and

identifying the second resource device as having enough available resources to support the virtual machine configuration.

8. The method of claim 1, wherein selecting the second resource device to execute the virtual machine comprises:

identifying the intermediate data set as the largest intermediate data set generated by one of a plurality of resource devices;

searching a set of resource devices eligible to process one or more intermediate data sets for a resource device having the highest bandwidth; and

identifying the second resource device as the resource device having the highest bandwidth among the set of resource devices eligible to process one or more intermediate data sets.

9. An apparatus comprising:

one or more network interfaces configured to communicate in a computer network;

a processor configured to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

receive data indicative of the size of an intermediate data set generated by a first resource device;

associate the intermediate data set with a virtual machine to process the intermediate data set;

determine a virtual machine configuration for processing a next computational phase of the intermediate data set based on the size of the intermediate data set;

select a second resource device to execute the virtual machine based on the virtual machine configuration and on an available bandwidth between the first and second resource devices; and

assign the virtual machine to the second resource device to process the intermediate data set, wherein the intermediate data set is generated by a mapper task executed within a virtual machine on the first resource device and the virtual machine assigned to the second resource device executes a reducer task to process the intermediate data set.

10. The apparatus of claim 9, wherein the process, when executed, is further operable to:

determine, for each of a plurality of virtual machines, a virtual machine configuration such that the maximum computation time taken by any of the virtual machines in the plurality to process an intermediate data set is minimized.

11. The apparatus of claim 10, wherein a maximum number of virtual machines in the plurality is limited by a preset parameter.

12. The apparatus of claim 9, wherein the intermediate data set comprises a key/value pair.

13. The apparatus of claim 9, wherein the virtual machine configuration comprises at least one of a memory size or a processor speed.

14. The apparatus of claim 9, wherein the process, when executed, is further operable to:

heuristically search a set of resource devices eligible to process one or more intermediate data sets for a resource device having enough available resources to support the virtual machine configuration; and

identify the second resource device as having enough available resources to support the virtual machine configuration.

15. The apparatus of claim 9, wherein the process, when executed, is further operable to:

identify the intermediate data set as the largest intermediate data set generated by one of a plurality of resource devices;

search a set of resource devices eligible to process one or more intermediate data sets for a resource device having the highest bandwidth; and

identify the second resource device as the resource device having the highest bandwidth among the set of resource devices eligible to process one or more intermediate data sets.

16. A tangible, non-transitory, computer-readable media medium having software encoded thereon, the software, when executed by a processor, operable to:

receive data indicative of the size of an intermediate data set generated by a first resource device;

associate the intermediate data set with a virtual machine to process the intermediate data set;

determine a virtual machine configuration for processing a next computational phase of the intermediate data set based on the size of the intermediate data set;

select a second resource device to execute the virtual machine based on the virtual machine configuration and on an available bandwidth between the first and second resource devices; and

assign the virtual machine to the second resource device to process the intermediate data set wherein the intermediate data set is generated by a mapper task executed within a virtual machine on the first resource device and the virtual machine assigned to the second resource device executes a reducer task to process the intermediate data set.