FaaSFlow: enable efficient workflow execution for function-as-a-service

Serverless workflows waste time asking a central master node for permission at every step, so FaaSFlow ships each worker its own piece of the workflow graph and lets functions on the same machine hand data to each other through memory.

Why this problem is worth solving

Serverless computing, also called Function-as-a-Service, lets a developer upload small functions and pay per invocation while the platform manages machines, containers and scaling. Real applications are rarely one function. A video pipeline splits, transcodes and merges; a machine-learning service preprocesses, predicts and postprocesses. These are serverless workflows: sets of functions with data dependencies, described as a directed acyclic graph — nodes are functions, edges say “this one needs that one’s output.”

The trouble is that serverless functions are small — often milliseconds to a few seconds of work — while the machinery around each step was inherited from an era of long-running jobs. Two costs repeat at every edge of the graph.

The trigger cost. Someone must notice a function finished and decide what runs next. In the classic architecture that someone is a central master node, so every step costs a report to the master, a decision, and a dispatch to a worker. The authors’ follow-up study measures this state-management gap on production platforms (AWS Step Functions, Azure Durable Functions, Alibaba Serverless Workflow) at about 63 milliseconds between adjacent functions — longer than many functions’ entire execution.

The data cost. Functions are stateless and containers can be recycled at any moment, so intermediate results are persisted to a backend database. Every edge of the graph becomes two network transfers: producer up to storage, storage down to consumer — even when both functions run on the same physical machine. In the same follow-up study, communication takes 26.0%, 49.5%, 35.3% and 89.2% of end-to-end latency across four representative workflows (video processing, image ML, matrix decomposition, word count).

Multiply these two taxes by every edge of every workflow invocation, and the platform spends most of its time on bookkeeping. That is the gap FaaSFlow attacks.

What people did before, and where it broke

The master-side schedule pattern — the paper’s name for the classic design — is not foolish. A single master with the whole graph and all execution state makes correctness easy: one place knows everything, one place decides everything. It was built for workflows of heavyweight tasks, where a 63-millisecond decision against minutes of computation is noise.

Serverless broke its assumptions from both directions. Functions shrank until the per-step overhead dominated, and workflows widened — many parallel edges, high invocation rates — until the master’s decision loop and the shared database became chokepoints. The database path also wastes the cluster’s own locality: two functions on the same node still ship data through a remote store, paying the network twice for bytes that never needed to leave the machine. And when the datacenter network is congested, everything degrades together, because every edge of every workflow rides the network.

The idea

Worker-side scheduling: ship the graph, not the commands

FaaSFlow’s first move is to relocate the decision-making. Instead of a master triggering every function everywhere, the workflow graph is partitioned and each worker node receives its own subgraph. A per-worker engine watches its local functions; when a function’s predecessors are complete, the engine triggers it locally — in-process bookkeeping, no network round trip, no master in the loop. The authors’ follow-up paper names this decentralized pattern WorkerSP (worker-side pattern) and credits it with reducing cross-node scheduling overhead.

Coordination does not disappear — it shrinks to the graph’s cut edges. Only when a dependency crosses from one worker’s subgraph to another’s do the engines synchronize. Every edge that the partition keeps internal to one node becomes overhead-free. This is the classic distributed-systems trade made well: global decisions (where each function lives) happen once per workflow, and per-invocation decisions (when each function fires) happen where the information already is.

The measured result, from the abstract: scheduling overhead falls by 74.6% on average.

FaaStore: let co-located functions share memory

Worker-side scheduling creates an opportunity: after partitioning, many producer-consumer pairs now live on the same machine. FaaStore, the paper’s adaptive storage library, exploits it. Data passed between functions on the same node goes through in-memory storage on that node — the released implementation uses Redis — skipping the remote database entirely. Only cross-node edges pay for remote storage. The abstract calls the library adaptive: it manages how memory is used for data passing alongside the functions’ own needs, though the sizing policy’s details are in the full text.

The measured result, from the abstract: data-transmission overhead falls by up to 95%, and when network bandwidth fluctuates, throughput degradation shrinks by 23.0% while usable network bandwidth multiplies by 1.5–4× — because most bytes no longer touch the network at all, the remaining transfers get the bandwidth to themselves.

per edge: report -> decide -> dispatch  (~63 ms measured)
per edge: upload to DB -> download from DB (2 network trips)

Why it works

Because a workflow’s structure is known before it runs, the expensive global decision — which worker owns which functions — can be made once at deployment, leaving only cheap local decisions at run time. → Because each worker’s engine holds its own subgraph, a finished function can trigger its successor in-process, so the per-step cost stops scaling with network latency and master load. → Because partitioning co-locates producers with consumers, most data edges become node-internal, and FaaStore turns node-internal edges into memory reads. → Because only cut edges still use the network, total network traffic drops by an order of magnitude — which is also why fluctuating bandwidth hurts less: fewer bytes compete for it, and the abstract reports usable bandwidth multiplying 1.5–4×. → Therefore both taxes on every graph edge — the trigger tax and the data tax — shrink together: scheduling overhead by 74.6% on average, data transmission by up to 95%.

What it costs

The abstract does not list the design’s prices, so the following are the natural costs of this architecture, stated as expectations rather than reported measurements.

• Correctness bookkeeping is now distributed. With no single master holding the truth, execution state lives in many engines that must stay consistent across cut edges — the classic price of decentralization.
• Partition quality decides the benefit. The gains come from edges made local; a workflow whose graph partitions badly (dense cross-dependencies, or functions too big to co-locate) keeps paying cut-edge costs.
• Memory is taken from the tenants. FaaStore’s in-memory data store competes for the worker’s RAM with the function containers themselves — the reason the library must be adaptive about sizing.
• Recovery on the same node weakens. Data held in a node’s memory rather than a replicated database is data lost if the node fails mid-workflow; handling this is exactly the kind of detail that lives in the full paper.

The evaluation, as far as the sources report it

From the abstract: FaaSFlow mitigates workflow scheduling overhead by 74.6% on average and data-transmission overhead by 95% at most. Under fluctuating network bandwidth, FaaSFlow with FaaStore reduces throughput degradation by 23.0% and multiplies network-bandwidth utilization by 1.5–4×.

From the authors’ follow-up paper (DataFlower, ASPLOS 2024), which re-measures FaaSFlow as a baseline: FaaSFlow’s benchmarks cover video processing, ML-based image processing, singular-value decomposition and word count; against production control-flow platforms those workflows spend 26–89% of latency on communication. The follow-up also locates FaaSFlow’s remaining ceiling: even with worker-side scheduling and local-memory data passing, functions are still triggered only after predecessors complete (the control-flow paradigm), so data is not streamed to successors early — the gap DataFlower itself was built to close, reporting up to 35.4% lower tail latency and up to 3.8× higher peak throughput beyond FaaSFlow-style systems.