Execution plan generation and scheduling for network-accessible resources

• US 9,479,382 B1
• Filed: 03/27/2012
• Issued: 10/25/2016
• Est. Priority Date: 03/27/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Ward, David John Jr.
• Primary Examiner(s): Joo, Joshua
• Assistant Examiner(s): Naji, Younes
• Application Number:
  US13/431,393
• Time in Patent Office: 1,673 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2009/45562 Creating, deleting, cloning virtual machine instances
• CPC Class Codes: G06F 2009/45575 Starting, stopping, suspending or resuming virtual machine instances
• CPC Class Codes: G06F 2209/5011 Pool
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: H04L 65/40 Support for services or applications
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Methods and apparatus for deadline-based pricing and scheduling of network-accessible resources are disclosed. A system includes resources organized into a plurality of pools, and a resource manager. The resource manager receives a task execution query comprising a specification of a task to be performed for the client. The specification includes the task'"'"'s deadline and a budget constraint. In response, the resource manager generates a task execution plan comprising using a resource from a selected pool to perform at least part of the task, where the pool is selected based at least partly on a pricing policy of the pool. In response to an implementation request for the task, the resource manager schedules at least a part of the task using a particular resource from the selected pool.

Claims

1. A system, comprising:

a plurality of computing devices configured to implement a plurality of resources of a provider network, wherein the resources are organized into a plurality of resource pools, wherein each resource pool of the plurality of resource pools has an associated pricing policy and an associated resource usage interruptibility policy, and wherein at least one resource pool of the plurality of resource pools has a different resource usage interruptibility policy than another one of the plurality of resource pools; and

one or more computing devices configured to implement a resource manager;

wherein the resource manager is configured to;

receive a task execution query comprising a specification of a task to be performed for a client using one or more resources of the plurality of resources, wherein the specification has an associated target deadline for completion of the task and an associated budget constraint for completion of the task;

determine an interruptibility characteristic of at least a portion of the task, wherein the interruptibility characteristic describes a suitability of the at least a portion of the task for being interrupted;

in response to receiving the task execution query and determining the interruptibility characteristic of the at least a portion of the task, generate an execution plan for the task, wherein the execution plan comprises using a resource of a selected resource pool to perform the at least a portion of the task, wherein the resource pool is selected from among the plurality of resource pools based at least in part on the associated pricing policy of the resource pool, the associated resource usage interruptibility policy of the resource pool, and the interruptibility characteristic of the at least a portion of the task;

provide an indication of the execution plan to the client; and

in response to a task implementation request from the client, schedule the at least a portion of the task using a particular resource from the selected resource pool.

2. The system as recited in claim 1, wherein the resource manager is further configured to:

determine the interruptibility characteristic of the at least a portion of the task based at least in part on one of;

an analysis of the task specification, an interruptibility setting indicated in the task execution query, or an analysis of a resource usage history record of the client.

3. The system as recited in claim 1, wherein the execution plan comprises a plurality of sub-tasks including a first sub-task and a second sub-task, wherein the resource manager is further configured to:

determine that the first sub-task and the second sub-task are to be performed in parallel based at least in part on one of;

a parallelizability setting indicated in the task execution query, or a parallelizability analysis of the task specification.

4. The system as recited in claim 1, further comprising an interface manager configured to:

implement a programmatic interface allowing the client to submit the task execution query,

wherein the task execution query is received via the programmatic interface.

5. The system as recited in claim 1, wherein the resource manager is further configured to:

determine a performance rating of the resource on which to schedule the at least a portion of the task, based at least in part on one of;

a resource performance setting indicated in the task execution query, or a requirements analysis of the task specification.

6. A method, comprising:

receiving a task execution query comprising a specification of a task to be performed for a client using one or more resources of a plurality of resources, wherein the specification has an associated target deadline for completion of the task, and wherein each resource of the plurality of resources has an associated pricing policy and an associated resource usage interruptibility policy, wherein at least one of the plurality of resources has a different resource usage interruptibility policy than another one of the plurality of resources;

determining an interruptibility characteristic of at least a portion of the task, wherein the interruptibility characteristic describes a suitability of the at least a portion of the task for being interrupted;

