大数据流处理弹性伸缩论文阅读笔记

[1] Multi-Level Elasticity for Data Stream Processing. IEEE Transactions on Parallel and Distributed Systems(TPDS).2019.A

研究内容

更改不同的执行容器(虚拟机、进程、线程)的数量来影响容器的性能。基本的想法是不同的执行容器会有不同的性能，但是也会带来不同的开销。作者的想法是自动提供最少的资源来满足应用所需的性能。在作者的方法中，使用低级别的容器组合来充分利用高级别容器的资源。

技术路线

多层次扩展的主要思路是，检查当前节点是否达到阈值，如果达到了就扩展节点，如果没达到就考虑增加一个进程。主要是在进行进程与虚拟机之间的调度。

文章中的应用程序主要考虑处理大量小信息的流处理程序(比如，推特消息，传感器日志)。文章提出了使用环境是非多租户环境，并且节点是应用专用(这个应该就是为了避免CPU等信息受干扰的问题)。算子实例之间平均分配数据流(不考虑数据倾斜)。

作者提出的方法依次执行以下步骤，（1）评估不同层次的执行容器的性能（2）为给定的负载提供适当的配置（3）构造具体应用的弹性控制器。

为了决定提供什么样的执行容器，需要知道不同级别的执行容器的并行度如何影响性能，作者获得这个信息的方式是通过平台提供，或进行基准测试。在考虑瓶颈算子的时候，是从离源算子近的地方开始考虑，避免上游影响下游。

什么时候决定扩展

作者在考虑是否进行扩展时，是按照算子实例逐个考虑，通过比较实例的$Health$值是否低于$minHealth$来判断实例是否需要扩展。

如何进行扩展

首先找到具有最小资源负载的节点(也就是当前空闲资源最多的节点)。当具有最多资源的节点的CPU与内存的占用超过设定的阈值，则会扩展起一个新的节点。如果节点还有资源，则会根据最优容器配置部署一个新的实例来提增加性能，这个最优信息是通过第一步中获得的。算法也会更新新的配置信息。

为了防止震荡发生，不是每次观察时都会进行缩放，而是对多个观察值进行线性回归来计算变化趋势。

结论

论文内容

摘要

文章研究了在低延迟和最小资源使用情况下，以分析大量数据为目标的流处理环境的被动弹性问题。文章提出了一种弹性管理策略，该策略可以太藕节应用程序组件的并行度，同时明确解决执行容器的层次结构(虚拟机、进程、线程)。展示了错误提供执行容器所导致的性能衰减，并提出了一种方法来使用最少的资源增加性能。文章描述了监控指标并展示了如何考虑执行环境的细节。通过使用真实应用程序进行实验验证了方法的有效性。

Introduction

在不同的计算系统领域，大数据都是一个挑战。随着互连设备的普及，它出现在物联网中，随着高性能计算系统规模的增长而增长，并伴随着互联网和社交网络活动的扩展。也是数据只能的主要主题。

处理大数据有两种主要技术：批处理和流处理。批处理是先将数据存储在巨大的数据库中，然后再进行处理，通常使用可扩展的编程模型，例如Google的MapReduce。 但是，随着数据规模的不断增长，数据传输和存储的成本变得令人望而却步。

作者关注于执行环境，并研究如何更改不同执行容器的数量来影响程序的性能。

Motivation for Multi-level Elasticity

System Model

主要介绍了流处理模型，并引出多级并行实例及弹性等。

Preformance mertrics

在流处理环境下，主要的性能评价是应用程序处理输入负载并及时产生结果的能力。文章主要考虑单个算子实例的处理活动。提出以下指标：

  • 元组接收数量：使用$received_T(c)$表示，量化实例$c$在时间$T$内所接收到的元组数量。
  • 元组处理数量：$processed_T(c)$，量化实例$c$在时间$T$内所处理的元组数量。
  • 处理活性：定义$health$指标，用来表示实例在时间$T$内所处理的元组与收到的元组的比例$health_T(c)=\frac{processed_T(c)}{received_T(c)}$。如果一个实例的$为$$health_T(c)=100%$，则表示实例能够及时处理所有输入，相反，如果$health_T(c)<100%$，则说明有些元组需要等待。如果这种情况持续，则这个实例则会变成应用的瓶颈。

