CAP 与一致性模型

• CAP 与一致性模型
  • CAP 定理
    • 组成
      • C(Consistency，一致性)：所有客户端在同一时刻读到的数据一致
      • A(Availability，可用性)：每个请求都能在有限时间内得到非错误响应
      • P(Partition tolerance，分区容错)：系统在网络分区时仍然能提供服务
    • 关键结论
      • 发生网络分区时，无法同时满足 C 和 A
      • 分布式系统里 P 几乎是必选项（网络一定会分区/超时/抖动）
  • 一致性
    • 线性一致性
      • 定义：所有操作看起来像某个全局时间顺序瞬间发生，读一定能看到最近完成的读
      • 工程含义：通常需要 leader+共识+或严格 quorum+顺序约束
      • 代价：跨节点协调->延迟变高；分区时更可能不可用
    • 顺序一致：比线性一致弱
      • 只要存在一个全局顺序能解释所有的操作，但不要去符合真实时间，不要去最近完成的写立即可见
    • 因果一致：社交消息系统常见
      • 保证有因果关系的操作顺序一致；无因果关系的并发操作允许不同节点看到不同顺序
      • 先发帖再评论，所有人必须看到帖再评论，但两个人同时发帖，顺序可能不一样
    • 最终一致：AP 常见的一致性目标
      • 定义：如果不再有新的更新，所有副本都最终收敛到一个值
      • 允许：短时间读到旧值，不同客户端看到不同值
      • 收敛：复制、反熵、读修复、后台合并、冲突解决策略
  • Quorum(N/R/W)
    • 数据库用 quorum 思路来调一致性/可用性
    • 定义
      • N：副本数
      • W：写成功需要确认的副本数
      • R：读成功需要读取的副本数
    • 关键结论
      • 若 R+W>N，读写集合必然有交集->通常能读到最新写（接近强一致，但还要考虑版本选择/时钟/并发写）
      • 若 R+W<=N，可能读不到最新写（更偏最终一致/读旧值概率更高）
      • 举例
        • W=2,R=2->R+W=4>3：读写交集至少一个副本，读更可能拿到最新
        • W=1,R=1->2<=3：读很可能读到旧副本
    • 分区时怎么选 C/A
      • 更一致：提高 W 或 R，分区更容易失败
      • 更可用：降低 W 或 R，分区时能继续响应，可能读旧/冲突
    • 读修复与 hinted handoff
      • Read Repair（读修复）：读时发现副本版本不一致，把新值回写到旧副本，加速收敛
      • Hinted Handoff：某副本暂时不可达，协调者先把代写的 hint 记录下来，等它恢复再补写
    • 冲突从哪里来？怎么解决？
      • AP 系统分区时允许两边都写 -> 一定会出现冲突，关键是冲突语义
      • LWW(Last Write Wins)
        • 用事件戳/版本号选最新覆盖旧值
        • 风险：依赖时钟
        • 优点：实现简单，很多常见足够
      • 向量时钟/版本向量
        • 判断两个更新是否并发（不可比较）还是有先后关系（可比较）
        • 并发写需要应用层合并
      • CRDT
        • 通过数学结构保证并发合并可收敛
  • 一致性 != 事务 ACID
    • CAP 的 C：指副本之间对外可见的读写一致语义
    • ACID 里的 C：Consistency（约束一致性）是事务前后满足约束
    • 事务强一致可能跨分区不可用；最终一致系统也可以在单分区内做局部事务
  • 典型场景
    • 必须强一致
      • 余额扣款、库存扣减不超卖、唯一性约束、权限变更立即生效
      • 宁可失败重试/排队，也不能错
    • 可以最终一致
      • 点赞数、播放量、推荐特征、日志埋点、监控指标
      • 短时间误差可接受，最终对齐即可
    • 折中：读写分离 + 关键路径强一致
      • 下单扣库存走强一致存储：报表/BI 走 ClickHouse 最终一致导入
      • 缓存允许短暂不一致，通过失效策略、异步刷新、补偿修正

分布式存储底层

