首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每周学点大数据 | No.46 MapReduce 平台的局限

每周学点大数据 | No.46 MapReduce 平台的局限

作者头像
灯塔大数据
发布2018-04-04 17:03:55
7080
发布2018-04-04 17:03:55
举报
文章被收录于专栏:灯塔大数据灯塔大数据

No.46期

MapReduce 平台的局限

Mr. 王:前面我们讲了许多基于MapReduce 的并行算法,现在我们讨论一个新话题——超越MapReduce 的并行大数据处理。虽然MapReduce 可以有效地解决很多并行计算的问题,但是经过前面对MapReduce 的使用我们也发现了一些常见的问题;这些问题用MapReduce 解决虽然是可行的,但是实现和执行起来多少会有一些不方便。

小可:嗯,MapReduce 虽然是一个很好用的平台,但是也不是完美的。

Mr. 王:的确,时至今日,Google 公司已经宣布放弃使用MapReduce 平台了。现在有很多超越MapReduce 的平台被提出。在并行计算领域中,其实有大量的计算机工作者在做新计算平台构建的研究,而且目前大多数进行并行计算的科学家和工程师所做的工作其实已经与MapReduce 无关了。也有很多好的平台被提出,比如加州大学伯克利分校的Spark 等。

小可迫不及待地说:那么继MapReduce 之后,哪一个平台是最好的呢?

Mr. 王:这样的平台有很多,它们各有各的适用范围,其实我们并不能说出哪一个平台是最好的,而是在处理具有某种特征的问题时,某个平台的效果就会比较好,因为该平台往往就是面向这种特征设计的。所以并没有万能的平台,合适的才是最好的。这些相比MapReduce来讲比较特殊的平台就像是一种特殊的舞台,某种特殊的舞蹈可能就适合在这种特殊的舞台上表演。

首先我们来介绍基于迭代平台的并行算法。MapReduce 平台已经被证明,作为一个非递归的描述语言通用平台,是非常成功的。后人开发的基于MapReduce 的各种工具包和组件包非常多,也在并行框架下实现了非常多样和复杂的功能,比如实现类SQL 语言的Hive,以及实现嵌套类型支持关系代数的工具Pig 等。但是MapReduce 并不是没有缺点的,我们在讨论MapReduce 中的图算法时发现,在MapReduce 上运行我们所设计的算法时,往往要进行多轮的迭代MapReduce,将前一轮迭代的输出结果作为下一轮迭代的输入,不断地执行,这就是循环和迭代。不仅仅是在图的处理中,循环和迭代在程序设计中也是非常普遍存在的,比如在像聚类这样的数据挖掘等中都是非常常见的。而MapReduce 本身是不能表示循环和迭代的,当需要进行这样的操作时,往往需要在框架之外用脚本来控制。

而循环结果往往是很大的,比如在计算传递闭包、PageRank 这样的算法中,每一轮迭代的输出量都是非常大的,如果平台本身不能提供一个比较好的循环和迭代处理,那么就会非常不方便。另外,每一个循环和迭代算法都要有停止判定,迭代MapReduce 也不例外,不过在测试迭代MapReduce 的算法是不是已经收敛时,往往不得不进行一轮额外的MapReduce,通过观察结果与上一轮是否有区别来判断迭代是否已经收敛。

小可:如果每一轮MapReduce 操作之后,都要再来一轮MapReduce 作为退出循环判定的话,那么效率实在是太低了。

Mr. 王:没错,所以我们要考虑一些新的策略和方法。这里我们先提出一个概念,叫作函数的不动点。

小可:我知道,不动点就是能使f(x)=x 这样的x 值。可是这和MapReduce 有什么关系呢?

Mr. 王:你想一想,循环和迭代时,我们一般以什么样的条件作为停止条件呢?

小可恍然大悟,说:当经过迭代之后结果已经不变时,停止迭代。我懂了,x 相当于输入的数据,函数f 相当于本轮迭代的处理,如果f(x)=x,这说明本轮的输出已经和输入一样,也就是结果不变,这时就可以停止迭代了。

Mr. 王点点头,说:在MapReduce 这种分布式环境下,我们也要去尝试一些分布式的不动点判定方法,此内容后面再讲。为了设计超越MapReduce、在循环和迭代的计算中表现更好的算法,我们先来看看现在的MapReduce 在处理一些典型问题时是怎么做的,在循环上有哪些部分非常浪费资源和效率低下。先来说说PageRank。

小可:我听说过PageRank,当年Google 正是凭借PageRank 这个简单却非常有效的网页重要度评价算法起家的,一步步成就了今天的Google。我很想知道它的具体思想是什么。

Mr. 王:PageRank 用于评价网页的重要程度,它的基本思想就是,对于一个网页,如果指向(有超链接连向这个网页)它的网页越多,或者指向它的网页越重要,就说明该网页的重要程度越高。在这个算法的执行过程中,我们就需要不断地根据链接去更新一些网页的重要程度。

在这些网页的重要程度更新之后,它们所指向的网页的重要程度又要由于这些网页的更新而更新,也就需要不断地循环和迭代,一直迭代到这些网页的重要程度不再变化为止。PageRank 用MapReduce 来做的话,分为三步:①对存储各个网页及其重要程度的表,与记录链接的表做一个连接,因为有链接,我们就要更新它所指向网页的重要性;②更新每个网页的rank(重要程度),就根据第1 步求得的结果来做;③由于要检测收敛情况,所以还要额外地启动一轮MapReduce 去判定算法是不是已经收敛了。

小可:这样每一轮迭代都要进行三次MapReduce,开销确实有点大。

