BSP模型与实例分析（一）-低调大师

BSP模型与实例分析（一）

2017-05-01 537

一、BSP模型概念

BSP(Bulk Synchronous Parallel，整体同步并行计算模型)是英国计算机科学家Viliant在上世纪80年代提出的一种并行计算模型。Google发布的一往篇论文(《Pregel: A System for Large-Scale Graph Processing》)使得这一概念被更多人所认识，据说在Google 80%的程序运行在MapReduce上，20%的程序运行在Pregel上。和MapReduce一样，Google并没有开源Pregel，Apache按Pregel的思想提供了类似框架Hama。

关于BSP，按我的理解做一些解释：

1. Processors指的是并行计算进程，它对应到集群中的多个结点，每个结点可以有多个Processor；
2. Local Computation就是单个Processor的计算，每个Processor都会切分一些结点作计算；
3. Communication 指的是Processor之间的通讯。我们接触的图计算往往需要做些递归或是使用全局变量，在BSP模型中，对图结点的访问分布到了不同的Processor中，并且往往哪怕是关系紧密具有局部聚类特点的结点也未必会分布到同个Processor或同一个集群结点上，所有需要用到的数据都需要通过Processor之间的消息传递来实现同步；
4. Barrier Synchronization 又叫障碍同步或栅栏同步。每一次同步也是一个超步的完成和下一个超步的开始；
5. Superstep 超步，这是BSP的一次计算迭代，拿图的广度优先遍历来举例，从起始结点每往前步进一层对应一个超步。
6. 程序该什么时候结束呢？这个其实是程序自己控制，一个作业可以选出一个Proceessor作为Master，每个Processor每完成一个Superstep都向Master反馈完成情况，Master在N个Superstep之后发现所有Processor都没有计算可做了，便通知所有Processor结束并退出任务。
二、Hama的BSP实现原理

Apache Hama可以说是一个利用Hadoop的基础设施自己封装的一个BSP计算模型的实现，它虽然跟Hadoop有关但是不使用Hadoop集群，而是用的自己的集群。依赖ZooKeeper分布式锁作为作业的调度控制，可以用HDFS/Local/HBase等文件系统作输入输出。

(一) 基本结构

Hama的集群由一个BSPMaster和多个互不关联的GroomServer作计算结点组成，HDFS和Zookeeper都可以是独立的集群。启动从BSPMaster开始，如果是master会启动BSPMaster、GroomServer两个进程，如果只是计算结点则只会启动GroomServer，启动/关闭脚本都是Master机器远程在GroomServer机器上执行。下面分别解释下几个基本概念：

1. BSPMaster 即集群的主，负责了集群各GroomServer结点的管理与作业的调度，就我所知它还存在单点的问题。相当于Hadoop的JobTracker或HDFS的NameNode；
2. BSPGroomServer 即计算结点，GroomServer是物理上的概念，也相当于是BSPPeer的宿主，负责了BSPPeer对外的消息通讯、机器状态报告等，相当于Hadoop的TaskTracker或HDFS的DataNode，在集群中往往和DataNode一一对应的部署（底层机制就是Hadoop的TaskTracker）；
3. BSPPeer 即BSP中的Processor，当作业过来的时候，任务jar包和配置会被同步过来，GroomServer就启动一个独立JVM进程来执行一个BSPPeer实例，就像TaskTracker的作法一样。BSPPeer是分布式计算中的逻辑计算单元；
4. BSPJobClient 作业客户端，职责是将作业所需jar以及配置提交给BSPMaster
5. Zookeeper 分布式锁。用于实现Barrier Synchronisation机制。在ZK上，进入BSPPeer主要有进入Barrier和离开Barrier操作，所有进入Barrier的Peer会在zk上创建一个EPHEMERAL的node（/bsp/JobID/Superstep NO./TaskID），最后一个进入Barrier的Peer同时还会创建一个ready node(/bsp/JobID/Superstep NO./ready)，Peer进入阻塞状态等待zk上所有task的node都删除后退出Barrier
(二) 输入与输出

Hama的输入输出文件格式、分块、文件传输等机制都跟HDFS是一样的，也都是K-V对，派生自Writable。输入的K-V对为结点（VertexWritable）和邻接结点集合(VertexArrayWritable)。

(三) 消息通讯

图计算涉及到大量消息传递，Hama不完全是实时传送，消息的传输发生在Peer进入同步阶段后，并且对同一个目标GroomServer的消息进行了合并，两个物理结点之间每一次超步其实只会发生一次传输

(四) 图算法运用

Hama其实只提供了一个图计算框架，算法都是需要自己去实现的。理想的情况是图文件分块，Peer尽可载入本地文件作计算，这样即加快了图载入时间也减少了网络传输。不过事实是可能不能这样假设，为使结构尽更简单，对图的切割往往只是将结点用简单的Hash算法分布到Peer上，不能对图作任何局部聚类的假设。
本文来源于"阿里中间件团队播客",原文发表时间" 2012-06-08"

微信关注我们

原文链接：https://yq.aliyun.com/articles/85547

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

通过eclipse调试MapReduce任务

利用MapReduce利器作开发，不论从思想上还是技能上都是新的体验。以下罗列下如何利用eclipse调试MR任务。(本人环境：hadoop 1.0.2，部署在linux上，本地windows开发)1、安装hadoop。先在linux上安装好hadoop，为更接近线上环进，我的是安装成Cluster注意要远程访问相关端口，conf/mapred-site.xml中localhost:9001中需要换成ip加端口。sh bin/start-all.sh启动，先按文档命令行跑一下example的wordcount。我安装好运行example遇到了XML解析的错(原因应该是${java.home}/lib/jaxp.properties没有设置，见:javax.xml.xpath.XPathFactory.newInstance(uri)的注释)，后来手动加了xalan-j_2.7.0.jar、xercesImpl-2.7.1.jar、xml-apis-2.7.1.jar、xmlenc-0.52.jar、serializer-2.7.1.jar几个包解决。2、下载hadoop eclipse...

2017-05-02

509

本节书摘来异步社区《Storm技术内幕与大数据实践》一书中的第1章，作者：陈敏敏 , 黄奉线 , 王新春责编：杨海玲，更多章节内容可以访问云栖社区“异步社区”公众号查看。第1章绪论 Storm技术内幕与大数据实践Apache Storm（http://storm.apache.org/）是由Twitter开源的分布式实时计算系统。Storm可以非常容易并且可靠地处理无限的数据流。对比Hadoop的批处理，Storm是一个实时的、分布式的、具备高容错的计算系统。Storm应用可以使用何编程语言来进行开发，并且非常有趣。 Storm的使用场景非常广泛，比如实时分析、在线机器学习、分布式RPC、ETL等。Storm非常高效，在一个多节点集群上每秒钟可以轻松处理上百万条的消息。Storm还具有良好的可扩展性和容错性以及保证数据可以至少被处理一次等特性。图1-1中水龙头和后面水管组成的拓扑图就是一个Storm应用（Topology），其中的水龙头是Spout，用来源源不断地读取消息并发送出去，水管的每一个转接口就是一个Bolt，通过Stream分组的策略转发消息流。

2017-05-02

561

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。