Angel 图计算:基于 Spark On Angel 的 K-Core 大规模图算法实现与运行指南
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[][] 估计值数组](docs/img/kcore_structure.png)
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 具体计算流程分为四步:
- 拉取更新:Executor 从
reader拉取est[][]中可更新节点的 coreness,并对其进行更新; - 计算 h-index:对 Executor 中的每个节点,计算其对应
est[]的 h-index,更新该节点的 coreness 估计值; - 推送结果:将步骤 2 中更新了的 coreness 推送到
writer; - 角色切换:所有 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 完整描述了任务的执行链路:
- 从 DataFrame 中提取边
(src, dst)并持久化; - 统计节点最小/最大 ID 与边数;
- 创建 PSContext,用
ModelContext(psPartitionNum, minId, maxId, ...)构建 KCorePSModel; - 按
execMode调用makeDenseGraph/makeSparseGraph/makeMidGraph/makeFullGraph将边组装为RDD[KCorePartition]; - 初始化 coreness(可用
initialCore预置,否则按 batch 初始化,sparse/mid 模式还会推送 static cores); - 进入迭代循环直到
numMsgs == 0,期间可按需压缩子图与 checkpoint; - 从
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 参数加载初始值。