この文章について
本当は恐ろしい分散システムに触発されて、よりライトな部分で並列処理がどのように実現されるのかを自分なりにまとめたものです。
なお、筆者は並列/分散処理に対する専門家ではないため、マサカリ大歓迎です。
並列処理が求められる理由
- ムーアの法則に限界が来て、次なる戦略として水平スケールすることが求められるようになった
- 高価なハードウェアに依存するのではなく、コモディティアーキテクチャを複数用意することで、速度・信頼性を高める1
- クライアント数が莫大になったため、１プロセスで同時処理することが現実的ではなくなっている
並列処理に対する基本的な戦略
- 並列化される処理は基本的にステートレスなものとする
- ディスパッチャやマスター（リーダー）ノード、メインスレッドと呼ばれる司令塔が（一時的に）存在する
- 失敗したタスクを補填する仕組みを用意する必要がある
- 整合性を保ちつつデータI/Oをどのように減らすかが全体的な速度の鍵
- 多くの場合、任意のタイミングで水平スケール可能なアーキテクチャを考慮する
データの持ち方
並列処理で扱うデータとは、いかに分散システムとして処理可能な形でデータを持っているかといえる。上述のスライドが詳しく解説しているので、ここでは並列処理に特化した部分でまとめたい。
シェアードナッシングとシェアードエブリシング
データを分散システムがそれぞれ持っているか、何処かに偏っているかを示す特性をこのようにいう。
並列処理ではそれぞれのタスクが別々に動作するため、それぞれのデータがどのように共有されるのかを検討する。
シェアードナッシング
データはノードごとに局所化しており、他ノードで該当データを行うためにはデータの輸送が必要となる。
その代わり、タスクとデータのノードが一致している場合にはデータの輸送が発生せず、ロックが極小化されるため速度向上が期待できる。
代表例はAmazon Redshiftである。
シェアードエブリシング
各ノードから等距離のストレージクラスタを利用し、それぞれに同一のデータが存在する（かのように振る舞う）。
実装にもよるが、一般的にはデータ書き込み時にクラスタへのデータ伝播が行われるため遅くなる。
また、データ伝播中のロックも大きくなる。
代表例はHadoop(HDFS)である。
その他のアプローチ
これらどちらかではなく、その中間的なアプローチも存在する。
ジャーナルと適正量のコピーを組み合わせて、いわばネットワーク越しのRAID5のような構成にしたMapR FS2などがその例である。
カラムナストレージなどもキーワードとしてあるが、基本的には「どこにあるか」「ディスクI/Oをどれだけ減らせるか」「ネットワークを通すか」に焦点を当てて高速化する。
並列処理アルゴリズムの基本
基本的には、各ノードでステートレスなデータを独立して処理する。(Map)
集計などが必要な場合に、再度集計処理を走らせる。(Reduce)
これらのMap/Reduceを素直に構築したのが、Google MapReduceでありそのクローンであるHadoop MapReduceである。
素直に構築すると、Map(やshaffle)処理の待ち合わせが発生し、非効率となることから、空いたノードに小規模なタスクを詰め込んでいく方法が取られる。
それがDAG(有向非巡回グラフ)に基づくタスク配分である。
DAGを実装したのがDremel、TezやSpark。
基本的には、データをそれぞれに処理させて再集計する戦略なので、逐次処理は無理だったり無駄が多い（ストアドプロシージャみたいな処理とか）。
並列化のレイヤー
さて、これまで一般的な並列処理アーキテクチャについてまとめたが、御存知の通り並列化には様々なレイヤーがある。
- コンピュータ・クラスタ
- プログラム
- ハードウェア
ただし、いずれも戦略は似たようなものとして捉えられる。（私がそのようにしか理解できていない）
各レイヤーにおける代表例とその戦略
コンピュータ・クラスタ
Hadoop
- データ：HDFSによるシェアードエブリシング
- アルゴリズム：クラシカルなものはMapReduce。2.0以降TezでのDAGが実現。
- クラスタによるMap/Reduceをフレームワーク化したことが最大の功績
Redshift
- データ：カラムナストレージによるシェアードナッシング。分散キーによりコントロール可能。
- アルゴリズム：explainからの推測だが、基本的にはMapReduceと考えられる。コンパイル済みコードの配布、分散化の失敗によるボトルネックなどから。
BigQuery
- データ：カラムナストレージ。シェアードエブリシングとして扱われていると考えられる。
- アルゴリズム：DAG（のはず）
プログラム
スレッド処理
- データ：共有メモリによるシェアードエブリシング。（混乱を避けるためにスレッドごとにアクセス
制限を加える言語もある） - プロセス内でスレッドをわけ、処理を分散させる。Rubyのようにネイティブスレッドを使えない言語では、コア分散などの恩恵を受けられない（難しい）言語もある
プロセス並列(coroutine)
- データ：メッセージングによるシェアードナッシングが多いと感じている。OSレベルでの共有メモリによるシェアードエブリシングなアプローチを取ることもできる。
- プロセスをフォークするコストが高いため、それに見合うだけの処理内容でないと差し引きで損をする。ただし、起動後はCPUのコアを最大限に利用できるため効率が良い。
goroutine
- データ：channelによるシェアードナッシング
- 名前とは裏腹に、どちらかと言えばスレッド寄りの機能と理解している。ネイティブスレッドのようにタイムスライスに任せているのではないようだが、軽量なスレッドとして大人気
Map/Reduce
- データ：言語実装によるが、使用者側からすればシェアードナッシングな考え方で用いるケースが多い。
- 関数型言語に端を発する概念。Enumerableなデータに対して同一の処理を加え、その後再集計する。これ自体が並列処理ではないが、ループせずにmap/reduce関数を用いてimmutableな処理に仕立て上げることが関数型言語の楽しみ。この感覚をつかむと並列処理が怖くなくなる。
ハードウェア
CPU
- データ：そもそもCPUはデータを持たず、メモリに対して要求するシェアードエブリシング。速度向上のためにL1〜L3キャッシュとして局所性を高めている
- マルチコアにより並列処理を行うが、ここでも命令のディスパッチ処理などが存在する。この処理を最適化するためにFPGAが台頭してきた
スレッド
そもそもスレッドをハードウェアに加えるべきかというと違う気もするが、ここではハードウェアの項目に記載する。
- データ：プロセスが保有するメモリにはアクセスできるシェアードエブリシング。
- 本来は並列処理ではなく並行処理のための機能だが、マルチコア環境でネイティブスレッドで操作されている場合にはタイムスライスを考慮せず並列処理が期待できる。ただし、共有メモリのオブジェクトに対するロックでオーバーヘッドもあるため、一概に高速化できる簡単な話ではない。
まとめ
かなり筆者の趣味によったが、並列処理するときの個人的な感覚をまとめた形になった。
- 必要に応じて水平スケール可能な処理にすること（並列数が固定されるのは並列処理ではない）
- 実現したい処理に即したアーキテクチャを選択すること
- いかに整合性を保ちつつデータを局所化するか
- 手続き的な処理がしたければ無理に並列処理アーキテクチャを選ぶな