MapReduceの本質
また一つ、『計算機プログラムの構造と解釈』から面白いネタが飛び出してきた。
一見なんでもないようなschemeの例題から、GoogleのIndex生成アルゴリズムとして名高いMapReduceの概要を理解するための機会を得た。
あの例題の本質は何だったのか？
きっかけは、先日の「プロセスの抽象化（シーケンスへの作用）」というエントリーに関して、会社の先輩から興味深い指摘をいただいたことだった。エントリーの内容は、抽象化によって「木構造の要素に対して作用する手続き」を改善するという話だが、その改善前後の手続きをもう一度掲載する。
【A】改善前の実装
(define (sum-odd-squares tree) (cond ((null? tree) 0) ((not (pair? tree)) (if (odd? tree) (square tree) 0)) (else (+ (sum-odd-squares (car tree)) (sum-odd-squares (cdr tree))))))
【B】改善後の実装(define (sum-odd-squares tree) (accumulate + 0 (map square (filter odd? (enumerate-tree tree)))))
僕は【B】への改善の本質的な目的として「可読性の向上」と、「部品の再利用性向上」を挙げた。しかし、先輩から以下の指摘を受けた。
・【A】はそこまで可読性が低いのか？
・【B】では明らかに計算量が増加していることをどう説明するのか？
確かにその通りだ。特に計算量の問題は明らかで（リスト走査の回数が増えている）、そのことには前の記事を書いた段階でも気づいていたものの、「可読性の確保（今や自明ではないが…）」と「部品化による再利用」を行うことがこの例題で伝えたい本質なのだと考えてスルーしてしまった。
実際どの程度計算量が増加していたのか。【A】の計算量（シーケンスに対する全走査１回）をnとした場合、【B】では約３nの計算量を要することがわかる。
n + n + n/2 + n/2 = 3n
※enumerationとfilterが全走査であるため「n」、mapとaccumulationは奇数要素のみに対する作用であるため「n/2」となる。
つまり、計算量を３倍にしてでも【B】のスタイルをとる意味はあるのか？というのが先輩の問いだった。しばらく考えたものの、僕には明確なメリットを提示することができなかった。
MapReduceの戦略
先輩の出した答えは、「並列処理による分散が可能になる」ということだった。
つまり、【B】の場合、accumulation以外の関数（map、filter、enumeration）は引数として与えられるリストからしか影響を受けないため（環境が閉じているため）、各々の処理を個別的に切り出し、並行にスケールできるという話だ*1。例えば、【B】に渡された木構造が超巨大だったとしても、それをいくつかに分割して、走査処理を別のマシンで同時に行い、最後にそれぞれの走査結果を集計(accumulate)すればよい。accumulationを除けば、処理速度は論理的にはマシンの台数に比例して早くなるはずである。もちろん、【A】の設計では、全ての処理要素がメインの再帰手続き内に混在しているため、部分的に切り出してスケールすることはできない。
そして、これこそがGoogleのMapReduceアルゴリズムがとっている戦略に他ならないのだと。もう目から鱗でした。
MapReduceについては、以下の記事が非常によくまとまっている。
Radium Software Development ― MapReduce
map タスクは，膨大な量の元データを分解し，必要な情報を抽出し，有用な形へと変換し出力する，いわゆる「フィルター」の役目を担う。 reduce タスクは，抽出された情報を集約し，一塊のデータとして出力する，いわゆる「アグリゲーター」の役割を担う。このうち map タスクが純粋にフィルターとして振舞う（副作用が無い）ならば，この処理を複数のマシンで手分けして行うことができる。たとえ処理対象のデータがテラバイト単位で存在したとしても，その処理を数百台のマシンへと効率良く分配することができたならば，現実的な時間内で処理することが可能になると考えられる。
今回の例題に置き換えると、mapタスクは map、filtere、numeration であり、reduceタスクは accumulation にあたる。
本当に面白いと思うのが、この単純な「mapによるリソースのフィルタリング → reduceによる集計処理」というモデルで様々な処理を実装できることだ。先に引用した記事では、WEB上の単語出現回数の集約と、逆リンクリスト生成の例が出てきている。
それから、もうひとつ気になる点。mapタスクはスケールするが、reduceタスクはスケールしないという話。
MapReduce を構成するタスクのうち map タスクが並列実行可能であることは自明に思われる。他方で reduce タスクの方は，個々の操作が可換 (commutative) ないしは結合法則を満たす (associative) とすれば階層的に並列実行することが可能だが， MapReduce においてはそのいずれも前提として設けられていない。（中略）明らかに map タスクの方が並列実行に特化されており， reduce タスクの並列性の低さが目に付いてしまう。
このような map と reduce の間に見られる非対称性は，恐らく Google の扱う問題領域の特殊性から生じるものであろうと思われる。
交換法則や結合法則を満たさない集約処理の具体的は述べられていないが、きっと色々難しいことがあるんだろう（適当）。ただ、例えばIndex生成処理の、パフォーマンス上のクリティカル・ポイントは間違いなくmapタスクだ。それを考えればmapタスクのスケーラビリティが充分に高ければよくて、それがGoogleにとっての最適解なのかもしれない。reduceタスクのスケーラビリティを無理に高めようとするとアルゴリズムの複雑度が高くなって、デメリットの方が大きくなってしまうとか。例えば。
とにかく、WEB上の膨大なリソース（テキスト、画像、映像、リンク）を何らかの規約に基づいてフィルタリングし、それをまた何らかの規約によって集計する。Googleにとってこれほど最適かつ簡潔なアルゴリズムのモデルはほかにないだろう。
Joel Spolskyは言いました
関数プログラミングを理解していなければ、GoogleをあれほどスケーラブルにしているアルゴリズムであるMapReduceは発明できない。MapとReduceという用語はLispと関数プログラミングから来ている。純関数プログラムは副作用がなく容易に並列化できるということを6.001に相当するプログラミングの授業で聞いて覚えている人には、MapReduceは容易に理解できる。
今年に入ってから社内でSCIP勉強会を始めた。そのきっかけとなったJoelの記事に上のような一節がある。これを最初に読んだときに比べ、確実に階段を昇っていることが感じられて非常にうれしい。そして、大きな気付きを与えてくれた先輩には感謝感激雨あられです。
