第5章：访问图与 cohort 学习

第 4 章把 AURA 的 12 模块图 + 三态生命周期 + I1–I4 不变量讲完，本章正式进入论文 §3.3 + §3.4 的算法本体——访问图怎么建、cohort 怎么从图上长出来。这是整个 AURA 论文最”算法味”的一章：typed edge（ww/wr/rr）为什么必须区分、EWMA decay 的半衰期物理含义、union-find merge 为什么必须配 Jaccard 迟滞、倒排索引为什么砍掉 W14 的 1500×250 explosion。读完你能徒手讲完”事务流 → 顶点边权更新 → cohort 形成” 的 online 学习链，并能解释每个超参（α / 半衰期 / Jaccard 阈值 / streak）的物理含义。

📑 目录

1. 全景：从事务流到 cohort 的 4 步流水线
2. §3b W13 TraceCollector：把事务变成可学习样本
3. §3.3 AccessGraphProfiler：顶点 + 边的在线维护
4. Typed edge：ww / wr / rr 为什么必须区分
5. EWMA decay：半衰期物理含义推导
6. §3.4 LockCohortGenerator：merge / split / transfer / evict
7. §3b W14 工程细节：union-find + Jaccard + 倒排索引

1. 全景：从事务流到 cohort 的 4 步流水线

   事务流（TPC-C NewOrder / SmallBank Amalgamate / TATP UpdateLocation）
      │
      ▼
   ┌─────────────────────────────────┐
   │ Step 1: TraceCollector          │  把 key 映射到 key group, 旁路采样
   │   record_key → key_group        │  按采样率 p 投递事件
   │   {vertex_access, edge_access,  │
   │    txn_result}                  │
   └────────────────┬────────────────┘
                    ▼
   ┌─────────────────────────────────┐
   │ Step 2: AccessGraphProfiler     │  顶点计数 + 边计数（按 ww/wr/rr 分类）
   │   R(v)/W(v)/A(v)                │  EWMA decay 防止历史污染
   │   C(u,v) + P_ww/P_wr/P_rr       │
   └────────────────┬────────────────┘
                    ▼
   ┌─────────────────────────────────┐
   │ Step 3: LockCohortGenerator     │  在图上找强连通子集
   │   union-find merge              │  Jaccard 阈值 + streak 迟滞
   │   ww 边优先于 wr 优先于 rr      │  α 加权降权
   └────────────────┬────────────────┘
                    ▼
   cohort 集合 → 喂给 §3.5 OwnershipPlanner（第 6 章）

🌟 每一步的关键算法：

步	关键算法	关键超参	关键工程细节
1	record → key group 映射	采样率 p	thread_local batch 防丢尾
2	顶点边权 EWMA 更新	decay λ	typed edge 分类（ww/wr/rr）
3	union-find merge	Jaccard 阈值 + streak	倒排索引砍 1500×250 explosion
4	merge/split/transfer/evict 决策	Benefit 函数（第 6 章）	冷却时间防抖

🍎 学习节奏建议：本章长度比前 4 章长——因为论文里 §3.3 + §3.4 + §3b W13/W14 加起来是密度最大的一段。先通读全景，再按 §2–§7 一节一节啃。

2. §3b W13 TraceCollector：把事务变成可学习样本

2.1 输入：事务的读写集合

   TPC-C NewOrder 一个事务的读写集合（简化）：
   ┌─────────────────────────────────────────────┐
   │ Reads:                                       │
   │   WAREHOUSE(w_id=2)                          │
   │   DISTRICT(w_id=2, d_id=3)                   │
   │   CUSTOMER(w_id=2, d_id=3, c_id=42)          │
   │   STOCK(w_id=2, i_id=10)                     │
   │   STOCK(w_id=2, i_id=11)                     │
   │   ...                                        │
   │ Writes:                                      │
   │   DISTRICT(w_id=2, d_id=3) [d_next_o_id++]  │
   │   ORDER, ORDER_LINE, NEW_ORDER inserts       │
   │   STOCK(w_id=2, i_id=10) [s_quantity--]      │
   │   STOCK(w_id=2, i_id=11) [s_quantity--]      │
   └─────────────────────────────────────────────┘

