The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing

无界、无序、大规模的数据集在日常业务中越来越普遍，并且，这些数据的消费端也发展出更复杂的需求，例如事件时间排序和数据本身特征的窗口化等，以及对消费速度有了更高的要求。本文介绍了Google在数据流模型的核心设计原则

INTRODUCTION

现代的数据处理是一个非常复杂且发展蓬勃的领域，从MapReduce到SQL社区内大量关于流的工作如窗口、查询系统等，再到Spark Streaming、Storm等低延迟领域的发展。然而，现有的模型和系统在许多常见场景中仍然存在不足。批处理系统会遇到导入系统带来的延迟问题，而对于流处理系统，要么缺乏大规模的容错机制，要么缺乏提供exactly-once语义的能力影响数据准确性，又或者缺少窗口所必需的时间原语等等。Lambda架构可以满足很多需求，但由于必须和构建两套系统就会带来简单性的不足。论文提出的观点是，不再关注执行引擎决定系统语义的主流思维，而是通过考虑批处理，微批处理和流传输系统之间潜在的差异（即延迟和资源成本）来选择执行引擎。

本文提出了一个简单统一的模型概念：

允许计算event-time的有序结果，并根据数据本身的特征在无边界，无序的数据源上进行窗口聚合处理，在准确性，延迟和成本三者之间平衡；
拆分四个跨维度相关的管道实现：
- what：正在计算什么结果；
- where：事件发生时在哪里计算；
- when：在哪个处理时间内进行物化；
- how：前期结果如何与后续改进相关联；
将数据处理的逻辑概念与底层的物理实现分开，允许基于准确性，延迟和成本的考虑来选择批处理，微批处理或流引擎；

具体而言可以分为以下几个部分：

A windowing model：支持未对齐的event-time窗口；
A triggering model：将事件处理的运行时特征与输出次数坐绑定；
incremental processing model：将数据更新整合到前面的window model和trigger model中；
Scalable implementations：基于MillWheel流式引擎和Flume批处理引擎实现了Google cloud Dataflow的SDK；
core principles：模型设计的核心原则；

Unbounded/Bounded vs Streaming/Batch

Dataflow统一用Bounded/Unbounded Dataset来描述有限/无限数据集，而Streaming/Batch则用来特指某些执行引擎。

Window

Window即窗口化，是指将无限的数据集切分为有限的数据片以便进行聚合处理。对于无边的数据集，有些操作如aggregation，outer join，time-bounded都需要窗口。窗口一般是基于时间的，但也有些系统支持基于记录数的窗口，这可以理解为是逻辑时间，其中的元素按顺序依次增加逻辑时间戳。

窗口模型主要由三种主要分为以下三种：

Fixed Window：这是按固定窗口的大小定义的，比如说小时窗口或天窗口，通常是对齐窗口，每个窗口都包含了对应时间段范围内的所有数据，可以看到的是每个窗口之间没有重叠；
Sliding Window：这是根据窗口大小和滑动周期大小来定义的，比如说小时窗口，每一分钟滑动一次，通常情况滑动周期会比窗口更小，滑动窗口一般也是对齐的，如上图的五个滑动窗口实际上都包含了对三个键的处理；Fixed Window可以认为是窗口大小等于滑动周期大小的Sliding Window；
Session Window：这种类型的窗口会在数据的子集上捕捉一段时间内的活动，属于非对齐窗口，比如上图的窗口2只包含key 1，窗口3则只包含key2；

Time Domain

在流式处理中有两个关于时间的概念需要重点关注：

Event Time：事件本身实际发生的时间，系统时钟时间在事件发生时的记录；
Processing Time：事件在系统中被处理的时间；

在数据处理过程中，由于系统自身收到的影响如通信延迟，调度算法，处理时长，管道中间数据序列化等，会导致上述两个值之间存在一定的差值，诸如punctuations或watermarks之类的全局进度指标都提供了一种可视化这种差值的好方法，本文则是使用了一种类似MillWheel的水位标记，这是一个时间戳，用来表示小于这个时间戳的数据已经完全被系统处理了。理想情况下，这两个时间的差值应该为0，即事件一旦发生则马上做处理，如下图所示。但实际上，由于前面提到的原因，水位标记会偏离真实时间，这是非常正常的现象。

DATAFLOW MODEL

接下来将讨论Dataflow的正式模型。

Core Primitives

首先从经典的批处理模型开始，Dataflow把所有的数据都抽象成键值对，并提出了两个核心的数据转换操作：

ParDo：对每个输入元素都用一个用户自定义函数进行处理，生成零个活多个的输出元素，如下图所示：

GroupByKey：根据键值将元素重新分组，作为一个聚合操作，由于需要收集到所有需要的数据，需要结合窗口化一起使用；

Windowing

支持GroupByKey的系统通常会将其重新定义为GroupByKeyAndWindow，Dataflow在这里的主要贡献是支持未对齐窗口，其底层的优化则是通过下面两部来实现：

Set AssignWindows(T datum)：将元素复制给若干个窗口；
Set MergeWindows(Set windows)：窗口合并；

为了在本地支持事件时间的窗口，这里不再是传递简单的键值对，而是传递(key, value, eventtime, window)4元组。元素进入系统时会带有事件时间的时间戳，并且在最初会分配一个磨人的全局窗口。

Window Assignment

窗口赋值就是指将数据拷贝到对应的窗口。下图就是一个窗口大小为2分，滑动窗口间隔为1分钟的例子。

Window Merge

窗口合并是GroupByKeyAndWindow操作的一部分，具体来说这是一个由五部分组成的复合操作：DropTimestamps、GroupByKey、MergeWindows、GroupAlsoByWindow和ExpandToElements，其具体的含义可以参考下图：

Triggers & Incremental Processing

能够构建未对齐的事件时间窗口是一种进步，但仍面临两个问题：

为了与其他流式系统保持兼容，需要提供基于processing time和基于tuple的窗口；
由于事件发生时间是无序的，数据可能会慢一步到来，我们需要何时才能将窗口的结果数据发往下游；

论文这里主要讨论第二种情况，就是如何保证窗口数据的完整性。最原始的想法是使用某种全局事件时间戳，比如watermark来处理，这里可以立即为一个阈值，但watermark设计的过长过短对数据处理的准确性会有一定的影响，过短会导致水位标记到达后仍有记录到达，过长则可能会使得迟到的数据影响到整个数据处理管道的watermark。

Dataflow的处理方法是用一种叫Trigger的机制，这种机制是受信号激励从而触发GroupByKeyAndWindow执行并输出结果的机制，相对于窗口是决定哪些event time数据被分到一组进行聚合操作，Trigger更多是决定在什么处理时间窗口的结果会被输出。Trigger提供了三种不同的模式来控制不同计算结果之间是如何关联的：

Discarding：窗口数据的Trigger之后直接丢弃；
Accumulating：窗口的结果数据在Trigger之后持久化下来，用以支持后面的数据更新；
Accumulating & Retracting：在第二种基础上增加了回撤结果，即窗口再次Trigger时会将上次的结果做回撤，然后将新的结果作为正常数据下发。

CONCLUSIONS

无边界的数据时数据处理的未来，有边界的数据本身也是由无边界的对应部分所包含的，并且处理数据的消费者进化的越来越快，因此需要更强大的架构支持例如事件时间顺序和未对齐的窗口等。Dataflow模型把数据处理的逻辑划分了以下几个部分：计算什么、在哪个event time范围内计算、在什么处理时间点触发计算，如果用新的结果修正之前的处理结果，这使得整个数据处理逻辑变得更加透明清晰。