应用程序能否满足具体的时间约束，依赖于多种因素，包括执行节点的可用资源、网络链接属性、输入负载的波动、应用程序的计算。文章中的应用程序主要考虑处理大量小信息的流处理程序(比如，推特消息，传感器日志)。这种应用程序的性能受限于计算资源的可用性，而不是网络。由于为应用程序配置的资源是分配给应用程序的执行容器的资源，因此在执行节点级别，它们受节点的内存和CPU容量的限制。因此监控如下资源：

  • $CPU occupation$. 使用$totalCPU_T(n)$表示在给定执行节点$n$上在时间$T$内的平均$CPU$使用率。
  • $Memory occupation$. 使用$totalMem_T(n)$表示在给定执行节点$n$上在时间$T$内的平均内存使用。

使用这两个指标可以跟踪节点的情况，如果这两个指标都没有饱和，则说明可以分配新的执行容器，否则，需要考虑扩展决定。

Preformances of Storm

  • 这张图在更改任务并行度，1-4-4表示1个worker(进程)，4个executors(线程)，4个task，说明每个线程执行一个Task，1-4-16表示每个线程执行4个任务，1-4-64表示每个线程执行16个任务。三条线有着类似的表现，这说明只增加Task并行度对任务的性能没有影响。在Storm拓扑的实际使用中，任务的数量实际上定义了这个任务所用的最大的执行器(线程)的数量。

  • image-20201111232803371

    线程级别的并行度变化能够改变性能，只要线程没有达到CPU核数限制。（实验环境是四核的机器）可以从b中看到，提升了线程数量后任务的出性能有提升，而当线程数量为8时，和4的表现基本一致。当CPU饱和时，health下降，当内存饱和时节点宕机。

  • image-20201111231828781

    过量提供进程资源反而导致了性能下降，而且更多的进程导致了性能不稳定，这是因为多个进程占用更多的内存，导致了到达了节点的极限。

A Strategty for multi-level elasticity

文章提出了使用环境是非多租户环境，并且节点是应用专用(这个应该就是为了避免CPU等信息受干扰的问题)。算子实例之间平均分配数据流(不考虑数据倾斜)。

作者提出的方法依次执行以下步骤，（1）评估不同层次的执行容器的性能（2）为给定的负载提供适当的配置（3）构造具体应用的弹性控制器。

第一步解决了系统模型中的执行容器的层次结构，为了决定提供什么样的执行容器，需要知道不同级别的执行容器的并行度如何影响性能，作者获得这个信息的方式是通过平台提供，或进行基准测试。

在第二步中，作者自动测试应用程序，以建立给定级别的输入负载和合适应用程序配置之间的映射关系。这个想法是为了变化输入负载然后发现指定算子所需的并行度级别(相关的执行容器)。

测试程序如算法1所示，使用线性负载为应用程序提供输入。作者在考虑是否进行扩展时，是按照算子实例逐个考虑，通过比较实例的$Health$值是否低于$minHealth$来判断实例是否需要扩展。

image-20201112110527246

扩展算法如算法2所示。首先找到具有最小资源负载的节点(也就是当前空闲资源最多的节点)。当具有最多资源的节点的CPU与内存的占用超过设定的阈值，则会扩展起一个新的节点。如果节点还有资源，则会根据最优容器配置部署一个新的实例来提增加性能，这个最优信息是通过第一步中获得的。算法也会更新新的配置信息。在进行向下扩展时，会尽快释放新分配的节点，主要目的是使用更少的节点。为了防止震荡发生，不是每次观察时都会进行缩放，而是对多个观察值进行线性回归来计算变化趋势。

image-20201112111630936

Implementation

Experimental Evaluation

Conclusion

[2] Joker: Elastic stream processing with organic adaptation. Journal of Parallel and Distributed Computing（JPDC）,2020/03/01.B

作者信息

毕尔肯大学，是土耳其最好的大学之一，世界排名501-600th

研究内容

通过弹性方法来解决流处理应用中数据流图子图并行度及算子并行度的弹性问题。

技术路线

结论

论文内容

摘要

作者提出一种在线并行度优化算法，以联合方式调整流水线和数据并行度。作者提出的并行执行模型将数据流图划分为多个区域。一个区域包含一系列可以兼容的算子，这些算子采用相同的数据并行度，并且作为一个整体进行流水线并行化。作者提出的运行时Joker可以持续监控运行时性能，并运行优化算法来解决瓶颈，并通过调整数据并行度和流水线并行度来扩展应用程序。

Introduction

随着世界万物互联的变化，现在越来越多的人关注可以接近实时计算连续数据的系统。电信，金融，制造系统，网络监控系统，医疗健康系统都是使用这种连续流数据的一个领域，这些领域都要求快速分析高速率的数据流，并提取其中的有用信息。

流处理是一种处理大规模连续流数据的计算范式。高吞吐量的处理要求流处理程序必须利用多个处理器或多个机器。流处理应用通常使用数据流图表示，其中算子是数据的处理者，通过FIFO语义的流将算子链接起来。但利用并行度对数据流进行扩展还有一些问题。

缺少直接的方式找到流处理应用合适的并行数量，并且流处理任务是在负载变动的情况下长时间运行。有效的方式是连续应用并行优化，并调整逻辑应用与计算资源的映射，来实现弹性。

作者扩展了流水线分裂模型，将数据流图划分为区域。一个区域包含最长的兼容序列，这些算子总体上适合数据并行，并且可以进一步实现子流水线并行。其次，并行优化算法检测流应用中的瓶颈，并通过联合调整流水线并行度和数据并行度来解决瓶颈。

Background

Solution overview

从源算子开始考虑形成区域，只要算子与当前区域兼容，就加入区域，当遇到不兼容的算子则终止当前区域的构建，而建立一个新的区域。作者自己定义了一个兼容性规则，主要思想是流应用程序应该减少数据交换。作者的方法是在早期形成较长的区域，并分配更多的处理资源，以便有更多的扩展机会。作者区域构造的规则如下：

  • 源算子有独立区域，称之为源区域$source\ regions$。源区域不在优化范围内
  • 区域中的算子有至多一个上游或至多一个下游，如果需要构造分支，则会中断当前的区域并开始一个新的区域。这表示每个区域只会有一个入口和一个出口。如果一个算子有多个下游，那下游算子会开始自己的区域。
  • 数据并行区域开始于无状态或已分区的状态算子，并且只会包含这两种算子。
  • 数据并行区域的第一个分区状态算子的$Key$为该区域的$Key$属性，随后加入的分区状态算子必须与当前区域兼容。(其实是在物理执行图上进行区域划分)

下图包含两个区域，其中黑点为区域分隔符，第一个区域是源算子区域，第二个是包含三个算子的区域，第二个区域中有两个流水线，第一个流水线包含$O_2$和$O_3$，第二个流水线只包含$O_4$。

image-20201112220629106

Organic adaptation

