英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料

Kineograph：掌握快速变化的连通世界的脉搏

摘要

Kineograph是一种分布式系统，需要输入数据流来构造一个不断变化的图形，来获取存在于数据流中的关系。作为一个计算平台，Kineograph更多的支持图形挖掘算法，来及时的从瞬息万变的图形结构中提取有用信息。为了适应图挖掘算法，假设一个静态的基础图，Kineograph采用一种新的、高效的事务提交协议，创建了一系列连续快照。为了适应图的不断更新，Kineograph包括增量图计算引擎。我们在Kineograph中开发了最经典的三种应用来分析Twitter数据，这三种应用分别是用户排名、近似最短路径和争议性话题检测。对于这些应用，Kineograph需要真实的Twitter数据流，并维护所有用户和主题标签之间的图形关系。我们的评估显示，40机每秒可以处理100K的微博数据，Kineograph能够连续计算全局属性，如用户的排行，小于2.5分钟时。这一计算速率是2011年10月微博速率的10倍以上。

分类和主题描述 D.4.7[操作系统]：组织设计；D.1.3[编程技术]：并发编程

一般术语 设计，性能

关键字 图形处理，分布式存储

1.介绍

越来越受欢迎的服务，如Twitter、Facebook和Foursquare等代表网络搜索和网络挖掘的应用，已在过去的十年中大大推动了分布式系统的研究。这些新兴的服务提供的信息有两个特征。首先，新的信息（例如，微博）是不断产成的，其时间敏感性远远超过大多数静态网页。突发新闻的出现和传播迅速，使得新的流行活动和趋势主题，不断从物质世界的实时事件中产生。其次，虽然每条信息可能很短小，且只包含有限的文字内容，但是如用户、主题和微博等实体之间的连接可以揭示重要的社会现象。微博中的信息搜索和检索功能已经开始受到广泛的关注^[27]。

Kineograph是一种分布式系统，从不断生成的具有丰富结构和连接的信息中提取及时信息。Kineograph必须解决一系列新的问题。首先，Kineograph必须处理持续更新问题，且它的计算必须具有及时性。理想情况下，最新更新的分析结果应该在1-2分钟内计算得到。广泛采用的分批处理范例（例如，MapReduce ^[9]），不能通过优化吞吐量来保证所需的及时性。第二，Kineograph必须保持图型结构，捕获各种实体之间的关系。这点具有一定的挑战性，因为图往往比较大，并且必须始终以分布式的方式进行存储。第三，Kineograph必须支持使用图挖掘算法分析图结构。图的不断变化给许多图挖掘算法带来了挑战。例如，大多数的图挖掘算法假定静态的基本图，操作不断变化的图，最终结果可能不再是我们所期望那样。

针对这些问题，Kineograph设计了一个分布式内存图存储系统，和一个图引擎即基于传播的支持增量迭代的图形挖掘。分布式图存储定期产生可靠的和连续的快照，使现有的图挖掘算法可以应用于静态快照。为了避免不必要的干扰，本设计还将图的更新和图挖掘分开处理，当新的更新生成新的快照的同时，图挖掘也在处理现有快照。利用图更新的性质，使用一个基于仲裁复制的简单的新型的事务提交协议处理图的更新，用于有效的实现一致性和可靠性，而不需要全局锁定和复杂的跨服务器协调。使用可靠的连续快照，计算不需要被确定或复制。如果在图挖掘过程中出现故障，Kineograph则会重新启动。最终的计算结果可以使用传统的主备份方案进行复制。

我们设计的Kineograph系统是一个灵活的平台，开发人员可以使用Kineograph的API开发可扩展的图形应用程序。我们使用真实的微博数据作为数据源，在Kineograph上开发了三个有代表性的应用程序：TunkRank^[31]给用户排名，SP^[28]计算近似最短路径，K-exposure ^[27]检测有争议性的话题。我们对一些真实的微博数据集进行了测试，这些数据集以每秒10万微博量的速度，生成一个包含800多万个顶点和2900多万条边的图。我们的研究结果表明，Kineograph可以及时的显示图挖掘结果，平均计算结果表明所有的微博更新可以在2.5分钟内完成。

论文的其余部分介绍如下。第2节介绍Kineograph的概述，下面的章节中会有详细的描述。第3节介绍Kineograph如何创建并保存分布式的连续图形快照。第4部分介绍Kineograph的图形计算模型。第5节则讲述了怎样在Kineograph中开发应用程序，以及包括描述我们开发的三个有代表性的应用程序。第6部分描述Kineograph所支持的容错性、增量扩展性和衰减性。第7节是一些典型应用程序的评估报告。随后，第8部分是讨论相关操作。我们在第9部分进行总结。

