Volcano 调度器 Gang-Aware Eviction 设计：基于 HyperNode 与 Bundle 的拓扑感知驱逐机制

Volcano 调度器 Gang-Aware Eviction 设计基于 HyperNode 与 Bundle 的拓扑感知驱逐机制【免费下载链接】volcanoA Cloud Native Batch System (Project under CNCF)项目地址: https://gitcode.com/GitHub_Trending/vol/volcano导读本文基于 Volcano 开源仓库的设计文档 docs/design/gang-aware-eviction-design.md深入讲解 Volcano 调度器如何让驱逐Eviction决策同时具备拓扑感知与Gang 感知能力。文中将覆盖两阶段搜索管道、SearchPurposeAPI 扩展、专用的gangPreempt/gangReclaim动作、Safe/Whole Bundle 受害者模型、Nomination 提交机制以及评分排序策略并结合仓库源码给出可验证的实现证据帮助读者理解如何在多租户、带网络拓扑约束的批量计算集群中让驱逐行为既精准又收敛。背景与动机为什么驱逐需要 Gang-Aware现有调度动作之间的一致性缺口Volcano 调度器中的各类调度动作Action各自擅长解决特定问题但组合使用时存在一致性缺口。设计文档明确指出allocate动作通过 HyperNode 实现了拓扑感知Topology-Aware而preempt与reclaim仍然以任务task为单位逐个挑选受害者victim。这种不一致导致一个典型的负面后果一个调度周期可能从多个不同的 Gang分布式任务组中各驱逐一个任务造成大范围扰动wide disruption却无法保证目标 Gang 在驱逐之后能够被成功放置。也就是说驱逐动作做了功但目标 Gang 依然无法调度。拓扑缺口对于带有网络拓扑约束network-topology constraints的作业现有的驱逐路径在挑选受害者时可能跨越多个节点却没有先承诺一个连贯的 HyperNode。对需要协调放置coordinated placement的 Gang 型作业而言这种驱逐既昂贵又不可预测。问题的两分法设计文档将问题拆解为两个子问题并分别给出答案调度器应该在哪里搜索分配与驱逐——答案来自HyperNode 梯度HyperNode gradients调度器应该驱逐谁——答案来自Gang-aware 的 Bundle受害者包模型。设计目标与边界目标Goals同时实现拓扑感知与 Gang 感知让allocate、preempt、reclaim共享同一个 HyperNode 约束模型即使它们的优化目标仍然不同保持插件兼容性不破坏现有插件契约控制调度器延迟让驱逐决策的复杂度有界增量采纳现有集群继续运行传统行为除非通过配置显式启用新路径。非目标Non-Goals不将所有插件重写为 Job 级接口不将传统preempt/reclaim动作与新设计完全合并统一。设计总览两阶段执行管道调度器的执行模型是一个两阶段管道Stage 1搜索空间收缩。调度器向拓扑插件请求有序的 HyperNode 梯度并用它们缩小搜索空间。每个 HyperNode 是一个搜索单元search unit一个作业的所有分配或驱逐决策都在单个 HyperNode 内评估。每个 HyperNode 通过ssn.RealNodesList映射到具体的真实节点见 pkg/scheduler/framework/session.go注释为RealNodesList maps hyperNode Name - nodes under the hyperNode。Stage 2动作特定逻辑。调度器在 HyperNode 内部执行动作相关逻辑分配allocate按偏好顺序遍历 HyperNode 梯度在每个梯度内评估该梯度下的所有 HyperNode 并选出最佳者若找不到可行分配则继续下一个梯度驱逐preempt/reclaim按顺序尝试 HyperNode一旦某个 HyperNode 产生有效受害者集合 驱逐后可行放置立即停止。这一设计将拓扑从事后的检查转变为事前的约束同时尽可能保留原有行为。API 与框架变更为梯度回调引入搜索目的为了让同一个拓扑 API 同时服务于分配与驱逐梯度回调被扩展了显式的搜索目的Search Purpose。这一设计在仓库源码中已落地实现pkg/scheduler/api/types.go 定义了SearchPurpose枚举与两个梯度函数类型type SearchPurpose int const ( // PurposeAllocate indicates the caller is performing placement/allocation search. PurposeAllocate SearchPurpose iota // PurposeEvict indicates the caller is performing eviction search. PurposeEvict ) // HyperNodeGradientForJobFn group hyperNodes into several gradients, // and discard hyperNodes that unmatched the job topology requirements. type HyperNodeGradientForJobFn func(job *JobInfo, hyperNode *HyperNodeInfo, purpose SearchPurpose) [][]*HyperNodeInfo // HyperNodeGradientForSubJobFn group hyperNodes into several gradients, // and discard hyperNodes that unmatched the subJob topology requirements. type HyperNodeGradientForSubJobFn func(subJob *SubJobInfo, hyperNode *HyperNodeInfo, purpose SearchPurpose) [][]*HyperNodeInfo在这个契约下插件可以为PurposeAllocate返回更宽的梯度集合为PurposeEvict返回有界的 Top-K 集合。第一个注册了该函数的已启用插件决定梯度结果低 tier 中同样注册该函数的插件将被忽略——这一赢家通吃winner-takes-all语义在 pkg/scheduler/framework/session_plugins.go 的Session.HyperNodeGradientForJobFn/HyperNodeGradientForSubJobFn中实现按 tiers 顺序遍历插件找到第一个注册函数即返回若没有任何插件注册则回退为只返回输入的 HyperNode[][]*api.HyperNodeInfo{{hyperNode}}。对应的注册接口AddHyperNodeGradientForJobFn/AddHyperNodeGradientForSubJobFn位于 pkg/scheduler/framework/session_plugins.go。两层级排序契约[][]*HyperNodeInfo的返回类型具有两层级的排序契约外层切片有序的梯度gradient列表内层切片同一偏好层级preference level上的 HyperNode 集合。对PurposeAllocate梯度按 HyperNode tier 组织并按 tier 升序排列即更紧密的拓扑范围优先尝试更宽的范围作为 fallback。梯度内部分配会评估所有 HyperNode并通过评分scoring而非列表位置选出最佳者。对PurposeEvict排序应偏向可行性与延迟。梯度仍然基于 tier但按 tier 降序遍历这样在需要时更宽的 HyperNode 会被更早纳入受害者搜索。梯度内部的 HyperNode 应按可行性分数排序例如按目标 HyperNode 中的可用资源排序。源码中的目的区分实现network-topology-aware插件在 pkg/scheduler/plugins/network-topology-aware/network_topology_aware.go 中注册了两个梯度回调硬拓扑模式IsHardTopologyMode下调用hyperNodeGradientFn生成按 tier 升序的梯度当purpose api.PurposeEvict时额外调用reverseAndCapEvictionGradients反转顺序并限制返回的 HyperNode 数量DefaultEvictMaxHyperNodes为该文件 第 64 行 定义的默认最大返回数量。梯度构建的核心逻辑hyperNodeGradientFn同文件 L601-L647从搜索根出发做 BFS用isEligibleHyperNode过滤不合格节点然后按 tier 升序组织结果。值得注意的细节是isEligibleHyperNodeL649-L671对PurposeEvict与分配采用不同的资源预过滤逻辑驱逐场景检查minResource.LessEqual(hnResourceStatus.allocatable, api.Zero)可分配量不足才放行而分配场景检查 idle 与 futureIdle 两个维度体现了驱逐搜索放宽约束、分配搜索收紧约束的设计意图。单元测试 pkg/scheduler/framework/session_plugins_test.go 中的TestHyperNodeGradientForJobFn_ForwardsPurposeAndKeepsWinnerTakesAll与TestHyperNodeGradientForJobFn_NoPluginKeepsCurrentFallback验证了目的透传、赢家通吃与无插件回退三条语义pkg/scheduler/plugins/network-topology-aware/network_topology_aware_test.go 的TestHyperNodeGradientForSubJobFn_NoSubJobPolicyRespectsHardTopology则验证了 SubJob 场景下的梯度行为。专用动作gangPreempt 与 gangReclaim设计文档选择不扩展现有动作而是引入两个专用动作gangPreempt和gangReclaim。现有preempt与reclaim动作保持不变Gang 感知行为被隔离在新动作中以获得更干净的发布面和更低的回归风险。actions: allocate, backfill, gangPreempt, gangReclaim tiers: - plugins: - name: gang - name: priority - name: drf - name: predicates - name: nodeorder - name: binpack要点用户通过在 action 链中显式选择gangPreempt/gangReclaim来主动启用该特性新动作不得与传统的preempt/reclaim在同一个调度器 action 列表中共存在该模型下Gang 感知执行不会与同一周期内的任务中心传统循环共享控制流。从源码看这两个动作在仓库中已注册为正式动作framework.RegisterAction(gangpreempt.New())与framework.RegisterAction(gangreclaim.New())位于 pkg/scheduler/actions/factory.gogangpreempt与gangreclaim包分别位于 pkg/scheduler/actions/gangpreempt/gangpreempt.go 与 pkg/scheduler/actions/gangreclaim/gangreclaim.go其Name()分别返回gangpreempt与gangreclaim。pkg/scheduler/api/types.go的EvictionKind枚举也相应增加了EvictionKindGangPreempt与EvictionKindGangReclaim两个成员pkg/scheduler/api/types.go。HyperNode 作用域的驱逐流程逐 HyperNode 的贪心处理对每个 pending 的 preemptor Gang动作首先以PurposeEvict获取有序的拓扑 HyperNode 集合——插件可以提前对集合设上限以控制延迟。然后按顺序贪心处理每个 HyperNode。Bundle最小驱逐选择单元Bundle 是此动作中最小的驱逐选择单元一旦选中其任务作为一次决策被一起驱逐其扰动成本在 Bundle 作用域而非任务作用域上评估。每个候选作业的任务被划分为两类 bundleSafe bundle安全包包含富余任务surplus tasks或来自已低于其有效可用性目标effective availability target的 Gang 的任务Whole bundle整体包包含核心任务core tasks驱逐它们意味着打破该 Gang。注意候选作业中的每个任务要么属于其 safe bundle要么属于其 whole bundle。这个划分赋予了动作一个显式的扰动模型safe bundle 是低成本机会whole bundle 是高成本决策只有在 safe 机会不足时才被考虑。两趟排序与一次性插件过滤每个 HyperNode 的 Bundle 排序分两趟进行第一趟调度器对所有原始rawbundle 排序然后将其扁平化为有序任务切片交给插件过滤。插件Reclaimable/Preemptable对每个 HyperNode 恰好调用一次one-shot call传入该有序切片。这一点对capacity这类有状态插件至关重要重复的按 Job 调用会重置内部记账可能违反队列的 deserved 保证queue deserved guarantees。插件返回允许的任务后动作按完整性规则重建有效 bundlewhole bundle仅当其所有任务都被允许时才保留safe bundle可以收缩shrink到其被允许的子集。第二趟调度器在最终选择前重新排序重建后的 bundle 列表。第二次排序是必需的因为插件过滤可能移除或收缩 bundle从而改变其有效价值与相对优先级。增量选择与放置模拟第二趟排序后受害者 bundle 被按顺序增量选择。动作逐个添加 bundle并跟踪累计释放资源。当满足以下条件时(HyperNode 当前可用资源 累计释放资源) preemptor 作业的总资源请求动作以当前受害者集合运行放置模拟placement simulation模拟成功在该 HyperNode 内确定 preemptor 任务的放置节点然后在一个事务中执行驱逐与提名nomination返回成功模拟失败继续选择下一个 bundle 并重试所有 bundle 耗尽仍未成功当前 HyperNode 视为不可驱逐动作移到下一个 HyperNode。首轮发布Job 级受害者选择模式为了加快首轮迭代受害者选择可以运行在Job-level 模式下每个候选作业被当作单个 whole bundle复用相同的两趟排序、插件过滤、模拟与提名流程但跳过 safe/whole 拆分步骤。这降低了实现复杂度和发布风险同时保持行为确定性。也可以通过按作业配置选择退出 bundle 拆分使所选作业始终作为一个整体 bundle 被处理。后续阶段可以在核心路径稳定后默认启用完整 bundle 拆分以提升扰动效率。从源码看gangpreempt动作实现了文档中的maxDomains默认 8与allowWholeBundle默认开启两个可配置项相关常量与Action结构定义于 pkg/scheduler/actions/gangpreempt/gangpreempt.go这正对应文档中限制每个饥饿 preemptor 扫描的 HyperNode 域数量与是否允许选择 whole-bundle 受害者的延迟与扰动控制手段。为什么 Nomination 至关重要Gang 感知驱逐必须保留结果reserve outcome而不仅是腾出容量。如果动作驱逐了受害者却没有把目标任务管线化pipeline到预期节点上后续调度周期可能用无关任务消费这些节点导致 Gang 仍然被阻塞。因此设计将提名.status.nominatedNodeName视为正确性的一部分驱逐与提名一起提交这样下一个分配周期可以兑现预期放置并保持 HyperNode 连贯性。源码佐证pkg/scheduler/actions/utils/util.goL99 起注释明确gangpreempt/gangreclaim Statement has committed, and marks the jobpkg/scheduler/api/sub_job_info.goL54中的NominatedHyperNode字段注释为the hyperNode chosen by gangpreempt/gangreclaim表示提名以 HyperNode 粒度记录。allocate动作也为此提供了提名快速路径支持见 pkg/scheduler/actions/allocate/allocate.go 附近注释Honor gangpreempt/gangreclaims pin via the nomination fast path。此外pkg/scheduler/actions/utils/simulate.go 定义了ReasonGangPreempt gangpreempt与ReasonGangReclaim gangreclaim用于在模拟与事件中标识驱逐原因。评分与排序策略同族比较器、不同输入两趟排序使用同一族比较器但作用于不同输入第一趟在插件过滤前对原始 bundle 排序第二趟对插件验证后的 bundle经过 whole-bundle 丢弃与 safe-bundle 收缩排序。两趟使用相同的排序逻辑使行为可预测同时仍能适应过滤后的变化。固定优先级顺序比较器应用固定顺序safe bundle 优先于 whole bundle然后根据动作类型应用队列公平性或优先级queue-level fairness or priority剩余平局时应用效率指标efficiency metric。效率指标的直观解读是在所选 HyperNode 中每单位全局扰动能获得多少局部缓解。效率指标的计算对 preemptor 实际请求的每个资源维度如 CPU、内存、GPU调度器比较候选 bundle 的两个量Local该 bundle 在当前 HyperNode 内释放的资源——本次驱逐尝试的即时收益Global在集群范围内选择该 bundle 的总扰动成本。safe bundle 的Global通常是所驱逐任务资源之和whole bundle 的Global包含打破该受害者作业所隐含的完整 Gang 级扰动。得分分三步计算localGain对请求的各个维度累加min(Local_i, Need_i) / Need_iglobalCost对同样的请求维度累加Global_i / Need_iEfficiency localGain / globalCost。preemptor未请求的维度在基础分中被跳过这使指标保持 preemptor 中心化preemptor-centric并避免除零。伪代码SelectGangVictimsInHyperNode# Pseudo code: SelectGangVictimsInHyperNode def select_gang_victims_in_hypernode(preemptor, hypernode, candidates, ssn): bundles [] # Phase 1: build raw bundles for each candidate job. for job in candidates: local_tasks tasks_in_hypernode(job, hypernode) if not local_tasks: continue safe_bundle, whole_bundle split_safe_and_whole(job, local_tasks) if safe_bundle: bundles.append(safe_bundle) if whole_bundle: bundles.append(whole_bundle) # Phase 2: first-pass sort and one-shot plugin filtering. bundles sort_bundles(bundles, preemptor) # safe before whole, then policy order ordered_tasks flatten_tasks(bundles) allowed set(filter_eligible_tasks(ssn, preemptor.any_task(), ordered_tasks)) # Rebuild bundles with integrity rules. valid [] for b in bundles: if b.is_whole(): if all(t in allowed for t in b.tasks): valid.append(b) else: kept [t for t in b.tasks if t in allowed] if kept: b.tasks kept valid.append(b) # Phase 3: second-pass sort, then incremental select simulate. valid sort_bundles(valid, preemptor) chosen [] released zero_resource() for b in valid: chosen.append(b) released add_resource(released, b.local_resource()) if enough(add_resource(current_free(hypernode), released), preemptor.total_request()): if simulate_place(preemptor, hypernode, chosen): return chosen, True return None, False待办未请求资源的惩罚与可配置比较器未来工作包括两个后续增强除基础分中跳过未请求维度外后续扩展可为驱逐摧毁大量未请求资源的 bundle 增加显式惩罚bundle 排序可提取为插件回调使用户能配置比较器优先级例如效率是在优先级之前还是之后应用。gangPreempt 与 gangReclaim 的行为差异两个新动作共享同一核心机制但使用不同的 bundle 排序比较器维度gangPreemptgangReclaim驱动原则优先级驱动priority-driven公平性驱动fairness-driven受害者选择在相关队列上下文中选择低优先级受害者从过度使用的队列overused queues回收资源给服务不足的队列under-served queues效率指标地位次级优化器不能覆盖优先级在公平性约束满足后才使用VictimQueueOrderFn与可回收性检查优先共性共享相同的 HyperNode 与 Bundle 机制同左这种分离保持了既有调度语义的清晰同时让两个动作从相同的 HyperNode 与 bundle 机制中受益。从源码看gang插件同时注册了ReclaimableFn与PreemptableFnpkg/scheduler/plugins/gang/gang.go其回调利用job.ReadyTaskNum()与job.MinAvailable判断当作业就绪任务数大于MinAvailable时允许驱逐任务否则拒绝L109-L120。这正是 safe bundle富余任务与 whole bundle触及 MinAvailable 下限的核心任务划分在插件层的对应体现。此外该插件还注册了AddUnifiedEvictableFnL133-L137注释明确Gang-aware eviction uses the bundle model (safe/whole split) to manage MinAvailable constraints, so the plugin permits all candidates here——即 Gang 感知驱逐的 MinAvailable 约束由 bundle 模型统一管理插件层直接放行全部候选交由动作层做完整性判断。实施计划Phase 1 端到端实现核心 Gang 感知驱逐路径API 扩展更新HyperNodeGradientForJobFn与HyperNodeGradientForSubJobFn以包含SearchPurpose随后更新框架/session 的接线与调用点使 purpose 一致传播——这一部分在仓库中已经落地见 pkg/scheduler/api/types.gonetwork-topology-aware 插件使其遵循目的特定排序——PurposeAllocate保持分配导向行为PurposeEvict使用驱逐导向排序——已实现于 pkg/scheduler/plugins/network-topology-aware/network_topology_aware.go新增专用动作添加gangPreempt与gangReclaim并接入动作配置与执行——已注册于 pkg/scheduler/actions/factory.go抽取可复用放置逻辑从allocate抽取放置逻辑使 Gang 感知动作中的驱逐后模拟使用相同的放置语义——驱逐侧调用ssn.RealNodesList[hyperNode]获取域内节点进行模拟见 pkg/scheduler/actions/utils/simulate.go 与 pkg/scheduler/actions/gangpreempt/gangpreempt.goBundle 工具集添加 bundle 拆分、第一趟排序、为插件调用扁平化、过滤后收缩/重建、第二趟排序与最终选择记账等工具并更新gang插件的PreemptableFn/ReclaimableFn使 whole-bundle 驱逐在必要时可以有意打破 Gang。未来工作核心路径稳定后的未来工作聚焦优化与灵活性受害者选择模式演进初始发布默认或通过按作业选择退出保持 Job 级受害者选择一个作业 一个 whole bundle随后过渡到默认启用完整 safe/whole 拆分以获得更好的扰动效率评分模型扩展为摧毁大量未请求资源的 bundle 增加显式惩罚比较器可配置化将 bundle 比较器优先级抽取为插件回调使用户可以配置效率指标是在优先级/公平性键之前还是之后应用。小结Gang-Aware Eviction 设计通过HyperNode 梯度限定搜索范围 Bundle 模型限定受害者粒度 驱逐与提名事务化提交三管齐下解决了 Volcano 调度器中驱逐动作与拓扑约束、Gang 语义脱节的问题。gangPreempt与gangReclaim作为独立动作存在保证了增量采纳与低回归风险Safe/Whole Bundle 的两趟排序模型在及时腾出容量与控制全局扰动之间给出了明确的折中框架。对该机制感兴趣的读者可以进一步阅读 docs/design/gang-aware-eviction-design.md 原文以及仓库中 pkg/scheduler/actions/gangpreempt/gangpreempt_test.go 与 pkg/scheduler/actions/gangreclaim/gangreclaim_test.go 的测试用例结合 network-topology-aware 插件深入理解其端到端行为。【免费下载链接】volcanoA Cloud Native Batch System (Project under CNCF)项目地址: https://gitcode.com/GitHub_Trending/vol/volcano创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考