Diminishing cold starts in serverless computing with approximation algorithms

Serverless products, such as Function as a Service (FaaS), orchestrate low-level resources (VMs, containers, CPUs, and memory) and software systems (schedulers, load balancers) into convenient and often moderately priced offerings. A large-scale FaaS provider hosts many small functions, most rarely executed. The provider cannot prepare in advance all environments to execute these functions, as each takes at least hundreds of MBs of memory. Thus, cold starts become a critical performance problem: when a user invokes a function while its serving environment is not ready, this setup may take several seconds, increasing the response time significantly (up to inadmissibly). While many systems approaches moderate this problem, we show that significant improvements can be made by carefully scheduling the invocations and explicitly considering cold starts. We use a formal scheduling model that extends the well-developed theory of scheduling with setup times. In this model, we design an approximation algorithm tuned to long, FaaS-specific setups. We additionally test the algorithm by simulation on realistic instances derived from cloud providers' workload traces. Compared with the published heuristic a recently proposed approximation algorithm of Deppert and Jansen, our method significantly reduces the length of the schedule.