🌟 关键观察：一个事务同时访问多张表，读写集合共享 wid。这是 AURA cohort 能跨表聚簇的物理基础。

2.2 工作流：record_key → key_group 映射

// 简化版（来自 src/transaction/aura/KeyGroupId.h）
inline key_group_id_t MakeKeyGroupId(int table_id, uint64_t record_key) {
    return (uint64_t(table_id) << 10) | (record_key & 0x3FF);
}

🧠 关键洞察：

9 张 TPCC 表（WAREHOUSE/DISTRICT/CUSTOMER/HISTORY/STOCK/ORDER/ORDER_LINE/NEW_ORDER/ITEM）→ 9 张表 × 1024 bucket = 9216 key group
bucket = record_key % 1024（哈希后均匀分布）
table_id 在高位、bucket 在低位 → 同一表的 bucket 在数值上连续，便于范围统计

📎 工程踩坑视角：模块十五第 14 章讲过 MakeStockKey(w_id, i_id) = w_id * 10000 + i_id 导致 stock bucket 在 wh 间哈希均匀，所以 cohort 不能按 home_wh 分。这是 §5 record_key reshape 的根本动机。

2.3 算法原则：采样率公式

论文 §3b 给的采样率公式：

p_i = \min\left(p_{\max}, \frac{B_{\text{sample}}}{tps_i + \epsilon}\right)

$p_{\max}$ ：采样率上限（典型 1.0 = 全采）
$B_{\text{sample}}$ ：每 CN 每秒允许的样本预算
$tps_i$ ：CN $i$ 的当前吞吐

🌟 结论：采样开销不随吞吐线性失控——高吞吐时降低采样率，让 trace 路径不占 CPU。

📎 工程踩坑视角：模块十五第 10 章讲过 thread_local batch + 提交后批量投递的细节——这是 §2 工程实现的展开版。

3. §3.3 AccessGraphProfiler：顶点 + 边的在线维护

3.1 顶点状态

每个 key group $v$ 维护：

量	含义	EWMA 更新
$R(v)$	读访问频率	$R(v) \leftarrow \lambda R(v) + r_t$
$W(v)$	写访问频率	$W(v) \leftarrow \lambda W(v) + w_t$
$A(v)$	RDMA atomic 压力	$A(v) = W(v) \cdot C_{CAS} + Abort(v) \cdot C_{retry}$
$L(v)$	当前 owner CN 上的本地 CPU 负载	从 AuraStats 反馈

3.2 边状态

每条边 $(u, v)$ 维护：

量	含义	更新
$C(u,v)$	共同访问频率（总）	$C(u,v) \leftarrow \lambda C(u,v) + c_t$
$P_{ww}(u,v)$	写写共同访问占比	$P_{ww} \cdot C(u,v) = C_{ww}$
$P_{wr}(u,v)$	写读共同访问占比	同上
$P_{rr}(u,v)$	读读共同访问占比	同上

🌟 关键设计：边按访问模式（ww / wr / rr）分类——AURA 不是建简单”共同出现图”，是建typed access graph。

🧠 关键洞察：为什么必须区分类型？因为 ww 边和 rr 边对 atomic 压力的贡献完全不同——ww 共同访问意味着这两个 key group 会同时争锁，rr 共同访问只是会一起读，不引发 atomic。后面 §4 会展开。

📎 工程踩坑视角：模块十五第 10 章讲过为什么 W13 在工程层踩了”统一边权”的坑——这是 §3 必须 typed 的工程对照。

4. Typed edge：ww / wr / rr 为什么必须区分

4.1 三种边的物理含义

边类型	共同访问含义	对 atomic 压力的贡献
ww	两个 key group 在同一事务中都被写	高 —— 两把锁都要争
wr	一个被写、一个被读	中 —— 写那个要锁，读那个看版本
rr	两个都只被读	低 —— 都走 RDMA READ，不锁

