前言
最近正在深入地研究与重度使用Flink，中途了解到它实际上就是Google Dataflow模型的一种implementation。我是个喜欢刨根问底的人，于是就阅读了Dataflow的原始论文与其他相关资料，顺便写篇东西来总结下。看官如果对Flink有了解的话，就会发现Flink的设计与Dataflow模型高度贴合。
Dataflow模型入门
Dataflow模型在2015年由一群来自Google的大佬提出，目前Google Cloud上也有对应的服务提供，名字就叫Cloud Dataflow，通过Apache Beam主打“简单的流式与批量大数据处理”（Simplified stream and batch data processing），官网在这里。
Dataflow模型的思想集中体现在论文《The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing》中。这个题目很长，但是值得推敲一番：
- 该模型处理的是大规模的、无界的、乱序的数据；
- 在处理这种数据的同时，需要兼顾正确性、时间延迟和资源消耗；
- 该模型是可实现的。
什么是“无界”数据
Google的大佬们认为，当我们提“流式”（stream）这个词时，实际上表达的意思就是在源源不断的连续数据上进行处理。反之，当我们提“批量”（batch）这个词时，就意味着在有限的一块或多块数据上进行处理，亦即“有界”。论文中倾向于用无界/有界来代替流式/批量，因为后者听起来像是在描述计算引擎的语义，而前者才是数据本身的特征。
对无界数据的处理必然要及时输出结果，否则就毫无意义。而输出的结果天然是有界数据，因此在Dataflow模型中，批量处理可以作为流式处理的一个子问题，目的是达到批流融合。这与传统Lambda架构（官网在这里）相比无疑是先进的，因为后者需要维护两套不同的组件分别用来做流式和批量处理，非常繁琐。
什么是“乱序”数据
我们都理解在数据的生成、采集、传输过程中，不可避免地会带来各种各样的延迟，这就意味着处理无界数据时，其顺序很有可能与业务逻辑的原始顺序不同。举个浅显的例子：某用户在7时55分浏览了某商品的详情页面，然后在7时56分加入购物车，57分下单购买，但日志队列中的顺序可能会变成“下单→加入购物车→浏览”。
在Lambda架构下的批量处理中，乱序数据造成问题的可能性往往很小。但是在Dataflow的批流融合构想下，必须正确地处理乱序数据才能保证整个大数据服务的正确性，因此非常重要。下面就来深入地看看Dataflow如何解决论文题目中的这些要点。
Dataflow思路概述
事件时间与处理时间
我们首先要分辨清楚Dataflow中最重要的一对基础概念，即事件时间（event time）和处理时间（processing time），说起来也很简单：
- 事件时间就是数据产生一瞬间的时间戳，比如调用某接口时的时间戳；
- 处理时间就是数据进入流式处理程序的时间戳。
下图示出事件时间和处理时间的关系。在理想情况下，数据总能及时地被处理，两者的关系应该是如虚线所示。但由于各种延迟的存在，实际情况更多地表现为红色粗箭头，两者之间会有一些差距（skew）。
将事件时间和处理时间区别对待，并且采用事件时间作为时间特征，是Dataflow的一大进步。
分解问题
Dataflow将上述无界数据的处理问题分解为4个子问题来考虑：
- 需要产出什么 [What results are being computed]；
- 计算什么时间的数据 [Where in event time they are being computed]；
- 在哪些时机物化/输出结果 [When in processing time they are materialized]；
- 后到的数据如何修正之前的结果 [How earlier results relate to later refinements]。
这样一来就清晰多了。为了解决上面的4个子问题，Dataflow提出了以下这些方案：
- 窗口模型（windowing model），支持基于乱序的事件时间的窗口操作，用于解决Where问题；
- 触发模型（triggering model），能够将数据结果与事件的时间特性绑定，解决When问题；
- 增量更新模型（incremental processing model），能够将后到的数据融合到窗口和触发模型中，解决How问题。
至于最基本的What问题，当然是用户自己要考虑的了。下面分别讨论这三个模型。
Dataflow三大模型
窗口模型
在大学计算机网络课程中，我们都学过窗口的概念，大家明白就好。
前面已经提到过，对无界数据的处理必然要及时输出结果，否则就毫无意义。那么要处理哪个时间范围的数据呢？通过窗口就可以将无界数据时域地划分为一个个的有限数据集，进而能在其上做分组、聚合、连接等比较高级的操作。下图示出乱序事件时间的一种窗口。
也就是说，Dataflow通过窗口模型将传统流处理中的(key, value)二元组改进为(key, value, event_time, window)四元组。
常见的开窗方式有三种，即固定（fixed/tumbling）窗口，滑动（sliding）窗口，会话（session）窗口，如下图所示。
固定窗口显然是最简单的，比如一个5分钟的固定窗口：[7:00, 7:05), [7:05, 7.10), [7:10, 7.15), ...。滑动窗口对我们来说也是老熟人，例如一个窗口时长1小时，滑动时长10分钟的滑动窗口就是以下的时间区间：[7:00, 8:00), [7:10, 8:10), [7:20, 8:20), ...。
会话窗口则不那么常见一些，它是Google在实践中总结出来的，通俗地说就是在一个key连续出现时才形成窗口，如果该key持续不出现超过一定时长，之后再出现就被划分到下一个窗口。这种方式比较灵活，并且容易想到它可以用于用户行为检测、异常检测等方面。
触发模型
如果我们不采用事件时间作为时间特征，而用处理时间的话，就没有必要考虑触发模型，因为窗口的边界与数据没关系。但是一旦用事件时间，由于数据会迟到，窗口的边界就会模糊，也就是无从知道窗口里的数据是否已经齐活了，触发结果的物化变成了一道难题。所以在这里又引入了一个重要的概念，就是水印（watermark）。
水印本质上是个时间戳，对一个无界数据源而言，水印T就表示已经接收到所有t <= T的数据，其他t > T的数据都将被视为迟到，接下来就可以进行输出。在讲解事件时间和处理时间时，图中的红色箭头就是实际的水印时间。
显然，如果没有延迟的数据，或者我们能对输入数据有完整的感知，那么水印就是理想的（ideal）。但无界数据源本身决定了我们不可能完整感知到输入数据的特征，所以水印的设定大多是启发式（heuristic）的，亦即根据历史指标尽量保证窗口内数据的完整性，但不能确保100%可靠，太快和太慢都不行。当然，也可以根据业务情况，采用更加简单暴力的方式（如周期性打水印、计数打水印）等，优势是比较灵活，不过就更加不可靠了。
增量更新模型
既然启发式水印不能确保100%可靠，那么就必须用迟到数据修正之前窗口的正确性，亦即增量更新，也叫做回填（backfill）。Dataflow原生定义了以下三种回填策略：
- 丢弃（discarding）：一旦窗口已经触发过了，就不再（在内存中）保留窗口的数据，所有超过水印的数据也都不算数；
- 累积（accumulating）：窗口触发过之后，保留窗口数据一段时间，超过水印的数据在该时间内仍然会进入窗口。保留的时间就是允许迟到时间（allowed lateness）。
- 累积与回撤（accumulating & retracting）：在累积的基础上，先撤回对上一次窗口操作的结果的修改，再输出新的结果。这是由于某些下游操作决定的，比如下游有累积计数操作，如果不撤回（即减去上一次的结果）的话，本次窗口的结果就不对了。
一个简单示例
有以下输入示例。
注意事件时间从12:00开始而处理时间从12:05开始。理想水印线如图中细线所示，实际水印则是粗线，说明有迟到数据。
下图是采用与Spark Streaming类似的微批次（micro-batch）手段进行处理的流程图，可见是根据processing time进行处理，与event time并没有关系。
下图则是与Flink类似的固定窗口+流式处理机制。
由这张图可以看出启发式水印的问题：数据9在水印触发时实际上还没有到，也就是水印太快了。而数据7要到8触发水印时才会输出，也就是水印太慢了。
The End
边看球边写的，三心二意并且水平有限，嘛就这样吧~
