抄訳 GraphChi: Large-Scale Graph Computation on Just a PC(2012)
November 12, 2022GraphChiは、商業規模の有向グラフをコンシューマPCで計算できるとうたうデータ構造とプログラミングモデルである。 そのためには、任意のひとつのノードとそのノードに接続する全てのエッジを読み込めるメモリがあればよい。 順序つきのノードを互いに素なP個の集合に分け、それぞれをintervalをよぶ。 interval内のノードに向うエッジを根のノード順にソートし、エッジをP個のshardに分けて保存する。 1つのshardをディスクの連続領域に保存することで、あるノードとノードに接続するエッジを、高々P回のディスクへのアクセスでメモリに読み込める。
エッジの追加や削除もできる。 メモリ上のバッファに追加されたエッジを追加し、バッファが満杯になるときにディスクに書き込む。 1つのshardごとにP個のバッファをもち、追加したエッジの根があるintervalで保存先のバッファを変える。 エッジを削除するときは、エッジに削除されたフラグを与え、shardをディスクに書き戻すときにそのエッジを無視する。
計算のモデルは、各ノードとそのエッジの現在の値から次の状態を計算するものであり、開発者は以下のf, gを実装する。
ガウス＝ザイデル法を応用し、非同期に各ノードをUpdate(vertex)によってグラフの状態が収束するまで非同期に更新する。
Update(vertex) begin
x[] ← read values of in- and out-edges of vertex ;
vertex.value ← f(x[]) ;
foreach edge of vertex do
edge.value ← g(vertex.value, edge.value);
end
論文のリンク
雑記
単一のPCで動かすため、ネットワーク上の通信の失敗をあまり考えなくてよい。 そのために、論文中で比較されたBulk-Synchromous Parall(BSP model) にある同期やフォールトトレランスの仕組みが省かれているようにみえる。 実験の比較対象がクラスタを使った場合なので、単一のPCで動かす同様の目的の手法と比べたときの評価がわからない。