“随机挑两台，选更空的一台”看起来只比随机分配多一次观察，却会显著降低最大负载。经典 Balanced Allocations 论文给出的结论更强：在明确的静态模型里，单选最大负载的量级约为 log n / log log n，固定 d>=2 次选择后降为 log log n / log d + O(1)，概率随规模增大趋近 1。

这项结论经常被压缩成“Power of Two Choices 总是更好”。本篇用独立研究项目检验这句话丢掉了哪些条件：先精确枚举小状态空间，再做固定种子的配对模拟，最后加入相关候选、整批陈旧快照和反向选择。结果同时包含支持主张的分布证据和推翻逐轨迹强断言的反例。

分布式系统（34）：复制 KV、分片迁移与故障恢复

研究问题先固定

实验只研究静态 balls-into-bins。m 个单位大小的 ball 依次到达，放入 n 个不会卸载的 bin。它可以代表一次性任务分配的抽象，却不包含服务完成、队列等待、节点权重或请求时延。

基线 one-choice 为每个 ball 均匀随机抽一个 bin。候选 two-choice 独立、有放回地抽两个 bin，读取当前负载，把 ball 立即放入较轻者；平局选第一个。两种策略复用同一条候选对序列，因此差异来自选择规则，而非换了一批随机数。

flowchart LR
  B[一个ball到达] --> R1[随机候选first]
  B --> R2[随机候选second]
  R1 --> C{比较当前负载}
  R2 --> C
  C -->|first较轻或平局| F[放入first]
  C -->|second较轻| S[放入second]

预注册有限假设 H：在 n=m=4096、200 个固定 seed 的配对试验中，fresh two-choice 的最大负载不高于 one-choice，且至少 95% 的试验严格更低。它不是论文的渐近定理；源码里的门槛只判断这组有限输入。

为什么平均值看不出差异

每种策略都放置 4096 个 ball，所有 bin 的平均负载必然是 1。只报告均值会得到“算法没有差别”的错误印象。分配是否均衡要看最大负载、bin 负载分位数、空 bin 数与标准差。

flowchart TB
  T[总ball数固定] --> M[平均负载固定为m/n]
  M --> X[不能区分均衡程度]
  X --> A[maximum]
  X --> P[p99 bin load]
  X --> E[empty bins]
  X --> D[standard deviation]

经典论文关心最大负载的高概率渐近界。有限实验报告样本统计，是为了检查趋势和实现，不用 200 次运行替代数学证明。

65,536 条小轨迹的精确结果

取 n=m=4，每个 ball 有一个有序候选对，共 4^(2*4)=65,536 条完整输入。穷举结果中，one-choice 最大负载的精确期望为 2.125，fresh two-choice 为 1.714844；完全相关的 two-choice 与 one-choice 在每条轨迹上逐字相同，反向选择的期望最大负载升到 2.558594。

分布改善不意味着逐轨迹支配。65,536 条输入中，fresh two-choice 有 24,240 条更好、41,200 条相同，还有 96 条更差。首个反例的候选对为：

1
(0,0), (0,1), (1,0), (1,1)

one-choice 始终取 first，得到 [2,2,0,0]，最大负载为 2。two-choice 逐步避开当时较重的候选，最终却得到 [1,3,0,0]，最大负载为 3。局部贪心在这条对抗性固定轨迹上更差，不与“随机输入分布下期望和高概率界更好”矛盾。

flowchart LR
  D[分布命题<br/>期望/高概率更低] --> OK[允许少量固定轨迹更差]
  P[逐轨迹支配<br/>每条输入都不差] --> BAD[被96条反例否定]

200 个配对 seed 的结果

默认规模为 4096 个 bin 和 4096 个 ball，seed 从 20260927 连续取 200 个。每个 seed 生成一条候选对序列，五种策略都在这条序列上运行。

策略 最大负载均值 最大负载中位数 最大负载p95 解释
one-choice 6.275 6 8 单次随机基线
fresh two-choice 3.030 3 3 当前负载、独立候选
correlated-two 6.275 6 8 两次都观察first
stale-two 6.275 6 8 整批只看初始快照
anti-two 8.270 8 10 故意选较重者

fresh two-choice 在 200 次中全部严格低于 one-choice，最大负载差的中位数为 3，有限假设 H 通过。它的 p99 bin load 中位数为 2，one-choice 为 4；标准差均值分别约 0.703 和 0.999。这里的 p99 指“bin 负载的第 99 百分位”，不是请求延迟。

选择次数不是独立信息的替代品

correlated-two 把第二候选强制设为第一候选。代码仍执行“两次观察”的接口，但有效信息只有一个 bin，精确枚举与 200 次模拟都与 one-choice 完全相同。

flowchart TD
  Q[两次采样] --> I{候选独立?}
  I -->|是| L{负载信息新鲜?}
  I -->|否| O[退化为一次选择]
  L -->|是| F[fresh P2C]
  L -->|否| S[可能退化或形成herd]
  F --> C{比较方向正确?}
  C -->|选轻者| G[分布更集中]
  C -->|选重者| H[放大热点]

