Hadoop Hama项目–BSP模型的实现

1、Hama概论 建立在Hadoop上的分布式 并行 计算模型。 基于 Map/Reduce 和 Bulk Synchronous 的实现框架。 运行环境需要关联 Zookeeper、HBase、HDFS 组件。 集群环境中的系统架构由 BSPMaster/GroomServer (Computation Engine )、Zookeeper (Distributed L

1、Hama概论
  ·建立在Hadoop上的分布式并行计算模型。
  ·基于 Map/Reduce 和 Bulk Synchronous 的实现框架。
  ·运行环境需要关联 Zookeeper、HBase、HDFS 组件。
  ·集群环境中的系统架构由 BSPMaster/GroomServer(Computation Engine)、Zookeeper(Distributed Locking)、HDFS/HBase(Storage Systems) 这3大块组成。
如图所示：

  ·Hama中有2个主要的模型:
    – 矩阵计算(Matrix package)
    – 面向图计算(Graph package)

·Hama项目起源于在2008年5月19日
·Hama主要成员 Edward J. Yoon (高丽棒子)
·Hama项目的最大支持者 韩国NHN互联网搜索引擎以及网络游戏公司，貌似中国的百度，详见这里。

2、Hama介绍 
   2008年5月Hama被视为Apache众多项目中一个被孵化的项目，目前(2010年12月)在Hama的项目网站上还没有正式的release版本，作为Hadoop项目中的一个子项目，BSP模型是Hama计算的核心，并且实现了分布式的计算框架，采用这个框架可以用于矩阵计算(matrix)和面向图计算(grah)、网络计算(network)。

我的废话:
1、如果要深入了解到 Hama中采用到的技术体系，需要去阅读一些BSP、MPI、Pregel等相关资料，可以有助于对Hama项目的了解。
2、看来Apache基金会对Google未开源的核心技术彻底的做了一个山寨版本，比如我之前提到过关于Yahoo山寨了Google的那些技术。
3、Hama中依然存在SPFO的单点问题，如果主节点BSPMaster挂了，依然全挂，当然有其他的解决办法，不过这里主要想指出的是Hama暂时还没有设计到这点。
4、Hama在MapReduce的基础上实现了2种算法，Iterative 和 Block ，其中Iterative比较简单，而Block相对复杂些。

3、关于BSP模型
Hama中最关键的就是BSP(Bulk Synchronous Parallel-“大型”同步模型)模型, BSP的概念由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步，该模型基于一个master协调，所有的worker同步(lock-step)执行, 数据从输入的队列中读取， 该模型的架构如图所示：

另外，BSP并行计算模型可以用 p/s/g/i 4个参数进行描述：
·    P为处理器的数目(带有存储器)
·    s为处理器的计算速度
·    g为每秒本地计算操作的数目/通信网络每秒传送的字节数，称之为选路器吞吐率，视为带宽因子 (time steps/packet)=1/bandwidth
·    i为全局的同步时间开销,称之为全局同步之间的时间间隔 (Barrier synchronization time)
那么假设有p台处理器同时传送h个字节信息，则g•h就是通信的开销。同步和通信的开销都规格化为处理器的指定条数。

BSP计算模型不仅是一种体系结构模型，也是设计并行程序的一种方法。BSP程序设计准则是 bulk同步 (bulk synchrony)，其独特之处在于超步(superstep)概念的引入。一 个BSP程序同时具有水平和垂直两个方面的结构。从垂直上看,一个BSP程序由一系列串行的超步(superstep)组成,如图所示:

这种结构类似于一个串行程序结构。从水平上看， 在一个超步中， 所有的进程并行执行局部计算。一个超步可分为三个阶段 ,如图所示:

1 )本地计算阶段， 每个处理器只对存储本地内存中的数据进行本地计算。 
2 )全局通信阶段， 对任何非本地数据进行操作。 
3 )栅栏同步阶段， 等待所有通信行为的结束。 

BSP模型相对于其他两种模型而言， 具有如下两个方面的优点： 
•MPI 和 PVM两种并行计算模型，依赖于接收和发送 的操作对。这样通信方式容易导致上层应用程序产生死锁，而BSP并行计算库是一个程序划分为超步(superstep)，使得死锁不再发生。 
•BSP模型由于其本身的特点， 使得对于程序的正确性和时间的复杂性预测成为可能。

4、Apache Hama与Google Pregel
Hama类似Google发明的Pregel，如果你听过Google Pregel这个利器的话，那么就对BSP计算模型不会陌生，Google的Pregel也是基于BSP模型，在Google的整个计算体系中有20%的 计算是依赖于Pregel的计算模型，Google利用Pregel实现了图遍历(BFS)、最短路径(SSSP)、PageRank计算,我猜想 Google的Google Me 产品很有可能会大量采用Pregel的计算方式，用Pregel来绘制Google Me产品中SNS的关系图。

Google的Pregel是采用GFS或BigTable进行持久存储，Google的Pregel是一个Master-slave主从结构，有一个节点扮演master角色，其它节点通过name service定位该顶点并在第一次时进行注册，master负责对计算任务进行切分到各节点(也可以自己指定，考虑load balance等因素)，根据顶ID哈希分配顶点到机器(一个机器可以有多个节点，通过name service进行逻辑区分)，每个节点间异步传输消息，通过checkpoint机制实行容错(更高级的容错通过confined recovery实现)，并且每个节点向master汇报心跳(ping)维持状态。

 Hama是Apache中Hadoop的子项，所以Hama可以与Apache的HDSF进行完美的整合，利用HDFS对需要运行的任务和数据进行持久化存储，也可以在任何文件系统和数据库中。当然我们可以相信BSP模型的处理计算能力是相对没有极限的特别对于图计算来说，换句话说BSP模型就像MapReduce一样可以广泛的使用在任何一个分布式系统中，我们可以尝试的对实现使用Hama框架在分布式计算中得到更多的实践，比如：矩阵计算、排序计算、pagerank、BFS 等等。