Mr. 王:现在我们就要考虑一下,每一轮迭代的开销如此之大,会存在什么样的问题,能不能找到一些可以降低开销的地方。后面我们再说这个问题。

再来看另一个问题,就是求传递闭包。在生活中也有求传递闭包的例子,比如你有3 个朋友,这3 个朋友每个都有2 个朋友,我们就认为,你和这6 个不直接是朋友的人也是有传递朋友关系的,你们可以通过这种传递关系认识。

小可:这类似于六度空间理论啊。我们虽然不认识,但是却可以通过朋友具有认识这种可能性。

Mr. 王:没错,我们将你的朋友称作“1 跳朋友”,通过你的1 跳朋友发现的朋友称作“2跳朋友”,依此类推,可以有“n 跳朋友”。当达到第n 跳,这个朋友圈子已经不再扩大时,我们就可以称之为一个传递闭包。这个朋友圈子中的任何一个人,都不能再带来新的朋友,此时我们寻找朋友的这个过程就收敛了。

小可:这个我懂了。

Mr. 王:很好,那你尝试模仿PageRank,说说在每一轮迭代中,需要哪些MapReduce 处理?

小可:第一次MapReduce,要做一次连接,对已经通过传递过程找到的人和他们的朋友列表进行连接;第二次,要做一个去重的工作,因为单纯根据朋友列表进行连接的话,就会发生重复的情况,比如A 的朋友有B 和C,而B 同时和C 也是朋友,那么C 就会在整个过程中被加入集合两次,这时就需要去重;第三次,进行不动点的验证,我们要去测试朋友的传递闭包是不是已经收敛不再发生变化了。

Mr. 王:很好。其实这个算法和前面的PageRank 在MapReduce 执行框架下有很多相似之处,目前设计的这个MapReduce 也不是很好的,如何去改进,我们一会儿再说。

现在来讨论第三个问题,就是经典的聚类算法k-means。k-means 希望在一个空间中,这里我们用二维空间举例,将整个空间中的点就近分成k 类。具体的做法是,每一轮迭代都求出k 个均值,然后对所有的点计算与k 的距离,这个距离的具体算法可以根据实际情况而定,在一般的二维空间中,就可以用平面上的距离公式(也就是欧几里得距离),将它划分到距离最近的均值那类。当所有的点都已经归到某一类中时,计算k 个类内的均值,这样就有了新的k个均值,然后重新执行前面的步骤,直到这k 个类内的成员不再发生变化为止。

小可:那如何确定第一轮中的k 个均值呢?

Mr. 王:很好,算法的设计一定要严谨,初始化也是算法非常重要的一部分,在设计算法时不能遗漏。不过对于k-means 来说,初始的均值是可以任意取的,也可以随机选取数据中的一些点。已经证明,初始化选取的那些随机的均值不影响最终的聚类结果,只影响其收敛速度。

小可:原来如此。

Mr. 王:如果我们希望用MapReduce 来解决聚类的问题,每一轮只需要一次MapReduce即可。

现在我们来看看目前设计的这些MapReduce 算法的缺陷,也就是它们比较浪费计算效率的部分,分析这些算法不必要的开销,尝试改进提出超越MapReduce 的算法。首先我们看看比较相似的PageRank 和传递闭包。

在PageRank 中我们注意到,记录朋友关系的那张表L 从始至终是不发生变化的,按照我们之前的设计每一轮都要载入一次L,这是造成浪费的第一个地方。其二,在每一次迭代的过程中,都会由于MapReduce 的洗牌而重排L。另外,在每一次迭代中,不动点计算作为单独的MapReduce 工作执行,这也是明显的计算资源浪费。

相似地,在传递闭包的计算中也有类似的计算资源浪费情况。

朋友列表在循环中也不会发生改变,而每一次循环都要重新载入朋友,将之输入到MapReduce 中,而且同样是由于MapReduce 中的洗牌重排了朋友列表。这也是资源的浪费。

在k-means 中,虽然我们只执行了一次MapReduce,但是其实也是存在浪费的。所有点的集合每一次都要重新输入到MapReduce 中,而这些点的位置或者说值都是不发生改变的,这也是对计算资源的一种浪费。

小可:总结起来,这些问题都是由于在迭代过程中不发生改变的某个量,被频繁重复地输入算法并进行洗牌,从而造成了大量的计算开销。那么我们该如何去解决这些问题呢?

Mr. 王:事实上,解决起来并不难,我们可以借助缓存技术。

我们可以在Mapper 的输入前加一个输入缓存(MI),在Mapper 的输出后加一个输入缓存(MO),Reducer 的输入之前加一个输入缓存(RI),在Reducer 的输出后加一个输出缓存(RO)。

小可:这几个缓存如何起到提升算法效率的作用呢?

Mr. 王:我们在执行多轮的迭代MapReduce 时,相当于进行多轮的循环,而在循环中会有很多并没有发生改变的量,这些量如果每次都重新加载和重排的话,那么对系统的运行效率消耗是巨大的。而缓存恰恰可以有效地解决这些问题。

比如Reducer 的输入缓存,缓存了那些无须Map/Shuffle 访问循环不动点的数据。例如在PageRank 中,输入缓存避免了每一步都重排网络;在传递闭包中,避免了在每一步都进行重排图这样浪费计算资源而没有效果的操作。对于Reducer 的输出缓存来说,它主要保存前一轮迭代的输出结果,这样系统就可以分布式地访问前一轮迭代的输出结果了。

内容来源:灯塔大数据 文章编辑:柯一

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-07-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 灯塔大数据 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
大数据
全栈大数据产品,面向海量数据场景,帮助您 “智理无数,心中有数”!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档