Angel 图计算:基于 Spark On Angel 的 K-Core 大规模图算法实现与运行指南

原创2026-10-06 12:10:491,995 阅读
文章标签:人工智能机器学习分布式训练图计算后端

Angel 图计算:基于 Spark On Angel 的 K-Core 大规模图算法实现与运行指南

K-Core(k-核分解)是复杂网络研究中的重要指标,用于度量节点在网络中的“核心程度”。本文以 Angel 仓库中 kcore_sona_en.md 为骨架,系统讲解其基于 Spark On Angel 的大规模图 K-Core 计算实现:从“参数服务器只存变化节点、Executor 存邻接表与估计值数组”的稀疏迭代架构,到 IO 参数与算法参数全表、YARN 集群提交命令,再到源码级的 reader/writer 向量切换与 h-index 计算细节。读完本文,你将能够独立完成 K-Core 任务的参数配置、集群提交与结果解读,并理解该算法在 Spark Executor 与 Angel 参数服务器之间协同收敛的底层原理。

K-Core 计算架构图:PS 端存储 reader 与 writer 两个节点向量,Executor 端存储邻接表与 est[][] 估计值数组

1. K-Core 算法与它在 Angel 中的定位

K-Core(k-degenerate graph)是图论中经典的图分解概念:图的 k-核是指反复删除度数小于 k 的节点后剩余的最大导出子图,节点的 coreness(核度) 即该节点所属的最大 k 值。由于 coreness 反映了节点在网络中嵌入的紧密程度,K-Core 在社区发现、关键节点识别、网络鲁棒性分析等复杂网络研究领域有着广泛应用。

在 Angel 项目中,K-Core 属于 Spark On Angel 图计算(graph)模块,核心算法类为 KCore.scala,示例程序入口为 KCoreExample.scala。中文版原始文档见 kcore_sona.md。

2. 架构设计:为什么 coreness 不能全部放在参数服务器

按照 K-Core 的算法原理,计算一个节点的 coreness 需要扫描其所有邻居的 coreness 值。如果简单地把全部节点的 coreness 都存储在参数服务器(PS)上,那么每一轮迭代,每个 Executor 都需要把所辖节点的所有邻居的 coreness 从 PS 端拉取下来,通信量巨大、扩展性差。

Angel 的实现充分利用了迭代的稀疏性:随着迭代推进,大部分节点的 coreness 不再变化,真正需要更新的节点比例会越来越小。因此设计上做了拆分:

  • Executor 端:存储图的邻接表,以及边对应的可变数据 est[][](每个节点邻居的 coreness 估计值数组),避免每次迭代都从远端拉取全部邻居的 coreness;
  • PS 端:只存储发生变化的节点的 coreness,用两个节点向量 reader 与 writer 组织读写。

这一设计在源码中有直接印证。查看 KCorePSModel.scala,PS 侧模型封装了四个 PSVector:

  • inMsgs:对应文档中的 reader,存储上一轮迭代更新过的节点的 coreness;
  • outMsgs:对应文档中的 writer,存储本轮迭代正在更新的节点 coreness;
  • cores:存储每个节点的最终 coreness 结果;
  • staticCores:仅在 sparse/mid 模式下使用,存储预先确定 coreness 的静态节点。

其中 inMsgs/outMsgs/cores 以 RowType.T_INT_SPARSE_LONGKEY 类型组织成稀疏长整型键向量(sparse/mid 模式为 4 行矩阵,其余模式为 3 行矩阵),对应 Apply 方法中的矩阵构建逻辑。

3. 迭代计算流程:reader 与 writer 的交替

文档给出的 K-Core 具体计算流程分为四步:

  1. 拉取更新:Executor 从 reader 拉取 est[][] 中可更新节点的 coreness,并对其进行更新;
  2. 计算 h-index:对 Executor 中的每个节点,计算其对应 est[] 的 h-index,更新该节点的 coreness 估计值;
  3. 推送结果:将步骤 2 中更新了的 coreness 推送到 writer;
  4. 角色切换:所有 Executor 完成步骤 1~3 的计算之后,PS 端的 writer 即为下一轮新的 reader,同时将 writer 重置。

