Multi-priority service instance allocation within cloud computing platforms

Patent metadata

Field	Value
Publication number	US-10630765-B2
Application number	US-201615751836-A
Country	US
Kind code	B2
Filing date	Aug 10, 2016
Priority date	Aug 10, 2015
Publication date	Apr 21, 2020
Grant date	Apr 21, 2020

Abstract

In various embodiments, methods and systems for optimizing allocation of multi-priority service instances are provided. In embodiments, a packing quality metric associated with each candidate node to which a service instance could be allocated are determined. An eviction cost associated with at least a portion of the candidate nodes to which the service instance could be allocated are determined. The eviction costs generally indicate a cost to evict a service instance from a corresponding node such that another service instance can be allocated to that node. At least a portion of the packing quality metrics and the eviction costs are used to select a node from the candidate nodes to which to allocate the service instance.

First claim

What is claimed is:

1. A system for optimizing allocation of multi-priority service instances, the system comprising: an allocator component configured for: identifying packing quality metrics associated with candidate nodes, each of the packing quality metrics indicating an extent to which a service instance to be allocated utilizes resources within a node; selecting a first subset of nodes of the candidate nodes based on the packing quality metrics; selecting a second subset of nodes of the candidate nodes based on eviction cost metrics associated with at least a first portion of the candidate nodes, each of the eviction cost metrics indicating cost to evict a service instance from a node such that another service instance can be allocated to that node; selecting a third subset of one or more nodes of the candidate nodes based on survival metrics associated with at least a second portion of the candidate nodes, wherein a survival metric indicates an extent that the service instance will not be evicted or will survive if deployed to a corresponding node; and allocating the service instance to one node within the first subset of nodes, the second subset of nodes, or the third subset of one or more nodes in accordance with the packing quality, eviction cost, and survival metrics.

2. The system of claim 1 , wherein the selection of the first subset of nodes of the candidate nodes is based on the candidate nodes associated with a greatest packing quality.

3. The system of claim 1 , wherein the first subset of nodes of the candidate nodes is selected based on the candidate nodes associated with a packing quality that exceeds a packing quality threshold.

4. The system of claim 1 , wherein the selection of the second subset of nodes is based on the nodes being associated with a lowest eviction cost.

5. The system of claim 1 , wherein the selection of the second subset of nodes is based on the nodes being associated with an eviction cost that exceeds an eviction cost threshold.

6. The system of claim 1 , wherein the selection of the third subset of the one or more nodes is based on the nodes being associated with a greatest survival value.

7. The system of claim 1 , wherein the selection of the third subset of the one or more nodes is based on the nodes being associated with a survival value that exceeds a survival threshold.

8. The system of claim 1 further comprising selecting the one node within the third subset of the one or more nodes based on the one node being associated with a greatest packing quality of the nodes within the third subset of the one or more nodes.

9. A computer-implemented method for optimizing allocation of multi-priority service instances, the method comprising: determining a packing quality metric associated with each candidate node to which a service instance could be allocated; determining an eviction cost associated with at least a portion of the candidate nodes to which the service instance could be allocated, each of the eviction costs indicating a cost to evict a service instance from a corresponding node such that another service instance can be allocated to that node; and utilizing at least a portion of the packing quality metrics and the eviction costs to select a node from the candidate nodes to which to allocate the service instance.

10. The method of claim 9 , further comprising allocating the service instance to the selected node.

11. The method of claim 9 , wherein the packing quality metric indicates an extent to which the service instance to be allocated corresponds with the corresponding node.

12. The method of claim 9 , wherein a survival metric is used with the at least the portion of the packing quality metrics and the eviction costs to select the node to which to allocate the service instance.

13. The method of claim 9 , wherein the packing quality metrics and the eviction costs are sequentially used to select the node to which to allocate the service instance.

14. One or more computer storage media having computer-executable instructions embodied thereon that, when executed, by one or more processors, causes the one or more processors to perform a method for optimizing allocation of multi-priority service instances, the method comprising: identifying a packing quality metric associated with each candidate node to which a service instance could be allocated; identifying a survival metric associated with at least a portion of the candidate nodes to which the service instance could be allocated, each of the survival metrics indicating an extent that the service instance will not be evicted or will survive if deployed to the corresponding node; and utilizing at least a portion of the packing quality metrics and the survival metrics to select a node from the candidate nodes to which to allocate the service instance.

15. The media of claim 14 , wherein eviction costs are used with the at least the portion of the packing quality metrics and the survival metrics to select the node to which to allocate the service instance.

16. The media of claim 14 , wherein each of the eviction cost metrics is based on the relative priority of an instance currently running on a node compared to the priority of an instance to be allocated to the node.

17. The media of claim 14 , wherein the survival metric is determined based on an independent danger probability for a node and an instance type pair.

18. The media of claim 17 , wherein the survival metric comprises a sum of terms, in which each term comprises an independent danger probability for a type of service instance.

19. The media of claim 16 , wherein the packing quality metrics and the eviction costs are sequentially used to select the node to which to allocate the service instance.

20. The media of claim 16 , wherein eviction costs are used with the at least the portion of the packing quality metrics and the survival metrics to select the node to which to allocate the service instance.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Moscibroda Thomas
• Chen Yang
• Johnson James E
• Mani Ajay
• Russinovich Mark Eugene

Classifications

• G06F9/505

  considering the load · CPC title

• G06F9/5088

  involving task migration · CPC title

• H04L67/10 Primary

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• H04L41/5022

  by giving priorities, e.g. assigning classes of service · CPC title

• H04L67/1002 Primary

  Electricity · mapped topic