首页OTHERS

# 摘要

无务器算革性地改变了应用程序的部署，消除了传统基础设施管理，并根据需求动态分配资源。一重要的使用案例是 I/O 密集型应用程序，如数据分析，这些应用程序广泛采用关键的 “洗牌” 操作。不式运行，因此仍然引入了无法预见的性能瓶颈，并绕过了未开发的优化机会。在本文中，我们开发 Mk 幸的是，洗牌操作由于大量针对远程存储的 PUT/GET 请求，特别是在高并行场景中，带来了严重的战，导致性能严重下降和存储成本增加。现有设计从多个方面优化数据传递性能，但它们以孤立的式运行，因此仍然引入了无法预见的性能瓶颈，并绕过了未开发的优化机会。在本文中，我们开发 MinFlow，这是一种针对 I/O 密集型无服务器分析任务的整体数据传递框架。MinFlow 首先快速生成大量可行的多级数据传递拓扑，同时减少 PUT/GET 操作。然后，它利用交错分区策略将拓扑有向无环图（DAG）划分为小规模的二部子图，以优化功能调度，进一步减少传输到远程存储的数据量超过一半。此外，MinFlow 还开发了一个精确模型，以确定最佳配置，从而在实际功能部署中最小化数据传递时间。我们实现了 MinFlow 的原型，大规模实验表明，MinFlow 在作业完成时间和存储成本上显著优于最先进的系统 FaaSFlow 和 Lambada。

# 现有方法

{13155747-BB5D-44B5-8B0F-718D5DD65FBD}.png

  • (a) 通过私有存储进行洗牌。 作为一个被众多用户和应用共享的公共云存储服务，S3 天生对每个单个用户分配有限的请求速率，以确保公平并避免租户之间的干扰。消除这一限制的简单方法是用自维护的私有存储替代 S3，例如 ElastiCache 集群。这使得用户拥有存储服务的独占权，从而大大提高了洗牌速度。然而，失去了 S3 的共享经济和精细化计费模式往往导致成本显著增加。
  • (b) 通过工作节点内部内存进行洗牌。 绕过 S3 限流的另一种方法是回收并利用工人中过度配置的内存来加速洗牌 。更具体地说，位于同一工人中的函数之间传递的数据是通过其本地内存进行的。以图 2 (b) 中工人 W1 中的函数 F2 和 F3 为例。假设要从 Fi 传递到 Fj 的数据记为 <Fi, Fj>。为了将数据传递给 F3，F2 首先将 <F2, F3> 放入 W1 的本地内存中，然后 F3 紧接着获取 <F2, F3> 并完成传输。这种方法在性能和成本上表现良好，因为回收的过度配置本地内存不仅提供了更高的性能。带宽和较低的延迟，但也不会产生额外的开销。缺点是其适用性的限制，因为只有共置的功能可以采用这种方法 。
  • （c）多级洗牌。 借鉴高性能计算（HPC）的思想，通过 k 维网状网络实现处理器之间的全连接 ，Starling 和 Lambada 项目将涉及洗牌的函数投影到一个边长为 k√N 的 k 维网格上，其中 N 表示函数的数量，并将全对全的集体原语应用于函数的子集，每个维度进行一次，以实现函数之间的全对全洗牌。与直接数据传递相比，这种多级间接方式（ML-Shuffle）大大减少了请求的数量，因为每个请求加载的数据量更大，并且每个链接只需要一个 PUT 加一个 GET。更确切地说，k 级洗牌（kL-Shuffle）将请求数量从 2N² 减少到 2kN k√N。例如，在图 2 (c) 中，我们通过将 k 设置为 2 展示了 2L-Shuffle。如图所示，仅需 60 个请求，而直接连接函数时需 72 个请求（见图 2 (a)）。由于在洗牌过程中需要通过远程 S3 传输的请求较少，因此由于 S3 的限制带来的性能下降得以缓解，同时收费也降低了。

# MinFlow Design

# Topology Optimizer

# Progressively Converging ML-Shuffle

{93468E8A-080E-4011-A63C-BF06B08F7F87}.png
方框代表函数，上下元组分别表示函数的标识和接收数据的范围。

