第10章：从 §3.3 到 W13 —— 访问图的工程实操与采样队列踩坑

模块十五第 5 章把访问图讲清楚了：节点是 key_group，边权是”两个 KG 在同一个事务里被共同访问的频率”。但当真的写代码把 §3.3 落地时会发现，这条”一条边一个权重”的设定藏着两个会让 cohort 划分失真的洞：写-写共访和写-读共访的物理含义完全不同（前者意味着锁竞争、后者只意味着 prefetch 受益），混在一起会让 cohort merge 把没有 LOCAL 收益的 read-only 簇也合并进来；trace 采样如果走 thread_local batch + 周期 flush，1000 个事务的 W13 闸门会丢掉绝大多数尾部样本。本章把 W13 的工程实操从设计到落地拆给你看，最后会诚实交代一个反直觉发现：W13 单独上线，ablation 不会动一寸——这是 bug 还是 feature？

📑 目录

• 1. 单边图的歧义 —— 第 5 章模型为什么不够用
• 2. C_ww / C_wr / C_rr —— typed edges 的三类语义
• 3. EWMA decay 0.99 —— 半衰期推导与”为什么不是 0.85”
• 4. 钩点选择 —— TxnIO.acquire vs Txn.Commit / Abort
• 5. 采样队列踩坑 —— thread_local batch 与 1000-txn 闸门
• 6. merge_score = C_ww + α · C_wr —— α=0.3 的物理意义
• 7. W13 落地后的 ablation 不动 —— 这是 bug 还是 feature
• 自我检验清单
• 参考资料

---

1. 单边图的歧义 —— 第 5 章模型为什么不够用

第 5 章给了访问图最干净的形式化：

G = (V, E)
V = { kg_i }                    // KG 节点
E = { (kg_i, kg_j, w_ij) }      // 共访边权
w_ij = 两个 KG 在同一个事务内被共同访问的 EWMA 平滑频率

这套模型在白板上看是齐的。落到代码会撞到第一个语义陷阱：「共同访问」是什么访问？

考虑 TPC-C NewOrder 的典型 footprint：

Warehouse(W=1)             // 读了一次，没改（只用来读 ytd）
District(W=1, D=2)         // 读出 d_next_o_id，写回 d_next_o_id + 1
Stock(W=1, I=42) × 10      // 全部 read-modify-write

如果把这三类记录在同一个事务里两两配对加一条边权，Warehouse↔District 的边权和 District↔Stock 的边权会变成同一个数量级。但这两条边的物理含义截然不同：

• District ↔ Stock：两边都被写，意味着如果两笔 NewOrder 同时跑，会在 District 锁和 Stock 锁上先后串行——这是真实的锁竞争。把它们划进同一个 cohort，由同一个 CN 持有所有相关锁，能消掉一次跨 CN 的 atomic CAS。
• Warehouse ↔ District：Warehouse 只读，不参与锁路径。即便把它划进 District 的 cohort，Warehouse 的锁路径根本不经过 OwnerLockTable，本地化也省不出 atomic CAS。

🍎 直觉比喻：把访问图想象成一张餐厅顾客的”同桌矩阵”。两个顾客都点了限量菜（写），他们的”同桌”意义是”会抢”；一个点限量菜、一个只点白开水（读），他们的”同桌”是”碰巧坐一块儿”。让限量菜厨师专门服务前一桌有意义，让他兼顾后一桌只是浪费。

🌟 结论：「共访」是个 overloaded 概念，必须按访问模式分型——否则 cohort merge 的目标函数就被污染了。这就是 §3.3 typed edges 存在的根因，也是为什么第 5 章的单边模型在 W13 落地时必须升级。

---

2. C_ww / C_wr / C_rr —— typed edges 的三类语义

W13 的修复是把一条边拆成三条：

边类型	全称	触发条件	物理含义	在 cohort merge 里的权重
C_ww	write-write	两个 KG 都在事务的 write_kgs 里	真实锁竞争源 —— 两笔事务并发会争抢这两个 KG 的锁	主驱动力（α=1）
C_wr	write-read	一个 KG 在 write_kgs、另一个在 read_kgs	prefetch / 读副本受益 —— 把写锁本地化能让相邻读省一次远端 fetch	次要（α=0.3）
C_rr	read-read	两个 KG 都在 read_kgs	只读路径，不进入锁路径	stats only（不参与 merge）

