跳到主要内容
分离式事务的动态锁所有权

第5章：在线学习与 cohort 划分 —— 从访问图到 cohort 边界

拆解 AURA 的 AccessGraphProfiler / LockCohortGenerator / OwnershipPlanner 三件套：访问图怎么建、cohort 怎么 merge/split、owner 怎么放、滞回如何防抖动

AURA AccessGraph cohort online learning owner placement 滞回

第 4 章把 AURA 骨架立住了，但留下了一个核心问题：cohort 边界是怎么决定的、owner 是怎么选出来的。本章拆解 AURA 控制面的三件套——AccessGraphProfiler 在线建图、LockCohortGenerator 决定 merge/split、OwnershipPlanner 决定 owner 位置。读完你应该能写一个简化版 cohort 学习器的伪代码，并能解释为什么”加滞回比 PID 更好”——这是真实工程经验，论文里只能写一两句。

📑 目录

1. AccessGraph：边权与节点权的物理含义

1.1 图模型定义

AccessGraph G=(V,E,w)G = (V, E, w)：

  • VV：节点 = key_group（不是单 key，避免图爆炸）
  • EE：边 = 共访问关系
  • ww：边权 = 共访问频率（衰减后）+ 节点权 = 单点访问频率
   节点（key_group）          边（共访问）
   ─────────────────         ─────────────────
   • kg₁: warehouse[wid=1]     kg₁ ─ kg₂ : weight=120
   • kg₂: district[wid=1,*]    kg₁ ─ kg₃ : weight=85
   • kg₃: customer[wid=1,*]    kg₂ ─ kg₃ : weight=200
   • kg₄: stock[wid=1,*]       kg₃ ─ kg₄ : weight=150
   • kg₅: warehouse[wid=2]     kg₅ ─ kg₆ : weight=98
   • kg₆: district[wid=2,*]    ...

1.2 节点权与边权的物理含义

量物理含义用途
节点权 w(v)w(v)该 key_group 在窗口内被独立访问的次数决定该 cohort 的”热度”，影响 owner CPU 负载
边权 w(u,v)w(u,v)该对 key_group 在同一事务内同时被访问的次数决定它们是否应该在同一 cohort

🌟 核心原则：应该聚簇的 = 边权高 / 节点权也高——既经常被一起访问，又访问量大。低热度即使强相关也不值得做 cohort。

1.3 为什么用普通图而不是超边

超边（hyperedge）能更精确表示”3 个 key_group 同时被访问”，但：

维度普通图（pairwise）超图（hyperedge）
表达力两两关系任意子集关系
计算复杂度O(|V|²)O(2^|V|)
在线维护容易难
聚类算法成熟度Louvain / spectral 都 OK限于研究阶段

🍎 直觉比喻：超图是”完美但慢”，普通图是”够用且快”——AURA 用普通图配合周期性精化（spectral re-clustering）。

1.4 AccessGraph 的物理存储

struct AccessGraphNode {
    key_group_id_t  id;
    double          weight;          // 衰减后的节点权
    uint64_t        last_update_ts;  // 最近一次更新时间戳
};

struct AccessGraphEdge {
    key_group_id_t  u, v;
    double          weight;
    uint64_t        last_update_ts;
};

class AccessGraph {
    std::unordered_map<key_group_id_t, AccessGraphNode>           nodes_;
    std::unordered_map<KGPair, AccessGraphEdge, KGPairHash>       edges_;
    DecayConfig                                                    decay_;
};

1.5 5ms 窗口够用、1ms 太抖

为什么是 5ms？这是工程权衡：

窗口优点缺点
1ms跟得上漂移噪声大，单 ms 内只有 ~1k–10k samples
5ms平衡是 AURA 默认
10ms噪声小漂移检测延迟
100ms决策稳定LOTUS 风格，错过快漂移

🧠 关键洞察：5ms 窗口让单窗口 sample 数 ≈ 1 万级——足够用统计意义但又不至于错过快漂移。第 7 章会用频谱分析进一步论证。

2. 采样与衰减：trace 不能无限堆

2.1 为什么不能记录所有 trace