四个步骤在源码中都有对应实现:

  • 步骤 4 的角色切换由 KCorePSModel.scala 的 resetMsgs() 完成:交换 inMsgs 与 outMsgs 的引用,然后调用 outMsgs.reset 清空本轮写入,使其作为下一轮的 reader 继续承载新数据;
  • PS 端的写入与切换还可以由参数服务器函数(PSF)UpdateKCore.scala 在服务器侧完成:update() 同时读取 inMsgs、outMsgs、cores 三行,把 outMsgs 中的值写入 cores(computeCores),再通过 switchWriteAndRead 清空 inMsgs 存储并与 outMsgs 交换存储,实现一轮迭代的原子收敛;
  • 步骤 1~2 的 Executor 侧计算位于 KCorePartition.scala:第一轮(firstIterations,见 L69 起)按 batch 计算全部节点的 coreness;后续轮次(nextIterationsByBatch,见 L146 起)通过 model.readTag(keys) 只拉取被标记为“可能变化”的节点,只对这些节点重新计算 h-index——这正是文档所强调的“利用迭代稀疏性”的落地方式。

整个 transform 主流程在 KCore.scala 中体现为:加载边 → 统计节点 ID 范围与边数 → 启动 PS 并构建模型 → 按 execMode 构建分区图 → 初始化 coreness → 进入 do { ... } while (numMsgs > 0) 迭代直到没有新消息(节点 coreness 全部收敛)→ 按 batch 拉取结果写出。

4. 运行参数详解

4.1 IO 参数

参数 说明
input HDFS 路径,输入网络数据。每行两个 long 型整数 id 节点,以空白符或逗号分隔,表示一条边
output HDFS 路径,输出节点对应的 coreness。每行输出一个节点及其 coreness 值,两者以 tab 符分隔
sep 输入数据分隔符,支持:空格(space)、逗号(comma)、tab,默认值为空格
srcIndex 源节点索引,默认 0
dstIndex 目标节点索引,默认 1

需要补充说明的是:集群版示例 KCoreExample.scala 中,若未显式传入 sep,代码兜底默认值为 Delimiter.TAB,因此实际提交任务时建议像官方示例那样显式指定 sep:space,避免歧义。

4.2 算法参数

参数 说明
batchSize 节点更新 batch 的大小
partitionNum 输入数据分区数
psPartitionNum PS 分区数
useBalancePartition 是否使用均衡分区,默认 false
balancePartitionPercent 均衡分区度,默认 0.7
needReplicaEdge 是否需要将边反向复制构造无向图。示例中设为 true,源码 KCore.scala 通过 edges.flatMap(f => Iterator((f._2, f._1), (f._1, f._2))) 实现双向边展开

4.3 源码中的扩展参数

集群版示例 KCoreExample.scala 实际解析的参数比文档更多,可在需要时按需使用:

  • pullBatchSize:从 PS 拉取 coreness 的批量大小,默认 1000;
  • storageLevel:图数据 RDD 的存储级别,默认 MEMORY_ONLY;
  • execMode:运行模式,可选 full / sparse / mid / dense,默认 full(详见第 6 节);
  • degreeThreshold(内部映射为 topK):dense / mid 模式下的度数阈值,用于剪枝低度节点,默认 1;当 execMode 为 full 或 sparse 时被强制置为 -1(即不参与阈值过滤);
  • initialCorePath:可选,预置部分节点初始 coreness 的文件路径(默认 null),通过 setInitialCore 注入;
  • staticCorePath:sparse / mid 模式必须提供的静态 core 节点集路径(可多个路径逗号分隔),否则会直接断言失败;
  • checkpoint:是否周期性对 PS 矩阵做 checkpoint,默认 false;开启后在迭代 0 轮与每 50 轮各执行一次 model.checkpoint(curIteration);
  • numFirsts:前 N 轮对全部节点做全量计算,默认 1,之后进入只算变化节点的稀疏迭代;
  • cpDir:checkpoint 目录,未指定时回退到 GraphIO.defaultCheckpointDir。

5. 任务提交示例

5.1 YARN 集群模式

进入 angel 环境的 bin 目录,按如下方式提交(命令来自原文档,参数说明为补充注释):

input=hdfs://my-hdfs/data
output=hdfs://my-hdfs/model

source ./spark-on-angel-env.sh
$SPARK_HOME/bin/spark-submit \
  --master yarn-cluster\
  --conf spark.ps.instances=1 \          # PS 实例数(参数服务器个数)
  --conf spark.ps.cores=1 \              # 每个 PS 占用的 CPU 核数
  --conf spark.ps.jars=$SONA_ANGEL_JARS \ # Angel PS 侧依赖 jar 包
  --conf spark.ps.memory=10g \           # 每个 PS 的堆内存大小
  --name "kcore angel" \
  --jars $SONA_SPARK_JARS  \             # Spark On Angel 客户端侧依赖 jar 包
  --driver-memory 5g \
  --num-executors 1 \
  --executor-cores 4 \
  --executor-memory 10g \
  --class com.tencent.angel.spark.examples.cluster.KCoreExample \
  ../lib/spark-on-angel-examples-3.1.0.jar
  input:$input output:$output sep:space batchSize:1000 partitionNum:2 psPartitionNum:2 \
  useBalancePartition:false needReplicaEdge:true

