分布式存储系统
从 CAP/BASE 基础理论，到数据分片、一致性哈希、复制与 Quorum、冲突解决，再到 Redis Cluster / DynamoDB / etcd / HBase / Cassandra / NewSQL。
🎯学习目标
- 掌握 CAP 定理三选二的本质，理解 CP/AP/CA 与 PACELC 扩展；
- 理解 BASE 理论与五级一致性模型（线性→顺序→因果→最终→读己写）；
- 掌握哈希分片、范围分片、一致性哈希与虚拟节点；
- 理解主从/多主/无主三种复制模式与 Quorum（W+R>N）机制；
- 掌握冲突解决（LWW/向量时钟/CRDT）与典型存储系统选型。
1CAP 定理 ⭐（核心考点）
CAP 定理（Brewer's Theorem）：由 Eric Brewer 于 2000 年提出，2002 年由 Gilbert & Lynch 正式证明。核心结论——分布式系统中，一致性（C）、可用性（A）、分区容错（P）三者最多同时满足两个。
| 特性 | 英文 | 含义 |
|---|---|---|
| 一致性 (C) | Consistency | 所有节点同一时刻看到相同数据（如转账后立即看到新余额） |
| 可用性 (A) | Availability | 每个请求都收到响应（不保证最新） |
| 分区容错 (P) | Partition Tolerance | 节点间通信故障时系统仍可运行 |
图1 · CAP 三角：三条边代表三种取舍，最多取两个顶点
🤔 为什么只能三选二？ 网络故障（P）在真实环境无法避免。分区发生时只有两条路：
- 选 C：拒绝响应、等节点联通再服务 → 牺牲可用性（A❌）
- 选 A：继续服务、可能返回旧数据 → 牺牲一致性（C❌）
| 选择 | 含义 | 典型系统 |
|---|---|---|
| CP | 分区时拒绝服务，确保数据绝对一致 | ZooKeeper、etcd、HBase |
| AP | 分区时继续响应，允许短暂不一致 | Cassandra、DynamoDB、Couchbase |
| CA | 理论上不存在（真实分布式无法避免 P），仅单机 | 单节点 MySQL/PostgreSQL |
⭐ CAP 的现实理解（必考）不是静态"三选二"——P 几乎不可避免，实际是分区发生时选 C 还是选 A。AP 系统提供的是最终一致性（不是永远不一致）；CP 系统只在分区期间拒绝服务（恢复后立刻恢复）。
📖 PACELC 扩展CAP 只关注"出故障时怎么选"。PACELC（Daniel Abadi）补充：正常运行（E=Else）时还要在延迟（L）与一致性（C）之间权衡。读法：分区（P）时 A or C？正常（E）时 L or C？例：DynamoDB=PA/EL，HBase=PC/EC，MongoDB=PA/EC。
2BASE 理论与一致性模型
BASE 是对 CAP 中 AP 路线的进一步阐述，是大型互联网系统（淘宝、微信、亚马逊）常用理念。核心思想：放弃强一致性，换取高可用和高性能。
| 缩写 | 全称 | 含义 |
|---|---|---|
| BA | Basically Available | 基本可用：允许部分功能降级或延迟，整体仍可用（大促搜索变慢但下单正常） |
| S | Soft State | 软状态：允许副本间短暂不同步（点赞数短暂不一致） |
| E | Eventually Consistent | 最终一致：停止写入后经一段时间所有副本趋于一致（DNS 更新） |
| 维度 | ACID | BASE |
|---|---|---|
| 一致性 | 强一致性 | 最终一致性 |
| 可用性 | 可能降低（等待同步） | 高可用 |
| 适用场景 | 银行转账、订单支付 | 社交动态、库存展示 |
| 代表系统 | MySQL、PostgreSQL | DynamoDB、Cassandra |
💡 选择依据需要强一致（金融/订单）→ ACID；需要高可用高吞吐（社交/推荐）→ BASE。BASE 并非"放任乱"，需设计冲突解决机制（读修复、向量时钟等）。
一致性模型（从强到弱，强度越高延迟越大）
| 模型 | 定义 | 延迟 | 典型系统 |
|---|---|---|---|
| 线性一致性 | 读必返回最新写入，所有操作按实时顺序 | 最高 | ZooKeeper、etcd |
| 顺序一致性 | 所有操作按同一全局顺序，不保证实时 | 高 | Raft/Paxos |
| 因果一致性 | 有因果关系的操作保序，无关可乱序 | 中 | MongoDB(Causal) |
| 最终一致性 | 停止写入后所有副本收敛同一值 | 低 | DynamoDB、Cassandra |
| 读己写一致性 | 用户一定能读到自己刚写入的数据 | 低 | 会话级优化 |
3数据分片（Sharding）
数据分片：将大规模数据集分割成多个子集分布存储在不同节点，每个节点只负责部分数据，实现水平扩展、突破单机瓶颈（容量、性能、可用性）。两大策略：
🔢
哈希分片
Hash Sharding按 Key 哈希值对节点数取模决定存哪节点。✅分布均匀 ⚠扩容大量迁移。代表 Redis Cluster
📏
范围分片
Range Sharding按 Key 值范围划分区间。✅范围查询高效、有序 ⚠易数据倾斜热点。代表 HBase/BigTable/Spanner
哈希分片核心公式：
node_id = hash(key) % N // 对节点数 N 取模
hash("user:1001") % 3 = 2 // → Node 2
slot = CRC16(key) % 16384 // Redis Cluster 16384 个槽⚠ 哈希分片致命缺点节点数 N 变化时几乎所有映射关系都改变：3 台→4 台约 75% 数据需迁移！解决方案是一致性哈希。
范围分片示例（按用户名首字母）
Node A: key ∈ [A, G) → alice, ben, fan
Node B: key ∈ [G, N) → han, kim, max
Node C: key ∈ [N, Z] → nao, sam, zhang优点：范围查询只访问一个节点、有序存储支持排序分页；缺点：数据倾斜产生热点、需维护分区元数据。
4一致性哈希 ⭐（核心考点）
设计目标：解决传统哈希节点增减时大量数据迁移的问题。传统哈希 3→4 台迁移约 75%，一致性哈希只需迁移约 1/N。
核心原理（Hash Ring）：哈希空间组成虚拟圆环（0 ~ 2³²−1），节点和 Key 均映射到环上，Key 顺时针找最近节点存入。类比钟表盘——数据找顺时针方向最近的刻度。
图2 · 哈希环：key 顺时针找到最近的节点 B 存入
✅ 节点增减优势：删节点只将该节点数据迁给顺时针下一节点；加节点只迁入新节点覆盖区间的数据。扩/缩容只影响 1/N 的数据！
| 对比 | 传统哈希 | 一致性哈希 |
|---|---|---|
| 10→11 节点迁移量 | ~(N-1)/N ≈ 91% | ~1/N ≈ 9% |
| 查询路由 | node=hash(key)%N，节点变则失效 | 顺时针找最近节点，增减不影响其他区段 |
虚拟节点（Virtual Nodes）
⚠ 遗留问题与解法少量节点时落点随机、分布不均，易出热点。虚拟节点：每个物理节点在环上注册多个"分身"（通常 100~200 个），均匀散落环上，数据仍顺时针找最近的分身，实际由对应物理节点处理。代表系统：Cassandra、DynamoDB、Riak。
5数据复制与 Quorum 机制
为什么复制？高可用（宕机时副本顶上）、低延迟（就近部署）、读扩展（多副本分担读）。三种复制模式：
| 模式 | 原理 | 代表 |
|---|---|---|
| ① 主从（Leader-Follower） | 主库写、从库只读，主同步 binlog 给从 | MySQL、PostgreSQL、Redis、Kafka 分区 |
| ② 多主（Multi-Leader） | 多地域各有主库、本地写后跨中心同步，需解决写冲突 | CouchDB、MySQL GR、Google Docs |
| ③ 无主（Leaderless） | 任意节点可写，靠 Quorum 投票保一致 | DynamoDB、Cassandra、Riak |
Quorum（法定人数）机制
读写操作必须得到足够多节点确认才算成功。N=副本数，W=写确认数，R=读确认数。
⭐ 强一致性条件：W + R > N保证读集与写集必有交集，一定能读到最新写入。常用配置 N=3, W=2, R=2，允许 1 个节点故障。
| 配置 | W | R | 特点 |
|---|---|---|---|
| 强一致读写 | 2 | 2 | W+R=4>3，任何读都能读到最新写入 |
| 写优先 | 3 | 1 | 写入所有副本，读取一个即可 |
| 读优先 | 1 | 3 | 写一个即返回，读取所有副本 |
| 最终一致 | 1 | 1 | 高性能，但可能读到旧数据 |
图3 · W+R>N 时写集与读集必有交集，保证读到最新写入
6冲突解决策略
多个客户端同时向同一 Key 写入不同值时产生写冲突。四种常见解决方案：
| 方案 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 最后写入胜出（LWW） | 取时间戳最大的写入 | 简单 | 可能丢失并发写入 |
| 向量时钟 | 记录每个节点版本号，检测并发冲突 | 精确检测冲突 | 实现复杂 |
| CRDTs | 数据结构自动合并，无冲突 | 无需冲突解决 | 只适用特定数据类型 |
| 应用层解决 | 返回所有冲突版本由应用合并 | 灵活 | 增加应用复杂度 |
📖 向量时钟示例初始 {A:0,B:0} → Node A 写 x=1 得 {A:1,B:0} → Node B 并发写 x=2 得 {A:0,B:1}。两者互不包含 ⚠ 检测到并发冲突，需应用层合并为 {A:1,B:1}。
📖 CRDT 类型G-Counter（只增计数器，合并取最大）、PN-Counter（可增可减）、G-Set（只添加集合取并集）、OR-Set（可添删）。特性：无冲突设计、最终一致、可交换可结合。适合协作编辑、点赞数、购物车。
7典型分布式存储系统
键值存储
| 系统 | 核心特点 |
|---|---|
| Redis Cluster | 哈希槽（共 16384 个，CRC16(key)%16384），主从复制自动切换，Gossip 协议去中心化 |
| Amazon DynamoDB | 全托管无服务器 NoSQL，Partition Key 哈希分片、3 AZ 复制，默认最终一致读可切强一致，个位数毫秒延迟 |
| etcd | K8s 默认数据存储，基于 Raft 共识强一致，Watch 机制、MVCC、Lease 租约 |
📖 Raft 共识算法选一位 Leader 统一处理写入，其他节点跟随同步。过半节点存活即可工作（3 台挂 1 仍运行）。流程：Leader 选举 → 日志复制 → 心跳维持。etcd 是 K8s 集群"唯一数据源"，所有组件通过 API Server 读写。
列族存储
Google BigTable（2006）是稀疏、分布式、持久化的多维有序 Map：(Row Key, Column Family:Qualifier, Timestamp) → Value，是 HBase 和 Cassandra 的设计原型。
| 维度 | HBase | Cassandra |
|---|---|---|
| CAP 选择 | CP（强一致） | AP（高可用） |
| 架构 | 中心化（Master-Slave） | 去中心化（P2P） |
| 组件 | Region/RegionServer/HMaster/MemStore/HFile/WAL | 对等节点、可调一致性（QUORUM/LOCAL_ONE） |
| 依赖 | HDFS + ZooKeeper | 独立运行（CQL 类 SQL） |
⭐ 列族存储选型口诀已有 Hadoop 生态、要强一致 → HBase；全球部署、要高可用 → Cassandra；用 GCP 免运维 → Cloud Bigtable。
NewSQL
NewSQL 兼备 SQL 关系模型与 ACID 事务，同时具备 NoSQL 的水平扩展能力。代表：Google Spanner（TrueTime 全球线性一致+分布式 ACID）、TiDB（MySQL 兼容、HTAP，组件 TiDB/TiKV/PD/TiFlash）、CockroachDB（PostgreSQL 兼容）。
📖 HTAP在同一系统同时支持 OLTP（事务）与 OLAP（分析），无需 ETL 同步到独立数仓。TiDB 用 TiKV 行存承接 OLTP、TiFlash 列存承接 OLAP，Raft 实时同步，实现 T+0 实时分析。
⭐重点例题
例题1：全球电商购物车选 CP 还是 AP？支付服务呢？
分析：购物车允许短暂数据偏差（用户可重试、最终一致即可），用户分布全球需高可用 → 选 AP（如 DynamoDB/Cassandra）。支付服务对金额绝对不能出错，宁可短暂不可用也不能返回脏数据 → 选 CP。
结论：CAP 不是全系统统一选择，而是按业务模块分别取舍。
结论：CAP 不是全系统统一选择，而是按业务模块分别取舍。
例题2：一致性哈希环 4 节点各 100 虚拟节点，删除一个节点迁移多少数据？迁到哪？
解答：一致性哈希删节点只影响该节点负责的区间，约 1/N = 1/4 = 25% 数据需迁移；这些数据迁移到环上顺时针方向的下一个节点。其余节点的数据完全不受影响——这正是一致性哈希优于传统哈希（需迁移约 75%）的根本原因。
例题3：Quorum 配置 N=3，要求强一致读写，W、R 怎么选？
思路：强一致条件是 W+R>N。取 W=2、R=2，则 W+R=4>3=N 成立，写集与读集必有交集，任何读都能读到最新写入，同时允许 1 个节点故障。若选 W=1,R=1 则 W+R=2<3，只能最终一致、可能读到旧数据。
🎯自测（点击展开）
CAP 定理的核心结论是什么？为什么只能三选二？
C/A/P 最多同时满足两个。因为网络分区 P 不可避免，分区时只能选拒绝响应（保 C 弃 A）或继续服务（保 A 弃 C）。
BASE 三个字母分别代表什么？
Basically Available（基本可用）、Soft State（软状态）、Eventually Consistent（最终一致）。
哈希分片扩容为什么代价高？怎么解决？
node=hash(key)%N，N 变化时几乎所有映射改变（3→4 台约迁 75%）。用一致性哈希+虚拟节点，迁移量降至约 1/N。
Quorum 强一致条件是什么？
W+R>N，保证读集与写集必有交集，一定能读到最新写入。
向量时钟和 LWW 各有什么优缺点？
LWW 取时间戳最大者，简单但可能丢并发写；向量时钟能精确检测并发冲突，但实现复杂、合并需应用层处理。
HBase 和 Cassandra 在 CAP 上分别属于什么？
HBase 是 CP（强一致、中心化）；Cassandra 是 AP（高可用、去中心化 P2P、可调一致性）。
📝强化题库
选择题点选即时判分；填空题输入后"检查"或"显示答案"。
已答 0/0答对 0正确率 —
已答 0/0答对 0