Source-linked AI summary
Costless: Optimizing Cost of Serverless Computing through Function Fusion and Placement
Tarek Elgamal, Atul Sandur, Klara Nahrstedt, Gul Agha
TL;DR
Serverless workflows introduce pricing decisions involving memory, execution, transitions, and placement, motivating cost optimization for AWS Lambda. The paper models these choices and uses an efficient fusion-placement algorithm to seek low-price solutions under latency constraints. In image-processing workflows, it reports price reductions exceeding 35%-57% with 5%-15% latency increases and identifies memory configurations that reduce both latency and price.
Problem
AWS Lambda workflow costs depend on function fusion, placement across edge and cloud resources, memory, execution, and transitions, making cost optimization nontrivial.
Method
The paper models price and execution time and explores function fusion-placement solutions with a constrained shortest-path algorithm.
Results
The algorithm finds solutions matching brute-force solutions and closely tracking AWS-log ground truth, while simple cloud-only and edge-only policies miss price-reduction opportunities.
Takeaways & Limitations
Jointly considering fusion, placement, and memory can reduce serverless application price while respecting latency constraints.
Abstract
from arXiv · showhide
Serverless computing has recently experienced significant adoption by several applications, especially Internet of Things (IoT) applications. In serverless computing, rather than deploying and managing dedicated virtual machines, users are able to deploy individual functions, and pay only for the time that their code is actually executing. However, since serverless platforms are relatively new, they have a completely different pricing model that depends on the memory, duration, and the number of executions of a sequence/workflow of functions. In this paper we present an algorithm that optimizes the price of serverless applications in AWS Lambda. We first describe the factors affecting price of serverless applications which include: (1) fusing a sequence of functions, (2) splitting functions across edge and cloud resources, and (3) allocating the memory for each function. We then present an efficient algorithm to explore different function fusion-placement solutions and find the solution that optimizes the application's price while keeping the latency under a certain threshold. Our results on image processing workflows show that the algorithm can find solutions optimizing the price by more than 35%-57% with only 5%-15% increase in latency. We also show that our algorithm can find non-trivial memory configurations that reduce both latency and price.
I. INTRODUCTION
Serverless platforms let developers deploy functions instead of managing virtual machines, but workflow pricing depends on execution, memory, and transitions. The paper studies AWS Lambda cost optimization through function fusion, placement, and resource-aware modeling.
- Serverless computing: Serverless computing lets developers deploy event-driven functions while the provider handles request reception, scheduling, and operational monitoring.
- Pricing model: AWS Lambda workflow pricing depends on executions, allocated memory, duration, per-GB-second pricing, and state transitions between functions.
- Optimization factors: Function fusion can remove transition charges, but differing memory requirements can make a fused function more expensive.
- Optimization factors: Edge placement through AWS Greengrass can process data near IoT sources, with device-based pricing independent of the number of functions executed there.
- Approach: The paper proposes models for AWS Lambda price and workflow execution time, then explores fusion-placement solutions using a constrained shortest-path formulation.
B. Factors affecting price of serverless applications
Serverless workflow cost is shaped by transitions, edge-versus-cloud placement, and function memory. The paper therefore treats fusion and placement jointly while accounting for their effects on both price and latency.
- Pricing factors: Serverless workflow pricing depends on state-transition count, edge-versus-cloud computation, and memory allocated to cloud functions.
- 1) Number of State Transitions:: Reducing transitions through function fusion can lower cost when transition charges dominate execution costs.
- 1) Number of State Transitions:: $52.3 versus $58.3: in the illustrated case, fusing FaceDetection and FaceDuplicate costs more than keeping them separate plus one transition.
- 1) Number of State Transitions:: Fusing parallel functions with their parent can serialize execution and increase workflow latency.
- 1) Number of State Transitions:: Fusion decisions must balance price and latency rather than minimize transitions alone.
2) Edge vs. Cloud Computation:
The paper models edge–cloud placement as a cost–latency trade-off: edge execution can reduce charges but may increase computation and transmission time. Memory allocation also changes both execution time and price.
- 2) Edge vs. Cloud Computation:: $0.16–$0.22 per edge device per month makes edge execution potentially cost-effective regardless of the number of functions placed there.The edge device communicates with the cloud through Amazon S3, which costs $0.023 per GB per month.
- 2) Edge vs. Cloud Computation:: Limited edge compute capacity can make function execution considerably slower, so compute-intensive applications may place only a subset of functions at the edge.
- 2) Edge vs. Cloud Computation:: Intermediate-data transmission between edge and cloud is non-trivial, motivating placement of functions that reduce transmission time on the edge.The model considers both computation and transmission times when selecting placements by price and latency.
- 3) Memory Allocation for each Function:: AWS allocates CPU proportionally to function memory, but doubling memory does not necessarily halve execution time because speed depends on implementation and CPU utilization.
- 3) Memory Allocation for each Function:: The algorithm treats memory configurations similarly to edge–cloud placements by exploring alternatives whose primary modeled effect is changing execution time.The paper focuses its discussion on one edge and one cloud configuration.
C. Workflow model:
The workflow is modeled as a DAG of dependent functions, with profiles describing execution, data-transfer, and memory characteristics. The model assigns placements and computes monthly price and workflow execution time from these properties.
- C. Workflow model:: A workflow is represented as a directed acyclic graph whose vertices are functions and whose links encode execution dependencies and data flow.An edge fi → fj means fi executes before fj and its output becomes the input of fj.
- D. Function Profile: Each function profile includes execution cost by placement, output-data size, and maximum memory consumption.Execution costs are denoted ei,E and ei,C, output size Dfi, and maximum memory mi.
- D. Function Profile: AWS Lambda memory allocation uses discrete allowed values, so actual consumption is rounded up to the closest larger permitted value.
- C. Workflow model:: A binary variable Xi indicates whether function fi runs in the cloud or on the edge.Xi = 1 denotes cloud execution and Xi = 0 denotes edge execution.
- C. Workflow model:: The monthly price combines cloud execution charges, state-transition charges, and the fixed edge-connection cost.For n functions executed r times, the transition component is multiplied by r(n + 1), after free requests and transitions are consumed.
- C. Workflow model:: Workflow execution time is defined as the completion time of the final function minus the start time of the first function.Function completion times are modeled recursively using prior completion time, cloud execution time, and transmission time.
G. Problem Definition:
The problem is to choose function fusions and placements that minimize price while keeping execution time below a threshold. Costless represents these alternatives in a cost graph and solves the resulting constrained shortest path problem.
- The optimization chooses a fused function graph and placement variables while minimizing price subject to an execution-time threshold.
- Each feasible solution decides which functions to fuse and assigns each fused function to the edge device E or cloud C.
- The cost graph represents each fused-function placement as a node and transitions between consecutive fused functions as links with price and delay costs.
- A path such as [(f1@E)(f2@C | f3@C)] places f1 on the edge and f2,f3 fused on the cloud.
- Because each link has independent price and time costs, the problem is formulated as a constrained shortest path rather than solved with standard shortest-path algorithms.
A. Costless Algorithm Steps:
Costless converts supported AWS workflows into an ordered function representation, enumerates fused functions and legal placements, builds a cost graph, and solves it with LARAC.
- Step 1: Create an intermediate representation: The algorithm represents sequential workflows by function order, parallel workflows by an ordered sequence while retaining the original DAG, and branching workflows by their main branch.
- Step 2: Construct cost graph: Adjacent functions in the sequence are grouped with parentheses to generate fused functions, including two-function and three-function combinations.
- Step 2: Construct cost graph: Placement sets allow functions beginning with f1 to run on edge E or cloud C, while later functions can only run on C because data does not flow from C to E.
- Step 3: Add cost graph links: The cost graph vertices are the union of all placement sets, and links connect nodes according to the sequence and its function successors.
- Step 4: Solve the CSP problem: LARAC solves the constrained shortest path by repeatedly applying Dijkstra’s algorithm to normalized aggregated price and delay costs.
B. Cost Calculation:
Costless assigns each graph link both price and execution-time costs, accounting for function execution, memory, scheduling, transitions, transmission, and parallelism.
- The path price and execution time are obtained by summing the corresponding link costs across consecutive functions or fused functions.
- For an edge-to-cloud transition, execution time includes transmission cost, while price includes the transition price and the relevant function costs.
- For parallel functions, execution time is bounded by the slowest function, whereas their prices are added separately.
- A fused-function link includes the fused execution cost based on combined execution time and maximum memory, plus one transition price.
- Fusing non-parallel functions causes one scheduling delay, adds their execution times, uses the maximum allocated memory, and produces one output transition.
C. Algorithm analysis
The algorithm’s complexity is dominated by solving the constrained shortest path on the cost graph with LARAC. The graph size depends on the number of devices and workflow functions.
- Solving the constrained shortest path is the step that dominates the algorithm’s complexity.
- LARAC’s CSP complexity is O(| E2 | log2(| E |)), where |E| is the number of cost-graph links.
- The placement parameter m equals 2 for one edge device and one cloud configuration, or 4 for one edge and three cloud configurations.
- The worst-case node out-degree occurs for f1@C and f1@E, which connect to fused functions beginning with f2 across possible placements.
- The resulting overall complexity is O(m4 ·n6 ·log2(m2 ·n3)).
V. EVALUATION
The evaluation profiles Wild Rydes and measures model accuracy, price under latency constraints, memory optimization, and search time for Costless.
- Application: Wild Rydes evaluates Costless on a five-function image-processing workflow implemented in JavaScript.The workflow includes face matching, thumbnail generation, face indexing, and metadata processing.
- Application Profiling: Costless profiling uses edge and cloud executions, two cloud memory configurations, AWS logs, and measured edge-to-cloud transfer time.The measured upload time averages 1.13 seconds for a 720p image of 1.2–1.5 MB.
- Evaluation Metrics: The evaluation compares estimated price and execution time with manually fused deployments and AWS billing information.It also compares deadline-constrained prices with brute force and heuristic baselines.
- Evaluation Metrics: Costless additionally searches memory configurations and measures solution-finding time as function graphs grow.The scalability experiment focuses on large function graphs.
A. Model Accuracy
The model-accuracy experiment compares Costless estimates against manually fused AWS deployments to assess agreement with observed price and execution time.
- A. Model Accuracy: All feasible fusion and placement combinations for the four eligible Wild Rydes functions were manually deployed on AWS as ground truth.Some fusions serialized two originally parallel functions.
- A. Model Accuracy: Costless price and execution estimates were very close to empirically measured values across the tested solutions.Execution-time discrepancies were attributed to variable scheduling delays of 100–300 ms.
B. Price vs. Execution time
Fusion and placement create a non-monotonic price–execution-time trade-off because fusion can remove transition overhead while serializing parallel work. Costless searches this space under latency constraints.
- B. Price vs. Execution time: Different fusion and placement choices produce multiple execution times at the same price, so higher price does not consistently imply lower execution time.Serializing parallel functions can reduce price while increasing execution time.
- B. Price vs. Execution time: The original graph is most expensive but fastest because it preserves parallelism between f3 and f4.The cheapest solution places f1 on the edge and fuses f2, f3, f4, and f5.
- C. Price within latency constraint: 37% cost reduction is achieved with a 5% latency increase, while the best result reaches 57% reduction with a 15% increase.The reported dollar comparison for the first result is $135 to $85; the best price is $58.
D. Effect of optimizing over memory configurations
Costless extends fusion and placement search to memory configurations, finding non-trivial settings that improve both price and execution time while supporting scalable solution search.
- D. Effect of optimizing over memory configurations: Costless searches 128 MB and 256 MB configurations for each function alongside fusion choices.For the non-fused case, five functions yield 25 memory combinations.
- D. Effect of optimizing over memory configurations: A memory increase for f3 produced the highest speedup and positively affected overall price and execution time.The result connects function-specific speedup with workflow-level optimization.
- D. Effect of optimizing over memory configurations: 6% price improvement and 10% execution-time improvement were achieved by the best memory configuration.The paper concludes that manually selecting memory settings is not ideal and exhaustive profiling is expensive.
- Related Work: Costless jointly models fusion and placement in one graph, distinguishing its constrained-shortest-path formulation from prior placement work.This unified graph represents both decisions together.