其中 input、output 即第 4.1 节中的 IO 参数;sep:space 显式指定输入分隔符为空格;batchSize:1000 将节点更新 batch 设为 1000;partitionNum:2 表示输入数据分为 2 个分区;psPartitionNum:2 表示 PS 侧分为 2 个分区;useBalancePartition:false 关闭均衡分区;needReplicaEdge:true 构造无向图。提交后可通过 YARN 日志观察 curIteration 与 numMsgs 的收敛过程(源码中每一轮都会打印 numMsgs 与 curMinCore)。

5.2 本地模式运行

仓库中还提供了本地模式示例 local/KCoreExample.scala:直接以 local 模式创建 SparkContext 与 PSContext,使用仓库内置数据 data/bc/edge 作为输入、输出到 model/kcore/edge,设置 partitionNum=3、psPartitionNum=2、execMode=full,适合在小规模数据上快速验证算法与排查问题。

6. 源码级原理剖析

6.1 KCore.transform 主流程

KCore.scala 的 transform 完整描述了任务的执行链路:

  1. 从 DataFrame 中提取边 (src, dst) 并持久化;
  2. 统计节点最小/最大 ID 与边数;
  3. 创建 PSContext,用 ModelContext(psPartitionNum, minId, maxId, ...) 构建 KCorePSModel;
  4. 按 execMode 调用 makeDenseGraph / makeSparseGraph / makeMidGraph / makeFullGraph 将边组装为 RDD[KCorePartition];
  5. 初始化 coreness(可用 initialCore 预置,否则按 batch 初始化,sparse/mid 模式还会推送 static cores);
  6. 进入迭代循环直到 numMsgs == 0,期间可按需压缩子图与 checkpoint;
  7. 从 cores 批量拉取结果,按 coreness 降序排序后写出。

6.2 execMode 四种构图模式

从 KCore.scala 的四个构图方法可以推断四种模式的设计意图:

  • full:全部节点参与计算,不依赖 PS 侧的静态 core 信息,构图最直接,适合整体规模可控的场景;
  • dense:构图时按 degreeThreshold 过滤低度节点,迭代过程中当 curMinCore 超过阈值时执行 compress 压缩子图,适合节点稠密的图;
  • sparse:必须提供 staticCores,利用 PS 上静态 core 过滤大量已收敛节点,只保留少量需要计算的节点,适合“绝大多数节点 coreness 已知”的稀疏场景;
  • mid:介于 dense 与 sparse 之间,同样需要 staticCores,并在构图与迭代中做混合过滤。

文档示例使用的是默认的 full 模式;degreeThreshold 在 full/sparse 下被置为 -1 正是为了让阈值过滤不生效。

6.3 h-index 计算与迭代收敛

Executor 侧核心计算是 KCorePartition.scala 的 hindexWithPrior:对邻居 coreness 数组排序后,从大到小递减计数,得到满足“至少有 k 个邻居的 coreness 不低于 k”的最大 k 值,并以此更新节点 coreness。只有 newCore < x(节点 coreness 确实下降)时才会写入 outMsgs 并标记其邻居为待更新节点。主循环 do { ... } while (numMsgs > 0) 在没有任何节点再发生变化时终止,保证算法收敛到稳定的 coreness 结果。

6.4 PSF 与参数服务器的交互

K-Core 通过 Angel 的 PSF(Parameter Server Function)机制把部分计算下沉到 PS 端执行。UpdateKCore.scala 展示了 update() 的实现:在服务器行上同时获取 inMsgs、outMsgs、cores 三行向量,将 outMsgs 中的新 coreness 写入 cores,并通过 switchWriteAndRead 完成读写角色切换。这种“在数据所在处完成更新”的设计,避免了将整行向量在网络间搬移,是稀疏大图迭代能够高效运行的关键之一。

7. 结果输出与后续使用

任务完成后,output 指向的 HDFS 路径下会生成结果文件:每行一个节点 ID 及其对应的 coreness 值,两者以 tab 分隔,结果按 coreness 降序排序(对应 KCore.scala 的 save 与 sortBy(_._2, false) 逻辑)。节点 ID 为 long 型,coreness 为 int 型,输出 DataFrame 的 schema 由 transformSchema 定义。得到每个节点的 coreness 后,即可作为节点特征用于社区发现、关键节点识别等下游复杂网络分析任务;如需预置部分节点的 coreness 以加速收敛,可在提交时通过 initialCorePath 参数加载初始值。

登录后查看全文
angel