使用 10GB RAM 的十亿级图算法：我喜欢 DataFusion

太长了；我使用 Apache DataFusion 实现了图映射缩减。在可能的情况下，我将所有内容卸载到磁盘，并将算法设计为依赖于批量扫描而不是随机访问。 DataFusion 处理溢出、排序合并连接、聚合、规划和执行，因此我的代码非常轻量级。我在严格模式下测试了它，通过带有硬内存限制的 systemd-run 运行它。有用。当然，我也遇到了一些问题：例如，我经常遇到极端场景下FairSpillPool的死锁，而且我还没有找到让SMJ对磁盘上的数据进行预排序的方法。但它有效。我可以使用 5 GB 内存在具有 10 亿条边的有向图（来自 Graphalytics 数据集的 graph500-26）上计算 PageRank。或者，我可以使用 10 GB 内存识别具有 20 亿条边的图中的所有弱连接组件（来自同一数据集集合的 twitter_mpi）。 NetworkX 和 Igraph 都无法做到这一点；大多数现有的图算法都要求图适合内存。以前，我认为您需要 Apache Spark 和 GraphFrames 来进行十亿级图形分析。然而现在，我认为你所需要的只是一台笔记本电脑。我完全改变了我对使用 Apache DataFusion 进行图形分析的旧看法。设置我测试了两个任务。 PageRank 什么是 PageRank？任务是计算来自 Graphalytics 数据集的 graph500-26 上的 PageRank： 键值 节点数 32,804,978 边数 1,051,922,853 定向错误内存限制 5 GB DataFusion 池大小 4 GB PageRank 是最流行的图中心性算法之一，用于搜索结果排名和反欺诈评分。我的 DataFusion 实现是经典的 Pregel：批量同步并行算法（又名 Map-Reduce），我使用连接和聚合来表达。与 Spark 的 GraphFrames 库核心内容非常相似。弱连通分量 什么是弱连通分量？任务是从同一数据集中识别 twitter_mpi 上的所有弱连接组件： 键值 节点数 52,579,682 边数 1,963,263,821 定向真实内存限制 10 GB DataFusion 池大小 8 GB WCC 是任何身份（实体）解析问题的核心部分。例如，当您需要通过传递 ID 从不同系统进行数据重复删除时，您最终会遇到 WCC 问题。我的 DataFusion 实现基于“数据库内连接组件分析”，Bögeholz 等人，arXiv 1802.09478。我已经为 Spark 的 GraphFrames 实现了相同的算法，因此这是一个显而易见的选择。结果 PageRank 一个简单的部分。我使用 SMJ 只是为了证明可扩展性，但也可以使用 HJ，因为顶点很小（32M）并且 PageRank 状态很简单：一列排名（ f64 ），一列出度（ i64 ），参与标志（ bool ）。有了HJ，速度更快。 PageRank 在有向边上工作，因此不需要使图对称。只需将边缘卸载到磁盘并通过更新状态进行迭代（并卸载到磁盘以打破沿袭）直到收敛。计算时间较长：15 次完整迭代大约需要 30 分钟。但设置与内存有关，而不是速度。给它一些更实际的数字来进行 1B 图形分析，它会运行得足够快（我测试过）。我根据实际情况检查了数字：100% 匹配（容差为 0.0001）。这里也可以进行很多优化：理论上可以按范围对边进行存储或进行某种范围分区，因此 SMJ 不需要在每次迭代时再次对最大的连接边（边）进行排序以获得三元组。我也不是 100% 镶木地板是这里的最佳选择。尝试融合 join+agg 也会很有趣：每个 Pregel 迭代都像edges <-[join]nodes-state ->group by + agg ->[join]->nodes-state->updatenodes-state 。如果我能将前两个阶段融合在一起，从性能的角度来看，这将是一个巨大的胜利。同时我还不知道如何在 DataFusion 中做到这一点：有很多东西需要学习。 WCC 最难的部分。 2B 边缘 twitter 图已经很大（它的边缘在 CSV 中为 30 GB！！！）。但对于 WCC，我们需要对边进行对称化（或者在 src、dst 和 dst AS src 之间进行并集，src AS dst + 顶部的不同），因此在高峰期，我们仅使用 8GB DataFusion 池就可以处理近 40 亿条边。流程在前几次迭代中幸存下来后，收缩过程会急剧减少边缘数量，算法在 10 分钟内结束，内存压力较低。 sem@fedora:~/github/graphframes-rs$ systemd-run --user --scope \ -p MemoryMax = 10G -p MemorySwapMax = 0 \ -p 允许的CPU = 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 作为单元运行： run-p316509-i284528.scope ；调用 ID：742f9296d31d426580b7ec8213422cf1 [2026-07-05T05:37:21Z INFO graphframes_rs::algorithm::connectivity::connected_components] 使用 run-id 启动 WCC 017c0a23-2b20-4ffa-ac6b-6e2cb