7

我正在使用 Hadoop 分析非常不均匀的数据分布。有些键有数千个值，但大多数只有一个。例如，与 IP 地址相关联的网络流量将有许多数据包与一些健谈的 IP 相关联，而只有少数与大多数 IP 相关联。另一种说法是基尼指数非常高。

为了有效地处理这个问题，每个reducer 应该获得一些高音量键或大量低音量键，以便获得大致均匀的负载。如果我正在编写分区过程，我知道该怎么做：我将获取keys映射器生成的（包括所有重复键）的排序列表以及减速器的数量，N并将拆分放在

split[i] = keys[floor(i*len(keys)/N)]

Reduceri将获得k诸如split[i] <= k < split[i+1]for0 <= i < N-1和split[i] <= kfor 的键i == N-1。

我愿意用 Java 编写自己的分区器，但Partitioner<KEY,VALUE>类似乎一次只能访问一个键值记录，而不是整个列表。我知道 Hadoop 对映射器生成的记录进行排序，所以这个列表必须存在于某个地方。它可能分布在几个分区器节点中，在这种情况下，我会在其中一个子列表上执行拆分过程，并以某种方式将结果传达给所有其他分区器节点。（假设选择的分区节点看到一个随机子集，结果仍然是近似负载平衡的。） 有谁知道排序的键列表存储在哪里，以及如何访问它？

我不想编写两个 map-reduce 作业，一个是查找拆分，另一个是实际使用它们，因为这看起来很浪费。（映射器必须做两次相同的工作。）这似乎是一个普遍的问题：不均匀分布很常见。

4

2 回答 2

2

I've been thinking about this problem, too. This is the high-level approach I would take if someone forced me.

  • In addition to the mapper logic you have in place to solve your business problem, code some logic to gather whatever statistics you'll need in the partitioner to distribute key-value pairs in a balanced manner. Of course, each mapper will only see some of the data.
  • Each mapper can find out its task ID and use that ID to build a unique filename in a specified hdfs folder to hold the gathered statistics. Write this file out in the cleanup() method which runs at the end of the task.
  • use lazy initialization in the partitioner to read all files in the specified hdfs directory. This gets you all of the statistics gathered during the mapper phase. From there you're left with implementing whatever partitioning logic you need to correctly partition the data.

This all assumes that the partitioner isn't called until all mappers have finished, but that's the best I've been able to do so far.

于 2012-08-26T14:52:42.247 回答
1

据我所知 - MR 处理中没有一个地方存在所有密钥。不仅如此 - 不能保证单台机器可以存储这些数据。我认为这个问题在当前的 MR 框架中没有理想的解决方案。我这么认为是因为要获得理想的解决方案 - 我们必须等待最后一个映射器的结束，然后才能使用这些知识分析密钥分布和参数化分区器。
这种方法将使系统显着复杂化并增加延迟。
我认为好的近似值可能是对数据进行随机抽样以了解密钥分布的概念，然后让分区器根据它工作。
据我了解，Terasort 实现正在做一些非常相似的事情：http ://sortbenchmark.org/YahooHadoop.pdf

于 2012-08-25T12:24:51.663 回答