8

O'Reilly CouchDB の本を読んでいます。64 ページの reduce/re-reduce/incremental-MapReduce の部分に困惑しています。O'Reilly の本には、次の文の修辞が残っています。

CouchDB のインクリメンタル リデュース機能の進化に興味がある場合は、Sawzall に関する Google の論文を参照してください。

「インクリメンタル」という言葉を正しく理解すれば、それは B ツリー データ構造におけるある種の加算演算を指します。なぜそれが典型的なmap-reduceよりも特別なのか、まだ理解できていません。おそらくまだ理解していません。CouchDB では、map 関数には副作用がないことが言及されていますが、reduce にも当てはまりますか?

CouchDB の MapReduce が「インクリメンタル」と呼ばれるのはなぜですか?

ヘルパーの質問

  1. Sawzall を使用したインクリメンタル MapReduce に関する引用を説明します。
  2. 同じこと、つまり還元を表す用語が 2 つあるのはなぜですか? 減らしてまた減らす？

参考文献

  1. Sawzallに関する Google の論文。
  2. CouchDB wiki のCouchDB ビューの紹介と、あいまいなブログ リファレンスが多数あります。
  3. CouchDB オライリーの本
4

2 に答える 2

8

user1087981 の発言に少し追加すると、CouchDB によって削減プロセスが実行されるため、削減機能は増分的です。

CouchDB はビュー関数から作成した B-Tree を使用し、本質的に値の塊で reduce 計算を実行します。これは、 O'Reilly Guideの B ツリーの非常に単純なモックアップで、引用したセクションの例のリーフ ノードを示しています。

B ツリーを減らす

では、なぜこれが漸進的なのでしょうか。最終的な削減はクエリ時にのみ実行され、すべての削減計算は B ツリー ビュー インデックスに格納されます。したがって、別の値である新しい値を DB に追加するとします"fr"。上記の 1 番目、2 番目、4 番目のノードの計算をやり直す必要はありません。新しい"fr"値が追加され、reduce 関数はその 3 番目のリーフ ノードに対してのみ再計算されます。

次にクエリ時rereduce=trueに、インデックス付きの値に対して最終的な ( ) 計算が実行され、最終的な値が返されます。reduce のこのインクリメンタルな性質により、既存のデータ セットのサイズではなく、追加される新しい値に対してのみ再計算にかかる時間が許容されることがわかります。

副作用がないことは、このプロセスのもう 1 つの重要な部分です。たとえば、reduce 関数が、すべての値を調べたときに維持されている他の状態に依存している場合、最初の実行ではそれが機能する可能性がありますが、新しい値が追加されてインクリメンタルな reduce 計算が行われると、それは機能します。同じ状態を利用できないため、正しい結果が得られません。これが、reduce 関数が副作用のないものである必要がある理由、または user1087981 が言うように「参照透過」である理由です。

于 2012-06-28T05:16:19.170 に答える
8

あなたがリンクしたこのページはそれを説明しました。

ビュー (CouchDB の map reduce の要点) は、最後のインデックス更新以降に変更されたドキュメントのみを再インデックス化することで更新できます。それが増分部分です。

これは、reduce 関数に参照透過性を要求することで実現できます。つまり、与えられた入力に対して常に同じ出力を返すということです。

reduce 関数は、配列値の入力に対して可換かつ結合的でなければなりません。つまり、同じ reducer の出力に対して reducer を実行すると、同じ結果が得られます。そのwikiページでは、次のように表現されています。

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

Rereduce は、いくつかのレデューサー呼び出しから出力を取得し、それをレデューサーで再度実行する場所です。これは、CouchDB がレデューサーを介してバッチで送信するために必要になることがあります。そのため、削減する必要があるすべてのキーが一度に送信されるとは限りません。

于 2012-06-28T01:29:42.240 に答える