in response to receiving the task execution query and determining the interruptibility characteristic of the at least a portion of the task, generating an execution plan for the task, wherein the execution plan comprises using a resource of the plurality of resources to perform the at least a portion of the task, and wherein the resource is selected from the plurality of resources based at least in part on the associated pricing policy of the resource, the resource usage interruptibility policy of the resource, the associated target deadline, and the interruptibility characteristic of the at least a portion of the task; and

in response to a task implementation request from the client, scheduling the at least a portion of the task in accordance with the execution plan.

7. The method as recited in claim 6, further comprising:

determining the interruptibility characteristic of the at least a portion of the task based at least in part on at least one of;

an analysis of the task specification, an interruptibility setting indicated in the task execution query, or an analysis of a resource usage history record of the client.

8. The method as recited in claim 6, wherein the execution plan comprises plans for a plurality of sub-tasks including a first sub-task and a second sub-task, further comprising:

determining that the first sub-task and the second sub-task are to be performed in parallel based at least in part on one of;

a parallelizability setting indicated in the task execution query, or a parallelizability analysis of the task specification.

9. The method as recited in claim 6, further comprising:

implementing a programmatic interface allowing the client to submit the task execution query,

wherein the task execution query is received via the programmatic interface.

10. The method as recited in claim 6, wherein the specification comprises an indication that the task comprises one or more compute sub-tasks, wherein each sub-task of the one or more compute sub-tasks comprises an execution on a computing device of an executable component specified for the compute sub-task.

11. The method as recited in claim 6, wherein the specification comprises an indication that the task comprises one or more data transfer operations, wherein each operation of the one or more data transfer operations comprises a transfer of a specified data set from a source to a destination, wherein at least one of the source and destination of a particular data transfer operation of the one or more data transfer operations comprises the resource.

12. The method as recited in claim 11, wherein said scheduling the at least a portion of the task comprises one of:

(a) an initiation of a network transfer of the specified data set, using a network path sharable by two or more clients, at a time determined at least in part on the associated target deadline (b) an initiation of a network transfer of the specified data set, using a private network connection established between a client network of the client and a data center comprising the resource or (c) a transfer of a copy of the specified data set to the resource from a physical storage device transported from a client premise of the client to a data center comprising the resource.

13. The method as recited in claim 6, wherein the specification has an associated budget constraint of the client, and wherein the execution plan is based at least in part on the associated budget constraint.

14. The method as recited in claim 6, further comprising:

receiving a second task execution query comprising a second specification of a second task to be performed for a client using one or more resources of the plurality of resources, wherein the second specification has an associated budget constraint for completion of the second task, and wherein the second task execution query comprises a request for a target time for completion of the second task in accordance with the associated budget constraint; and

in response to receiving the second task execution query, generating an estimated target completion time for the second task, based at least in part on pricing policies of one or more resources of the plurality of resources and an analysis of the second specification.

15. The method as recited in claim 6, wherein the execution plan comprises plans for a plurality of sub-tasks, wherein a particular sub-task of the plurality of sub-tasks comprises the at least a portion of the task, further comprising:

implementing a programmatic interface allowing the client to obtain a current status of each sub-task of the plurality of sub-tasks.

16. The method as recited in claim 15, wherein the programmatic interface allows the client to obtain an indication of whether an exception is encountered during the particular sub-task.

17. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

receive a task execution query comprising a specification of a task to be performed for a client using one or more resources of a plurality of resources, wherein the specification has an associated target deadline for completion of the task, and wherein each resource of the plurality of resources has an associated pricing policy and an associated resource usage interruptibility policy, wherein at least one of the resources of the plurality of resources has a different resource usage interruptibility policy than another one of the plurality of resources;

determine an interruptibility characteristic of at least a portion of the task, wherein the interruptibility characteristic describes a suitability of the at least a portion of the task for being interrupted;

in response to receiving the task execution query and determining the interruptibility characteristic of the at least a portion of the task, generate an execution plan for the task, wherein the execution plan comprises using a resource of the plurality of resources to perform the at least a portion of the task, wherein the resource is selected from the plurality of resources based at least in part on the associated target deadline, the associated resource usage interruptibility policy of the resource, and the interruptibility characteristic of the at least a portion of the task; and

