SpecFaaS: Accelerating Serverless Applications with Speculative Function Execution

---

- Hide Paper Summary

---

Highlights:

1. Chained function execution is mostly deterministic on control (given the same invocation history) and data dependency (given the same input). We can leverage these characteristics to speculatively execute functions using branch prediction and input prediction.

2. The actual algorithm for speculative execution resembles how the processor schedules basic blocks and how Hardware Transactional Memory schedules transactions. In fact, functions in this context are just similar to the concept of basic blocks or transactions.

Comments:

1. The conflict detection protocol may cause inconsistent reads. Imagine two functions A and B with A being the logical predecessor of B and two global data items X and Y. If A writes X, B reads X and Y, then A writes Y, eventually, B will be squashed due to the WAR conflict on data item Y. However, before A writes Y, function B has already seen an inconsistent state where X is modified but Y is not. This inconsistent state will never occur during a serial execution and therefore would incur undefined behavior. In practice, such inconsistent reads may be harmless. But in the worse case, they can also cause serious problems such as infinite loops, invalid pointers, etc. This problem has been studied thoroughly under the context of HTM Optimistic Concurrency Control algorithms. Since SpecFaaS essentially adopts the HTM algorithms for function execution, the same issue would also arise here.

This paper proposes SpecFaaS, a function-as-a-service (FaaS) framework that enables the speculative execution of functions to speed up chained invocation. SpecFaaS is motivated by the high degree of both control and data determinism during chained invocation, i.e., with high probabilities, chained function execution will follow the same path given the same invocation history, and the outputs of a single function will be identical given the same inputs. To leverage such high degrees of determinism, SpecFaaS speculatively executes functions in a call chain and buffers their outputs until all the predecessors of the functions complete non-speculatively. Consequently, SpecFaaS can achieve much shorter overall execution latency in most cases as it effectively overlaps the execution of dependent functions, which will be serialized without SpecFaaS.

SpecFaaS aims at optimizing chained execution of serverless functions in FaaS platforms. In FaaS, an application is divided into basic execution units called “functions”, and each function can be separately invoked either locally or via RPC. The FaaS platform is responsible for managing the resource provisioning, scheduling, and the scaling aspects of functions, liberating programmers from such tasks. FaaS platforms support chained function execution in two fashions. In the first fashion, the control flow between functions is explicitly expressed using a procedure annotation language which enables common control flow nodes, such as conditional branches and data dependencies to be expressed and understood by the platform. In this case, the platform functions as a function scheduler, which selects the next function to execute when the previous one completes according to the control flow graph. In the second fashion, control flow information is expressed implicitly during runtime invocation, forming a hierarchical view of execution where a callee returns to the caller and resumes caller execution, rather than giving control to the scheduler.

To better understand the behavior of chained function execution, the paper conducted experimentation using three serverless benchmarks that use function chaining. The first observation is that function execution only constitutes a minor fraction of the total invocation latency even on warm starts (it becomes much worse for cold starts), with the major part of the overhead being the chained invocation (a.k.a. transfer function) and platform overhead. It is therefore more beneficial to optimize the entire process via overlapping rather than simply making execution faster which can only yield marginal improvement. Second, both the control and data dependency pattern is highly deterministic, meaning that the control flow will likely be the same when a branch occurs given the same execution history till the branching point, and that the output of a function will also likely be the same given the same input. This observation indicates that history-based branch prediction and memorization would both work well. Lastly, many functions do not frequently read or write global states, and even if they do, they typically do not access the same location in the global state. This observation suggests that the chained functions are unlikely to collide with each other via global state access, and therefore, executing them out-of-order would be a feasible choice. In addition, most functions do not have side effects that may prevent speculative execution. The most common types of side effects are global state accesses, temporary file creation, and sending HTTP requests.