代码层面三类边各开一张 hash map，由 AuraControlLoop Tick 一次性派生：

// AuraControlLoop.h:251-254
static absl::flat_hash_map<EdgeKey, double, EdgeKeyHash> edge_ww_;
static absl::flat_hash_map<EdgeKey, double, EdgeKeyHash> edge_wr_;
static absl::flat_hash_map<EdgeKey, double, EdgeKeyHash> edge_rr_;

派生逻辑在 Tick 里，三段非常对称：

// AuraControlLoop.cc:459-463
for (const auto& s : drained_edges) {
    add_pairs_same_set (s.write_kgs,                edge_ww_);  // C_ww
    add_pairs_cross_set(s.write_kgs, s.read_kgs,    edge_wr_);  // C_wr
    add_pairs_same_set (s.read_kgs,                 edge_rr_);  // C_rr
}

add_pairs_same_set 因为 RecordTxnFinish 入口已经把 read_kgs / write_kgs 排好序去过重，pair (v[i], v[j]) 满足 i < j 自然就 v[i] < v[j]，可以省去运行时 min/max；add_pairs_cross_set 必须在每对 (w, r) 上做一次 min/max 才能产出 canonical EdgeKey（写和读的 KG ID 域可以任意交错，不能假设大小关系）。

⭕ C_rr 看似多余，为什么要保留？ —— 不用来做 merge，但用来做观测。AURA 在 §3.3 的论述里同时关心”hot kg”和”hot read footprint”；C_rr 是后者的代理。当未来想引入 read-only replica steering（第 7 章 Loop B 那个方向），C_rr 的统计已经在那里，不需要再加新通路。

🌟 关键洞察：typed edges 不是论文的形式主义，而是给 cohort merge 提供”边权语义”的下层。下游所有 merge / planner / migration 决策的好坏，都依赖这里的语义清晰度。

---

3. EWMA decay 0.99 —— 半衰期推导与”为什么不是 0.85”

第 5 章讲了”指数衰减让旧 trace 自然消失”，但没说衰减系数到底定多少、怎么定。W13 这里把两条衰减常数都拍死，理由值得拆开。

代码里有两个常数：

// AuraControlLoop.h:199, 210
static constexpr double DECAY      = 0.85;   // 单 KG 顶点权重的衰减
static constexpr double EDGE_DECAY = 0.99;   // typed edge 边权的衰减

单一顶点的 DECAY = 0.85

每个 tick（5ms）kg_count_[kg] *= 0.85。半衰期推导：

0.85^n = 0.5
n = log(0.5) / log(0.85) ≈ 4.27 ticks
4.27 × 5ms ≈ 21ms 半衰期

为什么 21ms 合理？因为单 KG 在 hot workload 下每 tick 几乎都会被命中（采样队列每 tick 上千个样本），衰减得快一点没问题——只有真的不再 hot 的 KG，连续几个 tick 没采样才会被压下去。

typed edge 的 EDGE_DECAY = 0.99

每个 tick edge_*[k] *= 0.99。半衰期：

0.99^n = 0.5
n = log(0.5) / log(0.99) ≈ 68.97 ticks
68.97 × 5ms ≈ 345ms 半衰期

🧠 为什么边权要慢一个量级衰减？ —— 因为 typed edge 是二项 fanout：两个 KG 必须同时出现在某个事务里才会被加一次。如果一个 cohort 有 K 个成员，组内边的总数是 K(K−1)/2，而每个事务对其中一对才触发加权——所以单条边被命中的频率比单个顶点稀疏 K 倍。

实测中：1000-txn W13 闸门跑完，顶点数 ~3000，边数 ~10000（cap 后），平均每条边在 1000 个事务里只被命中 1-3 次。如果还用 DECAY=0.85 衰减，21ms 半衰期意味着一条边过 4 个 tick（20ms）就被压成原来的一半——这条边在新闸门里根本来不及形成稳定信号就被衰减消失。

直接对照源码里的注释：

