8

我正在阅读 O'Reilly CouchDB 的书。我对第 64 页上的 reduce/re-reduce/incremental-MapReduce 部分感到困惑。O'Reilly 书中的句子中留下了太多的修辞

如果您有兴趣推动 CouchDB 的增量减少功能的发展，请查看 Google 关于 Sawzall 的论文，...

如果我正确理解“增量”这个词，它指的是 B 树数据结构中的某种加法运算。我还不明白为什么它比典型的 map-reduce 有点特别，可能还不理解它。在 CouchDB 中，它提到 map 函数没有副作用 - reduce 也适用吗？

为什么 CouchDB 中的 MapReduce 被称为“增量”？

帮助问题

  1. 用 Sawzall 解释关于增量 MapReduce 的引用。
  2. 为什么同一事物有两个术语，即减少？减少和重新减少？

参考

  1. 一篇关于Sawzall的 Google 论文。
  2. CouchDB wiki 中的CouchDB 视图介绍和许多模糊的博客参考。
  3. CouchDB O'Reilly 书
4

2 回答 2

8

你链接的这个页面解释了它。

可以通过仅重新索引自上次索引更新以来已更改的文档来更新视图（这是 CouchDB 中 map reduce 的全部要点）。那是增量部分。

这可以通过要求 reduce 函数具有引用透明性来实现，这意味着它总是为给定的输入返回相同的输出。

对于数组值输入，reduce 函数还必须是可交换和关联的，这意味着如果您在同一个 reducer 的输出上运行 reducer，您将收到相同的结果。在该 wiki 页面中，它表示为：

f(Key, Values) == f(Key, [ f(Key, Values) ] )

Rereduce 是您从多个 reducer 调用中获取输出并再次通过 reducer 运行的地方。这有时是必需的，因为 CouchDB 通过 reducer 批量发送内容，因此有时并非所有需要减少的键都会一次性发送。

于 2012-06-28T01:29:42.240 回答
8

只是稍微补充一下 user1087981 所说的，reduce 功能是增量的，因为 reduce 过程是由 CouchDB 执行的。

CouchDB 使用它从视图函数创建的 B-Tree，本质上它以值块的形式执行归约计算。这是O'Reilly 指南中一个非常简单的 B-Tree 模型，显示了您引用的部分中示例的叶节点。

减少 B 树

那么，为什么这是增量的？好吧，最终的reduce只在查询时执行，所有reduce计算都存储在B-Tree视图索引中。因此，假设您向数据库添加了一个新值，该值是另一个"fr"值。上述第 1、2、4 个节点的计算无需重做。添加新"fr"值，并且仅为该第 3 个叶节点重新计算 reduce 函数。

然后在查询时rereduce=true对索引值执行最终 ( ) 计算，并返回最终值。您可以看到，reduce 的这种增量性质允许重新计算所花费的时间仅与添加的新值相关，而不是与现有数据集的大小相关。

没有副作用是这个过程的另一个重要部分。例如，如果您的 reduce 函数在遍历所有值时依赖于维护的其他状态，那么这可能适用于第一次运行，但是当添加一个新值并进行增量 reduce 计算时，它会'没有相同的状态可用 - 因此它无法产生正确的结果。这就是为什么 reduce 函数需要无副作用的原因，或者正如 user1087981 所说的那样“引用透明”

于 2012-06-28T05:16:19.170 回答