ACM通信

研究突出了

具有及时数据流的增量迭代数据处理

作者:德里克·g·默里，弗兰克·麦克谢利，迈克尔·伊萨德，丽贝卡·艾萨克斯，保罗·巴勒姆，马丁·阿巴迪
ACM通信，2016年10月，第59卷第10期，第75-83页
10.1145 / 2983551
评论

描述了分布式计算的实时数据流模型及其在Naiad系统中的实现。该模型支持有状态迭代和增量计算。它同时支持低延迟流处理和高吞吐量批处理，使用了一种结合了异步和细粒度同步执行的新协调方法。我们描述了建立在Naiad上的两个编程框架:用于并行图处理的GraphLINQ和用于嵌套迭代和增量计算的差分数据流。我们展示了一个通用系统可以达到与专用系统相匹配，有时甚至超过专用系统的性能。

回到顶部

1.简介

本文介绍了及时的数据流迭代增量分布式计算模型，以及我们建立的用于演示它的Naiad系统。我们着手设计一个能够同时满足多种需求的系统:我们希望对大量数据并行工作负载进行高效的高吞吐量处理;支持低延迟(毫秒量级)查询和更新的有状态计算;还有一个简单而富有表现力的编程模型，具有迭代等一般特性。批量批量数据处理系统已经存在，^6，13，27流处理,^3.图算法,¹¹机器学习,¹⁵以及交互式AD hoc查询¹⁸；但他们都在各自的领域非常专业。我们的目标是找到一个通用的低级抽象和系统设计，可以重用所有这些计算工作负载。我们的动力来自两个方面，一个是研究问题，即是否可以找到这样一个低级模型，另一个是通过允许它们共享一个高度优化的核心代码库来降低特定领域分布式系统的工程成本的实际愿望。

要理解在同一个系统中支持低延迟、高吞吐量和迭代计算的困难，我们必须首先考虑调度和协调。在分布式系统中实现低延迟的一种简单方法是使用完全分散的调度，不需要全局协调:工作者急切地处理其他工作者发送的消息，并纯粹基于本地信息进行响应。我们可以用这种方式编写高度复杂的计算，例如使用触发器机制²¹但要在整个系统中实现一致性是一项挑战。相反，我们寻求一种高级编程模型，该模型使用语义理解良好的构造对数据集合进行抽象计算，包括循环;然而，很难将这样一个高级的程序描述转换成一大堆不协调的触发器。在另一个极端，实现具有强一致性的高吞吐量批处理系统的最简单方法是使用重量级中央协调，这在处理大量数据时具有可接受的成本，因为分布式计算的每个步骤可能需要几秒钟甚至几分钟。在这样的系统中，在计算步骤之间插入同步障碍可能是有意义的，⁶并将循环和其他控制流手动展开为显式的无循环计算图。^20.，27在只需要处理少量数据的情况下，这些机制的开销排除了低延迟响应。

及时数据流是一种计算模型，它将虚拟时间戳附加到结构化循环数据流图中的事件上。它的主要贡献是一个新的协调机制，允许低延迟的异步消息处理，同时有效地跟踪全局进度，并仅在需要强制一致性的地方进行同步。我们对Naiad的实现表明，一个及时的数据流系统可以实现与专业系统相匹配的性能，在许多情况下甚至超过专业系统。

最近高通量数据处理系统的一个主要主题^6，13，27当在不可靠的大型计算机集群上运行时，它们对透明容错的支持。Naiad采用了较老的想法，只是定期检查其状态，在失败时将整个系统状态恢复到最近的检查点。虽然这不是最复杂的设计，但我们选择它的部分原因是它的开销较低。更快的通用处理允许在检查点之间的间隔中进行更多的计算，因此常常减少作业完成的总时间。然而，流系统通常被设计成高可用性的^3.；这种系统的用户会正确地认为定期检查点是不够的，并且(暂且不考虑流系统通常不支持迭代的事实)像MillWheel这样的系统^3.如果简单地去掉容错的复杂性和开销，就可以实现更高的吞吐量。根据及时数据流的理念，我们相信有一种方法可以在单一设计中同时适应面向惰性批处理和迫切的高可用性容错，并在单个系统中适当地在它们之间插入。我们开发了一个实时数据流容错的理论设计²我们正在实施它。

