第6章：Owner 规划与亲和路由

第 5 章把访问图和 cohort 学习讲完了——但是 cohort 集合只是输入，谁来决定每个 cohort 归哪个 CN 持有？事务又怎么按这个决策路由？ 这就是论文 §3.5–3.7 的两个组件：OwnershipPlanner（决定 cohort → owner CN 映射）和 AffinityRouter（决定 txn → home CN 路由）。本章按论文 §3.5（Benefit 目标函数）→ §3.6（可实现的 greedy 规划器）→ §3.7（AffinityRouter 公式）三段顺序展开，把 Benefit 四项的物理含义 + greedy 算法的容量约束 + AffinityRouter Score 函数 + Lever B 双层路由（OwnerOfKeyGroup → RouteByWarehouse fallback）一次性讲透。读完你能徒手讲完 “cohort 怎么归人、事务怎么找到家”的完整决策链。

📑 目录

• 1. §3.5 Ownership Planner Benefit 模型
• 2. Benefit 四项的物理推导
• 3. §3.6 可实现的 greedy 规划器
• 4. §3.7 AffinityRouter：从写集合到 home CN
• 5. 双层路由：OwnerOfKeyGroup + RouteByWarehouse fallback (Lever B)
• 6. 一张图把 §3.5–3.7 串起来

---

1. §3.5 Ownership Planner Benefit 模型

1.1 论文公式

$$\text{Benefit}(c, i) = S_{\text{atomic}}(c, i) - C_{\text{rpc}}(c, i) - C_{\text{move}}(c, i) - C_{\text{load}}(i)$$

其中：

• $c$ = 候选 cohort
• $i$ = 候选 owner CN

🌟 直觉理解：把 cohort $c$ 交给 CN $i$ 当 owner，净收益 = 省下的 MN atomic − 跨 CN RPC 代价 − 迁移代价 − owner 负载惩罚。

1.2 它在解决什么

Planner 的目标：找一组 (cohort, owner) 映射，最大化集群总 atomic 节省，同时保证 owner CN 不过载。

🧠 关键洞察：这是一个带容量约束的 assignment 问题——naive 解是匹配最大流，AURA 第一版用 greedy（论文 §3.6）。

---

2. Benefit 四项的物理推导

每一项的物理含义都来自第 5 章访问图的统计量。这是论文 §3.5 的核心——把”算法目标”翻译成”工程可估算的量”。

2.1 S_atomic(c, i)：把 c 交给 i 能省多少 atomic

   S_atomic(c, i) = Σ_{v ∈ c} W(v) × P(home_CN(v) = i)
                    ↑       ↑       ↑
                    │       │       └── 路由到 i 的概率（依赖 AffinityRouter）
                    │       └── v 的写频率（来自 AccessGraphProfiler）
                    └── 求和所有 c 内的 key group

• $W(v)$ —— EWMA 维护的写频率
• $P(\text{home\_CN}(v) = i)$ —— 包含 $v$ 的事务被路由到 CN $i$ 的概率

🌟 物理含义：如果 c 内的 key group 经常被 CN $i$ 上发起的事务访问，把 c 交给 $i$ 就能把这些 atomic 转成本地 lock_cmpxchg。

🧠 关键洞察：$P(\text{home\_CN}(v) = i)$ 是 AffinityRouter 的输出——所以 OwnershipPlanner 和 AffinityRouter 是互相依赖的环。AURA 用迭代法（每 tick 都更新）解这个环。

2.2 C_rpc(c, i)：把 c 交给 i 后，别的 CN 来访问 c 的代价

   C_rpc(c, i) = Σ_{v ∈ c} W(v) × (1 - P(home_CN(v) = i)) × C_RPC_one_shot

• $C_{\text{RPC\_one\_shot}}$ —— 一次 OwnerRpc 慢路径调用的成本（典型 5–10 μs）

🌟 物理含义：c 内 key group 被其他 CN 访问的频率 × 一次 OwnerRpc 代价。比 fallback to MN 贵（因为 MN atomic 只走单边 RDMA），但避免了 atomic 物理墙。

🧠 关键洞察：S_atomic 和 C_rpc 是同一个 cohort 的两面——访问被 i 命中就转成 S_atomic（正收益），访问没被 i 命中就转成 C_rpc（负代价）。所以 Planner 选 owner 的本质是让”被命中的事务比例最大化”。