• 分布式存储底层
  • 分布式存储底层总览
    • Client/SDK
    • 路由层：根据 Key 找到 Shard/Leader
    • 分片层：每个分片负责一段 key 空间
    • 复制层：每个分片有 N 个副本
    • 一致层/共识层：决定写要等谁确认，谁是 Leader，如何提交日志
    • 存储引擎层：WAL + Memtable + SST/BTREE 等
    • 后台维护：compaction、rebalance、修复、反熵、GC
  • 数据分片
    • 为什么必须分片
      • 目标：水平扩展，吞吐=节点数线性增长
    • 分片策略对比
      • Hash 分片
        • 优点：数据分布均匀，天然抗热点
        • 缺点：范围查询弱，扩容时大量搬迁
        • 适用：KV，用户 ID 随机读写，计数器，缓存
      • Range 分片
        • 优点：范围查询强
        • 缺点：容易热点，需要 split/merge
        • 适用：按事件排序的日志、时序、OLAP 分区表
      • 一致性哈希 + 虚拟节点
        • 目标：扩容/缩容时减少迁移量
        • 一致性哈希结论：加/减一个节点只影响环上相邻的一段 key
        • 虚拟节点：每台机器对应多个 vnode，负载更均衡，迁移更细粒度
    • 路由：请求如何找到分片
      • Client-side routing（客户端算）
        • Client 拿到分片拓扑，自己算目标节点
        • 优点：少一跳、性能好
        • 缺点：拓扑变更要更新客户端（gossip/配置中心）
      • Proxy/Router（中间代理）
        • 由 Proxy 接请求，负责路由与重试
        • 优点：客户端简单，拓扑变更透明
        • 缺点：proxy 可能成为瓶颈/单点
      • Coordinator （协调节点）
        • 写入/查询可能由协调者拆分到多个分片再聚合
        • 常用于分析系统/分布式 SQL
    • Rebalance（扩缩容/再均衡）
      • 扩容
        • 数据迁移：搬迁期间读写怎么保证正确性
        • 双写/转发：迁移期间某些 key 可能在 old/new 两处
        • 限流：迁移会抢光 IO/CPU，影响线上延迟
      • 策略
        • 迁移期间双写，再切流
        • 迁移期间转发（写 old，old 转发到 new）
        • 分批搬迁+限速+热点优点处理
        • 稳定窗口切换元数据
  • 热点问题
    • 热点是什么
      • Hot key：单个 key QPS 极高
      • Hot partition：单个分片承担大量 key 或大量访问
    • 热点为什么致命
      • 分布式扩展依赖均匀分布，热点让整体吞吐被最热分片锁死
      • 延迟抖动：最热节点 CPU/网卡/锁竞争导致 p99 爆炸
    • 治理手段
      • Key 打散（加盐/分桶）
        • counter:global 拆分成 counter:global:{0..99}，读时聚合，写时随机桶
        • 代价：读放大/需要聚合
      • 读写分离 + 多副本读
        • 热读 key：允许从 follower/replica 读，或者使用 cache 层
      • 本地缓存 + 请求合并
        • 在网关/服务端合并通同 key 并发请求，防止缓存击穿引起雪崩
      • 分区拆分
        • range 分片：把热区间再拆细
        • 配合动态 split
      • 异步化/预计算
        • 把热点聚合改成写日志，异步聚合出结果
  • 副本复制
    • Leader-Follower（主从/Primary-Replica）
      • 写入路径：Client->Leader 写入->复制到 followers->达到确认策略后返回
      • 关键问题
        • 同步复制 vs 异步复制
          • 同步：延迟高但丢数据风险低
          • 异步：延迟低但主挂可能丢最后一段数据
        • 读策略
          • 读 leader：更一致
          • 读 follower：延迟小/抗压，但可能读旧
      • 适用：大多数传统分布式 DB/缓存系统
    • Multi-Leader（多主）
      • 多个 Leader 都可写，各自复制
      • 冲突不可避免，需要冲突解决（LWW/向量时钟/CRDT/业务合并）
      • 适用：跨地域多活、离线写入，复杂度高
    • Leaderless（无主，Dynamo 风格）
      • 任意节点可接写，写到 N 个副本
      • 用 Quorum(N/R/W)控制一致性
      • 配套：读修复、hinted handoff、反熵
      • 适用：高可用、可水平扩展、允许最终一致的系统
  • 一致写入确认：Quorum
    • 定义
      • N：副本数
      • W：写成功需要确认的副本数
      • R：读成功需要读取的副本数
    • 关键结论
      • 若 R+W>N，读写集合必然有交集->通常能读到最新写（接近强一致，但还要考虑版本选择/时钟/并发写）
      • 若 R+W<=N，可能读不到最新写（更偏最终一致/读旧值概率更高）
      • 举例
        • W=2,R=2->R+W=4>3：读写交集至少一个副本，读更可能拿到最新
        • W=1,R=1->2<=3：读很可能读到旧副本
  • 共识与选主
    • 共识
      • 只有一个 Leader（避免脑裂乱写）
      • 日志顺序一致（写入顺序全局一致）
      • 多数派提交（保证故障后不回滚）
    • Raft 最小正确集
      • Leader 选主
        • 节点有 term(任期)，超时发起选举
        • 多数派投票选出 Leader
        • 心跳维持 leader 身份
      • 日志复制
        • 客户端写入先到 leader
        • leader 追加日志并复制给 follower
        • follower 按 index/term 对齐（不一致就回滚到匹配点再补）
      • 提交规则
        • leader 只有在日志被多数派复制后才能提交
        • 提交后对外可见

