Fault-tolerant and transactional stateful serverless workflows


  • Serverless

    • AWS, Google cloud function, Microsoft Azure

    • Database: DynamoDB, ...

    • API gateway for communication

  • Motivation: Workers can fail

    • Receive error / timeout, should I retry?

      • Not sure whether crash or not before write

    • Write idempotent functions

      • Safely retry if previous invocation fails

      • Stateless function always idempotent

  • Contribution: make stateful serverless functions idempotent automatically

  • Write: log atomically

    • If have done write (check the log), skip it

    • If crash between writing and logging, do the writing the second time

    • Solution: collocate write log with the data

  • Challenge

  1. Limitation of databases

  • Can only hold limited data, need to do aggressive garbage collect

  • Solution: spread the log for a given key across multiple rows

  • Solution: use scan and projection to download a skeleton version of Linked DAAL (lock-free data structure)

    • 256 bits per row

    • Quickly traverse to the tail

2. Federated setup

  • Invocation with exactly-once semantics

  • Federated setup with serverless

    • Each lambda: own garbage collector

    • It's possible that before Lambda 1 gets resetted, the GC of lambda2 is triggered and clean up all the logs

    • Later, write in Lambda2 will be repeated again

  • Solution: call back

    • Complication: API gateway

    • Move the result from the callee side to caller side

3. Transactions across multiple lambdas


  1. costs of Beldi's API operations

    1. Operations: read, write, condWrite, invoke

    2. 2-4x more expensive than the baseline

  2. How does it perform in real-world application

    1. DeathStarBench (ASPLOS 19)

      1. Movie review service, travel reservation, social media site

    2. < 400 req/s: 2x higher

    3. < 700 req/s: 3.3x higher than baseline

  3. What is the effect of GC



  • Stateful serverless functions (SSFs) requires reasoning about the consistency and isolation semantics in the presence of concurrent requests and dealing with component failures

    • Unique idiosyncrasies that make existing approaches a poor fit

  • Peculiarities

    • Request routing is stateless

      • State machine replication are hard to implement because follow-up message might be routed by the infrastructure to a different SSF instance from the one that processed a prior knowledge

    • SSFs can be independent and have sovereignty over their own data

      • Different organizations develop and deploy different SSFs

    • SSF workflows (directed graphs of SSFs) can be complex and include cycles to express recursion and loops over SSFs

      • Transactions must observe consistent state to avoid undefined behavior

  • Beldi: library and runtime system for building workflows of SSFs

    • State: kept in low-latency db (e.x. DynamoDB)

    • SSFs: clients of scalable fault-tolerent storage services rather than stateful services themselves

    • Goal: guarantee exactly-once semantics to workflows, offer synchronization primitives to prevent concurrent clients from unsafely handling state

    • Extend Olive (OSDI 16')

      • operations beyond storage accesses (i.e. SSFs invocation to each other)

      • data structure for unifying storage of application state and logs

      • protocols that operate efficiently on this protocol

Backgrounds and Goals

  • Serverless functions: workflows

    • DAGs

      • Functions can be multi-threaded or perform async invocation

    • Step function: how to stich together different functions and their inputs and outputs, take care of scheduling and data movement, and user get an identifier to invoke it

    • Driver function: single function specified by developer that invokes other functions

  • Stateful serverless functions (SSFs)

    • Work-around to persist data: store it in fault-tolerant low-latency databases

    • Poorly with the way that existing platform handles failures

    • Current recommendation: write SSFs that are idempotent to ensure safety

  • Requirements

    • Exactly-once semantics

    • SSF data sovereignty

    • SSF reusability

    • Workflow transactions

    • Deployable today


(1) library: exposes API for invocations, db read / write, and transaction

(2) set of db tables that store the SSF's state and logs for reads, writes and invocations

(3) intent collector: serverless function that restarts any instance of the corresponding SSF that have stalled or crashed

(4) garbage collector: serverless function that keeps the logs from growing unboundedly

Executing and Logging Operations in Beldi

  • Linked DAAL

    • allows logs to exist on multiple rows (or atomicity scopes), with new rows being added as needed

  • Read

    • Read and log need not happen atomically

  • Write

    • Update and logging must be done atomically

    • Need to handle the case where SSFs are accessing and appending to the linked DAAL concurrently

Garbage Collection

  • Ensures that logs are pruned and the linked DAAL remains shallow with a GC that deletes old rows and log entries without blocking SSFs that are concurrently accessing the list

Locks and Transactions

  • Locks with intent

  • Transactions: based on a variant of 2PL, with wait-die deadlock prevention and two-phase commit

Last updated