OPPORTUNISTIC RESOURCE MIGRATION TO OPTIMIZE RESOURCE PLACEMENT

• US 20160269313A1
• Filed: 03/09/2015
• Published: 09/15/2016
• Est. Priority Date: 03/09/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: GREENWOOD, CHRISTOPHER MAGEE, DHOOLAM, SURYA PRAKASH, FLAHERTY, MITCHELL GANNON, BROOKER, MARC JOHN, THOMPSON, JAMES MICHAEL, OLSON, MARC STEPHEN
• Granted Patent: US 10,715,460 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

A distributed system may implement opportunistic resource migration to optimize resource placement. Resources may be placed amongst different resource hosts of a distributed system. An evaluation of the current placement may be performed according placement criteria that improve placement of the resources at the distributed system. Based on the evaluation, the prospective migration of resources that exceed an improvement threshold may be identified as candidate resources to migrate. Migration for the candidate resources may be opportunistically performed. In some embodiments, a priority may be assigned to the candidate resources according to which the candidate resources are selected for performing migration.

Claims

1. A distributed system, comprising:

a plurality of resource hosts respectively hosting one or more of a plurality of resources;

an opportunistic placement manager, configured to;

evaluate current placements of the plurality of resources according to one or more placement criteria, wherein the one or more placement criteria improve resource placement amongst the plurality of resource hosts for the distributed system;

based, at least in part, on the evaluation, identify one or more candidate resources of the plurality of resources to migrate from the respective resource hosts currently hosting the one or more candidate resources to respective destination resource hosts of the plurality of resource hosts, wherein the prospective migrations of the one or more candidate resources of the plurality of resource exceed an improvement threshold with respect to the one or more placement criteria; and

direct a migration operation to migrate at least one of the one or more candidate resources to the respective destination resource host, wherein the migration of the at least one candidate resource to the respective destination resource host improves resource placement of the plurality of resources host in excess of the improvement threshold.

2. The system of claim 1,

wherein to identify the one or more candidate resources of the plurality of resources, the opportunistic placement manager is configured to:

determine respective priorities for migration of the one or more candidate resources;

place respective migration operations for the one or more candidate resources into a queue;

wherein the opportunistic placement manager is further configured to;

based, at least in part, on an evaluation of the queue, select the at least one candidate resource to migrate according to the respective priorities assigned to the one or more candidate resources.

3. The system of claim 2, further comprising:

a plurality of migration workers;

wherein, to direct the migration operation to migrate the at least one candidate resource, the opportunistic placement manager is configured to send the migration operation to one of the plurality of migration workers to perform.

4. The system of claim 1, wherein the distributed system is a virtual block-based storage service, wherein the plurality of resources are a plurality of data volumes maintained for a plurality of clients of the virtual block-based storage service.

5. A method, comprising:

performing, by one or more computing devices;

evaluating current placements of a plurality of resources hosted at respective ones of a plurality of resource hosts of a distributed system according to one or more placement criteria, wherein the one or more placement criteria improve resource placement amongst the plurality of resource hosts for the distributed system;

based, at least in part, on the evaluation, identifying one or more candidate resources of the plurality of resources to migrate from the respective resource hosts currently hosting the one or more candidate resources to respective destination resource hosts of the plurality of resource hosts, wherein the prospective migrations of the one or more candidate resources of the plurality of resource exceed an improvement threshold; and

migrating at least one of the one or more candidate resources to the respective destination resource host, wherein the migration of the at least one candidate resource to the respective destination resource host improves resource placement of the plurality of resources in excess of the improvement threshold.

6. The method of claim 5,

wherein identifying one or more candidate resources of the plurality of resources comprises assigning respective priorities for performing migration of the one or more candidate resources;

and

wherein the method further comprises selecting the at least one candidate resource to migrate according to the respective priorities assigned to the one or more candidate resources.

7. The method of claim 6, further comprising:

updating the respective priorities of the one or more candidate resources according to another evaluation of the current placements of the plurality of resources; and

selecting another one of the one or more candidate resources to migrate according to the updated respective priorities of the one or more candidate resources.

8. The method of claim 6,

wherein identifying the one or more candidate resources of the plurality of resources further comprises placing respective migration operations for the one or more candidate resources into a queue;

and

wherein selecting the at least one candidate resource to migrate according to the respective priorities assigned to the one or more candidate resources is performed based on an evaluation of the queue.

