本文是《从 IP 到 SRv6 计算编排》新手教材第 9/13 编。 总目录 · 上一篇：第八编：链路变差时的三级自主降档 · 下一篇：第十编：业务、故障、前端和证据
57. 编排问题到底在求什么
一条业务声明“先Gray，再Edge”，系统仍不知道应该选择哪个Gray实例和哪个Edge实例。 不同选择会带来不同的：
- 网络传播与传输代价；
- 实例计算时间；
- 排队和资源竞争；
- 故障风险；
- 最终完成时间。
**Orchestration（编排）**就是把抽象计算步骤映射到具体可运行资源，并产生可执行路径。 本项目的Exact模式使用HEFT做这件事。
58. 异构是什么意思
**Heterogeneous（异构）**表示资源并不完全相同：
- 节点CPU逻辑核数不同；
- 当前CPU busy程度不同；
- 可用内存不同；
- 算子清单不同；
- 节点间跳数、带宽和可达性不同；
- 实例lifetime和故障状态不同。
如果所有节点和链路完全相同，随机挑选也可能表现相近；在异构环境里，放置选择才成为真正 的优化问题。
59. DAG的数学表示
设DAG为：
G = (V, E)
V是stage集合，每个stage是一项计算；E是依赖边集合，边(i,j)表示j必须等待i的输出；pred(i)是i的直接前驱集合；succ(i)是i的直接后继集合。
对每个stage i：
P_i是能执行它的候选processor集合；w(i,p)是i放在候选p上的计算代价；c(i,j,p,q)是i在p、j在q时传输依赖数据的代价。
HEFT论文把执行资源称为Processor（处理器）。在本项目中，实际调度资源是“某物理 节点上的某个具体算子实例”；同一物理节点上的任务还共享节点可用时间轴。
60. HEFT全称和基本思想
**HEFT（Heterogeneous Earliest Finish Time，异构最早完成时间）**是Topcuoglu、 Hariri和Wu提出的列表调度算法。它分两大阶段：
- Task Prioritizing Phase（任务优先级阶段）：用upward rank给DAG节点排序；
- Processor Selection Phase（处理器选择阶段）：按顺序把任务放到能最早完成的资源。
**Heuristic（启发式）**表示它用有效规则寻找优良解，但不保证对所有NP-hard调度实例都 得到数学全局最优解。HEFT的优势是计算快、解释清楚，适合在线重算。
61. HEFT第一阶段：平均代价
61.1 平均计算代价
stage i的平均计算代价是它在全部可用候选上的计算时间平均：
1
w_bar(i) = ----------- × Σ w(i,p)
|P_i| p∈P_i
Σ读作“求和”，|P_i|表示候选数量。
61.2 平均通信代价
依赖边(i,j)的平均通信代价，是所有可行候选组合上的通信时间平均：
c_bar(i,j) = average of c(i,j,p,q)
over viable p ∈ P_i and q ∈ P_j
若两个stage落在同一物理节点，具体实现可把网络通信视为本地代价；若跨节点，则根据数据量、 路径代价和链路速率估算。
平均值只用于计算优先级。真正放置某stage时，必须使用被选候选间的具体代价，不能继续用 平均值代替。
62. HEFT第一阶段：Upward Rank
**Upward Rank（向上排序值）**从DAG出口反向计算，估计“从当前stage开始直到任务结束”的 平均剩余关键路径长度。
对于一般stage：
rank_u(i) = w_bar(i)
+ max [ c_bar(i,j) + rank_u(j) ]
j∈succ(i)
若i没有后继，通常：
rank_u(i) = w_bar(i)
本项目还显式估算最后算子到目的端sink的通信时间，所以出口stage的rank包含平均sink代价。
max的含义是：多个分支里，最长的平均剩余路径决定关键程度。rank越高，越应优先调度。
HEFT随后按rank_u降序生成list（列表）。DAG依赖保证后继不会在前驱结果尚不存在时实际
开始。当前内置业务DAG是固定线性链，声明依赖顺序与rank优先顺序等价；代码仍计算并输出
rank，作为代价证据和未来支持分支DAG的基础。
63. HEFT第二阶段：EST与EFT
63.1 Processor Available Time
**Processor Available Time（处理器可用时间）**是候选物理节点完成此前已放置stage后，最早 何时还能接新工作。记为：
available(p)
本项目在物理节点层维护这条时间线，避免误以为同节点多个算子可以无限并行而没有CPU竞争。
63.2 Dependency Ready Time
对stage i的候选p，每个前驱j必须先计算完成，再把输出传到p：
ready(i,p) = max [ finish(j) + c(j,i,place(j),p) ]
j∈pred(i)
若i是第一个stage，ready time来自入口把输入送到候选p的通信代价。
63.3 Earliest Start Time
**EST（Earliest Start Time，最早开始时间）**是资源可用与依赖到达两者中较晚的一个：
EST(i,p) = max(available(p), ready(i,p))
63.4 Earliest Finish Time
**EFT（Earliest Finish Time，最早完成时间）**为：
EFT(i,p) = EST(i,p) + w(i,p)
算法为stage枚举所有候选，选择EFT最小者。最后一个stage选择时还把它到sink的通信代价 纳入比较，防止选中“算得很快却离目的端很远”的实例。
64. 本项目怎样估算计算时间
task DAG为每个stage声明cpu_cost_units。节点资源报告提供：
cpu_logical：逻辑CPU数量；busy_milli：繁忙比例的千分数，0表示完全空闲，1000表示没有剩余能力。
当前估算为：
compute_us = ceil(
cpu_cost_units × 1,000,000,000
÷ [cpu_logical × (1000 - busy_milli)]
)
ceil表示向上取整，us表示microsecond（微秒，百万分之一秒）。busy越高，分母越小，
估计时间越长；逻辑CPU越多，估计时间越短。
这是调度成本模型，不是物理CPU周期的完美预测。真正运行时间仍由事件时间戳观测，不能把 模型预测当成已经发生的事实。
65. 本项目怎样估算通信时间
stage输出声明data_bytes。路径提供cost_milli，链路提供link_rate_bps：
comm_us = ceil(
data_bytes × 8 × cost_milli × 1,000,000
÷ [1000 × link_rate_bps]
)
data_bytes × 8把byte换成bit；bps是bits per second，每秒bit数；cost_milli/1000表示路径成本倍数；- 默认未知速率按1 Mbit/s处理，而不是假设无限快。
当前控制面物理路径成本仍是：
cost_milli = hop_count × 1000
因此当前HEFT通信估算主要体现跳数、数据量和速率；它不能被描述为已经读取每条真实动态 传播时延的“latency-aware（时延感知）”优化。AF_XDP数据面仍独立应用真实配置的rate、 queue和delay。
66. 候选过滤先于优化
HEFT只能在真实可运行候选上优化。一个实例成为候选，至少要满足：
- 资源报告未过lifetime；
- 实例清单包含所需operator type；
- CPU剩余能力足够，
busy_milli < 1000； - 可用内存达到stage要求；
- 入口到实例、stage之间以及最终到sink存在可接受路径；
- 不在本次backup计算的excluded SID集合中；
- 不依赖已被排除的链路或失效节点。
这一步叫Feasibility Filtering（可行性过滤）。没有候选时返回no solution（无解）是正常 算法结果，不是HEFT程序崩溃，也不应该伪造一个实例继续。
代码还对线性DAG进行forward/backward viability（前向/后向可行性）过滤：只有既能由入口 到达、又能经余下stage到sink的候选才保留。这样避免先选中一个局部很快、后面却无路可走 的死端。
67. 一次完整手算
考虑线性DAG：
source@1 → Gray → Edge → sink@10
为方便手算，假设每段数据都是100 byte，链路速率1 Mbit/s。每跨一个hop的传输时间是：
100 × 8 ÷ 1,000,000 second = 800 us
候选与计算时间：
| Stage | 候选 | 计算时间 |
|---|---|---|
| Gray | G2 | 300 us |
| Gray | G5 | 500 us |
| Edge | E6 | 450 us |
| Edge | E8 | 250 us |
跳数矩阵：
| 方向 | hop | 通信时间 |
|---|---|---|
| source1 → G2 | 1 | 800 us |
| source1 → G5 | 2 | 1600 us |
| G2 → E6 | 2 | 1600 us |
| G2 → E8 | 3 | 2400 us |
| G5 → E6 | 1 | 800 us |
| G5 → E8 | 1 | 800 us |
| E6 → sink10 | 1 | 800 us |
| E8 → sink10 | 1 | 800 us |
67.1 算平均代价
Gray平均计算：
w_bar(Gray) = (300 + 500) / 2 = 400 us
Edge平均计算：
w_bar(Edge) = (450 + 250) / 2 = 350 us
Gray到Edge四种组合的平均通信：
c_bar(Gray,Edge)
= (1600 + 2400 + 800 + 800) / 4
= 1400 us
Edge到sink平均为800 us。
67.2 算upward rank
出口Edge：
rank_u(Edge) = 350 + 800 = 1150 us
Gray：
rank_u(Gray) = 400 + 1400 + 1150 = 2950 us
因此先放置Gray，再放置Edge，恰好也符合线性依赖顺序。
67.3 放置Gray
假设两个候选起始都空闲：
G2: EST = 800, EFT = 800 + 300 = 1100 us
G5: EST = 1600, EFT = 1600 + 500 = 2100 us
选择G2，Gray预计在1100 us完成。
67.4 放置Edge
选择E6：
dependency ready = 1100 + 1600 = 2700 us
EST(E6) = 2700 us
EFT(E6) = 2700 + 450 = 3150 us
加sink通信 = 3150 + 800 = 3950 us
选择E8：
dependency ready = 1100 + 2400 = 3500 us
EST(E8) = 3500 us
EFT(E8) = 3500 + 250 = 3750 us
加sink通信 = 3750 + 800 = 4550 us
虽然E8自己计算更快，完整完成时间却更晚，所以选择E6。最终放置为：
Gray@node-2 → Edge@node-6
predicted makespan = 3950 us
**Makespan（总完工时间）**是从任务开始到全部stage及最终交付完成的预计时间。
这个例子说明HEFT不是“永远选CPU最快的节点”，而是联合考虑入口、计算、stage间通信和 目的端交付。
68. 从HEFT结果到SR Policy
HEFT输出的是placement：
Gray → concrete Gray SID at node-2
Edge → concrete Edge SID at node-6
策略构造器再把物理路径和具体算子SID拼成segment list。例如概念上：
入口到node-2物理uSID
→ fd42:3:2::100
→ node-2到node-6物理uSID
→ fd42:3:6::200
→ node-6到目的端物理uSID
→ endpoint delivery SID
入口节点给task分配Color，安装这条SR Policy，成功后才发READY。HEFT本身不操作内核， 控制器也不替节点安装策略；它们之间通过清楚的接口分工。
69. Primary与Backup
**Primary（主策略）**是正常使用的HEFT结果。为了得到有结构差异的backup（备策略），系统：
- 先算primary；
- 从备份拓扑中移除primary第一条物理边；
- 排除primary已经选择的具体算子SID；
- 在剩余候选和路径上重新运行完整HEFT。
这样backup不是把primary名字改成“backup”，而是在入口分离和算子实例上都尽量独立。
若剩余图没有完整可行链，backup可以无解。系统应记录该事实，不能凭空捏造一条路径。任务 是否允许只有primary，由任务契约决定。
70. 动态重算
拓扑、资源、实例或endpoint事实发生变化时，入口本地planner检查现有Exact placement是否 仍可用。若相关路径或实例失效，则在一份immutable snapshot（不可变快照）上重跑HEFT。
不可变的含义是：一次计算从头到尾看到同一版本输入；更新到达时生成下一快照，而不是在 算法遍历一半时修改图。这样才能复现“这次决策为什么选了它”。
重算成功后，入口保持task_id、Color、目的端和placement mode不变，用route replace原子 替换内核策略。业务发生器不会由控制器重启，也不需要人为等待一个全局barrier。
71. HEFT耗时应该怎样记
必须把不同阶段分开：
故障真实发生
↓
节点发现/本地链路状态变化
↓
事实上报和控制面传播
↓
本地快照可用
↓
HEFT算法计算
↓
策略序列化和内核安装
↓
首个恢复业务包到达
decision_ns只应围绕HEFT算法计算本身。ns是nanosecond（纳秒，十亿分之一秒）。故障
发现、网络传播、消息排队、内核安装和首包恢复各有自己的时间戳。
若把整个闭环都记成“HEFT时间”，就无法判断超过100 ms是算法慢、CPU调度竞争、控制面 积压，还是内核安装慢。超过某个观察阈值本身不是程序错误；应如实记录分布与分阶段证据。
72. CPU调度竞争会怎样影响观测
在300节点环境中，许多容器、线程、AF_XDP轮询和分析进程共享宿主CPU。操作系统scheduler （调度器）可能让HEFT线程暂时得不到运行时间。墙钟耗时因此包括：
实际CPU执行时间 + 等待被调度时间 + 锁/队列等待时间
判断CPU竞争不能只看“某次decision超过100 ms”。至少要对比：
- 线程CPU time与wall-clock time；
- run queue长度和CPU utilization（利用率）；
- 同时发生的快照、日志和容器活动；
- 算法输入规模，如候选数、边数和DAG长度；
- install阶段与decision阶段的独立耗时。
先分层观测，才能决定优化算法、减少无效快照、调整进程资源，还是根本无需修改。
73. HEFT无解为什么正常
以下情况都可能产生无解：
- DAG需要的某类算子当前没有存活实例；
- 实例存在但资源报告已过期；
- 入口到stage或最后stage到sink不可达；
- 10%节点损毁切断了所有满足约束的链；
- primary有解，但施加独立性约束后backup无解；
- 内存或CPU下限没有任何候选满足。
正确行为是返回结构化REJECTED或重算失败事件，保留原因和输入版本。不能“短路HEFT后算 成功”，不能恢复控制器替端点制造业务，也不能延长超时掩盖不可行性。
74. 回看第六编：Resilient为什么不是HEFT
Resilient DAG只声明逻辑Anycast operator SID。每个节点的FIB根据当前路径选择provider：
logical Gray → nearest/reachable Gray provider
logical Edge → nearest/reachable Edge provider
实例变化时，局部FIB更新，task SRH不变。这是routing-based placement（基于路由的放置）， 不是HEFT。
两种模式各自回答不同问题：
| 维度 | Exact | Resilient |
|---|---|---|
| 算子地址 | 具体实例SID | 逻辑Anycast SID |
| 实例选择 | HEFT全链联合选择 | 每个服务逐跳路由选择 |
| 状态变化 | 相关失效时重跑HEFT | 更新逻辑服务FIB |
| task SRH | 可能被原子替换 | 保持稳定 |
| 有状态漂移 | 固定实例期间较稳定 | provider漂移可拆散窗口 |
不能因为Resilient“也选择了一个provider”，就把它称为HEFT结果。
75. HEFT伪代码
下面是帮助理解的简化伪代码，不替代仓库实现：
function HEFT(dag, facts, ingress, sink, exclusions):
candidates = filter_instances(dag, facts, exclusions)
candidates = forward_backward_viability(candidates, ingress, sink)
if any stage has no candidate:
return NO_SOLUTION
compute w_bar for every stage
compute c_bar for every dependency
compute rank_u from exits back to entries
order = stages sorted by descending rank_u
available_time[node] = 0
placement = empty
for stage in order:
best = none
for instance in candidates[stage]:
ready = dependency_ready(stage, instance, placement)
est = max(available_time[instance.node], ready)
eft = est + compute_cost(stage, instance)
score = eft
if stage is an exit:
score += communication_to_sink(instance, sink)
choose the lowest score with deterministic tie-break
if best is none:
return NO_SOLUTION
placement[stage] = best
available_time[best.node] = best.eft
return placement, ranks, costs, predicted_makespan
**Tie-break（平局裁决）**必须确定性：代价相等时按稳定字段排序，而不能依赖哈希表随机遍历 顺序，否则相同输入无法复现相同placement。
76. 第九编自测
- HEFT两个阶段分别做什么？
- upward rank为什么从出口反向计算？
- EST为什么是resource available与dependency ready的最大值？
- 手算例子中E8计算更快，为什么最终选择E6？
- 候选过滤与优化选择有什么区别？
- primary有解而backup无解，是否说明HEFT崩溃？
decision_ns为什么不能包含故障发现和内核安装？- Resilient的provider选择为什么不叫HEFT？