Fault-tolerant and transactional stateful serverless workflows

Presentation

• 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

Evaluation

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

Paper

Introduction

• 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

Design

(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