大规模图数据管理与分析 课件 08-图计算系统

大规模图数据管理与分析图计算系统第八章2认识图计算基于传统大数据组件的图计算实现针对图计算的点中心编程框架基于图数据库的图计算小结本章概览3认识图计算Part14图计算的基本概念广义图计算任何基于图数据模型的计算问题都处于图计算的范畴之内学术界和工业界提到的图计算问题往往并非广义图计算狭义图计算缺乏共识性定义图计算的共同点：全局性定义在全图点集或边集上的结果数据：PageRank，Betweenness，图染色，置信度定义在全图拓扑结构上的结果数据：WCC，MST，图聚类，图分割，K-Core图计算特点计算密集型侧重分析挖掘，而非查询匹配图计算系统5图计算的实现概述基于大数据组件大数据生态的支持，降低研发成本缺乏对图特性的聚焦优化，性能低如：MapReduce，Spark基于图计算的系统点中心编程框架，易用高效如：Pregel、GraphLab等在图数据库上设计图计算以图数据库作为数据后端通过基础数据管理接口进行数据加载后计算如：gStore图计算系统6基于大数据组件的图计算Part27基于分布式KV的图计算计算框架图数据规模庞大，用分布式KV组件进行组织图数据基于分布式KV来加载计算时数据，计算后基于写接口写回特点解决了单机无法容纳大规模图数据的问题效率低效，I/O和通信的代价过高图计算系统8基于MapReduce框架的图计算MapReduce框架简洁且功能强大支持自动并行化与分布式处理为图计算提供了一种可行途径图计算系统9MapMapMap

ReduceReduce输入数据输出数据基于MapReduce框架的图计算理解MapReduce：计算WordCount计算一个大规模文档集中每个单词的词频图计算系统10基于MapReduce框架的图计算理解MapReduce：矩阵向量乘法计算一个n维方阵M同一个n维相邻v的乘积：M*v图计算系统11基于MapReduce框架的图计算基于MapReduce计算PageRank图计算系统12基于MapReduce框架的图计算Pegasus

[Kangetal.,ICDM09]基于MapReduce实现的开源图计算系统图算法表示成重复的矩阵向量乘法计算Pegasus通过MapReduce的矩阵向量乘法以实现各种图算法矩阵向量乘法：分解为三个步骤，每个步骤用MapReduce轻松计算图计算系统13•Combine2:

𝑚𝑖𝑗与𝑣𝑗相乘

•CombineAll:

对同一行的结果累加，得到𝑣’𝑗

•Assign:

将𝑣’𝑗写入𝑣’

向量中基于MapReduce框架的图计算Pegasus实现PageRankPageRank表示成矩阵向量乘法图计算系统14①基本公式②带阻尼系数公式基于MapReduce框架的图计算Pegasus实现PageRank基于矩阵向量乘法图计算系统15③矩阵向量乘法基于MapReduce框架的图计算Pegasus实现PageRank分解三步骤图计算系统16Combine2:;.