独立均匀采样也是负载分散的前提。机架亲和、缓存命中、热点键或路由规则可能让两个候选高度相关；此时增加一次探测不等于增加一次独立机会。

陈旧负载把 two-choice 退化为 one-choice

stale-two 每隔固定数量的 ball 才刷新一次可见负载。默认刷新间隔等于整个批次 4096，因此所有决策都看到全零快照；平局规则始终选择 first。结果在每个 seed 上与 one-choice 完全相同。

这不是“旧信息永远无用”的证明。Mitzenmacher 对 old information 的分析说明，信息价值取决于刷新模型与批量大小。本地反例只说明：同步批次共享一份完全陈旧的快照时，fresh two-choice 的结论不能原样套用。真实系统还可能通过随机打破平局、缩短刷新间隔、late binding 或服务器端反馈减弱 herd。

第一次运行曾把刷新间隔设为 64，并预期多数试验会比 fresh two-choice 更差。实际只有 14/200 个试验的最大负载更高，中位差为 0，预注册门槛失败。这个 pilot 不能支持“轻度陈旧必然明显恶化”；失败日志保留在仓库内 .build/research35/，正式端点实验只回答整批不刷新时是否精确退化。

反向选择验证判定器不是装饰

anti-two 使用相同候选和实时负载，却故意把 ball 放入较重者。200 次中有 194 次最大负载高于 one-choice，中位差为 2。比较方向确实参与了结果；“多看一个候选”本身没有保证。

这个负例也检查实验是否只会打印成功。如果实现意外忽略负载比较，fresh、correlated、stale 和 anti 四种策略会趋同，预注册门槛或反例断言就会失败。

正确性与故障模型

静态分配器的安全性很窄：每个 ball 恰好放入一个合法 bin，最终负载总和等于 ball 数，没有负数。活性同样是构造性的，每个输入在一次策略调用内完成，不等待消息或多数派。

网络超时、节点崩溃、请求重试和任务执行失败都不在模型中。若一次分配响应丢失，重试可能重复放置；若节点在选择后失效，任务需要重新调度；若观测延迟，fresh 假设被破坏。这些问题需要请求身份、租约或调度协议，不能由 P2C 的负载界自动解决。

实验命令

1
2
3
4
5
mkdir -p examples/distributed-systems/.build/research35/tmp
export TMPDIR="$PWD/examples/distributed-systems/.build/research35/tmp"
export TMP="$TMPDIR" TEMP="$TMPDIR" PYTHONDONTWRITEBYTECODE=1
python3 -B examples/distributed-systems/research35/check.py \
  --output examples/distributed-systems/.build/research35/observations-final.json

Python 3.12.3 正式运行退出 0；--help 退出 0，--trials 0 退出 2。另用 n=m=2、单次试验触发预注册门槛失败，程序先写出完整结构化结果再退出 1，没有用 traceback 代替失败报告。每个正式 trial 都保留 seed、五种策略的最大负载和三个配对差值，便于复算 200/200。源码 SHA-256 见随文证据。完整结果见观察结果，来源和运行记录见实验证据，验证范围见验证说明。

从定理到工程系统

NGINX 的 random two least_conn 明确了两个工程参数：候选如何随机取，比较量是连接数还是权重。Sparrow 把小规模随机探测用于分布式调度，还需要 late binding 和批任务处理。产品名字里出现“two choices”并不表示它自动继承静态 balls-into-bins 的全部结论。

模型差异 可能改变什么 需要额外验证
ball 有不同工作量 计数相同但剩余工作不同 加权负载或剩余服务时间
bin 会完成任务 occupancy 变成动态队列 到达率、服务分布、稳定性
负载信息有延迟 多个分配器看到旧状态 刷新间隔、批量并发、tie-break
候选不独立 第二次采样信息减少 拓扑、亲和规则、热点分布
节点会失败 已选目标可能不可用 重试身份、重调度与容量余量
探测跨网络 两次观察产生额外成本 探测流量、超时和缓存一致性

标准库模型没有吞吐、p99 请求延迟、调度公平性或网络成本数据，也没有验证 NGINX、Sparrow 或云调度器。它只给静态占用分布与几种明确反例。

两个推演练习

为什么允许两个候选相同不会破坏经典模型？

独立均匀、有放回抽样本来就允许重复，概率为 1/n。重复时该 ball 退化为单选，但随 n 增大只占小部分。若实现要求两个候选必异，模型变成无放回抽样，需要在代码与结论中明确。

为什么 96 条更差轨迹不能否定论文主定理？

论文比较的是随机输入分布下的高概率最大负载界，不是对每条候选序列的点态不等式。有限穷举显示 two-choice 的精确期望更低，同时给出少量更差轨迹；两项观察可以同时成立。

结课结论

独立研究项目不应只寻找支持主张的图。问题先限定为静态模型，判定门槛在运行前固定，基线与候选复用随机输入，精确枚举保留反例，模拟结果与论文定理分开陈述。这样的报告可以复跑，也能说明结论在哪些条件下停止成立。

主线到这里结束。选修篇从 CRDT 与多主写入开始，讨论不依赖单一 leader 时，合并规则如何代替全局顺序。

参考资料