Resource based virtual computing instance scheduling

Patent metadata

Field	Value
Publication number	US-10241840-B2
Application number	US-201615283274-A
Country	US
Kind code	B2
Filing date	Sep 30, 2016
Priority date	Sep 30, 2016
Publication date	Mar 26, 2019
Grant date	Mar 26, 2019

Abstract

Examples provide two-tiered scheduling within a cluster. A coarse-grained analysis is performed on a candidate set of hosts to select a host for a virtual computing instance based on optimization of at least one resource. A host is selected based on the analysis results. The identified virtual computing instance is placed on the selected host. A fine-grained analysis is performed on a set of communication graphs for a plurality of virtual computing instances to generate a set of penalty scores. A set of communicating virtual computing instances are selected based on the set of penalty scores. A first virtual computing instance from a first host is relocated to a second host to minimize a distance between the first virtual computing instance and a second virtual computing instance. Relocating the first virtual computing instance reduces at least one penalty score for the set of communicating virtual computing instances.

First claim

What is claimed is:

1. A system for resource scheduling, said system comprising:
at least one memory associated with a set of servers in a cluster, the at least one memory storing a fine-grained scheduler;
a plurality of virtual computing instances on the set of servers; and
at least one processor programmed to execute the fine-grained scheduler to:
analyze a set of communication graphs associated with the plurality of virtual computing instances to generate a set of penalty scores;
select a set of virtual computing instances for relocation based on the set of penalty scores; and
relocate a first virtual computing instance in the set of virtual computing instances from a first host in the cluster to a second host in the cluster to minimize a distance between the first virtual computing instance and a second virtual computing instance in the plurality of virtual computing instances, relocating the first virtual computing instance reduces at least one penalty score in the set of penalty scores associated with the set of virtual computing instances.

2. The system of claim 1 , further comprising:
a selection component, wherein the at least one processor is further programmed to execute the selection component to initialize a plurality of queues, each queue in the plurality of queues is associated with at least one resource, the at least one resource for each queue is a different resource or combination of resources, wherein a queue comprises an ordered list of hosts, and wherein each host in the plurality of hosts is assigned to at least one queue.

3. The system of claim 2 , further comprising:
a selection component, wherein the at least one processor further executes the selection component to select a predetermined number of hosts from each queue in a plurality of queues to generate a candidate set of hosts.

4. The system of claim 3 , further comprising:
a coarse-grained analyzer, wherein the at least one processor is further programmed to execute the coarse-grained analyzer to:
retrieve resource statistics for virtual computing instances in the candidate set of hosts and the resource statistics for the hosts in the candidate set of hosts;
analyze the resource statistics based on a coarse-grained optimization to select a host for placement of a given virtual computing instance, wherein the host is selected based on optimization of network resource; and
place the given virtual computing instance on the selected host.

5. The system of claim 1 , further comprising:
a group tag, wherein the at least one processor is further programmed to tag each virtual computing instance in a set of virtual computing instances with the group tag, wherein the group tag indicates virtual computing instances in the set of virtual computing instances are communicating virtual computing instances.

6. The system of claim 1 , wherein the at least one processor is further programmed to execute the fine-grained scheduler to:
check a tag associated with a given virtual computing instance to determine whether the given virtual computing instance is to be placed on a same host as one or more other virtual computing instances to minimize a distance between virtual computing instances.

7. The system of claim 1 , wherein the at least one processor is further programmed to execute the fine-grained scheduler to:
update host resource capacity of the second host to deduct resources consumed by a given virtual computing instance being placed on the second host.

8. A method comprising:
analyzing a set of communication graphs associated with the plurality of virtual computing instances to generate a set of penalty scores;
selecting a set of virtual computing instances for relocation based on the set of penalty scores; and
relocating a first virtual computing instance in the set of virtual computing instances from a first host in the cluster to a second host in the cluster to minimize a distance between the first virtual computing instance and a second virtual computing instance in the plurality of virtual computing instances, relocating the first virtual computing instance reduces at least one penalty score in the set of penalty scores associated with the set of virtual computing instances.

9. The method of claim 8 , further comprising:
initializing a plurality of queues, each queue in the plurality of queues being associated with at least one resource, the at least one resource for each queue comprising a different resource or combination of resources, wherein a queue comprises an ordered list of hosts, and wherein each host in the plurality of hosts is assigned to at least one queue.

10. The method of claim 9 , further comprising selecting a predetermined number of hosts from each queue in a plurality of queues to generate a candidate set of hosts.

11. The method of claim 10 , further comprising:
retrieving resource statistics for virtual computing instances in the candidate set of hosts and the resource statistics for the hosts in the candidate set of hosts;
analyzing the resource statistics based on a coarse-grained optimization to select a host for placement of a given virtual computing instance, wherein the host is selected based on optimization of network resource; and
placing the given virtual computing instance on the selected host.

12. The method of claim 8 , further comprising:
tagging each virtual computing instance in a set of virtual computing instances with the group tag, wherein the group tag indicates virtual computing instances in the set of virtual computing instances are communicating virtual computing instances.

13. The method of claim 8 , further comprising checking a tag associated with a given virtual computing instance to determine whether the given virtual computing instance is to be placed on a same host as one or more other virtual computing instances to minimize a distance between virtual computing instances.

14. The method of claim 8 , further comprising updating a host resource capacity of the second host to deduct resources consumed by a given virtual computing instance being placed on the second host.

Assignees

• Vmware Inc

Inventors

• Tsai Po-An
• Gamage Sahan
• Griffith Rean

Classifications

• G06F9/5083

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F9/5077 Primary

  Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455) · CPC title

• G06F9/505

  considering the load · CPC title