人工智能机器学习分布式训练图计算后端【免费下载链接】angelA Flexible and Powerful Parameter Server for large-scale machine learning项目地址https://gitcode.com/gh_mirrors/an/angel点击查看免费下载本文围绕 Spark On AngelSONA框架下的 SCCStrongly Connected Components强连通分量算法展开完整讲解其在有向图上为同一强连通分量内节点赋予相同标签的核心原理、PSParameter Server与 Spark 双端协作机制、全部可配置参数以及基于spark-submit的集群提交脚本。读完本文你将掌握在大规模有向图上运行 SCC 算法的完整参数体系、资源估算方法以及结合仓库代码理解其分布式实现的关键脉络。1. 算法概述SCC强连通分量算法用于计算有向图的强连通分量。在有向图中若节点 A 与节点 B 之间存在双向可达路径即 A 能到达 B且 B 能到达 A则二者属于同一个强连通分量。SCC 算法为属于同一强连通分量的所有节点赋予相同的标签label从而将大规模有向图划分成若干个内部强连通的子图。Angel 在 Spark On Angel 框架下实现了面向大规模网络的 SCC 算法其核心思想与 CC连通分量算法一脉相承但针对有向图的强连通语义做了专门设计。作为对照CC 算法将图视为无向图并为连通分量赋标签相关实现与参数说明可参考仓库中的 docs/algo/sona/CC_sona_en.md中文版见 docs/algo/sona/CC_sona.md。1.1 双端协作的计算模型与 SONA 体系下其他图算法一致SCC 的实现采用PS 端存模型、Spark 端算图的分工模式PS 端负责维护每个节点的最新标签label估计值以及节点状态status。Spark 端维护网络的邻接表adjacency list并在每一轮迭代中从 PS 拉取最新的标签与状态估计值完成本地计算后再将更新推回 PS。这种设计将全局模型状态收敛到参数服务器统一管理使得算法可以在海量节点与边上并行推进这正是 Spark On Angel 处理大规模图数据的架构基础整体架构可参见 docs/overview/architecture.md。1.2 节点状态模型图中每个节点在算法运行期间处于两种状态之一final终态该节点的标签已经确定不会再发生变化non-final非终态该节点的标签尚未确定需要在后续迭代中继续判定。算法的目标就是通过多轮迭代逐步将越来越多的节点置为 final直至全部节点收敛为终态。2. 算法流程详解SCC 算法以分量内节点编号的最小值作为该强连通分量的标签label整体流程如下标记终态节点将与所有非终态邻居都不存在零入度zero in-degree或零出度zero out-degree关系的节点标记为 final 节点其标签即为当前所携带的标签值。沿边方向染色沿边方向对非终态节点进行染色painting颜色取路径上所有节点 id 的最小值。判定成分为终态若某个节点的颜色与其自身 id 相同则该节点所在的强连通分量即被确定将该分量内的节点标记为 final。扩散终态判定若某个节点存在指向颜色相同且仍为非终态节点的边则该节点同样属于该强连通分量将其标记为 final重复该步骤直到没有节点能从非终态变为终态。恢复标签依据染色过程前的标签恢复仍处于非终态节点的标签。循环迭代重复执行步骤 15直到所有节点都变为 final 状态。其中染色步骤的核心思想是在强连通分量内沿有向路径传播的最小节点 id 最终会回到分量内每个节点当某节点的颜色恰好等于自身 id 时说明它处于一个最小 id 节点可达自身、且自身可达最小 id 节点的闭合环路上从而证明该节点所在集合构成一个强连通分量。最终算法以每个强连通分量内部节点的最小 id 作为该分量的标签输出。说明上述 5 步流程与原文档一致反映了 Angel 实现中对终态判定 染色收缩两阶段交替推进的基本策略。3. 运行参数详解运行 SCC 任务需要配置三类参数IO 参数、算法参数与资源参数。3.1 IO 参数参数说明默认值input输入数据的 HDFS 路径每行表示一条边使用空格、Tab 或逗号等分隔符分隔必填无默认output输出结果的 HDFS 路径每行输出一对节点id 标签以 Tab 分隔必填无默认sep数据列分隔符空格 / 逗号 / Tab空格输入数据的组织方式与 SONA 图算法通用数据格式一致即一行一条边典型形如srcIdTABdstId或srcId,dstId。输出文件每一行对应节点 id 及其所属强连通分量的标签分量内最小节点 id二者以 Tab 分隔。3.2 算法参数参数说明partitionNum输入数据的 RDD 分区数。一般设置为 Spark 执行器数量 × 执行器核数 × 34 倍以保证并行度与数据倾斜容忍度psPartitionNumPS 上模型的分区数。最好是参数服务器数量的整数倍使每个 PS 承载的分区数相等、各 PS 负载尽可能均衡数据量较大时建议大于 500storageLevelRDD 存储级别可选DISK_ONLY/MEMORY_ONLY/MEMORY_AND_DISK。邻接表数据量较大时应考虑MEMORY_AND_DISK以避免频繁 GC 或 OOM从 SONA 图算法示例的实现结构看参见 spark-on-angel/examples/src/main/scala/com/tencent/angel/spark/examples/cluster/CCExample.scala这类图算法示例通常还支持useBalancePartition、src/dst列索引等扩展参数SCC 提交脚本中的useBalancePartition:true即用于开启基于节点度等信息的负载均衡分区缓解幂律分布图上的数据倾斜问题。3.3 资源参数参数说明ps.instance×ps.memoryPS 总数与单 PS 内存的乘积为 PS 总配置内存。为保证 Angel 不因内存不足而挂掉需将 PS 内存配置为模型大小的 2 倍左右num-executors×executor-memorySpark 执行器总数与单执行器内存的乘积为执行器总配置内存最好能存下 2 倍输入数据内存紧张时 1 倍也可运行但速度相对较慢资源估算示例原文给出的量级参考一个 100 亿条边的边集约占用 160G 空间此时配置20G × 20即 20 个执行器、每个 20G 内存即可满足。若资源确实紧张应优先增加分区数以摊薄单分区数据量而不是压缩内存。4. 任务提交SCC 任务通过spark-submit提交到 YARN 集群提交前需先执行环境变量脚本spark-on-angel-env.sh以加载 SONA 相关 JAR 路径。完整的提交脚本如下与原文一致inputhdfs://my-hdfs/data outputhdfs://my-hdfs/output source ./spark-on-angel-env.sh $SPARK_HOME/bin/spark-submit \ --master yarn-cluster\ --conf spark.ps.instances1 \ --conf spark.ps.cores1 \ --conf spark.ps.jars$SONA_ANGEL_JARS \ --conf spark.ps.memory10g \ --name cc angel \ --jars $SONA_SPARK_JARS \ --driver-memory 5g \ --num-executors 1 \ --executor-cores 4 \ --executor-memory 10g \ --class org.apache.spark.angel.examples.graph.SCCExample \ ../lib/spark-on-angel-examples-3.3.0.jar input:$input output:$output sep:tab storageLevel:MEMORY_ONLY useBalancePartition:true \ partitionNum:4 psPartitionNum:1脚本关键点说明--master yarn-cluster以 YARN Cluster 模式运行Driver 运行在集群中spark.ps.instances/spark.ps.cores/spark.ps.memory/spark.ps.jars指定 Angel PS 的实例数、核数、内存与依赖 JAR$SONA_ANGEL_JARS--jars $SONA_SPARK_JARS携带 Spark On Angel 侧依赖--class org.apache.spark.angel.examples.graph.SCCExampleSCC 示例入口类参数行input/output/sep/storageLevel/useBalancePartition/partitionNum/psPartitionNum直接以key:value形式追加在 JAR 路径之后由示例类内部的参数解析器读取。其中spark.ps.memory10g的取值需依据第 3.3 节的模型大小 2 倍原则调整sep:tab表示输入与输出均使用 Tab 分隔。关于 SONA 环境脚本与 JAR 的构建方式可查阅 spark-on-angel/README.mdPS 侧资源参数spark.ps.*的完整语义可参考 docs/deploy/config_details.md。5. 输出与结果解读任务结束后output目录下将生成形如下述的标签映射文件节点id \t 所属强连通分量的标签分量内最小节点id每个强连通分量内的所有节点共享同一个标签。由于标签取分量内最小节点 id结果天然具备确定性同一分量内的任意节点无论从哪条边路径进入最终都会收敛到相同的最小 id 标签。该结果文件可直接用于后续的社区划分分析、图结构压缩、环路检测等下游任务。6. FAQ 与调优建议算法效率与图结构强相关SCC 算法的效率高度依赖图的拓扑结构。稀疏图sparse graph上可能触发大量的循环迭代过程导致整体效率偏低。这是因为稀疏有向图中染色—判定—恢复的收敛链条较长每一轮只能将一小部分节点置为终态。针对稀疏图的应对思路结合资源参数中资源紧张时优先增加分区数的建议可在稀疏图上适当调大partitionNum与psPartitionNum以提升并行度、缩短单轮迭代时间同时结合useBalancePartition均衡各分区负载。PS 内存安全牢记ps.instance × ps.memory应约为模型大小的 2 倍否则大规模节点标签状态可能导致 PS 内存溢出。存储级别权衡MEMORY_ONLY最快但占用内存大DISK_ONLY最省内存但访问慢对超大图推荐MEMORY_AND_DISK以兼顾速度与稳定性。7. 与 CC 算法的对比及仓库延展阅读SCC 与 CC 同属为连通性赋标签类算法但语义不同CC将图视为无向图为连通分量赋标签适用于无向关系网络如好友网络、物理拓扑SCC面向有向图要求分量内任意两点双向可达适用于有向关系网络如网页链接、依赖关系、引用网络。在仓库中CC 的完整实现、扩展参数localLimit、compressIterNum、needReplicaEdge等及示例代码可参考算法文档docs/algo/sona/CC_sona_en.md集群示例spark-on-angel/examples/src/main/scala/com/tencent/angel/spark/examples/cluster/CCExample.scala连通分量实现目录spark-on-angel/graph/src/main/scala/com/tencent/angel/graph/connectedcomponent上述 CC 示例展示了 SONA 图算法的通用运行骨架参数解析 → 加载图 → transform → 保存结果SCC 的示例入口类org.apache.spark.angel.examples.graph.SCCExample与 CC 同构可参考其调用模式理解 SCC 任务的组装方式。部署层面的完整配置说明如 PS 内存、分区、检查点等可进一步阅读 docs/deploy/config_details.md 与 docs/deploy/resource_config_guide.md。赞分享人工智能机器学习分布式训练图计算后端【免费下载链接】angelA Flexible and Powerful Parameter Server for large-scale machine learning项目地址https://gitcode.com/gh_mirrors/an/angel点击查看免费下载相关推荐Angel 图计算系列基于 Spark On Angel 的分布式 Closeness 接近中心性算法实践Angel 图计算系列基于 Spark On Angel 的分布式 Closeness 接近中心性算法实践 本文聚焦 Angel 开源仓库中 docs/alg人工智能机器学习分布式训练图计算后端NumPy NEP 机制完全指南NEP 0 的目的、流程与状态机解析NumPy NEP 机制完全指南NEP 0 的目的、流程与状态机解析 NEPNumPy Enhancement ProposalNumPy 增强提议是人工智能机器学习分布式训练图计算后端Angel 图计算基于 Spark On Angel 的 K-Core 大规模图算法实现与运行指南Angel 图计算基于 Spark On Angel 的 K Core 大规模图算法实现与运行指南 K Corek 核分解是复杂网络研究中的重要指标用于人工智能机器学习分布式训练图计算后端上一篇Linux进程调度统计完全指南schedstat与调度延迟深度分析下一篇convex-backend开发者工具链从Justfile到调试环境配置创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考