基于MapReduce框架的图计算Pegasus实现连通分量计算核心思想是为每个顶点维护一个分量ID顶点v的分量ID是h跳内所有顶点ID的最小值初始化：每个顶点的分量ID是它自身的顶点ID每轮迭代中，顶点将自己分量ID外发到邻居处下轮迭代，每个顶点如果有收到小于自身分量ID的外部发来的分量ID，则将分量ID更新为收到的最小分量ID图计算系统17M是邻接矩阵基于MapReduce框架的图计算Pegasus/~pegasus/图计算系统18基于Spark框架的图计算Spark对MapReduce的优化传统的MapReduce计算系统性能低频繁磁盘写、高延迟、通信代价大Spark基于内存高效处理Spark实现流水线形式加速Spark有丰富的APIRDD数据结构VertexRDD存储顶点信息EdgeRDD存储边信息图计算系统19基于Spark框架的图计算Spark实现PageRank图计算系统20基于Spark框架的图计算GraphX除了通过RDD自定义实现图计算外，Spark还提供了一个成熟的图处理框架:GraphX封装了两个RDD类(VertexRDD和EdgeRDD)用于表示点集和边集定义了一系列图操作接口，允许用户转换和操作图结构和其属性图计算系统21基于点中心编程的图计算Part322基于点中心编程的图计算图计算系统23点中心编程将大规模图计算抽象为点操作调度集群更新点状态至全图收敛“Thinklikeavertex”?从MapReduce(行的抽象)视角看点中心模型(点的抽象)基于Pregel的图计算Pregel系统谷歌研发的图计算框架首创点中心编程框架，对图计算系统研究产生深远影响图计算系统24SuperStep1SuperStep2SuperStep3Machine1Machine2Machine3同步点Machine1Machine2Machine3Machine1Machine2Machine3BSP模型基于Pregel的图计算Pregel系统采用消息通信（从出边发出消息）Share-Nothing图计算系统25在初始迭代，即superstep=0时，所有顶点处于激活状态。顶点在计算函数中可以视计算情况主动进入非激活状态。进入非激活状态的顶点只有再接收到消息之后才会被重新激活。如果一个顶点被重新激活，只能等到下次主动进入非激活状态才能实现状态转变，即一个顶点不会被动进入非激活状态。全局图计算只会在所有顶点进入非激活状态且当前不再有消息传递的时候，才会终止。基于Pregel的图计算Pregel实现PageRank初始阶段(superstep=0)，系统为所有点初始化PageRank值为1/𝑁,其中𝑁是顶点数每轮迭代：针对每个激活顶点调用点计算函数(Compute)获取并处理该点所接收的来自邻居上一轮发送的消息(如果有)，进而更新PageRank值再向邻居发送对应的PageRank值的𝑛分之一(𝑛为发送节点的节点出度)，完成当前点的计算当完成所有点的计算之后，进入下一个超步如此往复，直至所有顶点都收敛或者达到目标迭代轮次图计算系统26基于Pregel的图计算Pregel系统架构存在一个Master节点来统筹全局超步和计算状态，整体框架是Master-Slave架构的图计算系统27基于Pregel的图计算Pregel实现PageRank图计算系统280.2PR=0.15/5+0.85*SUM0.10.10.20.0670.0670.0670.20.2Superstep=00.20.20.20.2基于Pregel的图计算Pregel实现PageRank图计算系统29PR=0.15/5+0.85*SUM0.1720.0150.0150.1720.010.010.010.340.426Superstep=10.340.4260.030.03基于Pregel的图计算Pregel实现PageRank图计算系统30PR=0.15/5+0.85*SUM0.0510.0150.0150.0510.010.010.010.1970.69Superstep=20.1970.690.030.03基于Pregel的图计算Pregel实现PageRank图计算系统31PR=0.15/5+0.85*SUM0.0510.0150.0150.0510.010.010.010.0950.794Superstep=30.0950.7920.030.03收敛顶点基于Pregel的图计算Pregel实现PageRank图计算系统32PR=0.15/5+0.85*SUM0.0510.0150.0150.0510.010.010.010.0950.794Superstep=40.0950.7920.030.03基于Pregel的图计算Pregel实现PageRank图计算系统33PR=0.15/5+0.85*SUM0.0510.0150.0150.0510.010.010.010.0950.794Superstep=50.0950.7920.030.03基于Pregel的图计算Pregel和MapReduce在图计算上的综合对比图计算系统34

