企业官网建设流程全解析

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 型作业而言，这种驱逐既昂贵又不可预测。

问题的两分法

设计文档将问题拆解为两个子问题，并分别给出答案：

1. 调度器应该在哪里搜索分配与驱逐？——答案来自HyperNode 梯度（HyperNode gradients）；
2. 调度器应该驱逐谁？——答案来自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 升序组织结果。值得注意的细节是isEligibleHyperNode（L649-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.go；gangpreempt与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 作用域（而非任务作用域）上评估。每个候选作业的任务被划分为两类 bundle：

• Safe bundle（安全包）：包含富余任务（surplus tasks），或来自已低于其有效可用性目标（effective availability target）的 Gang 的任务；
• Whole bundle（整体包）：包含核心任务（core tasks），驱逐它们意味着打破该 Gang。

注意：候选作业中的每个任务要么属于其 safe bundle，要么属于其 whole bundle。这个划分赋予了动作一个显式的扰动模型：safe bundle 是低成本机会，whole bundle 是高成本决策，只有在 safe 机会不足时才被考虑。

两趟排序与一次性插件过滤

每个 HyperNode 的 Bundle 排序分两趟进行：

第一趟：调度器对所有原始（raw）bundle 排序，然后将其扁平化为有序任务切片，交给插件过滤。插件（Reclaimable/Preemptable）对每个 HyperNode 恰好调用一次（one-shot call），传入该有序切片。这一点对capacity这类有状态插件至关重要：重复的按 Job 调用会重置内部记账，可能违反队列的 deserved 保证（queue deserved guarantees）。

插件返回允许的任务后，动作按完整性规则重建有效 bundle：

• whole 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.go（L99 起）注释明确gangpreempt/gangreclaim Statement has committed, and marks the job；pkg/scheduler/api/sub_job_info.go（L54）中的NominatedHyperNode字段注释为the hyperNode chosen by gangpreempt/gangreclaim，表示提名以 HyperNode 粒度记录。allocate动作也为此提供了提名快速路径支持（见 pkg/scheduler/actions/allocate/allocate.go 附近注释：Honor gangpreempt/gangreclaim's pin via the nomination fast path）。此外，pkg/scheduler/actions/utils/simulate.go 定义了ReasonGangPreempt = "gangpreempt"与ReasonGangReclaim = "gangreclaim"，用于在模拟与事件中标识驱逐原因。

评分与排序策略

同族比较器、不同输入

两趟排序使用同一族比较器，但作用于不同输入：

• 第一趟：在插件过滤前对原始 bundle 排序；
• 第二趟：对插件验证后的 bundle（经过 whole-bundle 丢弃与 safe-bundle 收缩）排序。

两趟使用相同的排序逻辑，使行为可预测，同时仍能适应过滤后的变化。

固定优先级顺序

比较器应用固定顺序：

1. safe bundle 优先于 whole bundle；
2. 然后根据动作类型应用队列公平性或优先级（queue-level fairness or priority）；
3. 剩余平局时应用效率指标（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_i；
• globalCost：对同样的请求维度累加Global_i / Need_i；
• Efficiency = 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

待办：未请求资源的惩罚与可配置比较器

未来工作包括两个后续增强：

1. 除基础分中跳过未请求维度外，后续扩展可为"驱逐摧毁大量未请求资源"的 bundle 增加显式惩罚；
2. bundle 排序可提取为插件回调，使用户能配置比较器优先级，例如效率是在优先级之前还是之后应用。

gangPreempt 与 gangReclaim 的行为差异

两个新动作共享同一核心机制，但使用不同的 bundle 排序比较器：

这种分离保持了既有调度语义的清晰，同时让两个动作从相同的 HyperNode 与 bundle 机制中受益。从源码看，gang插件同时注册了ReclaimableFn与PreemptableFn（pkg/scheduler/plugins/gang/gang.go），其回调利用job.ReadyTaskNum()与job.MinAvailable判断：当作业就绪任务数大于MinAvailable时允许驱逐任务，否则拒绝（L109-L120）。这正是 safe bundle（富余任务）与 whole bundle（触及 MinAvailable 下限的核心任务）划分在插件层的对应体现。此外，该插件还注册了AddUnifiedEvictableFn（L133-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 感知驱逐路径：

1. API 扩展：更新HyperNodeGradientForJobFn与HyperNodeGradientForSubJobFn以包含SearchPurpose，随后更新框架/session 的接线与调用点，使 purpose 一致传播——这一部分在仓库中已经落地（见 pkg/scheduler/api/types.go）；
2. network-topology-aware 插件：使其遵循目的特定排序——PurposeAllocate保持分配导向行为，PurposeEvict使用驱逐导向排序——已实现于 pkg/scheduler/plugins/network-topology-aware/network_topology_aware.go；
3. 新增专用动作：添加gangPreempt与gangReclaim并接入动作配置与执行——已注册于 pkg/scheduler/actions/factory.go；
4. 抽取可复用放置逻辑：从allocate抽取放置逻辑，使 Gang 感知动作中的驱逐后模拟使用相同的放置语义——驱逐侧调用ssn.RealNodesList[hyperNode]获取域内节点进行模拟（见 pkg/scheduler/actions/utils/simulate.go 与 pkg/scheduler/actions/gangpreempt/gangpreempt.go）；
5. Bundle 工具集：添加 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