在本文的其余部分，我们首先介绍了及时数据流，并描述了它的分布式实现如何实现我们的目标(第2节)。然后我们讨论了一些我们在Naiad上构建的应用程序，包括图计算(第3节)和微分数据流(第4节)。最后我们讨论了经验教训和开放问题(第5节)。本文中的一些材料之前在SOSP 2013年发表的一篇论文中更详细地描述了Naiad。¹⁹

回到顶部

2.系统设计与实现

图1说明了一种促进及时数据流的应用程序，因为它混合了对大量数据的高吞吐量迭代处理和对分布式状态的细粒度、低延迟的读取和更新。更新不断到达左侧，反映了社交网络的活动。虚线矩形包围着一个迭代聚类算法，该算法增量地维护对话主题的视图，由最近活动所暗示的动态社区结构聚合。在顶部，传入的查询请求针对特定用户及其社区兴趣定制的主题推荐:这些查询与最新的可用集群连接，以提供高质量和最新的结果。在Naiad之前，没有一个现有的系统能够以可接受的性能实现所有这些功能。标准的解决方案可能是用批处理系统(如MapReduce)的语言编写聚类算法⁶或火花²⁷并每隔几个小时重新运行一次，将输出存储在像Bigtable这样的分布式数据存储中。⁵一个单独的程序可以针对像MillWheel这样的低延迟流媒体系统^3.并对最近的更新执行更简单的非迭代分类，将新鲜但近似的推荐保存到分布式存储的另一个表中。第三个程序将接受用户查询，对批处理数据表和新数据表执行查找，将它们组合起来并返回结果。虽然这种混合方法已经被广泛部署，但是在单个系统上编写和维护单个程序会更简单，而且推断其输出的一致性也会更容易。

在高性能系统中组合这些不同的需求是具有挑战性的，关键的第一步是设计合适的抽象来构造必要的计算。本节首先解释我们得到的计算模型、我们选择的抽象以及它们背后的推理。

2.1.数据流

我们的第一个选择是将每个程序表示为数据流图。数据流是分布式数据处理的常用方法^6，13，27因为它显式地封装了计算之间的边界:数据流图的节点表示子计算，有向边表示数据在它们之间通信的路径。因此，使用数据流表示程序的系统可以自动确定可以并行执行的子计算。它在调度节点时具有很大的灵活性，至少在原则上，它可以独立地放置、移动和重启节点，而不改变整个计算的语义。

我们的设计基于有状态数据流，其中每个节点都可以保持可变状态，而边携带潜在的无界消息流。尽管有状态性使容错变得复杂，但我们相信它对于低延迟计算是必不可少的。增量或迭代计算可能在内存中保存非常大的索引数据结构，因此应用程序必须能够快速查询和更新这些数据结构以响应数据流消息，而不需要在调用之间保存和恢复状态。我们选择要求状态为节点私有，以简化分布式放置和并行执行。采用有状态数据流的一个后果是，可以使用数据流图中的循环有效地实现循环(消息绕一个循环返回到存储状态的节点)。相反，无状态系统^20.，27通过在循环和其他控制流执行时动态展开，使用非循环数据流图实现迭代。

在确定了有状态数据流之后，我们尝试最小化执行机制的数量，以便使及时的数据流系统更容易推理和优化。例如，我们采用了这样一种约定:节点中的所有计算都发生在单线程事件处理程序中，运行时显式调用该处理程序。通过这种约定，所有调度决策都集中在一个公共运行时中，使CPU使用更可预测，并允许系统构建者积极优化性能和控制延迟。它还简化了单个节点的实现:因为系统保证所有事件处理程序将在单个线程中运行，应用程序编程人员可以忽略并发编程的复杂性。通过鼓励单线程节点实现，我们推动程序员通过向数据流图中添加节点来获得并行性，并迫使系统构建者在调度节点计算时确保低开销。最终的系统应该能够交织不同节点的许多短期调用，并且非常适合执行延迟较低的细粒度更新。

