知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 09 - 分片与复制 ## 概述 分片(Sharding)和复制(Replication)是分布式存储系统的两大核心技术,分别解决数据扩展性和可用性问题。  ## 数据分片 ### 分片策略 #### 1. 哈希分片  #### 2. 范围分片  #### 3. 目录分片  ### 一致性哈希 #### 基本原理  *图:一致性哈希用虚拟节点减少扩容迁移量* ``` 解决普通哈希的扩缩容问题: - 普通哈希:增加节点后,hash % n 变化,大量数据需要迁移 - 一致性哈希:只需要迁移 1/n 的数据 一致性哈希环(物理节点 + 虚拟节点): 没有虚拟节点(3 个物理节点): 0 ┌┴┐ ┌────┤ ├────┐ 数据分布不均匀! │ └─┘ │ NodeA 可能负责 50% 的 key │ NodeA │ NodeB 只负责 10% │ │ → 热点问题 └──────NodeB───┘ NodeC 有虚拟节点(每个物理节点 150 个虚拟节点): 0 ┌┴┐ ┌────┤ ├────┐ 虚拟节点均匀分布 │ └─┘ │ VA1,VA2,...对应 NodeA │ VB3 │ VB1,VB2,...对应 NodeB │ VA1 VB1 │ → 数据在物理节点间均匀分布 └──VA2──VC1───VA3──┘ 扩缩容时(新增 Node D): 每个物理节点添加 150 个虚拟节点 数据迁移量 = 1/(已有节点数+1) ≈ 1/4 → 只需要迁移 Node A/B/C 各约 25% 的数据到 D ```  #### 一致性哈希扩缩容迁移示例  *图:新增节点 D 后 key 的归属与 25% 迁移量* ``` 增加节点前(3 个物理节点,各 150 个虚拟节点,共 450 个虚拟节点): 数据 key1 → hash → 落在 VA75 → 属于 NodeA 数据 key2 → hash → 落在 VB30 → 属于 NodeB 数据 key3 → hash → 落在 VC120 → 属于 NodeC 数据 key4 → hash → 落在 VA137 → 属于 NodeA 增加节点 D 后(4 个物理节点,各 150 个虚拟节点,共 600 个虚拟节点): 数据 key1 → hash → 落在 VA75(不变)→ 仍属于 NodeA ✓ 不需要迁移 数据 key2 → hash → 落在 VB30(不变)→ 仍属于 NodeB ✓ 不需要迁移 数据 key3 → hash → 落在 VC120 → 检查顺时针:VA75、VD10(新)比 VC120 更近 → 需要迁移到新节点 D ← 迁移量 ~1/4 数据 key4 → hash → 落在 VA137 → 旁边新增了 VD10 → 仍属 NodeA ✓ 不需要迁移 迁移量 ≈ 3000 万 key → 只需迁移 ~750 万 key(25%) 对比普通哈希:hash % 3 → hash % 4 → 需要迁移 ~75% 数据! ``` ```java public class ConsistentHashing { private TreeMap<Long, String> ring = new TreeMap<>(); private int virtualNodes = 150; // 虚拟节点数 // 添加物理节点 public void addNode(String node) { for (int i = 0; i < virtualNodes; i++) { long hash = hash(node + "#" + i); ring.put(hash, node); } } // 移除节点 public void removeNode(String node) { for (int i = 0; i < virtualNodes; i++) { long hash = hash(node + "#" + i); ring.remove(hash); } } // 查找数据应该存储的节点 public String getNode(String key) { if (ring.isEmpty()) { return null; } long hash = hash(key); // 找到第一个 >= hash 的节点 Map.Entry<Long, String> entry = ring.ceilingEntry(hash); if (entry == null) { // 绕回环的开始 entry = ring.firstEntry(); } return entry.getValue(); } private long hash(String key) { // 使用 MurmurHash 等高质量哈希函数 return Hashing.murmur3_128().hashString(key, StandardCharsets.UTF_8) .asLong(); } } ``` #### 虚拟节点  *图:每个物理节点映射多个虚拟节点使分布均匀* ``` 问题:节点数量少时,数据分布不均匀 解决:每个物理节点映射多个虚拟节点 0 │ A1 ──┼── B1 ╱ ╲ ╱ ╲ C2 A2 │ │ │ │ B2 C1 ╲ ╱ ╲ ╱ A3 ──┴── B3 物理节点 A: 虚拟节点 A1, A2, A3 物理节点 B: 虚拟节点 B1, B2, B3 物理节点 C: 虚拟节点 C1, C2 数据分布更均匀 ```  ### 分片扩容  *图:停机扩容与在线扩容的双写、迁移、切换* ``` 扩容策略: 1. 停机扩容(简单但有停机时间) - 停止服务 - 重新计算分片 - 迁移数据 - 重启服务 2. 在线扩容(复杂但无停机) ┌────────────────────────────────────────────────────────┐ │ 双写阶段 │ │ │ │ 写请求 ─────┬─────→ 旧分片(主) │ │ │ │ │ └─────→ 新分片(同步) │ │ │ │ 读请求 ──────────→ 旧分片 │ └────────────────────────────────────────────────────────┘ │ ▼ ┌────────────────────────────────────────────────────────┐ │ 数据迁移阶段 │ │ │ │ 后台任务将旧数据从旧分片迁移到新分片 │ └────────────────────────────────────────────────────────┘ │ ▼ ┌────────────────────────────────────────────────────────┐ │ 切换阶段 │ │ │ │ 读写都切换到新分片 │ │ 停止双写 │ └────────────────────────────────────────────────────────┘ ```  ## 数据复制 ### 复制策略  *图:同步、异步、半同步三种复制方式的一致性权衡* ``` 1. 同步复制(Synchronous Replication) ┌────────┐ 写入 ┌────────┐ 同步 ┌────────┐ │ Client │ ──────→ │ Master │ ──────→ │ Slave │ └────────┘ └────────┘ 等待 └────────┘ ↑ │ 确认 │ │ │ │ └─────────────────┴────────────────────┘ 返回成功 优点:强一致性,不丢数据 缺点:延迟高,可用性降低 2. 异步复制(Asynchronous Replication) ┌────────┐ 写入 ┌────────┐ 异步 ┌────────┐ │ Client │ ──────→ │ Master │ ──────→ │ Slave │ └────────┘ └────────┘ └────────┘ ↑ │ │ │ └─────────────────┘ 立即返回 优点:低延迟,高可用 缺点:可能丢数据,短暂不一致 3. 半同步复制(Semi-synchronous Replication) ┌────────┐ 写入 ┌────────┐ 同步 ┌────────┐ │ Client │ ──────→ │ Master │ ──────→ │ Slave1 │ ✓ 至少一个 └────────┘ └────────┘ 异步 └────────┘ 确认 ↑ │ │ │ ┌────────┐ │ └──────→ │ Slave2 │ 可以异步 └─────────────────┘ └────────┘ 等待一个确认 优点:平衡一致性和性能 ``` ### 主从复制  *图:一主多从:Master 写、Slave 分担读* ``` ┌─────────────────────────────────────────────────────────────┐ │ 主从复制架构 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ 写请求 │ │ │ │ │ ▼ │ │ ┌──────────┐ │ │ │ Master │ ─── 复制日志 ──→ Binlog/WAL │ │ │ (主节点) │ │ │ └────┬─────┘ │ │ │ │ │ ┌─────────┼─────────┐ │ │ │ │ │ │ │ ▼ ▼ ▼ │ │ ┌──────┐ ┌──────┐ ┌──────┐ │ │ │Slave1│ │Slave2│ │Slave3│ │ │ │(从节点)│ │(从节点)│ │(从节点)│ │ │ └──────┘ └──────┘ └──────┘ │ │ ↑ ↑ ↑ │ │ └─────────┴─────────┘ │ │ 读请求 │ │ │ └─────────────────────────────────────────────────────────────┘ ```   ```java // 主从复制示例 public class MasterSlaveReplication { private DataSource master; private List<DataSource> slaves; private AtomicInteger readCounter = new AtomicInteger(0); // 写操作走主库 @Transactional public void write(String sql, Object... params) { try (Connection conn = master.getConnection()) { PreparedStatement ps = conn.prepareStatement(sql); // 执行写入 ps.executeUpdate(); } } // 读操作走从库(轮询) public ResultSet read(String sql, Object... params) { int index = readCounter.getAndIncrement() % slaves.size(); DataSource slave = slaves.get(index); try (Connection conn = slave.getConnection()) { PreparedStatement ps = conn.prepareStatement(sql); return ps.executeQuery(); } } // 强一致读走主库 public ResultSet readFromMaster(String sql, Object... params) { try (Connection conn = master.getConnection()) { PreparedStatement ps = conn.prepareStatement(sql); return ps.executeQuery(); } } } ``` ### 多主复制  *图:多主双向复制及同一数据并发写的冲突* ``` ┌─────────────────────────────────────────────────────────────┐ │ 多主复制架构 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ 数据中心 A 数据中心 B │ │ ┌──────────────┐ ┌──────────────┐ │ │ │ │ │ │ │ │ ──→│ Master A │←─────→│ Master B │←── │ │ 写 │ │ 双向 │ │ 写 │ │ └──────┬───────┘ 复制 └───────┬──────┘ │ │ │ │ │ │ ┌──────▼───────┐ ┌───────▼──────┐ │ │ │ Slave A │ │ Slave B │ │ │ └──────────────┘ └──────────────┘ │ │ │ │ 问题:两个 Master 同时写入同一条数据,如何处理冲突? │ │ │ └─────────────────────────────────────────────────────────────┘ ``` ### 冲突解决 ``` 多主复制的冲突解决策略: 1. 最后写入胜出(Last Writer Wins, LWW) - 使用时间戳,最新的写入覆盖旧的 - 简单但可能丢失数据 2. 合并(Merge) - 自动或手动合并冲突数据 - 如:将两个列表合并 3. 自定义解决 - 应用层处理冲突逻辑 - 最灵活但最复杂 ``` ```java // 最后写入胜出 public class LastWriterWins { public void resolveConflict(Record local, Record remote) { if (remote.getTimestamp() > local.getTimestamp()) { // 远程更新,覆盖本地 localStore.put(remote.getKey(), remote); } // 否则保留本地版本 } } // 向量时钟解决冲突 public class VectorClockConflictResolver { public Record resolve(Record r1, Record r2) { VectorClock vc1 = r1.getVectorClock(); VectorClock vc2 = r2.getVectorClock(); if (vc1.happensBefore(vc2)) { return r2; // r2 更新 } else if (vc2.happensBefore(vc1)) { return r1; // r1 更新 } else { // 并发写入,需要合并或让用户选择 return merge(r1, r2); } } } ``` ## 分片 + 复制 ### 组合架构  *图:分片加复制:分片扩容、副本保高可用* ``` 实际系统通常同时使用分片和复制 ┌─────────────────────────────────────────────────────────────┐ │ 分片 + 复制架构 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ 数据按 Key 分片: │ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │ │ Shard 0 │ │ Shard 1 │ │ Shard 2 │ │ │ │ keys: 0-99 │ │keys: 100-199│ │keys: 200-299│ │ │ └─────────────┘ └─────────────┘ └─────────────┘ │ │ │ │ │ │ │ ▼ ▼ ▼ │ │ 每个分片有多个副本: │ │ ┌───┬───┬───┐ ┌───┬───┬───┐ ┌───┬───┬───┐ │ │ │ M │ S │ S │ │ M │ S │ S │ │ M │ S │ S │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └───┴───┴───┘ └───┴───┴───┘ └───┴───┴───┘ │ │ Master+Slaves Master+Slaves Master+Slaves │ │ │ │ 总结: │ │ - 分片提供水平扩展能力 │ │ - 复制提供高可用和读扩展 │ │ │ └─────────────────────────────────────────────────────────────┘ ```  ### 典型实现 ``` Redis Cluster: - 16384 个槽位,通过 CRC16(key) % 16384 确定槽位 - 每个节点负责部分槽位 - 每个节点可以有从节点 MongoDB: - 基于范围或哈希的分片 - 每个分片是一个副本集(Replica Set) - Config Server 存储元数据 Cassandra: - 一致性哈希分片 - 可配置复制因子(如 RF=3) - 无主架构,任意节点可读写 ``` ## 本章小结 - **分片策略**:哈希分片、范围分片、目录分片 - **一致性哈希**:解决扩缩容时的数据迁移问题 - **复制策略**:同步、异步、半同步复制 - **主从复制**:写主读从,提高读性能 - **多主复制**:多点写入,需要解决冲突 - **组合使用**:分片 + 复制,兼顾扩展性和可用性 ## 思考题 1. 一致性哈希为什么需要虚拟节点?没有虚拟节点会有什么问题? 2. 主从复制中,如何处理读写分离导致的数据不一致问题? 3. 多主复制中,为什么「最后写入胜出」可能导致数据丢失? ## QA ### Q1:一致性哈希为什么需要虚拟节点?没有虚拟节点会有什么问题? 虚拟节点的作用是把少量物理节点更均匀地映射到哈希环上,避免因为节点分布过稀导致数据倾斜。没有虚拟节点时,某些物理节点可能负责很大一段环区间,结果就是负载不均、热点明显,节点上下线时迁移量也可能集中在少数节点上。加入虚拟节点后,数据分布更平滑,扩缩容时的扰动也更可控。 ### Q2:主从复制中,如何处理读写分离导致的数据不一致问题? 本质上是要处理复制延迟窗口。常见办法包括:关键读走主库;用户写后的一小段时间内强制读主;会话粘滞到同一个副本;根据复制位点或版本号判断从库是否追平;对极端一致性要求高的查询直接关闭读写分离。也就是说,读写分离不是“所有读都走从”,而是按一致性要求做分级路由。 ### Q3:多主复制中,为什么「最后写入胜出」可能导致数据丢失? 因为 LWW 只保留时间戳最新的那份数据,默认把其他并发写入全部覆盖掉。可问题在于并发更新未必互相冲突到只能留一份,也未必能可靠比较先后,特别是在时钟不准、跨机房延迟或两个字段分别被不同节点修改时,较早但同样有价值的更新会被直接抹掉。所以 LWW 简单高效,但本质上是“用覆盖换收敛”,天然存在丢失业务语义的风险。 --- 下一篇:[10 - 分布式缓存与数据库](./10-distributed-cache-db.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入