2.3 C_move(c, i)：迁移代价

   C_move(c, i) = (current_owner(c) != i) ? C_freeze + C_drain + C_handoff : 0

• $C_{\text{freeze}}$ —— 冻结 cohort 不接受新 token 的时间窗（< 1 ms）
• $C_{\text{drain}}$ —— 等旧 token 释放的时间（取决于事务最长执行时间，典型 ~10 ms）
• $C_{\text{handoff}}$ —— 把 cohort 状态送到新 owner（cohort 状态几十字节，~10 μs RDMA）

🌟 物理含义：迁移本身有代价——如果当前 owner 还合适，别为了 marginal benefit 而搬。

🧠 关键洞察：C_move 是 AURA 防抖动的关键——没有它 Planner 会每 tick 都换 owner。第 7 章会展开 4 阶段时序的总耗时。

2.4 C_load(i)：负载惩罚

   C_load(i) = max(0, current_load(i) - capacity(i))² × C_load_unit

• $\text{current\_load}(i)$ —— CN $i$ 当前已接的 cohort 总 atomic 压力
• $\text{capacity}(i)$ —— CN $i$ 的负载预算（典型 = 集群总负载 / N_CN）

🌟 物理含义：防止把所有热 cohort 堆到同一个 CN——平方惩罚让超额越多代价越高。

🧠 关键洞察：没有 C_load 的话，Planner 会贪心地把热 cohort 全堆到访问频率最高的那个 CN——结果是一个 CN 100% CPU，其他 CN 闲置。C_load 强制 Planner 均衡 owner 分布。

2.5 四项一起看：典型场景

场景	S_atomic	C_rpc	C_move	C_load	决策
热 cohort 被 CN 1 90% 命中	高	低	0（已是 owner）	低	保持
热 cohort 被 CN 1 50%、CN 2 50% 命中	中	中	0–高	中	可能换或保持
漂移：原 owner CN 1，现在 CN 3 80% 命中	（新 owner）高	低	高	低	是否搬看 S_atomic - C_move
CN 1 已经过载	高	低	0	极高	被惩罚强制不能再加

🌟 结论：Benefit 四项的物理含义就是 AURA Planner 的”思考模型”——理解这四项，就理解了 Planner 在做什么权衡。

---

3. §3.6 可实现的 greedy 规划器

3.1 算法伪代码（论文 Table 4）