9. The method of claim 8, further comprising removing at least one of the one or more candidate resources from the queue according to another evaluation of the current placements of the plurality of resources.

10. The method of claim 5, wherein evaluating current placements of the plurality of resources hosted at the respective ones of the plurality of resource hosts of the distributed system according to the one or more placement criteria comprises:

generating respective placement scores for the current placements of the plurality of resources according to the one or more placement criteria;

wherein identifying the one or more candidate resources of the plurality of resources comprises;

generating respective placement scores for one or more possible placements of the plurality of resources according to the one or more placement criteria;

calculating respective score differences between the respective placement scores for the current placements and the respective placement scores for one or more possible placements; and

determining as the one or more candidate resources those resources with respective score differences that exceed the improvement threshold.

11. The method of claim 5, wherein the resource is one of a plurality of resources that implement a distributed resource, wherein the one or more placement criteria comprise an evaluation of a current placement configuration for the plurality of resources of the distributed resource.

12. The method of claim 5, wherein migrating the at least one of the one or more candidate resources to the respective destination resource host comprises identifying the destination resource host.

13. The method of claim 5, wherein migrating the at least one candidate resource to the respective destination resource host improves placement for another resource of the plurality of resources.

14. The method of claim 5, wherein the distributed system is a network-based service, wherein the plurality of resources are maintained at the network-based service for a plurality of clients of the network-based service, and wherein the evaluating, the identifying, the migrating are performed as part of a background service for the network-based service.

15. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

evaluating current placements of a plurality of resources hosted at respective ones of a plurality of resource hosts of a distributed system according to one or more placement criteria, wherein the one or more placement criteria improve resource placement amongst the plurality of resource hosts for the distributed system;

based, at least in part, on the evaluation, identifying one or more candidate resources of the plurality of resources to migrate from the respective resource hosts currently hosting the one or more candidate resources to respective destination resource hosts of the plurality of resource hosts, wherein the prospective migrations of the one or more candidate resources of the plurality of resource exceed an improvement threshold; and

migrating at least one of the one or more candidate resources to the respective destination resource host, wherein the migration of the at least one candidate resource to the respective destination resource host improves resource placement of the plurality of resources in excess of the improvement threshold.

16. The non-transitory, computer-readable storage medium of claim 15,

wherein, in identifying one or more candidate resources of the plurality of resources, the program instructions cause the one or more computing devices to implement assigning respective priorities for performing migration of the one or more candidate resources;

and

wherein the program instructions further cause the one or more computing devices to implement selecting the at least one candidate resource to migrate according to the respective priorities assigned to the one or more candidate resources.

17. The non-transitory, computer-readable storage medium of claim 16, wherein the program instructions cause the one or more computing devices to further implement:

updating the respective priorities of the one or more candidate resources according to another evaluation of the current placements of the plurality of resources; and

selecting another one of the one or more candidate resources to migrate according to the updated respective priorities of the one or more candidate resources.

18. The non-transitory, computer-readable storage medium of claim 16,

wherein, in identifying the one or more candidate resources of the plurality of resources, the program instructions cause the one or more computing devices to further implement placing respective migration operations for the one or more candidate resources into a queue;

and

wherein selecting the at least one candidate resource to migrate according to the respective priorities assigned to the one or more candidate resources is performed based on an evaluation of the queue.

19. The non-transitory, computer-readable storage medium of claim 18, wherein the program instructions cause the one or more computing devices to implement:

determining that the respective migration operation for the at least one candidate resource is complete; and

in response to determining that the respective migration operation is complete, removing the respective migration operation from the migration queue.

20. The non-transitory, computer-readable storage medium of claim 15,

wherein, in evaluating current placements of the plurality of resources hosted at the respective ones of the plurality of resource hosts of the distributed system according to the one or more placement criteria, the program instructions cause the one or more computing devices to implement generating respective placement scores for the current placements of the plurality of resources according to the one or more placement criteria;

wherein, in identifying the one or more candidate resources of the plurality of resources, the program instructions cause the one or more computing devices to implement;

generating respective placement scores for one or more possible placements of the plurality of resources according to the one or more placement criteria;

calculating respective score differences between the respective placement scores for the current placements and the respective placement scores for one or more possible placements; and

determining as the one or more candidate resources those resources with respective score differences that exceed the improvement threshold.

21. The non-transitory, computer-readable storage medium of claim 15, wherein the distributed system is a virtual block-based storage service, and wherein the plurality of resources are data volumes maintained for a plurality of clients of the virtual block-based storage service.