微分数据流:

本文为翻译文章

摘要:

现有的用于处理不断变化的输入数据的计算模型，除了在有限的特殊情况下，无法有效地支持迭代查询。这使得复杂的任务执行起来很困难, 例如在交互的时间尺度上对变化的数据进行社交图分析，这将极大地帮助那些分析服务行为（如Twitter）的人。

在本文中，我们引入了一种称为差分计算的新模型，该模型扩展了传统的增量计算以允许任意嵌套的迭代，并参考了一个公开的原型系统Naiad，该方法可以在一个声明式数据并行数据流语言中有效地实现差分计算.

最终的系统可以轻松地对以前难以处理的算法（例如，渐进更新的强连接的组件）进行编程，并将它们与数据转换操作集成在一起，从而从真实的数据流中获得实际相关的见解。

1. 介绍:

低成本存储的发展和联网设备的普及增加了超大的数据集的可用性，其中许多数据集正在不断更新。对这些变化的数据集执行复杂分析的能力是非常有必要的。 例如，在Twitter社交网络上发布的每条推文都可能提供有关该服务用户的社区结构的新信息，这些信息可利用于实时推荐服务或定向显示广告。尽管最近的大量研究都在增强“大数据”系统的增量计算功能[4、8、14、26]，添加循环结构[7、12、17、20、25]，甚至使用增量方法来有效地执行迭代计算 [13，19]，但到目前为止，还没有系统可以有效地支持对常规增量更新的复杂迭代计算。
例如，之前发布的系统都无法实时维护由Twitter引起的图中的强连接组件结构，这是对之前概述的应用程序的潜在输入。

本文介绍了一种新的差分计算方法，它对传统的增量计算模型进行了推广，尤其适用于迭代算法。微分计算的新颖性有两个方面: 首先，计算的状态根据部分有序的版本集而不是增量计算的标准的完全有序的版本序列而变化;其次，在任何给定版本上重新构建状态所需的更新集都保留在索引数据结构中，而增量系统通常会依次将每个更新合并到状态的“当前”版本中，然后放弃更新。具体而言，状态和对该状态的更新与多维逻辑时间戳相关联（今后的版本）。 这样可以实现更有效的重用：例如，如果版本（i，j）对应于输入的第i轮循环的第j次迭代，则其派生可以重用两个前导（i − 1，j ）和（i，j − 1），而不仅仅是系统最近处理的那个版本。

增量系统必须解决两个相关的问题：当输入更改时有效地更新计算，以及跟踪依赖关系，以便对状态的一部分的局部更新正确地反映到全局状态中。 微分计算解决了第一个问题，但是正如我们将看到的那样，它导致的更新规则要比增量系统的典型规则复杂得多。因此，我们还描述了当使用数据并行性和数据流来跟踪依赖项时如何实现差分计算，从而形成一个完整的系统模型，我们称之为微分数据流。 增量视图维护（IVM）算法^{[6、15、23]}解决了类似的问题，其目的是在更新视图以反映稍有不同的输入时复用先前输入所做的工作。 但是，现有的IVM算法不适用于交互式大规模计算，因为它们要么执行过多的工作，维护了太多的状态，要么限制表达性。

我们在一个名为Naiad的系统中实现了不同的数据流，并将其应用于多个真实数据集上的复杂图形处理查询。强调水中的仙女的特点,我们用它来计算一个24小时的强连通组件结构的Twitter的消息传递图(一个算法要求双重嵌套循环,而不是之前所知的方式来表述数据并行处理设置),并保持这种结构与次秒级延迟,面对Twitter的全量连续到达的tweet。而且，该算法的结果可以在相同的差异计算中传递给后续的数据流操作符，例如为每个组件维护最常见的散列标签，如附录中所述。

我们已经在名为Naiad的系统中实现了微分数据流，并将其应用于多个实际数据集上的复杂图形处理查询。 为了突出Naiad的特征，我们用它来计算一个24小时的强连通组件结构的Twitter的消息传递图（该算法需要双重嵌套循环，在数据并行设置中是未知的）, 并在面对Twitter全量连续到达的推文中保持这种结构与次秒级延迟。 此外，该算法的结果可以传递到同一微分计算中的后续数据流运算符，例如，为每个组件维护最常见的哈希标签，如附录中所述。

本文的贡献可以总结如下:

• 定义了一个新的计算模型: 微分计算，该模型通过允许状态根据版本的部分顺序变化来扩展增量计算，并维护单个更新的索引，从而允许它们针对不同版本以不同方式组合（第3部分）。

• 微分数据流的定义，它展示了如何在数据并行数据流环境中实际应用差分计算(第4部分)。

• 原型Naiad系统的实现草图，该系统实现了微分数据流，并带有示例结果，表明系统足够有效，可以在交互式的时间尺度下计算复杂计算的更新(第5部分)。

2. 动机:

为了激发我们新的计算框架，考虑确定图的连通部件结构的问题。在这个算法中，每个节点分配一个整数标签(最初是它自己的ID)，然后迭代更新到其邻域中的最小值。在关系设置中，通过将边关系连接到当前标注的节点，取当前标注的并集，计算每个节点ID对应的最小标注值，可以计算一次迭代:

在i步后，每个节点在其i-hop邻域中将具有最小的标签，并且当运行到固定点时，其连接的组件中将具有最小的标签。 以下数据流图说明了迭代计算：

为了使问题更具体，请考虑在Twitter在线社交网络上24小时内由@username提交形成的图的示例，并对比四种执行连接组件算法的每次迭代的方法。 图1绘制了针对各种算法的每次迭代中标签更改的次数，作为每种算法工作量的代表。 我们在第5节中确认运行时间表现出相似的行为。

