Multi-priority service instance allocation within cloud computing platforms

Patent metadata

Field	Value
Publication number	US-11032359-B2
Application number	US-202016839357-A
Country	US
Kind code	B2
Filing date	Apr 3, 2020
Priority date	Aug 10, 2015
Publication date	Jun 8, 2021
Grant date	Jun 8, 2021

Abstract

In various embodiments, methods and systems for optimizing allocation of multi-priority service instances are provided. In embodiments, a quality metric associated with each candidate node to which a service instance could be allocated is determined. An eviction cost or a survival metric 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 quality metrics and either the eviction costs or the survival metrics are used to select a node from the candidate nodes to which to allocate the service instance.

First claim

The invention claimed is:

1. A system for allocation of service instances, the system comprising:
an allocator component configured for:
identifying a first subset of nodes of candidate nodes based on a first quality metric associated with candidate nodes;

identifying a second subset of nodes of the candidate nodes based on a second quality metric, wherein the second quality metric comprises at least one of an eviction cost metric associated with at least a first portion of the candidate nodes, each of the eviction cost metrics indicating cost to evict an existing service instance from a node such that another service instance can be allocated to that node and a survival metric that indicates an extent that the first service instance will not be evicted or will survive if deployed to a corresponding node; and
allocating the first service instance to one node within the first subset of nodes and the second subset of nodes based on the first quality metric and the second quality metric.

2. The system of claim 1 , further comprising determining if the existing service instance can be evicted from a node.

3. The system of claim 2 , wherein determining if the existing service instance can be evicted from a node comprises identifying the existing service instance as having a lower priority than the first service instance.

4. The system of claim 1 , wherein the extent that the first service instance will not be evicted quantifies the impact to the subsequent deployment of higher-priority instances.

5. The system of claim 1 , wherein the first quality metric comprises a packing quality metric 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.

6. The system of claim 1 , wherein the first quality metric and the second quality metrics are sequentially used to select the one node to which to allocate the first service instance.

7. The system of claim 1 , wherein the identifying a second subset of nodes of the candidate nodes is based on a comparison of the second quality metric to a threshold.

8. The system of claim 5 , wherein the packing quality metric is applied to high priority workloads.

9. The system of claim 1 , wherein the first service instance is a new service instance.

10. A computer-implemented method for evaluating allocation of a service instance, the method comprising:
determining a first 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 first quality metrics and the eviction costs to select a node from the candidate nodes to which to allocate the service instance.

11. The method of claim 10 , wherein the first quality metric comprises a packing quality metric 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.

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

13. The method of claim 10 , 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.

14. The method of claim 10 , wherein the service instance is a new service instance.

15. 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 evaluating allocation of a service instance, the method comprising:
determining a first quality metric associated with each candidate node to which a service instance could be allocated;
determining 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 first quality metrics and the survival metrics to select a node from the candidate nodes to which to allocate the service instance.

16. The method of claim 15 , wherein the first quality metric comprises a packing quality metric 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.

17. The method of claim 15 , further comprising allocating the service instance to the selected node.

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

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

20. The media of claim 15 , wherein the service instance is a new service instance.

Assignees

• Microsoft Technology Licensing Llc

Inventors

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

Classifications

• H04L67/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) · CPC title

• H04L67/1001 Primary

  for accessing one among a plurality of replicated servers · 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

• H04L67/1023

  based on a hash applied to IP addresses or costs · CPC title

• G06F9/5088

  involving task migration · CPC title