基于圖計算的大數(shù)據(jù)分析系統(tǒng)

1、基于圖計算的高性能大數(shù)據(jù)分析系統(tǒng) 技術創(chuàng)新，變革未來大數(shù)據(jù)是指無法在一定時間內(nèi)用常規(guī)軟件工具對其 內(nèi)容進行抓取、管理和處理的數(shù)據(jù)集合（維基百科 定義）大數(shù)據(jù) = “海量數(shù)據(jù)”+“復雜類型的數(shù)據(jù)”大數(shù)據(jù)的特性（ Volume，Variety，Velocity）數(shù)據(jù)量大：PB、TB、EB、ZB級別的數(shù)據(jù)量種類多：包括文檔、視頻、圖片、音頻、數(shù)據(jù)庫、層次狀數(shù)據(jù)等速度快：數(shù)據(jù)生產(chǎn)速度很快；要求對數(shù)據(jù)處理和I/O速度很快2大數(shù)據(jù)對分析平臺的挑戰(zhàn)主流大數(shù)據(jù)平臺 - Hadoop基于內(nèi)存的大數(shù)據(jù)分析平臺 -SparkSpark的局限性-數(shù)據(jù)模型層面大數(shù)據(jù)應用:圖遍歷（BFS）5RDD部分數(shù)據(jù)更每新Spark

2、：只讀數(shù)據(jù)對象次細粒度的數(shù)據(jù)更新時，間片由段 于spark基于粗粒數(shù)度據(jù)RDD只讀的數(shù)據(jù)對象模型，需要RDD變換，即有大量數(shù)據(jù)的復制，導致處理效率 不高。.Spark的局限性-實現(xiàn)層面Spark基于Scala語言，運行在JVM上內(nèi)存表示冗余，占用內(nèi)存大內(nèi)存分配與回收開銷大GraphLab在某些任務上比Spark快10倍Gonzalez, Joseph E., et al. Graphx: Graph processing in a distributed dataflowframework. Proceedings of OSDI. 2014.圖計算 折衷的大數(shù)據(jù)分析平臺可讀寫的數(shù)據(jù)容錯困難不

3、支持自動負 載平衡只讀數(shù)據(jù)集容錯方便，擴展 性好自動負載平衡性能擴展性MPI，OpenMPGraphLab,GeminiMapReduce，Spark可讀寫的數(shù)據(jù)容錯性能較好一定程度的自動 負載平衡圖數(shù)據(jù)的重要意義圖能夠表達豐富的數(shù)據(jù)和關系網(wǎng)絡連接網(wǎng)頁鏈接社交關系蛋白質(zhì)交互人與人，人與公司，人與產(chǎn)品圖的計算與分析PageRank最短路徑連通分支極大獨立集最小代價生成樹Bayesian Belief Propagation代表性圖計算系統(tǒng)2010201120122013Pregel SIGMOD10PowerGraph OSDI12Galois SOSP13GraphLabUAI10Distri

4、buted GraphLab VLDB12Ligra PPoPP132014PowerLyra EuroSys152015Polymer PPoPP152016Gemini OSDI16PowerGraph/PowerLyra的問題計算性能低，處理小圖時8臺機器性能還不如單機系統(tǒng)twitter-2010數(shù)據(jù)集上，20 輪PageRank迭代(41.7M 結(jié)點, 1.47B 邊)性能數(shù)據(jù)對比14結(jié)點數(shù) 系統(tǒng)1Galois8PowerLyra運行時間 (s)19.326.9指令數(shù)482G6.06T內(nèi)存訪問數(shù)23.4G87.2G通信量(GB)-38.1IPC0.4140.655L3 缺失率49.7%

5、54.9%CPU 利用率96.8%68.4%瓶頸在計算！局部性差CPU利用率低twitter-2010數(shù)據(jù)集上，20 輪PageRank迭代(41.7M 結(jié)點, 1.47B 邊)分布式計算開銷計算不夠優(yōu)化網(wǎng)絡帶寬遠遠沒有飽和 執(zhí)行了更(1多00指Gb令ps和) 更(38.1*8/2多/2訪6.存9/8=0.708Gbps)分布式圖計算系統(tǒng)Gemini在高效性的基礎上支持擴展性避免沒有必要的“分布式”副作用優(yōu)化圖的劃分與計算設計理念的變化以計算性能為中心的分布式系統(tǒng)分布式系統(tǒng)有快速的通信網(wǎng)絡計算可以與通信重疊效率優(yōu)化自適應push-pull轉(zhuǎn)換層次化的分塊劃分擴展性優(yōu)化局部性感知的分塊基于分塊的