Based on the above observations, SpecFaaS implements a speculative function execution mechanism where functions are started before their predecessors are completed. In this novel paradigm, functions that are in the same invocation chain can be executed out-of-order rather than being serially invoked by the platform, overlapping their execution and hence significantly reducing the end-to-end latency. Similar to speculative execution on hardware, functions must be validated after execution in order after they are completed in order to ensure that the control and data dependencies are not violated. If a function is validated successfully, it commits all global state modifications and exits.

SpecFaaS consists of three major components. The first component is the Sequence Table and Branch Predictor. The sequence table stores the control flow of the function, which can be either compiled from the explicitly provided function specification or implicitly inferred from the runtime execution trace. When the first function with a chain is invoked, the platform’s scheduler can speculatively invoke functions following the control flow graph. To deal with branches, the scheduler also actively predict the outcome of branches using the past execution history. As stated earlier, branches in chained functions are highly biased given the execution history. Therefore, for each branching node in the control flow, the scheduler maintains the Branch Predictor metadata which is a mapping between execution history and the frequencies of branch outcomes. Branch prediction is then performed by using the current dynamic execution history to query the map and then selecting the path with the highest probability. The branch predictor metadata is also updated when functions commit and become non-speculative.

The second component is the per-function Memoization Table which maps the function’s input to the output. The Memoization Table addresses the data dependency problem between consecutive functions on the call chain. When a function is speculatively invoked, if its input depends on the output of its predecessors, then the input will be provided by querying the Memoization Table with the input of the predecessor function, which itself may be from the Memoization Table of another function. When the function is committed, the non-speculative input and output are also inserted into the Memoization Table for future reference. An easy case that is worth mentioning is when the function is pure, meaning that it has no side-effect and that the output of the function entirely depends on its input. In this case, the function need not be executed until the validation point. If validation succeeds, i.e., the actual input of the function matches the speculative input, then the function is completed without consuming any resources. However, if validation fails, the function is still executed non-speculatively.

The third component is the Data Buffer, which serves two purposes. First, the data buffer temporarily holds global state writes by speculative functions such that they are not committed to the visible global state until the function commit point. Second, the Data Buffer also detects conflicts between functions. In SpecFaaS, functions conflict via Write-after-Read (WAR) and Write-after-Write (WAW) dependencies. If function A is logically ordered before function B in the control flow graph, but function A writes a global data item after function B reads or writes them during speculative execution, then a conflict occurs and function B must be squashed. The remaining type of conflict, i.e., Read-after-Write, is benign in SpecFaaS as the Data Buffer can just forward the item generated by an earlier function to the later function.

The Data Buffer is organized as a per-application lookup table indexed by the function name and the identifier of the global data item. Each entry has a read bit and a write bit, which are set when the item is read or written by the corresponding function, respectively. When a function is about to write an item, it looks up the table to figure out whether the item has been read or written by a successor function. If either of these is true, then the successor is forced to be squashed. Similarly, when a function is about to read a global data item, it searches its predecessors from the closest one to the more remote ones (on the control flow graph) for possible data forwarding. When a function successfully commits, it also commits all its Data Buffer items to the global storage by writing them back.

SpecFaaS commits functions in order. A function can successfully commit after all its predecessors have committed if the branch prediction result matches the actual direction and inputs are correctly predicted. If the function fails validation, then the function itself plus all of its successor functions will be squashed by the platform. After the function is squashed, it can be restarted in either speculation mode or serial mode depending on the configuration.

Implicit function chaining can be handled similarly, i.e., if a function invokes another function during past execution, the platform will start the second function speculatively before its invocation point. However, for implicit chaining, the platform will not speculatively execute the caller function past the invocation point, since in the case of implicit chaining, the caller function typically depends on the data returned by the callee.

SpecFaaS also handles system calls that can introduce side effects. The most prominent of them are socket send and file operations. To avoid these side effects, which cannot be easily squashed once they occur, from being observed during speculative execution, SpecFaaS instruments the user-space system call interface of these functions and buffers the operation until the function commits.