假设每秒 1 M 事务，每个事务平均访问 10 个 key_group：

  • 每秒边事件：10 × 10 = 100 M / s
  • 每边记录 16B → 1.6 GB/s 写入
  • 一小时 5.7 TB

直接写完全不可行。必须用采样 + 衰减。

2.2 Reservoir sampling

经典 reservoir sampling：以 kn\frac{k}{n} 概率保留每个 sample，最终保持 size = kk 的均匀样本：

class ReservoirSampler:
    def __init__(self, k):
        self.k = k
        self.reservoir = []
        self.n = 0
    
    def add(self, item):
        self.n += 1
        if len(self.reservoir) < self.k:
            self.reservoir.append(item)
        else:
            j = random.randint(0, self.n - 1)
            if j < self.k:
                self.reservoir[j] = item

⭕ 互补：reservoir 保证均匀性但对最近事件不偏置——AURA 想”记住最近”，所以加衰减。

2.3 指数衰减：让旧 trace 自然消失

class DecayingCounter:
    def __init__(self, half_life_ms=5):
        self.value = 0.0
        self.last_update = now_ms()
        self.tau = half_life_ms / math.log(2)
    
    def add(self, x=1.0):
        elapsed = now_ms() - self.last_update
        self.value *= math.exp(-elapsed / self.tau)
        self.value += x
        self.last_update = now_ms()
    
    def read(self):
        elapsed = now_ms() - self.last_update
        return self.value * math.exp(-elapsed / self.tau)

🌟 关键性质：每个边权与节点权都用 DecayingCounter——5ms 半衰期意味着 25ms 前的 trace 权重已经降到 1/32。自然遗忘。

2.4 CN 侧 0.5–2% CPU 占用怎么来的

实测分解（c6525, TPC-C, 1M tps）：

项目CPU 占用
TraceCollector record()~0.3%
AccessGraph update（hash + 衰减）~0.5%
周期性 graph snapshot（5ms 一次）~0.4%
OwnerMap delta apply~0.2%
合计~1.4%

⭕ 互补：1.4% 不算什么，但热路径上每个事务只能花 ~10ns 在 trace——必须 hash + atomic add，不能上 lock。

2.5 Sketch 数据结构作为节省方案

更激进的做法：用 Count-Min Sketch 而不是精确边权：

方案内存精度
精确 hashmap1000 cohort × ~10 邻居 = 10000 entries × 16B = 160KB100%
Count-Min Sketch (4 hash × 4096 bucket)64KB概率性

AURA 默认精确（cohort 数不算多），但可选 Sketch 模式应对 cohort 爆炸。

3. cohort 边界决策：merge / split 触发条件

3.1 LockCohortGenerator 的工作流

   每 5ms 一次：
   ──────────────
   1. 取 AccessGraph snapshot
   2. 与上一窗口比 → diff
   3. 对每对相邻 cohort 计算"是否应该 merge"
   4. 对每个 cohort 计算"是否应该 split"
   5. 输出 merge/split deltas → OwnershipPlanner

3.2 merge 决策

触发条件：

  应当 merge(C1, C2) ⟺
      crossEdgeWeight(C1, C2) >= θ_merge × min(intraWeight(C1), intraWeight(C2))
      AND 持续 N=2 个窗口
      AND combinedSize(C1, C2) <= max_cohort_size
参数经验值解释
θ_merge0.6跨 cohort 边权达到内部 60% 才 merge
N2至少 2 个窗口稳定
max_cohort_size~500 key_group单 cohort 上限

🍎 直觉比喻：两个 cohort 之间”有 60% 的连线像他们内部一样紧密”才算”该合并”——避免噪声触发。

3.3 split 决策

触发条件：

  应当 split(C) ⟺
      存在 cut 使得 cutWeight / intraWeight <= θ_split
      AND 切后 |C1|, |C2| >= min_cohort_size
      AND 当前 owner 命中率 < θ_local OR 总热度 > 2 × peer_avg
参数经验值解释
θ_split0.2找到一个切口，让被切边权只占内部 20%
min_cohort_size5切完每个子 cohort 至少 5 key_group
θ_local0.7owner 命中率掉到 70% 以下时考虑切

3.4 找最优 cut：贪心而不是最大流

理论上找最优 cut 是 NP-hard（min-cut 在普通图上 P 但 weighted balanced cut 是 NPH）。AURA 用贪心：

