Distributed GraphLab: a Framework for Machine Learning and Data Mining in the Cloud (2012)
May 7, 2024Distributed GraphLabは、機械学習とデータマイニング向けのプログラミングモデルのGraphLabを、クラスタ上で実行できるように発展させた。 GraphLabは、グラフの一部から点の集合を返す関数を、反復的にグラフに適用する。 関数から返された点は再び関数に渡され、渡すべき点がなくなるとアルゴリズムは終了する。 Distributed GraphLabは、GraphLabをメモリ共有するノードからなるクラスタで実行できるように、Chandy-Lamportのスナップショットとロックを導入した。
GraphLabのグラフは、点や辺にデータの割り当てられた有向グラフからなる。 たとえば、モデルの重みやアルゴリズムの状態を点や辺に割り当てられる。 関数は、1つの点、点に隣接する点、その両方を結ぶ辺を引数にとり、点の集合を返す。 引数として受けとる点と辺の集合はスコープとよばれる。 関数はスコープ内のデータを更新できるが、グラフの構造を変更することはできない。 GraphLabは、初期値としてあたえられる関数に適用する点の集合\(\tau\)から点を選び、点のスコープに関数を適用する。 適用した点は\(\tau\)から取り除かれ、関数から返された点の集合\(\tau’\)は\(\tau\)に追加される。 関数の適用をくりかえし、\(\tau\)が空集合になるとGraphLabは終了する。
関数は、3種類ある一貫性の規則のいづれかにしたがって並列実行する。
3種類の一貫性は、full consistency, edge consistency, vertex consistencyであり、順に一貫性が高いかわりに並列性が低い。
Full consistencyでは、スコープが重複しない関数同士しか並列に実行できない。
Edge consistencyでは、関数は、スコープの中心にある点と辺にあるデータを排他的に読み書きでき、隣接する点のデータには、読み込みのみを行える。
Vertex consistencyでは、すべての関数を並列できる。
以下の図は、3つの一貫性の排他的なロックの範囲と一貫性と並列性のトレードオフを比較を示す。
図は論文から引用したものである。
Distributed GraphLabは、実行するアルゴリズムに適した仕方でグラフを分割し、atomというファイル形式で複数のノードにグラフの一部を配置する。
分割数はノードの数よりも大きく設定されるので、1つのノードに複数のatomファイルが置かれる。
atomファイルには、AddEdge(42->314, edata), AddVertex(500, vdata)のようなグラフを構築する命令の系列が書かれている。
分散したグラフで一貫性を守るためのスケジューリングのアルゴリズムは、Chromatic EngineとDistributed Locking Engineの2つがある。 Chromatic Engineは、グラフの彩色問題を解くことで、並列実行できる関数を特定する。 ただし、グラフの中には彩色問題で関数を容易に特定できない構造をもつものもある。 一方、Distributed Locking Engineは、グラフの点にreaders-writerロックをかける排他制御で並列実行できる関数を制限する。