algorithm - mapreduce 中是否有可以并行执行的非交换reducer？

Question

中值和均值等一些运算是不可交换的。这种情况下似乎只能有一个reducer，因为reducer需要有全局视图。map-reduce 中是否有可以并行执行的非交换reducer？当遇到非交换操作时，人们真的会使用 map-reduce 吗？或者只是在一些非常强大的机器上运行它？是否有将非交换运算分解为交换运算的常用方法？

谢谢

Answer 1

我不知道“交换”是否是在这里使用的正确词，但我明白你在说什么。

在 hadoop 中，post-mapping 阶段实际上分为两个步骤： aCombiner和 a Reducer，具有相同的签名。在Combiner映射器上运行以减少输出的大小，然后再进行键排序并发送到减速器。如果您只指定 a Reducer，那么它将用于两者；但是您可以将它们分开来做比您想象的更多的事情。

进行计数操作的简单案例使用计数归约器，可用于合并步骤和归约步骤。这减少了通过网络多次发送相同密钥的需要。

您可以通过定义不同的组合器和归约器来实现类似的计算平均值的效率。例如，映射器输出一个(number, 1)对应于数值和计数为 1 的值。组合器可以将一组值映射到一个(sum, count)元组或一个(mean, count)元组，而归约器可以使用计数的权重来聚合这些值以产生平均值。（顺便说一句：使用Kahan summation可以大大减少添加大量数字的错误）。这允许映射器进行一些组合，就像在一个简单的计数示例中一样。

你可以在一个 map-reduce 步骤中做很多聪明的事情。但是，我认为这对于中位数来说是不可能的。在这种情况下，您实际上必须通过一台机器的状态发送所有数字。