在开始运行时，为每个区域创建一个流水线和一个副本，然后运行一个三阶段的步骤来改变应用程序并行度。

  • 分析阶段：探查器收集适应阶段要使用的指标。收集三个类型的指标。

    • 收集流水线副本线程的CPU使用率，使用副本线程利用CPU的时间处理CPU时钟数来计算CPU利用率，线程的CPU时间是通过JMX接口获取的。
    • 定义算子成本$operator\ cost$，作为流水线实例线程在算子上花费的CPU时间的一部分。例如，一个流水线包含两个算子$O_1$和$O_2$，他们的成本估计是0.4和0.5，这表示算子$O_1$消耗了$40%$的流水线是来CPU时间。算子成本之和并不等于1，这是因为流水线包含了其他的CPU开销。将这一部分开销称之为流水线开销$pipeline\ overhead$，使用$1-\sum_{i=1}^{n}{cost_i}$。算子成本的计算会遍历流水线中的所有算子，在遍历过程中，采样线程会不断检查算子的指标值，如果在最后一秒内，采样线程访问了N次数据，而其中有C次发生了改变，则说明此算子的开销为$C/N$。
    • 吞吐量以一个时间段内处理的元组数量来衡量，我们使用区域吞吐量作为评估指标。作者尝试通过调整数据流图中每个区域的流水线程度和数据并行度来优化区域吞吐量。

    分析阶段会对采集的指标进行平均。

  • 自适应阶段：第二阶段开始识别瓶颈流水线，然后自适应算法将可能的并行度更改来解决存在的瓶颈。并尽可能最大程度的提高执行性能。

    区域中的流水线可能会利用流水线并行数量被进一步分割，自适应阶段的目标时为了解决瓶颈，并增加吞吐量来改变流水线程度和数据并行数量。如果一个区域包含了瓶颈流水线，则认为该区域是瓶颈区域。算法采用贪婪策略，通过并行度更改来改变流应用程序吞吐量。在每个阶段，会同时改变所有需要改变的瓶颈。

    在对瓶颈区域进行处理时，会开始寻找区域内的瓶颈流水线，会返回CPU使用率比配置阈值高的流水线。然后会尝试将流水线分割为两个更小的流水线，然后会对其中的副本数量进行更改。在对流水线进行分割时，会考虑使用算子成本，在分割时定义了一个新的指标，称之为分割效用$split\ utility$，这一指标用来预测当流水线在指定算子分割时，吞吐量的增加比率。例如，如果有一个3算子的流水线，其算子成本分别为0.2,0.1,0.4，流水线开销为0.3，如果我们在第二个算子处分割流水线，那第一个流水线运行第一个算子，第二个流水线运行第二和第三个算子，因为第二个流水线的总算子成本大于第一个流水线，我们推测第二条流水线将限制新的吞吐量值，那么在第二个算子处的分割效用$split\ utility=1/(0.3+max(0.2,0.1+0.4))$，同样的，如果在第三个算子处进行分割，分割效用为$split\ utility=1/(0.3+max(0.2+0.1,0.4))$在第三个算子处分割会导致更高的分割效用，所以我们选择使用第三个算子作为分割点。

  • 评估和控制阶段：在最后的阶段，来评估新的并行化配置，如果新配置提高了性能，则算法将强制应用更改，否则将返回第二阶段来寻找其他可能的更改。

流处理算子放置、分割论文阅读

可能需要阅读的一些论文

Placement strategies for Internet-scale data stream systems,

Optimal operator placement for distributed stream processing applications, 证明了最优算子放置问题是NP难问题。

“Optimal operator replication and placement for distributed stream processing systems,

很久之前的论文：

Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs

[1]Efficient Operator Placement for DistributedData Stream Processing Applications.TPDS.2019

研究内容

论文提出了几个启发式算法，能够解决在异构应用要求及计算资源情况下的算子放置问题。

论文内容

Introduction

过去也曾有一些启发式的方法，但是其中都是在集群环境下，没有考虑网络延迟。

image-20201116172209198

还有一些缺少灵活性，不能简单的优化新的放置目标。

image-20201116172322456

论文提出了几个启发式算法，能够解决在异构应用要求及计算资源情况下的算子放置问题。作者提出的启发式方法遵循三个规则：灵活性，计算资源高质量的放置，最优模型开发。

  • 对于灵活性，现有的一些方法主要都是为具体的QOS指标进行优化，而不能容易的定制或扩展使用新的指标。而作者想提出一种通用的框架能够容易调整不同指标的最优方法(响应时间、可用性、网络使用、组合参数)。

    image-20201116182511348

  • 对于服务质量，大多数现有的启发式方法通常确定尽力而为解决方案，这意味着它们不提供有关其计算近似最优解的能力的保证，定量或定性信息。比如很多的工作都是基于贪婪策略，通过本地的优化来改善，但这样可能会忽略一些全局优化配置。

    image-20201116182839537

  • 关于最优模型开发，作者在探索使用有效最优模型的可能性，为了确定高质量的放置方案。image-20201116183126412

相关工作

