> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/specific-work/seminar-and-talk/fall-21-reading-list/fault-tolerant-and-transactional-stateful-serverless-workflows.md). # 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 ![](/files/-MksagJVgUmndi3TvgNL) * 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 ![](/files/-MksbIC-168r6zjXG082) * 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 ![](/files/-MksblqYqXpbBqD3BN_s) 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 ![](/files/-MkscM_MY6SI1Zw1yyzY) * Solution: call back * Complication: API gateway * Move the result from the callee side to caller side ![](/files/-MkscmsStU9S5vHA5FoA) 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 ![](/files/-MksdivWMwBGgOFSdrz7) ### 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 ![](/files/-Mkso4xaCtYMzaD4z2KR) (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