Hadoop MapReduce デザインパターン1章〜3章

Hadoop MapReduce デザインパターン ―MapReduceによる大規模テキストデータ処理

ずっと原書であるData-Intensive Text Processing With MapReduce (Synthesis Lectures on Human Language Technologies)を読もうとは思っていて、Pre-Production Manuscript(PDF)とかもチラ見していたのですが、Hadoop Conference Japan 2011 Fallで売っていたのでAmazonの予約をキャンセルしてその場で買いましたｗ

ちなみに、私のスペックを説明しておくとtry-hadoop-mapreduce-java - Hadoop MapReduceを気軽に試せるようにすることを目的としています - Google Project Hostingの作者なのでMapReduceの基本は理解しているつもりですが、仕事でMapReduceは書いたことが無いので経験値的には微妙です。あと、数学やら自然言語処理に関しては知識がないに等しいです。

1章　イントロダクション

• Hadoop、ビッグデータ、言語処理、クラウド、スケールアウトみたいな単語について触れています。以前からHadoop界隈をウォッチしている方ならばだいたい知っていそうな話が載ってます。

2章　MapReduceの基礎

• 象本ことHadoop 第2版のMapReduce周りを要約したような内容です。ただ、こちらからいきなり読んでもよく分からないのではないかという気もしました。象本を読んでから再確認する感じで読んだほうがよいと思います。
  • 象本は読んでなくてもある程度Hadoopを触ったりしていれば読める気もします。といっても、Hadoop触ってて象本読んでない人がいるとは思えませんが。。

3章　MapReduceアルゴリズムの設計

• 本書で一番重要な章だと思います。そして、4章以降と比べてもそんなに難しくないです。
• 擬似コードはフィーリングで読めますが、判例が欲しかった気もします。この記法は一般的だったりするのでしょうか？

in-mapper combiningパターン

• combinerをmapperの中で実装するというパターンです。
• combinerと違って必ず実行されるという保証があります。
  • combinerは最適化としてMapReduce実行フレームワークが複数回実行する可能性があるだけで、実際に実行される保証はありません。
• メモリサイズについては一定間隔で出力すれば回避できます。
• 以上を考えると、combinerを使うことって実際にはないのかなと思いました。実際に普段からMR書いている方に聞いてみたいです。

pairsとstripesパターン

• 複数のキーにまたがる演算を行う場合のデザインパターンという理解です。例えば、group byでsumを求めるとして、その集約キーが2つある場合の実装方法です。2つある場合にmapper側ではレコードの集約キーと値をそのままreducer側に送るのがpairsパターン。mapper側で予め第2集約キー単位に値を合計した上で、第1キーでまとめてreducerに送るのがstripesパターンになる、、、という理解です。
  • ちなみに、pairsはキーと値のペアをそのままreducerに送るという意味で何となく分かるのですが、stripesはどのへんがstripesなのでしょうか。。。
• キーが単一の場合はmapperの出力のキー側にキーを入れるしか選択肢が無いわけですが、キーが2つあると第2キーをキーの側に入れるという選択肢と、値の側に入れるという選択肢が生まれるということだと思います。
• 書籍内では共起行列を例にして解説しています。詳細はHadoop MapReduce デザインパターンの3章まで読んでみた。 - watawata日記を読むのがよいと思います。共起行列の説明からサンプルコードまで載っていて素晴らしいです！
• 両者のパターンにおいて当たり前ですがトレードオフがあり、pairsとstripesの中間のsub-stripesについても紹介されています。
  • ちなみに、sub-stripesのメモリの制約ってreducer側の話ですよね。本文では言及されていない気がしたので、誰か教えてくれると嬉しいです(^_^;)
    • 2012-08-18追記 改めて読みなおしたのですが、やはりreducer側の話ですね。stripesの場合はreduceメソッドである語に共起する全ての語の共起数をメモリ上に展開することになるため、ボキャブラリが大きくなるとメモリが足りなくなります。そのため、共起する語の側を複数のバケットに分割することで複数のreduceメソッドに処理が分割されるのでメモリの制約を回避できるようになります（当然、出力する際のキーからはバケットに分割した際のキー（ハッシュ値など）は除去することになります）。

order inversionパターン

• reducer側で受け取るキーを制御することで、例えば相対頻度の計算ができたりしますよという内容です。象本の結合を読んでいれば、あーそうねーみたいな内容だと思います。

セカンダリソートと結合

• 象本の結合を読んでいれば(ry
• ちなみに結合に関してはJoin Algorithms using Map/Reduce(PDF)もいいかと思います。

まとめ

• MapReduceフレームワーク上でアルゴリズムを考える上での可変パラメーターが列挙されている感じです。押さえておくと良いと思います。

前編まとめ

まずは前編として1章〜3章について書きました。というのも、これを書くだけで3時間近くかかったので。。一応読み終えていたのですが、いざ書こうとすると読み直したり、色々考えたりする点が多く、時間がかかってしまいました。おかげで理解も深まったので結果オーライですね。

後編は残りの4章から7章を書く予定です。ちなみに、私自身は数学やら自然言語処理に関しては知識がないに等しいレベルなので、6章に関してはほぼ理解できませんでした。そんな私でも理解できた部分もあったので、その辺りについて書けるといいなと思ってます。

2011-10-10追記

後半はHadoop MapReduce デザインパターン4章〜7章 - n-3104の日記です。