Hama顶点编程

Hama是基于HDFS上的BSP模型实现。 Apache Hame是Google Pregel的开源实现

　　Pregel是Google提出的一个面向大规模图计算的通用编程模型。许多实际应用中都涉及到大型的图算法，典型的如网页链接关系、社交关系、地理位置图、科研论文中的引用关系等，有的图规模可达数十亿的顶点和上万亿的边。Pregel编程模型就是为了对这种大规模图进行高效计算而设计。

　　Pregel的设计思想来自BSP（Bluk Synchronous Parallel）模型。BSP模型包括三部分：BSP机器模型、BSP计算模型和BSP代价模型。其中BSP计算模型采用单程序多数据(SPMD)的执行方式。BSP计算由一组处理单元和一系列连续的超级步 (superstep)组成。在每个超级步内，每个处理单元并发地执行本地计算，并向其他的处理单元发送消息。在一个超级步结束时有一个全局的同步操作。因此，可以看作本地计算-全局通信-栅栏同步模式。

　　具体而言，Pregel计算由一系列的迭代(即超级步)组成。在每一个超级步中，计算框架会调用顶点上的用户自定义的Compute函数，这个过程是并行执行的。Compute函数定义了在一个顶点V以及一个超级步S中需要执行的操作。该函数可以读入前一超级步S-1中发送来的消息，然后将消息发送给在下一超级步S+1中处理的其他顶点，并且在此过程中修改V的状态以及其出边的状态，或者修改图的拓扑结构。消息通过顶点的出边发送，但一个消息可以送到任何已知ID的特定顶点上去。这种计算模式非常适合分布式实现：顶点的计算是并行的；它没有限制每个超级步的执行顺序，所有的通信都仅限于S到S+1之间。

　　Pregel是一个以顶点为中心的计算模型，边在这种计算模式中并不是第一类对象，在边上没有相应的计算。

少点：

单向松弛模拟：对于模式图中的一个出边而言，孩子节点或孙子节点必须出现在条件集合中

　　　　少点：如果该点不存在，则他的儿子节点必须都存在，会出现无用结果，如存在A–>B,则输出B

双向松弛模拟：将模式图的边反向，再匹配，双向匹配。

　　　　少点：如果该点不存在，则他的儿子和父亲节点必须都存在。

应用场景：社团发现，一个团体中某些人的工作可以被上一级代替。

数据来源：Twitter，Amazon，Google

与谁比较，优势？