文章主要将MasterSP改成了WorkerSP，MasterSP原来负责分配函数任务和统计执行状态，现在只负责DAG分割。

开源：https://github.com/lzjzx1122/FaaSFlow

Background

Master-side Workflow schedule pattern

主节点从工作节点收集函数的执行状态，确定工作流中的函数是否满足其触发条件。一旦函数f的前身全部完成，任务\(T_f\)将被触发并分配给一个工作节点进行调用，并将执行状态返回。

使用MasterSP的主引擎仍然需要收集状态并检查执行的触发条件，即使一个函数和它的前辈在同一个工作节点上。这导致了大量无用的网络交互和函数间的长响应延迟。

overhead evaluation

MasterSP中的每个函数调用包含三个阶段。

从主引擎分配函数任务
执行函数调用
将执行状态返回给主引擎

MasterSP的大量调度开销在第一和最后一个阶段被大量引入。

data shipping pattern

应用程序是由细粒度的函数构建的，并通过预先定义的逻辑步骤执行。每次函数任务运行时，需要从其前身函数中获取输入数据，然后读入内存，由容器执行者执行。

与直接构建单体应用相比，函数隔离带来了更多的任务间数据通信的开销。

在不考虑数据定位的情况下，即使两个相邻的函数在同一个节点上，也会有大量的开销，即通过不必要的数据库进行数据传输。
此外，由于无服务器架构的限制，功能之间的直接数据传输接口并不能提供足够的数据传输配额。
此外，在工作流场景中，数据传输的配额会更小，因为不受限制的数据大小会使集群中的带宽资源被剧烈消耗，从而导致性能瓶颈。这使得用户在处理功能任务之间的大文件和大对象时，必须使用远程存储服务作为中间桥梁。

对于无服务器的工作流程来说，有必要加强数据定位并减少通过网络的数据传输。

Overview

Management and Synchronization

在WorkerSP中，主节点的图调度器只负责将工作流图划分为工人节点的子图，同时确保工人在执行这些子图时有足够的资源分配。任务分配和状态管理功能则不再由主节点完成。每个worker引擎将被分配到子图中，以执行本地函数的触发和调用。

Structure organization in workers

一个worker里面用workflow结构来保存信息，一个InvocationID对应以下两个结构

State。包括函数的执行状态和predecessor
FunctionInfo。函数的metadata

State synchronization between workers

每个worker通过State和FunctionInfo结构来处理其本地引擎中的函数的同步。当一个函数的所有前置条件都被标记为已执行时，本地引擎会触发一个本地调用，并同步其本地子图中的更新状态。

如果一个函数有跨worker的依赖性，本地引擎通过TCP连接将执行的状态传递给远程工作者引擎。 TCP通信的协议只负责更新函数状态，不包括在主站和工作站之间分配函数任务。

以图6为例，说明WorkerSP的调用同步情况。每个工作节点的引擎都在本地子图中维护函数和它们的前辈的执行状态。一旦函数𝐹𝑛𝐴被调用，引擎会将执行状态更新到本地工作流中。然后，它将检查𝐹𝑛𝐴的后续函数𝐹𝑛𝐵,𝐹𝑛𝐶，并通过节点间TCP（例如，分布在不同工作器上）或内部RPC连接（例如，位于同一工作器上）传递执行状态。最后，函数𝐹𝑛𝐵, 𝐹𝑛𝐶将在每个工作器引擎中获得其前任状态的更新，之后计算已执行的前任数量。如果一个函数的PredecessorsDone计数达到其目标PredecessorsCount，本地引擎将触发并在本地调用它。

Adaptive Storage with FaaStore

两个设计点

Dependence-driven hybrid storage。根据情况选择是in-memory还是remote
Easy-to-use low-level APIs

Design

FaaSFlow主要包括三个部分

workflow graph scheduler
per-worker workflow engine
FaaStore

Graph Scheduler

接收用户上传的yaml，生成DAG，然后partition

DAG Parser

支持以下的结构

Function。最简单的一个点
Sequence。顺序
Parallel。并行，且前面的Function需要全部完成
Switch。条件判断
Foreach。一个循环

Graph partitioning

在serverless中，控制平面（用户定义的graph）和数据平面（runtime data dependency）并不完全等价。以下就是可能造成不等价的原因

auto-scaling和container reusing。它们导致控制平面的一个点在数据平面中可能对应多个。这个和resource allocation有关
Foreach步骤中可能的multiple executors。foreach step是一个atomic step，而且在数据平面可能create multiple mapped instance。这个和in-memory quota有关

整个partition是多次进行的。在第一次运行的时候使用hash-based partition。当发生性能下降时再次partition，使用runtime metric来重新分配。

Function Grouping and Graph Scheduling

这是一个NP-hard问题。因此采用的算法是greedy grouping strategy based on the critical path。步骤如下

所有点都是一个group，worker随机分配
取关键路径上最长的边，并进行如下判断，看两个点是否能够merge
判断merge是否会超过worker的container容量
判断merge是否会超过memory constraint
判断merge是否包含了resource contention（这个是别的工作的，只是在这留一个接口）
使用bin-pack放置

Per-Worker Workflow Engine

主要用的技术就是前面提到的State Synchronization。一般workflow engine需要在每个invocation结束之后释放state结构，在所有instance结束后释放workflow结构。

Red-Black Deployment and management

当graph发生更新之后，平台使用版本控制来更新instance。只有新的instance会被触发，老的instance就执行完就被回收了。

auto-scaling和现有的方法一样，没有warm的就之后cold start。

Memory Reclaimation in FaaStore

为了避免过度使用in-memory的内存通信导致的内存不足问题，FaaStore sets a well-organized quota for data movement by memory reclamation from the containers

实际上使用的是用户over-provision的内存。