def greedy_cut(cohort, graph):
    # 按节点权降序排
    sorted_kgs = sorted(cohort.members, key=lambda kg: -graph.node_weight(kg))
    # 用 weighted modularity 局部最优
    best_partition = None
    best_score = -inf
    for seed in sorted_kgs[:10]:  # 试 10 个种子
        part = grow_partition(seed, cohort, graph)
        score = modularity(part)
        if score > best_score:
            best_score = score
            best_partition = part
    return best_partition

⭐ 关键事实：贪心精度 ~85%（vs 最优），但耗时 ~50µs（vs 最优 ~10ms）。5ms 窗口下贪心是唯一选择。

3.5 滞回参数（hysteresis）

注意上面的 θ_merge / θ_split 都是单值，但实际工程中需要滞回带：

   θ_merge_low = 0.55, θ_merge_high = 0.65
   θ_split_low = 0.15, θ_split_high = 0.25

逻辑：

  • 不在合并状态 → 边权升到 0.65 才触发 merge
  • 已在合并状态 → 边权掉到 0.55 才回退

⭕ 避免：θ_merge=0.6 单值时，边权在 0.59–0.61 之间抖动会反复 merge/unmerge——OwnerMap 抖动 → AffinityRouter 命中率掉。

4. OwnershipPlanner：owner 放哪里

4.1 成本函数

  cost(cohort, owner_cn) =
      α × expected_atomic_offload      (越多越好，负号)
    - β × migration_cost                (一次性迁移 RDMA + drain 代价)
    - γ × cross_cohort_rpc_cost         (该 cohort 与其他 cohort 的预期 RPC 数)
    - δ × cn_load_imbalance             (该 CN 已经持有的 cohort 数)
    + ε × stickiness                    (不变 cohort 给 ε 奖励，避免抖动)
参数经验值物理含义
α1.0主目标：减 atomic
β0.3迁移成本权重
γ0.5跨 RPC 惩罚
δ0.1fairness
ε0.2sticky bias

4.2 用贪心 + local search 而不是 ILP

方案复杂度决策时间5ms 内能算几次
ILP（最优）NP-hard100ms+0
贪心 + local searchO(|cohort| × |CN|)~500µs10
周期性 spectral re-clusteringO(|graph|³)数 s（异步运行）0（异步）

AURA 默认贪心 + 每 1 秒做一次 spectral 矫正。

4.3 约束：CN 容量上限 + fairness

struct CnCapacity {
    cn_id_t  cn;
    uint32_t max_cohorts;          // 硬上限
    uint32_t max_lock_qps;          // 锁请求 QPS 上限
    double   current_cpu_pct;       // 实时 CPU 利用率
};

bool can_assign(cohort, cn) {
    return cn.current_cohorts < cn.max_cohorts
        && cn.expected_qps + cohort.qps < cn.max_lock_qps
        && cn.current_cpu_pct < 0.8;
}

🌟 fairness 重要性：owner CN 自己也会成为热点。如果一个 CN 持有 80% cohort，它就变成新瓶颈——退化到”集中式 owner”，相当于把 atomic 瓶颈搬到 CN 自己。

4.4 placement 决策伪代码

def plan_ownership(cohorts, cns, graph, prev_map):
    new_map = OwnerMap()
    pending = sorted(cohorts, key=lambda c: -c.weight)
    for c in pending:
        # 候选 = 该 cohort 内 key_group 当前最常被访问的 CN
        candidates = top_k_cns_by_access(c, k=3)
        best_cn, best_cost = None, inf
        for cn in candidates:
            if not can_assign(c, cn):
                continue
            cost = compute_cost(c, cn, graph, prev_map)
            if cost < best_cost:
                best_cost, best_cn = cost, cn
        if best_cn:
            new_map[c] = best_cn
        else:
            new_map[c] = FALLBACK
    return new_map

5. 防抖动：滞回 + 冷却窗口

5.1 抖动来源

来源表现
短时 burst1ms 内访问突增 → cohort 误升温
GC pauseCN 短暂不响应 → 误认为故障
NIC counter 周期对齐多 CN 计数同时刷新 → 假漂移
sample 噪声5ms 内 sample 数小，方差大

