hadoop - 能否自定义 Hadoop 的 Shuffle/Sort(或分区)阶段来执行图形遍历？

Question

我还在学习 MapReduce 框架，具体由 Hadoop 实现，我想知道是否可以修改它来执行以下任务:

Map() 函数将发出 (key,value) 对，其键是大小为 2 的数组，比如 int[2]。我希望将包含两个共同整数中的任何一个的每一对映射到同一个 reducer。

例如，如果 Map() 发出:([2,3],4),([2,4],5),([6,5],2),([5,7], 1)，那么 Reduce1 应该接收前两对，Reduce2 接收后两对(前两对共享 2，后两对共享 5)。这可以看作是一个连通分量问题，其中顶点是 int[] 中的整数，边在同一 int[] 中的任意两个整数之间共享。

Answer 1

算法的改变，你可能可以实现这个——但是你需要将每条边发射两次

对于您当前输出的每条边，您应该为两个顶点 ID 输出它们，修改输出值以包括另一条边、权重和可选的方向(如果边方向对您的算法很重要)。

所以不是这个:

([2,3],4)
([2,4],5)
([6,5],2)
([5,7],1)

输出这个(S表示键是源，D表示键是目的地):

(2, [3, 4, S])
(3, [2, 4, D])
(2, [4, 5, S])
(4, [2, 5, D])
(6, [5, 2, S])
(5, [6, 2, D])
(5, [7, 1, S])
(7, [5, 1, D])

现在在你的 reducer 中，你将按顶点 ID 分组，并且将能够迭代包含其他顶点 ID、权重和方向的其他元组:

(2, [3, 4, S])
(2, [4, 5, S])

(3, [2, 4, D])

(4, [2, 5, D])

(5, [6, 2, D])
(5, [7, 1, S])

(6, [5, 2, S])

(7, [5, 1, D])

您仍然需要注意每条边可能会被处理两次，尤其是当边存在于两个顶点之间的两个方向上时。