4.2 不区分的代价（W13 早期工程坑）

模块十五第 10 章讲过：W13 早期版本只维护一个总 C(u,v)——结果 AURA cohort 把”热读 + 冷写”的 key group 合并到一个 cohort，promote 后 atomic 没降。

   反例：
   cohort A: 热写 stock(w_id=2, i_id=*)
   cohort B: 热读 item(*)
   总边权 C(A, B) 很高 (NewOrder 同时访问 stock + item)
   合并后 → promote 到一个 CN
   但 atomic 压力来自 stock 写锁，不是 item 读 → 合并没价值

🌟 结论：合并只对 ww 边有显著 benefit；wr 边次之；rr 边几乎为零。

4.3 加权聚合

AURA v25 用的加权公式（论文 §3.4 + §3b W14）：

W_{\text{typed}}(u, v) = C_{ww}(u, v) + \alpha_{wr} \cdot C_{wr}(u, v) + \alpha_{rr} \cdot C_{rr}(u, v)

$\alpha_{wr} = 0.3$ （v25 实测最佳）
$\alpha_{rr} = 0$ （rr 边对 atomic 不贡献，忽略）

🧠 关键洞察：α 实际上是”按类型对 atomic benefit 打折”的系数——直接物理含义是”一个 wr 共同访问相当于 0.3 个 ww 共同访问的 cohort 合并 benefit”。第 6 章 Benefit 模型会再用到。

📎 工程踩坑视角：模块十五第 10 章 “α=0.3 的物理含义” 那一节是这里的 deep dive。

5. EWMA decay：半衰期物理含义推导

5.1 论文公式

X_t = \lambda X_{t-1} + \Delta_t

5.2 半衰期推导

如果 $\Delta_t = 0$ （不再有新观测）， $X$ 衰减到一半需要多少步 $t_{1/2}$ ？

\lambda^{t_{1/2}} = 0.5 \implies t_{1/2} = \frac{\ln 0.5}{\ln \lambda}

实测的 v25 默认 $\lambda = 0.95$ ，则：

t_{1/2} = \frac{-0.693}{-0.051} \approx 13.5 \text{ ticks}

每 tick 是 100 ms， $t_{1/2} \approx 1.35$ s。

🌟 结论：v25 的 EWMA 半衰期 ~1.35 秒——hotspot 漂移如果持续 < 1.35 秒，AURA 还来不及反应；> 1.35 秒 cohort 就跟着搬。

5.3 半衰期选择的权衡

半衰期	漂移响应	抖动风险
太短（< 0.5s）	响应快	误把瞬时抖动当成漂移，频繁迁移
太长（> 5s）	响应慢	hotspot 已经搬走但 cohort 还没跟上
1–2s（v25 默认）	平衡	典型 OLTP workload 的甜点

🧠 关键洞察：半衰期是控制环带宽的关键超参——它决定了 AURA 能多快跟随漂移、又不被瞬时抖动带偏。第 6 章 OwnershipPlanner 的迁移冷却时间是它的另一面。

📎 工程踩坑视角：模块十五第 7 章讲过 AdaptX 闭环 5ms 与 AURA 100ms tick 的关系——这是 §5 半衰期选择的更广视角。

6. §3.4 LockCohortGenerator：merge / split / transfer / evict

6.1 4 类操作

操作	触发条件	效果
Merge	两 cohort 的 $C_{ww}$ 长期高，合并后不超 owner 负载	减少跨 owner RPC
Split	cohort 内出现多个弱相关热点，或 owner 上等待时间过高	沿弱边切，让热点分散
Transfer	大部分事务被另一 CN 执行，或当前 owner 过载	迁移 ownership
Evict	长期低温（< $\theta_{cold}$ ）	退回 fallback

6.2 Merge 收益函数

论文给的合并收益（简化）：