5.2 滞回带宽度估算

经验公式：

hysteresis_width=2×σnoise\text{hysteresis\_width} = 2 \times \sigma_{\text{noise}}

其中 σnoise\sigma_{\text{noise}} 是单窗口 sample 的标准差。实测：

  • TPC-C 1M tps，5ms 窗口 → σ ≈ 0.05（边权相对值）
  • 推荐滞回带宽 ≈ 0.10

5.3 冷却窗口（cooldown）

在迁移完成后强制最小 100ms 不再迁移同一 cohort：

class MigrationCooldown {
    std::unordered_map<cohort_id_t, uint64_t> last_migrate_ts_;
    
    bool can_migrate(cohort_id_t c) {
        auto it = last_migrate_ts_.find(c);
        if (it == last_migrate_ts_.end()) return true;
        return now_ms() - it->second > 100;
    }
};

⭐ 设计原则：迁移成本 ~150–350µs，太频繁迁移成本累积起来吃光收益。100ms 冷却窗口 = 至多 10 次/秒 → 1.5–3.5ms/s 在迁移——可接受。

5.4 抖动检测：当滞回不够时

如果滞回 + 冷却仍然抖动（实测中可能发生），AURA 有两道补救：

  1. 频率检测：cohort 在 1 秒内 merge/split > 3 次 → 强制锁定 cohort 状态 5 秒
  2. 进入”研究模式”：输出 detailed log，下个 epoch 起调高滞回带宽

🧠 关键洞察：任何在线学习系统都需要”知道自己学不动”的 fallback——AURA 的研究模式就是这个角色。

5.5 PID 控制 vs 滞回的工程对比

方案优点缺点
PID 控制理论上有最优响应调参困难，对噪声敏感
滞回 + 冷却简单、鲁棒调整迟缓

⭕ 互补：AURA 选滞回不是因为它更”先进”，而是因为易调试 + 可解释。生产系统更重要的是工程师能看懂控制逻辑，而不是数学最优。

6. 一段简化版伪代码

6.1 主循环

class AuraControlLoop:
    def __init__(self):
        self.profiler = AccessGraphProfiler(window_ms=5)
        self.generator = LockCohortGenerator(merge_low=0.55, merge_high=0.65)
        self.planner = OwnershipPlanner(alpha=1.0, beta=0.3, gamma=0.5)
        self.cooldown = MigrationCooldown(min_ms=100)
        self.transfer = TransferController()
        self.publisher = OwnerMapPublisher()
        
        self.current_map = OwnerMap()
    
    def tick(self):  # 每 5ms 调用一次
        # ❶ 取 trace snapshot
        graph = self.profiler.snapshot()
        
        # ❷ 决定 cohort 边界变化
        cohort_deltas = self.generator.diff(graph, self.current_map.cohorts)
        
        # ❸ 决定 owner placement
        new_map = self.planner.solve(graph, cohort_deltas, self.current_map)
        
        # ❹ 过滤掉冷却窗口内的迁移
        filtered_deltas = []
        for delta in new_map.diff(self.current_map):
            if self.cooldown.can_migrate(delta.cohort_id):
                filtered_deltas.append(delta)
        
        if not filtered_deltas:
            return
        
        # ❺ 执行 4 阶段迁移协议
        self.transfer.apply(filtered_deltas)
        
        # ❻ 发布新 OwnerMap
        new_epoch = self.publisher.publish(new_map)
        
        # ❼ 记录冷却时间戳
        for d in filtered_deltas:
            self.cooldown.mark(d.cohort_id)
        
        self.current_map = new_map

6.2 一个完整迭代示例

   t=0ms   profiler.snapshot() → 1024 nodes, 8742 edges
           generator.diff()    → 3 merges, 2 splits
           planner.solve()     → 5 owner changes
           cooldown.filter()   → 4 changes (1 在冷却中)
           transfer.apply()    → 4 个 4-phase migration 并行
   t=0.3ms 4 个 transition → TRANSFERRING
   t=0.5ms drain done
   t=0.6ms handoff done
   t=0.7ms publish epoch=42
   t=5ms   下一轮 tick