2.概述

图1所示是Kineograph的概述。原始数据流（例如，微博）通过一组采集节点进入Kineograph（步骤1）。一个采集节点分析每个接收到的记录（例如，一条微博和与其相关联的前后文），创建一个图更新操作的“交易”，并给该交易分配一个序列号，然后把操作以序列号的形式分配给图的节点（步骤2）。图的节点本质上构成了一个可靠的分布式内存键/值存储器，支持增强图形。每个图节点上的存储引擎与每个顶点一一对应，而不是一个封闭的值字段，邻接表作为图形结构的元数据，其分别存储每个应用程序的相关数据。此外，该存储引擎支持快照。图节点首先存储从采集节点出来的图的更新。然后，在由中央服务维护的全局进度表中，从每个收集节点中获取图形更新进度（步骤3）。周期性的，一个snapshooter使所有的图节点生成一个快照，该快照基于进度表中当前序列号的

图 1系统概述

矢量（步骤4）。该矢量被作为一个全局逻辑时钟，定义一个周期的结束。然后，图节点被指定执行，并保证在本周期中所有的本地图形更新都会按照预先确定的顺序存储。这个周期所确定的最终结果生成了一个图形结果的快照（步骤5）。由于周期的作用，为了更新相关数据，图形结构里面的更新进一步触发了新快照里的增量图形计算（步骤6）。

Kineograph与现有系统不同的关键是图的更新与图的计算是分开的。这个重要的观点构成了一个简单且有效的系统架构。为了保证图的更新与计算是分开的，Kineograph将图形结构的元数据和应用程序中图形关联数据分开存储。图的更新简单，是因为它仅修改定义图形结构的元数据（例如，添加一个节点或添加一个边）。这种图的更新与计算的分开产生了一种新的事务提交协议，即为了不使用全局锁在图结构中创建全局的连续快照，图节点首先存储更新，然后在一个周期粒度执行这些更新。Kineograph使用快照以分段的方式进一步耦合图形计算和图形更新：图形计算是的静态快照上执行的，大大简化了图形算法的设计。最后，图的更新与计算的分离促进了Kineograph不同组件中分离器和简单的容错机制的发展（将在6.1节中描述）。

3.创建分布式的连续快照

在Kineograph中，图形节点由两层组成：一个负责维护图形数据的存储层，和一个负责图形计算的计算层。我们在本节中描述存储层，计算层将在下一节描述。

图节点的存储层实现了一个分布式键/值存储器，提高了原有的图形功能。一个图被分成固定数量到逻辑分区中，然后被进一步分配到物理机中。目前，图的划分是基于顶点id的哈希排列，而不考虑其局部性。这个方案简单，并通常有利于负载均衡。每个逻辑分区包括一组顶点、一组有向加权边存储在序列表中。边被认为是图形结构的一部分，并被存储层中的快照机制添加和修改。每个顶点也有一组顶点域，用来存储每个已配置的图形挖掘算法的相关数据。存储在顶点域中的值类型是任意的，只要它可以被序列化。

由存储层提供的一个关键功能是提供图形结构的连续快照。快照机制是通过采集节点、图节点和一个全局进度表共同实现的。Kineograph中的采集节点不仅仅作为简单的前端，同时还在系统中发挥重要的作用。一个采集节点负责将每个输入的记录传入一个事务中，该事务是由一组可能跨越多个分区的图形更新操作组成（例如，创建顶点v2，添加一个输出边到顶点v1，添加一个输入边到顶点v2）。在于顶点相关的数据结构中，这些操作可以全部被执行。此外，每个采集节点创建事务的序列，且其序列号是连续递增的。这些序列号被用于构造一个全局的逻辑时间标记，该标记决定哪些事务应包括在快照中，也可以作为该快照的标识符。

Kineograph的快照机制实现了一个新的事务提交协议，该协议只有在一个时间段被定义后才会提交更新，然后再处理更新。一个采集节点向图节点发送图更新操作，还包括这些操作所属事务的序列号。通过记录每个采集节点的一个序列号，进度表与每个采集节点的进度保持一致。一个采集节点i更新入口到序列号s_i，并已经从所有相关的节点接收确认，所有的事务到s_i的图更新操作已被接收并存储。周期性地（例如每10秒），Snapshooter从当前全局进度表中获取序列

图 2在分区u和v间创建一个连续的快照的例子

