第40卷 计算机学报 Vol.402017论文在线出版号No.61 CHINESEJOURNALOFCOMPUTERS OnlinePublishingNo.61———————————————本课题得到国家自然科学基金(61572039)、国家“九七三”重点基础研究发展规划项目基金(2014CB340405)和深圳政府研究(JCYJ20151014093505032)资助. 黄权隆(通讯作者)，男，1991年生，硕士研究生，主要研究领域为数据仓库、分布式存储.E-mail:huang_quanlong@126.com. 黄艳香，女，1990年生，博士研究生，计算机学会(CCF)会员（0297748）, 主要研究领域为社交媒体数据分析、大数据处理分析及应用. 邵蓥侠，男，1988年生，博士，博士后, 主要研究领域为大规模图数据分析. 孟嘉，1982年生，硕士，明略数据系统架构师、技术合伙人，主要研究领域为分布式存储. 任鑫琦，1984年生，硕士，明略数据产品总监、技术合伙人，主要研究领域为大数据计算和可视化. 崔斌，男，1975年生，博士，教授，计算机学会(CCF)杰出会员, 主要研究领域为数据库、社交数据分析、大规模图挖掘. 冯是聪，1973年生，博士，明略数据CTO，大数据分析与挖掘.HybriG：一种高效处理大量重边的属性图存储架构黄权隆1)黄艳香1)邵蓥侠1)孟嘉2)任鑫琦2)崔斌1)冯是聪2)1)(北京大学信息科学技术学院高可信软件技术重点实验室, 北京100871)2)(北京明略软件系统有限公司, 北京102218)摘要 在图中，起点和终点都相同的两条边称为重边。属性图是一种带标志和重边的有向图，图中的点和边可以拥有任意数目的属性值。属性图由于其丰富的表达能力而广泛应用于实际建模中。实际应用中一般用图数据库解决属性图的存储需求。相比于传统的关系型数据库，图数据库在做多跳邻域查询、路径查询等与图结构相关的查询时，具有更优异的性能。Titan是产业界日渐关注的一个开源的分布式图数据库，Titan的数据以邻接表的方式组织，每个点的邻接表存储了相邻的所有边，这使得与邻接点集相关的查询都需要遍历整个邻接表。当图中含有大量重边时，邻接表规模巨大，这种数据组织方式导致邻域查询性能严重受损。邻域查询是大部分图查询的基础，如多跳邻域查询、路径查询、局部聚集系数查询（计算）等，这些查询往往由嵌套的邻域查询实现，随着邻域深度的增加，这种性能受损将被急剧放大。本文提出了一种基于Titan和列式存储数据库HBase的复合架构设计——HybriG，基于Titan和HBase建立存储层，用Titan来存储图的结构信息和点集的属性信息，HBase存储边集的所有属性信息。在HybriG中邻接表保持了项数和数据量上的精简，从而能克服上述图数据库的缺点。相比于传统图数据库Titan，HybriG在邻域点集相关查询以及边集数据批量导入上的性能提升一个量级以上。本文介绍了HybriG基于Titan和HBase的存储设计，并描述了在此存储设计基础上，如何高效地实现图查询以及图数据的插入操作。此外，本文还提出了图数据的高效导入方案，并保证导入过程中Titan与HBase存储数据的一致性。最后通过实验验证了HybriG在处理大量重边时的优异性能。关键词 属性图；重边；图数据库；Titan；HBase；架构设计中图法分类号TP18论文引用格式：黄权隆,黄艳香,邵蓥侠,孟嘉,任鑫琦,崔斌,冯是聪,HybriG：一种高效处理大量重边的属性图存储架构,2017,Vol.40,在线出版号No.61HuangQuan-Long，HuangYan-Xiang,MengJia,,RenXin-Qi,CuiBin,FengShi-Cong,HybriG:ADistributedArchitectureforPropertyGraphwithLargeSetofMulti-edges,2017,Vol.40,OnlinePublishingNo.61HybriG: ADistributed Architecture for Property Graph with Large Set ofMulti-edges网络出版时间：2017-05-19 12:00:37网络出版地址：http://kns.cnki.net/kcms/detail/11.1826.TP.20170519.1200.006.html2 计算机学报 2017年HUANGQuan-Long1)HuangYan-Xiang1)SHAOYing-Xia1)MENGJia2)RENXin-Qi2)CUIBin1)FENGShi-Cong2)1)(KeyLaboratoryofHighConfidenceSoftwareTechnologies(MOE),EECS,PekingUniversity,Beijing100871)2)(MiningLampSoftwareSystemCo.,Ltd.Beijing102218)Abstract ThepastdecadeshavewitnessedthemassivegrowthofInternet.Vastamountofgraphdatawasproducedbytheboomofsocial network, e-commerceandonlineeducation. Toanalyzeandmanagegraphdata, therearetwobranchesofdevelopment.Onefocusesondistributedgraphcomputing,solvingproblemslikePageRankorotheralgorithmsthatfitintotheBulkSynchronousParallel (BSP)model. SystemslikePregel, GraphLabandPowerGraphareproposedforthisbranch. Theotherbranchfocusesonmanagementofgraphdata,providingsupportlikeOLTPandgraphqueries. Inthisbranch,graphdatabaseslikeNeo4jandTitanaredevelopedformanagementofpropertygraph.Thepropertygraphisadirected, labeledgraphwithmulti-edges, i.e.,edgeswiththesamesourcevertexanddestinationvertex. Vertices andedges canbeassociatedwithanynumber of properties. Sinceit canrepresentgraphdatainmostscenarios, thepropertygraphmodelhasnumerousapplicationsinindustry.However, traditionalgraphdatabasesencountersignificantperformancedegradationwhenthegraphcontainslargeamountofmulti-edges.Werevealthecauseof thisinTitan. It’sanopensourcedistributedgraphdatabase, whichhasattractedwideattentioninindustry. Furthermore, weproposeHybriG, abetterdistributedarchitecturebasedonTitanandHBaseforthisscenario. Titanstoresgraphsinadjacencylistformat,whereagraphisstoredasacollectionofverticeswiththeiradjacencylists.Eachentryoftheadjacencyliststoresanedgeoravertexproperty.Whenqueryingaboutadjacentvertices,Titanhastolookthroughtheentireadjacencylistofthesourcevertex,whichisawastesincewejust needtheconnectedverticesbut not themulti-edges. Thiscost hurtstheperformancewhenthemulti-edgeset growsexplosively. Forhighlevel queriesthat arebasedonadjacent verticesquery, e.g. pathqueries, local clustercoefficient queriesetc., theperformancelosswill beworse. HybriGimplementspropertygraphmodel aswell. It storesthevertexdataandgraphstructureinTitan, theedgedatainHBase, respectively.WechoseHBasesinceit’soneof thestorageenginesofTitanandiswidelyusedinindustry.StoringpartofthegraphdataintoHBasewon’tbringtoomuchcostbecauseit’salsothedatastoreofTitan.ThisseparationhelpsHybriGtokeepaconciseadjacencylistaboutthegraphstructure,whichhelpstogainanorderofmagnitudeimprovement inexecutionof adjacent verticesbasedqueriesandbatchloadingof edgeset. Thedifficultyof thisseparationsolutionisthatweshouldguaranteetheconsistencyofedgedatabetweenTitanandHBase.Inmostofthescenarioswithlargeamount ofmulti-edges, multi-edgesareusedtorepresent event-likedata, e.g. phonecall recordsbetweentwopeople, whichwon’t bemodifiedafter insertion. Thuswecanrelaxtheconsistencyconstrainof edgedatatojust guaranteeconsistencyforinsertion.WeleveragethetransactioninTitantoachieveconsistencywithHBaseinedgeinsertion, especiallyinbatchloadingofedgedata.Finally,extensiveexperimentshavebeenconductedtoshowtheoutstandingperformanceofHybriG.Keywords propertygraph;multi-edge;graphdatabase;Titan;HBase;architecture1引言图是一种表达能力丰富的数据结构，实际应用中往往用点表示实体，用边表示实体间的关系。在有向图中，如果两条边具有相同的起点和终点，则称这样的边为重边（multi-edge）。属性图[1]是一种带重边的有向图，图中的每个元素（点/边）可以拥有任意数量的属性值。特别地，每个元素都有一个label属性，标识该元素的类别。实际应用中，有些属性图会含有大量重边。比如在电信行业的通话关系图中，两人之间可以发生多次通话关系；又比如金融行业的交易关系图中，两人之间可以发生多次交易关系。更复杂的，在刑侦应用中，整个情报系统获得的信息融合成一个知识图谱[2]，其中的实体和关系类型丰富多样。比如实体类别有人、汽车、公司等，实体间的关系有亲属关系、共同出行关系、通话关系等。有的关系是可以多次重复的，频次可能成百上千，这使得两个实体间不仅有多种label（即多种关系）的边，还包含大量重边。图1是属性图在刑侦场景中的一个简单示例，显示了类型为人的结点以及通话关系和共同出行关系。其中共同出行关系是双向的，因此在图中以无向边表示。刑侦场景中的典型查询包括：从一个人出发查询与其相关的所有人（邻域点集查论文在线出版号No.60 黄权隆等：HybriG：一种高效处理大量重边的属性图存储架构 3询）、查询两个人在几跳内是否有关系（路径查询）、查询两人之间的所有关系（两点间边集查询）等。图1属性图示例由于重边在实际应用中常表示事件类型的关系（如一次通话记录），传统解决方案将数据存储在关系型数据库中。关系型数据库能胜任图数据的存储，也能方便地检索元素的内容，但在图结构相关的查询上表现欠佳。比如在两跳邻域查询中，锁定一个嫌疑人后，要查看其两跳范围内的子图信息。为得到第二跳的邻域结点，需要对各种关系表做昂贵的JOIN操作。图数据库由于其以图的形式存储数据，在图的拓扑结构查询中具有更优异的性能。因此当应用场景中图的拓扑结构查询与元素的内容查询同等重要时，图数据库是最佳的选择。明略数据①的SCOPA②平台即使用图数据库实现其存储核心。SCOPA是明略数据的重要产品，在海量刑侦数据上构建起一个数据分析挖掘平台，展现给领域专家的是一张属性图，关联了客户的所有数据。在富含重边的属性图中，图数据库的查询性能不佳。图数据库以邻接表的方式存储图，表中每一项存储一条边。这使得查询邻接点集时，需要遍历整个邻接表中的所有边，而查询目标只是这些边里邻接的点集数据。当图中含有大量重边时，邻接表规模巨大，这种数据组织方式导致邻域查询性能严重受损。邻域查询是大部分图查询的基础，如多跳邻域查询、路径查询、局部聚集系数查询（计算）等，这些查询往往由嵌套的邻域查询实现，随着邻域深度的增加，这种性能受损将被指数级放大。一种简化重边的建模方式是，将所有同label的重边合并为一条边来表示，边上存储这些重边的所有信息，这样两个实体间的重边数能降低为边的label种类数。然而，将多条重边的数据合并在一条①http://www.mininglamp.com2017,3,29②http://www.mininglamp.com/solutions/scopa2017,3,29边中存储，会使边的单位数据量骤增，图中的数据粒度过大，同时降低了单条重边的检索和插入效率，每次操作都要先读取相关的所有重边数据，再在其中做查询或插入操作。因此，处理大量重边是一个不可避免的需求。在许多富含重边的图应用场景中，数据的操作需求相对单一，而且没有很强的事务性要求。比如在SCOPA的刑侦应用场景中，数据都是一些客观的事实数据，不需要修改，数据操作主要是图查询和批量的图数据插入。图数据插入操作包括原始的全量数据导入和定期的增量数据导入，可以规避并发的写冲突，也不需要很强的事务性要求。基于上述观察，在放宽了对强事务的支持后，我们可以设计一个相比传统图数据库更为高效的属性图处理系统，来应对含有大量重边的应用场景。本文提出了一种基于图数据库Titan③和列式存储数据库HBase④的复合存储架构——HybriG。HybriG能从容地处理富含重边的属性图，克服图数据库的局限性，具有更好的查询和插入性能。HybriG架构应用于SCOPA的底层核心设计，在实践中也验证了其性能的优异性。本文的贡献主要有：分析了图数据库处理大量重边时性能受损的原因，并基于此提出了解决方案HybriG及其存储、查询和高效数据导入设计，最后通过实验验证了HybriG的优异性能。本文组织如下：第2节介绍图数据库相关的预备知识，包括HBase及Titan的实现及其在处理大量重边时的局限性；第3~6节介绍HybriG的系统架构，包括查询模块的设计，数据高效导入方案的设计，以及数据一致性的设计；第7节展示实验结果；第8节介绍大规模图数据处理的相关工作；最后在第9节对本文进行总结。2预备知识介绍2.1HBase简介HBase是Hadoop⑤生态系统中一个列式NoSQL数据库，基于BigTable[3]模型设计，搭建在HDFS（Hadoop分布式文件系统）之上。③Titan,http://titan.thinkaurelius.com2017,3,29④ApacheHBase,http://hbase.apache.org2017,3,29⑤Hadoop,http://hadoop.apache.org2017,3,294 计算机学报 2017年图2BigTable模型示例BigTable是Google在2008年提出的一个处理海量数据的NoSQL数据库。图2是BigTable的模型示例。在BigTable的模型中，数据表以行为单位组织，每行由一个键值唯一标识，称为行键（rowkey）。一行中可以包含任意数目的单元格（cell），每个单元格由列名、版本号（时间戳）和值（value）组成。BigTable中的行是以行键排序的，每一行中的单元格又是以列名和版本号进行排序，这使得其与关系数据库一样能快速定位到目标单元格。区别于传统关系模型，BigTable中的列名不需要事先定义，因为其底层实际为一个Key-Value图4当属性图富含重边时，Titan在HBase中的数据表是一张扁平而宽的表。存储，如同数据结构Map不需要事先定义所有key。每个列名从属于一个列族，只有列族需要在定义表结构时给出。HBase提供对某一行数据的Put、Get、Delete接口，能够具体操作该行中的给定列。另外，HBase提供给定行键范围的Scan接口，可以快速地获得连续几行的数据。Scan接口也可指定特定的列或附加Filter来过滤无关数据。HBase由于其优异的可扩展性和稳定性，在产业界已得到广泛应用。2.2图数据库Titan图数据库是以图的形式来表示和管理数据的数据库[4]，与传统的关系型数据库相比，图数据库在图结构相关的查询上有更优异的性能，如多跳邻域查询、路径查询、局部聚集系数计算等。Titan是一个基于Blueprints①接口设计的开源图数据库，其实现了一个可插拔的存储接口，可以部署在BerkerlyDB②、HBase或Cassandra[5]之上。相比于著名的图数据库Neo4j[6]，Titan是完全开源免费的，其受关注度正在与日俱增。而且由于Hadoop生态系统在产业界的广泛应用，在HBase上搭建Titan，即使用TitanonHBase应对图处理需求是较为常见的选择。①TinkerPop Blueprints: AProperty Graph Model Interface,https://github.com/tinkerpop/blueprints2017,3,29② Oracle Berkeley DB Java Edition,http://www.oracle.com/technetwork/database/berkeleydb2017,3,29图3Titan内部的BigTable实现在图数据库Titan中，基于BigTable模型，数据在HBase中以邻接表的形式存储，如图3所示。Titan为每个点分配了一个全局唯一的id，每个点占BigTable中的一行，行键就是点的id。每行存储了该点相关的属性和边，它们各占一个单元格。Titan在BigTable模型中设置最大版本数为1，从而使每行中的列名与单元格一一对应，根据行键和列名可以快速定位到目标单元格，实现对边和属性内容的快速检索。在Titan中，每个属性是一个key-value对。点的属性存储在该点所在的行，每个属性占一个单元格，并以属性名key作为列名，这使得每个点的属性查询可以非常高效。每个点所在的行还存储了邻接的所有边数据，每条边占一个单元格。一条边的信息包含了邻接点、类别（label）、方向、边的唯一id，以及边上的各属性。单元格的值用来存储边上的所有属性，论文在线出版号No.60 黄权隆等：HybriG：一种高效处理大量重边的属性图存储架构 5列名则存储边上除属性外的其它信息。在BigTable模型中，同一行的单元格按列名排序。为了方便检索，每条边所在的单元格依次以label、方向、邻接点id以及边id拼接成为列名，即列名=边label+方向+adjVid+eid这种列名设计使得一个点的所有边先按label排序，再按方向、邻接点id、边id等排序。其优点是当要检索该点指定label的所有边时，只需要扫描邻接表的一部分。图4是一个更详细的示例。2.3图数据库Titan的局限性当图中的重边数量巨大时，Titan的邻接表列数也急剧变大，这会对邻域中点和边的检索带来严重影响。图4展示了一个富含重边的场景，为方便展示省略了边的方向。v1只有v2和v3两个邻接点，其中与v2有两种label的边，与v3有一种label的边。虽然邻接的点数不多，但v1与邻接点都有数量巨大的重边。由于邻接表存储的是每条边的信息，当要查询v1的所有邻接点集（即v2、v3）时，不得不遍历一次v1的所有边，即遍历整个邻接表。当重边数量巨大时，这是大量的无谓开销。为了规避上述情形，我们可以换一种列名设计来优化邻域点集查询，比如让邻接表先按邻接点id排序，令列名=adjVid+边label+方向+eid这样当发现一个邻接点时，可以跳过相同邻接点的所有边，不用再遍历整个邻接表。然而，面对label相关的查询时又会面临同样的问题，比如查询该点总共有几种label的边，仍需要遍历该点的整个邻接表。因此，改变邻接表的列名设计并不能解决问题，本质原因是邻接表存储了所有的边集。另一方面，Titan为加快数据访问设计了缓存，存储最近访问的点及其邻接表内容。如果图中各点的重边都很多，则缓存空间被大量的重边占满。由于是重边，这些边中只有为数不多的邻接点。在做邻域点集相关查询时就会极大增加缓存的失效率。面对富含重边的属性图，把所有边集都存在邻接表中是Titan性能受损的原因所在。3 HybriG的系统架构概述为了更好地应对含有大量重边的属性图应用场景，规避传统图数据库的局限性，本文提出了一种复合存储架构HybriG。HybriG架构应用在明略数据的关联数据分析平台SCOPA中，提供属性图数据的查询与存储。HybriG将图的连接信息和点集的属性数据存储在Titan中，边集的所有属性数据则直接存储在HBase中。由于HybriG架构基于Titan和HBase实现存储，而Titan的数据本身也存储在HBase中，为了方便表述以及避免混淆，下文中的HBase指的都是不包含Titan数据表的部分。Titan在HBase中的数据表直接用Titan代称。图5展示了HybriG的系统架构。StorageLayer图5 HybriG系统架构是HybriG的存储层，QueryAdapter和DataLoader分别为用户程序提供图查询和数据插入接口。其中，QueryAdapter将图查询转换为对Titan和HBase数据的高效查询，再将结果汇总返回给用户程序。DataLoader实现了数据的高效导入，在面对大批量的数据导入时，实现了错误恢复、断点恢复机制，同时保证了Titan和HBase的数据一致性。下面将分别介绍HybriG各模块的实现。4 StorageLayerHybriG将图数据分开存储在Titan和HBase中。具体地，如果两点之间有相同label的重边，HybriG会在Titan中这两点间建立一条该label的边，将对应重边的数据都存储在HBase中的一个表，不妨称其为边表。每条边一行，行键是Titan图中分配的边id拼接上重边的主键，单元格的值则存放具体边的内容。重边的主键是这样定义的：在两点间同label的重边中，如果有一个属性能唯一确定一条边，则选该属性作为主键。比如交易关系的时间戳，两个人在同一个时间点只能发生一次交易，因此该时间戳可以唯一确定两人间的一次交易。如果某种label的边没有属性能唯一确定一条重边，则选该数据插入的时间戳作为主键。6 计算机学报 2017年在HBase边表中，同label的重边数据的行键都有相同的前缀（即Titan中的边id），由于HBase中的数据是按行键排序的，它们在HBase中有相邻的位置。label相同的重边经常会被同时检索，这种设计使得一次顺序扫描便可得到所有同label的重边。另外，HybriG利用Titan中边上的属性记录一些统计信息，如原图中实际有几条这样的重边，或者边上某个属性值的求和等，这些统计信息可以根据业务定制，用来加快业务相关的查询，不用再遍历相关的边。图6是数据存储的一个示例，左边是实际要存储的图数据，e1、e2、…、en都是label为“交易”的重边，表示两人的所有交易记录。右边是数据在Titan和HBase中的存储情况。Titan中只存一条label为“交易”的边，该边有一个属性记录实际的边数。利用这条边的id作为前缀，拼接上重边的主键（交易的时间戳）作为HBase的行键，将每条边的数据都存入对应的单元格中。本文在引言中提到了一种避免产生重边的建模方式，即将所有同label的重边合并为一条边来表示，边上存储这些重边的所有数据。HybriG架构图6 HybriG存储示例。左图为原始数据的属性图，右图为数据在Titan和HBase边表的存储情况。图7合并同label重边示意。左图为实际数据图，右图为Titan中的存储示意图。无向边中的重边是指端点对应相同的两条或多条边，有向边中的重边是指起点和终点对应相同的两条或多条边。与其有相似之处，但本质区别是边集元素的数据粒度仍是每条重边，不会将多条重边的数据作为一个单元来处理。在HybriG中每条边的数据独占HBase边表中的一行，因此每条边的相关操作都会更加高效。得益于HBase的高可扩展性，这种存储方式的性能也不会受制于数据规模的增长。而前述建模方式将所有重边的数据合并在一条边中存储，当重边量级巨大时，对每条边的操作势必更加低效。HybriG采用的是合并同label的重边，而不是所有的重边，这仍是基于数据粒度的考虑。图7是合并相同label重边后Titan的图示例（在HBase边表中的重边数据未显示）。在实际应用场景中，经常需要根据具体的关系种类（label）来进行邻域点集查找，对于具体边数据的查询也常按label进行。因此合并相同label的重边设计可以使很多查询在Titan中就得到满足，不需要再涉及HBase边表。5 QueryAdapterQueryAdapter模块将图查询转化为对应Titan和HBase的查询，再将结果汇总返回。下面分别叙述其查询接口、查询实现以及查询优势。5.1查询接口我们在HybriG架构上实现了基本图查询接口，暴露给上层应用的仍是一张属性图。基本的图查询接口可分为如下几类：Ÿ 以点为中心的查询：获取某点邻接的点、获取某点的属性、获取某点邻接的边等；Ÿ 以边为中心的查询：获取某条边的端点、获取某条边的属性等；论文在线出版号No.60 黄权隆等：HybriG：一种高效处理大量重边的属性图存储架构 7Ÿ 从图中直接查询：查询符合某种条件的元素（点/边），其中的条件可以是label、限定返回集大小（limit）等。更详细的属性图查询接口，可以查看Blueprints中的定义。除了基本的属性图查询接口，HybriG还提供了重边的统计信息查询。比如查询两点间某种label的重边具体的边数、或者查询某个属性上的聚集信息（如MIN、MAX、AVG、SUM等），可以根据业务需要来定制具体统计的信息。比如通话关系所表示的边中包含了通话开始时间戳的属性。可以设置HybriG统计该类重边在该属性的最小值，从而可以查询两人最早的通话发生时间。在HybriG架构中，这些统计信息存储在Titan中的边上，因而可以快速返回结果，无需再对具体的边数据（存在HBase边表中）进行统计。区别于传统Titan图数据库，我们没有实现事务性的接口。因为业务场景可以规避对事务性的依赖，在富含重边的应用场景中，边集数据都是事件记录类型的数据，数据导入后就无需修改。而且数据导入可以分批定期执行，不会有多数据源写入导致的写-写冲突或读-写冲突。另外HybriG的数据分开存储在Titan和HBase两个数据库中，实现严格图8 HybriG在HBase中的数据表分为两张，左边为Titan转化成的数据表，右边为边表。当属性图富含重边时，Titan数据表不被影响，边表将是一张高而窄的表。事务的代价比较大，会带来显著的性能牺牲。如Google的Percolator[7]在BigTable上实现了分布式事务，但写性能有75%的牺牲。5.2查询实现查询的实现可分为两部分，一部分只依赖于Titan中的数据，另一部分需要联合Titan和HBase边表的数据来返回结果。下面分别叙述。5.2.1仅依赖Titan数据的查询在HybriG中，点集数据和邻接信息都存储在Titan中，因此只与点集相关的查询都可以直接转换为对Titan的查询，如点上属性的查询、查询给定点的邻域点集、在图中查询某种label的点等。对于重边的统计信息查询，其需要的统计结果都已在Titan的边中存储，故可以直接转换为对Titan边上的属性值查询。具体实现中需要维护一个映射关系作为元信息，以得知一个统计信息对应Titan边上的哪个属性。5.2.2关联Titan和HBase数据的查询当查询具体的边数据时，就需要关联Titan和HBase来实现查询。在HybriG架构中，HybriG_Edge=TitanEdgeID+HBaseRowData上式表示每条边对象的两部分组成，所有边集数据存储在HBase的边表中，每条边的数据占据一行，存储其所有属性，该行的行键是Titan中对应的边id拼接上该边的主键值。因此查询某条重边的数据，需要先在Titan中找到对应边的id，再在HBase边表中找到对应行的数据。下面以两点间边集查询为例阐述HybriG的实现。两点间边集查询是指给定两个点，查询它们之间满足某种条件的边。比如已经从邻域查询得知v1与v2相邻，现在想得到它们之间某种label的所有边。查询的伪代码见算法1.算法1. 两点间给定label的边集数据查询输入：点v1，点v2，eLabel输出：两点间的所有符合条件的边集数据1. e=v1.query().adjacent(v2).label(eLabel).limit(1).edges().next()2. IFe==nullTHEN3. RETURNnull4. ENDIF5. res=hbaseTable.scan(e.id,next(e.id))6. RETURNwrapEdges(res)算法1中，第1行查询两点间该label的边，并利用limit(1)修饰来加速。在HybriG架构中，Titan8 计算机学报 2017年只在这两点间存储该label的一条边，因此我们可以利用边的唯一性来加速查询。第2-4行，若在Titan中查询到该label的边不存在，则不需要再在HBase中检索。第5行根据Titan中的边id，在HBase的边表中通过Scan查询得到所有边的具体数据。e.id是一个字符串，伪代码中的next(e.id)表示同等长度的下一个字符串，即将字符串e.id中最后一个字符的值加一。比如e.id为“abbb”，则next(e.id)为“abbc”。HBase的Scan函数返回连续的若干行数据，接收的两个参数是行键范围的起始和结束点，是一个左开右闭的区间。用e.id和next(e.id)作为该区间的左右端点，即可查询到所有行键以e.id作为前缀的数据。最后第6行wrapEdges函数将这些数据转换为具体的边对象，每行一条边。5.3HybriG的查询优势5.3.1邻域点集相关查询的优势为了解释HybriG在图查询上的优势，图8展示了HybriG在HBase中的表结构，包括Titan自身的HBase数据表和HybriG特殊设计的边表。当属性图的重边数量爆炸性增长时，Titan的数据表并不会被影响，因为两点间同label的边至多只会存在一条，每个点的邻接表列数仍为不同label邻接的点数。另外，Titan中的边只存放统计信息，因此每个单元格（即每条边）的数据量实际很小。面对含有大量重边的属性图，各点的邻接表仍保持了列数和数据量上的精简。即使面对邻域点集查询的全表扫描，也能提供优异的性能。另一方面，得益于邻接表的精简，Titan的缓存因此可以存放更多点集数据。对于邻域点集相关查询，如多跳邻域（k-hop）查询、路径查询、局部聚集系数计算等，具体的实现往往由多个基本的邻域点集查询组成，缓存的命中率就显得尤为重要。传统的解决方案中使用Titan存储所有的重边，使得缓存中只能存储少量点集的数据，大部分空间被边集数据占据，而具体的边集数据在查询中并不相关。在HybriG架构中，Titan的缓存能充分保留更多的点集数据，从而进一步提高邻域点集相关查询的缓存命中率。综上，HybriG对邻域点集相关的查询具有很好的表现，后续的实验结果将展示具体的数据。5.3.2边集相关查询的优势在许多刑侦推演场景中，往往只需要查询两点间拥是否拥有某种label的边，而不需要查看具体各个重边的数据。比如得知两人之间有表示共同住宿酒店的边相连后，基本可以断定两人认识，领域专家可以在图中继续推演出其他相关的人，后续有需要再展开这条关系，查看具体的各条酒店住宿记录。HybriG架构为这种场景提供了便利，上述场景相当于在HybriG架构的Titan图中进行游走（Graphtraversal），当有需要时再展开某条边，在HBase边表中读回相应的边数据。对于边集数据的读取，HybriG将所有边的数据存储在HBase边表中，而且每条边占一行，这使得对边的检索是行级别的检索，即在表中查找一行。传统的解决方案将重边数据都存储在Titan中，边集数据存储于各点的邻接表，而每个点的邻接表在HBase数据表中占据一行，因此对边的检索是选定行后的列级别检索。HBase中行级别的检索要略优于列级别的检索，因此HybriG会略占优势。然而，HybriG对边的检索需要跨Titan和HBase两个系统，会多一次交互的开销。实验表明，这两方面功过相抵，HybriG的边集数据查询性能与Titan相差不大。HybriG架构在边集统计信息的查询或计算上会有很大优势。在HybriG架构中，Titan中某种label的边存在，代表原属性图中两点间拥有该label的边，具体的重边数据存储在HBase中的边表，而Titan中的边上的则存储了该label声明时设定的统计信息，如具体的重边数目、边上某个属性的最大最小值等。对于这些统计信息，可以直接在Titan中查询得到结果。6 DataLoaderDataLoder模块负责图数据的导入，包括点的导入和边的导入。在HybriG架构中，点集数据都存储在Titan中，故点集数据导入直接在Titan上完成。边集数据虽然存储在HBase中，但Titan中的对应边上存储了重边的统计信息，因此需要同时更新Titan和HBase，以保证二者数据的一致。下面详述边的数据导入，以及如何保证Titan和HBase的数据一致性。6.1边数据的高效导入在HybriG架构中，边的插入既要更新Titan，又要更新HBase边表。对于给定label的一条边数据，首先要查看Titan中两点间是否已有一条边表示这样的关系存在。若这样的边不存在，则将其创建。然后更新Titan边上的统计信息，再利用其边id将边的属性数据存入HBase中。算法2展示了上论文在线出版号No.60 黄权隆等：HybriG：一种高效处理大量重边的属性图存储架构 9述逻辑。第1行查询Titan中该label的边，由于至多只有一条，故可用limit(1)加速。第2-4行若这样的边不存在，则在Titan中添加一条边。第5行根据待插入的边数据来更新Titan中边上的统计信息。第6行提交对Titan的所有修改。第7行将边数据写入HBase边表中，行键为e.id拼接上边的主键。算法2. 插入一条边的伪代码输入：Titan图接口graph，HBase边表接口hbaseTable，点v1，点v2，edgeLabel，边数据realEdge1. e=v1.query().adjacent(v2).label(edgeLabel).limit(1).edges().next()2. IFe==nullTHEN3. e=v1.addEdge(v2,edgeLabel)4. ENDIF5. updateStats(e,realEdge.properties)6. graph.commit()7. hbaseTable.put(e.id+realEdge.primaryKey,realEdge.properties)传统的解决方案将所有重边存储在Titan中，边数据的导入逻辑只需要上述代码的第3、5、6行。HybriG架构中每条边的插入多加了一次查询操作（第1行），以及HBase边表的插入操作（第7行），带来了额外的时间开销。而且最耗时的也是这两步操作，分别要从底层存储读取数据以及持久化所有修改到底层存储中。如果有批量重边需要导入，这些开销可以让所有重边来平摊，即在数据导入时，对于两点间同label的重边作为一批来处理，这样就可以共享查询操作的结果，对Titan边上统计信息更新的持久化操作（commit）也只需进行一次。批量导入重边数据的伪代码如算法3所示。算法3. 重边数据的批量导入输入：Titan图接口graph，HBase边表接口hbaseTable，点v1，点v2，edgeLabel，重边数据集allRealEdges1. e=v1.query().adjacent(v2).label(edgeLabel).limit(1).edges().next()2. IFe==nullTHEN3. e=v1.addEdge(v2,edgeLabel)4. ENDIF5. FORrealEdgeINallRealEdgesDO6. updateStats(e,realEdge.properties)7. ENDFOR8. graph.commit()9. FORedgeINallRealEdgesDO10. hbaseTable.put(e.id+edge.pk,edge.properties)11. ENDFOR在算法3中，第1到8行是对Titan的更新，将两点间同label的重边作为一批处理，共享了对Titan的操作，从而平摊了额外的开销。另外第9到11行是对HBase边表的多次put操作，可以使用HBase的BulkLoading①技术来进行加速。6.2数据一致性在Titan的接口设计中，对图(graph)的初次操作将自动打开一个事务，执行graph.commit()时该事务提交，将事务里的修改持久化到底层存储中，Titan的事务保证了自身数据的一致性。HybriG架构由于把边数据的存储分开在Titan和HBase上，需要保证Titan和HBase上数据的一致性。比如Titan上关于重边的统计信息跟HBase边表的一致性，或者HBase边表里各行行键的边id部分跟Titan里的一致性。由于实现强一致性的代价过高，本架构保证的是Titan和HBase数据的最终一致性[8]，即系统保证在经过错误恢复后，数据最终会达到一致的状态。最终一致性足以满足应用场景的需求。由于只有边集数据是跨Titan和HBase存储的，下面讨论的都是边数据的导入。图9演示了边数据导入的三个步骤，第①步对应前述算法3中的第1~7行，更新Titan数据；第②步对应第8行，提交修改；第③步对应第9~11行，利用边id将边数据插入HBase边表中。对数据的持久化修改是第②③步，数据会出现不一致的原因是②③并不是原子的。如果②成功但是③失败了，即成功持久化了对Titan数据的修改，但对HBase边表的修改却失败了，则两边的数据出现不一致。失败的原因是多种多样的，比如程序内存溢出（OutofMemory）、网络中断、硬件故障等。图9边的数据导入分三步：①更新Titan数据；②提交Titan更改即graph.commit()；③将数据插入HBase边表中当数据导入程序在故障之后重启时，这种不一①http://hbase.apache.org/book.html#arch.bulk.load10 计算机学报 2017年致性需要被修复。该批次的边数据将会被重新导入，为了得知②是否已经成功，我们需要知道Titan中的数据是否已经被修改了。这可以利用Titan的事务原子性来实现：在②提交之前，往Titan中写入一个成功标志（可以用一个点或属性来表示），然后再提交。根据原子性，该标志被成功写入当且仅当Titan的更新都被持久化。这样当数据导入程序重启时，我们先查看该标志是否存在，便可得知②是否已经成功了。若其已成功，则跳过这一步，直接进行第③步。该过程的伪代码如算法4所示。算法4. 保证一致性的边集数据批量导入输入：graph，batchID，HBase边表hbaseTable，点v1，点v2，edgeLabel，allRealEdges，所有边的属性1. e=v1.query().adjacent(v2).label(edgeLabel).limit(1).edges().next()2. IFhasNotCompleted(graph,batchID)THEN3. IFe==nullTHEN4. e=v1.addEdge(v2,edgeLabel)5. ENDIF6. FORrealEdgeINallRealEdgesDO7. // 按需更新边上的统计信息8. ENDFOR9. markCompleted(graph,batchID)10. graph.commit()11. ENDIF12. FORedgeINallRealEdgesDO13. hbaseTable.put(e.id+edge.pk,properties)14. ENDFOR算法4中，第2行的函数hasNotCompleted判断给定的Titan图中是否存在给定批次的成功标志。若不存在则执行第3到10行更新Titan，其中第9行的markCompleted函数在Titan图中插入该批次的成功标志。值得一提的，我们在HBase中并没有放置成功标志。如果数据导入程序在第③步成功插入HBase数据后出现故障，则重启后还会将边集数据再次插入HBase中。但这是没有问题的，因为HBase边表中的数据不存在统计信息，因此不存在更新操作，所有操作都是新数据的插入操作。我们设置HBase的最大版本数为1，则多次插入同一内容到一个单元格，实际只保存一份，不会增加存储开销。7实验和分析在现有的公开数据集（比如LDBC①、SNAP②、LAW③）中，并没有富含重边的场景，这些图也不是属性图。富含重边的属性图普通存在于电信、金融、刑侦等行业中，数据是不公开的。由于实际的数据只能在相关部门内部查询，明略数据根据客户数据中统计出的特征构造测试用图，以支持SCOPA的开发与测试，验证HybriG架构的优秀性能。本组实验选用的图中有20万个顶点，48197700条边，平均度数为482，每个点平均与3.6个点相邻，两点间同label的重边的平均重数为134。实验对比的是直接将图存储在Titan中的传统方案以及将图存储在HybriG中的方案。实验环境为5台服务器组成的集群，每台机器安装Ubuntu14.04操作系统，物理配置均为一个IntelXeonE3-1220(3.10GHz)处理器、16GB内存、一个1Gbps网卡及一个4TBSATA接口硬盘。HBase部署在这5台机器上，每台机器的RegionServer设置最大堆内存为4GB。其中HBase版本为1.0.1.1，Titan版本为0.5.4。7.1邻域点集相关查询邻域点集查询是指查询给定点的邻接点集。许多图查询基于邻域点集查询实现，如k-hop点集查询、局部聚集系数查询、广度优先搜索等。下面叙述两个基于邻域点集查询的图查询实验。7.1.1k-hop点集查询k-hop点集查询即查询给定点在k跳能到达的点集。实验在测试图中随机抽取100个点作为起点，查询它们的多跳邻域点集，测试它们的平均查询时间。同时又对小邻域（邻域点数小于5）的点集和大邻域（邻域点数大于20）的点集进行了同样的实验。表1-3是Titan与HybriG的性能表现。表1 随机选100个点的k-hop查询平均耗时（毫秒）架构hops1 2 3 4Titan 13.65 72.97 446.34 2755.86HybriG 4.25 18.73 34.69 99.78表2 随机选100个小邻域点的k-hop查询平均耗时（毫秒）①LDBC,http://ldbcouncil.org②SNAP,http://snap.stanford.edu/data③LaboratoryforWebAlgorithmics,http://law.di.unimi.it/datasets.php论文在线出版号No.60 黄权隆等：HybriG：一种高效处理大量重边的属性图存储架构 11架构hops1 2 3 4Titan 8.67 31.08 179.47 1140.0HybriG 2.08 7.79 19.88 52.45表3 随机选100个大邻域点的k-hop查询平均耗时（毫秒）架构hops1 2 3 4Titan 17.79 110.34 721.25 4781.79HybriG 3.52 14.49 39.98 163.15随着跳数的增加，两系统的查询时间都呈指数增长。HybriG不管在1跳的初始值还是在增长的倍数上都远优于Titan。正如2.3节分析的，对某个点的邻域点集查询需要遍历该点的邻接表。当图中的重边数目巨大时，Titan受累于其庞大的邻接表，对邻域点集的查询速度大大降低。而HybriG由于极大简化了存储在Titan中的边数目，使得邻接表的数据量大大缩小，从而降低了邻接表的遍历耗时。7.1.2局部聚集系数计算局部聚集系数（LocalClusterCoefficient）是以点为中心的度量，表示其邻域子图的紧密程度，即邻居节点之间有多大比例有边相连。定义如下：| } , : ) , {( || } ) , ( , , : ) , {( |) (vvN w u w uE w u e N w u w uv LCCÎÎ Î=其中Nv为点v的邻域点集，E为图中的边集。上式表示邻域的点对集合中，有边相连的点对比例。由于 E w u e Î ) , ( 等价于uN wÎ ，分子部分可转化为åÎÇ = Î ÎvN uv u u vN N N w N w u w u | | } , , : ) , {(从上式可知，局部聚集系数的计算需要对邻域点集中的点再做一次邻域点集查询，因此其复杂度相当于2跳邻域点集查询。实验对比的是HybriG与直接将图存储在Titan中的传统方案。测试点集的抽取方式同7.1节，即小邻域（邻域点数小于5）的点集、随机采样点集和大邻域（邻域点数大于20）的点集，每个点集拥有100个点。图10是实验结果。图10计算100个点的局部聚集系数的平均耗时与k-hop查询一样，HybriG在局部聚集系数计算的性能上要远优与Titan，而且在大邻域点集上的优势更加明显。7.2边集相关查询下面介绍边集相关查询的两个实验结果。7.2.1节是两点间边集查询，在刑侦场景中，图中的一类顶点代表人，人之间的边代表两人的关系，比如共同出行记录、共同住宿酒店记录、通话记录等。当研判专家锁定两个嫌疑人后，需要查询两人间的关系数据，即为两点间边集查询。7.2.2节是邻接边集查询，在刑侦场景中，锁定嫌疑人后要查看其某种类型的关系数据，即为邻接边集查询。这两种查询的图查询语句是不同的，前者限定了边的两个邻接点，后者只给定了边一个端点，侧重于限定label。使用Blueprints图查询接口，两点间边集查询的示例语句如下：v1.query().adjacent(v2).edges()邻接边集查询的示例语句如下：v.getEdges(Direction.BOTH,eLabel)其中v1、v2、v是顶点，eLabel是边的一种label，Direction.BOTH是常量，代表边的方向可以是入边或出边。7.2.1两点间边集查询实验测试的是给定两个点和一个label，查询两点间该label的所有边。在图中随机抽取100个有边相连的点对，实验测试查询这些边的耗时。12 计算机学报 2017年图11 查询100个点对间所有边的总耗时图11统计了两种系统的时间对比，两种方案的查询耗时非常接近。HybriG的存储层基于Titan和HBase实现，对边集的查询先要在Titan里查询边id，再在HBase的边表中查询具体的边，因此时间开销分两部分（详见5.1节）。图中展示了HybriG查询时间的两部分组成。两种方案的耗时相近主要有两方面的原因。一方面，HybriG检索边集数据需要在Titan和HBase这两个数据库中进行查询，且这两个查询不能并行。传统方案只需要在Titan中查询，HybriG多加了一轮查询的时间开销。然而，这部分的时间开销并不是很大。Titan的数据表本身也存储在HBase中，HybriG的查询实际上只是HBase中的跨表查询。跨表查询能共用HBase的一些缓存信息，如HMaster、RegionServer的位置信息、HBase中Root表和Meta表的信息等。不过尽管只是跨表查询，在这方面HybriG还是引入了时间开销。但另一方面，HybriG对边集的查询是转化为HBase边表中的行级别检索（详见5.1节）。而将图存储在Titan中的方案，对边集的查询实际是转化为HBase数据表中选定行后的列级别检索。当图中含有大量重边时，前者是在一张高窄（tall-narrow）表中查找连续的几行，后者是在一张扁宽（flat-wide）表中选定一行后查找连续的几列，前者的性能会略优一些。因此在这方面HybriG略优。7.2.2邻接边集查询实验测试的是给定一个点，查询其某种label的所有边。点集的抽取方式同7.1节，即小邻域（邻域点数小于5）的点集、随机采样点集和大邻域（邻域点数大于20）的点集，每种点集抽取1000个点。图12展示的是两种系统的查询时间，以及查询耗时中具体的时间组成，其中HybriG的查询时间分为Titan中的查询耗时和HBase中的查询耗时两部分。当边集规模增大时，HybriG在Titan中的查询耗时并没有显著增加，而在HBase边表中的查询耗时增长的幅度也没有传统方案中的Titan大。图12查询1000个点给定label的所有边总耗时7.3边数据的导入速度关于边的数据导入速度，我们对不同规模的图进行了测试。对比直接将图存储在Titan以及将图存储在HybriG的两种方案。我们基于MapReduce[9]开发了分布式的导入程序。表5是边数据导入时间的统计：表5 边集数据的批量导入耗时测试图号点数 边数重边的重数Titan导入时间HyBriG导入时间1 50000 23786800 100 30min 14min2 200000 48197700 100 45min 16min3 200000 481977000 1000 9h26min 1h24min可以看到，在所有测试用图中，HybriG对边集数据的导入拥有更高的速度。这主要有两方面的原因：一是HybriG对HBase边表的数据导入使用了HBase的BulkLoading技术。二是Titan对新增的点和边都会分配一个全局唯一的id（这也是Titan没有实现HBaseBulkLoading的原因），HybriG大大减小了自身Titan中的边数目，从而节省了id分配的时间开销。8相关工作图数据分析与处理是大数据背景下的一大应用分支[10]，大数据背景下的图处理系统可以分为图计算框架和图数据库两大类。图计算框架旨在高效地进行全图量级的并行计算，如计算PageRank[11]、社区发现[12]（Community论文在线出版号No.60 黄权隆等：HybriG：一种高效处理大量重边的属性图存储架构 13Detection）、子图匹配[13]等，提供的是对OLAP（OnlineAnalyticalProcessing）的支持。这类系统中，Pregel[14]、GraphLab[15]、PowerGraph[16]支持BSP[17]模型的计算，对图数据进行特定的分割，使得集群中的机器可以在内存中计算分区的数据，再通过交互完成全量数据的计算。上述系统中，Pregel没有开源，GraphLab和PowerGraph都需要单独部署，无法有机地融入已有的大数据生态系统中，需要导出数据以供计算。GraphX[18]解决了这个问题，其是基于分布式内存计算框架Spark[19]实现的图计算引擎，使得图计算可以融入整个数据流处理的框架。相对于分布式计算框架，GraphChi[20]则追求在单机完成大规模图数据的计算问题。在图计算领域还有许多研究旨在提高图计算框架在特定问题的处理性能，如[21-25]等。学术界对图计算的研究热情普遍高涨。图数据库专注于图数据的管理，提供高效的图遍历查询（graphtraversal）。图数据模型则是指图数据库如何以图的方式对数据进行抽象[4]，应用较广泛的图数据模型有RDF①模型和属性图模型。RDF全称为ResourceDescriptionFramework，是由W3C制定的知识描述标准，使得按RDF表示的不同数据源可以进行数据交换或合并。RDF中的数据单元是由主语、谓语、宾语组成的三元组，可以直接对应为图上的一条边，因此将RDF模型归类为图数据模型。常见的RDF存储有Jena②、AllegroGraph③等。当今的图数据库大都采用属性图模型设计[26]，如DEX[27]、GraphChi-DB[28]、Neo4j、Titan等，其中DEX和GraphChi-DB都只是单机数据库，Neo4j的开源版本也是单机的，只适合处理中等规模的图。Titan的底层实现了可插拔的存储接口，可部署在HBase、Cassandra或BerkeleyDB之上，因此可以很好地与Hadoop集群结合，组成统一的数据处理框架。然而，现有的图数据库都没有考虑含有大量重边的属性图应用场景。HybriG架构填补了这个空白，为含有大量重边的属性图应用场景提供了一种可行的解决方案。① RDF 1.1 Concepts and Abstract Syntax,https://www.w3.org/TR/rdf11-concepts2017,3,29②ApacheJena,http://jena.apache.org2017,3,29③AllegroGraph,http://franz.com/agraph/allegrograph2017,3,299总结本文提出了一种基于Titan和HBase的复合存储架构——HyBriG，可以高效处理含有大量重边的属性图。相比于传统图数据库Titan的实现，HyBriG在处理大量重边时拥有更优异的查询性能，在数据导入方面也有不错的表现。在获得高性能的同时，所带来的牺牲就是简化了对事务性的支持。然而，含有大量重边的许多应用场景并不需要很强的事务性支持，HybriG架构提供了最终一致性，足以满足这些场景的应用需求。在实践中，明略数据的关联数据分析平台——SCOPA基于HybriG架构开发了核心存储部件。验证了HybriG架构在处理大量重边时的优异性能。参考文献[1] ArodriguezM,NeubauerP.Constructionsfromdotsandlines.BulletinoftheAmericanSocietyforInformationScienceandTechnology,2010,36(6):35–41.[2] LiuQiao,LiYang,DuanHong,LiuYao,QinZhiGuang.KnowledgeGraphconstructiontechniques.JournalofComputerResearchandDevelopment,2016,53(3):582-600(刘峤,李杨,段宏,刘瑶,秦志光. 知识图谱构建技术综述. 计算机研究与发展,2016,53(3):582-600)[3] ChangF,DeanJ,GhemawatS,etal.Bigtable:adistributedstoragesystemforstructureddata.AcmTransactionsonComputerSystems,2008,26(2):205--218.[4] Angles R, Gutierrez C. Survey of graph database models. ACMComputingSurveys,2008,40(1):1-39.[5] LakshmanA,MalikP.Cassandra:adecentralizedstructuredstoragesystem.AcmSigopsOperatingSystemsReview,2010,44(2):35-40.[6] WebberJ.AprogrammaticintroductiontoNeo4j.//ProceedingsoftheConferenceonSystems,Programming,andApplications:SoftwareforHumanity,Tucson,USA,2012,1(1):217-218[7].PengD,DabekF.Large-scaleincrementalprocessingusingdistributedtransactionsandnotifications.//ProceedingsoftheOperatingSystemsDesignandImplementation.Vancouver,Canada,2010:251-264.[8].VogelsW.Eventuallyconsistent.CommunicationsofTheACM,2009,52(1):40-44[9] DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters.//ProceedingsoftheOperatingSystemsDesignandImplementation.SanFrancisco,USA,2004:10-10[10]CuiBin,MeiHong,OoiB.C,Bigdata:thedriverforinnovationindatabases.NationalScienceReview,2014,1(1):27-30[11]PageL,BrinS,MotwaniR,WinogradT.Thepagerankcitationranking:Bringingordertotheweb.Stanford,CA,USA:StanfordUniversity14 计算机学报 2017年InfoLab,TechnicalReport:66,1998.[12] Leskovec J, LangK. J, DasguptaA, MahoneyM. W. Communitystructure inlarge networks: Natural cluster sizes andthe absenceoflargewell-definedclusters.InternetMathematics,2009,6(1),29–123.[13]ChibaN,NishizekiT.Arboricityandsubgraphlistingalgorithms. SIAMJournalonComputing,1985,14(1):210-223.[14]MalewiczG,AusternMH,BikAJ,etal.Pregel:asystemforlarge-scalegraphprocessing.//ProceedingsoftheACMSIGMODInternationalConferenceonManagementofData.Indianapolis,USA,2010:135-146.[15]LowY,GonzalezJ,KyrolaA,etal.GraphLab:ANewFrameworkForParallelMachineLearning.//ProceedingsoftheUncertaintyinartificialintelligence,CatalinaIsland,USA.2010:340-349.[16]GonzalezJ,LowY,GuH,etal.PowerGraph:distributedgraph-parallelcomputationonnaturalgraphs.//ProceedingsoftheOperatingsystemsdesignandimplementation.Hollywood,USA,2012:17-30.[17]ValiantLG.Abridgingmodelforparallelcomputation.CommunicationsofTheACM,1990,33(8):103-111.[18]GonzalezJ,XinR,DaveA,etal.GraphX:graphprocessinginadistributeddataflowframework.//ProceedingsoftheOperatingsystemsdesignandimplementation,Broomfield,USA,2014:599-613.[19]ZahariaM,ChowdhuryM,FranklinMJ,etal.Spark:clustercomputingwithworkingsets.//ProceedingsoftheWorkshoponHotTopicsinCloudComputing. Boston,USA,2010:10-10.[20]KyrolaA,BlellochGE,GuestrinC,etal.GraphChi:large-scalegraphcomputationonjustaPC.//ProceedingsoftheOperatingsystemsdesignandimplementation.Hollywood,USA,2012:31-46.[21]Xu Ning, Chen Lei, Cui Bin. LogGP: a log-based dynamic graphpartitioning method. //Proceedings of the Vldb Endowment, 2014,7(14):1917-1928.[22]Shao Yingxia, Cui Bin, Chen Lei. Parallel subgraph listing in alarge-scale graph. //Proceedings of the international conference onmanagementofdata.Snowbird,USA,2014:625-636.[23]Shao Yingxia, Chen Lei, Cui Bin. Efficient cohesive subgraphsdetectioninparallel. //Proceedings of theinternational conferenceonmanagementofdata.Snowbird,USA,2014:613-624.[24]Xu Ning, Cui Bin, Chen Lei. Heterogeneous Environment AwareStreamingGraphPartitioning. IEEETransactions onKnowledge andDataEngineering,2015,27(6):1560-1572.[25]ShaoY,CuiB,MaL,etal.PAGE:APartitionAwareEngineforParallelGraphComputation.IEEETransactionsonKnowledgeandDataEngineering,2015,27(2):518-530.[26] Angles R. AComparison of Current Graph Database Models. //Proceedings of the International conference on data engineering.Arlington,USA,2012:171-177.[27]Martinez-BazanN.,Muntes-MuleroV.,Gomez-VillamorS.,NinJ.,Sanchez-MartiınezM.-A.,Larriba-PeyJ.-L.Dex:high-performanceexplorationonlargegraphsforinformationretrieval.//Proceedingsofthe16thACMconferenceoninformationandknowledgemanagement.Lisbon,Portugal,2007:573–582.[28]KyrolaA,GuestrinC.GraphChi-DB:Simpledesignforascalablegraphdatabasesystem–onjustaPC.ComputingResearchRepository,2014,abs/1403.0701:1-12HUANG Quan-Long, born in1991, Master Candidate. His researchinterests focus ondata warehouse anddistributedstorage.HUANGYan-Xiang, bornin1990,Ph.D. candidate.Herresearch interests focus on social media analysis, real-timerecommendation.SHAOYin-Xia, bornin1988, Ph.D., Postdoctoral. Hisresearchinterestsfocusonlarge-scalegraphanalysis.MENGJia, bornin1982, Master, Systemarchitect ofMiningLamp. His research interests focus on distributedstorage.RENXin-Qi, bornin1984, Master, Product DirectorofMiningLamp. His research interests focus on Big Datacomputingandvisualization.CUI bin, bornin1975, Ph.D., professor. His researchinterests focus ondatabase, social media analysis andlargescalegraphmining.FENG Shi-Cong, born in 1973, Ph.D., CTO ofMiningLamp.HisresearchinterestsfocusonBigDataanalysisanddatamining.BackgroundThepast decadeshavewitnessedthemassivegrowthofInternet.Vastamountofgraphdatawasproducedbytheboomof social network, e-commerceandonlineeducation. Systemslike Pregel, GraphLab and PowerGraph are proposed fordistributedgraphcomputing. GraphdatabaseslikeNeo4j andTitanaredevelopedfor management of propertygraph. Thepropertygraphisadirected, labeledgraphwithmulti-edges.Vertices and edges can be associated with any number of论文在线出版号No.60 黄权隆等：HybriG：一种高效处理大量重边的属性图存储架构 15properties. Sinceit canrepresent graphdatainmost scenarios,the property graph model has numerous applications inindustry. However, traditional graph databases encountersignificant performancedegradationwhenthegraphcontainslargeamount of multi-edges. Wereveal thecauseof this inTitan, anopensource distributedgraphdatabase whichhasattracted wide attention in industry. Titan stores graphs inadjacencylistformat,whereagraphisstoredasacollectionofverticeswiththeiradjacencylists. Eachentryoftheadjacencylist stores anedge. Whenqueryingabout adjacent vertices,Titanhastolookthroughtheentireadjacencylistofthesourcevertex, whichhurts theperformancewhenthemulti-edgesetgrows explosively. For highlevel queries that are basedonadjacent vertices query, e.g. path queries, local clustercoefficientqueriesetc.,theperformancelosswillbeworse.WeproposeHybriG,abetterdistributedarchitecturebasedonTitanandHBaseforthisscenario. HybriGstoresthevertexdata andgraphstructure inTitan, the edge data inHBase,respectively. HybriGkeepsaconciseadjacencylist about thegraphstructure, whichhelps togainanorder of magnitudeimprovement inexecutionof adjacent vertices basedqueriesandbatchloadingofedgeset. Inthisarticle,weintroducehowHybriGimplements its storagelayer uponTitanandHBase,andhowHybriGtransforms graphoperations intoTitanandHBaseAPIs. Besides, HybriGachieves highperformanceforinsertingbatchof graphdata. Furthermore, weintroducetheimplementationofdataconsistencybetweenTitanandHBase.Extensive experiments have been conducted to showtheoutstandingperformanceofHybriG.Thisworkis supportedbytheNational Natural ScienceFoundationofChinaunderGrantNos. 61572039, theNationalBasicResearchProgram(973Program) ofChinaunderGrantNo. 2014CB340405, andtheShenzhenGovResearchProjectunderGrantNo.JCYJ2015101409350532.