hadoop - 如何在 Hadoop 中实现前缀和？

Question

我无法尝试在 Hadoop 中实现前缀和。我理解算法:

• 每个节点都有自己的数据“桶”
• 每个节点对桶求和
• 每个节点将他的总和广播给“以下”节点
• 每个节点现在可以对“先前”数据求和，并计算其桶中每个元素的前缀和

但是我该如何实现呢？我如何知道使用了多少个节点？我怎么知道“我是”哪个节点？ Hadoop 文档非常缺乏信息且令人困惑。我想通过使用范围内的键 (nodeID, numberOfNodes) 多次发出总和来广播数据，以便每个 reducer 都可以对其求和。我感到迷茫，我在 Hadoop 方面没有太多经验。谁能帮帮我？

Answer 1

您可以在 Hadoop 中通过三个任务完成此操作:

1. 第一个任务(只有一个 reducer)

   • 映射器采样数据并将其作为(0, value) 对发送
   • Reducer 在未来的任务中从配置中读取 r 个 reducer，按升序对数据进行排序并选择 r - 1 个分割点。将它们保存为(null, value)

   假设结果存储在 hdfs 上的 partition 目录中。

2. 第二个任务(使用 r 个 reducer)

   • Mappers 从partition 中读取数据(只有一个文件，每一行都是一个split point int 升序的值)并保存在vector 中。使用二进制搜索，将数据映射到(p, value)，其中p 是从0 到r - 1 代表数据所在的 reducer。
   • Partitioners 是一个身份分区器 - 对于给定的 (key, value) 对，它将它发送到 key parititoner。
   • Reducer 计算他从映射器获得的值的数量。将结果保存为 (reducer, size) 对。

   假设结果存储在 hdfs 上的 sizes 目录中。

3. 第二个任务(使用 r 个 reducer)

   • 映射器——与第 1 号任务相同。 2
   • 分区器 - 与第 1 号任务相同。 2
   • Reducer 从sizes 目录中读取所有reducer 窗口的大小。该目录包含的文件的行仅包含整数对 - reducer 的数量及其数据的大小。计算数量小于当前 reducer 的 reducer 的窗口总大小作为 total。对数据进行排序，并将第 i 个值保存为 (total + i, value)