E2B Placement Best of K 优化

E2B 的 placement 策略在高并发场景下存在"状态滞后"导致的负载不均问题：调度器倾向于反复选中初始空闲的几个节点,但不会随着请求涌入及时调整,被选中的节点会承担远超平均的负载。

E2B Placement 介绍见 E2B Placement&NodeManager。本文最终落地为 PR e2b-dev/infra#2201。

一、问题:陈旧指标 + 惊群效应

1.1 线上集群的负载倾斜

为了确认问题真实存在,先在线上集群跑了 500 并发的压力测试:

real cluster

并发到来时少数节点的 sandbox 数量骤升到 100+,同时集群里大多数节点几乎为 0。这种极端不均衡和后文 benchmark 复现的现象完全吻合——不是纸面问题。

1.2 核心原因:评分依据的是"陈旧"指标

E2B 使用 Best of K 算法。placement_best_of_K.go 中 Score 函数计算节点负载分数的逻辑:

// packages/api/internal/orchestrator/placement/placement_best_of_K.go
func (b *BestOfK) Score(node *nodemanager.Node, resources nodemanager.SandboxResources, config BestOfKConfig) float64 {
	metrics := node.Metrics() // <--- 关键点:取的是节点上报的指标
	reserved := metrics.CpuAllocated

    // ... 省略 ...

	// 分数 = (请求 + 已分配 + 权重 * 当前使用率) / 总容量
	return (cpuRequested + float64(reserved) + config.Alpha*usageAvg) / totalCapacity
}

问题分析:

metrics := node.Metrics() 来自 Node 的定期上报(心跳或 gRPC 响应),是异步且滞后的数据。
高并发场景:500 个请求在极短时间内涌入时,api 并发调用 Score。Node 还来不及处理完第一个请求,更不用说更新并上报新的 CpuAllocated。
结果:这 500 个请求看到的每个 Node 的 Score 几乎一致(都基于压测开始时的旧状态)。算法虽然每次随机选 K 个节点,但分数不变时,初始状态稍好的节点会在每次比较中胜出,被反复选中。

1.3 本地"正在进行中"的状态被忽略

api 在内存里维护了正在部署的 Sandbox 信息,但这部分信息没被纳入评分。

packages/api/internal/orchestrator/placement/placement.go 的 PlaceSandbox:

func PlaceSandbox(...) {
    // 1. 选择节点 (基于旧指标)
    node, err = algorithm.chooseNode(...)

    // 2. 记录"正在部署"状态 (写进内存中的 PlacementMetrics)
    node.PlacementMetrics.StartPlacing(sbxRequest.GetSandbox().GetSandboxId(), nodemanager.SandboxResources{...})

    // 3. 发起创建请求
    err = node.SandboxCreate(ctx, sbxRequest)
    // ...
}

而 nodemanager/placement_metrics.go 中 PlacementMetrics 确实存了这些信息:

type PlacementMetrics struct {
	sandboxesInProgress *smap.Map[SandboxResources]
    // ...
}
func (p *PlacementMetrics) InProgressCount() uint32 {
	return uint32(p.sandboxesInProgress.Count())
}

设计缺陷:chooseNode → Score 流程完全跳过了 node.PlacementMetrics。把 metrics.CpuAllocated 加上 sandboxesInProgress 中的 CPU 预留量,就能在本地实时反映节点的"预期负载"。

1.4 为什么分布是 59~145,而不是全部集中在一台?

既然分数没变,为什么不是所有请求都打到分最低的那台?这是 Best of K (K=3) 的随机采样在起作用:

算法每次只从 5 台机器中随机选 3 台 (sample 函数)。
假设 Node A 是当前分数最好的,它只有在被采样进 3 个候选名单时才会被使用。
概率上 Node A 出现的概率是 $3/5 = 60%$:即使它最优,也只有 ~60% 的请求会考虑它。
次优节点 Node B 在 Node A 没被选中的 40% 情况下胜出。

所以 59~145 的分布正是"静态分数 + 随机采样"的数学体现:最空闲的机器拿到了最多流量(约 28%),较忙的机器流量较少,但这并不是基于实时负载的动态均衡。

二、优化方案

2.1 第一步:在评分中纳入 InProgress

修改 Score,把"已上报的 CpuAllocated"和"本地 InProgress 的 CPU"一起作为预期负载:

