Durable Functions: Semantics for Stateful Serverless

Serverless, or Functions-as-a-Service (FaaS), is an increasingly popular paradigm for application development,
as it provides implicit elastic scaling and load based billing. However, the weak execution guarantees and
intrinsic compute-storage separation of FaaS create serious challenges when developing applications that
require persistent state, reliable progress, or synchronization. This has motivated a new generation of serverless
frameworks that provide stateful abstractions. For instance, Azure’s Durable Functions (DF) programming
model enhances FaaS with actors, workflows, and critical sections.
As a programming model, DF is interesting because it combines task and actor parallelism, which makes
it suitable for a wide range of serverless applications. We describe DF both informally, using examples, and
formally, using an idealized high-level model based on the untyped lambda calculus. Next, we demystify
how the DF runtime can (1) execute in a distributed unreliable serverless environment with compute-storage
separation, yet still conform to the fault-free high-level model, and (2) persist execution progress without
requiring checkpointing support by the language runtime. To this end we define two progressively more
complex execution models, which contain the compute-storage separation and the record-replay, and prove
that they are equivalent to the high-level model.