基于图计算的大数据分析系统

基于图计算的高性能大数据分析系统技术创新，变革未来大数据是指无法在一定时间内用常规软件工具对其内容进行抓取、管理和处理的数据集合（维基百科定义）大数据

=“海量数据”+“复杂类型的数据”大数据的特性（

Volume，Variety，Velocity）数据量大：PB、TB、EB、ZB级别的数据量种类多：包括文档、视频、图片、音频、数据库、层次状数据等速度快：数据生产速度很快；要求对数据处理和I/O速度很快2大数据对分析平台的挑战主流大数据平台

-

Hadoop基于内存的大数据分析平台

-SparkSpark的局限性-数据模型层面大数据应用:图遍历（BFS）5RDD部分数据更每新Spark：只读数据对象次细粒度的数据更新时，间片由段

于spark基于粗粒数度据RDD只读的数据对象模型，需要RDD变换，即有大量数据的复制，导致处理效率不高。...Spark的局限性-实现层面Spark基于Scala语言，运行在JVM上内存表示冗余，占用内存大内存分配与回收开销大GraphLab在某些任务上比Spark快10倍Gonzalez,JosephE.,etal."Graphx:Graphprocessinginadistributed

dataflowframework."ProceedingsofOSDI.

2014.图计算

–

折衷的大数据分析平台可读写的数据容错困难不支持自动负载平衡只读数据集容错方便，扩展性好自动负载平衡性能扩展性MPI，OpenMP GraphLab,Gemini MapReduce，Spark可读写的数据容错性能较好一定程度的自动负载平衡图数据的重要意义图能够表达丰富的数据和关系网络连接网页链接社交关系蛋白质交互人与人，人与公司，人与产品图的计算与分析PageRank最短路径连通分支极大独立集最小代价生成树BayesianBelief

Propagation…代表性图计算系统2010201120122013PregelSIGMOD’10PowerGraphOSDI’12GaloisSOSP’13GraphLabUAI’10DistributedGraphLabVLDB’12LigraPPoPP’132014PowerLyraEuroSys’152015PolymerPPoPP’152016GeminiOSDI’16PowerGraph/PowerLyra的问题计算性能低，处理小图时8台机器性能还不如单机系统twitter-2010数据集上，20轮PageRank迭代(41.7M

结点,

1.47B

边)性能数据对比14结点数系统1Galois8PowerLyra运行时间

(s)19.326.9指令数482G6.06T内存访问数23.4G 87.2G通信量(GB)-38.1IPC0.4140.655L3

缺失率49.7%54.9%CPU

利用率96.8%68.4%瓶颈在计算！局部性差CPU利用率低twitter-2010数据集上，20

轮PageRank迭代(41.7M

结点,

1.47B

边)分布式计算开销计算不够优化网络带宽远远没有饱和执行了更(1多00指Gb令ps和)

更(38.1*8/2多/2访6.存9/8=0.708Gbps)分布式图计算系统Gemini在高效性的基础上支持扩展性避免没有必要的“分布式”副作用优化图的划分与计算设计理念的变化以计算性能为中心的分布式系统分布式系统有快速的通信网络计算可以与通信重叠效率优化自适应push-pull转换层次化的分块划分扩展性优化局部性感知的分块基于分块的任务窃取稠密-稀疏双模式的计算模型图计算中的活跃结点数在不同迭代步骤时不同活跃结点多，适合稠密模式活跃结点少，适合稀疏模式bcsparseSignalasparseSlotadenseSignalzxydenseSlotzcommunicationcomputationmastermirror双模式:

以BFS

为例

(1)170123491st

iterationActiveedge

set|Activeedgeset|/|E|<

threshold

Sparse

mode

Push

operationsActivevertex

set57Selective

scheduling:onlyaccess

out-edges68fromactive

verticesDualmodeupdatesproposedinshared-memorysystems(Ligra[PPoPP

’13])Locks/atomic

operationsrequiredforcorrectnessofconcurrent

updates双模式:

以BFS

为例

(2)1801256347892nd

iterationActiveedge

set|Activeedgeset|/|E|>

threshold

Dense

mode

Pull

operationsVerticespullingalong

in-edgesContention-free

updatingLimitedselective

scheduling分布式双模式计算190125634789Node0Node1Node1Node0分布到两个节点20138025647901234567902485679MasterMirrorInter-nodemessage

passingGemini的分布式push21Node0012345679Node102485679Mastersmessagemirrors,whoupdatetheirlocal

neighborsGemini的分布式Pull22Node0012345679Node102485679Mirrorspullupdatesfromneighbors,thenmessage

masters基于chunk的图划分方法传统图划分方法代价高：metis划分效果差：hash基于chunk的划分利用数据集中的局部性为什么做chunk划分?chunk划分保留了局部性!–

很多实际图中都存在局部性•E.g.,WebGraph[WWW’04],BLP[WSDM

’13]图结点按“语义”排序241TheAnatomyoftheFacebookSocial

GraphFacebookCountry

AdjacencyMatrix1 UKWeb(2005)Adjacency

Matrix结点没有排序时存在可接受的预处理方法E.g.,BFS[Algorithms09],LLP[WWW’11]Chunk的其它好处不需要转换vertex

IDs

(global

local)大大缩小了partition信息的维护开销O(p)

chunk

边界结点数据更容易管理在共享内存中分配连续的数据可以在多个层次递归地使用25Touched局部性感知的Chunking如何分块?260LLCChunksizeaffectsrandomaccess

efficiency!Gemini

同时考虑了结点和边边数:

处理的工作量结点数局部性混合度量:

⍺·|Vi|

+

|Ei|⍺

现在设为

8(p-1)Balancingby

edges?|V|nodesocket27coreWorkpartitioningwithinsocketclusterPer-node

partitionPer-socketpartitionw.NUMA-aware

placementDatapartitioningtillsocket-levelPer-corework

chunkMini-chunkforwork

stealingLocality-awareFinegrain(64-vertex)多层次分块划分和任务窃取性能评估––28Graph|V||E|enwiki-20134,206,785101,355,853twitter-201041,652,3301,468,365,182uk-2007-05105,896,5553,738,733,648weibo-201372,393,4536,431,150,494clueweb-12978,048,09842,574,107,469平台:8-结点集群IntelXeonE5-2670v3(12-coreCPU),30MBL3cache2socketssharing128GBRAM(DDR4

2133MHz)Network:MellanoxInfinibandEDR

100Gbps测试程序 • 输入图PageRank(PR)(20

iterations)ConnectedComponents

(CC)Single-SourceShortestPaths

(SSSP)Breadth-FirstSearch

(BFS)BetweennessCentrality

(BC)单结点效率29“*”usesdifferent

algorithms.ApplicationLigraGaloisGeminiPR21.219.312.7CC6.513.59*4.93SSSP2.813.333.29BFS0.3470.5280.468BC2.453.94*1.88Runtimeinseconds

(twitter-2010)NUMA-awarememory

accessesMore

iterationsMore

instructionsSystemLigraGeminiRemoteaccess

ratio50.1%9.10%L3cachemiss

rate52.6%40.1%Averageaccess

latency183ns125nsMemoryreferenceprofiling

results基于chunk的分块方法和基于Hash的划分方法30分布式push/pull效果3110.750.50.250020PageRank00.150.30.450.6076SparseDense00.050.10.150.20172Sparse DenseRuntimeofeachiterationusingsparse/densemode

(uk-2007-05)Connected

Components Single-SourceShortest

PathsSparseDense“