HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

10GBのRAMで数十億規模のグラフ上のアルゴリズムを実行: DataFusionに夢中

Algorithms on billion-scale graph using 10GB RAM: I love DataFusion (semyonsinchenko.github.io)

102 pointsby speckx32 コメント

要約

Apache DataFusionを使用して、ディスクへのオフロードを最大限に活用し、ランダムアクセスではなくバルクスキャンに依存するグラフMapReduceを実装しました。これにより、10億エッジのグラフでPageRankを5GBのメモリで、20億エッジのグラフで弱連結成分を10GBのメモリで計算可能になりました。これは、従来のメモリにグラフ全体をロードする必要があるアルゴリズムでは不可能でした。

全文翻訳

10GB RAMで数十億ノードのグラフに対するアルゴリズムを実行: DataFusionを愛する理由!

TLDR;

Apache DataFusion を使ってグラフの Map-Reduce を実装しました。可能な限りすべてをディスクにオフロードし、ランダムアクセスではなくバルクスキャンに依存するアルゴリズムを設計しました。DataFusion がスピルオーバー、ソートマージ結合 (SMJ)、集計、プランニング、実行を処理してくれるため、私のコードは非常に軽量です。メモリ制限を厳密に設定し systemd-run 経由で実行するという厳格なモードでテストしました。動作します。もちろん、いくつかの問題にも遭遇しました。例えば、極端なシナリオでは FairSpillPool からデッドロックが頻繁に発生し、SMJ がディスク上のデータの事前ソートを利用する方法はまだ見つかっていません。しかし、動作します。Graphalytics データセットの 10億エッジを持つ有向グラフ (graph500-26) に対して、5GB のメモリで PageRank を計算できます。あるいは、同じデータセットコレクションの 20億エッジを持つグラフ (twitter_mpi) のすべての弱連結成分を、10GB のメモリで特定できます。NetworkX や Igraph ではこれができません。既存のグラフアルゴリズムのほとんどは、グラフがメモリに収まることを必要とします。以前は、数十億ノードのグラフ分析には Apache Spark と GraphFrames が必要だと思っていました。しかし今では、必要なのはラップトップだけだと思います。Apache DataFusion をグラフ分析に使うことに関する 私の古い意見 を完全に覆しました。

セットアップ

2つのタスクをテストしました。

PageRank

PageRankとは?

タスクは、Graphalytics データセット の graph500-26 で PageRank を計算することです。

キー値
ノード数32,804,978
エッジ数1,051,922,853
有向False
メモリ制限5 GB
DataFusion プールサイズ4 GB

PageRank は最も人気のあるグラフ中心性アルゴリズムの1つであり、検索結果のランキングから不正防止スコアリングまで使用されます。私の DataFusion 実装は古典的な Pregel です。バルク同期並列アルゴリズム(別名 Map-Reduce)を、結合と集計を使用して表現しました。Spark の GraphFrames ライブラリのコアにあるものと非常によく似ています。

弱連結成分 (Weakly Connected Components)

弱連結成分とは?

タスクは、同じデータセットから twitter_mpi 上のすべての弱連結成分を特定することです。

キー値
ノード数52,579,682
エッジ数1,963,263,821
有向True
メモリ制限10 GB
DataFusion プールサイズ8 GB

WCC は、あらゆるアイデンティティ(エンティティ)解決問題の中核部分です。例えば、異なるシステムからのトランザクティブIDを介したデータ重複排除を行う際に、WCCの問題に直面します。私の DataFusion 実装は、Bögeholz らによる「In-database connected component analysis」、arXiv 1802.09478 に基づいています。私は既に Spark の GraphFrames 用に同じアルゴリズムを実装していたため、これは明白な選択でした。

結果

PageRank

簡単な部分です。スケーラビリティを証明するために SMJ を使用しましたが、頂点が小さく(32M)、PageRank の状態も単純(列 rank (f64)、列 out-degree (i64)、参加フラグ (bool))であるため、HJ を使用することも可能です。HJ を使うとより高速です。PageRank は有向エッジ上で機能するため、グラフを対称化する必要はありません。エッジをディスクにオフロードし、状態を更新しながら(そして線形性を断ち切るためにディスクにもオフロードしながら)収束するまで反復するだけです。