in response to a task implementation request from the client, schedule the at least a portion of the task in accordance with the execution plan.

18. The storage medium as recited in claim 17, wherein the instructions when executed on the one or more processors:

implement a programmatic interface allowing the client to submit the task execution query,

wherein the task execution query is received via the programmatic interface.

19. The storage medium as recited in claim 17, wherein the specification comprises an indication that the task comprises one or more compute sub-tasks, wherein each sub-task of the one or more compute sub-tasks comprises an execution on a computing device of an executable component specified for the compute sub-task.

20. The storage medium as recited in claim 17, wherein the specification comprises an indication that the task comprises one or more data transfer operations, wherein each operation of the one or more data transfer operations comprises a transfer of a specified data set from a source to a destination, wherein at least one of the source and destination of a particular data transfer operation of the one or more data transfer operations comprises the resource.

21. The storage medium as recited in claim 17, wherein the specification has an associated budget constraint of the client, wherein the execution plan is based at least in part on the associated budget constraint.

22. The storage medium as recited in claim 17, wherein the instructions when executed on the one or more processors:

receive a second task execution query comprising a second specification of a second task to be performed for a client using one or more resources of the plurality of resources, wherein the second specification has an associated deadline for completion of the second task, and wherein the second task execution query comprises a request for an estimated cost of completion of the second task in accordance with the associated deadline; and

in response to receiving the second task execution query, generating an estimated cost of completion of the second task, based at least in part on pricing policies of one or more resources of the plurality of resources and an analysis of the second specification.

23. A system, comprising:

a plurality of computing devices configured to implement a plurality of resources of a provider network, wherein the plurality of resources are organized into a plurality of resource pools, wherein each resource pool of the plurality of resource pools has an associated pricing policy and an associated resource usage interruptibility policy, wherein at least one of the plurality of resource pools has a different resource usage interruptibility policy than another one of the plurality of resource pools; and

one or more computing devices configured to implement a resource manager;

wherein the resource manager is configured to;

receive a task execution query comprising a specification of a task to be performed for a client using one or more resources of the plurality of resources, wherein the query comprises a request to generate a lowest-estimated-cost execution plan for the task;

determine an interruptibility characteristic of at least a portion of the task, wherein the interruptibility characteristic describes a suitability of the at least a portion of the task for being interrupted;

in response to receiving the task execution query and determining the interruptibility characteristic of the at least a portion of the task, generate an execution plan for the task, wherein the execution plan comprises using a resource of a selected resource pool to perform the at least a portion of the task, wherein the resource pool is selected based at least in part on the associated pricing policy of the resource pool, the associated resource usage interruptibility policy of the resource pool, and the interruptibility characteristic of the at least a portion of the task;

provide an indication of an estimated cost of the plan to the client; and

in response to a task implementation request from the client, schedule the at least a portion of the task using a particular resource from the selected resource pool.

24. A system, comprising:

a plurality of computing devices configured to implement a plurality of resource instances of a provider network; and

one or more computing devices configured to implement a resource manager;

wherein the resource manager is configured to;

receive a task execution query comprising a specification of a task to be performed for a client using one or more of;

(a) at least a specified number of resource instances of the plurality of resources, or (b) a network transfer of at least a specified data set;

determine an interruptibility characteristic of at least a portion of the task, wherein the interruptibility characteristic describes a suitability of the at least a portion of the task for being interrupted;

in response to receiving the task execution query and determining the interruptibility characteristic of the at least a portion of the task, generate an execution plan for the task, wherein the execution plan comprises using one or more resource instances of the plurality of resource instances to perform the at least a portion of the task, wherein the one or more resource instances are selected based at least in part on respective pricing policies of the one or more resource instances, respective resource usage interruptibility policies of the one or more resource instances, and the interruptibility characteristic of the at least a portion of the task, wherein at least one of the plurality of resources has a different resource usage interruptibility policy than another one of the plurality of resource instances; and

in response to a task implementation request from the client, schedule the at least a portion of the task using the one or more resource instances.