func (b *BestOfK) Score(node *nodemanager.Node, resources nodemanager.SandboxResources, config BestOfKConfig) float64 {
    metrics := node.Metrics()

    // 本地记录的、尚未上报的资源预留
    pendingCPUs := int64(0)
    for _, res := range node.PlacementMetrics.InProgress() {
        pendingCPUs += res.CPUs
    }

    // 已分配 + 正在分配
    reserved := metrics.CpuAllocated + uint32(pendingCPUs)
    // ... 后续计算保持不变
}

2.2 第二步:乐观更新(Optimistic Add / Remove)

仅靠 InProgress 还不够。完整看一下一个 Sandbox 创建请求的生命周期、以及 Score 在每个阶段看到的数据:

T0 - 开始调度:算法调用 Score。InProgress=0,Metrics=旧数据(0)。评分低 → 选中节点。
T1 - 锁定资源:调用 StartPlacing。InProgress=1,Metrics=旧数据(0)。评分变高 → 后续并发请求避开此节点。
T2 - 执行创建:调用 node.SandboxCreate(RPC),通常只需毫秒级。
T3 - 创建成功:RPC 返回,调用 node.PlacementMetrics.Success(id),该请求被从 InProgress 中移除。
T4 - 隐形阶段(The Gap):InProgress=0(已移除),Metrics=旧数据(0)(心跳还没来,假设心跳间隔 100ms)。评分错误地变低,算法又开始疯狂选中该节点。
T5 - 心跳同步:SyncMetrics 触发,Metrics 更新到新数据,评分恢复正常。

RPC ~1ms,心跳 ~100ms:每个成功的请求在 InProgress 里只停留 1ms,剩下 99ms 是"隐形窗口"——既不在 InProgress 也不在 Metrics 里,新进来的请求会再次堆积到这个节点。

解决方案:不等节点上报 Metrics,在 RPC 成功后立即在本地更新 Metrics 视图。

// 在 placement.go 的 PlaceSandbox 中:
if err == nil {
    node.PlacementMetrics.Success(sbxRequest.GetSandbox().GetSandboxId())

    // 乐观更新:假设创建成功后资源已经被占用,
    // 等下一次真实 Metrics 上报到达时,这个值会被覆盖(自动修正)。
    node.OptimisticAdd(nodemanager.SandboxResources{
        CPUs:      sbxRequest.GetSandbox().GetVcpu(),
        MiBMemory: sbxRequest.GetSandbox().GetRamMb(),
    })
}

// packages/api/internal/orchestrator/nodemanager/node.go
func (n *Node) OptimisticAdd(res SandboxResources) {
    n.metricsMu.Lock()
    defer n.metricsMu.Unlock()
    n.metrics.CpuAllocated += uint32(res.CPUs)
    n.metrics.MemoryAllocatedBytes += uint64(res.MiBMemory) * 1024 * 1024
}

2.3 容易忽略的对称问题:OptimisticRemove

PR review 阶段 maintainer 立刻指出:只 Add 不 Remove,短生命周期 sandbox 会让账本只增不减,造成新一轮的负载倾斜。

举例:某些 sandbox 创建后很快被销毁,这些已释放的资源在心跳到达前依然被记在 OptimisticAdd 的"已占用"里。调度器会误以为该节点很忙而绕开它,反而把流量集中到剩余节点。

修正方案对称地补一个 OptimisticRemove,在 delete_instance.go 的 killSandboxOnNode gRPC 删除成功后立即调用:

func (n *Node) OptimisticRemove(res SandboxResources) {
    n.metricsMu.Lock()
    defer n.metricsMu.Unlock()
    if n.metrics.CpuAllocated >= uint32(res.CPUs) {
        n.metrics.CpuAllocated -= uint32(res.CPUs)
    }
    // memory 同理
}

2.4 Feature Flag 兜底

整个乐观账本逻辑包在 feature flag sandbox-placement-optimistic-resource-accounting 后面,默认关闭。这是生产稳健性的常规做法——新逻辑出现意外时可以即时回退到原始基于 metrics 的行为,不需要重新发版。

三、未尽事宜:竞态与更彻底的方案

OptimisticAdd 不是没有代价。它和 metrics sync 之间存在一个短暂的双计数(double-count)窗口,maintainer 在 review 中也明确点出。我尝试过通过调整顺序来回避,结论是三种方案都不干净:

