Network-level garbage collection in an on-demand code execution system

Patent metadata

Field	Value
Publication number	US-11526434-B1
Application number	US-201916452440-A
Country	US
Kind code	B1
Filing date	Jun 25, 2019
Priority date	Jun 25, 2019
Publication date	Dec 13, 2022
Grant date	Dec 13, 2022

Abstract

Systems and methods are described for management of garbage collection processes in an on-demand code execution system. An on-demand code execution system may execute user-submitted code on virtual machine instances. As each virtual machine instance executes code, garbage (e.g., memory that is allocated and then not properly de-allocated) may accumulate and may reduce the computing resources that the virtual machine instance makes available for allocation to further code executions. A garbage collection schedule manager may be used to generate a system-wide garbage collection schedule and manage garbage collection processes in accordance with the schedule. The garbage collection schedule manager may schedule garbage collection processes at times when demand for computing resources is forecasted to be low, and may coordinate scheduling of garbage collection processes across multiple virtual machine instances and host computing devices to prevent garbage collection processes from impacting code execution performance.

First claim

What is claimed is:

1. A system for managing garbage collection in an on-demand code execution system, the system comprising:
a processor in communication with a non-transitory data store; and
computer-executable instructions stored in the non-transitory data store, wherein the computer-executable instructions, when executed by the processor, configure the processor to perform operations including:
obtaining historical workload metrics regarding demand for a plurality of host computing devices, the demand comprising requests to execute user-submitted tasks on an on-demand code execution system;
determining, based at least in part on the historical workload metrics, a workload forecast for the plurality of host computing devices;
determining, based at least in part on the workload forecast, a garbage collection schedule, wherein the garbage collection schedule comprises a plurality of timeslots, wherein each of the plurality of timeslots is associated with a time at which the workload forecast predicts that future requests to execute user-submitted tasks will consume less than a threshold amount of computing resources of the plurality of host computing devices, and wherein a number of timeslots associated with individual times is determined based at least in part on the workload forecast;
receiving a request to schedule a first garbage collection process on a first virtual machine instance that is hosted on a host computing device of the plurality of host computing devices;
identifying a first open timeslot on the garbage collection schedule, the first open timeslot being associated with a first time; and
assigning the first open timeslot to the first virtual machine instance, wherein assigning the first open timeslot to the first virtual machine instance causes the first virtual machine instance to execute the first garbage collection process at the first time.

2. The system of claim 1 , wherein the first open timeslot comprises an earliest open timeslot on the garbage collection schedule.

3. The system of claim 1 , wherein the first garbage collection process comprises:
identifying one or more portions of a computing resource associated with the first virtual machine instance, wherein the one or more portions of the computing resource were allocated during one or more user-submitted task executions, have not been deallocated, and are no longer in use; and
deallocating the one or more portions of the computing resource.

4. The system of claim 3 , wherein the computing resource associated with the first virtual machine instance comprises a computer memory.

5. The system of claim 1 comprising further computer-executable instructions stored in the non-transitory data store, wherein the further computer-executable instructions, when executed by the processor, configure the processor to perform operations including:
processing a request to execute a user-submitted task on the on-demand code execution system, wherein processing the request comprises:
identifying, from a plurality of virtual machine instances that are each hosted on a computing device of the plurality of host computing devices, a virtual machine instance that is not currently executing a garbage collection process; and
causing execution of the user-submitted task on the virtual machine instance that is not currently executing a garbage collection process.

6. A computer-implemented method comprising:
determining, based at least in part on historical workload metrics for a plurality of host computing devices that execute user-submitted tasks in an on-demand code execution system, a workload forecast;
determining, based at least in part on the workload forecast, a garbage collection schedule, wherein the garbage collection schedule comprises a plurality of timeslots, wherein each of the plurality of timeslots is associated with a time, and wherein a number of timeslots associated with individual times is determined based at least in part on the workload forecast;
receiving a request to schedule a first garbage collection process on a first virtual machine instance that is hosted on one of the plurality of host computing devices;
identifying a first open timeslot on the garbage collection schedule; and
causing the first virtual machine instance to execute the first garbage collection process at a time associated with the first open timeslot.

7. The computer-implemented method of claim 6 , wherein identifying the first open timeslot on the garbage collection schedule is based at least in part on a capacity of the first virtual machine instance to defer execution of the first garbage collection process.

8. The computer-implemented method of claim 6 further comprising:
identifying a peak demand time at which the workload forecast predicts that future requests to execute user-submitted tasks will consume more than a threshold amount of computing resources of the plurality of host computing devices, wherein no timeslots in the garbage collection schedule are associated with the peak demand time;
selecting, from a plurality of times associated with open timeslots in the garbage collection schedule, an earlier time associated with a second open timeslot, the earlier time preceding the peak demand time;
identifying, from a plurality of virtual machine instances that are each hosted on a computing device of the plurality of host computing devices, a virtual machine instance that is likely to request scheduling of a garbage collection process at or near the peak demand time; and
assigning the second open timeslot to the virtual machine instance, wherein assigning the second open timeslot to the virtual machine instance causes the virtual machine instance to execute the garbage collection process at the earlier time.

9. The computer-implemented method of claim 8 , wherein selecting the earlier time is based at least in part on minimizing a difference between the earlier time and the peak demand time.

10. The computer-implemented method of claim 6 further comprising:
receiving a request to execute a user-submitted task on the on-demand code execution system;
obtaining, for individual virtual machine instances of a plurality of virtual machine instances that are each hosted on a computing device of the plurality of host computing devices, an estimated capacity to execute user-submitted tasks without first executing a garbage collection process;
selecting, based at least in part on the garbage collection schedule, the user-submitted task, and the estimated capacities of the individual virtual machine instances, a virtual machine instance to execute the user-submitted task; and
executing the user-submitted task on the virtual machine instance.

11. The computer-implemented method of claim 10 , wherein executing the user-submitted task on the virtual machine instance causes the virtual machine instance to request scheduling of a garbage collection process at a time when there is an open timeslot on the garbage collection schedule.

12. The computer-implemented method of claim 10 , wherein executing the user-submitted task on the virtual machine instance reduces a likelihood that the virtual machine instance will request scheduling of a garbage collection process at a time when there are no open timeslots on the garbage collection schedule.

13. The computer-implemented method of claim 10 further comprising estimating an amount of garbage generated by execution of the user-submitted task.

14. The computer-implemented method of claim 13 , wherein estimating the amount of garbage generated by execution of the user-submitted task is based at least in part on one or more p

Assignees

• Amazon Tech Inc

Inventors

• Brooker Marc John
• Lusk Andrew J
• Danilov Mikhail

Classifications

• G06F9/5016

  the resource being the memory · CPC title

• G06F12/0253 Primary

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F9/45558 Primary

  Hypervisor-specific management and integration aspects · CPC title

• G06F2009/45595

  Network integration; Enabling network access in virtual machine instances · CPC title

• G06F9/505

  considering the load · CPC title