图1:对于24小时的tweet窗口，使用三种不同的技术，通过迭代绘制不同的连接组件标签的数量。此外，还绘制出了更新第三条tweet时所需的差异。

最简单和性能最差的方法将上述查询重复应用于上一次迭代的结果，直到标签停止更改。 在这种情况下，所有先前计算的结果将在每一轮中都被新标签覆盖，从而导致每次迭代的工作量保持不变，并且图1中标记为“无状态”的平线也不变。 包括MapReduce[10]和Dryad[16]在内的数据并行框架在迭代之间不维护任何状态，只能以这种方式执行算法。
一种更高级的方法(“增量式”)将状态从一个迭代保存到下一个迭代，并使用增量评估策略根据先前迭代中的更改来更新标签集[13、17、19]。 当标签收敛到其正确值时，每次迭代所需的计算量就会减少。 在图1中，每次迭代的差异数量在第八次迭代之后呈指数衰减，并且总工作量不到传统方法所需工作量的一半。 增量方法确实需要在内存中维护状态以提高性能，不过不会超过标签的全部集合。

可以通过重新排序计算来改进增量方法的(“优先级”)，从而减少迭代之间的更改。例如，在连接的组件中，我们可以确定较小的标签的优先级，这些较小的标签在最小计算中更可能占优势，然后在较大的标签之前引入这些标签。这种思想在本质上与Zhang等人提出的优先迭代相似。 [28]。 实际上，总工作量仅是增量工作的10％，大约相当于无状态数据流系统完成的工作量的4％。

允许输入更改

差异数据流一般化了增量方法和优先级方法，并且可以用于实现其中任何一种，从而在差异中产生相同数量的记录。尽管差异数据流存储了多个迭代的差异(而不是丢弃或合并它们)，但为24小时窗口保留的总数仅比标签集（增量数据流所需的状态）多1.5％。

如果修改了输入图（例如，通过删除单个边），则可以显示微分数据流的功能。 在这种情况下，必须丢弃传统的，增量的和优先的数据流计算的结果, 并在新图上从头开始重新执行其计算. 可以使用支持递归查询的IVM算法，但是会有很大的计算或内存开销。相比之下，我们的方法(“微分(1s变化)”)能够重复使用图中未更改的部分相对应的状态。微分数据流系统可以区分由于更新的输入而产生的变化和由于迭代执行而产生的变化，并重用任何适当的先前状态。在图1中，我们看到，当最初的24小时窗口滑动1秒时，系统只处理了67个差异(这在跟踪期间是典型的)，并且在几个迭代中不需要做任何工作。更新滑动窗口完成的工作仅是完全优先级重新评估中完成工作的0.003％。

我们将在第5节中表明，差异的减少与执行时间的减少相对应, 并且对于这些类型的计算，可以实现多个数量级的性能改进。

3. 微分计算

在本节中，我们将描述差分计算如何跟踪更改并更新其状态。由于我们将在后面的部分中使用计算来实现数据并行数据流，因此我们在这里采用数据并行数据流系统的术语。 必须适应其不断变化的输入的函数称为operators ，其输入和输出称为collections 。我们将集合建模为多集，其中对于集合A与记录x，整数A（x）表示A中x的多重性。无论本文中的哪个示例描述了通用一元或二元运算符，都应假定运算符的扩展 具有两个以上明确的输入。

在计算的生命周期中，集合可以有多个版本，其中版本是某些部分顺序的成员。特定版本的集合称为集合轨迹，用粗体表示，定义为从偏序 的元素到集合的函数; 我们用符号来表示版本t的集合。我们将看到，在一次计算中，不同的集合可能会根据不同的部分顺序而变化。将操作符应用于集合跟踪的结果本身就是集合跟踪，这里用符号表示; 例如，对于一般的二进制运算符

计算的输入和输出被建模为集合轨迹，因此会按部分顺序变化。通常输入和输出随自然数变化，以表示连续的计算周期。

3.1 增量计算:

在增量计算中，我们为每一个的运算符考虑集合的序列: 和运算[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Fvy7bOgd-1603100189833)(C:/Users/Janus II/AppData/Roaming/Typora/typora-user-images/image-20201018114938846.png)]

最简单的方法（相当于图1中的“无状态”方法）是为每个t独立地重新执行，如图2所示。

当连续的A_t具有较大的交集时，我们可以通过增量评估获得可观的效益。 我们可以根据差异跟踪来定义后续版本中两个集合之间的差异，类似于集合跟踪，并再次为集合的每个版本取一个值。 差异和差异跟踪是使用应用于相应集合或跟踪名称的一个专用符号δ来表示的。

对于每个版本t>0 , 他们遵循这个公式:

注意可能为负，对应于从版本t的A中删除记录r。

运算符可以通过产生相应的输出对新的做出反应，如图3所示。增量系统通常会计算

并仅保留最新版本的集合

一旦将和并入各自的集合中，则将其丢弃。

对于随后的泛化，考虑等效公式将很有帮助:

在实际的增量系统中，运算符被实现为确保通常可以按大致与成正比的时间计算，这与完全重新评估所需的相反。

增量评估和循环依赖图可以结合起来影响迭代计算。非正式地说，对于将集合映射到集合的循环体f，可以将f的输出重新引入到其输入中。迭代t为某个初始集合X定义了，并且可以进行固定次数的迭代，或者直到集合停止变化。这种方法让人想起朴素的Datalog评估, 实际上可以使用增量计算来评估Datalog程序

