MapReduce
言わずとしれた00年代以降の分散処理に多大な影響を与えたMapReduceのpaper
極めてシンプルなプログラミングモデルながら大規模な分散処理のためのタスク自体とそのインフラストラクチャを分離しタスクを書くプログラマが再実行や並列化について考えなくてもよくしたという点で功績が大きい
LISPなどの関数型言語のモデルに影響を受けている(Map, Reduceというfunctionは関数型言語で最もよく使う基本でもある)
副作用のないmap関数とreduce関数を書くことによってタスクの場所透過性の確保を行い大規模な並列処理におけるスループットを確保している
また再実行やタスクの分散をmasterとなるタスクスケジューラが管理する
タスクの冗長化と最初に終わったタスクがWinするFirst Finish Winで局所的な障害や一部だけディスクが遅かったりネットワークが遅かったりといった局所障害に対応している
また中間結果をソートし同じようなデータをLocalityを意識してスケジュールすることでネットワークの帯域幅の上限を考慮している
具体的にはGFS(Googleの分散ファイルシステム)で64MBごとに分けられているブロック内でinput dataが存在するworkerのマシンにmap taskを指示する
GFS上は同じデータが3つのレプリカにレプリケーションされているためいずれかは使用出来る可能性が高い
そのためほとんどのmap taskはローカルreadとなりネットワークリソースを消費しない
もし該当するレプリカのscheduleが埋まっている場合は同じネットワークやスイッチ内など近くのworkerにtaskを割り当てる
他のバッチ処理にも言えることだけどネットワークの帯域幅というのは基本的には光の速度以上を超えられず大規模処理を相手にする場合しばしばボトルネックになる箇所だし、物理的にもフォールトも存在するのでLocalityを意識するとタスクの安定性やスループットが増す
タスクスケジューリングをするmasterは冗長化が難しいのでシングルマスタでも問題ないがmasterが死ぬと全部のタスクも実行出来なくなるため可用性とのトレードオフとなる
ただ途中までの計算結果は分散ファイルシステムに書き出されていたりmaster上でもチェックポイントを書き出しているためmasterがリカバリした時にチェックポイントよりタスクを再実行出来る
masterは1台になるがその分master自体の可用性はそれなりに高くなる
ここでもmap, reduceの副作用がないことの利点が生かされている
プログラミングモデル自体は低レベルのため、利用しやすくするためにHiveやPigなどの抽象化レイヤーも存在する
SQL likeなdeclartiveなクエリを書けたり、より直観的なタスク定義が出来る
タスクの最適化をクエリエンジンに任せることが出来る
シンプルゆえに多様なcomputational heavyなタスクに応用が効く
分散ソート, 分散grep, 分散Index構築, 分散graph処理…etc
基本的にはinputとして与えられたkey-valueのペアをリストにmap変換し最終的なoutputのlistにreduceしているだけ
多数のコモディティ化されたマシンのIOを多重化しCPUがスケールする
MapReduceを利用するユーザに公開しているインターフェースを制限し限られたプログラミングモデルにすることで背後の複雑さを隠蔽し、並行性と耐障害性を獲得している
パイプとファイルというインターフェースのみを公開し背後の複雑さを隠蔽するUnixの設計思想に近いとも言える
結局我々はUnixという哲学に大きく影響されている
今では色々非効率的な部分も発見されDataFlowベースの実行モデル(Spark等)の進化に伴い直接的に利用されることは少なくなってきたMapReduceではあるがその考え方や設計思想は今でも有用
革新的というよりは既存の様々な技術を組み合わせて現実的な問題を解決している点など見るべき点は多い
公開するインターフェースの制限とプログラミングモデルの制限による並列化、耐障害性等別の問題の隠蔽
taskの多重化, FFW (First Finish Win) によるfault torelance
LocalityによるIOのOptimization
中間結果のdiskへの書き出しによるoptimization
分散ファイルシステムによるinputの多重化, etc...
よくありがちな2つのデータセットを結合したいというようなリレーショナルな操作やグラフ操作などをより簡単に実行出来るdataflow-basedなシステムに置き換えられていることが多い
MapReduceを拡張しより一般化したモデルとなっている
MapReduceとの違いはMapReduceベースの場合ディスクに中間結果を永続化するのに対してインメモリで処理を行う
途中タスクのフォールトのためディスクに書き出されたりはする
インメモリ故にメモリに乗り切らないようなPB級のデータセットに対しての処理に対してはMapReduceより非効率になることもある
とはいえPB級のデータを抱える組織はそこまで多くなく、概してHadoopはオーバースペックになりがちなのでこういったインメモリベースのバッチ処理フレームワークが進化したというところはある
ストリーム処理ベースが普及したことによりバッチ処理はストリーム処理のサブセットと捉えられることも可能になった
AWSはコモディティ化においては強いがGoogleは大規模なデータセット処理という点ではBigQueryなど一つ抜けているサービスを有しているので強い. ビッグデータ処理だけBigQueryやCloud DataFlowに出すという構成を取るところもある