MapReduce 框架输出列表与完全确定值

Question

我对MapReduce的初步理解是，它是为reduce函数的输出与reduce函数的输入兼容的问题而设计的，以便在必要时可以重复调用它——将值彼此合并。这似乎得到了原始 Google 论文的支持，其中说：“输入键和值与输出键和值来自不同的域。此外，中间键和值与输出键来自相同的域和价值观。”

map(k1,v1) → list(k2,v2)
reduce(k2,list(v2)) → list(v2)

根据这种理解，我认为您可以假设，如果一个键仅映射到一个值，则可以完全绕过并永远不会调用reduce。 至少在 MongoDB 中似乎是这样。只要一个键映射到多个值，该过程就会不断减少，直到达到该键的一个值。

解释中缺少的是 MapReduce 本身的整体类型签名，我认为最有用的是：

MapReduce(list(k1,v1)) → (k2 → v2)

例如最终产品是键到单个值的唯一映射。

但是，我对在其他地方读到的内容感到困惑。首先要摆脱的是维基百科对Reduce输出的扩展：

Map(k1,v1) → list(k2,v2)
Reduce(k2,list(v2)) → list((k3, v3))

然后给出了一个示例，计算某个人在社交网络上的特定年龄的平均联系人数量：

function Map is
    input: integer K1 between 1 and 1100
           representing a batch of 1 million social.person records
    for each social.person record in the K1 batch do
        let Y be the person's age
        let N be the number of contacts the person has
        produce one output record (Y,(N,1))
    repeat
end function

function Reduce is
    input: age (in years) Y
    for each input record (Y,(N,C)) do
        Accumulate in S the sum of N*C
        Accumulate in Cnew the sum of C
    repeat
    let A be S/Cnew
    produce one output record (Y,(A,Cnew))
end function

他们强调“如果处理减少超过一次，记录中的计数信息很重要。如果我们不添加记录的计数，计算出的平均值将是错误的。”

但是在多重归约的情况下谁在进行合并平均呢？这里的变量名称并没有真正暗示Reduce 的输出会自动反馈到其中。他们没有指出

(Y,(N,1))

具有

N

作为一个微不足道的平均值……他们可以说

A1=N

并发出

(Y,(A1,1))

。当他们枚举Reduce中的输入记录时，他们说的是

(Y,(N,C))

而不是

(Y,(A,C))

。

他们还说“MapReduce 框架”与函数式编程 map/reduce 不同，因为它们不能保证给出单个结果，只能给出一个列表：

“因此，MapReduce 框架将一个（键，值）对列表转换为另一个（键，值）对列表。这种行为与典型的函数式编程映射和化简组合不同，后者接受任意值列表并返回一个单一值，组合了映射返回的所有值。”

那么如果多次调用Reduce，是否会输出一个列表中具有相同键的多条记录呢？这意味着您必须在读取输出的任何内容中进一步对代码进行平均。在最坏的情况下，Reduce 可能会在每个 Map 输出上一次调用一个...增加开销却没有任何好处。

从函数式编程的角度来看，我很困惑为什么不做出选择来确保 MapReduce 完全合并值。为什么框架不会在产生输出之前继续将Reduce 的输出反馈到自身中...当列表达到一个元素时停止？

否则，基本上每个人在读取输出元组时不都需要重用Reduce的代码吗？从语义上讲，他们似乎必须这样做——因为他们无法先验地知道有多少个群体将聚集在一起。提供具有相同密钥的输出列表似乎只会增加无法有意义地采取行动的工作。

Answer 1

专为reduce函数的输出与reduce函数的输入兼容的问题而设计，以便在需要时可以重复调用

这并不总是（甚至偶尔）正确，这可能会澄清你剩下的问题。

正如您所指出的，如果减速器多次运行，则平均不起作用，排名算法也将是另一个在这里不起作用的常见用例。在我职业生涯的早期，我编写了数百个 MapReduce 作业，但我很难想到任何可以支持重新运行减速器的作业。