流式处理的一些概念 二：水印、触发器、积累模式（翻译）

继续上一篇的内容，研究下面的三个概念：

• 水印（Watermark）：水印是一种关于事件时间的输入完整性的概念。具有时间值X的水印声明：已经观察到所有事件时间小于X的输入数据。当观察无界数据源时，水印充当进度度量。

• 触发器（Trigger）：触发器是一种机制，用于声明窗口的输出何时应该具体化（materialized），相对于某些外部信号。触发器在选择何时输出时提供了灵活性。它们还能够随着窗口的进展多次观察窗口的输出。这使得能够随时间推移细化结果，允许在数据到达时提供推测性结果，以及处理随着时间推移的上游数据随时间变化或相对于水印延迟到达的数据（例如，在移动场景，在默认离线状态，记录各种动作及其事件时间，然后在恢复连接时，继续上传这些事件进行处理）

• 累积（Accumulation）：累积模式指定在同一窗口中观察到的多个结果之间的关系，这些结果可能完全脱节（随着时间推移，代表独立的增量，或者它们之间可能存在重叠）。不同的累积模式具有不同的语义和与之相关联的成本，从而发现跨各种用例的适用性。

原文中首先回顾上一篇的几个概念，结合一些事例（Dataflow Java SDK 的伪代码）帮助理解他们。下面正式讲解本章节内容：

水印（watermarks）

水印是事件时间域中输入完整性的时间概念。换句话说，它们是系统对于事件流中正在处理的记录的事件时间的进度测量和完整性判断。回想一下之前提到的事件时间和处理时间之间的偏差，对于大多数真实世界的分布式数据处理系统，它是一个不断变化的时间函数。

代表现实的红线本质上是水印，它捕获了随着处理时间推进的事件时间完整性的进展。从概念上讲，可以将水印看作一个函数 F(P)->E，接受处理时间的一个点，并返回事件时间的一个点（更准确地说，函数的输入实际上是正在观察水印的流水线中点上游的所有东西的当前状态：输入源、缓冲数据、正在处理的数据等；但在概念上，将其看作从处理时间到事件时间的映射更简单）。事件时间点E是系统认为已经观察到事件时间小于E的所有输入的点。换句话说，这是一个断言，没有更多的事件时间少于E的数据将再次出现。水印有两种类型：

• 完美水印（perfect watermarks）：在我们对所有输入数据都具有完美认知的情况下，可以构造一个完美水印；在这种情况下，不存在延迟数据；所有数据都是早期的或准时的。

• 启发式水印（heuristic watermarks）：对于许多分布式输入源，完全了解输入数据是不切实际的，在这种情况下，下一个最佳选择是提供启发式水印。启发式水印使用关于输入的任何可用信息（分区、分区内的排序、文件的增长速度等）来提供尽可能准确的进度估计。在许多情况下，这些水印在预测中可图是非常精确的。即使如此，使用启发式水印意味着它有时可能是错误的，这将导致延迟的数据。我们将在下面的触发器部分了解如何处理延迟数据。

现在，为了更好地理解水印所起的作用以及它们的一些缺点，让我们看一下流引擎的两个示例，其中流引擎仅使用水印来确定何时实现输出。左边的示例使用完美的水印，右边的示例使用启发式水印。

在这两种情况下，当水印通过窗口的末端时，窗口实现输出。这两种算法的主要区别在于，在右侧的水印计算中使用的启发式算法没有考虑9的值，这极大地改变了水印的形状。这个例子突出了水印的两个缺点：

• 太慢：当任何类型的水印由于已知的未处理数据（例如，由于网络带宽限制而缓慢增长的输入日志）而被正确地延迟时，如果水印是唯一的依赖刺激，则直接转换为输出的延迟。

  这在左图中最明显，其中延迟到达9阻止了所有后续窗口的水印，即使这些窗口的输入数据更早的时候就完成了。这在第二个窗口 [12:02，12:04) 中尤其明显，其中从窗口中的第一个值出现到看到任何窗口的结果需要将近7分钟。这个例子中的启发式水印没有那么糟糕（5分钟后输出），但不要意味着启发式水印不会出现水印滞后。这只是在这个特定示例的表现。

  这里的要点如下：虽然水印提供了关于完整性的非常有用的概念，但是从延迟的角度来看，根据完整性生成输出通常并不理想。设想一个仪表板（dashboard），它包含有价值的度量，按小时或每天进行窗口化。你可能不希望等待整整一个小时或一天后来再来查看当前窗口的结果。这是使用批处理系统的痛苦点之一。相反，当输入逐渐进入并最终变得完整时，这些窗口的结果会随着时间变得更好。

