6

我正在尝试了解 hadoop 和 map/reduce 的界限，这将有助于了解我们知道 map/reduce 无法解决的非平凡问题或问题类别。

如果改变问题的一个因素可以简化 map/reduce，那肯定会很有趣。

谢谢

4

5 回答 5

6

想到两件事：

  1. 任何需要实时/交互式/低延迟响应时间的东西。提交给 Hadoop 的任何作业都会产生固定成本。

  2. 任何不平行的问题都尴尬。Hadoop 可以处理很多需要数据之间简单的相互依赖关系的问题，因为记录是在 reduce 阶段连接的。但是，某些图形处理和机器学习算法很难在 Hadoop 中编写，因为存在太多相互依赖的操作。一些机器学习算法需要非常低的延迟，随机访问大量数据，而 Hadoop 不提供开箱即用的功能。

于 2010-08-06T15:51:41.240 回答
3

您所说的“我们知道 map/reduce 无法提供帮助”并不完全清楚。其他答案似乎满足于一些例子，当它不是微不足道的，容易或不太困难如何使用 map reduce 来获得一些显着的加速时，但对于一个人来说容易的事情可能对其他人来说并不容易，而对于重要的人来说也是如此。我个人会对一个说某事无法完成的定理感到更满意。如果我们看计算复杂度，有一类难以并行化的问题，即 P 完全问题。众所周知的此类问题是上下文无关语法识别（对编译器很重要）、线性规划和一些压缩问题。维基百科条目有更多。

有些人正在为 map reduce 制作新的复杂性类。我非常怀疑，但陪审团不知道这些会有多大用处。

另一个问题是：我们可以在 map reduce 中模拟任何并行算法吗？当然，我们无法通过 P-complete 问题 map reduce 我们的方式，但也许有一些问题可以并行解决，但在 mapreduce 中无法解决。我不知道有任何此类问题，但我知道一篇指向相反方向的论文，尽管是在 Michael T. Goodrich 的“Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry”的一些假设下

在实践中，我们几乎没有时间思考 map reduce 的方式和开发特定于这个模型的算法技术，我看到新的问题落在 map reduce 解决方案上。当一切尘埃落定时，我们可能会发现 mapreduce 比最初看起来更强大。

于 2010-10-05T07:57:59.540 回答
0

我认为任何无法通过分而治之解决的问题都不适用于 hadoop。如果算法可以修改为能够创建子任务，那么我猜它可以很好地在hadoop下运行。

为了增加您的问题（而不是答案，我是否将这部分评论作为评论？），如果有我可以将问题分解成的子任务，但没有明确的方法来完成filterhadoop 的阶段？我想人们仍然可以在map阶段使用 hadoop 并在单台机器上进行缩减。

于 2010-08-06T19:46:04.797 回答
0

对 Gangadhar 的回应（对不起，评论框中没有足够的空间）：

我喜欢你关于分而治之的回答，但我有一个警告要补充。Mapreduce 不能很好地处理分治算法的递归方面，因为某些 d/c 算法的子问题的组合取决于最终减少到一个键。以合并排序算法为例（暂时忽略排序在 Hadoop 中是微不足道的，因为其 Mapreduce 实现的关键排序属性）：您将使用映射器将数据划分为两个块，使用任意 id 作为钥匙。您的 reduce 阶段会将其各自键的值列表合并在一起。

7 3 2 4 1 5 8 9 would map to 
1->[[7],[3]] 2->[[2],[4]] 3->[[1],[5]] 4->[[8],[9]] would reduce to
3,7 2,4 1,5 8,9 would map to 
1->[[3,7],[2,4]] 2->[[1,5],[8,9]] 
etc.

您会看到键的数量减少了两个（或您用于 d/c 算法的任何分块因子），并且最终应该减少到一个用于排序列表的键。这对并行性不利。

所以分而治之的划分方面显然对于 mapreduce 是必要的，但是我们在征服阶段也需要数据并行性，这样你的结果就是一些数据并行项的集合。FFT 是与 mapreduce 配合得很好的分治算法的一个很好的例子。

于 2010-08-19T18:37:18.053 回答
0

正如其他人所说：问题必须易于切割成可以独立处理的碎片。

因此，让我给你举两个我过去作为 WebAnalytics 架构师的例子（基本上我试图做 Hadoop 现在提供的东西......没有 hadoop......在具有多个 CPU 内核的单个系统上使用 bash shell 脚本）。我希望这两个能让你对这些边界在现实生活中的样子有所了解。

语境：

假设您有大量来自网络服务器的日志。并且您想分析访问者的行为。您需要一个属性来可靠地告诉您哪个请求是由哪个用户完成的。

我的两个例子：

  1. 您想要用来关联行为的属性在某些部分是不好的（比如说：sessionid）。如果网站使用 JavaScript 放置这个因素，这通常会发生（YUCK！）。然后就变得非常困难（根据我的经验：几乎不可能）来划分纠正这个相关属性的工作。这个“必须”在“一个巨大的分区”中完成，因此 MapReduce 无法帮助您。
  2. 现在，将所有数据分成可管理的块所需的属性是可靠的（即单个浏览器在站点上所做的一切），创建大量数据子集变得非常容易。您可以轻松地将大型站点的处理扩展到数百个系统。

过去有人曾告诉我，流体动力学方程 (Navier–Stokes) 不能拆分为“Mapreducable”部分。尽管我确实看到了为什么这是正确的一些逻辑（流体的每个部分都会影响流体的每个其他部分）；我应该明确一点，我什至不会尝试理解这些方程式。

我希望这些例子能帮助你找到边界。

于 2010-08-07T19:06:32.337 回答