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
        - ![](https://an-img.oss-cn-hangzhou.aliyuncs.com/2026/02/22/20260222101553862.png,604,382)
        - 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 复习.md

CAP 与一致性模型

分布式存储底层

Cassandra/HBase

数据建模与查询建模

CAP 与一致性模型#

分布式存储底层#

Cassandra/HBase#

数据建模与查询建模#

CAP 与一致性模型

分布式存储底层

Cassandra/HBase

数据建模与查询建模