1. 从最近窗口统计 W(c), C(c,c'), 本地命中, owner RPC, fallback CAS, 队列长度
2. 选满足 W(c) > θ_w 或 fallback CAS 占比 > θ_f 的 cohort 形成 H
3. 按 W(c) × atomic_cost 从高到低遍历 c ∈ H
4. 对每个候选 CN i，估计 Benefit(c, i)
5. 若最佳 Benefit > θ_b 且 Load(i) + Load(c) < B_i，把 owner(c) = i
6. 若当前 owner 与目标 owner 不同，且距离上次迁移超过冷却窗口，生成 transfer 计划
7. 对长期 < θ_cold 的 cohort 生成 evict 计划，回到 fallback

3.2 复杂度分析

   |H| × N_CN
   ──────────
   |H| = 候选热 cohort 数（典型 ~1024）
   N_CN = CN 数（典型 4–8）
   总：~4K–8K 次 Benefit 计算 / tick

🌟 结论：O(|H| × N_CN) ~= O(N_cohort × N_CN) —— 4–8K 次乘加，5 ms 内能跑完。可作为 100 ms tick 的低开销控制环。

3.3 为什么是 greedy 不是图划分

方案	复杂度	收益	AURA 第一版选哪个
Greedy（按 atomic 压力降序）	O(	H	× N_CN)
带容量约束的图划分（min-cut）	O(N² log N)	全局最优	❌ 太贵
整数规划（ILP）	指数	最优	❌ 跑不动
学习型 cost model（MorphoSys 风格）	训练 + O(	H	)

🌟 结论：Greedy 已经能拿到 70–80% 全局最优收益——AURA 的核心收益不在 planner 优化得多狠，而在让锁权威能动起来。第一版做 greedy 完全够。

🧠 关键洞察：好系统不需要好算法，需要正确的抽象。AURA 的核心抽象（cohort + ownership + epoch）让 greedy 都能拿好处；如果抽象不对，再好的算法也救不了。

3.4 ArgmaxOwner：v25 工程实现

v25 工程实现的 router-side ArgmaxOwner（简化版）：

cn_id_t ArgmaxOwner(const Cohort& c, const std::array<double, N_CN>& load) {
    cn_id_t best = INVALID_CN;
    double best_benefit = -INF;
    for (cn_id_t i = 0; i < N_CN; ++i) {
        double benefit = S_atomic(c, i) - C_rpc(c, i)
                       - C_move(c, i) - C_load_penalty(load[i]);
        if (benefit > best_benefit && benefit > theta_b) {
            best = i;
            best_benefit = benefit;
        }
    }
    return best;
}

📎 工程踩坑视角：模块十五第 14 章讲过 v25 cohort planner 用 kMaxCohortSizeRouter=64 + kMaxPublishedCohorts=1024 的工程参数——这两个超参就是为了让 greedy planner 不被超大 cohort 拖死。

---

4. §3.7 AffinityRouter：从写集合到 home CN

4.1 论文公式

$$\text{route}(T) = \arg\max_i \sum_{c \in C_W(T)} \mathbf{1}[\text{owner}(c) = i] \cdot \text{weight}(c, T) - \text{Queue}(i)$$

• $C_W(T)$ —— 事务 $T$ 写集合涉及的 cohort
• $\text{owner}(c)$ —— OwnerMap 上 cohort $c$ 的当前 owner
• $\text{weight}(c, T)$ —— 事务 $T$ 对 cohort $c$ 的访问权重
• $\text{Queue}(i)$ —— CN $i$ 的当前队列深度

4.2 Score(T, i) 公式（§3b W18 加强版）

论文 §3b 给的更详细公式：

$$\text{Score}(T, i) = \sum_{c \in C_W(T)} \mathbf{1}[\text{owner}(c) = i] \cdot A(c) + \beta \sum_{c \in C_R(T)} \mathbf{1}[\text{owner}(c) = i] \cdot R(c) - \text{Queue}(i)$$

🌟 关键改进：

• 写优先（$A(c)$ 在 $C_W$ 上）—— 写锁是 atomic 主源
• 读次要（$\beta$ 加权 $R(c)$ 在 $C_R$ 上）—— 读 token 优先级低
• 队列扣分（$-\text{Queue}(i)$）—— 防止把所有事务路由到一个 CN

4.3 β 的物理含义

β 值	含义	适用场景
β = 0	完全忽略读 cohort	纯 OCC/MVCC 读路径（读不锁）
β = 0.3–0.5	读 cohort 贡献部分权重	读锁存在但远小于写锁
β = 1	读写同等重要	2PL 系统（读也锁）

🌟 AURA v25 默认 β = 0——因为 CREST 是 OCC，读路径走 RDMA READ + version check，不发 atomic，所以读 cohort 对 routing 决策没贡献。

4.4 决策过程示例

   事务 T 写集合 = {cohort_A (CN1 owns), cohort_B (CN1 owns), cohort_C (CN2 owns)}
   事务 T 读集合 = {cohort_D (CN3 owns), cohort_E (CN1 owns)}
   Queue: [CN1=5, CN2=2, CN3=8]
   假设 A(A)=10, A(B)=10, A(C)=10, R(D)=5, R(E)=5
   β = 0.3
   
   Score(T, CN1) = 10 + 10 + 0.3 × 5 - 5 = 16.5  ← 写命中 2 个
   Score(T, CN2) = 10 + 0.3 × 0 - 2 = 8         ← 写命中 1 个
   Score(T, CN3) = 0 + 0.3 × 5 - 8 = -6.5       ← 写命中 0 个
   
   → 路由到 CN1（最大化写命中）

🧠 关键洞察：写命中比读命中重要 30 倍以上——这是 AURA 减少 atomic 的本质。

📎 工程踩坑视角：模块十五第 12 章讲过 W18 工程实现的 TransactionRouter::Resolve——这是 §4 公式的工程落地版。

---

5. 双层路由：OwnerOfKeyGroup + RouteByWarehouse fallback (Lever B)

5.1 为什么需要双层

理论上 §3.7 公式直接按 cohort owner 路由就行——但工程上有两个 corner case：

Corner case 1：事务里出现一个 新 key，OwnerMap 上还没这个 cohort（cold key）

• 不能 abort，必须有 fallback 路由

Corner case 2：Router 进程刚启动，OwnerMap 是空的

• 不能停服等 Planner 学完第一轮

🌟 AURA v25 工程解决方案：双层路由

cn_id_t RoutingTable::Resolve(const TxnDescriptor& td) {
    // Lever B: primary cohort 路由（如果命中）
    auto primary_kg = MakeKeyGroupId(DISTRICT_TABLE, td.district_key);
    cn_id_t cohort_owner = OwnerOfKeyGroup(primary_kg);
    if (cohort_owner != INVALID_CN) return cohort_owner;
    
    // Fallback: 按 home_warehouse 静态路由
    return RouteByWarehouse(td.home_wh);
}

5.2 OwnerOfKeyGroup：cohort overlay 路由

cn_id_t OwnerOfKeyGroup(KeyGroupId kg) {
    auto it = kg_overrides_.find(kg);
    if (it == kg_overrides_.end()) return INVALID_CN;
    return it->second.owner_cn;
}

• kg_overrides_ 由 Router 的 manifest publish 维护
• 只覆盖热 cohort（按 Benefit 决策出来的）
• 冷 cohort 留给 RouteByWarehouse fallback

🌟 结论：热数据走 cohort overlay，冷数据走 wh 静态路由 —— 这是 AURA 的两层路由策略。

5.3 RouteByWarehouse：静态 fallback

cn_id_t RouteByWarehouse(int home_wh) {
    return home_wh % N_CN;
}

最简单的 hash 路由——与 wh 数量无关、与 cohort 学习无关，总是有定义。

🧠 关键洞察：这是 AURA 的”地板”——即使 Planner 完全没学到任何 cohort，事务也能按 wh 路由到 CN，系统不会停服。

5.4 Lever B 的反直觉负结果（v25 实测）

v25 在 TPCC 上测了 Lever B + 关闭 Lever B 两组：

配置	LOCAL hit	atomic_per_txn	KOPS
Lever B OFF（只用 RouteByWarehouse）	17%	13.51	134
Lever B ON（OwnerOfKeyGroup + fallback）	17%	13.51	133（持平）

🌟 反直觉：Lever B 没有显著提升——LOCAL hit 没涨、atomic 没降。

5.5 为什么 Lever B 没用：feedback loop

诊断后的根因：client cohort-aware dispatch + router cohort planner 形成 feedback loop：

   1. router 学到 cohort C 被 CN_x 70% 访问 → 把 C 给 CN_x
   2. client 看到 C 的 owner 是 CN_x → 把所有访问 C 的事务路由到 CN_x
   3. CN_x 上 access pattern 变得更加偏向 C → router 学到 C 100% 在 CN_x
   4. cohort 集合开始 collapse（其他 cohort 失去访问，被 evict）
   5. 几个 tick 后，活跃 cohort 数减少到极少
   6. AffinityRouter 大部分时候用 RouteByWarehouse fallback
   7. 结果与 Lever B OFF 没区别

🧠 关键洞察：Lever B 的根本问题是 record_key 编码——TPCC MakeStockKey(w_id, i_id) = w_id × 10000 + i_id 让 stock bucket 在 wh 间 hash 均匀。Cohort 没法按 home_wh 聚簇，所以 cohort 的 owner 与 wh 静态路由几乎重合。

📎 工程踩坑视角：模块十五第 14 章 §8.4 详细诊断了这个 feedback loop，并提出”record_key reshape 必须在 Lever B 之前做”。详见第 8 章。

5.6 Lever B 的方法论教训

🌟 可推广教训：当多个 lever 形成 feedback loop 时，激活顺序决定结果。

错误顺序	后果
先激活 client cohort-aware dispatch（Lever B），后做 record_key reshape	反馈环 collapse，效果归零
先做 record_key reshape，让 cohort 能按 home_wh 聚簇，再激活 Lever B	两个 lever 互相增强，效果叠加

第 8 章会展开”lever ordering 方法论”。

---

6. 一张图把 §3.5–3.7 串起来

   ┌───────────────────────────────────────────────────────────────┐
   │                       Router 进程                              │
   │                                                                │
   │   AccessGraphProfiler  ──► cohort 集合 C                       │
   │   (来自第 5 章)                  │                              │
   │                                  ▼                              │
   │              ┌───────────────────────────────────────┐         │
   │              │  OwnershipPlanner (§3.5–3.6)           │         │
   │              │  for each c in C:                       │         │
   │              │    for each CN i:                       │         │
   │              │      Benefit(c, i) = S_atomic           │         │
   │              │                    - C_rpc              │         │
   │              │                    - C_move             │         │
   │              │                    - C_load             │         │
   │              │    pick best i (if Benefit > θ_b)       │         │
   │              │  → owner_map: cohort → owner_cn         │         │
   │              └────────────────────┬──────────────────┘         │
   │                                   │                              │
   │                                   ▼                              │
   │              ┌───────────────────────────────────────┐         │
   │              │  AffinityRouter (§3.7)                 │         │
   │              │  for txn T:                             │         │
   │              │    Score(T, i) = Σ_{c ∈ C_W(T)} A(c)    │         │
   │              │                  + β Σ_{c ∈ C_R(T)} R(c)│         │
   │              │                  - Queue(i)             │         │
   │              │    if owner overlay hit → route by cohort│        │
   │              │    else → RouteByWarehouse fallback     │         │
   │              └────────────────────┬──────────────────┘         │
   │                                   │                              │
   └───────────────────────────────────┼──────────────────────────────┘
                                       │ Dispatch ExecuteTxn (TCP)
                                       ▼
                                  ┌──────────┐
                                  │  Home CN │
                                  └──────────┘

🌟 结论：OwnershipPlanner 决定”谁拥有”，AffinityRouter 决定”事务找谁”——两个组件接力把”cohort 学习”翻译成”事务路由”。

✅ 自我检验清单

• Benefit 公式：能徒手写 Benefit = S_atomic − C_rpc − C_move − C_load + 解释每项物理含义
• S_atomic vs C_rpc：能解释为什么这两项是”同一 cohort 的两面”
• C_move 必要性：能解释为什么没有 C_move 会导致 Planner 抖动
• C_load 平方惩罚：能解释为什么用 (overload)² 不是 max(0, overload)
• Greedy 算法：能写伪代码 + 解释 O(|H| × N_CN) 复杂度
• ArgmaxOwner：能从 Benefit 公式推导 ArgmaxOwner 实现
• AffinityRouter Score 公式：能写 Score(T, i) 公式 + 解释 β 的物理含义
• β=0 的原因：能解释 CREST OCC 下为什么 β=0（读不锁）
• 双层路由：能讲清 OwnerOfKeyGroup 命中 vs RouteByWarehouse fallback 的分工
• Lever B 负结果：能讲清 feedback loop 的形成 + record_key 是根因 + lever ordering 教训

第 7 章预告

第 7 章按论文 §4 展开 迁移协议与一致性证明：

• freeze-drain-handoff-publish 4 阶段时序
• 每阶段的 RDMA / 内存操作 / 锁状态
• I1–I4 不变量在每阶段的证明草图
• TransferController + OwnerMapPublisher 的协作
• corner case：owner CN 在 handoff 中途 crash 怎么办

读完第 7 章你能徒手画 4 阶段时序图 + 给出每条 I 的违反 corner case + 防御。

---

📚 参考资料

论文原文

• AURA paper §3.5 所有权规划目标：paper_lock_ownership_cn/sections/3_design_overview.tex
• AURA paper §3.6 可实现的规划器：同上
• AURA paper §3.7 亲和路由：同上
• AURA paper §3b OwnershipPlanner + AffinityRouter：paper_lock_ownership_cn/sections/3b_component_workflows.tex

算法相关

• Greedy assignment with capacity constraints —— 任一组合优化教材
• Argmax-based scheduling —— scheduler 文献常见原语

参照系统

• MorphoSys 学习型 cost model —— 论文 §3.6 提到的后续扩展方向
• TiDB PD scheduler —— 工业级 region balance 算法（cost model 思路类似）

模块内交叉引用

• 本模块第 5 章：访问图与 cohort 学习 —— Benefit 公式 S_atomic / C_rpc 的统计量都来自第 5 章
• 本模块第 8 章：Router-Centric 实现细节（待写）—— Lever B 负结果 + record_key reshape 方法论
• 模块十五第 12 章：W15/W16/W18 跨 CN 一致性 —— AffinityRouter 工程展开
• 模块十五第 14 章：Router-centric 重构 —— §5 Lever B 负结果的工程现场