算子放置问题已经在不同的模型假设和优化目标下呗广泛讨论，【2】【17】对此作了综述。下面主要使用三个维度对本领域的相关工作进行回顾。

  1. 放置目标：最优化的目标

    现存的方案主要是优化一个多样性的目标，比如最小化应用响应时间，节点之间的流量，网络使用率，或者包含不同qos指标的通用开销函数。作者提出的优化目标也是多参数组合的多目标优化方法。

    image-20201116185521976

  2. 定义应用程序放置的方法论

    image-20201116185831900

    image-20201116190020805

  3. 放置解决方案管理的分布式计算基础架构的特征

方案也需要考虑在线重新部署的状态迁移的网络开销，以及再额外考虑副本数量。

Systemc model and problem statement

Data Stream process DSP数据流模型

DSP应用通过由数据流链接起来的算子网络组成。算子是执行特定操作的独立的处理单元(filtering aggregation merging等)。流是只无限的数据队列。由于难以抽象化抽象运算符的非功能属性，因此我们对其非功能属性进行了特征描述：

$C_i$表示执行所需要的资源数量，$R_i$表示算子处理每单元数据的平均延迟。在本文中，假设资源数量$C_i$足够保持算子$i$输入速率，

Resource Model资源模型

计算资源和网络资源也可以使用有标记的、全连接的、有向图来表示。图中的每个节点可以使用以下变量作为特征，$C_u$表示可用资源数量，$S_u$表示响应处理器上处理速度的提高，$A_u$表示可用性概率，比如节点$u$是否启动和运行。

算子放置问题

放置问题主要是确定流处理执行图与资源图之间的映射关系。

image-20201117133603759

The Placement Problem

正式提出算子放置问题，并提出启发式方法的概述，同时定义资源惩罚函数。

Optimal Placement Formulation

最优流处理放置问题(ODP)，可以被方便的定义为整数数问题，其中算子放置可以使用二元变量建模$x_{i,u}$，$i\in V_{dsp}$，$u \in V_{res}^{i}$。$x_{i,u}=1$表示算子$i$在节点$u$上，否则$x_{i,u}=0$。

image-20201117135021000

其中$F(x)$表示最合适的目标函数，$x$为放置向量。公式1表示节点资源限制，根据其可用资源对放置在节点$u$上的资源进行限制。公式（2）保证了每个算子$i$被放置在1个且仅1个节点$u$上。目标函数$F(x)$定义了放置策略目标。在本文中，作者考虑了应用响应时间$R(x)$，应用可用性$A(x)$，网络使用率$Z(x)$。这就产生了多目标优化问题，但是可以使用简单的加法加权技术转换为单目标优化问题。因此，我们定义了$F(x)$作为加权和的应用的标准化服务质量属性：
$$
F(x)=w_r \frac{R(x)-R_{min}}{R_{max}-R_{min}}+w_a \frac{logA_{max}-logA(x)}{logA_{max}-logA_{min}}+w_z \frac{Z(x)-Z_{min}}{Z_{max}-Z_{min}}
$$

其中$w_r$，$w_a$，$w_z \geq 0$，$w_r+w_a+w_z=1$，是服务质量$QoS$参数的权重。$R_{max}(R_{min}), A_{max}(A_{min}), Z_{max}(Z_{min})$分别表示期望响应时间、可用性、网络使用率的最大（最小）值。这里使用对数表达式对可用性进行描述，是为了获得线性表达式。

目标函数会在$[0,1]$范围内，其中值0对应最佳指标，1对应最差指标。

Heuristics：Overview

作者主要提出了基于模型及不基于模型的启发式方法。都是为了最小化目标函数$F(x)$，为此，启发式方法使用了一个特殊的惩罚函数，其定义了资源之间的顺序关系。

基于模型的启发式方法尝试限制计算资源的备用资源集，层次化的最优资源方法表示按虚拟数据中心中的层次结构组织的计算体系结构。

无模型的启发式方法实现的著名的元启发式方法来解决最优放置问题。贪婪和首次适应算法是解决装箱问题最流行的方法。也广泛的用于解决算子放置问题【4】【20】。

Resource Penalty Function

启发式方法包含了不同阶段的选择，节点是否合适会指引放置的决定。为此，我们需要一个指标来比较不同的方案。

