Graph queries arrive in bursts, so running them on reserved cloud servers means paying all day for peak capacity — 85.7 percent of it wasted — and still watching tail latency jump from 1.5 seconds to over 30 when a spike arrives; serverless has exactly the right elasticity but the wrong shape, and dropping an existing graph engine onto it makes things 4.8 times worse and more expensive, so this paper (Shanghai Jiao Tong and NUS) rebuilds both sides at once, deliberately breaking the isolation between containers that all serve the same query and deleting a preprocessing step that only made sense on a machine that never turns off.
The argument in one glance
-
Problem
The traffic is spiky and the servers are not
Graph queries — routing on a road network, recommendations on a social graph — arrive unevenly. The authors show a real pattern from an industry partner where load varies through the day and occasionally spikes hard. Because the frameworks assume a stable cluster, operators reserve enough servers for the peak and leave them running. Over one day of that pattern, 85.7 percent of the reserved capacity does nothing. And it still does not work: when the midday spike arrives, tail latency goes from 1.5 seconds to more than 30.
-
What people did
Use the thing built for spiky workloads
Serverless computing exists for exactly this shape of problem. Functions start on demand, scale out automatically, and are billed only while running, which is why it works well for web services and short workflows. The obvious move is to take a state-of-the-art distributed graph framework, package its workers as functions, and let the platform handle the elasticity that the framework never had.
-
Why it fell short
The obvious move makes everything worse, including the bill
Measured on a 1.8-billion-edge graph, the ported framework spends up to 28.2 times longer in computation and 4.8 times longer per query overall, and costs 1.1 to 1.8 times MORE money despite billing in fine-grained units. Three things go wrong at once. Small containers force the graph into more pieces, and communication grows faster than the extra parallelism helps. Loading and preprocessing a large graph turns cold start into minutes, so a spike spawns containers that are all stuck starting. And the frameworks build memory-hungry index structures that make sense only on a machine that never turns off.
-
This paper's idea
Change both sides until they fit each other
This paper (Shanghai Jiao Tong University and NUS — Liu, Sun, Li, Chen, Gao, He, Li and Guo) co-designs the platform and the framework rather than porting one onto the other. Treat the group of containers serving one query as a single allocation unit, then deliberately break the isolation between them, since they all serve the same task anyway. When a spike arrives, queue behind a busy group instead of starting a new one, bounded so that waiting never costs more than a cold start would. And drop the preprocessing entirely by changing what the message-passing model requires.
Why this problem is worth solving
Two mismatches drive everything here, and both come from assumptions each side
made about the other.
SERVERLESS
computing runs user-supplied functions on demand, with the provider handling
allocation and scaling and the user billed only for what runs. The model carries
three assumptions. Each function instance gets small, fixed resources — the
containers here have 2 cores and 3 gigabytes. Functions cannot address each other,
so they communicate through remote storage. And when several functions cooperate,
the control flow between them is a predefined workflow of distinct steps. Graph
processing breaks all three. It needs far more memory than one container holds, so
the graph must be split across many. Its workers exchange vertex states every
ITERATION, which through remote storage is ruinous. And it is not a workflow of
different steps at all — it is one task forked across data partitions, every
partition running identical code
The other mismatch is subtler, because it is an optimization that was correct on
the machine it was designed for.
A
distributed graph framework running on always-on servers can afford to spend time
up front building auxiliary structures that make the actual computation fast — an
index of every vertex neighbourhood, and both incoming and outgoing edges stored
so the algorithm can alternate between pushing updates outward and pulling them
inward. On a reserved cluster this is free, because you build it once and the
server never stops. In a container that lives for one query it is paid every
single time, and the measurements are brutal: on a 1.8-billion-edge graph the
preprocessing takes 110 seconds against 115 seconds of actual computation, and in
most configurations it DOMINATES total query time. The index also costs memory
proportional to the whole vertex set in every partition, so adding containers does
not reduce the per-container footprint
What people did before, and where it broke
- Reserve servers for the peak and leave them running. The default, because the frameworks need a stable cluster and query latency has to stay low.
- But most of the capacity is idle most of the time. On the real workload pattern here, 85.7 percent of a day’s resources are wasted, and the spike still breaks it — tail latency going from 1.5 seconds to over 30.
- Start servers on demand instead. Pay only when there is work.
- But virtual machines take about 20 seconds to start, before the graph has even been loaded, so the first query of a burst waits a very long time.
- Predict the load and scale the cluster ahead of time. With a known daily pattern this genuinely reduces latency.
- But spikes are the part you cannot predict. With a scaling policy that adjusts every ten minutes on known patterns, the midday spike still pushes tail latency to over 14 seconds.
- Package the framework’s workers as serverless functions. The elasticity is exactly right, and containers start in under a second rather than twenty.
- But every property of the framework is now wrong. More partitions mean more communication, communication through remote storage is catastrophic, and preprocessing that was amortised across a server’s lifetime is now paid per query.
- The gap. Both sides were designed correctly for a world the other one does not live in, so no amount of porting fixes it. The framework assumes a machine that never stops; the platform assumes a task that barely runs.
How a graph query fits into functions
Co-designing the platform and the framework instead of porting one onto the other
-
Run a distributed graph framework on a reserved cluster
Split the graph across servers, iterate until convergence with each node updating its vertices and exchanging states with the others, and keep the cluster running so the setup cost is paid once. This is the established approach and it is genuinely fast at the computation itself.
-
Measure what actually dominates once it moves to functions new
Profile the ported framework stage by stage rather than trusting the usual figure of merit. In-memory computation, which is what the literature optimises, turns out to be a minority of query time; graph loading and preprocessing dominate, and the start-up they cause is what makes a spike expensive.
-
Make the group of containers, not the container, the unit new
A graph query is one task spread across data partitions, not a workflow of different steps. So allocate and release a whole set of containers together as a single unit, with one coordinator synchronising their iterations, and size that set from the memory the graph needs rather than from whatever the cluster has.
-
Break the isolation between containers serving the same query new
Isolation exists because containers normally serve unrelated tenants. Within one set they do not. So containers on a host share a memory buffer instead of talking through remote storage, and share a control group so an idle core in one can be used by another. Across hosts, a per-host proxy consolidates messages and sends them asynchronously.
-
Queue behind a busy set rather than starting a new one new
The default policy starts a container whenever none is free, which during a spike spawns many that are all stuck in a minutes-long cold start. Instead, join the shortest queue for a set already holding the right graph, with a bound ensuring the wait never exceeds what a cold start would have cost.
-
Delete the preprocessing by changing what the algorithm needs new
The index and the bidirectional edge storage exist to support alternating push and pull. Restrict message passing so only a partition own vertices initiate updates, and the index shrinks from the whole vertex set to just those vertices, only one edge direction is needed, and partitions can be read straight from storage with no preprocessing at all.
The idea
Isolation you are paying for and do not need. Containers are isolated from each other for excellent reasons: they usually run code belonging to different people, and the platform must guarantee that one cannot read or starve another. None of those reasons apply to the containers holding the partitions of a single graph query. They are one task, submitted by one user, running identical code on different slices of the same data — and yet the platform makes them talk through remote storage and prevents a container with idle cores from helping one that is overloaded. So the paper introduces a grouping abstraction whose whole purpose is to name the set of containers among which isolation is pointless, and then selectively removes it: a shared memory buffer for containers on the same host, a shared control group so CPU can flow between them, and a per-host proxy that merges messages destined for the same machine. The CPU sharing alone is worth up to 1.79 times, because splitting a graph into many small partitions creates load imbalance that a rigid per-container allocation cannot absorb. Identifying a protection boundary that is doing no protective work in a particular configuration, and dissolving it there rather than everywhere, is the same isolation-costs-something-so-charge-it-honestly argument covered elsewhere on this site where a barrier retained by default turns out to be pure overhead once you ask who it is defending against.
The number everybody optimises was not the number that mattered. This is the sharpest result in the paper and it is easy to miss. Graph processing research optimises in-memory computation, and the auxiliary index structures that make computation fast are the standard way to do it. The profiling here shows that on a large graph, preprocessing takes about as long as computation on a reserved server and dominates everything in a container, because a structure built once per server lifetime is now built once per query. So the redesign goes the other way: restricting message passing so that only a partition’s own vertices initiate updates shrinks the index from the size of the entire vertex set to the size of that partition, removes the need to store edges in both directions, and lets partitions be read directly out of storage — eliminating preprocessing outright. The consequence is stated plainly and is worth pausing on: the resulting system is SLOWER at in-memory computation than the frameworks it beats, and wins anyway, because it deleted a larger term. Discovering that the metric a field has been improving for years is not the one controlling end-to-end outcomes is the same optimise-the-term-that-dominates correction covered elsewhere on this site where a carefully tuned inner loop turns out to be a small fraction of what users actually wait for.
When starting is expensive, waiting is the cheaper answer. Serverless platforms scale without bound by default: a request arrives, no container is free, start one. That is correct when starting costs milliseconds. Here it costs minutes, because the container must load and prepare a multi-gigabyte graph, so a spike produces a crowd of containers that are all simultaneously stuck starting, none of them serving anything, all of them holding memory — and then held for fifteen minutes more by the keep-alive policy, with 23.6 percent of memory wasted. The alternative is almost embarrassingly simple: queue. A new query joins the shortest queue among the sets already holding the right graph, and only allocates a new set if every queue is long enough that waiting would cost more than a cold start. That bound is the part that makes it defensible rather than a gamble, since it guarantees the query never does worse than it would have done by starting fresh. Replacing an eager allocation policy with a bounded wait, justified by comparing the wait against the cost of the thing you are avoiding, is the same admission-control-beats-overprovisioning instinct covered elsewhere on this site where a system declines to spin up capacity because the queue is cheaper than the cold path.
Following a query spike through both designs
What happens at noon, on reserved servers and on functions
Measurements on a 1.8-billion-edge graph and a real road-network query pattern from an industry partner.
Step 1 of 5
The baseline: reserve for peak and hope
Enough servers run all day to handle the busiest minute. Over the observed pattern that wastes 85.7 percent of the capacity, and it still fails where it matters: when the midday spike arrives, tail latency rises from about 1.5 seconds to more than 30. Scaling the cluster on a predicted daily curve helps but still spikes to over 14 seconds, because spikes are the unpredictable part.
starting a virtual machine takes about 20 seconds before the graph is even loaded, which is why on-demand provisioning does not rescue this a container starts in under a second, which is the elasticity the workload wants
Why it works
- Containers within one query serve one task and one user → the isolation between them protects nothing and can be dissolved into shared memory and shared CPU → removing remote-storage communication and recovering up to 1.79 times from load imbalance.
- Preprocessing was amortised over a server lifetime and is now paid per query → restricting who initiates updates removes the index and the second edge direction entirely → so the dominant term disappears instead of being optimised.
- More partitions increase communication faster than they add useful parallelism → sizing the container set from the memory the graph needs rather than the cluster size → keeping both the bill and the message volume down.
- Cold start costs minutes because a multi-gigabyte graph must be loaded → queueing behind a busy group beats starting a new one whenever the wait is shorter → cutting memory footprint 21.1 percent while keeping tail latency flat through a spike.
- Billing is per second of allocated resource → eliminating idle reserved capacity matters more than raw computation speed → giving 85.7 percent cost reduction on a real bursty workload despite slower in-memory compute.
What it costs (trade-offs and scope)
- It deliberately breaks container isolation. Shared memory segments and shared control groups between containers are exactly what the sandbox exists to prevent. The security discussion suggests authentication and secure container runtimes but implements and evaluates neither.
- Reserved servers still win on sustained heavy load. The cost curves cross; above a certain sustained query rate, always-on virtual machines are cheaper, which the authors state directly.
- The serverless baseline is simulated. The framework being ported needs addressable workers, which commodity serverless platforms do not offer, so all measurements run in the authors’ own container environment rather than on a real platform.
- Two key results come from simulation or synthesis. The queueing evaluation is simulated because the resources needed exceed the testbed, and the case study trace is randomly synthesised from the observed pattern because per-query details were not available.
- Some parameters are hand-set. The memory amplification factor used to size a container set is fixed at 1.45, and choosing between push and pull message passing is left to the user after a few trial runs.
The evaluation
Four graphs from about a million to 1.8 billion edges, four standard algorithms, compared against three distributed frameworks, one shared-memory framework, and the naively ported version of the strongest baseline. The comparison is run both one-shot, where resources start from nothing, and as a sustained stream, where reserved machines get to amortise their start-up. The most informative part is the ablation, which separates the graph-side changes from the platform-side ones and shows that removing preprocessing carries most of the benefit while the isolation breaking adds a further large factor on top.
| Property | Reserved servers, always on | Framework ported to functions | Co-designed serverless graph engine |
|---|---|---|---|
| Idle capacity on a bursty day | |||
| Tail latency through a spike | |||
| Where query time goes | |||
| How workers communicate | |||
| Cost over one real day |
Check yourself
Check your understanding
1. Packaging a state-of-the-art graph framework as serverless functions gives the elasticity the workload needs, yet total query time gets 4.8 times worse and the bill goes up. Predict what goes wrong.
2. The design shares a memory buffer and a CPU control group between containers, which is exactly what container isolation exists to prevent. Predict the argument for doing it.
3. The system ends up SLOWER at in-memory computation than the frameworks it outperforms end to end. Predict how that is possible.
4. When a query spike arrives and no container group is free, the system waits instead of starting a new group. Predict why waiting beats scaling here, and what stops it from waiting too long.
Sources
- Yushi Liu, Shixuan Sun, Zijun Li, Quan Chen, Sen Gao, Bingsheng He, Chao Li and Minyi Guo. “FaaSGraph: Enabling Scalable, Efficient, and Cost-Effective Graph Processing with Serverless Computing.” ASPLOS 2024, La Jolla. Shanghai Jiao Tong University and the National University of Singapore. DOI 10.1145/3620665.3640361.
- Full text of the paper was used for this explainer, including the profiling study of a ported framework in Section 2, the container-set abstraction and data-centric execution model in Section 3, locality-aware resource fusion and bounded resource scaling in Section 4, the query optimizer, message passing and storage changes in Section 5, and the comparisons, ablation study, overhead measurements and industry-pattern case study in Section 6.
- The authors released their implementation publicly.