Hadoop MapReduce デザインパターン まとめ

手に入ったので読みつつ必要なところをまとめていく。

2章:MapReduceの基礎

大規模データの問題に対する実際的なアプローチは分割統治法しかない。
分割統治法アルゴリズムの実装には対処する必要のある問題（低水準なものも）が多い。
Hadoopはその低水準な問題をプログラム作成者が考えずにすむ抽象化されたインターフェースを提供する。

Hadoopとgoogleのmap reduce実装は異なる点がある。
googleの実装ではreducerに渡るvalueの並びを指定するセカンダリソートキーを指定できる。
Hadoopではそのような指定はできない。

mapタスクの数は入力データにより可変だが、Reduceタスクの数は厳密にプログラマが指定可能。
mapタスクやreduceタスクでは外部状態に影響された処理を行うことも可能。

mapタスクとreduceタスクの実行時間はそれぞれもっとも遅いタスクの実行時間に規程される。
しかし投棄的実行、つまり同じタスクの複製が別々のマシンで実行され、早く終了した結果を使用することにより、高速化が可能。
しかしタスクでおこなわれる処理そのものが重い場合、実行時間はあまり改善することはできない。

タスクを実行するノードは、必要なデータがある場所からなるべく最も近いノードを選んで行う。
これは通信による実行コスト増大を防ぐため。

mapとreduceのタスクの他に、combinerとpartitionerが存在する。
combinerはmapの結果を集約する役割を、partitionerはどのキーを持つデータをどのreduceタスクへ送るかを決定する役割を持つ。

HDFSはデータノードとネームノードに分かれており、データノードはデータそのものを、ネームノードはデータの流れ全体を管理する役割を持つ。
クライアントとのデータの通信はデータノードが直接行う形となり、ネームノードが通信するデータはメタデータのみとなる。

HDFSのネームノードは以下の責任を負う。

MapReduceアルゴリズムの効率的な設計には以下の選択を理解することが必要

  • 比較的少数の大きなサイズのファイルを保存する(これはHDFSのブロックサイズが大きい、入力ファイルが増えるとその入力ファイル分のmapタスクが生じるので)
  • 広い転送帯域の確保
  • 安価だが信頼性がそれほど高くない構成要素によってシステムが構築される

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

主なデザインパターン

in-mapper-combining

combinerをmapクラスのインスタンスに持たせておく方法。
本来のcombinerは必ず実行されるものではないため、combinerを必ず実行させたいときはこの方法が有向。
mapクラスのインスタンスは同じタスク？で使いまわされるため、インスタンス変数として連想配列を持っておいて、そこにデータを蓄えておき、集約した結果をインスタンス破棄時に出力するなど。

pairsとstripes

pairsは共起の語をそれぞれのペアごとにmapで出力し、reduceで集計する。
stripesは共起する語をハッシュマップに蓄え、それ自身をmapで出力し、reduceで集計。
stripesのほうが効率的だが、メモリがスケーラビリティのボトルネックとなる。
どちらもcombainerで集約処理が可能

order inversion

演算の並びをソートの問題に変換するというのが基本的な考え。
ソートにより先に必要なデータをReduceに先に送ることが可能となる（ソート順にreduceでは処理を行うため）。

value-to-key conversion

値の一部をキーに移すことで、ソートのためにmap reduceの実行フレームワーク自身を使うことが可能。

突き詰めればmap reduceで同期を制御するということは、以下のテクニックを効率的に利用するということに集約される。

  1. 演算に必要なデータを組み合わせた複合型のキーと値の構築
  2. mapperやreducerでのユーザー指定の初期化及び終了コードの実行
  3. mapperやreducerでの復数の入力にまたがる状態の保存
  4. 中間キーのソート順序の制御
  5. 中間キー空間のパーティショニングの制御(どのreduceへ送るか)

5章:グラフのアルゴリズム

並列幅優先探索

mapではキーを現在のid、valueを現在のグラフとして受け取り、いける先とグラフそのものを出力。
redeuceではグラフデータとそこまでの距離を受け取り、新たな距離データを作りだす。
辺のコストが1に固定されている場合は、コストが∞のノードがなくなった時点で終了すればよい。
それまでmap reduceを繰り返すことになり、終了判定はhadoopAPIに存在するカウントを使用すれば可能(ノードのコストが更新されたらインクリメント)。

辺のコストが1に固定されていない場合は、最悪で|ノード数-1|の繰り返しが必要となる。
終了判定は、ノードの最短コストが更新されなくなったら終了すればよい。これもカウントを用いれば可能。

これはダイクストラ法を一台で行った時と比べ、はるかに効率が悪いが（おそらく閉路たくさんあると最悪）
それは並列化のためのコストとみなす。

並列幅優先検索アルゴリズムは、map reduceでの多数の一連のグラフアルゴリズムの原型となる構造を示している。それらのグラフアルゴリズムは以下のような特徴を共通して持つ。

  • グラフの構造は隣接リストで表現される
  • map処理はノードのデータ構造に大して行われ、reduce処理では同じ行き先のデータを受け取り、それに対する処理をする。
  • 演算処理の結果に加えてグラフ構造そのものを渡す必要がある。
  • map reduceでのグラフアルゴリズムは繰り返しの処理が前提となっている。
PageRank

Webページの品質を測定するためにGoogleの検索エンジンで用いられてる有名な手法。
ハイパーリンクのグラフ構造に基づいて測定を行う。



引用元:
「Hadoop MapReduce デザインパターン」