机器学习和图计算应用,都会使用到迭代计算,Flink 通过在迭代算子中定义 Step 函数来实现迭代算法,迭代算法包括 Iterate 和 DeltaIterate 两种类型。
Iterate
Iterate Operator 是一种简单的迭代形式:每一轮迭代,Step function 消费整个数据集(前一个迭代的结果或初始数据集),计算出下一轮迭代的输入(也称为 Next Partial Solution),满足迭代的终止条件后,会输出最终迭代结果。
Iterate分析上图的流程:
- 迭代输入:前一个迭代的结果或初始数据集。
- Step function:Step function 将在每次迭代中执行。由算子 map、reduce、join 等组成。
- Next Partial Solution:在每次迭代中,Step function 的输出将反馈到下一次迭代。
- 迭代结果:最后一次迭代的输出被写入 DataSink 或用作后续算子的输入。
有多个选项可指定迭代的终止条件:
- 最大迭代次数:没有任何其他条件,迭代将执行多次。
- 自定义聚合器收敛:迭代允许指定自定义聚合器和收敛条件,如SUM聚合已发出记录的数目(聚合器),如果该数目为零,则终止(收敛条件)。
伪代码表示:
IterationState state = getInitialState();
while (!terminationCriterion()) {
state = step(state);
}
setFinalState(state);
示例:递增数字
在以下示例中,迭代地递增一组数字:
Iterate Example
- 迭代输入:初始输入从数据源读取的五个记录(整数1到5)。
- Step function:单个 map 算子,将整数字段从
i
增加到i+1
。将应用于输入的每个记录。 - Next Partial Solution:Step function 的输出(map 算子的输出),反馈给下一次迭代。
- 迭代结果:经过十次迭代,最初的数字将被增加十,新的数据集为整数11到15。
// 1st 2nd 10th
map(1) -> 2 map(2) -> 3 ... map(10) -> 11
map(2) -> 3 map(3) -> 4 ... map(11) -> 12
map(3) -> 4 map(4) -> 5 ... map(12) -> 13
map(4) -> 5 map(5) -> 6 ... map(13) -> 14
map(5) -> 6 map(6) -> 7 ... map(14) -> 15
Delta Iterate
Delta Iterate 实现了增量迭代。有选择地修改其解中的数据元并演化解决方案,而不是完全重新计算它。
在适用的情况下,这会使算法更高效,因为解中的每个数据元不会都出现在每次迭代中。这样可以专注于解中的的 hot part,并保持 cold part 不受影响。
Delta Iterate分析上图的流程:
- 迭代输入:读取初始 Workset 和 Solution Set 作为第一次迭代的输入。
- Step function:在每次迭代中执行。
- Next Workset / Update Solution Set:Next Workset 驱动迭代计算,并将反馈到下一个迭代。此外,Solution Set 将被更新并隐式转发(不需要重建)。两个数据集都可以由 Step function 的不同 算子更新。
- 迭代结果:在最后一次迭代之后,Solution Set 被写入 DataSink 或用作后续算子的输入。
Delta Iterate 的默认达到指定的最大迭代次数或当生成的下一个工作集为空时,迭代将终止。还可以指定自定义聚合器和收敛标准。
伪代码表示:
IterationState workset = getInitialState();
IterationState solution = getInitialSolution();
while (!terminationCriterion()) {
(delta, workset) = step(workset, solution);
solution.update(delta)
}
setFinalState(solution);
示例:在图表中传播最小值
在以下示例中,每个顶点(Vertex)都有一个ID和一个颜色(Color)。每个顶点将其顶点ID传播到相邻顶点。目标是为子图中的每个定点分配最小ID。如果顶点接收的ID小于当前的ID,则它将变为接收到的ID的顶点的颜色。
Delta Iterate Example初始输入同时设置 Workset 和 Solution Set。在上图中,颜色显示了 Solution Set 的演变。在每次迭代中,最小ID的颜色在各自的子图中传播。同时,每次迭代的工作量(交换和比较顶点ID)都会减少,对应于 Workset 减小,在三次迭代后,Workset 的大小从所有七个顶点变为零,此时迭代终止。
Reference:
https://ci.apache.org/projects/flink/flink-docs-release-1.6/dev/batch/iterations.html
网友评论