论文部分内容阅读
图数据结构能够很好的表达数据之间的关联性，因此在社交分析、商品推荐、舆论监测和欺诈检测等应用中被广泛使用。随着互联网的发展，现实社会和生产环境中的图数据越来越呈现海量和动态特性。 目前发展较为成熟的分布式图处理框架Google Pregel、Spark GraphX和GraphLab等，所处理的图数据都是静态稳定的图数据。针对动态变化图数据的处理，大多集中在算法研究层面上，仅有的KineoGraph和IncGraph等系统是以串行的方式进行增量式更新，无法充分利用多机并行更新的优势，此外SpecGraph提出的基于推测机制的并发更新模型，虽然提高了系统的并行性，但其模型的出发点是状态更新只与顶点接收消息有关而与原始状态无关，这个约束又使得模型的表达能力有限。 基于现有工作的不足，本文提出了一种基于状态更新传播的流式图计算模型。它将连续不断的图数据流抽象成一系列的事件流，将用户关心的图计算结果抽象成图的状态，用户只需定义图状态如何根据到达的事件增量式地进行状态转换，就能完成事件流到状态流的映射，提供实时反馈中间计算结果的能力。本文的关键技术有(1)通过状态直接反映了用户所关注的信息，使得系统无需存储全部的图数据，而只需存储用户关心的数据，从而减少了存储开销;(2)通过采用增量更新和变化传播的方式，使得增量数据对全图的影响范围更小，迭代收敛的速度更快;(3)通过分析典型的图算法特征，抽象出两种常见的状态类型:独立状态和关联状态，通过对独立状态的分布式存储和并发更新策略，以及对关联状态的细粒度分布式锁的更新策略，能够有效解决关联状态下更新冲突的问题，从而提高了系统的并行性和正确率。 实验结果表明，相比较传统的批式图计算系统，实现的基于状态更新传播的流式图计算模型GraphFlow系统，能够实时计算并反馈结果，在本文给定的实验环境和算法下，90％的图数据更新请求能在12ms内得到响应;相比较动态图数据的估计模型，GraphFlow的准确率较高，计算偏差在1％以内;而采用细粒度分布式锁的方式进行并发更新时，更新冲突的概率在3％以内。