6

我的理解是计算百分位数，数据需要排序。如果大量数据分布在多个服务器上，而无需移动，这是否可行？

4

3 回答 3

2

While MapReduce as a paradigm does not looks suited for the problem, hadoop's implementation of MR - is.
Hadoop's implementation of map reduce is based on distributed sort - and it is what you need. Hadoop is doing sort by moving data between servers only once - not that bad.
I would suggest to look onto hadoop terasort implementaiton which illustrate the good (and probabbly the best) way to sort massive data with hadoop. http://hadoop.apache.org/docs/current/api/org/apache/hadoop/examples/terasort/package-summary.html

于 2012-09-16T06:20:07.477 回答
2

我会首先在一台机器或多台机器上创建一个直方图。一旦您对可能值的桶的每个可能值进行计数，您可以在需要时将它们组合起来。使用直方图的好处是它具有 O(1) 插入/排序时间而不是 O(log n) 并使用 O(M) 空间，其中 M 是可能值或桶的数量，而不是 O(N)，其中 N是样本数。

直方图是自然排序的，因此您可以获得总计数并通过从任一端计数来找到百分位数。

于 2012-09-16T09:36:34.930 回答
0

你的问题的答案是肯定的，有可能。但 Map-Reduce 并不是真正为此类任务而设计的。Map-Reduce（例如在 Hadoop 集群中使用）适用于非结构化或半结构化数据。虽然它具有处理其他种类的能力，但它并不是最适合它。（我在一家公司有一个项目，他们想在 Hadoop 集群中分析 XML……这不是最有趣的事情。）

这篇学术文章描述了 Map-Reduce 在结构化数据上的一些问题，并提供了“Clydesdale”的替代方法。（我从未听说过或使用过这个，所以我既不能认可它，也不能说出它的优点/缺点。）

我正在寻找更多提供解释和替代方案的链接。

于 2012-09-16T03:40:32.473 回答