从BSP模型到Apache Hama(2)

2. 一般而言,分布存储的MIMD模型的可编程性比较差,但在BSP模型中,如果计算和通信可以合适的平衡(例如g=1),则它在可编程方面呈现出主要的优点。

3. 在BSP模型上,曾直接实现了一些重要的算法(如矩阵乘、并行前序运算、FFT和排序等),他们均避免了自动存储管理的额外开销。

4. BSP模型可以有效的在超立方体网络和光交叉开关互连技术上实现,显示出,该模型与特定的技术实现无关,只要路由器有一定的通信吞吐率。

5. 在BSP模型中,超级步的长度必须能够充分的适应任意的h-relation,这一点是人们最不喜欢的。

6. 在BSP模型中,在超级步开始发送的消息,即使网络延迟时间比超级步的长度短,该消息也只能在下一个超级步才能被使用。

7. BSP模型中的全局障碍同步假定是用特殊的硬件支持的,但很多并行机中可能没有相应的硬件。

五、BSP与MapReduce对比

  执行机制:MapReduce是一个数据流模型,每个任务只是对输入数据进行处理,产生的输出数据作为另一个任务的输入数据,并行任务之间独立地进行,串行任务之间以磁盘和数据复制作为交换介质和接口。

  BSP是一个状态模型,各个子任务在本地的子图数据上进行计算、通信、修改图的状态等操作,并行任务之间通过消息通信交流中间计算结果,不需要像MapReduce那样对全体数据进行复制。

  迭代处理:MapReduce模型理论上需要连续启动若干作业才可以完成图的迭代处理,相邻作业之间通过分布式文件系统交换全部数据。BSP模型仅启动一个作业,利用多个超步就可以完成迭代处理,两次迭代之间通过消息传递中间计算结果。由于减少了作业启动、调度开销和磁盘存取开销,BSP模型的迭代执行效率较高。

  数据分割:基于BSP的图处理模型,需要对加载后的图数据进行一次再分布的过程,以确定消息通信时的路由地址。例如,各任务并行加载数据过程中,根据一定的映射策略,将读入的数据重新分发到对应的计算任务上(通常是放在内存中),既有磁盘I/O又有网络通信,开销很大。但是一个BSP作业仅需一次数据分割,在之后的迭代计算过程中除了消息通信之外,不再需要进行数据的迁移。而基于MapReduce的图处理模型,一般情况下,不需要专门的数据分割处理。但是Map阶段和Reduce阶段存在中间结果的Shuffle过程,增加了磁盘I/O和网络通信开销。

  MapReduce的设计初衷:解决大规模、非实时数据处理问题。"大规模"决定数据有局部性特性可利用(从而可以划分)、可以批处理;"非实时"代表响应时间可以较长,有充分的时间执行程序。而BSP模型在实时处理有优异的表现。这是两者最大的一个区别。

六、BSP模型的实现

1.Pregel

  Google的大规模图计算框架,首次提出了将BSP模型应用于图计算,具体请看Pregel——大规模图处理系统,不过至今未开源。

2.Apache Giraph

  ASF社区的Incubator项目,由Yahoo!贡献,是BSP的java实现,专注于迭代图计算(如pagerank,最短连接等),每一个job就是一个没有reducer过程的Hadoop job。

3.Apache Hama

  也是ASF社区的Incubator项目,与Giraph不同的是它是一个纯粹的BSP模型的java实现,并且不单单是用于图计算,意在提供一个通用的BSP模型的应用框架。

4.GraphLab

  CMU的一个迭代图计算框架,C++实现的一个BSP模型应用框架,不过对BSP模型做了一定的修改,比如每一个超步之后并不设置全局同步点,计算可以完全异步进行,加快了任务的完成时间。

5.Spark

  加州大学伯克利分校实现的一个专注于迭代计算的应用框架,用Scala语言写就,提出了RDD(���性分布式数据集)的概念,每一步的计算数据都从上一步结果精简而来,大大降低了网络传输,同时保证了血统的纯正性(即出错只需返回上一步即可),增强了容错功能。Spark论文里也基于此框架实现了BSP模型(叫Bagel)。值得一提的是国内的豆瓣也基于该思想用Python实现了这样一个框架叫Dpark,并且已经开源。https://github.com/douban/dpark

6.Trinity

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/03c4ef9b84c2f74409e2436d679f2132.html