不幸的是，增量计算的顺序性质意味着可以使用差异来更新计算的输入集合或执行迭代，但不能同时使用两者。 为了同时实现这两个目标，我们必须概括差异的概念，以允许使用多个先前版本，这将在下一部分中讨论。

3.2 偏序推广

这里我们介绍了微分计算，它将增量计算有机地融合在一起。数据仍然被建模为集合，但不是要求它们形成序列，而是可以部分排序。t一旦计算出来，每个个体差异就会被保留，而不是像增量系统那样被并入当前的集合中。此功能使我们可以根据集合可能更改的原因来仔细组合差异，从而使差异数量大大减少，计算量也减少了。

我们必须重新定义差异，以解决没有单个定义明确的的可能性。回到等式1，我们使用与之前完全相同的等式，但是s和t现在在偏序的元素范围内，而≤使用偏序的小于关系。 然后将差定义为和之间的差。 在下一部分中，我们将提供一些具体示例。

与增量计算一样，每个运算符都使用公式2从输入差异确定输出差异。重写后，我们可以看到，每个都由和严格的先验和确定：

使用偏序的一个结果是，与增量计算相反，输入和输出差之间不必一一对应。每个新的可能在多个不同的处产生。这使递增运算符的逻辑复杂化，第3.4节将对此进行详细讨论。

3.3 微分计算的应用

现在，我们考虑差分计算的三个示例，以显示差异的使用与先前的增量方法有何不同。 特别是，我们将概述从抽象的可组合性以及重新定义偏序以选择集合的最合适前驱的能力中获得的好处。

例1：增量和迭代计算

想象一个集合，它根据输入的回合i和包含它的循环的迭代j取不同的值。 例如，在第2节的连接组件示例中，可能是从第i个输入纪元的j跳邻域派生的节点标签。考虑其中的偏序

图4显示了基于此偏序的微分计算将如何消耗和产生差异

的一些区别很容易描述：

集合的初始值（等于）。
使前进到第二次迭代
将更新为第二个输入。

因为（0, 1）和（1, 0）都不小于另一个，所以和都不用于另一个推导中。 如果我们必须对版本强加一个总顺序，那么这种独立性将是不可能的，因为这两个版本中的一个必须首先出现，而第二个版本将*减去与第一个版本相关的任何差异。

考虑差异并查看其反映的变化是有益的。 回想

差异使集合的值与已经计算出的先前差异：。 请注意，并非所有先前计算出的差都被使用：即使可用，它也描述了第二次循环迭代，对于确定没有用。 在这里，保持每个的好处变得显而易见：最合适的差异集可以用作计算任何给定的起点。 因此，校正可能很小，实际上常常是完全空白的。 在图1中，微分计算的几次迭代（3、5和11之后）完全为空。
如果使用差异的总顺序，则可以仅根据来定义。 尽管已经计算出（一次迭代对可能在很大程度上相同的集合的影响），但的计算将无法访问此信息，并且会浪费精力进行一些相同的工作。 产品部分订单更适合遭受来自两个来源的独立更改的集合。

示例2：优先级和迭代计算。

微分计算也可以用于实现连接的组件优化，其中最小的标签首先在整个图中传播，然后是第二个最小的标签，依此类推，直到引入所有标签为止^[28]。 这种优先级方法更有效，因为在组件内仅传播最小的标签：较大的标签会立即遇到较小的标签，并且不会进一步传播。

为了实现此优化，我们使用字典顺序，如果，则。 每个标签 l以优先级l传播，并且其传播通过差异反映出来；当按字典顺序使用时，相对于先前优先级采用计算极限而不是。 这样可以减少差异，因为标签l的进度会在收到任何较低标签的顶点上立即受到阻碍。 所产生的顺序依赖性也减少了可用的并行性，但是在实践中可以通过批量处理优先级来减轻这种并行性，例如使用优先级传播标签l。
此优化是区分图1中的增量线和优先级线的基础

示例3：可组合性和嵌套

差分计算的一个吸引人的特点是它的可组合性。 由于增量由迭代组成，并以迭代为优先，我们可以轻松地将这三个方法结合起来，以使用简单的偏序组合器（此处为整数总阶与字典顺序的乘积）来创建一个增量，有优先权的迭代计算。 图1中的“ 差异”线是通过增量，优先级和迭代计算的组合获得的。由此产生的复杂性可以向用户隐藏，从而获得实际的性能提升，这将在第5节中看到。
对迭组合迭代计算的支持使嵌套循环成为可能：可以使用递增，迭代，优先排序，迭代实现（四维部分顺序）来计算强连接的组件。 我们在附录中介绍了针对强连接组件的数据并行算法

3.4差分运算符

现在，我们描述基本的运算符实现，该实现采用根据集合定义的任意运算符，并将其转换为差值。 在最坏的情况下，这种基本实现最终将重建整个集合并将其传递给运算符。 第4.3节说明了如何优化微分数据流实现中最常见的运算符，以避免这种最坏的情况。

在执行差分计算时，其运算符会被重复调用并带有差异以合并到其输入中，并且必须产生反映新差异的输出差异轨迹。 考虑一个二进制运算符f，它已经处理了两个相应输入上的集合轨迹 A和B的一系列更新。 假设必须将新的差异和应用于其各自的输入，其中差异和均具有版本。
式（3）用差轨迹表示对f输出的最终更新，公式（3）表明：

当at满足

对于b也一样

