分散計算#
内容来自
- 極客時間専欄:《分散技術原理とアルゴリズム解析》
MapReduce 計算モード（分治法）#
分治の思想#
略して分治法とは、複雑で直接解決が難しい大きな問題を、いくつかの規模が小さく、比較的簡単または直接解決できるサブ問題に分割することです。これらのサブ問題は互いに独立しており、元の問題と同じ形式を持ち、再帰的にこれらのサブ問題を解決し、サブ問題の解を統合して元の問題の解を得ます。
計算フロー#
全体の MapReduce の作業フローは、主に 5 つの段階に要約できます。すなわち：Input（入力）、Splitting（分割）、Mapping（マッピング）、Reducing（簡略化）、および Final Result（出力）です。
Fork-Join 計算モード#
Fork-Join は、Java などの言語やライブラリが提供するネイティブなマルチスレッド並列処理フレームワークで、スレッドレベルの分治計算モードを採用しています。これはマルチコア CPU の利点を最大限に活用し、再帰的に 1 つのタスクを複数の「小タスク」に分割し、複数の「小タスク」を複数のプロセッサで並行して実行します。つまり、Fork 操作です。複数の「小タスク」が実行を完了した後、これらの実行結果を統合することで元のタスクの結果を得ることができます。これが Join 操作です。
Fork-Join は大規模に拡張することができず、単一の Java 仮想マシン上での実行にのみ適しています。複数の小タスクは異なるプロセッサで実行されますが、相互に通信でき、1 つのスレッドが他のスレッドのサブタスクを「奪う」こともできます。
Stream 計算モード#
MapReduce モードでタスクが完了すると、全体のタスクプロセスは終了します。これは短いタスクモードに属します。しかし、タスクプロセスの起動と停止は非常に時間がかかるため、ストリームデータの処理や処理遅延に対するリアルタイム性が要求されるタスクには、Stream ストリーム計算モデルがよく利用されます。
Stream の動作原理#
ストリーム計算はリアルタイム性を強調します。データが生成されるとすぐに処理され、1 つのデータが処理を完了すると、シリアライズされてキャッシュに保存され、すぐにネットワークを通じて次のノードに送信され、次のノードが引き続き処理します。MapReduce のように、キャッシュが満杯になるのを待ってから処理や送信を開始することはありません。データのリアルタイム性を保証するために、ストリーム計算ではデータを保存しません。水流のように常に前進します。
計算ステップ#
- ストリーム計算ジョブを提出する：ストリーム計算ジョブでは、計算ロジックを事前に定義する必要があり、提出後に実行中にロジックを変更することはできず、再提出して実行する必要があります。
- ストリームデータをロードしてストリーム計算を行う：ストリーム計算ジョブが起動されると、常にイベントトリガーを待機する状態になります。小規模なデータが入ると、システムはすぐに計算ロジックを実行し、迅速に結果を得ます。
- 計算結果を継続的に出力する：小規模なデータの計算結果を得た後、結果データをオンライン / バッチシステムに即座に書き込むことができ、全体のデータの計算結果を待つ必要はありません。これにより、リアルタイム計算結果のリアルタイム表示が可能になります。
Actor 計算モード#
Actor モデルは、分散並列計算モデルを表します。このモデルには独自のルールがあり、Actor の内部計算ロジックや複数の Actor 間の通信ルールが定められています。Actor モデルでは、各 Actor はシステム内のコンポーネントに相当し、基本的な計算単位です。
Actor モデルの三要素は状態、行動、メッセージであり、非常に人気のある等式があります：Actor モデル =（状態 + 行動）+ メッセージ
Actor の作業フロー#
Actor A と Actor B が Actor C の Function ロジックを実行する必要がある場合、Actor A と Actor B はメッセージを Actor C に送信します。Actor C のメッセージキューには Actor A と Actor B のメッセージが保存され、メッセージの順序に従って Function が実行されます。
Actor の利点と欠点分析#
利点#
- より高い抽象化を実現しました。Actor は OOP オブジェクトに似ており、状態と行動をカプセル化しています。しかし、Actor 間は非同期通信であり、複数の Actor は独立して実行でき、干渉しないため、OOP に存在する競合問題を解決しました。
- 非ブロッキング性。Actor モデルでは、Actor 間は非同期通信であるため、1 つの Actor が他の Actor に情報を送信した後、応答を待つ必要はなく、情報を送信した後にローカルで他のタスクを続行できます。つまり、Actor モデルはメッセージ伝達メカニズムを導入することで、ブロッキングを回避します。
- ロックを使用する必要がありません。Actor は MailBox から 1 回に 1 つのメッセージしか読み取れず、つまり Actor 内部では同時に 1 つのメッセージしか処理できないため、天然の排他ロックとなり、コードに追加のロックをかける必要はありません。
- 高い並行性。各 Actor はローカル MailBox のメッセージのみを処理するため、複数の Actor が並行して作業でき、全体の分散システムの並列処理能力が向上します。
- 拡張が容易です。各 Actor は複数の Actor を作成でき、単一の Actor の作業負荷を軽減します。ローカルの Actor が処理しきれない場合、リモートノードで Actor を起動し、メッセージを転送できます。
欠点#
- Actor はモジュールとカプセル化を提供しますが、継承と階層が欠けているため、複数の Actor 間に共通のロジックやコード部分があっても、各 Actor でその部分のコードを再実装する必要があります。つまり、再利用性が低く、ビジネスロジックの変更は全体のコードの再実装を引き起こします。
- Actor は動的に複数の Actor を作成できるため、全体の Actor モデルの動作が常に変化し、プロジェクトで Actor モデルを実装するのが難しくなります。また、Actor を増やすと同時にシステムのオーバーヘッドも増加します。
- Actor モデルは、メッセージ処理の順序に厳しい要求があるシステムには適していません。Actor モデルでは、メッセージはすべて非同期メッセージであり、各メッセージの実行順序を確定することができません。ブロッキング Actor を使用して順序の問題を解決することはできますが、明らかに Actor モデルのタスク処理効率に深刻な影響を与えます。
Actor モデルの応用#
- Akka
- Quasar (Java)
- Erlang/OTP
Actor モデルのまとめ：
Pipeline パイプライン計算モード#
コンピュータにおけるパイプライン（Pipeline）技術は、各命令を複数のステップに分割し、異なる命令の異なるステップを重ねて操作することで、いくつかの命令を並行処理する技術です。現代の CPU 命令はパイプライン設計を採用し、1 つの CPU 命令を取指（IF）、訳読（ID）、実行（EX）、訪問（MEM）、回書（WB）の 5 段階のパイプラインで実行します。分散分野においても、パイプライン計算モードは類似しており、大きなタスクを複数のステップに分割して実行し、異なるステップは異なるプロセスで実行できます。
計算フロー#
機械学習におけるデータ前処理を例にとると、現在 5 つのサンプルデータがあり、各サンプルデータの前処理フローには、データの重複排除、データの欠損値処理、データの正規化の 3 つのステップが含まれ、順番に実行する必要があります。つまり、データ前処理というタスクはデータの重複排除→データの欠損値処理→データの正規化の 3 つのサブタスクに分割できます。現在 3 つのノードがあり、ノード 1 がデータの重複排除を実行し、ノード 2 がデータの欠損値処理を実行し、ノード 3 がデータの正規化を実行します。ノード 1 がサンプル 1 のデータを処理し終えたら、処理されたデータをノード 2 に送信し、ノード 1 はサンプル 2 のデータを処理し続け、同時にノード 2 はサンプル 1 のデータを処理します。このようにして、複数のタスクの並行実行が実現されます。
パイプライン計算モードの応用#
- 機械学習のパイプラインタスク、例えば TensorFlow
- Apache Beam（具体的には研究していませんが、紹介によるとパイプライン処理の考えに基づいています）
まとめと拡張#
ストリーム計算とバッチ計算の違い#
パイプラインモードと MapReduce モードでは、大タスクを複数のサブタスクに分割する点で共通していますが、両者の違いは何ですか？#
- MapReduce はタスクを粒度として、大きなタスクを複数の小タスクに分割し、各タスクは完全で同じステップを実行する必要があります。同じタスクは並行して実行でき、タスク並行の計算モードと言えます。
- 一方、パイプライン計算モードはステップを粒度として、1 つのタスクを複数のステップに分割し、各ステップは異なるロジックを実行します。複数の同種のタスクはステップを重ねることで異なるタスクの並行計算を実現でき、データ並行のモードと言えます。
さらに、サブタスク（ステップ）間の関係が異なります：
- MapReduce では、各サブタスクは独立して実行され、互いに干渉せず、複数のサブタスクが実行を完了した後、結果を統合して全体のタスクの結果を得るため、サブタスク間に依存関係がないことが求められます。
- パイプラインモードでは、複数のサブタスク間には依存関係があり、前のサブタスクの出力が次のサブタスクの入力となります。
総じて、MapReduce 計算モードはタスク並行のシナリオに適しており、パイプライン計算モードは同種のタスクのデータ並行処理のシナリオに適しています。
オフライン計算とバッチ計算、リアルタイム計算とストリーム計算の関係#