5、Hama Architecture
Apache的Hama主要由三个部分组成：BSPMaster，GroomServers和Zookeeper，下面这张图主要概述了Hama的整体系统架构,并且描述了系统模块之间的通讯与交互。Hama的集群中需要有HDFS的运行环境负责持久化存储数据(例如:job.jar),BSPMaster负责进行对Groom Server 进行任务调配，groom Server 负责进行对BSPPeers进行调用 程序进行具体的调用，Zookeeper负责对Groom Server 进行失效转发。

BSPMaster
在Apache Hama中BSPMaster模块是系统中的一个主要角色，他主要负责的是协同各个计算节点之间的工作，每一个计算节点在其注册到master上来的时候会分配到一个唯一的ID。Master内部维护着一个计算节点列表，表明当前哪些计算节点出于alive状态，该列表中就包括每个计算节点的ID和地址信息，以及哪些计算节点上被分配到了整个计算任务的哪一部分。Master中这些信息的数据结构大小取决于整个计算任务被分成多少个partition。因此，一台普通配置的BSPMaster足够用来协调对一个大型计算。
下面我们来看看BSPMaster做了哪些工作：
   •    维护着Groom服务器的状态。
   •    控制在集群环境中的superstep。
   •    维护在groom中job的工作状态信息。
   •    分配任务、调度任务到所有的groom服务器节点。
   •    广播所有的groom服务器执行。
   •    管理系统节点中的失效转发。
   •    提供用户对集群环境的管理界面。

   一个BSPMaster或者多个grooms服务器是通过脚本启动的，在Groom服务器中还包含了BSPeer的实例，在启动GroomServer的时候就会启动了BSPPeer，BSPPeer是整合在GrommServer中的，GrommServer通过PRC代理与BSPmaster连接。当BSPmaster、GroomServer启动完毕以后，每个GroomServer的生命周期通过发送“心跳”信息给BSPmaster服务器，在这个“心跳”信息中包含了GrommServer服务器的状态，这些状态包含了能够处理任务的最大容量，和可用的系统内存状态，等等。

   BSPMaster的绝大部分工作，如input ，output，computation，saving以及resuming from checkpoint，都将会在一个叫做barrier的地方终止。Master会在每一次操作都会发送相同的指令到所有的计算节点，然后等待从每个计算节点的回应(response)。每一次的BSP主机接收心跳消息以后，这个信息会带来了最新的groom服务器状态，BSPMaster服务器对给出一个回应的信息，BSPMaster服务器将会与groom 服务器进行确定活动的groom server空闲状态，也就是groom 服务器可资源并且对其进行任务调度和任务分配。 BSPMaster与Groom Server两者之间通讯使用非常简单的FIFO(先进先出)原则对计算的任务进行分配、调度。

GroomServer
   一个Groom服务器对应一个处理BSPMaster分配的任务，每个groom都需要与BSPMaster进行通讯，处理任务并且想BSPMaster处理报告状态，集群状态下的Groom Server需要运行在HDFS分布式存储环境中，而且对于Groom Server来说 一个groom 服务器对应一个BSPPeer节点，需要运行在同一个物理节点上。

Zookeeper
   Zookeeper这里就不多提了，可以参考我之前写的几篇文章，在Apache HaMa项目中zookeeper是用来有效的管理BSPPeer节点之间的同步间隔(barrier synchronisation),同时在系统失效转发的功能上发挥了重要的作用。

6、Hama对BSP模型的实现
在一个BSP计算模型的程序中包含了一个supersteps步骤，每一个superstep由以下3个体系：
   •    本地计算
   •    进程通信
   •    同步间隔

public class BSPEaxmple {

  public static class MyBSP extends BSP {

    @Override
    public void bsp(BSPPeer bspPeer) throws IOException, KeeperException,
        InterruptedException {
      // 1. Do something locally
     
      // 2. Sends/receives data to/from neighbor nodes
      bspPeer.send(peerName, msg);

      while ((message = bspPeer.getCurrentMessage()) != null) {
         byte[] data = message.getData();
      }

      // 3. Barrier synchronization
      bspPeer.sync();
    }

    @Override
    public Configuration getConf() {
      return conf;
    }

    @Override
    public void setConf(Configuration conf) {
      this.conf = conf;
    }   

  }
 
  // BSP job configuration
  public void main(String[] args) throws Exception {
    BSPJob bsp = new BSPJob(new HamaConfiguration(), BSPEaxmple.class);
    // Set the job name
    bsp.setJobName("My BSP Job");
    bsp.setBspClass(MyBSP.class);

    // Submit job
    BSPJobClient.runJob(bsp);
  }
} 

接下来将会介绍 Hama的具体的用例和安装配置说明，待续。

感谢您的阅读。

相关文章:
  Apache ZooKeeper入门2
  Apache Zookeeper入门1
  Apache ZooKeeper入门3

–end–

原文地址：Hadoop Hama项目–BSP模型的实现, 感谢原作者分享。