通过对t的归纳可以清楚地看出，当时，这反映出一种自然的直觉，即更新版本上的差异不会导致对之前的版本进行任何修改。 可能更令人惊讶的是，对于所有，即使，也可能存在的版本，其中。 幸运的是，可能需要更新的版本集并不是无限的，实际上，可以证明，如果，则，其中T是的上界和一些非零增量的

为了有效地计算任意输入的，我们的基本运算符必须将其完整的输入微分轨迹和存储在内存中。 在Naiad原型实现中，此跟踪存储在三重嵌套的稀疏计数数组中，首先由键k，然后由点阵版本t，然后由记录r。 Naiad仅维护非零计数，并且当记录被添加到差异跟踪中或从差异跟踪中减去时，Naiad会动态调整分配的内存。
借助按版本索引的和，可以针对任何t重建和，并使用算法1的伪代码显式计算。尽管重建似乎很昂贵，并且与增量计算背道而驰，但必须能够支持程序员可以为其指定任意（非增量）函数来处理所有记录的完全通用运算符。 我们很快将看到许多特定的运算符具有更有效的实现。
一种对算法1中算法的一般优化，减少了重建和值所花费的精力。
系统可以更新先前计算出的集合（例如，版本的），而不是针对每个t遍历所有s <t。 这样做只涉及差异

这通常导致需要更新的s相对较少，例如在循环索引前进的情况下仅需要更新一个。 通过确保按照尊重偏序的顺序处理差异，系统仅需要从和t的最大下限开始扫描，直到同时通过和t。 另外，如果可用一个以上的版本τ进行更新，则可以对它们进行批处理，从而再次潜在地减少了需要重建的集合数量和f的评估数量。