MapReducePREGEL每轮迭代都需要全图拓扑的传输每个顶点负责向邻居发消息，图拓扑不需要被传输中间结果反复写入磁盘，并从磁盘加载主要是用内存进行计算，非常高效需要写个主驱程序来控制迭代，编程相对复杂使用超步和主从架构使得编程简易35包括但并不限于PageRankTriangleCountingConnectedComponentsShortestDistanceRandomWalkGraphCoarseningGraphColoringMinimumSpanningForestCommunityDetectionCollaborativeFilteringBeliefPropagationNamedEntityRecognitionPregel和类Pregel系统支持的图算法基于Pregel的图计算36/ApacheGiraph是一个为高可扩展性而构建的迭代图处理系统。它目前在Facebook中用于分析由用户及其联系人形成的社交图。Giraph最初是Pregel的开源版本，Pregel是Google开发的图处理框架，主要内容在2010年的一篇论文中进行了阐述。这两个系统都受到LeslieValiant提出的分布式计算批量同步并行模型的启发。Giraph在基本Pregel模型之外添加了几个功能，包括主计算、分片聚合器、面向边缘的输入、核外计算等。凭借稳定的开发周期和不断增长的全球用户社区，Giraph成为大规模释放结构化数据集潜力的自然选择。基于Pregel的图计算Pregel的开源实现：ApacheGiraph基于GraphLab的图计算GraphLab计算模式异步计算共享内存(UAI‘10),分布式内存(VLDB’12)数据模型：数据图+共享数据表计算单元：update函数三种一致性模型完全一致性、边一致性、顶点一致性调度器Scheduler决定更新顶点集合，决定更新时机图计算系统37基于GraphLab的图计算Pregel的强同步BSP的问题一个超步下的运行时间取决于最耗时的顶点计算时间可能造成大部分顶点处于等待同步的阶段图计算系统38圈出部分的数据计算同其它计算有较强的独立性，异步进行能够避免强制同步带来的等待时间基于GraphLab的图计算Pregel的强同步BSP的问题异步与同步的计算量对比强同步模式每次调度每个顶点，4轮共计计算36次异步模式每次只调度有顶点变成红色的时候，4轮共计计算8次图计算系统39邻居有红色的时候，则会转为红色Time1Time2Time3Time4调度器一致性模型数据模型update函数40GraphLab框架基于GraphLab的图计算41基于GraphLab的图计算数据模型数据图：除了点边图拓扑之外，还可以有点边各自数据：数值或文本共享数据表：key-value的形式，存储超参和整体收敛信息分布式版本还需要考虑分割：点切点数据:用户信息文本其它数值边数据:如权重数值42基于GraphLab的图计算update函数定义一个在局部数据上的计算操作系统调度该函数与图中顶点，异步式地进行计算直到计算目标收敛每个Update函数的输入是一个顶点，在函数中的数据访问范围是该点的近邻拓扑和数据范围由设定的可视范围(Scope)控制GraphLab中的Update函数采用的是拉取(Pull)的方式从该节点的邻域(Scope)范围内访问相应的信息。这一点不同于Pregel中的消息推送(Push)模型43基于GraphLab的图计算：PageRankupdate函数实现PageRank所有调度顶点会执行给定的Update函数调度节点首先会将顶点的PageRank值保存，并遍历所有邻居顶点获取邻居顶点的PageRank值，之后计算得出当前顶点的最新PageRank值如果新旧值的差值超过设定阈值，则将该顶点所有出边的目的邻居顶点加入调度顶点集合中调度顶点再执行上述过程，直到算法全局收敛Update函数的调度涉及到数据访问的一致性问题和调度序列优化问题S𝑣

:

Scope

44基于GraphLab的图计算一致性问题update函数从顶点的Scope范围内拉取数据，Scope包含顶点，和邻接点边不同顶点Scope可能重叠，并行执行update函数可能导致资源竞争，破坏一致性GraphLab的三种数据一致性模型完全一致性(FullConsistency):Update对Scope内独占读写权限。边一致性(EdgeConsistency):Update对其顶点和相邻边独占读写权限，对相邻的顶点只读权限。顶点一致性(VertexConsistency):Update只对其顶点有独占的写权限，对相邻的边有读权限。三种一致性模型都可以通过上锁的策略实现重叠程度影响并发度45基于GraphLab的图计算图染色算法图染色算法是解决一组并行任务序列化执行的经典算法将任务看成图上的顶点，任务之间的依赖关系看成图上的边为每个顶点分配一个颜色，使得有依赖关系的顶点(任务)不共享相同的颜色相同颜色的顶点可以并发执行46基于GraphLab的图计算调度器Scheduler负责协调并发的顶点更新操作以最大化计算效率和性能决定哪些顶点可以被更新，以及在何时更新调度器包含一个调度列表，列表每个元素指明了哪个update函数（update函数可能不止一种类型）并行应用在哪些顶点上update执行的过程中可能产生新的活跃顶点，扩充调度列表调度列表空了之后算法终止•FIFO(先进先出)调度器:最先进入调度器的任务最先完成•优先级调度器:按照任务的优先级调度任务470.2PR=0.15/5+0.85*SUMSchedulerT:V1,V2,V3,V4,V5