kL-Shuffle 网络由 k + 1 个功能层（记作 flevel）和 k 个通信层（记作 clevel）组成，图 5 (a) 显示了一个涉及四个 flevel 和三个 clevel 的 3L-Shuffle 网络。逐渐收敛的方式首先将第一个 flevel 中的功能分为相同大小（最初为 1）的组，并逐渐让它们在下一个 flevel 中汇聚成更大的组，同时保留每个组与其上游映射器之间的完全连接，直到最后一个 flevel 中的所有功能位于同一组中，从而最终实现全局的全到全连接。

函数个数：N
第 i 个 FL 有组数：gig_i

则gig_i 满足

g0=N,gL=1,gi=di×gi+1where di∈N+∖{1}.(1)g_0 = N, \quad g_L = 1, \quad g_i = d_i \times g_{i+1} \quad \text{where } d_i \in \mathbb{N}^+ \setminus \{1\}. \tag{1}

Fi,j 的接收函数设置为 R

R={Fi+1,k∣⌊ksi+1⌋=⌊jsi+1⌋∧⌊k%si+1di⌋=j%si},wheresi=⌊Ngi⌋,si+1=⌊Ngi+1⌋,di=⌊gigi+1⌋.(2)R = \{ F_{i+1,k} \mid \left\lfloor \frac{k}{s_{i+1}} \right\rfloor = \left\lfloor \frac{j}{s_{i+1}} \right\rfloor \land \left\lfloor \frac{k \% s_{i+1}}{d_i} \right\rfloor = j \% s_i \}, \tag{2} where s_i = \left\lfloor \frac{N}{g_i} \right\rfloor, \quad s_{i+1} = \left\lfloor \frac{N}{g_{i+1}} \right\rfloor, \quad d_i = \left\lfloor \frac{g_i}{g_{i+1}} \right\rfloor.

公式看着很绕我也没看懂，其实就是下一层组里的函数均分上一层的接受数据吧
很明显总边数只和 d 和 L 有关，为

N×∑i=0L−1diN \times \sum_{i=0}^{L-1} d_i

# Candidates for Optimal Topology

仅基于拓扑结构之间的比较选择一小部分候选者，然后将最终的最佳决策委托给后续模块。特别是，尽管直接找到拓扑结构的全序是困难的，但它们之间的比较可以总结为以下几种情况：

  1. 在相同的 L 下，边数最少的拓扑具有最短的完成时间和数据传输成本，因为它通过最少的 PUTs/GETs 来传输数据，这些数据能更快地被远程存储服务处理。
  2. 在不同的 L 下，比较可能会产生歧义，因为一方面，较大的 L 会减少边数，从而减少 PUTs/GETs 的数量；另一方面，它会传输中间数据 L 次，可能会受到函数网络带宽的限制。

case1: 假设 N 可以分解为 p 个质因子，这意味着可行的 L 位于 [1, p] 之间，候选选择可以转化为一系列优化问题，如下所示：

For L∈[1,p],{minimizeN×∑i=0L−1disubject to∏i=0L−1di=N, di∈N+∖{1}\text{For } L \in [1,p], \quad \begin{cases} \text{minimize} & N \times \sum_{i=0}^{L-1} d_i \\ \text{subject to} & \prod_{i=0}^{L-1} d_i = N, \, d_i \in \mathbb{N}^+ \setminus \{1\} \end{cases}

动态规划可解：

MinSum(i,j)={ij=1min⁡ni(n+MinSum(in,j−1))j>1(4)\text{MinSum}(i, j) = \begin{cases} i & j = 1 \\ \min_{n_i}\left(n + \text{MinSum}\left(\frac{i}{n}, j-1\right)\right) & j > 1 \end{cases} \tag{4}

# Function Scheduler

pre 做完了不想写了，反正也没人看，作者视频讲的很清楚
https://www.youtube.com/watch?v=1lk9ihW1LUk
b 站也有搬运：
https://www.bilibili.com/video/BV1km41167Tr/?vd_source=60be106da45a5ce3eb9dd43f3e41769c#reply245510138881