上面的解释假设微分轨迹将无限期保持，因此算法1中s <t上的重建循环的成本将随着t的增加而无限制地增长。 实际上，可以将视为到目前为止已发生的（部分排序）更新日志。 如果我们知道对于t <的任何版本都不会收到进一步的更新，那么直到[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9peZ93Nz-1603100190265)(https://gitee.com/janusv/typora-pic-bed/raw/master/img/20201018171935.png)]版本的所有更新都可以合并到一个检查点中，从而可以节省存储成本和重建工作。 Naiad原型包括此合并步骤，但细节不在本文讨论范围之内。

4.微分数据流

现在，我们介绍差分计算的实现：微分数据流。 如第6节所述，增量计算已在多种设置中引入。 我们为差分计算的第一个实现选择了一个声明性数据流框架，因为我们认为它非常适合作为主要动机应用程序的数据并行分析任务。
与有关查询计划和数据并行处理的现有工作相同，我们将数据流计算建模为有向图，其中顶点对应于程序输入，程序输出或运算符（例如Select，Join，GroupBy），并且边表示使用 一个顶点的输出作为另一个顶点的输入。 通常，数据流图可能具有多个输入和输出。 数据流图可能是循环的，但是在本文的框架中，我们仅允许系统引入循环以支持定点子计算。

4.1 语言

我们的声明式查询语言基于.NET语言集成查询（LINQ）功能，该功能通过声明性运算符（例如Select，Where，Join和GroupBy等）扩展了C＃，这些运算符应用于强类型集合^[5]。 每个运算符对应一个数据流顶点，具有来自一个或两个源运算符的输入边。
我们使用两种新的查询方法扩展LINQ，以利用不同的数据流：

FixedPoint接受一个源集合(某个记录类型T的集合)以及从T的集合到相同类型的集合的函数。 该函数表示循环的主体，并且可以包括嵌套的FixedPoint调用； 它会产生一个循环数据流子图，其中主体的结果将反馈给下一个循环迭代。
PrioritizedFP还具有一个函数priorityFunc，该函数应用于源集合中的每个记录，并表示这些记录应该被引入主体的顺序。 对于每个唯一优先级，依次将具有该优先级的记录添加到当前状态，并且循环迭代到到目前为止引入的记录上的定点收敛。 我们将在以下小节中更精确地解释语义。
这两种方法将任意微分数据流查询作为其主体，其中可能包括进一步的循环和排序指令。 系统管理部分订单的复杂性，并向用户隐藏细节。

4.2集合数据流

在本小节中，我们描述如何将使用上面的声明性语言编写的程序转换为循环数据流图。 我们在标准数据流模型中描述图，在该模型中，运算符可立即对整个集合进行操作，因为这简化了运算符语义的描述。 在4.3节中，我们将描述如何修改数据流运算符以对差异进行操作，而4.4节将概述系统如何调度计算。

回顾3.2节，集合轨迹根据部分顺序进行版本控制的模型集合。 我们要求对运算符的所有输入都以相同的部分顺序变化，但是对于我们考虑的所有部分订单，都存在一个简单的订单嵌入，该嵌入是使用Extend运算符实现的：

Extend运算符允许在定点循环外定义的集合在其中使用。 例如，连接的组件计算中的边集合相对于循环迭代i是恒定的，并且在引用循环中的边时使用Extend。
标准LINQ运算符（例如Select，Where，GroupBy，Join和Concat）每个都对应于数据流图中的单个顶点，并且将其通常的集合语义提升为适用于集合跟踪。

定点运算符

尽管定点运算符非正式地像一个循环体和一个后沿一样简单，但是我们必须仔细处理与循环索引相对应的新整数坐标的引入和移除。 可以使用三个新的运算符来构建定点循环（图5）：扩展部分顺序以包括新整数坐标的入口顶点，将循环体的输出作为后续迭代的输入的反馈顶点，以及 一个出口顶点，它从部分顺序中剥离循环索引并返回固定点。 （使用标准的Concat运算符来合并入口和反馈顶点的输出）更准确地说，如果输入集合X已经以偏序T变化，则入口运算符会产生随变化的轨迹。

反馈运算符获取循环主体的输出并提高其循环索引。 对于循环体W的输出，我们有

最后，egress运算符观察循环体的输出，并发出第一个重复的集合

对于这些运算符的实现，我们没有说什么具体的，但是在这个极限存在的地方, 它们的数学定义应该清楚地表明：

优先定点运算符

此运算符为集合中的每个记录分配一个优先级，并使用此优先级对将记录引入定点循环施加总顺序。 从一个空集合开始，运算符按顺序将下一个未引入优先级的记录引入到集合中，迭代到一个固定点（如上所述），并将结果用作下一个优先级的起点。
优先级定点运算符使用与未优先级定点运算符相同的数据流模板，包括入口，反馈，出口和Concat运算符（图5），但是它具有不同的语义。 入口运算符为每个记录的版本添加两个坐标，分别对应于其评估的优先级（p）和初始迭代（i = 0）：

其中P（r）是对记录r的priorityFunc的求值。
如第3.3小节所述，附加坐标（p; i）按字典顺序排序。
反馈运算符的作用更为复杂。 对于每个优先级的第零次迭代，它会反馈先前优先级迭代的固定点； 否则，它的行为就像无优先权的反馈一样。

最后，将egress运算符修改为在插入最终优先级之后发出定点：

4.3运算符的实现

3.4节概述了差分运算符的一般实现。 尽管可以使用通用运算符更新算法来实现任何微分数据流运算符，但我们还是专门实现了以下运算符，以实现更好的性能：数据并行运算。

利用数据并行结构是从微分数据流中受益的最有效方法之一。 对于数据流中的每个运算符实例f，假定存在一个键类型K，以及为每个运算符输入定义的键函数，该键函数将该输入中的记录映射到K。键空间定义f的独立性概念，可以 被写成

其中限制根据其关联的键功能键定义为

由于映射到不同键的记录子集可以在不同的CPU或计算机上进行处理而无需同步，因此在许多系统中都利用了这种独立性来并行化计算。 微分数据流系统可以以相同的方式利用并行性，但同时也可以从以下事实中受益匪浅：对集合的更新可以隔离到传入差异中存在的键，因此运算符只需对对应的集合子集执行工作。 在通常情况下，传入差异的大小和处理差异的计算成本都与这些子集的大小大致成比例。 很容易修改算法1中的伪代码，使其仅对映射到键k的记录进行操作，并且由于和由键索引，因此很容易只对对应的和子集进行工作

诸如Join和GroupBy之类的运算符自然会在其语义中包含关键功能。 对于诸如Count，Sum和Min的聚合，我们采用了一种稍微不标准的定义，该定义有效地为每个运算符添加了GroupBy。
例如，Count需要一个键函数并返回一组计数，该计数与映射到集合中每个唯一键的记录数相对应。 通过指定将每个记录映射到相同键的常量键函数，可以获得这些运算符的标准行为。

流水线运算符

包括Select，Where，Concat和Except在内的多个运算符是线性的，这意味着它们可以将δz确定为仅取决于δa的函数，而与δA无关。 这些运算符可以与前面的运算符进行流水线化，因为它们不需要维护任何状态，也不需要基于关键字对记录进行分组：它们将逐记录逻辑应用于δa ----非零元素，分别进行转换，过滤， 重复和否定输入记录。

Join

Join运算符通过计算这些输入的笛卡尔积来组合两个输入集合，并且只生成两个输入记录都具有的记录。 由于Join的分布特性，输入和输出之间的关系很简单

尽管Join的实现仍必须保持其输入差异跟踪常驻，但其实现比一般情况要简单得多。 输入δa可以直接与δB的非零元素连接，并且对于δb和δA可以类似地连接，而无需遵循算法1中的重建逻辑。

集合体

许多数据并行聚合具有非常简单的更新规则，不需要重新评估所有记录。
例如，Count只需要保留由累积权重定义的每个键的记录数差异记录，而不是映射到该键的记录集。 Sum具有类似的优化。 最小值和最大值必须保持其完整的输入差异轨迹，因为最小（最大）元素的缩回会导致第二（最小）记录成为新输出，但通常可以通过与更新进行比较来快速确定更新而不需要输出 无需重构A的先前输出

定点运算符

4.2节中的Extend，Ingress，Feedback和Egress运算符具有简单的差分实现。
Extend运算符为任何i报告相同的输出，因此

Ingress运算符将其输出从零更改为，然后又恢复为零，要求输出形式为

反馈运算符最初为零，但随着其输入的先前迭代更改而更改

Egress运算符产生最终看到的输出，这是到目前为止看到的所有累积的结果

非正式地讲，Ingress添加了一个新的循环索引，并为看到的每个输入生成了正输出和负的输出； Feedback推进了看到的每个输入的循环索引，而Egress删除了看到的每个输入的循环索引。 优先定点运算符PIngress，PFeedback和PEgress的不同实现遵循类似的方式

4.4调度微分数据流

调度微分数据流计算的执行由于需要协调循环数据依赖性而变得很复杂。 在我们的Naiad原型中，调度程序会跟踪在每个运算符处处理的未解决差异，并使用数据流图的拓扑对这些差异施加部分顺序，从而使系统能够对其进行拓扑排序，从而获得有效的调度 。 面临的挑战是，与每个差异相关联的版本在同一运算符上对两个未完成的差异进行排序，但是对于两个不同的运算符存在未完成的差异，则什么也没有说。

从直觉上讲，存在因果关系的概念：如果处理d1可能会导致版本的产生新数据，则版本s的运算符与版本s的差d1因果先于的版本t。 回顾一下第4.2节，有些运算符修改了输入差异的版本：例如，未优先级的Feedback运算符使版本的最后一个坐标前进。 调度程序将此信息与数据流图的边缘关系结合起来，以确定因果顺序并确定一组最小的未完成差异。 此后，重复安排最小差异之一可确保前进。
一些迭代的数据并行系统依赖于显式的收敛性测试[7、20、25]，而在微分数据流系统中，由于没有差异而隐含了收敛性。
因此，如果没有明显的差异，则所有输入都已处理，所有循环都收敛到固定点。

5.应用

为了支持这种说法，即微分数据流可以极大地提高增量计算和迭代计算的性能，我们现在描述一些示例应用，并介绍使用Naiad原型进行的初始性能测量¹.

5.1 Twitter连接组件

我们测量了第2节中描述的连接组件计算的每次迭代执行时间。

我们在具有48个（四个12核）1.9GHz处理器和64GB RAM，运行Windows Server 2008 R2 Enterprise Service Pack 1的AMD 皓龙处理器’MagnyCours’上进行了实验。图6显示了递增，优先和差异时间。 使用8个内核执行时（1s更改）版本的计算。 请注意，这些曲线与图1中的差异计数具有相同的相对顺序和大致相同的形状。与图1相比，与24小时差分计算相比，一秒钟的更新间隔较小的数量级。 这种低于预期的提速是由于工作量很小时渗透开销变得更加明显。 但是，Naiad能够在24.4毫秒内响应一秒钟的更新； 这比差分或增量数据流使用的7.1s和36.4s快得多，这使Naiad可以实时维护Twitter提及图的组件结构。

5.2迭代网络图算法

我们还使用了适用于ClueWeb的B类网络图的几种图形算法对Naiad的性能进行了评估。我们借鉴了Najork等人的工作。 [22]评估了三种算法在三种不同类型的平台上的性能，可伸缩性和易于实现性：Microsoft SQL Server 2008 R2并行数据仓库（PDW）关系数据库，DryadLINQ [24]数据并行批处理处理器， 以及可伸缩超链接存储（SHS）[21]分布式内存中图形存储。 为了进行直接比较，我们在Najork等人使用的同一实验集群上运行Naiad的分布式版本：16台服务器，具有8个内核（两个2.66GHz四核Intel Xeon E5430处理器）和16GB RAM，所有服务器均连接到 一台千兆以太网交换机。
表1列出了Naiad的总体改进，这是因为Naiad具有以下功能：它在内存中存储索引数据，在许多工作程序上分布计算以及在收敛时加速迭代计算的能力。值得注意的是，每个其他系统仅实现修整 -SCC的处理步骤，然后在简化图上运行单线程SCC； Naiad能够将SCC计算表示为声明性双嵌套定点计算，并在整个集群中分配全部执行。 这些工作负载都不是交互性的，并且这些评估并未利用Naiad支持增量更新的能力。 但是，每个计算都会自动递增，并且可以有效地响应输入图的变化。

6.相关工作

已经研究了许多增量执行方法。 据我们所知，微分数据流是第一个支持将任意嵌套迭代与输入数据的有效添加和删除相结合的技术。 但是，现有的增量计算研究发现了可能与微分计算互补的技术，在本节中，我们试图在此领域的相关工作之间建立联系。

增量视图维护

如前所述，微分数据流解决了与增量视图维护（IVM）解决的问题类似的问题，增量目标维护是为了在基于稍有不同的输入计算新视图时重用对先前输入所做的工作。 在过去的三十年中，受支持的查询集已经从简单的select-project-join查询[6]增长到完全通用的递归查询[15，23]。 尽管后一种技术非常广泛，但对于交互式大规模计算却不是理想的选择，因为它们要么执行过多的工作，要么保持过多的状态，要么限制了表达能力。 Gupta等人的经典DRed算法[15]可以高估无效元组的集合，并且在最坏的情况下，将执行大量工作来“消除”已删除元组的影响，只是得出以下结论： Nigam等人的扩展PSN算法[23]依赖于每个元组存储用于导出它的完整元组集合，这可能需要大量的状态。 Ahmad等人改进了包含高阶联接的查询的增量性能，但目前不支持迭代工作量[3]；这种方法可以适应包含这种联接的差分程序的好处。

增量数据流

像MapReduce和Dryad这样的数据流系统已经扩展，并支持增量计算。 康迪等。 开发了MapReduce Online [8]，它可以在内存中维护MapReduce作业链的状态，并对其他输入记录做出有效反应。 增量数据流对于粗粒度更新也很有用：Gunda等。
随后开发的Nectar [14]缓存了DryadLINQ程序的中间结果，并使用LINQ运算符的语义生成了利用缓存的增量程序。 Incoop项目[4]通过将输入缓存到reduce阶段，并仔细确保在更改输入后重新执行最少数量的reducers，从而为任意MapReduce程序提供类似的好处。 这些系统都不支持迭代算法，相反，它们是为处理非常大的数据的高吞吐量而设计的。

迭代数据流

为了扩展数据流系统的通用性，一些研究人员研究了将数据依赖的控制流构造添加到并行数据流系统的方法。
HaLoop [7]是MapReduce的扩展版本，可以通过重复执行MapReduce作业链直到满足数据相关的停止条件，来执行以递归SQL变体编写的查询。 类似的系统包括Twister [12]和iMapReduce [27]。 Spark [25]支持类似于DryadLINQ的编程模型，并为频繁重复使用的输入添加了显式的内存中缓存。 Spark还提供了“弹性分布式数据集”抽象，允许在发生故障时重建缓存的输入。所有这些系统都使用类似于4.2节中描述的面向集合的数据流的执行策略，并且将执行 D-Streams [26]通过执行一系列小批量计算来扩展Spark来处理流输入，但它不支持迭代。D-Streams[26]扩展了Spark以处理流输入。 CIEL分布式执行引擎[20]提供了基于“动态任务图”的通用执行模型，该模型可以对嵌套迭代进行编码；但是，由于CIEL不支持可变数据对象，因此对运算符进行细化的修改进行编码是不切实际的。
最近，已经开发了一些支持增量定点迭代的迭代数据流系统，这些系统实现了与图1中“ Incremental”行成比例的性能。Ewen等人扩展了Nephele执行引擎，并支持“ bulk”和“ incremental”。 迭代[13]，其中可以使用对当前状态的一系列增量更新来执行单调迭代算法。Mihaylov等人开发了REX [19]，它还支持增量迭代中的记录删除，但程序员负责编写 用户定义函数（UDF）的增量版本。差分运算符更新算法（算法1）会自动增量许多UDF，但是缺少部分更新顺序会限制其用途。最后，Conway等人最近引入了BloomL [ 9]，它支持使用各种单调函数的组合进行定点迭代，这种方法的优点是 可以在无阻塞的分布式系统中执行此类程序，这可能比Naiad当前的调度策略（第4.4节）更为有效，但它不支持撤消或非单调计算。

替代执行模型

已经开发了自动技术来递增除数据流以外的编程模型。 纯函数程序的基本技术是备忘录[18]，该备忘录已应用于多种现有系统[14，20]。 Acar率先推出了自调整计算[1]，它可以通过记录执行跟踪并仅重播跟踪变量中发生突变时直接受影响的那些部分，来自动递增具有可变状态的程序。 尽管可以将自调整计算的一般方法应用于任何程序，但使用"traceable“数据类型[2]通常更为有效，这些数据类型是支持高级查询和更紧凑操作的抽象数据类型。 跟踪中的表示形式。
响应式命令式编程[11]是一种使用数据流约束条件来执行程序状态更新的编程模型：运行时跟踪“响应式”变量的突变，这可能会触发对依赖于那些变量的约束条件的评估。这些程序中的约束可以是循环的，这使得连接组件和单源最短路径等算法可以在这个模型中表达。但是，只有在约束对程序状态具有单调影响的程序中才能保证收敛, 这使得在反应性命令式程序中很难表示边缘删除。
原则上，可跟踪的数据类型或高级数据流约束可用于实现差分计算。 此外，在许多情况下，微分数据流可能会受益于递增的用户定义函数（尤其是用户定义的GroupBy约简函数），并且自调整计算技术提供了自动执行此操作的潜力。

7. 结论

我们已经提出了差分计算，它概括了增量计算的现有技术。 差分计算的独特之处在于，它可以通过通用增量更新实现任意嵌套的迭代计算。 我们对Naiad的初步实验----数据并行微分数据流系统----展示了该技术可以使以前难以处理的应用程序实现，并在一些实际应用程序中实现最先进的性能。

在数据流的背景下，这些有希望的结果使我们得出结论，差分计算技术值得进一步研究，并且有可能类似地增强其他形式的增量计算。

8. 参考文献

[1] U. A. Acar. Self-adjusting computation. PhD thesis, Carnegie Mellon University, 2005.

[2] U. A. Acar, G. Blelloch, R. Ley-Wild, K. Tangwongsan, and D. Turkoglu. Traceable data types for self-adjusting computation. In ACM PLDI, 2010

[3] Y. Ahmad, O. Kennedy, C. Koch, and M. Nikolic.
DBToaster: Higher-order delta processing for dynamic, frequently fresh views. In 38th VLDB, Aug.
2012.

[4] P. Bhatotia, A. Wieder, R. Rodrigues, U. A. Acar, and R. Pasquini. Incoop: MapReduce for incremental computations. In 2nd ACM SOCC, Oct. 2011.

[5] G. M. Bierman, E. Meijer, and M. Torgersen. Lost in translation: Formalizing proposed extensions to C]. In 22nd OOPSLA, Oct. 2007.

