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

时间:2023-01-08 16:57:30


目录

一、同步图计算

1.图算法

2.同步图计算

3.系统实现

二、异步图计算

1.数据模型

2.计算过程

(本文为陈世敏老师课程笔记)

-------------------------------------------

同步图运算:消息传递
异步图运算:共享内存,可以立即看到完成的计算结果


一、同步图计算

1.图算法

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

  PageRank:随机游走模拟网页浏览得到网页重要度排名,从1/N初始化,直到公式收敛

 (1-d)/n是任意跳转的概率,后面的邻居通过超链接跳到他的概率。为了防止N很大时候精度不够,公式两边乘以N,R‘=NR,R’初始化为   1 

2.同步图计算

  +超步内顶点并行计算,步间全局同步。

  +特点:BSP模型、基于顶点编程(每个顶点都调用computer函数:接收消息->进行计算->发送消息)

  +结束:所有顶点处于非活跃态(初始所有顶点是活跃态,非活跃态的顶点可以转变为活跃态)

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

3.系统实现

  GraphLite为例,运算在内存中实现

  超步开始master->worker(调用computer 收、算、发)->完成通知master->下一个超步.....

  初始In-message list为空->received list是上个超步发来的信息,放入In-message list->computer

  Aggregator全局统计量:本地副本->超步结束发送到master->master 汇总->master发送给worker

  容错靠定期地把图状态写入硬盘生成检查点

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

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

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


二、异步图计算

1.数据模型

  Data graph G=(V, E)
  每个顶点可以有数据Dv
  每条边可以有数据Du->v
  +全局数据表(SDT, shared data table)
  SDT[key]  value
  可以定义全局可见的数据

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

2.计算过程

  直接访问内存进行,update修改立即可见

  DScopev = update (DScopev ;SDT)

  SDT是全局数据表(SDT, shared data table),修改全局可见

 
  三个一致性模型,规定了scope的范围:

    full consistency:范围到邻居顶点可读写

    edage consistency:update不能写邻居顶点,可写本顶点和临边

    vertext consistency:update只能写本顶点,可读临边数据

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

 

  Update 函数的 Scheduling策略:

  +同步调用

  +Round -robin :顺序计算每个顶点,下一个顶点可以看到

  +FIFO:创建Task,按照Task顺序

  +Prioritized :创建Task并指定优先顺序

  sync全局计算

3.Graplab

  以顶点为中心计算,异步可制定不同scheduling策略,共享内存编程,需要一致性模型,全局aggregate判断是否收敛