Cassandra/HBase

• Cassandra/HBase
  • LSM-Tree + WAL

    • 

    • LSM-Tree 要解决什么问题
      • 传统 OLTP 存储引擎常见是 B+Tree
        • B+Tree 更新/插入会改动树上的多个节点页
        • 页可能在磁盘不同位置->随机写很多
        • 随机在 HDD 上很慢，在 SSD 上也不便宜
      • LSM 的核心目标
        • 把随机写变成顺序写/批量写
        • 把整理数据到成本挪到后台异步做（Compaction）
      • LSM 通过先写日志+写内存+顺序刷盘成不可变文件，再后台合并文件，大幅提高写吞吐，但是读取会更复杂，且 compaction 会带来放大和抖动
    • 写入流程
      • 先写 WAL（顺序追加）
        • 把这条写操作追加到 WAL 文件末尾
        • 顺序写，非常快
        • 目的：宕机可恢复
      • 写入 Memtable（内存有序结构）
        • MemTable 一般用 SkipList/红黑树等保证有序
        • 写入是内存操作，快
      • MemTable 满了就 Freeze（变成 Immutable）
        • 当前 Memetable 变成不可变，新写进入新的 MemTable
        • immutable 的存在时为了让刷盘不阻塞写入
      • 刷盘生成 SSTable（顺序写文件）
        • 后台线程把 immutbale MemTable 以排序后的顺序写成 SSTable，不可变有序文件
        • SSTable 通常附带
          • 稀疏索引
          • Bloom Filter
          • 数据块
    • 读流程
      • 步骤
        • 先查 MemTable
        • 再查 Immutable MemTable
        • 再查磁盘上的多个 SSTable
        • 找到 Key 后还要做版本合并
      • 同一个 Key 可能在很多层都有
        • SSTable 不可变，更新不是原地修改，而是写一个新版本
        • 旧版本会在后台 compaction 时被清理
        • 读放大：SSTable 越多，读需要查的地方越多
      • Bloom Filter 的作用
        • 对于某个 SSTable，Bloom Filter 判断：这个 key 不可能在里面->直接跳过，不读磁盘
        • 如果 Bloom 说在，才去查索引/数据块
      • Delete 怎么做
        • LSM 不会立刻物理删除数据，而是写入一个 Tombstone（删除标记）
        • Delete(key) 本质是写入 key->tombstone
        • 读到 tombstone 说明该 key 已经被删除
        • 真正清理旧值与 tombstone，依靠 Compaction 完成
    • Compaction
      • 目标
        • 合并多个 SSTable
        • 丢弃被覆盖的旧版本
        • 清理 tombstone
        • 降低读放大、回收空间
      • Compaction 为什么会导致 p99 抖动
        • 需要大量读旧文件 + 写新文件
        • CPU 做合并、校验、压缩
        • 可能把 SSD/HDD 打满，影响在线请求
      • compaction 策略
        • Sized-Tiered Compaction
          • 当 L0/L1 有若干大小相近的 SSTable，就合并成更大的
          • 优点：写放大相对小，吞吐高
          • 缺点：读放大可能更大
        • Leveled Compaction
          • 各层有大小上限，保证 L1+ 之间范围重叠更可控
          • 优点：读放大更小
          • 缺点：写放大更高

数据建模与查询建模

• 数据建模与查询建模
  • NoSQL 建模的通用原则
    • Query-driven modeling(按查询建模)
      • RDB 常按照范式建模，再用 SQL 去适配查询
      • 在 NoSQL 里更像：先确定查询，再设计主键/分区/排序/冗余表
    • Denormalization
      • 目的：消灭 join，降低在线查询复杂度
      • 代价：写入多处更新、需要处理一致性补偿
      • 同一份实体多份查询视图表
      • 把维度字段复制进事实表
    • 预计算/物化视图
      • 把聚合从读时搬到写时
      • 写路径：事件 -> 聚合状态更新
      • 读路径：直接读聚合结果
      • 适合：排行榜、计数器、报表、指标面板
    • 幂等与版本化
      • NoSQL + 分布式写入经常至少一次交付，天然要支持幂等
    • 热点治理
      • 避免分区键过于集中
      • 避免自增 RowKey
      • 避免单 key 计数器