第 12 章：十二大核心技术挑战——分布式数据库的”终极 Boss”

难度评级（基于源码复杂度和理论深度）：

  ★★★★★ 极难（涉及分布式理论根本限制）
  ├── 1. 分布式事务一致性
  ├── 4. 全局时钟与因果序
  └── 6. 共识协议工程化

  ★★★★☆ 困难（需要大量工程权衡）
  ├── 2. 分布式查询优化
  ├── 3. 数据分片与再均衡
  ├── 5. HTAP 双引擎隔离
  ├── 7. 分布式 DDL
  ├── 9. SQL 兼容性完整度
  ├── 10. 故障检测与自动恢复
  └── 12. 全局死锁检测

  ★★★☆☆ 中等（成熟方案可借鉴）
  ├── 8. 连接管理与执行调度
  └── 11. 多租户隔离

CockroachDB：Parallel Commits
  传统 2PC 需要两轮 RTT（prepare + commit）
  → 把 commit 决策与最后一批写并行发出
  → 一轮 RTT 完成事务
  → 用 TLA+ 数学证明正确性
  源码：docs/tla-plus/ParallelCommits/ParallelCommits.tla

TiDB：Percolator 协议
  基于 Google Percolator 论文
  → 用 TiKV 的 MVCC + 锁机制实现 2PC
  → 通过 PD 分配全局时间戳保证一致性
  
OpenTenBase：GTM 中心化
  所有事务 ID 和快照由 GTM 统一分配
  → 简化了一致性保证
  → 但 GTM 成为性能瓶颈
  源码：src/gtm/main/gtm_txn.c（4029 行）

Vitess：不提供分布式事务
  → 一致性由应用层负责
  → 最简单但对开发者要求最高

TiDB：Cascades 框架（最完整的开源实现）
  源码：pkg/planner/cascades/cascades.go
  - Memo 存储等价执行计划
  - 规则引擎驱动搜索
  - 40+ 优化规则
  - 同时评估 TiKV 和 TiFlash 路径

Citus：五层渐进式（最优雅的工程设计）
  源码：planner/README.md
  Layer 1: Fast-path Router → 单分片快路径
  Layer 2: Router Planner → 协同分片路由
  Layer 3: Modification Planning → DML 专用
  Layer 4: Recursive Planning → 子查询递归
  Layer 5: Logical Planner → 多关系代数树
  命中即停，大部分 OLTP 查询在前两层解决

CockroachDB：基于代价的优化器（CBO）
  Cascades 风格，与 Pebble 存储紧密集成
  DistSQL 执行引擎支持跨节点并行执行

OpenTenBase：pgxcship 可下推判断
  源码：src/backend/optimizer/util/pgxcship.c
  判断查询能否整条下推到单个 Datanode
  能下推 → 直接发送（接近单机性能）
  不能 → 走分布式执行计划

CockroachDB：Range 自动分裂 + Raft Learner 迁移
  源码：pkg/kv/kvserver/split_queue.go
  - load_based_splitter.go 选择最优分裂点
  - 先创建 Learner 副本同步数据
  - 数据追上后原子切换
  对客户端完全透明

Vitess：VReplication
  源码：go/vt/wrangler/resharder.go
  - 后台复制数据到新分片
  - 切换流量时原子更新路由规则
  - 支持在线 resharding

TiDB：Region 分裂 + PD 调度
  PD（Placement Driver）自动检测热点 Region
  → 分裂热点 Region
  → 迁移 Region 到负载较轻的节点

OpenTenBase：静态分片
  建表时指定 DISTRIBUTE BY HASH(col)
  分片数量和策略相对固定
  在线再均衡能力有限 → 贡献方向

方案 A：TrueTime（Google Spanner）
  用 GPS + 原子钟提供高精度物理时间
  误差 ~7μs
  代价：需要专用硬件，成本极高
  开源世界无人使用（硬件要求太高）

方案 B：TSO（TiDB）
  中心化的时间戳分配器（PD 组件）
  精度：逻辑递增，绝对精确
  代价：PD 是单点，吞吐量有上限
  源码：TiDB 的 PD server

方案 C：HLC（CockroachDB、YugabyteDB）
  混合逻辑时钟 = 物理时钟 + 逻辑计数器
  精度：依赖 NTP（通常 < 250ms 偏差）
  代价：不确定窗口内可能读到过期数据
  无需中心化组件、无需专用硬件

TiDB（物理隔离，最佳方案）：
  TiKV(行存) ──Raft Learner──► TiFlash(列存)
  不同进程、可以在不同机器上
  AP 查询不影响 TP 延迟
  代价：架构复杂，运维两套存储

OpenTenBase（逻辑隔离）：
  行存 + 列存 在同一个 Datanode 进程中
  简单，但高负载下可能资源竞争