引入链路开销函数$\delta (u,v) \in [0,1]$，作为链路$link(u,v) \in E_{res}$的惩罚。同样的，与定义$QoS$属性的加权组合类似，链路惩罚函数$\delta (u,v)$如下：
$$
\delta (u,v) = w_r\delta _R(u,v)+w_a\delta_A(u,v)+w_z\delta_Z(u,v)
$$
其中$w_r$，$w_a$，$w_z \in [0,1]$，

image-20201117152931510

链路$link(u,v)$上的响应时间$\widetilde R(u,v)$依赖于网络延迟$d_{(u,v)}$以及参考算子的执行时间

image-20201117153457707

Model-Based Heuristics

Hierarchical ODP

分层最优算子放置(hierarchical ODP)表示以有限数量的实体(虚拟数据中心VDC)组织的基础架构。VDC可以将许多节点及其相应的网络链接抽象成为能力更强的计算节点。

Model-free Heuristics
Greedy First-fit

Experimental Results

Experimental Setup
Application Topologies and network size
Optimization Objectives
Heuristics Overall Performance

[2] B. Gedik, H. G. Özsema, Ö Öztürk. Pipelined fission for stream programs with dynamic selectivity and partitioned state. Journal of Parallel and Distributed Computing,2016/10/01/.B

研究内容

技术路线

论文内容

摘要

本文解决了流水线分割的问题，利用管道并行性和数据并行来并行化程序。将流水线分割问题表达为优化问题，使用一种启发式算法。

introduction

在本文中，主要研究流水线分割问题，自动寻找组合流水线的最优配置和数据并行度来优化应用吞吐量。流水线并行度是流处理应用自然而然的问题【39】。本文的目标是确定如何在流应用程序中在数据和流水线并行方面分配处理资源，以便最佳地优化吞吐量。由于数据并行被应用与拓扑中算子的自己，因此性能仍然受到无法进行数据并行的运算符的限制，正是这一点激发了流水线分割的重要性，即组合流水线与数据并行的需求。

本文主要专注于链式拓扑的流应用程序，将其中多个阶段组织为一系列，每个阶段消费前个阶段的数据，然后将数据输出到下一阶段。每一阶段可以是单个算子或组合的算子。

本文工作适用于具有以下特性的流处理系统：

  • 动态选择性：消费的输入数据数目或算子产生的输出数据项目未固定，并可能会更根据输入数据的内容而变化，则算子具有动态选择性。
  • 背压
  • 流分区

在解决流水线分割方面面临的挑战，首先通过DSPS所用的执行模型来正式定义有效的并行化配置，这涉及对线程和应用并行部分进行映射的定义。其次，需要对流水线分割的配置与吞吐量进行建模，以便比较不同配置方案之间的区别。最后，即便是小规模的算子、处理器核心、线程，组合起来也有多种方案，重要的是要快速找到可以提供接近最佳吞吐量的配置。

这一问题有两个强烈的动机，首先是对应用程序有快速的编辑-调试周期，第二是动态进行流水线分割的开销较低，即能够在运行时更新并行化配置。在本文中，重点是在合理的时间范围、高吞吐量的解决流水线分割的问题。

解决方案包含三个部分，首先，我们基于应用融合和算子分割定义有效的流水线分割配置，融合是一种用于最小化调度开销和以流水线方式执行流应用的一项技术【25，13】。使用分割，复制形成并行区域的流水线，来实现数据并行性。其次，我们对相关概念进行建模，比如算子兼容性(用于定义并行区域)、背压(定义吞吐量的关键因素)、系统开销（线程切换和副本开销），并使用推导出来的公式计算吞吐量。最后，我们提出一个启发式算法可以快速定位流水线分割配置，并提供近似最优的性能。算法依赖于三个主要想法：1.基于最长兼容队列规则形成区域，其中兼容式形成的区域具有使之适合整体数据并行的特性。2.使用贪婪瓶颈解决方法来将区域分割为流水线，该过程使用可变的基于利用率的上限作为停止条件，来执行迭代流水线操作。3.使用贪婪的方式通过增加区域副本数量解决剩下的瓶颈。

BackGround

image-20201117220238360

Problem Formulation

扩展函数

image-20201117222551835

区域和流水线

image-20201118095712355

