免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 5525 | 回复: 2

[学习分享] 分布式并行计算的算法应用 [复制链接]

论坛徽章:
0
发表于 2011-04-13 21:41 |显示全部楼层
众所周知MapReduce模型是Google公司在多台普通机器,利用函数式的思想,提高程序执行的性能,而Stanford的 Phoenix则是这一模型在多核时代的解决方案。作为Google MapReduce技术的开源实现,Hadoop借鉴了谷歌的Google File System文件系统、MapReduce并行算法以及BigT able。因此,Hadoop也是一个能够分布式处理大规模海量数据的软件框架,也是一个开源的分布式并行计算平台,它主要由MapReduce的算法执 行和一个分布式的文件系统等两部分组成。

Hadoop是并行工作的,以加快任务处理速度。Hadoop的可扩展依赖于部署Hadoop软件框架计算集群的规模,Hadoop的运算是可扩展 的,具有处理PB级数据的能力。虽然Hadoop自身由Java语言开发, 但它除了使用Java语言进行编程外, 同样支持多种编程语言,如C++。

   与Hadoop不同的是微软是通过DryadLINQ语言进行编程与设计,它可以根据程序员给出的LINQ查询生成可以在Dryad引擎上执行的分布式 策略算法建模(运算规则),并负责任务的自动并行处理及数据传递时所需要的序列化等操作。此外,它还提供了一系列易于使用的高级特性,如强类型数 据,Visual Studio集成调试,以及丰富的任务优化策略(规则)算法等等。这种模型策略开发框架也比较适合采用领域驱动开发设计(DDD)来构建“云”平台应用, 并能够较容易的做到自动化分布式计算。

  并行算法分治策略

  Y=(A+B(C+DEF))+G,串行计算 需要6步。利用结合律和交换律,该式变为Y=Y + (分裂为两个问题),其中Y =A+G, =B (C+DEF),在两台处理机的系统上只需5步并行计算。在用分配率,Y=(A+B(C+DEF))+G可变为Y= + ,其中 =A+G+BC, =BDEF,在两台处理机的系统上并行计算只需4步。如四台处理机的系统,并行计算可进一步减少为3步。两台处理机下的运算分解树和四台处理机下的运算分 解树,如图1所示。

1.png
图1 DGA运算分解树

  从上面分析我们可以看到,通过并行算法策略建模,可以有效的控制数据的颗粒度,当程序运行在Dryad分布式并行平台时候,可最大化的提高分布式并行运算效率。

  分布式并行策略

  在云计算的时代,Dynamo(Amazon 公司的一个分布式存储引擎)可以说是一本实现分布式存储的红宝书,借鉴Dynamo实现的产品如雨后春笋般冒出。

  我们经常会遇到所开发的网站/系统,无法承载大规模用户并发访问的问题。解决该问题的传统方法是使用数据库,通过数据库所提供的访问操作接口来保证处理复杂的查询能力。当访问量增大,单数据库处理不过来时便增加数据库服务器。如果增加了3台服务器, 再把用户分成了三类(关注:策略建模、颗粒度和映射):A(学生),B(老师),C(程序员)。每次访问的时候,Dryad会先查看用户属于哪一类,然后 直接访问存储那类用户数据的数据库,可能处理能力增加了三倍。这时我们已经实现了一个分布式的存储引擎过程,而Dryad与Dynamo具有相似的功能。 Dynamo分布式存储引擎,如图2所示。

2.png
▲图2 Dynamo分布式存储引擎

我们可以通过Dryad和Dynamo进行分布式云平台来解决云存储扩容困难问题。如果这3台服务器也承载不了更大的数据要求时,需要增加到5台服务器, 那必须更改分类方法把用户分成5类,然后重新迁移已经存在的数据,这时候就需要非常大的迁移工作,这种方法显然不可取。另外,当群集服务器进行分布式计算 运行的时候,每个资源节点处理能力可能有所不同(例如不同硬件配置的服务器等等),如果只是简单的把机器直接分布上去,性能高的机器得不到充分利用,性能 低的机器处理不过来。

3.png
图3 通过Dryad DAG排列的节点(程序)扩展性能

  ? P parses lines(解析线)

  ? D hash distribute(哈希分布)

  ? S quicksort(快速排序)

  ? C count occurrences(事件计算)

  ? MS merge sort(合并分类)

  ? M non-deterministic merge(未确定合并)

   Dryad和Dynamo解决此问题的方法是采用虚节点。把上面的A B C三类等用户都想象成一个逻辑上的节点。一台真实的物理节点可能会包含一个或者几个虚节点(逻辑节点),看机器的性能而定。我们可以把那任务程序分成Q等 份(每一个等份就是一个虚节点),这个Q要远大于我们的资源数。现在假设我们有S个资源,那么每个资源就承担Q/S个等份。 当一个资源节点离开系统的时候,它所负责的等份要重新均分到其他资源节点上,一个新节点加入的时候,要从其他的节点“偷取”到一定数额的等份。

   在这个策略建模算法下,当一个节点离开系统的时候,虽然需要影响到很多节点,但是迁移的数据总量只是离开那个节点的数据量。同样,一个新节点的加入,迁 移的数据总量也只是一个新节点的数据量。之所以有这个效果是因为Q的存在,使得增加和减少机器的时候不需要对已有的数据做重新哈希(D)。这个策略的要求 是Q>>S(存储备份上,假设每个数据存储N个备份则要满足Q>>S*N)。如果业务快速发展,使得不断的增加主机,从而导致Q 不再满足Q>>S,那么这个策略将重新变化。

  通过上述的论述,我们可以看到Dryad通过一个有向无环图的策略建模算法, 提供给用户一个比较清晰的编程框架。在这个编程框架下,用户需要将自己的应用程序表达为有向无环图的形式,节点程序则编写为串行程序的形式,而后用 Dryad方法将程序组织起来。用户不需要考虑分布式系统中关于节点的选择,节点与通信的出错处理手段都简单明确,内建在Dryad框架内部,满足了分布 式程序的可扩展性、可靠性和性能的要求。在云平台分布式算法上Dryad与Dynamo分布式存储引擎相似,并且有更好的创新。


本篇文章来源于 中间件技术社区(http://middleware123.com) 原文链接:http://middleware123.com/cloud/tech/683.html

论坛徽章:
0
发表于 2011-11-09 10:22 |显示全部楼层
最近也在研究并行计算与云处理,尤其是hadoop,就像你说的一样,他分为MapReduce部分以及HDFS文件存储部分,但是个人感觉它主用应用于数据的分析处理上,但对频繁写的处理可能并不适用。其实,说白了它更像个可以并行数据分散存储的数据库,可以虚拟各个节点的数据为统一的逻辑文件适用。不知道我的理解是否真确,请指正。

论坛徽章:
0
发表于 2012-02-18 17:27 |显示全部楼层
今天赚到了,哈哈,谢谢楼主的分享,学到了很多~~顶http://www.itvcp.com/Lottery/Buy_SYYDJ.aspx期待楼主更精彩的文章!一定还要多多给我们分享分享哦!
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP