Pregel: A System for Large-Scale Graph Processing(2010)

August 19, 2022

Googleで開発されたPregelは、ソーシャルグラフやハイパーリンクのグラフなどの巨大なグラフデータの処理に適した計算モデルである。 計算モデル自体も、処理対象のデータとおなじく、ワーカーが別のワーカーとのメッセージの送受信を繰り返すグラフ構造をなす。 このモデルのオリジナルは、以前紹介したValiantのBulk Synchronous Parallel model(BPS)である。 BPSは時間を一定間隔に区切り、次の間隔が始まる時点で、それまでのメッセージの送受信が全て成功していることを保証する。 間隔の中で、コンポーネントは別のコンポーネントにメッセージを送信する。 間隔を過ぎたとき、失敗した処理や未送信のあるコンポーネントがあれば、成功するまで計算を再実行させる。 Pregelでは、この間隔をsuperstepとよび、グラフ上の点であるワーカーがコンポーネントにあたる。

グラフの頂点は、開発者が定義した処理とその送信先がふくまれる。 頂点は、active, inactiveの2値状態をもつ。 superstep 0では全ての頂点はactiveであり、inactiveはメッセージを受信しない限り以降のsuperstepでやるべき処理をもたないことを示す。 inactiveのノードがメッセージを受信すると、activeな状態に戻る。 すべての頂点がinactiveになるとプログラムは終了する。

実行前にプログラムは、クラスターのマシンに配布され、そのうちの一つはマスタとして機能する。 マスターは、プログラム上のグラフに分割し、パーティションをマシンに配布する。 以降、マスターは、プログラムの入力のグラフを受理すると、それをマシンに配布、すべての頂点をactiveにし、計算を始める。 マスターは定期的にワーカーにpingを送り、ワーカーが停止していないか確認する。 ワーカーから応答がなければ、マスターはワーカーの処理は失敗したとみなす。 また、逆に、ワーカーは、一定時間内にpingを受信しなければ、実行中の処理を中止する。

雑記

マスターが失敗した場合の説明はなさそう。

グラフデータを処理する場合、MapReduceと比べて、グラフの状態をプログラムのステップからステップへ引き渡し続ける手間がかからないとある。 しかし、Pregelのコードと同じ処理をする他の計算モデルのコードの比較がなく、Pregelのコードがどれほど書きやすいかは論文だけからは比べ難い。

ワーカー同士で共有メモリをもたず、メッセージの交換で処理をすすめる点で、アクターと似ている。 大きな違いはsuperstepの有無で、superstepがあることで、ある時点までの処理がすべて正常終了していると仮定できることで、開発者はどれくらいプログラムを書きやすくなるだろうか。また、superstepでの同期によるオーバーヘッドはどうなのか。

論文へのリンク