// AuraControlLoop.h:201-209
// W13.c: edges decay slower than vertices because individual
// (kg_a, kg_b) pairs fire less frequently than single-KG events
// (the bipartite expansion is N^2/2 sparse). With ~85 ticks/s
// observed and EDGE_DECAY=0.99, a sample's contribution halves
// every ~70 ticks (~0.8s wall), which is the same effective
// half-life as vertex DECAY=0.85 over a single-vertex sample.
// Otherwise the empirical edge weights underflow to ~1e-70
// long before W14 cohort merge can compare them against
// MERGE_THRESHOLD.

⭐ 如果不按”边采样比顶点稀疏”这个事实选边衰减，会出现的具体 bug：每个 tick 衰减得太快 → 边权快速 underflow 到 ~1e-70 → W14 merge 阶段对照 MERGE_THRESHOLD 全部判负 → 永远没有 cohort 被合并 → ablation 上看起来 “AURA 控制面没收益” —— 这是一个静默的、不会报错的 bug，没有日志会告诉你它的存在。

---

4. 钩点选择 —— TxnIO.acquire vs Txn.Commit / Abort

第 5 章讨论”trace 不能无限堆”的时候没回答一个问题：trace 从哪里采？这个钩点选择会决定访问图的覆盖范围。

W13 之前 AURA 只有一个钩点：

// AuraControlLoop::RecordAccess(kg) — 在 TxnIO.acquire 路径上被调用

这是个单 KG 单事件钩点，每次某个事务获取一把锁就触发一次。问题：

• 只看到写：TxnIO.acquire 是写锁路径，读路径走的是另一条 LockReadBatch，不进 RecordAccess。所以访问图里只有 write footprint，C_wr 这条信息根本采不到。
• 不知道事务边界：单事件钩没法天然形成”哪些 KG 是同一个事务里访问的”——必须额外用 thread_local 数组追踪，再在 commit/abort 处 flush。这等于在 TxnIO 路径上加一个无用的状态。

W13 的修复是新加一个事务级钩点：

// Txn.cc:270-298
void Txn::AuraRecordTxnFinish(bool committed) noexcept {
    // ...
    std::vector<aura::key_group_id_t> read_kgs;
    std::vector<aura::key_group_id_t> write_kgs;
    read_kgs.reserve(selected_records_.size());
    write_kgs.reserve(selected_records_.size() + insert_records_.size());

    for (const auto& r : selected_records_) {
        const auto kg = aura::MakeKeyGroupId(r.table_id(), r.record_key());
        if (r.has_write()) {
            write_kgs.push_back(kg);
        } else if (r.has_read()) {
            read_kgs.push_back(kg);
        }
    }
    for (const auto& r : insert_records_) {
        write_kgs.push_back(
            aura::MakeKeyGroupId(r.table_id(), r.record_key()));
    }

    aura::AuraControlLoop::RecordTxnFinish(read_kgs, write_kgs, committed);
    // ...
}

这个钩点跑在 Txn::Commit() 和 Txn::Abort() 的末尾，遍历事务的 selected_records_ + insert_records_，按访问模式（has_write / has_read）分两个集合。

为什么这两个集合就够？因为 CREST 的 Txn 在执行过程中已经把所有触达的 record 都登记到 selected_records_（读出来的、改过的）或 insert_records_（插入的），事务终结时这两个集合就是完整 footprint。不需要在热路径插钩，事务结束时一次性导出即可。

代价分析（也写在 Txn.cc:266-269 注释里）：

开销：2 次 cache pass 遍历 selected_records_ + insert_records_
      1 次 std::vector<key_group_id_t> 分配
      1 次 RecordTxnFinish 内部 mutex acquire

频率：1 / txn，不在 per-record hot loop 上

钩点	信息覆盖	频率	是否看到读	是否看到事务边界
TxnIO.acquire (W13 之前)	单写锁事件	per-record	❌	❌（需要 thread_local 追踪）
Txn.Commit / Abort (W13)	完整 footprint	per-txn	✅	✅

🌟 结论：事务级钩点天然带”事务边界”和”读写区分”两条关键信息，而它的频率比单事件钩点低一个数量级（事务里平均 ~10 条 record，所以 per-txn 钩比 per-record 钩省 10×）。免费提升信息密度，没有理由不换。

---

5. 采样队列踩坑 —— thread_local batch 与 1000-txn 闸门

写到这里你可能已经注意到一个细节：RecordTxnFinish 内部用了一把全局 mutex。