[6] J. A. Blakeley, P.-˚ A. Larson, and F. W. Tompa.
Efficiently updating materialized views. In 1986 ACM SigMod, 1986.

[7] Y. Bu, B. Howe, M. Balazinska, and M. D. Ernst.
HaLoop: Efficient iterative data processing on large clusters. In 36th VLDB, Sept. 2010.

[8] T. Condie, N. Conway, P. Alvaro, J. M. Hellerstein, K. Elmeleegy, and R. Sears. MapReduce Online. In 7th USENIX NSDI, 2010.

[9] N. Conway, W. R. Marczak, P. Alvaro, J. M.
Hellerstein, and D. Maier. Logic and lattices for distributed programming. In 3rd ACM SOCC, 2012.

[10] J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In 6th USENIX OSDI, 2004.
computations. In 2nd ACM SOCC, Oct. 2011.

[10] J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In 6th USENIX OSDI, 2004.

[11] C. Demetrescu, I. Finocchi, and A. Ribichini. Reactive imperative programming with dataflow constraints. In 26th OOPSLA, 2011.

[12] J. Ekanayake, H. Li, B. Zhang, T. Gunarathne, S.-H.
Bae, J. Qiu, and G. Fox. Twister: a runtime for iterative MapReduce. In 19th ACM HPDC, June 2010.

