Asynchronous task management in an on-demand network code execution environment

• US 10,282,229 B2
• Filed: 06/28/2016
• Issued: 05/07/2019
• Est. Priority Date: 06/28/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Wagner, Timothy Allen, Brooker, Marc John, Nair, Ajay
• Primary Examiner(s): Cao, Diem K
• Application Number:
  US15/195,920
• Publication Number:
  US 20170371703A1
• Time in Patent Office: 1,043 Days
• Field of Search: None
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• 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

Abstract

Systems and methods are described for managing asynchronous code executions in an on-demand code execution system or other distributed code execution environment, in which multiple execution environments, such as virtual machine instances, can be used to enable rapid execution of user-submitted code. When asynchronous executions occur, a first execution may call a second execution, but not immediately need the second execution to complete. To efficiently allocate computing resources, this disclosure enables the second execution to be scheduled accordingly to a state of the on-demand code execution system, while still ensuring the second execution completes prior to the time required by the first execution. Scheduling of executions can, for example, enable more efficient load balancing on the on-demand code execution system.

Claims

1. A system to manage asynchronous execution of tasks in an on-demand code execution system, the system comprising:

a non-transitory data store configured to store a queue of operations awaiting execution on the on-demand code execution system, wherein individual operations are associated with code executable to implement functionality corresponding to the individual operations; and

one or more processors configured with computer-executable instructions to;

obtain instructions to execute a first task associated with first executable code;

begin execution of the first executable code, wherein execution of the first executable code calls for execution of a first dependency operation;

determine a deadline for the first dependency operation based at least in part on historical data regarding prior executions of the first executable code;

determine that the deadline for the first dependency operation satisfies a threshold value, wherein the deadline indicates an expected point in time at which the execution of the first executable code will reach a state in which a result of the first dependency operation is required by the execution of the first executable code;

enqueue the first dependency operation into the queue based at least in part on the deadline;

process the queue based at least in part on an available capacity of the on-demand code execution system to execute operations, wherein processing the queue comprises executing the first dependency operation; and

notify the execution of the first executable code that the first dependency operation has completed.

2. The system of claim 1, wherein the one or more processors are configured to determine the deadline for the first dependency operation at least partly by:

identifying a reference to completion of the first dependency operation within the first executable code;

predicting a length of time until execution of the first dependency operation reaches the reference; and

assigning the length of time as the deadline for the first dependency operation.

3. The system of claim 1, wherein the one or more processors are configured to determine the threshold value based at least in part on a predicted length of time required for execution of the first dependency operation to complete.

4. The system of claim 1, wherein the one or more processors are further configured to:

begin execution of second executable code, wherein execution of the second executable code calls for execution of the first dependency operation; and

after executing the first dependency operation, select at least one of the execution of the first executable code or the execution of the second executable code to notify that the first dependency operation has completed.

5. The system of claim 4, wherein the one or more processors are further configured to:

in response to the call for execution of the first dependency operation by the execution of the second executable code, enqueue a second instance of the first dependency operation in the queue, wherein processing the queue further comprises executing a second instance of the first dependency operation; and

notify the execution of the second executable code that the first dependency operation has completed.

6. A computer-implemented method to manage asynchronous code executions in an on-demand code execution system, the computer-implemented method comprising:

initiating execution of first executable code on the on-demand code execution system, wherein execution of the first executable code calls for execution of a first dependency operation;

determining a deadline for the first dependency operation based at least in part on historical data regarding prior executions of the first executable code on the on-demand code execution system, wherein the deadline indicates an expected point in time at which the execution of the first executable code will reach a state in which a result of the first dependency operation is required by the execution of the first executable code;

enqueuing the first dependency operation into an execution queue based at least in part on the deadline;

processing the execution queue based at least in part on an available capacity of the on-demand code execution system to execute operations, wherein processing the execution queue comprises executing the first dependency operation; and

notifying the execution of the first executable code that the first dependency operation has completed.

7. The computer-implemented method of claim 6 further comprising determining that the deadline for the first dependency operation satisfies a threshold value, wherein the threshold value is set based at least in part on a predicted a length of time required for execution of the first dependency operation to complete.

8. The computer-implemented method of claim 6, wherein determining the deadline for the first dependency operation comprises:

identifying a reference to completion of the first dependency operation within the first executable code;

predicting a length of time until execution of the first dependency operation reaches the reference; and

assigning the length of time as the deadline for the first dependency operation.

9. The computer-implemented method of claim 8, wherein determining the deadline for the first dependency operation further comprises adjusting the deadline based at least in part on a predicted a length of time required for execution of the first dependency operation to complete.