// AuraControlLoop.cc:136-139
{
    std::lock_guard<std::mutex> lk(edge_pending_mtx_);
    edge_pending_.push_back(std::move(sample));
}

第 5 章讲 trace 设计的时候提过一个性能优化模式：thread_local batch + 周期 flush——每条工作线程维护一个 thread_local 缓冲区，攒到 64 个样本再一次性进全局队列，把 mutex 频率从 per-event 降到 per-batch。这是个看上去稳赚的优化。

W13 的初版（v1）就是这么做的。结果在 1000-txn 的 W13 闸门测试里跑出了一个看不懂的结果：访问图边数始终 < 100，明显远低于预期。

排查过程：

1. Print 一行：RecordTxnFinish 每次被调用都计数 ——
   显示 1000 次（OK）
2. Print 一行：edge_pending_ 在 Tick 里被 drain 的样本数 ——
   显示 50-80 次（异常）
3. 检查 thread_local 缓冲区：发现 4 条工作线程 × 单线程
   平均累积 ~12 个样本就被 1000-txn 闸门捞走（gracefully
   exited），它们的 thread_local buffer 永远没有 flush
   到全局队列。

🧠 关键洞察：1000-txn 是闸门，不是 batch 整数倍。如果一个工作线程在 buffer 攒到 64 之前事务总数就已经满 1000，剩下 12-50 个样本永远进不了全局队列。控制线程没有任何办法看到其他线程的 thread_local 状态——这是 thread_local 的语言学约束。

修复（v2，也就是当前代码）：把 thread_local batch 拆掉，每个 RecordTxnFinish 调用直接进全局 mutex。代价是 mutex 频率从 per-batch 升到 per-txn——但 RecordTxnFinish 跑在事务终结路径（每秒 ~100K 次 / 工作线程），不是 per-record（每秒 ~1M 次 / 工作线程），频率本来就低一个量级，mutex 开销可以接受。

代码里的注释把这个权衡写得很白：

// AuraControlLoop.h:87-90
// V2 deliberately skips thread_local batching (the 1000-txn W13
// gate would lose tail samples since the control thread cannot
// drain other workers' thread-local buffers). Each call takes
// pending_mtx_ once. Optimise later if profiling shows it.

⭕ 这条踩坑的可推广教训：任何”控制线程依赖工作线程产生数据”的设计，都要先想清楚『控制线程怎么强制 flush 工作线程的本地缓冲』。在用户态线程模型下，控制线程做不到这件事——除非引入 RCU 风格的 quiescent state 或者跨线程的 epoch 屏障。绝大多数场景下，不要 batch，老老实实走 mutex 反而是正确选择。

如果未来 profiling 显示 mutex 真的成了瓶颈（W13 落地后没出现），可选的演进方向：

方案	复杂度	适合的瓶颈类型
lock-free MPMC queue（boost::lockfree、moodycamel）	中	mutex contention 真实可测
per-thread ring buffer + 控制线程主动遍历	高	跨平台无 lockfree、但能接受复杂度
double-buffer with seqlock（写线程写当前 buffer，控制线程 swap）	中	控制线程节奏稳定（5ms tick）

但前提是 profile 数据先证明 mutex 是瓶颈，不要做盲优化——这正是 W13 v1 撞坑的根因。

---

6. merge_score = C_ww + α · C_wr —— α=0.3 的物理意义

到这里 typed edges 已经准备好了。下一步是 W14 把三类边喂给 CohortGenerator 做合并。CohortGenerator 把两种”会驱动 merge”的边权融合成单一标量：

// CohortGenerator.cc:105-115
absl::flat_hash_map<EdgeKey, double, EdgeKeyHash> combined;
combined.reserve(edge_ww.size() + edge_wr.size());
for (const auto& [k, w] : edge_ww) {
    combined[k] += w;
}
for (const auto& [k, w] : edge_wr) {
    combined[k] += merge_alpha_wr * w;       // α × C_wr
}
for (const auto& [k, w] : combined) {
    try_push(k.a, k.b, w);
}

默认 merge_alpha_wr = 0.3（CohortGenerator.h:96）。

α 怎么选？这是 W13 这条线最容易”凭直觉拍脑袋”的地方，下面给出一个能在白板上推导的理由。

Step 1：先定上下界