計算時間は長いです。15回の完全な反復で約30分かかります。しかし、セットアップは速度ではなくメモリに関するものです。10億エッジのグラフ分析に、より現実的な数値を設定すれば、十分に高速に動作するでしょう(テスト済み)。グラウンドトゥルースと比較して数字を確認しました。100%一致しました(許容誤差 0.0001)。ここでも多くの最適化が可能です。理論的には、エッジを範囲でバケット化したり、ある種の範囲パーティショニングを行ったりすることが可能であり、SMJ が各反復で最大の結合側(エッジ)を再度ソートする必要がなくなります。また、Parquet が最良の選択肢であると100%確信しているわけではありません。また、結合と集計を融合させてみるのも興味深いです。各 Pregel 反復は edges <-[join] nodes-state -> group by + agg -> [join] -> nodes-state -> update nodes-state のようなものです。最初の2つのステージを融合できれば、パフォーマンスの観点から大きな利益が得られる可能性があります。一方、DataFusion でこれをどのように行うかはまだわかっていません。学ぶべきことがたくさんあります。

WCC

最も難しい部分です。20億エッジの Twitter グラフはすでに巨大です(エッジだけで 30 GB の CSV !!!)。しかし、WCC のためにはエッジを対称化する必要があります(または src, dst と dst AS src, src AS dst + その上の distinct を結合する必要があります)。そのため、ピーク時には 8GB の DataFusion プールしか使用せずに、約40億エッジを処理しています。フローが最初の数回の反復を乗り越えると、収縮プロセスによってエッジの量が劇的に減少し、アルゴリズムは10分で低メモリ負荷で終了します。

sem@fedora:~/github/graphframes-rs$ systemd-run --user --scope \
     -p MemoryMax=10G -p MemorySwapMax=0 \
     -p AllowedCPUs=0-1 \
     --setenv=RUST_LOG=graphframes_rs=info,datafusion=warn \
     ./target/release/run-algorithm twitter_mpi-v.parquet twitter_mpi-e.parquet wcc 42 file:///var/home/sem/Downloads/gf_wcc_out 8G 2
Running as unit: run-p316509-i284528.scope; invocation ID: 742f9296d31d426580b7ec8213422cf1
[2026-07-05T05:37:21Z INFO  graphframes_rs::algorithm::connectivity::connected_components] start WCC with run-id 017c0a23-2b20-4ffa-ac6b-6e2cb8d7203e
[2026-07-05T05:52:21Z INFO  graphframes_rs::algorithm::connectivity::connected_components] after preparation graph has 3228212374 edges
[2026-07-05T06:13:21Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 1, edges remaining: 840238268
[2026-07-05T06:17:39Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 2, edges remaining: 77322906
[2026-07-05T06:17:57Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 3, edges remaining: 5624128
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 4, edges remaining: 1075998
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 5, edges remaining: 230838
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 6, edges remaining: 97940
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 7, edges remaining: 42352
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 8, edges remaining: 16720
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 9, edges remaining: 8238
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 10, edges remaining: 3860
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 11, edges remaining: 1488
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 12, edges remaining: 982
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 13, edges remaining: 514
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 14, edges remaining: 132
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 15, edges remaining: 120
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 16, edges remaining: 40
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 17, edges remaining: 18
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 18, edges remaining: 10
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 19, edges remaining: 6
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 20, edges remaining: 4
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 21, edges remaining: 2
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc forward iteration 22, edges remaining: 0
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=21
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=20
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=19
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=18
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=17
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=16
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=15
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=14
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=13
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=12
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=11
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=10
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=9
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=8
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=7
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=6
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=5
[2026-07-05T06:17:59Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=4
[2026-07-05T06:18:00Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=3
[2026-07-05T06:18:01Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=2
[2026-07-05T06:18:12Z INFO  graphframes_rs::algorithm::connectivity::connected_components] cc back propagation step t=1
[2026-07-05T06:18:23Z INFO  graphframes_rs::algorithm::connectivity::connected_components] connected components written to file:///var/home/sem/Downloads/gf_wcc_out after 22 forward iterations
num-iterations: 22

結果は正しいです。Graphalytics はグラウンドトゥルースを提供しており、確認は簡単です。

memory D SELECT column1, count(*) as cnt FROM read_csv('twitter_mpi-WCC', delim=' ') GROUP BY column1 ORDER BY cnt DESC LIMIT 5;
┌──────────┬──────────┐
│ column1  │   cnt    │
│  int64   │  int64   │
├──────────┼──────────┤
│        1 │ 52515193 │
│ 27052874 │       67 │
│ 47269046 │       44 │
│ 45352761 │       33 │
│ 17516773 │       30 │
└──────────┴──────────┘
memory D SELECT component, count(*) as cnt FROM results  GROUP BY component ORDER BY cnt DESC LIMIT 5;
┌───────────┬──────────┐
│ component │   cnt    │
│   int64   │  int64   │
├───────────┼──────────┤
│         1 │ 52515193 │
│  27052874 │       67 │
│  47269046 │       44 │
│  45352761 │       33 │
│  17516773 │       30 │
└───────────┴──────────┘
memory D