算子性能模型相关论文

[1]An Experiment-Driven Performance Model of StreamProcessing Operators in Fog Computing Environments.ACM SAC.2020

法国数字科学与技术研究创新实验室

论文仅考虑无状态算子

环境

  • flink1.7.0
  • 使用docker，每个docker中放置一个TM，每个TM中有一个slot。(没有进行slotgroup设置)
  • 使用nc命令来进行网络延迟的仿真，仿真的数据来自Global ping statistics. https://wondernetwork.com/pings
  • 使用数据生成器生成数据
  • 使用斐波那契函数作为处理算子
  • 每次实验执行4次，然后舍弃第一次的数据，当做系统热身
  • 输入系统100_000个记录
  • 假设source、sink处理时间忽略不计

性能参数

文中主要关注吞吐量

  • 定义处理时间PT，为每个算子定义处理时间PT，从上一个算子输出到当前算子输出的时间间隔。包含了网络延迟。
  • 任务运行时间JRT，从第一个记录进入到flink，到最后一个记录输出。

性能模型

简单用例

image-20210118142727549

此时所有算子都运行在一个TM中，然后衡量处理全部输入所用的时间$\alpha$，这也表示了一个节点的全部处理能力。

如果增加算子副本，理论上会按比例减少时间

  • 初始简单性能模型如下：

$$
\Pi_n = \frac{\alpha}{n}
$$

image-20210118143244205

​ 由于实际情况并不是线性，所以提出并行开销参数$\beta$

  • 第二个版本的性能模型如下：
    $$
    \Pi_n = \frac{\alpha}{n^{\beta}}
    $$
    image-20210118144823615

    当$\Pi$是所选算子的处理全部数据所需时间时，$\alpha$表示单一实例的处理能力。（因为无论是$\Pi$还是$\alpha$表示的都是处理一定量数据所需的时间）。对$\alpha$以及$\beta$进行拟合，可以得到算子的性能预测模型。实验表明$\beta \in[0.8,0.9]$

    image-20210118150032046

考虑异构网络延迟

image-20210118150631438

提出了一个线性模型来表示网络延迟对两个TM之间的处理时间的影响
$$
\Pi_2=a \times ND+b
$$
$ND$表示两个TM之间的网络延迟，$\Pi_2$表示有两个副本的算子的处理时间。$a$和$b$是两个常数。

下图表示了两个TM之间不同延迟的影响

image-20210118151615736

下图表示了不同延迟以及不同数量的TM对处理时间的影响

image-20210118151640450

当每个节点之间的网络延迟都不同时，我们观察到主导因素是source与任意TM之间最大的延迟。这是因为整体的处理时间是由最慢的算子副本所决定的。

image-20210118152041838

因此提出的更新版本的性能模型：
$$
\Pi_n = \frac{\alpha}{n^{\beta}}+\gamma \times ND_{max}
$$
image-20210118152418370

其中$\gamma$通过实验表明$\gamma \in [50,150]$

多源情况

image-20210118153015222

使用不同网络延迟增加源算子数量没有更改通用模式，因此可以使用上述的模型，仅需要更新$ND_{max}$参数

image-20210118153147809

模型参数校准

以上模型需要推测$\alpha , \beta , \gamma$三个参数。

  • 如果进行了一次测量，在这种情况下，我们只能将单个模型参数拟合到数据中。因此我们提供了默认值$\beta=1$以及$\gamma=0$，只拟合$\alpha$参数。这样使得模型简化为简单模型$\Pi_n = \frac{\alpha}{n}$，该模型没有处理复杂的长江，但是可以提供良好的性能预测。
  • 如果可以进行两次测量，在这种情况下，我们可以拟合两个参数$\alpha$和$\beta$或$\alpha$和$\gamma$。剩下的那个参数使用默认值。在实验中发现，拟合$\alpha$以及$\gamma$会获得更好的结果，因此模型更改为$\Pi_n=\frac{\alpha}{n}+\gamma \times ND_{max}$
  • 如果可以进行三次或更多次测量，就可以使用完整模型。

其他信息

1. 流处理性能分析

image-20210118134629173

2.各种方法的调度

image-20210118134954888