\text{Gain}_{\text{merge}}(c_a, c_b) = C_{ww}(c_a, c_b) \cdot C_{RPC} - \text{LoadPenalty}(c_a \cup c_b) - \text{StateCost}(c_a \cup c_b)

$C_{ww}(c_a, c_b)$ —— 两 cohort 间 ww 共同访问（合并后省下的 RPC）
$C_{RPC}$ —— 一次跨 CN RPC 的成本（典型 5 μs）
$\text{LoadPenalty}$ —— 合并后 owner 负载是否超限
$\text{StateCost}$ —— OwnerLockTable 内部状态膨胀代价

🌟 结论：Merge 收益 > 阈值 + 合并后负载 < 预算 → 合并。

6.3 Split 决策

Split 反向找弱边：

   cohort c 内部图：
     ┌───┐     ┌───┐
     │ A │─────│ B │   (强 ww 边)
     └───┘     └───┘
       │          │
       │          │ (弱跨 cluster 边)
       │          │
     ┌─┴─┐     ┌─┴─┐
     │ C │─────│ D │   (强 ww 边)
     └───┘     └───┘

   → 沿 (B,C) 或 (B,D) 这条弱边切，分成 {A,B} 和 {C,D}

🧠 关键洞察：Split 是 Merge 的对偶。一个 workload 漂移会同时触发 cohort split + 新 cohort merge——这就是为什么”cohort 不是静态分区”。

6.4 4 类操作的 MorphoSys 对应

AURA 操作	MorphoSys 对应	作用对象差异
Merge	merge replicas / partitions	AURA 合并锁权威，MorphoSys 合并数据
Split	split partition	同上
Transfer	remaster	AURA 搬锁，MorphoSys 搬主副本
Evict	remove replica	AURA 退回 fallback，MorphoSys 真的删数据

🌟 结论：AURA 借鉴 MorphoSys 的”在线物理变形”思想，但作用对象从”数据分区”换成”锁权威”。详见第 3 章 §4 + 第 4 章 §1.3。

7. §3b W14 工程细节：union-find + Jaccard + 倒排索引

7.1 朴素 Jaccard 的工程坑

W14 早期版本：每个 cohort 与其他所有 cohort 算 Jaccard 相似度，相似度高就 merge。

   cohort 数量 N → O(N²) Jaccard 计算
   N=1500 → 1500 × 250 ≈ 375K 次 Jaccard
   每次 Jaccard O(|cohort|)
   控制线程每 tick 卡 几百 ms

🌟 结论：朴素 Jaccard 把控制线程冲飞，ms 级控制环退化为 s 级。

7.2 W14 工程修复：倒排索引

   维护：key_group → [覆盖它的 cohort 列表]
   每个新 cohort 来：
     1. 查倒排索引找候选 cohort
     2. 只对"有共享 key_group"的 cohort 算 Jaccard
   候选数从 N 降到 ~50

🌟 结论：1500 × 250 explosion 降到 ~50 候选 —— 控制线程从 ms 级回到 5 ms tick 内。

📎 工程踩坑视角：模块十五第 11 章是这个倒排索引的代码 walkthrough。

7.3 Jaccard 迟滞：streak 防止抖动

朴素 merge：单 tick 看 Jaccard 高就 merge → 下一 tick 一个事务模式变了又 split → 抖动。

修复：streak 迟滞：

   for each (c_a, c_b) candidate pair:
     if Jaccard(c_a, c_b) > θ_merge:
       streak[c_a, c_b] += 1
     else:
       streak[c_a, c_b] = 0
     if streak[c_a, c_b] >= 3:    // 连续 3 个 tick 都 > 阈值
       merge(c_a, c_b)

🌟 结论：streak ≥ 3 的迟滞让 merge 决策抗 1-tick 噪声。

7.4 Union-Find：cohort_id 漂移问题

合并两个 cohort 后，它们的 cohort_id 谁继承谁？

   merge(c_a, c_b) → 新 cohort 的 id 选 min(c_a.id, c_b.id)
   或者：用 union-find 的 root id