• 太快：当启发式水印被错误提前时，在水印到达之前的事件时间的数据有可能延迟一段时间，可能创建延迟数据。这就是在右边的示例中发生的情况：水印在观察该窗口的所有输入数据之前就经过第一窗口的末端，导致错误的输出值为5而不是14（这是一个求和的场景）。这个缺点严格来说就是启发式水印的一个问题；启发式本质就意味着它们有时会出错。因此，如果关心正确性，仅仅依靠它们来确定何时实现输出是不够的。

仅仅依赖完整性概念的系统不能同时获得低延迟和正确性。解决这些问题是触发器发挥作用的地方。

触发器（Trigger）

触发器声明窗口的输出在处理时间域中应该什么时间发生（尽管触发器本身可以基于其他时间域发生的事情做出那些决定，比如事件时域中的水印）。窗口的每个特定输出称为窗口的窗格（pane of the window）。

信号触发的例子包括：

• 水印进展（事件时间进展），在上面两种水印对比图中，其中当水印通过窗口的末尾时，输出被具体化。另一个场景是在窗口的生存期超过某个有用水平界线时触发垃圾收集，稍后我们将看到一个示例。

• 处理时间进度，这对于提供定期、定期的更新是有用的，因为处理时间（不同于事件时间）总是或多或少地均匀且无延迟地进行。

• 元素数量，这对于在窗口中观察到有限数量的元素之后触发非常有用。

• 标识符（Punctuations），或其他依赖于数据的触发器，其中记录的某些记录或特征（例如，EOF元素或刷新事件）指示应该生成输出。

除了基于具体信号触发的简单触发器之外，还有允许创建更复杂的触发逻辑的复合触发器。复合触发器包括：

• 重复触发（Repetitions），这对于结合处理时间触发器来提供定期更新特别有用。

• 联合触发（Conjunctions），逻辑“与”，只有在所有子触发器都触发时才触发（例如，在水印经过窗口末尾之后 AND 观察到终止标识记录）。

• 选择触发（Disjunctions），逻辑“或”，任意子触发器触发之后都可以触发（例如，在水印经过窗口末尾之后 OR 观察到终止标识记录）。

• 顺序触发（Sequences），按预定义顺序触发子触发器进程。

我们可以使用触发器考虑解决水印太慢或太快的问题。在这两种情况下，我们本质上都希望为指定窗口提供某种规则的、物化的更新，在水印超出窗口末尾之前或之后（除了更新之外，我们将在通过窗口末尾的水印的阈值处接收）。所以，我们需要一些重复触发器。然后问题就变成了：我们要重复什么？

在速度太慢的情况下（提供过早的推测性结果），我们可以假定，对于任何给定的窗口，都会有稳定数量的传入数据。因为我们知道（通过定义什么处于窗口的早期阶段），观察到的窗口输入到目前为止是不完整的。因此，当处理时间提前的情况，进行周期性地触发（例如，每分钟一次）可能是明智的，因为触发器触发的数量并不取决于窗口实际观察到的数据量；最坏的情况是，我们只是得到了周期性触发器触发的稳定流。

在速度太快的情况下（由于启发式水印，为响应延迟数据而提供最新的结果），让我们假设水印是基于相对准确的启发式（通常是相当安全的假设）。在这种情况下，我们不希望经常看到延迟的数据，如果快速修改结果会很好。在观察元素计数1之后触发将给我们的结果提供快速更新（即，在任何时候我们看到延迟数据时立即更新），考虑到预期的延迟数据不频繁，不太可能压垮系统。

对于提前水印的数据的执行每分钟触发一次，对于延迟水印的数据执行每统计到一个立即触发，得到的结果如图：

这个版本与只使用水印的版本对比，有两个明显的改进：