• α = 0：完全忽略 C_wr，cohort 只按 C_ww 驱动。问题：write set 小、但与 write set 邻近的 read set 大的 KG 永远不会被划进同一 cohort，C_wr 那条 prefetch / 读副本受益全丢。
• α = 1：把 C_wr 与 C_ww 同等看待。问题：见 §1 的反例——Warehouse↔District 这种”读边”会被加权到和真实锁竞争边一样的水平，cohort 边界跑偏。

所以 α ∈ (0, 1) 之间，且应该明显小于 1。

Step 2：用物理意义定锚点

一条 C_ww 边代表”一次 atomic CAS 的可节省”——把这两个 KG 划进同一 cohort，每次两笔事务并发，本地化能省一次跨 CN 的 RDMA atomic（~3µs）。

一条 C_wr 边代表”一次 RDMA READ 的可节省”——把它们划进同一 cohort，写锁本地化的同时，读路径可以走本地副本，省一次 RDMA READ（~1µs）。

所以一条 C_wr 边的”价值”大致是一条 C_ww 边的 1µs / 3µs ≈ 0.33。

Step 3：用 0.3 而不是 0.33

0.3 是 0.33 的”保守版本”——略低于物理意义算出来的比例，让 cohort merge 在 read-only 共访很重的边界场景更稳一点（宁可漏并、不可错并）。

🌟 结论：α=0.3 不是经验拍脑袋，是 “C_wr 边的可节省成本 / C_ww 边的可节省成本 ≈ 1µs / 3µs ≈ 0.33” 的下舍入。任何换硬件平台的工作（比如 ConnectX-3 atomic 性能 vs READ 性能比例不同）都应该重算这个比值。

下表给一个换硬件后的快速估算法：

硬件	atomic 单次延迟	READ 单次延迟	C_wr/C_ww 比例	推荐 α
ConnectX-6 Dx (AURA 实测)	~3µs	~1µs	0.33	0.30
ConnectX-5 (CREST baseline)	~3.5µs	~1.2µs	0.34	0.30
ConnectX-3 (LOTUS baseline)	~9µs	~3µs	0.33	0.30
假设的全 host-CAS 平台	~50ns	~1µs	20×	完全反转，建议重新设计

⭐ 第 4 列大致都是 0.3-0.34 —— 这不是巧合，是 RDMA 原语之间的相对延迟比例在 ConnectX 系列里相当稳定。所以 α=0.3 在主流 ConnectX 硬件上都能直接复用。

---

7. W13 落地后的 ablation 不动 —— 这是 bug 还是 feature

W13 的实现完成后，跑 4-CN W=4 的 ablation 矩阵，结果非常诚实：

配置	4-CN W=4 聚合 commit (KOPS, 中位数)	vs baseline
baseline (CREST 原版)	185.24	—
baseline + W13 (typed edges 开，cohort plan 关)	185.10 ± 0.5	−0.07%（噪声内）

W13 单独上线，ablation 不动。第一次看到这个数有点反直觉——花了几百行代码、修了 thread_local 踩坑、推导了 EDGE_DECAY 半衰期，结果什么收益都没有？

🧠 这是 feature 不是 bug。W13 的产出是typed access graph这个数据结构，它本身不驱动任何运行时变化：

W13 上线：
  edge_pending_ 队列里有样本进来   ✅
  edge_ww_ / edge_wr_ / edge_rr_ 在 Tick 里被填充   ✅
  EDGE_DECAY 让边权随时间衰减   ✅
  但是 ——
  没有任何代码读 edge_ww_ 去做决策   ❌
  cohort plan 还是走 W8.5 hash_det 的老路（kg % num_cns）
  OwnerLockTable 还是按老 cohort 集合工作

W13 是给 W14 cohort merge 准备的输入数据结构。单 W13 上线相当于”建了一座漂亮的图书馆但还没有读者来”——书都在书架上，但没人翻它。

⭕ 写论文 §3.3 的时候，如果只把 W13 当作一个能跑的功能模块来摆 ablation 行，会让审稿人觉得”你这一条没用啊”。正确的表达是把 W13 + W14 合并成一个 ablation 行，标注”access graph (W13) + cohort merge (W14)“——这是一个最小可观测改动单元，单独跑 W13 没有 observable 效果是符合设计预期的。

这也对应模块十五第 8 章「实验方法论」§4 提到的原则：每个 ablation 行必须对应一个独立 claim。W13 单独没有 claim 可以挂；它必须和 W14 一起出现才有意义。