号的向量，lt;s₁ ,s₂ ,...,s_n gt;，其中s_i是与采集节点i相对应的序列号，并且它作为一个全局的逻辑时间标记用来定义当前周期的结束。所有图节点都满足这个定义，即所有属于这个周期的图形更新被修改为同一确定性的，但是人为定义的，在所有逻辑分区内排序。当且仅当sle;s_i成立时，从采集节点i获取的图的更新，其序列号s包含在周期lt;s₁ ,s₂ ,...,s_n gt;中。即使，在一个逻辑分区中的操作是串行处理的，但是通常每个图节点上都会有足够的逻辑分区，来满足服务器级别的并发性。如图2展示了一个例子，分区u和v被指定由一个全局逻辑时间标志，从进度表中创建一个连续快照。

创建快照的同时并不会停止获取更新。采集节点会以更高的序列号连续发送新的图形更新到系统。发送（采集节点）和存储（图节点）图更新操作的过程，与使用这些更新创建快照的过程是重叠的。这种属性确保了在足够长的一段时间内延迟执行不会影响到吞吐率，即使它可能会产生额外的延迟。为了保证合理的时效性和能够处理更高的图形更新传入速率之间的平衡，Kineograph在一个小的周期窗口中有效地进行批处理操作。在更高的速率中，批处理会变得更加有效。

一致性 ：

为避免采集节点之间的阻断，新型的事务提交协议提供了一个非传统的并发控制解决方案。由于图形更新的简单性，当采集节点发送事务性操作时，协议不需要全局串行。snapshooter从进度表取回全局逻辑时间标记（向量时钟的一种形式），使全局串行被延迟且隐含实现，阻挡了系统关键路径。这个过程与现有的方案（例如，两相锁定和时间标记排序）有本质上的区别^[30]。

Kineograph保证，要么事务中的所有操作都包含在一个快照中，要么都不在。这保证了一个快照中不包括某一顶点，该顶点拥有输出边，但不能匹配输入边到目标顶点。Kineograph进一步确保来自同一采集节点的所有事务以相同的序号顺序被处理。值得指出的是，由于图形更新和图形计算的分离，Kineograph在创建连续快照时只处理简单的图形更新，并利用每个事务由一组图形结构的更新组成且可以被一个单一的顶点结构应用的事实。更新依赖于顶点的状态，这种情况只有在计算阶段（对于图形挖掘）才能见得到。

本质上，Kineograph的快照机制确保被包含在一个快照中的事务组的一致性，甚至可以在该组内强加一个人为地顺序，使所有的事务都以相同的顺序进行处理。然而，顺序是人为的。例如，图形节点可以被指定处理那些来自第一采集节点的所有更新，之后再处理来自第二采集节点的所有的更新，并依次类推。这种外部强加的顺序不考虑任何因果关系。它所反映的既不是物理时间顺序，也不是任何因果顺序。我们发现在我们的情况这已经足够了，有一部分是因为Kineograph从图挖掘分离出图的更新——图的更新通常是简单明了的。在大多数情况下，顺序是不重要的。即使更新以不同的顺序被应，但得到的图形将保持不变，并且所有图节点的顺序也相同。Kineograph的一个重要的特性是保证顶点的生成是确定性的。例如，如果一个顶点是为每个微博用户ID而创建的，那么该顶点有一个内部ID，则该ID确切地取决于微博用户ID。通过这种方式，我们甚至可以在该顶点被创建之前，为该顶点创建一个输入或输出边，从而消除交叉操作依赖关系。

4.支持增量图挖掘算法

在Kineograph中，图节点计算层负责执行增量图挖掘。基于图形最近的变化，计算结果被更新，反映在新的快照中。图挖掘算法在一组用户定义的顶点域上操作，这些顶点域存储了该类算法的相关数据。

Kineograph采用基于顶点的计算模型^{[ 17，18 ]}。在这个模型中，所关注的数据与顶点一起存储，并通过处理交叉顶点来计算所得。

4.1概述

图3从顶点的角度说明了整个图的挖掘过程。最初，Kineograph使用用户定义的规则来检查点状态用于对比以前的快照。如果顶点已被修改（例如，边的增加，值的改变），Kineograph调用用户指定的功能来计算与顶点相关的新的值。

图 3算法概述

如果值明显发生改变，Kineograph则会将这些更改传送到用户定义的顶点集（通常在附近）。在计算中有一个可选的聚集阶段，其中某一点有可能参与图规模削减来计算全局值。这些值可以是任意的复杂的值，如顶点x是有影响力的用户，或

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[153836]，资料为PDF文档或Word文档，PDF文档可免费转换为Word