Token-Based Adaptive Task Management for Virtual Machines

• US 20140237468A1
• Filed: 02/21/2013
• Published: 08/21/2014
• Est. Priority Date: 02/21/2013
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Desai, Aalap, Bhatt, Chirag
• Granted Patent: US 9,411,658 B2
• Time in Patent Office: Days
• US Class Current: 718/1
• 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

Abstract

Embodiments perform adaptive throttling of tasks into a virtual datacenter having dynamically changing resources. Tasks are processed concurrently in batches. The rate of change in throughput at different batch sizes is calculated. With each iteration, the batch size is increased or decreased based on the rate of change to achieve a maximum throughput for given resources and load on the virtual datacenter.

Claims

1. A system for achieving maximal throughput in a virtual datacenter having dynamically changing resources, said system comprising:

a memory area associated with a task management device, said memory area storing a plurality of outstanding tasks to be performed by a plurality of virtual machines (VMs) executing in the virtual datacenter; and

a processor programmed to;

normalize the outstanding tasks stored in the memory area by assigning a quantity of tokens to each of the outstanding tasks, the tokens representing an amount of work performed by the virtual datacenter when performing the outstanding tasks, the assigned quantity of tokens representing a second token batch size;

measure, by the task management device, a first throughput at a first token batch size and a second throughput at the second token batch size;

calculate, by the task management device, a rate of change between the measured first throughput at the first token batch size and the measured second throughput at the second token batch size; and

identify an output token batch size by;

if the calculated rate of change is negative, identify an output token batch size based on a combination of the first token batch size and the second token batch size; and

otherwise, select, by the task management device, a third token batch size and repeat said measure, said calculate, and said identify using the second token batch size as the first token batch size and the third token batch size as the second token batch size during the repeating.

2. The system of claim 1, wherein the processor is further programmed to select a quantity of the normalized outstanding tasks, the selected quantity corresponding to the identified output token batch size.

3. The system of claim 2, wherein the processor is further programmed to identify the selected quantity of the normalized outstanding tasks to the virtual datacenter.

4. The system of claim 1, wherein the tokens represent an amount of resources consumed by the virtual datacenter when performing the outstanding tasks.

5. The system of claim 1, wherein the processor is further programmed to receive the plurality of outstanding tasks from a client device.

6. The system of claim 1, wherein the processor is programmed to normalize the outstanding tasks by assigning the quantity of tokens to each of the outstanding tasks based on the amount of resources to be consumed during performance of each of the outstanding tasks, wherein each of the tokens represents consumption of the same amount of resources.

7. The system of claim 1, wherein the memory area further stores values, each value representing an amount of resources to be consumed by each of the tasks, and wherein the memory area further stores values representing an amount of resources available in the virtual datacenter.

8. The system of claim 7, wherein the processor is further programmed to update the values representing the amount of resources available in the virtual datacenter as resources are added and/or removed from the virtual datacenter.

9. The system of claim 1, wherein each of the plurality of outstanding tasks stored in the memory area is associated with a task type, each task type being associated with an amount of resources to be consumed.

10. The system of claim 1, further comprising means for iteratively determining an optimal token batch size to achieve optimal throughput in the virtual datacenter.

11. A method for iteratively determining an optimal amount of work to be performed efficiently by a computing device, the method comprising:

measuring, by a task management device, a first throughput at a first token batch size and a second throughput at a second token batch size, the first token batch size and the second token batch size each representing an amount of work performed by a computing device;

calculating, by the task management device, a rate of change between the measured first throughput at the first token batch size and the measured second throughput at the second token batch size;

selecting, by the task management device, a third token batch size based on the calculated rate of change;

providing a quantity of tasks corresponding to the selected third token batch size to the computing device for processing; and

repeating said measuring, said calculating, said selecting, said providing, and said repeating using the second token batch size as the first token batch size and the third token batch size as the second token batch size during said repeating.

12. The method of claim 11, wherein calculating the rate of change comprises calculating a gradient.

13. The method of claim 12, wherein selecting the third token batch size comprises selecting the third token batch size based on the calculated gradient.

14. The method of claim 11, wherein if the calculated rate of change is negative, further comprising throttling the amount of work performed by the computing device.

15. The method of claim 14, wherein throttling the amount of work comprises reducing the quantity of tasks to be performed by rejecting and/or queuing one or more of the tasks.

16. The method of claim 11, wherein measuring the second throughput at the second token batch size comprises measuring the second throughput at a second token batch size selected based on a quantity of outstanding tasks to be performed by the computing device.

17. One or more computer-readable storage media including computer-executable instructions that, when executed, cause at least one processor to intermittently identify maximal throughput in an environment having dynamically changing resources by:

measuring, by a task management device, a first throughput at a first token batch size and a second throughput at a second token batch size, the token batch size representing an amount of work performed by a computing device;

calculating, by the task management device, a rate of change between the measured first throughput at the first token batch size and the measured second throughput at the second token batch size; and

identifying an output batch size by;

if the calculated rate of change is negative, allocating a quantity of tokens based at least on the first token batch size to outstanding tasks to be performed by the computing device; and

otherwise, selecting, by the task management device, a third token batch size and repeating said measuring, said calculating, and said identifying using the second token batch size as the first token batch size and the third token batch size as the second token batch size during said repeating.

18. The computer storage media of claim 17, wherein the computer-executable instructions further cause the processor to normalize the outstanding tasks by weighting each of the outstanding tasks based on anticipated resource usage during performance of the outstanding task.

19. The computer storage media of claim 18, wherein the computer-executable instructions cause the processor to normalize the outstanding tasks by grouping the outstanding tasks into categories and dynamically weighting each of the categories.

20. The computer storage media of claim 18, wherein the computer-executable instructions cause the processor to normalize the outstanding tasks by associating a quantity of tokens with each of the outstanding tasks based on the anticipated resource usage during performance of the outstanding task.