mapreduce作业中的"Combiner"类

Question

组合器在Mapper之后运行,在Reducer之前,它将接收Mapper实例在给定节点上发出的所有数据作为输入.然后将输出发送到Reducers.

而且,如果reduce函数既是可交换的又是关联的,那么它可以用作组合器.

我的问题是" 交换和联想 "这个词在这种情况下意味着什么？

Answer 1

假设您有一个数字列表,1 2 3 4 5 6.

这里的关联意味着您可以执行操作并将其应用于任何子组,然后将其应用于这些组的结果并获得相同的答案:

(1) + (2 + 3) + (4 + 5 + 6)
  ==
(1 + 2) + (3 + 4) + (5) + (6)
  ==
...

可以将括号视为组合器的执行.

交换意味着订单无关紧要,因此:

1 + 2 + 3 + 4 + 5 + 6
  ==
2 + 4 + 6 + 1 + 2 + 3
  ==
...

例如,添加,适合此属性,如前所述."Maximum"也符合上述属性,因为maxs的最大值是max.max(a,b)== max(b,a).

中位数是一个不起作用的例子:中位数的中位数不是真正的中位数.

不要忘记组合器的另一个重要属性:键/值的输入类型和键/值的输出类型必须相同.例如,您不能接受字符串:int并返回一个字符串:float.

通常情况下,减速器可能会输出某种字符串而不是数值,这可能会阻止您将减速器作为组合器插入.

Answer 2

对于可交换性,假设你的reducer可以用一个叫做f()的函数(在数学术语中)来表示.如果f(a,b)= f(b,a),那么你的reducer是可交换的,例如:

• sum(A,B)与sum(B,A)相同
• xor(A,B)与xor(B,A)相同
• 的concat(A,B)是不一样的concat(B,A)

对于关联性,属性是f(f(a,b),c)= f(a,f(b,c)).例如:

• (A + B)+ C与A +(B + C)相同
• (A - B) - C是不一样的A - (B - C)

因此,在Map/Reduce的上下文中,您的reducer必须遵守这两个属性.例如,如果您的reducer只执行sum()或max(),它会同时考虑这两个属性,但是像mean()或median()这样的东西不会,因此您不能将它用作组合器.

我个人认为组合器是在地图阶段之后在内存中运行的迷你减速器,作为减少网络流量的优化,如果你看到这样的Map/Reduce,交换性/关联性实际上是有意义的: