# 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 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://sliu583.gitbook.io/blog/specific-work/seminar-and-talk/fall-21-reading-list/fault-tolerant-and-transactional-stateful-serverless-workflows.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.