数据并行是一种标准的方法，用于从输入和输出都是记录集合的操作符构造并行数据流图。数据并行运算符包括关键功能它将每个输入记录映射到一个键，这样具有不同键的记录就可以独立处理。正如DeWitt和Gray在20多年前展示的那样，通过将数据流图分割为多个节点，可以在数据流图中实现这样的运算符，每个节点负责键空间的一个不相交子集。⁷数据并行性很有吸引力，因为无论如何划分键空间，结果都是相同的，所以程序员只需要指定一个适当的键函数，系统就可以自动选择并行度。我们的框架库提供了标准的数据并行操作符，可以针对特定的应用程序进行定制。

2.2.及时的数据流

应用程序应该产生一致的结果，而一致性需要跨数据流节点和环的协调。我们将新模型称为“及时”数据流，因为它依赖于逻辑时间戳来提供这种协调。我们以支持具有良好性能的通用增量和迭代计算为目标，然后尝试在系统和应用程序编写器之间构建尽可能窄的编程接口，以满足我们的需求。我们对窄接口的渴望，就像我们对少机制的渴望一样，源于这样一种信念:它使系统更容易理解和设计。

异步消息。所有数据流模型都需要一些方法，以便一个节点沿出方向向另一个节点发送消息。在及时数据流系统中，每个节点都实现了一个OnRecv事件处理程序，当消息到达传入边缘时，系统可以调用该事件处理程序发送方法，节点可以从其任何事件处理程序调用该方法以在传出边缘上发送消息。消息是异步传递的，这使得系统在消息的传递方式上有很大的自由度。例如，它可以在一对节点之间缓冲消息，以最大化吞吐量。在另一个极端，系统可能通过“直通”传递消息OnRecv目标节点的处理程序运行在与源节点相同的调用堆栈上发送调用。直通完全消除了缓冲，从而提高了缓存性能，并支持诸如急于数据减少等优化²⁵这可以大大减少内存消耗。与同步数据流模型不同，¹⁴一个及时的数据流节点可能会调用发送响应传入消息的可变次数;因此，及时的数据流可以表示更多的程序，但它需要对单个节点进行动态调度。

及时数据流图中的每条消息都用逻辑时间戳标记。时间戳可以很简单，只需将一个整数附加到输入消息，以指示它到达的批处理。时间戳通过计算传播，例如，使应用程序程序员能够关联输入和输出数据。及时数据流还支持更复杂的多维时间戳，当数据流图包含周期时，可以使用该时间戳强制一致性，如下所述。

一致性。许多计算包括子程序，它们必须在生成输出之前累积所有的输入:考虑例如约简函数数或平均．与此同时，分布式应用程序通常将输入分割为小的异步消息，以减少延迟和缓冲，如上所述。为了使及时的数据流支持对无界输入流和迭代的增量计算，当一个节点(或数据并行节点集)看到一个一致的输入子集时，就会发出信号，从而产生结果。

