大数据运算系统(2)--- 图计算系统

时间:2022-03-04 21:13:56
同步图运算:消息传递 异步图运算:共享内存,可以立即看到完成的计算结果
一、同步图运算系统 1、图算法 (1)PageRank Google用于对网页重要性打分的算法。 大数据运算系统(2)--- 图计算系统
顶点:网页 边:超链接
(2)计算方法 初始化:所有顶点的PageRank为1/N 迭代:用公式迭代直至收敛
迭代公式: 大数据运算系统(2)--- 图计算系统
Ru:所求u的PageRank Rv:顶点v的PageRank Lv:顶点v的出度(出边的条数) Bu:顶点u的入邻居集合 d:damping factor N:总顶点个数 (3)出现问题 由于N很大,造成的数据精度可能不够。 所以Ru’=NRu 大数据运算系统(2)--- 图计算系统
改进算法计算方法: 初始化:所有顶点的PageRank为1 迭代:用新公式迭代直至收敛
新的迭代公式: 大数据运算系统(2)--- 图计算系统
Ru:所求u的PageRank*N Rv:顶点v的PageRank*N Lv:顶点v的出度(出边的条数) Bu:顶点u的入邻居集合 d:damping factor N:总顶点个数
2、同步图运算 (1)图计算模型 运算分成多个超步。 超步内,并行执行每个顶点。 超步间,全局同步
顶点算法通常步骤: 接收上个超步发出的in-neighbor的消息。 计算当前顶点的值。 向out-neighbor发消息。  (2)图计算模型的特点 特点1:BSP模型  Bulk Synchronous Processing 大数据运算系统(2)--- 图计算系统
特点2:基于顶点的编程模型   每个顶点有一个value。 顶点为中心的运算:程序员实现一个compute函数。在每个超步中,同步图系统对每一个顶点调用一次Compute。Compute通常接收消息,计算,发送消息。 (3)图计算如何结束 顶点有两种状态: 活跃态:图系统只对活跃顶点调用Compute;顶点初始状态均为活跃态。 非活跃态:Compute调用Vote to halt时,顶点变为非活跃态;非活跃态的顶点也可以重新变为活跃态。
当所有的顶点处于非活跃状态时,图系统结束本次图运算。
3、图计算编程 GraphLite编程 实现class Vertex的一个子类 class Vertex中有两类函数: (1)图计算程序员需要实现的:Compute() (2)系统提供的,可以在Compute调用的。例如: getValue(),mutableValue(), getOutEdgeIterator(),sendMessageTo(),sendMessageToAllNeighbors(), voteToHalt() superstep():获取当前超步数:从0开始计数 acculate(),getAggregate():全局统计量
4、系统实现 master worker 每个worker对应一个graph partition。
5、小结 基于BSP模型实现同步图运算 运算在内存中完成 容错依靠定期地把图状态写入硬盘生成检查点:在一个超步开始时,master可以要求所有的worker都进行检查点操作。 可以比较容易地表达一些图操作
二、异步图运算系统 可以用来实现一些机器学习算法。允许不同的顶点有不同的更新速度;一个顶点的更新,它的邻居顶点立即可见,而不是等到下一个超步开始。从而可以更快读地收敛。
1、数据模型 (1)Data graph G=(V,E)  每个顶点、每条边都可以有数据D (2)全局数据表(SDT,shared data table) SDT[key] -> value 可以定义全局可见的数据
2、计算过程 Dscopev = update(Dscopev;  SDT) update:类似compute,程序员定义的顶点运算 Dscopev:顶点运算设计的范围。包括顶点v,v的相邻边,v的相邻顶点。