6、任務竊取稠密-稀疏雙模式的計算模型圖計算中的活躍結(jié)點數(shù)在不同迭代步驟時不同活躍結(jié)點多，適合稠密模式活躍結(jié)點少，適合稀疏模式bcsparseSignalasparseSlotadenseSignalzxydenseSlotzcommunicationcomputationmastermirror雙模式: 以BFS 為例 (1)170123491st iterationActive edge set|Active edge set| / |E| threshold Dense mode Pull operationsVertices pulling along in-edgesContention

7、-free updatingLimited selective scheduling分布式雙模式計算190125634789Node0Node1Node1Node0分布到兩個節(jié)點20138025647901234567902485679MasterMirrorInter-node message passingGemini的分布式push21Node0012345679Node102485679Masters message mirrors, who update their local neighborsGemini的分布式Pull22Node0012345679Node102485679M

8、irrors pull updates from neighbors, then message masters基于chunk的圖劃分方法傳統(tǒng)圖劃分方法代價高：metis劃分效果差：hash基于chunk的劃分利用數(shù)據(jù)集中的局部性為什么做chunk劃分?chunk劃分保留了局部性! 很多實際圖中都存在局部性E.g., WebGraphWWW 04, BLPWSDM 13圖結(jié)點按“語義”排序241 The Anatomy of the Facebook Social GraphFacebook Country Adjacency Matrix1UK Web (2005) Adjacency Ma

9、trix結(jié)點沒有排序時存在可接受的預處理方法E.g., BFSAlgorithms 09, LLPWWW 11Chunk的其它好處不需要轉(zhuǎn)換vertex IDs (global local)大大縮小了partition信息的維護開銷O(p) chunk 邊界結(jié)點數(shù)據(jù)更容易管理在共享內(nèi)存中分配連續(xù)的數(shù)據(jù)可以在多個層次遞歸地使用25Touched局部性感知的Chunking如何分塊?260LLCChunk size affects random access efficiency!Gemini 同時考慮了結(jié)點和邊邊數(shù): 處理的工作量結(jié)點數(shù)局部性混合度量: |Vi| + |Ei| 現(xiàn)在設為 8(p-

10、1)Balancing by edges?|V|nodesocket27coreWork partitioning within socketclusterPer-node partitionPer-socket partition w. NUMA-aware placementData partitioning till socket-levelPer-core work chunkMini-chunk for work stealingLocality-awareFine grain (64-vertex)多層次分塊劃分和任務竊取性能評估28Graph|V|E|enwiki-20134,2

11、06,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-結(jié)點集群Intel Xeon E5-2670 v3 (12-core CPU), 30MB L3 cache 2 sockets sharing 128 GB RAM (DDR4 2133MHz)Network: Mellanox Infiniband EDR 100Gbps測試

12、程序輸入圖PageRank (PR) (20 iterations)Connected Components (CC)Single-Source Shortest Paths (SSSP)Breadth-First Search (BFS)Betweenness Centrality (BC)單結(jié)點效率29“*” uses different algorithms.ApplicationLigraGaloisGeminiPR21.219.312.7CC6.513.59*4.93SSSP2.813.333.29BFS0.3470.5280.468BC2.453.94*1.88Runtime in

13、 seconds (twitter-2010)NUMA-aware memory accessesMore iterationsMore instructionsSystemLigraGeminiRemote access ratio50.1%9.10%L3 cache miss rate52.6%40.1%Average access latency183ns125nsMemory reference profiling results基于chunk的分塊方法和基于Hash的劃分方法30分布式push/pull效果3110.750.50.250020PageRank050

14、.6076SparseDense00.00172SparseDenseRuntime of each iteration using sparse / dense mode (uk-2007-05)Connected ComponentsSingle-Source Shortest PathsSparseDense“mis-predictions”: 2 out of 76 for CC and 5 out of 172 for SSSPRuntime(s)Iteration #結(jié)點內(nèi)負載平衡322.521.510.50uk-2007-05Speedups of diff

15、erent intra-node load balancing strategies over static scheduling (PR)twitter-2010static schedulingbalanced partitionstealingstealing w/ balanced partition分布式系統(tǒng)Gemeni 性能測試環(huán)境8臺雙路Xeon E5- 2670V3 4 (hypert.) vCPU cores128 GB memoryInfiniband EDR(100Gbps)與PowerLyra相比， 加速比約為18.7X與GraphX相比， 加速比約為80- 300X內(nèi)存占用情況Gemini的內(nèi)存占用約為PowerGraph的