🌟 关键事实：单轮决策 ~700µs（含迁移），剩 ~4.3ms 给数据面跑事务——控制面不抢数据面 CPU。

6.3 这段代码的工程注意点

点注意
profiler.snapshot()必须无锁（用 RCU 或 epoch-based GC）
generator.diff()比较成本高时只对 hot cohort 做
planner.solve()最坏 ~500µs，超时则 reuse 上轮决策
transfer.apply()必须串行化 cohort（同一 cohort 不能并发迁两次）
publisher.publish()atomic CAS 推 epoch，失败重试

7. 与 LOTUS critical field 的对比

7.1 一个具体 TPC-C cross-table 场景

考虑 NewOrder 同时访问 7 张表的场景：

方案cohort 怎么定义atomic offload 比例
LOTUS（critical field=wid）各表按 wid hash → 不同表的 wid=1 在不同 owner0%（cross-table 无法 offload）
LOTUS（critical field=wid+表名 复合）复杂，需要应用知道每张表的”wid 字段名”复杂度爆炸
AURA自动识别 wid=1 的所有相关行 → 同 cohort~95%

🌟 结论：AURA 在 cross-table 场景下相比 LOTUS 是数量级优势——LOTUS 的 critical field 模型本质上是单表的，跨表必须应用层手工拼。

7.2 在线学的好处不止于此

场景LOTUSAURA
schema 变更应用必须重新声明 critical field自动重新学
临时 hot key（如黑五）反应式 100ms5ms 适应
多 tenant 共享集群必须按 tenant 切自动按 tenant 聚簇（如果访问图分明）
索引选择影响访问 patternLOTUS 假设失效AURA 自适应

7.3 AURA 的弱点：profile 开销 + 不完美 cohort

⭕ 互补：AURA 不完美：

  • 在 critical field 已知 + 稳定的工作负载下，AURA 比 LOTUS 慢 0–3%（profile 开销 + 不完美 cohort）
  • 在 cohort 数量爆炸（>10k）时，OwnerMap 可能撑爆 AffinityRouter 缓存
  • 在跨 cohort 比例高（>50%）时退化到 routing-only

🌟 诚实的话：AURA 适用面大，但不是无敌。第 8 章会展开如何把这些边界做成 negative regime 实验。

✅ 自我检验清单

  • AccessGraph：能解释为什么用普通图而不是超边
  • 节点权 vs 边权：能区分两者的物理含义
  • 采样与衰减：能写一个 reservoir + 指数衰减的伪代码
  • CPU 占用 1.4% 怎么来：能列出至少 3 个开销项
  • merge/split：能列出至少 3 种触发条件和对应滞回参数
  • 贪心 cut：能解释为什么不用 ILP（5ms 窗口约束）
  • OwnershipPlanner 成本函数：能写出至少 4 项的成本函数
  • fairness 约束：能解释为什么 owner CN 自己也可能成为瓶颈
  • 滞回带宽：能用 σ_noise 公式估算合理宽度
  • 冷却窗口：能解释 100ms 与迁移成本的数学关系
  • PID vs 滞回：能解释为什么生产系统选滞回
  • TPC-C cross-table：能用具体例子说明 AURA 在 LOTUS 上的优势
  • AURA 的 3 个弱点：能列出至少 3 个 AURA 不完美的场景

📚 参考资料

概念入门

  • Reservoir Sampling：Wikipedia
  • Count-Min Sketch (Cormode & Muthukrishnan, 2005) —— 替代精确 hashmap 的方案

关键论文

  • MorphoSys (et al., VLDB’21) —— 物理设计在线学习的代价模型设计参考
  • Lion (et al., 2024) —— 访问图驱动 partition 重排的 prior art
  • Louvain Community Detection (Blondel et al., 2008) —— 经典图聚类算法
  • Spectral Clustering (Ng, Jordan, Weiss, NeurIPS’01) —— AURA 周期性矫正用的算法

行业讨论

  • Hysteresis in Control Systems —— 经典控制论教科书章节
  • AURA 论文 §3.3 / §4 —— 在线学习与 owner placement 的详细描述

框架文档

  • CREST 仓库 txn/scheduler/ —— 路由实现参考
  • 本仓库 caesar/ 项目早期 AccessGraph 原型