🌟 结论一句话：W13 的价值不在 ablation 数字里，而在”为后续所有 cohort 决策提供语义清晰的输入”。这条信息流上去之后，W14 才能做出『让 +1.06% 站得住脚』的 cohort 划分；W18 才能做出『跨 CN 共识的 owner 计算』。它是地基，不是上层建筑。

⭐ W14 的故事——cohort merge 的稳定性陷阱，以及”为什么 1229 个 cohorts + 100% inheritance + LOCAL hit 反而崩到 0.30%“——见下一章。

---

✅ 自我检验清单

• 单边图歧义：能用 TPC-C NewOrder 的具体 footprint 举例，说明为什么把”两个写”和”一写一读”用同一条边权刻画会让 cohort merge 跑偏。
• typed edges：能徒手列出 C_ww / C_wr / C_rr 的触发条件、物理含义、以及在 cohort merge 里的角色（主驱动 / 次要 / stats-only）。
• EDGE_DECAY 半衰期：知道 EDGE_DECAY=0.99 + tick=5ms 推出的半衰期 ≈ 345ms；能解释为什么边衰减比单 KG 衰减慢一个量级（二项 fanout / 边的命中频率比顶点稀疏 K 倍）。
• 钩点选择：能说出为什么把钩点从 TxnIO.acquire 改到 Txn.Commit / Abort 是免费收益——前者只看写、不知道事务边界；后者两条信息都自带。
• thread_local 踩坑：能解释为什么 1000-txn 的 W13 闸门下 thread_local batch=64 会丢尾——根因是控制线程拿不到工作线程的 thread_local 状态；推论是”任何依赖工作线程产生数据的控制路径都不要用 thread_local batch”。
• α=0.3 的物理含义：能在白板上推出 α ≈ READ 延迟 / atomic 延迟 ≈ 1µs/3µs，并解释换硬件后如何重算（ConnectX-3 / 5 / 6 比例稳定，host-CAS 平台需要重新设计）。
• W13 单 ablation 不动的解释：知道这是”地基模块”特征——访问图本身不驱动运行时改变，必须和 W14 一起出现。ablation 行应该合并标注 “access graph + cohort merge”。

---

📚 参考资料

概念入门

• CREST 论文 —— USENIX FAST 2025：Disaggregated-Memory Transactional Systems and the Atomic-IOPS Wall (CREST)，CREST 把 OCC + RDMA single-sided 的”原版”形态固化下来，是 AURA 注入点的基线。
• LOTUS 论文 —— USENIX ATC 2024：CN-side critical-field 锁的设计起点，AURA 在 §3.3 的访问图模型是 LOTUS critical-field 的”动态化版本”——LOTUS 假设 schema 静态指定，AURA 用 typed edges 在线推导。

关键论文

• AURA paper (2026)：本仓库 paper_lock_ownership_atc_en/sections/3_design.tex §3.3。typed edges 的形式化定义、edge fanout 与采样率的 N² 推导、α 的物理解释均出于此章。
• “Affinity Propagation: Sample Complexity and Stability”（Frey & Dueck, 2007, Science）：访问图驱动聚类的早期工作，对”边权衰减系数 / 半衰期”的工程化设定有方法论参考价值。

行业讨论

• Mellanox / NVIDIA RDMA Programming Manual —— 第 4 章 Atomic Operations：原子操作的硬件限制 + 跨硬件版本性能差异，是 α 表格里 ConnectX-3/5/6 比例稳定性的依据。
• “Why thread_local Defeats You” —— Bryce Lelbach (CppCon 2018)：thread_local 在跨线程数据流上的语义限制，对应本章 §5 的踩坑根因。

框架文档

• CREST 实现：本仓库 CREST-aura-impl/CREST-Opensource-0007/src/transaction/aura/AuraControlLoop.{h,cc}、CohortGenerator.{h,cc}、Txn.cc 的 AuraRecordTxnFinish——本章所有代码引用均可在这些文件里找到完整上下文。
• abseil-cpp absl::flat_hash_map 官方文档：abseil.io/docs/cpp/guides/container，typed edges 三张 hash map 的容器选型理由（flat 比 node 在小 value、大量插入场景上快 1.5–2×）。