[13] S. Ewen, K. Tzoumas, M. Kaufmann, and V. Markl.
Spinning fast iterative data flows. In 38th VLDB, 2012.

[14] P. K. Gunda, L. Ravindranath, C. A. Thekkath, Y. Yu, and L. Zhuang. Nectar: automatic management of data and computation in datacenters.
In 9th USENIX OSDI, Oct. 2010.

[15] A. Gupta, I. S. Mumick, and V. S. Subrahmanian.
Maintaining views incrementally. In 1993 ACM SigMod, 1993.

[16] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly.
Dryad: Distributed data-parallel programs from sequential building blocks. In EuroSys, Mar. 2007.

[17] G. Malewicz, M. H. Austern, A. J. C. Bik, J. C.
Dehnert, I. Horn, N. Leiser, and G. Czajkowski.
Pregel: a system for large-scale graph processing. In 2010 ACM SigMod, June 2010.

[18] D. Michie. \Memo" functions and machine learning.
Nature, (218):19{22, Apr. 1968.

[19] S. R. Mihaylov, Z. G. Ives, and S. Guha. REX: recursive, delta-based data-centric computation. In 38th VLDB, 2012.

[20] D. G. Murray, M. Schwarzkopf, C. Smowton, S. Smith, A. Madhavapeddy, and S. Hand. CIEL: a universal execution engine for distributed data-flow computing. In 8th USENIX NSDI, Mar. 2011.

[21] M. Najork. The scalable hyperlink store. In 20th ACM Conference on Hypertext and Hypermedia, 2009.

[22] M. Najork, D. Fetterly, A. Halverson, K. Kenthapadi, and S. Gollapudi. Of hammers and nails: An empirical comparison of three paradigms for processing large graphs. In 5th ACM WSDM, Feb. 2012.

[23] V. Nigam, L. Jia, B. T. Loo, and A. Scedrov.
Maintaining distributed logic programs incrementally.
In 13th ACM PPDP, July 2011.

[24] Y. Yu, M. Isard, D. Fetterly, M. Budiu, U. Erlingsson, P. K. Gunda, and J. Currey. DryadLINQ: A system for general-purpose distributed data-parallel computing using a high-level language. In 8th USENIX OSDI, Dec. 2008.

[25] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. Franklin, S. Shenker, and I. Stoica.
Resilient Distributed Datasets: A fault-tolerant abstraction for in-memory cluster computing. In 9th USENIX NSDI, Apr. 2012.

[26] M. Zaharia, T. Das, H. Li, S. Shenker, and I. Stoica.
Discretized streams: An efficient and fault-tolerant model for stream processing on large clusters. In 4th USENIX HotCloud, 2012.

[27] Y. Zhang, Q. Gao, L. Gao, and C. Wang. iMapReduce: A distributed computing framework for iterative computation. In 1st International Workshop on Data Intensive Computing in the Clouds, May 2011.

[28] Y. Zhang, Q. Gao, L. Gao, and C. Wang. PrIter: A distributed framework for prioritized iterative computations. In 2nd ACM SOCC, Oct. 2011.

演示：

滑动强连接组件在此演示中，我们将展示Naiad如何计算从Twitter流的时间窗口提取的提及图的强连接组件（SCC）结构，然后将其扩展以构建使用Naiad的交互式应用程序 跟踪窗口随时间前后滑动时这些组件的演变。

背景

经典的SCC算法基于深度优先搜索，并且不容易并行化。 但是，通过在外部FixedPoint中嵌套两个连接的组件查询（图7），我们可以使用Naiad（图8）编写数据并行版本。 严格来说，ConnectedComponents查询计算定向可达性，并且SCC算法反复删除其端点到达不同组件且因此必须位于不同SCC中的边。
通过反转每次迭代中的边缘，以交替的方向迭代地修剪图形，最终收敛到仅包含端点在相同SCC中的那些边缘的图形。
尽管Naiad的声明性语言使嵌套FixedPoint循环变得简单明了，但是生成的数据流图却相当复杂。 图9显示了简化版本，其中为了清晰起见将一些顶点组合在一起：在我们当前的实现中，该程序的实际数据流图包含58个顶点。 尽管如此，SCC程序接受增量更新，并且微分数据流使双重嵌套定点计算能够在其输入发生更改时有效地做出响应。

演示

交互式演示显示Naiad继续执行上述SCC查询。 输入的是来自整个Twitter firehose的一个月的推文，我们在给定的时间范围内计算由Twitter提及图形成的SCC。 图形化的前端使我们可以向前和向后滑动感兴趣的窗口（至少一秒钟的步长），并显示随着Naiad系统递增地重新执行查询，SCC的集合如何变化。 另外，我们对每个连续的SCC计算结果保持连续的top-k查询，并显示每个组件中最流行的主题标签。
当产生增量输出时（相对于Twitter流实时），GUI会自动刷新以显示Naiad计算的SCC的相对大小和最受欢迎的术语。 然后，用户可以在窗口中调查“热门话题”，我们甚至可以将特定的对话与当时发生的实际事件相关联（例如，在大约同一时间，我们看到一个包含＃标签的组件） 一场重要的棒球比赛）。
该演示突出显示了Naiad在执行包含双重嵌套循环的复杂增量查询时的响应能力。 我们认为，SCC代表了复杂的数据分析，而该分析在从数据仓库和科学应用程序到Web应用程序和社交网络的范围内越来越重要。 我们的演示强调了在单个声明式查询中有效组合增量更新，迭代计算和交互式数据分析的功能