# 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 ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MksZwJSi_k_zOCbaczE%2F-MksagJVgUmndi3TvgNL%2Fimage.png?alt=media\&token=f9d3cf69-4dc4-4670-98bc-597704a11151) * 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 ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MksZwJSi_k_zOCbaczE%2F-MksbIC-168r6zjXG082%2Fimage.png?alt=media\&token=fccc4462-adfd-4fee-b050-3d5f99d39b3e) * 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 ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MksZwJSi_k_zOCbaczE%2F-MksblqYqXpbBqD3BN_s%2Fimage.png?alt=media\&token=35f46f06-433c-4f63-81d5-55bf85c403aa) 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 ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MksZwJSi_k_zOCbaczE%2F-MkscM_MY6SI1Zw1yyzY%2Fimage.png?alt=media\&token=5eb2546c-095b-4fca-84fe-05b0882224c5) * Solution: call back * Complication: API gateway * Move the result from the callee side to caller side ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MksZwJSi_k_zOCbaczE%2F-MkscmsStU9S5vHA5FoA%2Fimage.png?alt=media\&token=a32281dc-d36f-4132-8f05-8bf0a4ea234b) 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 ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-MksZwJSi_k_zOCbaczE%2F-MksdivWMwBGgOFSdrz7%2Fimage.png?alt=media\&token=fcf8ace9-1c5b-4b3d-a5ca-b0c1102de469) ### 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 ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-Mksdt3MEqbUAjMjRQM2%2F-Mkso4xaCtYMzaD4z2KR%2Fimage.png?alt=media\&token=cb920894-d8d6-4d02-9ed8-2dc689afc930) (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