• 对于第二个窗口 [12:02，12:04) 中的“水印太慢”的情况：现在每分钟提供一次定期的 early update。这种差异在完美的水印情况下最为明显(第一次输出时间的7分钟等待到减少到3.5分钟），但是在启发式情况下也明显改善了。

• 对于第一个窗口 [12:00，12:02) 中的“水印太快”的情况：当9的值出现较晚时，我们立即将它合并到一个新的、值为14的校正窗格中。

触发器有效地规范化了完美水印和启发式水印之间的输出模式，这两个版本的输出看起来非常相似。

此时剩余的最大的差异是窗口生命周期界限。在完美的水印情况下，一旦水印已经过了窗口的末尾，就再也看不到窗口的数据了，因此以在那个时候删除窗口的所有状态。在启发式水印情况下，仍然需要保持窗口的状态一段时间，以解决延迟数据。但是到目前为止，还没有任何好的方法来知道每个窗口需要保持多长时间的状态。

允许的延迟，垃圾回收（allowed lateness - garbage collection）

在长期存活、无序的流处理系统中，垃圾回收是很重要的一个部分。在启发式水印示例中，每个窗口的持久状态在逗留在整个生命周期中，这是很必要的，因为这允许迟到的数据到达时能够得到适当地处理。但实际上，在处理无界数据源时，为给定的窗口无限期地保持状态是不现实的，最终将用完磁盘空间。

因此，任何现实世界的无序处理系统，都需要提供某种方法来限制其处理的窗口的生命周期。一种方法是在系统内允许的延迟上设置一个界限（设置一个数据最大的延迟）。任何之后到达的数据都会被丢弃。一旦确定了单个数据的延迟时间，你也可以准确的知道窗口的状态必须保持多久：直到水印超过窗口末尾的延迟时间。除此之外，还给系统提供了在界限之外观测到数据之后立即删除的自由，这意味着系统不会浪费资源处理没有人关心的数据。

在之前的基础上，添加一分钟的延迟时间范围，pipeline 的执行类似于下图，允许延迟的影响：

• 粗白线表示处理时间中的当前位置，现在用来指示所有活动窗口的延迟时间范围（在事件时间）。

• 一旦水印通过了窗口的延迟范围（lateness horizon），该窗口关闭，该窗口的所有状态都被丢弃。虚线矩形，显示窗口关闭时所覆盖的时间范围（在两个时间域中），矩形上方向右延伸的虚线表示窗口的延迟时间范围（与水印对比）。

• 仅对于此描述图，第一个的延迟数据6，虽然数据晚到，但是在允许的延迟时间范围内，因此它被合并到一个更新的结果中，结果为11。而9号超出 lateness horizon 到达，所以它只是简单地丢弃。

1 2

关于 lateness horizons 的两个附注：

• 如果正在消费来自完美水印可用的数据源，那么就不需要处理延迟数据，并且允许的延迟时间为零秒是最佳的。

• 需要指定延迟时间范围的规则的一个值得注意的例外是，即使是使用启发式水印的情况，这是为有限数量的键值计算全局聚合值，（例如，计算所有时间访问站点的总次数，由Web浏览器品牌分组）。只要键的数量保持可控制的低，就不需要关系使用允许的延迟来限制窗口的生命周期。

累积（accumulation）

当触发器用于随着时间推移，为单个窗口生成多个窗格（panes of window）时，我们面临着一个问题：“结果的细化如何关联？”。实际上存在三种不同的累积模式：

• 丢弃（Discarding）：每次窗格被物化（materialized）时，任何存储状态都被丢弃。这意味着每个连续的窗格独立于之前的任何窗格。当下游消费者本身正在执行某种累积时，丢弃模式是有用的。

• 累积（Accumulating）：如之前的图示，每当窗格被实现时，任何存储状态都被保留，并且将来的输入被累积到现有状态中。这意味着每个连续窗格都建立在前一个窗格上。当稍后的结果可以简单地覆盖以前的结果时。

• 累积和收缩（Accumulating & retracting）：与累积模式类似，不同的是当生成一个新的窗格时，会为前面的窗格生成独立的收缩。收缩（与新的累积结果相结合）本质上是一种明确的表达：“之前的结果是X，是错误的，用Y代替它。”

参考之前图示中第二个窗口 [12:02，12:04) 的三个窗格，下表显示了三种累积模式中每个窗格的值是什么样子的：

	Discarding	Accumulating	Accumulating & Retracting
Pane 1: [7]	7	7	7
Pane 2: [3, 4]	7	14	14, -7
Pane 3: [8]	8	22	22, -14
Last Value Observed	8	22	22
Total Sum	22	51	22

• Discarding：每个窗格只包含特定窗格期间到达的值。因此，观察到的最终值不能完全捕获总和。如果对所有独立窗格进行求和，则会得到正确答案22。当下游消费者本身对窗格执行某种聚合时，丢弃模式是有用的。

• Accumulating：每个窗格都包含特定窗格期间到达的值，以及之前窗格的所有值。因此，正观察到的最终值捕获了22的总和。但是，如果对单个窗格本身进行汇总，则可以对窗格2和窗格1的输入分别进行重复计数，从而得到不正确的结果。

• Accumulating & Retracting：每个窗格包括新的累积模式值以及前一个窗格值的收缩。因此，所观察到的最后一个（非收缩）值以及所有物化窗格（包括收缩）的总和，都提供了正确答案。

在之前的基础上增加，丢弃模式的伪代码，pipeline 效果图如下，丢弃版本中的窗格没有重叠。因此，每个输出都独立于其他输出

而累计和收缩的模式如下，窗口是重叠的，retractions 用红色表示，该颜色与重叠的蓝色窗格结合在一起。

横向比较三种模式：

可以想象，按顺序呈现的模式（丢弃、累积、累积和收缩）在存储和计算成本方面依次更加昂贵。累积模式提供了沿着正确性、延迟和成本轴进行权衡的另一个维度。

原文：https://www.oreilly.com/ideas/the-world-beyond-batch-streaming-102