Neptune Analytics SSSP Δ-parameter

Transcript

1. Neptune Analytics SSSP Δ-parameter chiaoi
2. Amazon Neptune Analytics グラフデータベース
3. グラフ ノード(点)とエッジ(辺)からなる 今回は、 - 有向（エッジに向きがある） - 重み付き（エッジに重みがある） とします。 E B C A D 3 3 3 3 3 3 3
4. インメモリデータベース 使い方の手順 - グラフを作成する - S3などからデータをロードする - グラフに対するクエリを実行する 全データが常にメモリ上にあるので、どんなクエリでもディスクI/O待ちが発生しません。 データをロードした後は基本的に読み取り中心で排他制御が不要になります。 → 固定的なオーバーヘッドは大幅に軽減されます。
5. 計算リソース 計算リソース メモリサイズ(m-NCU)を指定すると他は勝手に決まります。 1m-NCU: 1GBのメモリ + 対応するコンピュートおよびネットワーク容量 https://aws.amazon.com/jp/blogs/database/introducing-smaller-capacity-units-for-amazon-ne ptune-analytics-up-to-75-cheaper-to-get-started-with-graph-analytics-workloads/ 選べるm-NCU: 16, 32, 64, 128, 256, 384, 512, 768, 1024 2048, 3072, 4096, 6144, 9216, 12288, 18432, 24576
6. CloudWatchでの監視 CloudWatchを見つつ調整できます。 例えば - スロットルされたリクエスト - キューに入っているリクエスト - CPU使用率 - グラフストレージ使用率 が十分に小さいことが重要です。
7. SSSP（単一始点最短経路問題） ノードを一つ指定して、これを始点とします。 今回の場合は A とします。 A から A, B, C, D, E のそれぞれの点への 最短経路を求める問題です。 E B C A D 3 3 3 3 A B C D E 0 ∞ 6 3 9 3
8. SSSP (単一始点最短経路問題) Delta-Stepping法 Neptune Analyticsでは、 openCypherのみ対応。 explain-modeを”DETAILS”にすることで クエリ実行かかった時間の内訳を 見ることができる。 （本来はここに通信などの時間もかかる） ΔパラメータでSSSPを解くのに必要な時間が変 わる。（デフォルトは 2）
9. explain-mode “DETAILS” ID Out #1 Out #2 Name Arguments Mode Units In Units In Ratio Time(ms) 0 1 - SolutionInjection solutions=[{}] - 0 1 0.00 0 1 - - DFSSubquery subQuery= subQuery1 - 0 0 0.00 216 Summed execution 216 27 6 - DFESSSPAlgo … - 1 1000 00 10000 0 208 … SSSPAlgoが ボトルネック
10. Δ Parameter (N = 100,000) ある値を超えるとそこからは ほとんど高速にはならない。 頂点数が100,000である疎なグラフはΔ が大きければ大きいほどよい。
11. Δ Parameter (N = 10,000,000) Δ=5,000,000が最もよい。 並列化のスケーリングの恩恵により、 LambdaでのDijkstra法実装より高速。
12. まとめ Amazon NeptuneのSSSP - とても大きなグラフだと並列化の恩恵を受けやすくなる。 - 大きなグラフを扱う場合は、Amazon Neptuneに頼った方が簡単。 - Δのパラメータをチューニングすることが大きなグラフになればなるほど重要にな る。 今後 - グラフの形状別にΔの目安の値を求める。 - Delta Stepping法の最悪ケースでの挙動を調査する。
13. 本題 N = 10,000,000のときの最適なΔは、1,000,000から5,000,000程度。 理論から導けないかを考えます。 問題
14. 表記方法 0~Δ Δ~2Δ 2Δ~3Δ kΔ~(k+1)Δ B(0) B(1) B(2) B(k)
15. 初期状態 0~3 頂点 tent B ∞ C ∞ D ∞ E ∞ E B C A D 3 3 3 3 5 0~3 4~7 A
16. パスを書き出す 0~3 頂点 tent B ∞ C ∞ D ∞ E ∞ E B C A D 3 3 3 3 5 0~3 4~7 A A → C: 5 A → D: 3
17. 軽い辺と重い辺に分ける 0~3 頂点 tent B ∞ C ∞ D ∞ E ∞ E B C A D 3 3 3 3 5 0~3 4~7 A A → C: 5 A → D: 3
18. 軽い辺を処理する 0~3 頂点 tent B ∞ C ∞ D 3 E ∞ E B C A D 3 3 3 3 5 0~3 4~7 A A → C: 5 A → D: 3 D
19. tentの更新 0~3 頂点 tent B ∞ C ∞ D 3 E ∞ E B C A D 3 3 3 3 5 0~3 4~7 A → C: 5 D
20. 軽い辺を再度処理する 0~3 頂点 tent B ∞ C ∞ D 3 E ∞ E B C A D 3 3 3 3 5 0~3 4~7 A → C: 5 D → C: 3 D
21. 軽い辺を再度処理する 0~3 頂点 tent B ∞ C ∞ D 3 E ∞ E B C A D 3 3 3 3 5 0~3 4~7 A → C: 5 D → C: 3 D C
22. 軽い辺の処理が終わる 0~3 頂点 tent B ∞ C 6 D 3 E ∞ E B C A D 3 3 3 3 5 0~3 4~7 A → C: 5 C
23. 重い辺の処理をする 0~3 頂点 tent B ∞ C ∞ D 3 E ∞ E B C A D 3 3 3 3 5 0~3 4~7 A → C: 5 C
24. 重い辺の処理が終わる 0~3 頂点 tent B ∞ C 5 D 3 E ∞ E B C A D 3 3 3 3 5 0~3 4~7 C
25. バケット0が空になる 0~3 頂点 tent B ∞ C 5 D 3 E ∞ E B C A D 3 3 3 3 5 0~3 4~7 C 0~3のバケットからは頂点が なくなり、 重みが正なのでこれ以降は ずっと空。
26. 疑似コード
27. 計算量解析 再度バケットに入る頂点の個数は、R(Δ)以下となる。 全体の計算量は逐次の場合、以下の通り。 Δの増減に関して、トレードオフがある。
28. 最適Δの値の具体的な計算 https://www.sciencedirect.com/science/article/pii/S0196677403000762
29. 実験で得られた値への考察 Δ=1,000,000以上になると、最大重みよりも大きい値となります。 全辺がlightな辺となり、1つのバケット内での内部フェーズは増える（軽い 辺の処理が多くなる）が、バケット数やフェーズ数が減る。 Δが大きいと、バケット内にたくさんの頂点が入り並列化がよくなる。 並列化の同期ポイントが1つのバケットの処理後に入るが、それによるオー バーヘッドも大きい。 → 並列化を進めると同時に、並列化の同期の回数を減らすようなΔが強く 出たのではないか？
30. 値のズレの原因考察 Meyer & Sanders(1998)の解析の中では、並列環境による同期やオー バーヘッドなどが考慮されていない。 理論的な最適値と並列環境での実測値の間に乖離が生じる。 Dong, Gu, Sun & Zhang(2021)によると - 同じグラフでも実装が異なると最適なΔはかなり変わる。 - Δに対する性能感度が高い。 → 論文中ではρ-Steppingを提案しており、最良のDelta-Steppingと　同 等以上の性能を達成。 https://arxiv.org/pdf/2105.06145
31. まとめ Delta-Stepping法のΔを理論的に決定するのは難しい。 グラフの形状によってもかなり違いがある。 https://arxiv.org/pdf/2105.06145 巨大グラフのSSSPを解く目的でAmazon Neptuneを使用するのはとて も有効。Delta-Stepping法のΔは実験的に決定する必要がある。グラ フの形状に依存するので、グラフの形状を予測したり、グラフの形状が 変わるほどの変更があるたびにチューニングをした方がよい。