🧠 关键洞察：id 选择影响所有引用过老 id 的下游模块——OwnerLockTable、Manifest publisher、OwnerMapSubscriber 都需要知道 id 重映射。AURA v25 用 CohortIdFor(min_kg) 做命名规范，避免漂移。

📎 工程踩坑视角：模块十五第 11 章讲过 “1229 cohort + 100% inheritance + LOCAL hit 0.3%” 的反直觉——根因是 cohort_id 漂移没传到 OwnerMapSubscriber。这是本节工程教训的具体案例。

7.5 一张工程优化前后的对比

维度	W14 早期（朴素）	W14 v25（倒排索引 + streak）
每 tick Jaccard 计算次数	1500 × 250 = 375K	~50
控制线程 tick 耗时	百 ms	5 ms
抖动次数 / 分钟	几十次	0–1 次
Cohort 总数稳定性	漂 ±200	稳定 ±10

🌟 结论：工程优化让算法的”理论收益”真正落到生产。算法对了不等于工程做对了——这是 §3b W14 章节背后的工程哲学。

✅ 自我检验清单

4 步流水线：能徒手画 TraceCollector → AccessGraphProfiler → LockCohortGenerator → cohort 集合
key_group 编码：能解释 (table_id << 10) | (bucket) 的高低位含义 + 9216 怎么来的
typed edge 必要性：能用 “stock 热写 + item 热读” 反例解释为什么必须区分 ww / wr / rr
α=0.3 物理含义：能解释 “一个 wr 共同访问相当于 0.3 个 ww 共同访问的合并 benefit”
EWMA 半衰期：能推导 $t_{1/2} = \ln 0.5 / \ln \lambda$ + 计算 λ=0.95 半衰期 ≈ 13.5 ticks
4 类操作：能列出 merge/split/transfer/evict 各自的触发条件 + MorphoSys 对应
倒排索引：能解释为什么 1500×250 explosion 能砍到 ~50（共享 key_group 候选）
Jaccard 迟滞：能写 streak ≥ 3 的伪代码并解释为什么这么做
cohort_id 漂移：能讲清楚为什么 union-find 后 id 选择需要全局一致命名

第 6 章预告

第 6 章按论文 §3.5–3.7 + §3b W16/W18 展开 Owner 规划与亲和路由：

Benefit = S_atomic − C_rpc − C_move − C_load 每一项的物理推导
Greedy planner 算法 + 容量约束
AffinityRouter Score(T, i) 公式 + β 系数的物理含义
OwnerOfKeyGroup 与 RouteByWarehouse fallback 怎么配合

读完第 6 章你能讲清楚 “router 怎么决定一个 cohort 归谁 + 一个事务路由到哪个 CN”。

📚 参考资料

论文原文

AURA paper §3.3 事务访问图：paper_lock_ownership_cn/sections/3_design_overview.tex
AURA paper §3.4 锁簇生成：同上
AURA paper §3b TraceCollector / AccessGraphProfiler / LockCohortGenerator：paper_lock_ownership_cn/sections/3b_component_workflows.tex

算法相关

EWMA decay —— 信号处理基础（参考 Oppenheim DSP 教材任一版）
Union-Find —— 任一数据结构教材；Kruskal MST 同款算法
Jaccard 相似度 —— 集合相似度经典度量

参照系统

Lion (Yan et al., 2024) —— 访问图驱动 partition 重排（论文 §3.3 引用）
MorphoSys (Lemur et al., VLDB’21) —— “在线物理变形”思想（论文 §3.4 引用）

模块内交叉引用

本模块第 4 章：Router-Centric 架构 —— 本章的上游：AccessGraphProfiler 在哪个组件
模块十五第 10 章：访问图工程实操：typed edges 与采样队列踩坑 —— 本章 §3 §4 的工程展开
模块十五第 11 章：W14 Cohort merge 的稳定性陷阱 —— 本章 §7 倒排索引 + streak 迟滞的工程实战

搜索