作者：Tyler Akidau, Alex Balikov etc. Google Inc.
原文：http://research.google.com/pubs/pub41378.html
译者：phylips@bmy 2013-10-1
译文：http://duanple.blog.163.com/blog/static/709717672013918101253853/
[说明：最近Google在VLDB上发表了两篇文章，其中一篇是F1，另外一篇就是此文。关于流处理，目前业界也已有如下多个系统：Storm，Samza，Summingbird，Spark Streaming，StreamBase。另外，highscalability.com上也有个关于这篇paper的推荐文章Paper: MillWheel: Fault-Tolerant Stream Processing At Internet Scale，Zeitgeist。]
摘要
MillWheel是一个在Google被广泛应用于构建低延迟数据处理应用的框架。用户只需要描述好关于计算的有向图，编写每个节点的应用程序代码。系统负责管理持久化状态和连续的记录流，同时将一切置于框架提供的容错性保证之下。
本文描述了MillWheel的编程模型及其实现。同时以一个在Google实际使用的产品(continuous anomaly detector)为例，来看一下MillWheel的应用。MillWheel的编程模型中提供了一个logical time的概念，这使得它很容易进行基于时间的聚合计算。在MillWheel的设计中始终将容错性和扩展性牢记于心。实际上，我们发现MillWheel这种综合了容错性和扩展性的独特优势，以及灵活的编程模型，使得它可以用来解决Google遇到的一大类问题。
1.导引
流处理系统在为用户提供内容帮助组织进行更快更好的决策方面具有重要价值，特别是因为它们可以提供低延迟的结果。用户希望可以得到关于他们周围世界的实时信息。同样地，商业人士更加对那些由实时情报源(像垃圾邮件过滤和入侵检测系统)提供的信息感兴趣。类似地，科学家必须从庞杂的原始数据中提炼出值得关注的结果。
应用于Google的流处理系统需要具有容错性，持久化状态和可扩展性。对于由数千台机器组成的分布式系统来说，任意时间都有可能有机器发生故障。基于模型的流处理系统，像异常检测器，除了会依赖于数周前的数据产生预测模型，同时在新数据到达也需要对模型进行调整。同时在对这些系统进行数量级的规模扩展时，系统的构建和运维成本不能随规模而线性增长。
像MapReduce[11]这样针对分布式系统的编程模型，它通过将底层实现细节隐藏到框架内部，使得用户可以方便快捷地创建自己的分布式应用。这种编程模型，通过让用户只需要关注自己的应用逻辑，使得他们只需了解自己系统的语义而不必成为分布式系统专家。特别是，用户可以直接将系统提供的框架级别的正确性和容错性保证作为一种基本原语，极大限定了bug和错误可能出现的范围{!对于用户来说，因为不再需要考虑分布式环境下的容错等复杂逻辑，而将它们看成是理所当然的，这样对于用户来说，出现bug和错误的范围就限定到了应用本身的逻辑上}。通过提供对各种通用编程语言的支持进一步提高了框架的适用性，因为这样用户就可以充分利用他们熟悉的编程语所提供的丰富工具和函数库，而不是局限在某一个DSL(domain-specific language)的范围内。
MillWheel就是这样的一种编程模型，不过是专门为流式和低延迟系统量身定制的。用户将他们的应用逻辑作为有向计算图里的节点，同时他们可以任意地、动态地定义图的拓扑结构。数据记录持续不断地沿着图的边进行传输。MillWheel在框架层面提供了容错性保证，任意节点和边可以在任意时刻发生故障而无需担心结果的正确性。作为容错性保证的一部分，系统会保证每条记录都会被传送给它的消费者。此外，MillWheel提供的用于记录处理的API保证对每条记录的处理是幂等的，这样从用户角度来看每条记录的发送就是exactly-once的(不重不漏)。MillWheel会对整个处理过程进行细粒度的checkpoint，这样在两次checkpoint之间就不再需要外部发送者长期地缓存pending数据。
现有的其他流处理系统并未提供这样的容错性，灵活性和可扩展性。Spark Streaming [34]和Sonora [32]在checkpointing方面做的非常出色，但是用户代码被限制在有限的Operator空间上。S4 [26]并未提供完完全容错的持久化状态，与此同时Storm[23]虽然提供了记录传输的exactly-once机制Trident[22]，但是要求事务顺序提交。另外那些通过对MapReduce和Hadoop[4]的批处理模型进行扩展来提供低延迟结果的尝试，会导致灵活性的丧失，就像在Spark Streaming中依赖于RDD的操作符描述(operator-specific)那样。Streaming SQL systems [1] [2] [5] [6][21] [24]为很多流处理问题提供了简单快捷的解决方案，但是对于那些具有直观的状态抽象和复杂的应用逻辑(比如矩阵乘法)的场景来说，采用命令式语言(imperative language)要比SQL这样的声明式语言(declarative language)表达起来更自然。
我们的主要贡献就是一个用于流处理系统的编程模型和MillWheel框架实现。
l 我们设计了一个允许用户不需要分布式经验就可以创建复杂流处理应用的编程模型
l 我们实现了一个高效的MillWheel框架，具备容错性，灵活性和可扩展性
本文剩余部分组织如下。第2节概述下当初驱动我们开发MillWheel的那个项目，看下它所暴露出来的需求。第3节提供了关于该系统的一个高层视图。第4节定义了MillWheel的一些基础抽象概念，同时在第5节讨论下MillWheel提供的API。第6节概述下MillWheel中容错性的实现，第7节讲述下整体实现。第8节提供了MillWheel性能方面的一些实验结果。第9节讨论下相关研究工作。
pdf完整版本下载：
http://pan.baidu.com/s/123Lv