0.20.20.20.2V1V2V3V4V5Vertexconsistencymodel:Allvertexcanbeupdatedsimultaneously ActiveNodes 基于GraphLab的图计算：PageRank48基于GraphLab的图计算：PageRank0.172PR=0.15/5+0.85*SUMSchedulerT:V1,V4,V5

0.340.4260.030.03V1V2V3V4V5Vertexconsistencymodel:Allvertexcanbeupdatedsimultaneously ActiveNodes 49基于GraphLab的图计算：PageRank0.051PR=0.15/5+0.85*SUMSchedulerT:V4,V5

0.1970.690.030.03V1V2V3V4V5Vertexconsistencymodel:Allvertexcanbeupdatedsimultaneously ActiveNodes 50基于GraphLab的图计算：PageRank0.051PR=0.15/5+0.85*SUMSchedulerT:V5

0.0950.7920.030.03V1V2V3V4V5Vertexconsistencymodel:Allvertexcanbeupdatedsimultaneously ActiveNodes 51基于GraphLab的图计算：PageRank0.051PR=0.15/5+0.85*SUMSchedulerT:

0.0950.7920.030.03V1V2V3V4V5Vertexconsistencymodel:Allvertexcanbeupdatedsimultaneously ActiveNodes GraphLab实现的部分图计算算法PageRankLoopyBeliefPropagationGibbsSamplingCoEMGraphicalModelParameterLearningProbabilisticMatrix/TensorFactorizationAlternatingLeastSquaresLassowithSparseFeaturesSupportVectorMachineswithSparseFeaturesLabel-Propagation…52GraphLab：SharedMemory和DistributedMemory共享内存共享数据表来获取邻居信息基于调度器判断算法是否终止分布式内存点切（镜像顶点）分布式锁基于分布式一致性算法判断算法终止基于异步Chandy-Lamport快照实现容错53GraphLab同Pregel的对比54同步计算PREGELGraphLab异步计算非并发，无一致性问题更新函数有一致性问题每个强同步后有检查点机制快照实现一致性容易等待过久，尤其是负载不均衡时异步更快的效率在负载不均衡时，依然高效GraphLab

2.0：PowerGraph扩展创新点1：幂率分布针对性优化大量图数据的度数分布满足幂率分布数据倾斜到严重的存储、通信、计算负载不均衡PowerGraph率先提出点切的分割方式大幅缓解幂率分布的问题图计算系统55GraphLab

2.0：PowerGraph扩展创新点2：GAS模型Gather阶段：负责收集相邻顶点和边的信息，对邻接点边只读Apply阶段：调用顶点上的函数用于更新顶点的值，只写当前点，不写边Scatter阶段：负责更新边上的数据，顶点只读，边进行写操作图计算系统56三个阶段的划分和读写权限的控制避免了数据的读写冲突,达到了互斥的目的并行计算过程之中顶点副本之间的同步则由主版本向镜像副本广播数据的更新GraphLab

2.0：PowerGraphGAS模型实现PageRank图计算系统57基于图数据库的计算实现Part458基于图数据库的计算实现框架以图数据库为后端的架构含有四个模块图数据库后端层内存数据组织层基础算子层上层算法层图计算系统59基于gStore的计算实现框架北京大学邹磊教授团队研发的图数据库系统图计算支持框架图数据在内存中组织成压缩稀疏矩阵（CSR）提供内存组织之上的原子操作，支持二次开发图计算系统60基于gStore的计算实现框架内置函数图计算系统61gStore实现PageRank基于gStore的计算实现框架基于SPARQL调用自定义函数图计算系统62gStore通过PFN接口融合SPARQL和自定义函数ReferencesJeffreyDean,SanjayGhemawat:MapReduce:SimplifiedDataProcessingonLargeClusters.OSDI2004:137-150U.Kang,CharalamposE.Tsourakakis,ChristosFaloutsos:PEGASUS:APeta-ScaleGraphMiningSystem.ICDM2009:229-238GrzegorzMalewicz,MatthewH.Austern,AartJ.C.Bik,JamesC.Dehnert,IlanHorn,NatyLeiser,GrzegorzCzajkowski:Pregel:asystemforlarge-scalegraphprocessing.SIGMODConference2010:135-146LeslieG.Valiant,Abridgingmodelforpara