在10GB内存上运行十亿级图算法：我爱DataFusion
摘要
一位开发者展示，Apache DataFusion 可以通过将数据卸载到磁盘，在配备5–10GB内存的笔记本电脑上执行 PageRank 和弱连通分量等十亿级图分析，从而挑战对 Spark/GraphFrames 的需求。
暂无内容
查看缓存全文
缓存时间: 2026/07/31 16:59
# 使用10GB内存处理十亿级图算法：我爱 DataFusion！
来源：https://semyonsinchenko.github.io/ssinchenko/post/datafusion-graphs-cc-2/
## TLDR；
我使用 Apache DataFusion 实现了一个图 map-reduce。在可能的情况下，我将所有内容卸载到磁盘，并将算法设计为依赖批量扫描而非随机访问。DataFusion 处理溢出、排序合并连接、聚合、规划和执行，所以我的代码非常轻量。我通过 `systemd-run` 以硬内存限制的严格模式进行了测试。它确实可行。当然，我也遇到了一些问题：例如，在极端场景下我经常遇到 `FairSpillPool` 的死锁，而且我还没有找到方法让 SMJ 利用磁盘上已排序的数据。但它确实能工作。我可以在 5GB 内存下计算具有十亿条边的有向图（Graphalytics 数据集中的 `graph500-26`）的 PageRank。或者，我可以在 10GB 内存下识别具有二十亿条边的图（同一数据集集合中的 `twitter_mpi`）中的所有弱连通分量。NetworkX 和 Igraph 都做不到这一点；大多数现有图算法要求图能够装入内存。以前，我认为十亿级图分析需要 Apache Spark 和 GraphFrames。但现在，我认为你只需要一台笔记本电脑。我完全改变了我之前关于使用 Apache DataFusion 进行图分析的观点（https://semyonsinchenko.github.io/ssinchenko/post/datafusion-graphs-cc/#principal-limitations）。
## 环境配置
我测试了两个任务。
### PageRank
什么是 PageRank？(https://en.wikipedia.org/wiki/PageRank)
任务是在 Graphalytics 数据集 (https://ldbcouncil.org/benchmarks/graphalytics/datasets/) 的 `graph500-26` 上计算 PageRank：
| 指标 | 值 |
|---|---|
| 节点数 | 32,804,978 |
| 边数 | 1,051,922,853 |
| 有向 | False |
| 内存限制 | 5 GB |
| DataFusion 池大小 | 4 GB |
PageRank 是最流行的图中心性算法之一，应用范围从搜索结果排名到反欺诈评分。我的 DataFusion 实现是经典的 Pregel：批量同步并行算法（即 Map-Reduce），我通过连接和聚合来表达它。这与 Spark 的 GraphFrames 库核心中的实现非常相似。
### 弱连通分量
什么是弱连通分量？(https://en.wikipedia.org/wiki/Weak_component)
任务是在同一数据集的 `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 (https://arxiv.org/abs/1802.09478)。我已经为 Spark 的 GraphFrames 实现了相同的算法，所以这是一个显而易见的选择。
## 结果
### PageRank
简单部分。我使用 SMJ 只是为了证明可扩展性，但也可以使用 HJ，因为顶点数量很小（32M），而且 PageRank 状态非常简单：一列 `rank`（`f64`）、一列 `out-degree`（`i64`）、一个参与标志（`bool`）。使用 HJ 会更快。PageRank 作用于有向边，因此不需要对图进行对称化。只需将边卸载到磁盘，并通过更新状态（同时将状态卸载到磁盘以打破血缘关系）进行迭代，直到收敛。
计算时间较长：15 次完整迭代大约需要 30 分钟。但这里的重点是内存，而不是速度。给它一些更现实的十亿级图分析数据，它会运行得足够快（我测试过）。我将结果与基准答案进行了核对：100% 匹配（容差为 `0.0001`）。这里还可以做很多优化：理论上可以按范围对边进行分桶，或做某种范围分区，这样 SMJ 就不需要在每次迭代中重新对最大的连接侧（边）进行排序以获得三元组。此外，我也不能 100% 确定 parquet 是这里的最佳选择。尝试融合 join+agg 也会很有趣：每次 Pregel 迭代就像是 `edges <-[join] nodes-state` -> `group by + agg` -> `[join] -> nodes-state` -> `update nodes-state`。如果我能将前两个阶段融合在一起，从性能角度来看将是一个巨大的胜利。但与此同时，我还不知道如何在 DataFusion 中实现这一点：还有很多东西要学。
### WCC
最困难的部分。20 亿条边的 twitter 图已经非常巨大（其边在 CSV 中占 30 GB！！！）。但对于 WCC，我们需要对边进行对称化（或者在 `src, dst` 和 `dst AS src, src AS dst` 之间做 union，并在其上做 `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
```
相似文章
@techwith_ram：一个1000万文档的语料库以float32格式占用31GB内存。大多数团队遇到这一瓶颈后会转向托管向量数据库。每月400美元……
turbovec 是一个开源的 Rust 向量索引，使用 Google Research 的 TurboQuant 算法，实现了16倍压缩，搜索速度比 FAISS 更快，并且集成了 LangChain、LlamaIndex 和 Haystack 等 RAG 框架。
@akshay_pachaar：谷歌刚刚发布了一款新LLM！你只需8GB内存就能在本地运行。让我们用自己的数据来微调它（完全本地运行…
谷歌发布了一款新LLM，只需8GB内存即可在本地运行。推文展示了如何在本地利用个人数据对其进行微调。
Slater – 专为读密集型图设计的低内存图数据库
Slater 是一款低内存图数据库，专为读密集型工作负载设计。它使用固定的缓存预算从磁盘提供大型图服务，仅需几百 MB 的 RAM 即可查询数亿节点和数十亿边，同时兼容标准 Bolt 协议并支持实时写入。
@N01ennn: 微软将其图系统与向量RAG在8k、120k和完整百万token上下文窗口上对比，百万……
微软研究院的LazyGraphRAG在8k、120k和百万token上下文的数据本地问题上超越了向量RAG，以十分之一的成本赢下92/90/91%的胜率，现已在GitHub上开源。
我如何仅用24GB内存运行193B参数模型
介绍 Iris Ai，一个在消费级硬件上将查询路由至8个专用LLM的系统，通过每次仅激活一个模型和动态模型交换，以低内存实现大模型性能。