超越批处理的世界：流计算（三）
内连接(Inner-Join)
另外一种时间不可知的应用场景就是内连接(也叫哈希连接， Hash-Join)。当连接两个无穷数据源的时候，如果你只想得到在两个数据源里都有的元素，那么这里的逻辑就跟时间无关了。在得到一个新的值后，只要简单地把它持久的缓存起来，再一直等到另外一个源里也送来这个值，然后输出即可。当然有可能这里会需要一些垃圾回收机制来把那些从来没出现的连接的元素给清理掉，这时候就跟时间有关了。但是对于那些不会出现不完全连接的场景，这个就没什么了。
当来自两个数据源中都出现了相同的观察值后，就进行连接操作。
如果问题转变成了外连接(Outer-Join)，这就会出现之前讨论的完整性的问题，即当你看到连接的一边，你怎么能知道另外一边是否会出现?事实是，你不知道!这种情况下，你就必须采用某种超时机制，而这就又涉及到了时间。这里的时间本质上就又是一种时间窗口分片，后面会仔细分析。
近似算法(Approximation algorithms)
数据进入后通过了一个复杂的近似算法的运算，得到差不多你想要的结果。
第二类方法是近似算法，比如近似Top-N、流K-means聚类等。他们都以无穷数据为输入，并计算出差不多你想要的结果。这些近似算法的好处是它们一般开销小，而且就是设计来处理无穷数据的。缺点是这类方法数量有限，且实现都比较复杂，更新也难。近似的特性又使得它们不能广泛应用。
值得注意的是，这些算法一般都有一些时间域的特性(例如，某种衰退机制)。同时也因为这些方法一般都是在数据到达后就处理，所以它们基本用的都是处理时间。对于有些可以提供证明的错误范围的算法，这一点很重要。因为如果算法能够利用数据到达的顺序来预测错误范围，那么即便是事件-时间漂移有变化，对于无穷数据，这些错误都可以忽略不计了。请记住这一点。
近似算法本身是很有趣的话题，但它们本质上也是时间不可知方法的一种(如果不考虑它们自身带有的一些时间域特性)。而且这些算法也很直白容易理解和使用，这里就不再详细地介绍了。
时间窗口分片
另外两个无穷数据处理的方法都是时间窗口分片法的变形。在继续前，我会花一些篇幅来讲清楚时间窗口分片的具体含义是什么。分片就只是对应于一个输入数据源(无穷或有穷)，按时间区间把数据分成有限个片，再来处理。图8里面给出了三种分片的方式。
每个例子都包括三个输入键对应的数据，并按不同的分片方式进行了划分，如窗口对齐的(对所有的键都适用)和窗口不对齐的(只对应于某些键的)。
1.固定窗口(Fixed windows)：固定时间窗口按固定长度的时间来分片。如图8所示，固定时间窗口典型地会对所有的数据集进行划分，也叫对齐的窗口。在某些情形下，可能会希望对不同的数据子集应用不同的相位偏移，从而能让分片的完整度更加的平均。这时就不再是对齐的窗口，而是非对齐的。
2.滑动窗口(Sliding windows)：滑动窗口是固定窗口的一个更一般化的形式。一般会定义两个量，即窗口大小(时间长短)和滑动时间。如果滑动时间比窗口要小，则窗口会重叠;如果相等，这就是固定窗口;如果滑动时间比窗口大，就产生了一种特殊的数据采样，也就是按时间只看数据集里的一部分子集的数据。类似于固定窗口，滑动窗口一般也是对齐的。出于性能考虑也会在某些情况下是非对齐的。需要注意的是，图8里为了能表明滑动的性质而没有把每个窗口对应到所有的键。实际情况里是都要对应到的。
3.会话单元(Sessions)：是动态窗口的一种。一个会话是在不活跃时间段之间的一连串事件。这个不活跃时间一般是设定的比超时的时间要长。会话单元一般用来做用户行为分析，即观察在一个会话单元里用户的一系列事件。会话单元的长度一般都没法提前确定，完全取决于实际数据的情况。会话单元也是非对齐窗口的一个经典案例，因为实际情况下，不同子集数据的会话单元长度几乎不可能一致地对齐。
上面讨论的处理时间和事件时间是我们最关心的两个概念2。在两种情况下，时间窗口分片都可以使用。所以下面我们会详细的来看看他们的区别。由于按处理时间做窗口分片是最常见的，我们就想讲它吧。
按处理时间做时间窗口分片
这种方式下，系统本质上是把进来的数据进行缓存，达到一定的处理时间窗口再对缓存的数据进行处理。例如，在一个5分钟的固定窗口里，系统会按自己的系统时间缓存5分钟内的数据，然后把这5分钟内的数据视为一片，交由流程的下一步做处理。
用处理时间做窗口分片有一下几个好的特性：
简单。实现起来非常简单明了，不用担心数据失序和重排序。只要把数据缓存后按时交给下游就好了。
判断完整性很容易。因为系统能很清楚地知道某窗口里的数据是否已经全部到到，所以数据的完整性很容易保证。这就意味着系统不用操心去处理那些“晚到的”数据了。
如果你关心的是事件被观察到后的信息，那么按处理时间做时间窗口分片就是你所需要的方法。很多监控应用场景都可以归到这一类。比如你想获得某大型网站的每秒访问量，再通过监控这个数量来判断网站是否有服务中断，这时候用处理时间做时间窗口分片就是绝佳的选择。
尽管有这些好处，这个方法也有一个非常大的缺陷，即如果要处理的数据包含事件时间，而时间窗口需要反映的是数据的事件时间，那么就需要数据严格地按照事件时间来到达。不幸的是，在现实中这种按事件时间排好序到达的数据几乎是没有的。
举一个简单的例子，手机里的App收集上传用户的使用数据用于后期分析。当手机离网一段时间后(比如无网络连接、飞行模式等)，这期间记录的数据就需要等到手机接入网络后才能上传。这意味着处理时间和事件时间就会出现从分钟到几周不等的偏移。这时候用处理时间来做时间窗口分片就没法对这样的数据做出有效的处理并产生有用的信息。
另外一个例子是有些分布式的数据源在系统正常情况下可以提供按事件时间排序好(甚至非常好)的数据。但是当系统的健康状况得不到保证的时候，就很难保证有序性了。比如某全球业务需要处理采集自多个大洲的数据。而洲际间的网络带宽一般会受限(不幸的是，这很常见)，这时就会出现突然间一部分数据会比通常情况下晚到。再用按处理时间做分片，就不再能有效地反映数据实际发生时的情景了。这时窗口内的数据就已经是新旧混合的数据了。
这两个例子里，我们真正想用的都是事件的发生时间，因为这样才能保证数据到达的有序性。这就需要按事件时间进行时间窗口分片。
按事件时间做时间窗口分片
当你需要的是把事件按照发生时的时间分进有限的块内，你所需要的就是按事件时间做时间窗口分片。这是时间窗口分片的黄金标准。很不幸，目前绝大多数系统都不支持这样的方法。尽管那些支持强一致的系统(比如Hadoop和Spark)经过一些修改都可以支持这种方法。
下图就给出了一个用一小时的固定窗口对无穷数据做按事件时间分片的演示。
数据按照他们发生的时间收集。白色箭头指出把那些事件时间属于同一个分片的数据放到同一个窗口中去。
图里的白色箭头线对应于两个特别的数据。这两个数据先后达到处理管道的时间和他们的事件时间并不一致。如果是按照处理时间来分片处理，但实际我们关心的是事件发生时的信息，那么计算出的结果就会不正确了。如此，用事件时间分片来保证事件时间计算的正确性就很完美了。
这个方法来处理无穷数据的另外一个好处就是你可以使用动态大小窗口，比如会话单元，而不用出现前面用批处理引擎来处理会话时会出现的会话被分到两个窗口里(见图4)。
数据按照他们发生的时间以及活动性被分到了不同的会话单元里。白色箭头指出把那些事件时间属于同一个分片的数据放到同一个窗口中去并按事件时间排序。
当然，天下没有免费的午餐，按事件时间做时间窗口分片也不例外。由于窗口必须要比窗口的长度存在更长的时间(处理时间)，所以它有两个很大的缺点。
缓存：由于窗口的存在时间要长，所以就需要缓存更多的数据。比较好的是，现在持久化已经是整个数据处理系统资源里最便宜的部分(其他的是CPU、带宽和内存)。所以在一个设计良好的数据处理系统里，用强一致的持久化机制加上好的内存缓存机制后，这个问题可能并没想像的那么严重。另外不少的聚合运算(比如求和、算平均)都不需要把所有的数据都缓存起来，只要把很小的中间结果缓存下来，并逐步累积就可以了。
完整性：考虑到我们通常没有好的方法来确定已经收集到了一个窗口片里的所有数据，我们怎么知道什么时候可以把窗口里的数据交给下游去处理?事实是，我们确实不知道。对很多输入类型，系统可以给出一个相对合理准确的完整性估计，比如在MillWheel系统里使用的水印。但是对于绝对的准确要求极度高的场景(比如计费)，唯一的选择就是提供一个方法让引擎来决定什么时候交出数据，同时能让系统不断地修正结果。应对窗口内数据的完整性是一个非常有趣的题目，但最好是能在一个具体的例子里来讨论说明，以后我会再介绍。
