HORSE: Ultra-low latency workloads on FaaS platforms

Djob Mvondo, François Taı̈ani, Yérom-David Bromberg2024 · DOI

TL;DR

This paper tackles the challenge of running ultra-low latency (uLL) workloads on Function-as-a-Service (FaaS) platforms. They introduce HORSE, a novel approach that significantly speeds up the "warm start" resume process of sandboxes, achieving up to a 7.16x improvement and reducing initialization overhead by up to 142.84x. This makes FaaS a more viable option for latency-critical applications.

What Problem Does This Paper Address?

Modern cloud services are increasingly demanding ultra-low latency (uLL) – workloads requiring response times in the microsecond or even nanosecond range. While traditional infrastructure has been optimized for this, Function-as-a-Service (FaaS) platforms, known for their scalability and ease of use, have historically struggled to meet these stringent requirements. Even with "warm starts" (reusing an already initialized sandbox), the process of resuming a paused sandbox can introduce significant overhead. This overhead, particularly the time taken to re-integrate the sandbox's virtual CPUs (vCPUs) into the system's scheduling queues and update load information for frequency scaling, can consume a disproportionate amount of the total execution time, rendering FaaS unsuitable for uLL workloads. The paper aims to bridge this gap by making FaaS platforms capable of handling these latency-sensitive applications.

Methods

The core of HORSE lies in two novel techniques designed to optimize the sandbox resume process:

  • P²SM (Parallel Precomputed Sorted Merge): This algorithm addresses the bottleneck of merging the sandbox's vCPUs into the system's CPU-sorted run queues. Instead of performing a sequential merge for each vCPU, P²SM leverages precomputed data structures to achieve a sorted merge in constant time (O(1)). This significantly reduces the time spent on this critical step.
  • Load Update Coalescing: The second major optimization targets the update of a global variable that tracks CPU load for frequency scaling. Instead of updating this variable for each vCPU individually, HORSE coalesces these updates. It calculates the net effect of multiple updates using a mathematical formula and applies a single, optimized update. This drastically reduces the overhead associated with maintaining this critical system parameter.

These techniques are implemented within virtualization platforms like Xen and Firecracker, which are commonly used in FaaS environments.

Datasets

The paper does not explicitly mention using pre-existing datasets for training. Instead, it relies on:

  • Real-world FaaS traces from Azure serverless Cloud: These traces are used to evaluate the impact of HORSE on colocating uLL workloads with longer-running functions.
  • Micro-benchmarks: Custom micro-benchmarks are used to isolate and measure the performance of specific components of the resume process, such as the impact of varying vCPU counts.
  • SEBS benchmark suite (thumbnail generator): This is used in the evaluation of HORSE's impact on longer-running functions.

The paper does not introduce a new benchmark suite but rather uses existing traces and standard benchmarks to evaluate their proposed solution.

Key Insights and Ideas

  • Warm starts are not enough for uLL: Even when a sandbox is ready, the resume process itself can be a major bottleneck, consuming up to 61% of the total execution time for uLL workloads.
  • vCPU count exacerbates resume overhead: The time taken to resume a sandbox increases with the number of allocated vCPUs, as more vCPUs need to be re-integrated into the system.
  • Two operations dominate resume time: The insertion of vCPUs into run queues and the update of the CPU load variable are the primary culprits for slow resume times, accounting for up to 93.1% of the total resume overhead.
  • P²SM and coalescing are synergistic: Combining P²SM for efficient vCPU merging with load update coalescing yields the most significant performance improvements, demonstrating the power of addressing multiple bottlenecks simultaneously.
  • Dedicated run queues for uLL: HORSE utilizes a dedicated run queue for uLL workloads, ensuring that these latency-sensitive tasks are not impacted by longer-running functions.

Key Results

  • Significant resume time improvement: HORSE improves warm sandbox resume time by up to 7.16x.
  • Drastic reduction in initialization overhead: HORSE reduces sandbox initialization overhead for uLL workloads by up to 142.84x.
  • Minimal overhead: The overhead introduced by HORSE in terms of CPU and memory usage is less than 1%.
  • Constant O(1) resume time: With HORSE, the resume time becomes largely independent of the number of vCPUs, achieving a near-constant O(1) performance.
  • No negative impact on longer-running functions: When colocating uLL workloads with longer-running functions, HORSE shows negligible overhead on the latter, with only a minor impact on the 99th percentile latency in extreme cases.

Limitations and Future Work

  • Memory overhead: While small, HORSE does introduce a memory overhead of up to 528 KB for storing the P²SM data structures for paused sandboxes.
  • Potential for preemption: In rare cases, the high priority of merge threads in P²SM could preempt longer-running functions, leading to a slight increase in their 99th percentile latency.
  • Future work could explore:
    • Further optimizing the P²SM data structure updates.
  • Investigating the impact of HORSE on different FaaS platforms and virtualization technologies.
  • Exploring dynamic allocation of dedicated run queues based on workload characteristics.

Summary updated

Abstract

We investigate if FaaS platforms can handle ultra-low latency workloads that run as low as less than 1μs and show that even for a warm start, the initialization time takes up to 99, 99% of the total execution time. This is due to the resume process of warm sandboxes that takes more time as the number of the sandbox's allocated virtual CPUs (vCPUs) increases. We uncover that two operations use up to 93, 1% of the resume time. The first is the insertion of the paused sandbox's vCPUs to a CPU-sorted run queue. The second is the update of a lock-protected variable, which represents the vCPUs' load on each CPU. This variable is used for frequency scaling.
BibTeX
@misc{mvondo2024horse,
  author = {Djob Mvondo and François Taı̈ani and Yérom-David Bromberg},
  title = {{HORSE: Ultra-low latency workloads on FaaS platforms}},
  year = {2024},
  doi = {10.1145/3652892.3700784},
}
Figure