一个通知是在特定逻辑时间戳处或之前的所有消息都已交付给特定节点时触发的事件。因为逻辑时间戳t标识一批记录，即节点的通知事件t指示该批处理中的所有记录都已交付给节点，并且可以为该逻辑时间戳生成结果。通过添加一个系统方法，我们在编程模型中公开了通知，NotifyAt (t），节点可以从事件处理程序调用该程序来请求通知。当系统能够保证不再有带有该时间戳的消息被传递到节点时，它将调用该节点的时间戳OnNotify (t）处理程序。这个保证是系统状态的全局属性，依赖于我们下面描述的分布式协议。节点通常使用OnNotify处理程序，以发送包含对批输入的计算结果的消息，并释放与该批处理相关的任何临时状态。

循环图的迭代。对迭代的支持使通知的传递变得复杂，因为在循环数据流图中，节点的输入可能依赖于它的输出。^一个因此，我们必须对及时数据流图的结构和可以附加到消息的时间戳进行适当的限制，以保证通知的有效性。一般模型在其他地方有详细描述^1，19但我们在奈阿德体系中采用的限制很容易用非正式的方式解释。除了与程序中的循环对应的结构嵌套循环外，Naiad数据流图是非循环的。与节点上的每个事件相关联的逻辑时间戳是一个或多个整数的元组，其中第一个整数表示与事件相关联的输入批次，后面的每个整数给出包含该节点的任何(嵌套的)循环的迭代计数。循环的每条路径都包含一个特殊的节点，该节点使时间戳的最内层坐标增加。最后，系统强制执行一条规则，即任何事件处理程序都不能发送时间早于它正在处理的事件的时间戳的消息。这些条件保证了有一个偏序系统中所有挂起的事件(未交付的消息和通知)，这支持有效的进度跟踪。

2.3.跟踪进展

及时和安全地交付通知的能力对于及时的数据流系统支持低延迟增量和迭代计算并获得一致结果的能力至关重要。例如，系统可以使用全局变量进度追踪建立保证不再有具有特定时间戳的消息被发送到节点。通过维护系统中待处理事件的聚合视图，进度跟踪器可以使用这些事件的部分顺序来确定(对于每个节点)任何后续事件的最早逻辑时间;这个最早的时间是单调的(也就是说，它永远不会倒退)。此外，下面有一个计算最早时间的有效方法，以便通知在到期时及时发送。

进度跟踪器是用于传递通知的“带外”机制。以前的系统已经实现了与沿数据流边缘使用“带内”控制消息的通知等效的功能:例如，要求节点在其输出边缘上转发一个特殊的“标点”消息，以表示批处理已完成。²⁴虽然带内标点符号似乎更符合我们保持事情简单的理念，但带外进度跟踪器设计的性能优势超过了额外复杂性的成本。标点符号对于数据并行数据流图是没有吸引力的，因为必须发送的消息的数量来指示批处理的结束与图中的边的数量成正比，而不是与节点的数量成正比(如带外设计)。当数据流可以是循环的时候，标点符号的简单性就不存在了，因为(i)一个节点在它的所有输入上都接收到标点符号之前不能产生标点符号，(ii)在循环图中至少有一个节点必须有一个依赖于其输出的输入。尽管标点符号支持有限的迭代计算，⁴它们不能推广到嵌套迭代或非单调运算符，因此不满足我们的要求。

在建立了带外协调的需求之后，我们仍然可以采用更简单的集中调度规程，例如在前一个迭代完成后触发节点处理每个迭代中的事件。增量更新迭代计算的一个微妙但强大的特性说服我们追求更高的性能。例如，考虑计算一个大型图的连接组件的问题:它可能需要200次迭代，并被划分到100台工作计算机上。现在，想象一下在从图中删除一条边后重新运行计算。如果第二次运行所做的工作与第一次运行所做的工作相同，除了，比如说，8个不同的循环迭代之外，这并不奇怪;如果这些迭代只在两个或三个工人上有差异。当增量地更新计算时，一个复杂的实现实际上可以只在那20次左右的时间和工作者执行工作，这是可能的，因为带外通知机制可以“跳过”无事可做的工作者和迭代;如果一个设计要求系统在每次迭代时都绕着循环步进每个节点，那么效率就会低得多。此示例还说明了事件处理程序在将来处理的事件的不同时间内发送消息和请求通知的情况;同样，我们可以选择一种限制这种通用性的更简单的设计，但是对于有用的应用程序来说，我们会损失大量的性能。 Space does not permit a full treatment of the node logic needed for such applications, but Section 4 sketches an explanation and provides further references.

2.4.实现

Naiad是我们的高性能分布式实时数据流实现。它是用c#编写的，可以在Windows、Linux和Mac OS X上运行。^bNaiad应用程序开发人员可以使用c#的所有特性，包括类、结构和lambda函数，从系统提供的泛型库构建一个及时的数据流图流对象。Naiad使用延迟执行:在运行时执行类似Max的方法流实际上向内部数据流图表示添加了一个节点。数据流计算只有在图完全构建并将数据呈现给输入节点时才开始。同一个程序可以在单台计算机上运行，使用一个或多个工作线程，或者通过简单的配置更改，作为与分布式计算中同一程序的其他实例通信的进程。工作人员使用共享内存在本地交换消息，并使用进程之间的持久TCP连接远程交换消息。每个数据流边传输一个特定c#类型的对象序列，泛型被广泛使用，因此操作符和连接它们的边可以是强类型的。

性能考虑。为了达到与更专业的系统竞争的性能，我们大量优化了Naiad的少数原始机制。特别是，我们发现有必要通过添加运行时代码生成来减少. net类型序列化的开销，以及通过在运行时和标准操作符中大量使用值类型来减少垃圾收集的开销。为了获得对小型增量更新和快速循环迭代的低延迟响应，我们需要确保进度跟踪是有效的:一旦节点无法通过给定的时间戳发送任何消息，通知将尽快传递给节点。

Naiad的进度跟踪协议本质上相当于用于终止检测或垃圾收集的分布式引用计数。²³每个事件都与一个图位置(边或节点)相关联:一个消息与发送它的边相关联，一个通知与请求和接收它的节点相关联。每个worker为其本地视图维护每对位置和时间戳的未完成事件数量的计数。每当一个事件被传递时，进度跟踪器会减少事件时间戳中相应位置的计数，并增加事件处理程序所发送的消息或请求的通知的计数，然后将此信息广播给所有其他工作者。

如前所述，这个协议的效率非常低，但我们做了一些优化，允许工作者累积更新并延迟发送更新，而不会导致全局计算停滞。举个简单的例子，如果一个worker在某个节点上有一个挂起的通知n和时间戳t，它可以安全地累积更新到以后的时间戳，直到该通知被交付。累积的更新经常会互相抵消，因此全球广播流量比天真的分析所认为的要少得多。

通知的传递定义了Naiad计算的关键路径，实现的协议可以在单个网络往返中跨集群分发通知。图2显示，使用该协议，在一个紧密循环中通知的简单微基准测试在64个服务器(通过千兆以太网连接)之间执行全局屏障，平均延迟仅为750秒。

分层编程抽象。我们希望确保Naiad对于初学者来说很容易使用，同时仍然足够灵活，允许有经验的程序员定制性能关键的节点实现。因此，我们采用分层模型来编写Naiad程序。最低层为完全定制的节点公开原始的及时数据流接口。更高层的结构是框架库，它将节点实现隐藏在具有相关功能的数据并行操作符集后面，这些操作符的输入和输出是c#对象的分布式集合。

我们模仿了DryadLINQ中的分布式查询库，²⁶增加了对图处理和增量计算的支持，我们将在下面几节中讨论这些。在库中，我们经常可以重用公共实现;例如，Naiad中的大多数LINQ运算符都建立在通用缓冲运算符的一元和二元形式之上OnRecv回调函数将记录添加到按时间戳索引的列表中OnNotify (t）方法，该方法将适当的转换应用于时间上的列表t。在许多情况下，我们能够专门化需要较少协调的操作符的实现:例如Concat立即从它的输入端转发记录，选择在不进行缓冲的情况下转换和输出数据不同的/在第一次看到记录时立即输出记录。

在Naiad上轻松实现新框架作为库，使我们能够试验各种分布式处理模式。在接下来的小节中，我们将详细介绍为图处理(第3节)和差分数据流(第4节)所构建的框架。

回到顶部

3.基于Naiad的图形处理

在许多数据处理系统上实现高性能的图算法是一个挑战。分布式图算法通常需要高效的通信，细粒度的协调，以及表达迭代算法的能力。这些挑战刺激了对专门的分布式图形处理系统的研究¹¹最近又尝试将数据流系统用于图形处理。¹²我们使用了各种图算法来评估及时数据流编程模型的表现力和我们的Naiad实现的性能。在本节中，为了避免混淆，我们使用术语“操作符”来表示数据流节点，而“图”、“节点”和“边”则指运行在Naiad上的程序正在分析的图的元素，除非另有规定。

为了理解我们如何在Naiad上实现图算法，考虑Gonzalez等人的集合-应用-散射(GAS)抽象是有指导意义的。¹¹在GAS抽象中，图算法被表示为在图中一个节点上的计算(i)从它的邻居收集值，(ii)对节点的状态应用更新，(iii)将新值分散到它的邻居。图3展示了我们如何将这个抽象表示为一个及时的数据流图。第一步是加载并划分图(1)的边。这一步可能使用简单的节点ID散列，或者更高级的分区方案，试图减少跨分区边界的边的数量。计算的核心是一组有状态的graph-join运算符(2)，它将图存储在一个高效的内存数据结构中，该结构针对随机节点查找进行了优化。图连接有效地计算它的两个输入的内部连接。src，dst)边关系，迭代更新(src，瓦尔)状态关系，并具有沿图的边缘散射更新状态值的效果。一组有状态的node-aggregate操作符(3)执行收集和应用步骤:它们存储图中每个节点的当前状态，收集来自邻居的传入更新(即图-join的输出)，将最终值应用到每个节点的状态，并将其作为输出产生。为了执行迭代计算，节点聚合运算符在第一次迭代(4)中取每个节点的初始值，在循环的后边缘(5)周围输入更新的状态值，并在算法达到一个固定点(6)后生成每个节点的最终值。

根据算法的性质，可以完全异步运行，也可以在每次迭代后同步运行。根据我们的经验，最有效的图算法实现，如PageRank或弱连接组件使用OnRecv异步地将传入值聚合到节点聚合运算符，以及OnNotify在每次迭代中同步地为节点生成新的聚合状态。因为在毫秒级的时间尺度上进行协调是可能的，所以使用我们在第4节简要描述的优先级技术，更复杂的图算法从将迭代划分为同步子迭代中受益。

由流入的数据驱动图3，我们在Naiad上实现了GraphLINQ框架。GraphLINQ通过集合上的高阶声明式操作符扩展了LINQ编程模型，例如选择,,GroupBy与GraphJoin, NodeAggregate,迭代中描述的专用数据流节点的实现符图3．GraphLINQ允许程序员使用标准的LINQ操作符来定义数据流计算，将输入数据加载、解析和划分为图，然后声明式地指定图算法。PageRank的一个简单实现只需9行GraphLINQ代码。

当在数据流系统上实现图算法时，一个常见的问题是，系统的通用性将比专门的系统带来性能损失。为了评估这一开销，我们在一个公开的Twitter追随者图(拥有4200万个节点和15亿条边)的抓取中测量了几个PageRank实现的性能。^c图4比较了两种Naiad实现的PageRank和PowerGraph发布的结果，¹¹这是在类似的硬件上测量的。^d我们在Naiad上提出了两种不同的PageRank实现。第一个(“Naiad Vertex”)使用一个简单的哈希函数在工作者之间划分Twitter图的节点，并在单个工作者上执行每个节点的所有处理;该实现的执行与最好的PowerGraph实现类似，在64台机器上每次迭代大约需要5.55秒。更高级的(“Naiad Edge”)实现使用基于边缘的划分，这种划分遵循PowerGraph带有顶点切割目标的边缘划分的精神，但基于空间填充曲线¹⁶；它比PowerGraph高出5倍，在49台机器上每次迭代只需1.03秒。图4绘制PageRank操作的单线程基线，使用2014年末的MacBook Pro, 16gb RAM:使用类似于高级的Naiad实现的数据布局，该实现每次迭代花费5.25 s。

回到顶部

4.微分数据流

差分数据流是我们开发的一个计算框架，用于有效地执行和增量更新迭代数据并行计算。该框架包括算法、数据结构和在实时数据流系统之上分层的数据流图结构。¹⁷

4.1.增量视图维护

差分数据流是一种推广增量视图维护，这是数据库系统的一个有用技术。增量视图维护可以作为数据并行节点的数据流图来实现。每个节点持续接收记录，并维护其累积的正确输出。因为节点实现是数据并行的，所以它们只需要使用与新到达的输入相同的键重新访问以前接收的输入记录。只查看这些记录，节点就可以确定必须如何更正输出(如果需要的话)以反映新的输入。通过只产生和通信更改的输出记录，节点通知下游节点它们必须重新考虑的相对较少的密钥。系统作为一个整体，只在发生实际更改时才执行工作。

增量视图维护是许多成功的流处理系统的基础^3.以及图形处理系统。⁸在流处理系统中，较短的每条记录更新时间意味着与批处理系统相比，系统可以以非常低的延迟执行。在增量图处理系统中，执行一轮消息交换的时间只取决于交换的消息数量，而不是节点或边的总数。尽管增量视图维护对流和图处理系统都有价值，但它不适合将两者结合起来。

4.2.从增量数据流到差异数据流

差分数据流通过消除时间完全有序的隐含假设，提供了结合增量和迭代更新的能力;相反，它根据部分有序的时间戳索引和累积记录。考虑一个图处理系统，它接受对节点和边集的增量更新，并正确地更新迭代计算的输出。由于迭代的进展和输入的变化，该系统必须处理多种类型的更新;差异数据流使用多维逻辑时间戳来区分这些类型的更新。当新记录到达时，实现构造所需的累积，以确定来自时间戳小于或等于新记录的所有记录的新输出。具体地说，考虑时间戳(epoch，迭代)的例子，用于接收更新输入的多个epoch的多次迭代计算。使用部分顺序(a、b) (x, y敌我识别)一个xby我们可以同时获得标准流和图形处理行为:时间戳(epoch, 0)收集所有更新(我, 0)我纪元和一个时间戳(0，圆)收集所有更新(0，j);j圆的。此外，时间戳(epoch, round)可以完全利用那些对它有用的记录:我,我),我时代和j圆的。以后的纪元或轮的记录可以被忽略。

图5显示了对于不同的实现策略，图处理计算每次迭代的执行时间:即，从24小时Twitter提及窗口派生的图上的弱连接组件(通过标签传播)。每个顶点代表一个用户，它重复地与它的邻居交换到目前为止看到的最小的用户ID(包括它自己的)。随着计算的进行，标签最终停止变化，并收敛到每个连接组件中的最小用户ID。实施策略如下:

• 无状态的批处理执行(未显示)在每次迭代中重复地重新计算所有标签，并在计算过程中进行固定数量的更新。这是可以在MapReduce之上实现的基线版本。
• 增量Dataflow使用增量视图维护来改进无状态版本。当计算开始收敛且未改变的标签既不重新通信也不重新计算时，工作量会减少。
• 优先差分数据流进一步改进了这一点，它从最小的值(那些最有可能保留在每个顶点上的值)开始，并在小标签完全传播后添加较大的值。早期引入小标签的好处是，许多顶点(最终接收小标签)将不再传播它们在早期迭代中拥有的更大的标签，这减少了非生产性通信和计算的数量。

的1 s变化级数表明，通过将窗口向前滑动一秒钟来更新边缘集所需的工作量(增量地更新连接结构)相比之下是微乎其微的。

由于差分数据流对集合的增量和迭代更改使用相同的表示，因此这些技术是可组合的。图7给出了查找有向图强连通分量(SCC)算法的实现。经典的SCC算法基于深度优先搜索，不容易并行化。但是，通过嵌套两个连接的组件查询(图6)在外面的定点，我们可以使用差分数据流(图7)．严格来说，连接的组件查询计算有向可达性，而SCC算法反复删除其端点到达不同组件的边，因此必须位于不同的SCC中。通过在每次迭代中反转边，以交替方向迭代地修整图，最终收敛到只包含端点在同一SCC中的那些边的图。

4.3.实现

差分数据流的实现包括几个标准节点，包括选择,GroupBy,加入，以及更高阶的定点迭代应用任意差分数据流表达式，直到收敛到一个固定点的节点。交换的记录的形式是(data、time、difference)，其中data是任意用户定义的类型，time是时间戳，而difference是(可能是负的)整数。

标准节点的实现有些微妙，但大多遵循差分数据流的数学定义¹⁷索引需要快速响应单个时间索引更新。的定点Node向所包含节点的时间戳引入一个新坐标，并根据上面描述的乘积顺序为时间戳扩展“小于或等于”和“最小上界”(如果所有的坐标都小于或等于另一个时间戳)。实现的一个重要方面是，只要实现了“小于或等于”和“最小上限”方法，所有差分数据流节点就其时间戳类型而言都是泛型的，这意味着它们可以放置在任意嵌套的定点循环中。当计算表达式的不动点时，表达式的数据流子图将按照正常方式构造，但通过一个将最内坐标提高1的节点，从子图的输出返回到它的输入有一个额外的连接(非正式地说，这将提高迭代计数)。

回到顶部

5.经验教训和开放的问题

及时数据流表明，将异步消息传递与分布式协调相结合，可以从复杂的循环数据流程序中生成一致的结果。Naiad进一步证明，我们可以构建一个将通用数据流系统的灵活性与专门系统的性能相结合的系统。

我们最初的Naiad实现使用c#作为实现语言。c#对泛型类型和一级函数的支持使得构建像LINQ这样的可重用数据并行操作符库变得简单。正在运行的c#程序可以访问它的类型化中间语言表示，这一事实意味着可以使用反射自动生成高效的序列化代码。在编写分布式应用程序时，不应低估自动序列化的优势，因为它允许程序员使用原生语言机制(如类)来表示中间值，而不必为每个类编写和维护序列化器付出代价。

c#的一些生产力优势是以性能为代价的，我们必须努力将这种代价降到最低。. net运行时使用标记-清除垃圾收集器(GC)回收内存，这简化了用户程序，但对基于维护内存中大量状态构建高效系统提出了挑战。虽然我们能够使用c#值类型来减少堆上指针的数量，从而减少GC所需的工作量，但不可能完全消除GC相关的暂停。自从建立了最初的Naiad版本以来，我们研究了减少垃圾收集影响的替代设计:Broom项目显示，使用基于区域的内存分配，Naiad程序的吞吐量有了令人鼓舞的改进，⁹并且在Rust语言中重新实现了及时的数据流，从而完全消除了垃圾收集器。^e

许多分布式数据流系统利用确定性执行来提供自动容错，^{13，20.，27}但奈阿德拥抱非决定论和异步，以更快地产生结果。此外，Naiad顶点可以保持任意状态，这使得生成生成顶点检查点的代码变得非常重要。正如在介绍中所解释的，我们目前的容错实现基于从全局检查点恢复，这需要每个有状态顶点中的代码来生成和使用其状态的检查点。全局检查点在周期和迭代执行时间的分布中引入了大量的倾斜，并迫使未失败的流程在发生故障时回滚。我们开发了一个模型，允许不同的顶点实现不同的检查点策略，²他们正在研究该模型的一个Naiad实现，这暴露了一系列的性能权衡，在许多情况下允许高吞吐量、低延迟和容错执行。

最后，我们注意到，虽然Naiad支持在同一个程序中组合许多不同的计算模型，但它缺少一种高级编程语言，如SQLand，一种为特定任务选择最合适模型的优化器。其他作者将程序分析和查询优化技术应用到Naiad。苏萨等。²²通过分析用户定义的函数并生成新的运算符，实现了对Naiad内置运算符的加速。高格等。¹⁰Musketeer取得了令人鼓舞的结果，它将用高级语言编写的迭代程序转换为使用包括Naiad在内的各种系统的代码。尽管如此，我们相信还有更强大的编译器，可以针对Naiad的不同库，包括差分数据流，并生成优化的顶点代码。

回到顶部

致谢

从2011年到2014年9月，我们在微软研究硅谷实验室(Microsoft Research Silicon Valley Lab)研究Naiad。我们感谢Dave Andersen、Amer Diwan和Matt Dwyer提出的改进本文的建议。我们感谢我们所有的前同事，他们评论了以前的版本的工作，特别是罗伊莱文和迈克施罗德，他们创造了一个独特的环境，鼓励和培养这种研究。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.

---

没有发现记录