分布式编程未来展望（主讲人：吴威）在线视频

在BSP模型的基础上

我们再来看看图计算模型

这里挑选了一个

典型的图计算模型

ODPS Graph计算框架

在阿里云开放的计算能力里

就包含了ODPS Graph

比如

阿里巴巴天池技术大赛里面

就可以用到ODPS Graph

实现一些图算法

ODPS Graph参考了

Google论文里的里Pregel实现

类似的开源系统

还有阿帕奇的（00:36）

和（00:37）等

Graph计算框架

实现了BSP计算模型

所以也继承了BSP模型的优点

和缺点

刚才已经提到过了

Graph模型的另外一个

核心的概念

是以顶点为中心的API设计

我们来看这个示例图

顶点之间的通信

是通过消息来传递的

每一轮迭代之前

每个顶点都会收到

从它的圆发来的消息

然后顶点对消息做处理

并将结果发给它的下一个顶点

比如顶点5

它受到了顶点2和3

发来的两条消息

2和3可能是它的邻居

或者上游结点

经过结点5的处理

它又发出了三条消息

可能它的另外三个邻居

也有可能是刚才的2和3两个顶点

下游的三个顶点

接着做

刚才的顶点5上发生的操作

整体流程和BSP流程类似

但是在Graph模型里

关注的是各个顶点

所以这被称为

先要向顶点那样做思考

然后再来写Graph的程序

下图我们可以清晰地看到

Graph作业的生命周期

首先数据是来自ODPS表

有一个加载图的操作

这个操作做了一轮从关系表

到图的映射

我们可能在图论

或者算法课程里学到过

图的存储方式是连接表

或者连接矩阵

在ODPS表

保存的就是这样的结构

我们的图是一个分布式的图

所以需要做数据分片

把图加载到不同的计算单元中

数据的分片方式可以自己定义

也可以用默认的哈希分片的方式

在图加载和分片完成之后

就可以开始进行多轮的迭代运算

这里举了

最简单的vertex.compute方法

输入是一系列的消息

当然其他的编程接口

比如用（02：35）来减少

消息发送端的消息量

减少内存的使用

或者用（02：41）来汇总

并分发全局信息等

经过多轮运算

我们得到了想要的图结构

最后可以把图输出到ODPS表

我们来看一个

ODPS Graph的编程事例

在图中找到值最大的顶点

有四个顶点

内部的值分别是3 6 2 1

他们两两之间都有联系

每一轮迭代开始

每个顶点都会向它们的邻居结点

发送消息

消息的内容是顶点自己的值

所以顶点3收到了顶点6的消息

顶点6也收到了顶点3的消息

依次类推

当所有的顶点

都收到自己的消息后

开始比较当前顶点的值

和消息顶点的值

如果消息顶点的值更大

则把自己顶点的值

置为收到消息的值

否则就处理下一个结点

这样我们看到了顶点3

收到了顶点6的消息

它会把自己的值置为6

对于其他顶点也是一样

它们处理完消息

并修改自己的值

这时候要做一轮全局的同步

确保大家都处理完消息

全局同步之后

又是发消息的过程

只有那些在本轮迭代

改变过值的顶点

才会继续需要发送消息

经过几轮迭代

大家都没有状态更新

我们的全局最大值就找出来了

这就是6

右边是具体顶点

Computer代码示例

流程是比较简单的

刚才讲解中都有涉及到

我这儿就不展开了

在现实生活中

ODPS Graph从性能上看

非常适合迭代计算

现在的实现中

所有的内部状态都是在内存中

只有加载图 网生图（00：43）

或者做Checkpoint的时候

才会写磁盘

所以比较高效

并且有一定的线性扩展能力

因为运算过程中不需要

锁和信息量

所以并发度非常高

其次

通过Checkpoint

和心跳机制保证了

Graph的编程框架的容错性

除此之外

我们有一个问题

想让大家思考一下

之前提到过的图

是比关系运算更加复杂的结构

图的表达能力更强

比如

可以把一条关系数据库的记录

看成一个顶点

关系数据之间的组建和外件依赖

看成两个点之间的边

那么以关系型数据

为代表的块编程

当然可以跑到点的框架之上

比如

我们是否可以

把MapReduce的模型

运行在Graph上

大家可以思考这个问题

还有其他的图计算相关的编程

或者软件

这里也简单介绍一下

Mahout是一个通用的算法库

当然也包括图算法

最初的版本是Mahout

基于MapReduce实现的

我们之前说过

MapReduce在很多场景下

并不适合图

所以Mahout的代码效率并不高

Neo4j是一个单机版图数据库

上面有一些简单的图运算操作

但是做不了复杂的计算

更关键的是

Neo4j是一个单机版的程序

所以扩展性并不好

GraphLab是一个

基于MPI实现的图的算法库

API较为复杂

而且是因为基于异步模型的操作

没有BSP的全局同步功能

所以虽然效率非常高

但是因为需要用户自己定义一些

一致性模型

且代码过程中要防止死锁

用户使用的代价还是比较高昂的

GraphChi

是一个单机版的图数据库

性能很高

但也是受制于单机环境

无法做到线性扩展

GraphX

是Spark上的图计算框架

它们在SparkRDD通用算子之外

扩展了大量的图相关的算子

所以GraphX既可以使用

简单的关系型运算

也可以直接操作图

编程接口非常简单

是一个比较有前景的

图计算发展方向

各个图编程模型各有千秋

关键还是需要在合适的时间

选择合适的模型

前面说了这么多当前的编程模型

和编程语言

我们也需要展望一下未来

在未来分布式编程模型

会更加丰富多彩

可能在各个维度上做扩展

比如当前主要的编程模型

都是以处理离线数据为主

未来可能会向实时计算方向发展

当前在开源社区里

涌现了大量的

更加实时的编程引擎

比如Spark Tez Impala等等

这些引擎让上层编程模型

变得更加高效

另外一个方向

是从当前的批量计算

到流式计算演化

我们后续处理的数据

可能不是一次性获取的

而是源源不断地输入

需要我们的编程模型

能处理这样的数据

比如Pig on Storm项目

就是一个例子

我们还是使用Pig latin语言

但是又能利用到

Storm的流式计算处理能力

最后一个方向是

编程模型的融合

关系型计算 图计算

迭代计算等编程模型

如果能融合在一起

将极大地简化我们的编程方法

之前提到过的Spark GraphX

就是一个例子

在Spark社区里

SparkSQL GraphX

Spark Streaming

等多种编程模型在一起出现

而且可以很方便地互操作

这代表了未来的方向

分布式编程模型的课程

就到这里结束了

最后给大家推荐一些参考资料

这里有google研究团队出品的

MapReduce FlumeJava

以及parallel相关的论文

也有阐述SparkIDD相关的论文

还包含了Pig相关的论文

PPT和Vick

有兴趣的同学可以进一步研读