大规模关系图增量计算框架研究.pdf

《大规模关系图增量计算框架研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《自动化与仪器仪表》2017年第7期(总第212期)大规模关系图增量计算框架研究刘玉芳(兰州职业技术学院甘肃兰州，730070)摘要:随着大数据时代的到来,关系图的规模日益扩大,现有的系统已经无法满足应用程序对图数据处理的及时性要求。提出了增量图计算原理,然后将关系图快照,增量数据计算以及数据延迟加载等机制加入到图计算过程中,并在此基础上提出了支持大规模关系图增量计算的框架,并对框架中的实现技术和核心模块进行阐述。关键词:关系图计算框架;关系图快照;增量数据计算;数据延迟加载中图分类号:TP311文献标识

2、码:ADOI编码:10．1４016/j．cnki．1001-9227．2017．07．033Abstract:Withthearrivalofbigdataera，thescaleoftherelationgraphiskeepingincrease，thetimelinessdemandsoftheapplicationcannotbesatisfiedfortheexistingsystem．Theextendinggraphcomputingtheory，combinedwithgraphsnaps

3、hot，extendingdatacomputing，andlazyloadingmechanismareemployedinthegraphcomputing，onthisbasis，thelargegraphcomputingframeworkisproposed，andthedetailoftheframeworkisdiscussed．Keywords:graphcomputingframework;graphsnapshot;;relationindex及节点到源数据的引用集合{ref}。0引言

4、在关系图中，现有的图数据存储中不断有新的数据加入，近年来，随着互联网应用的飞速发展以及以Web2．0技新加入数据之后，原有数据计算的结果就发生了变化，这些新[1]术为基础的社交网络的普及，互联网上的网页数量呈指数加入的数据在加入旧数据转换，根据用户自定义的计算，从而倍增加。社交网络中许多场景都需要用图结构来表示，而这实现全图数据计算结果的更新。些图数据中往往包含着很多实际的应用价值。与普通的关系图不同，社交网络图更新的更加频繁，新的信息不断产生。作为国内设计网络的代表，新浪微博月活动用户达2．01亿，全[

5、2]年净增４300万，这么多用户中每天都存在大量的注册和删除帐号，关注和取消关注，好友的添加和删除，这些操作都会图1节点增量计算更新过程导致关系图的变化。在图计算的开始阶段，节点不停地更新数据，在用户自定社交网络图的频繁更新，以及图结构的增量都具有局部义的规则下检测节点内容的变化，如图关系中有添加边，值改性，然而社交网络应用，如好友推荐，广告定向发送等，对网络变等，然后系统根据用户自定义的节点值计算方法，获得该节图的分析处理有一定的实时性要求，因此在处理社交网络图[5]点的新值，然后检测该值是否超过了预设

6、的阈值，一旦超过中要求尽快地分析处理。当前流行的图计算模型大多是全局阈值，则将该新值传播到用户自定义的一些节点，通常情况来[3]的，批量的计算模型，由于社交网络的庞大网络规模，这种说，新值的更新都是毗邻该节点的所有节点。通过用户自定计算模型的计算时间往往比较长，不能满足社交网络应用的[6]义的聚合操作，实现关系图的全局通信和状态变化的检测。实时性和及时性要求。由于社交网络中的更新具有增量性和在本次迭代过程中，本节点可能会受到其他节点值的更新，每[４]局部性，因此在离线计算引擎的基础上，本文将图快照机次更新

7、的过程中都会触发本节点状态的更新，因此这种循环制，增量数据计算以及延迟加载等功能应用到关系图数据的迭代，直到整个系统趋于稳定或者达到用户自定义的迭代计算过程中，保障大规模图增量数据计算的及时性。次数。1增量图计算原理1．2图快照机制通常来说，关系图存储在分布式存储系统上，而分布式存1．1增量图计算[7]储系统上的数据随着采集节点的工作，其数据在不停地更在图数据模型中，一个图G的定义可以表示为:新，而这导致图的计算存在不定性，为了方便计算，需要引入G=(1)图快照机制。图快照提供了

8、整个存储系统某一时刻的静态图五元组，其中gid是图的标识ID，V是图中所有节点的集[8]映像。图快照的定义如下:图G是图G的快照，则G保存合，L是图中关系的集合，T是图中允许的所有节点类型的集ii着拍摄快照时的所有符号状态及其子图，且G是只读的。在合，μ是图中时间信息的基本单位。对于节点的定义:i图数据不断地更新过程中，定时的拍摄快照，因此动态的图数node=(