Citus（可选列存）：
  ALTER TABLE ... USING columnar;
  表级别选择存储格式
  不是真正的 HTAP，更像是分析友好的存储选项

CockroachDB / YugabyteDB：
  只有行存，OLAP 能力有限

源码：pkg/raft/（fork 自 etcd Raft，深度修改）

三大创新：

1. StoreLiveness（替代传统心跳）
   传统：leader 定期发心跳，follower 超时则选新 leader
   问题：网络抖动导致不必要的选举风暴
   StoreLiveness：不仅检测节点在线，还评估存储层健康状态
   源码：pkg/raft/raftstoreliveness/

2. Fortification（防止不必要的选举）
   当 leader 确认与所有 follower 的连接都健康时
   → follower 承诺不会发起选举
   → 减少选举风暴
   源码：tracker/fortificationtracker.go

3. 异步存储写入（Asynchronous Storage Writes）
   传统：leader 必须先把日志写入本地磁盘，再发给 follower
   优化：leader 与 follower 并行写入磁盘
   → 减少一次磁盘写入的延迟

CockroachDB：F1 渐进式 Schema 变更
  灵感来源：Google F1 论文
  一次变更经过多个阶段：
  delete-only → write-only → public
  任何时刻集群中最多只有两个相邻版本的 schema
  相邻版本被设计为互相兼容

TiDB：异步 DDL 框架
  源码：pkg/ddl/
  通过 owner 选举确保同一时刻只有一个 TiDB 节点执行 DDL
  DDL 操作被记录在系统表中，节点可以异步执行

OpenTenBase：基于 2PC 的同步 DDL
  Coordinator 通过两阶段提交同步 DDL 到所有 Datanode
  简单但 DDL 期间可能有短暂的阻塞

Citus：利用 PG 原生 DDL + 分布式传播
  在 coordinator 执行 DDL 后传播到 worker
  依赖 PG 原生的 DDL 锁机制

Citus 的自适应执行器（最精巧的设计）：
  源码：executor/adaptive_executor.c（5359 行）
  - Slow Start 算法动态调整连接池（类似 TCP 拥塞控制）
  - WaitEventSet 多路复用所有连接的 IO 事件
  - 支持多副本 failover

Vitess 的 ScatterConn：
  源码：go/vt/vtgate/scatter_conn.go
  - 通过 health check 动态选择最健康的 tablet
  - 连接池按 keyspace/shard 组织

难以兼容的 SQL 特性：

  全局自增 ID（AUTO_INCREMENT）：
    单机靠本地计数器
    分布式需要中心化分配或范围预取

  存储过程中的事务控制：
    单机在同一个进程中执行
    分布式可能跨多个节点执行

  全局 ORDER BY + LIMIT：
    需要从所有分片获取排好序的数据
    取 TOP 10 可能需要从每个分片取 TOP 10 再合并

  跨分片 JOIN：
    单机只需在本地做
    分布式需要通过网络传输数据

CockroachDB 的 StoreLiveness：
  不仅检测节点是否在线
  还评估存储层的健康状态
  比传统心跳更精细

YugabyteDB 的 Master Leader：
  YB-Master 通过 Raft 管理元数据
  检测到 TServer 宕机后重新分配 tablet leader

OpenTenBase 的 GTM 主备切换：
  GTM Standby 持续同步主 GTM 的状态
  主 GTM 宕机后自动接管

CockroachDB：SQL 层多租户
  源码：pkg/multitenant/
  tenantrate/ 基于 token bucket 限流
  每个租户有独立的 SQL 执行环境

Citus：Schema-based 分租户
  源码：schema_based_sharding.c
  每个租户一个 schema
  利用 PG 的 schema 隔离机制

YugabyteDB 的方案：
  源码：src/yb/docdb/deadlock_detector.cc
  每个 tablet 维护本地等待关系
  周期性汇报给 coordinator 构建全局等待图

Citus 的方案：
  通过 WaitGraph 在协调节点上构建全局等待图

根本难点：Phantom Deadlock（幻影死锁）
  由于网络延迟，不同节点收集到的等待关系属于不同时刻
  → 可能检测到一个"其实已经不存在"的死锁
  → 导致不必要的事务中止

哪些挑战最适合犀牛鸟参赛者切入？

  高可行性 + 高影响力（推荐）：
  ├── GTM 性能优化（挑战 1 在 OpenTenBase 的具体体现）
  ├── 查询优化器增强（挑战 2，pgxcship 下推判断）
  └── 向量搜索集成（不在 12 个挑战中，但是热门方向）

  可行但需要更多基础：
  ├── HTAP 列存完善（挑战 5）
  └── 连接管理优化（挑战 8）

  适合学习但不建议作为贡献目标：
  ├── 共识协议（挑战 6，太深）
  ├── 全局时钟（挑战 4，太深）
  └── 分布式 DDL（挑战 7，涉及面太广）