Add 在 RPC 之后(当前方案):一次 metrics sync 抢在 api 处理 RPC 响应之前完成时,会先更新 base metrics,紧接着 OptimisticAdd 又叠加一次 → 临时双计数。
Add 在 RPC 之前:一个在途的 stale metrics sync 在 RPC 期间到达,会把刚加的 optimistic 抹掉 → 资源短暂"消失",再次惊群。
TTL 队列:维护一个 OptimisticAllocations 队列靠 TTL 过期。但 ServiceInfoResponse 心跳只携带聚合数字,没有 SandboxID 列表,无法判断某次心跳是否已经包含这次新分配,必然存在 10–20s 的重叠窗口。

要彻底解决,需要做到 ID 级 reconciliation——api 知道每个 OptimisticAdd 对应的 Sandbox 是否已经被某次心跳"认账"。两条路线:

同步返回 Metrics:SandboxCreate RPC 响应直接带回该节点最新的 ServiceInfoResponse。简单,但要改接口、做版本兼容。
心跳带上 SandboxIDs(更推荐):在 ServiceInfoResponse protobuf 加 repeated string sandbox_ids。api 侧维护一个 Unconfirmed 集合,只在某个 ID 出现在心跳列表里时才释放对应的 optimistic 锁。不会双计数也不会少计数。

考虑到 PR 范围,本次只落地了 OptimisticAdd/Remove + feature flag 的简化版本,ID 级 reconciliation 留给后续 PR。

另外还有一种粗粒度的兜底:开启 BestOfKTooManyStartingFlag(默认关闭),限制每个节点并发启动数量,强制流量溢出到其他节点。

// packages/api/internal/orchestrator/orchestrator.go
tooManyStarting := featureFlagsClient.BoolFlag(ctx, featureflags.BestOfKTooManyStartingFlag)

它不解决滞后问题,但能给惊群效应加一个上限,可以与本次的乐观账本方案叠加使用。

四、Benchmark 验证

BenchmarkPlacementDistribution 在 10 节点集群上模拟带心跳延迟的并发流量,输出 ASCII 直方图与 CV(变异系数)。

4.1 参数选择的小坑

最初配置是 500 burst / 1s + 心跳 20s,目的是放大 thundering herd。codex bot review 时指出一个问题:1s 内根本不会发生心跳同步,benchmark 实际模拟的是"永远不上报“而不是”周期性滞后"——两者表现接近,但前者不够贴近真实场景。

最终改成 25s / 20 RPS + 心跳 20s,让心跳在 benchmark 跑到 ~20s 时真正触发一次同步,更接近线上 heartbeat 行为。

另外还修了一个 benchmark 自身的 bug:合成请求里 SandboxId 留空,导致 InProgress map 的 key 全部碰撞、pending CPU 严重低估——也就是说"看起来 InProgress 已经在抑制堆积了",但实际数据被偏好性地变好了。修复就是在合成请求里显式填上 SandboxId。

4.2 结果

关闭 feature flag(仅依赖滞后 metrics 的原始 BestOfK_K3)

CV ≈ 1.1,最忙节点 120 个 sandbox,最闲节点 2 个。

before

开启 feature flag(InProgress + OptimisticAdd/Remove)

CV ≈ 0.02,分布几乎均匀。

after

五、小结

这次优化本身的"算法变化"不大:把 InProgress 加进 score、用 OptimisticAdd/Remove 填补心跳间隙。但走完整个 PR 之后,更值得记下的是几条工程层面的取舍:

本地 shadow state 是治标,ID 级 reconciliation 才是治本。乐观账本是在工程取舍下选出的最小可用方案,而不是最干净的方案。
任何 optimistic 写都要对称:有 Add 必须有 Remove,否则只是把不均衡换了个方向。
Benchmark 参数决定它在测什么:心跳间隔大于 benchmark 时长,等于在测一个永远不上报的世界。
Feature flag 是这种带竞态风险的优化的标配,比花更多时间证明"绝对没问题"更划算。

一、问题:陈旧指标 + 惊群效应#

1.1 线上集群的负载倾斜#

1.2 核心原因:评分依据的是"陈旧"指标#

1.3 本地"正在进行中"的状态被忽略#

1.4 为什么分布是 59~145,而不是全部集中在一台?#

二、优化方案#

2.1 第一步:在评分中纳入 InProgress#

2.2 第二步:乐观更新(Optimistic Add / Remove)#

2.3 容易忽略的对称问题:OptimisticRemove#

2.4 Feature Flag 兜底#

三、未尽事宜:竞态与更彻底的方案#

四、Benchmark 验证#

4.1 参数选择的小坑#

4.2 结果#

五、小结#