10. The computer-implemented method of claim 8, wherein processing of the execution queue is further based at least in part on deadlines of operations within the queue.

11. The computer-implemented method of claim 8, wherein the dependency operation is a task on the on-demand code execution system, and wherein executing the dependency operation comprises executing second code on the on-demand code execution system.

12. The computer-implemented method of claim 8, wherein processing the execution queue further comprises:

determining that the execution queue comprises at least two instances of the same operation;

selecting an execution environment in the on-demand code execution system in which to execute the at least two instances; and

executing the at least two instances in the selected execution environment.

13. The computer-implemented method of claim 8, wherein notifying the execution of the first executable code that the first dependency operation has completed comprises receiving a request from a computing device executing the first executable code and responding to the request with a notification that the first dependency operation has completed.

14. The computer-implemented method of claim 8 further comprising:

during execution of second executable code, detecting a call to the first dependency operation by the second executable code;

determining that the execution of the first dependency operation, as called by the first executable code, satisfies the call to the first dependency operation by the second executable code; and

notifying the execution of the second executable code that the first dependency operation has completed.

15. The computer-implemented method of claim 8 further comprising:

detecting that execution of the first executable code has become blocked awaiting completion of the first dependency operation;

generating state information for the execution of the first executable code;

removing the execution of the first executable code from a first execution environment in which it was previously executing; and

wherein notifying the execution of the first executable code that the first dependency operation has completed comprises using the state information to resume execution of the first executable code within at least one of the first execution environment or a second distinct execution environment.

16. Non-transitory computer-readable storage media including computer-executable instructions that, when executed by a computing system, cause the computing system to:

initiate execution of first executable code on the on-demand code execution system, wherein execution of the first executable code calls for execution of a first dependency operation;

determine a deadline for the first dependency operation, wherein the deadline indicates an expected point in time at which the execution of the first executable code will reach a state in which a result of the first dependency operation is required by the execution of the first executable code;

enqueue the first dependency operation into an execution queue based at least in part on the deadline;

process the execution queue based at least in part on an available capacity of the on-demand code execution system to execute operations, wherein processing the execution queue comprises executing the first dependency operation; and

notify the execution of the first executable code that the first dependency operation has completed.

17. The non-transitory computer-readable storage media of claim 16, wherein the deadline for the first dependency operation is determined based at least in part on historical data regarding prior executions on the on-demand code execution system of at least one of the first executable code, other executable code related to the first executable code, or functions referenced in the first executable code.

18. The non-transitory computer-readable storage media of claim 16, wherein the computer-executable instructions further cause the computing system to determine that the deadline for the first dependency operation satisfies a threshold value, and wherein the threshold value is set based at least in part on a predicted a length of time required for execution of the first dependency operation to complete.

19. The non-transitory computer-readable storage media of claim 16, wherein the computer-executable instructions further cause the computing system to determine the deadline for the first dependency operation at least in part by:

identifying a reference to completion of the first dependency operation within the first executable code;

predicting a length of time until execution of the first executable code reaches the reference; and

assigning the length of time as the deadline for the first dependency operation.

20. The non-transitory computer-readable storage media of claim 19, wherein the predicted length of time until execution of the first executable code reaches the reference is based at least partly on a statistical measurement of prior executions of a portion of the first executable code between the call to the first dependency operation and the reference to completion of the first dependency operation.

21. The non-transitory computer-readable storage media of claim 20, wherein the statistical measurement is at least one of an average or a minimum length of time needed to execute the portion of the first executable code.

22. The non-transitory computer-readable storage media of claim 16, wherein the computer-executable instructions further cause the computing system to:

begin execution of second executable code, wherein execution of the second executable code calls for execution of the first dependency operation; and

after executing the first dependency operation, select at least one of the execution of the first executable code or the execution of the second executable code to notify that the first dependency operation has completed.

23. The non-transitory computer-readable storage media of claim 16, wherein the computer-executable instructions further cause the computing system to:

detect that execution of the first executable code has become blocked awaiting completion of the first dependency operation;

generate state information for the execution of the first executable code;

remove the execution of the first executable code from a first execution environment in which it was previously executing; and

wherein notifying the execution of the first executable code that the first dependency operation has completed comprises using the state information to resume execution of the first executable code within at least one of the first execution environment or a second distinct execution environment.

24. The non-transitory computer-readable storage media of claim 16, wherein the computer-executable instructions further cause the computing system to:

during execution of second executable code, detect a call to the first dependency operation by the second executable code;

determine that the execution of the first dependency operation, as called by the first executable code, satisfies the call to the first dependency operation by the second executable code; and

notify the execution of the second executable code that the first dependency operation has completed.