一致性 Hash 与 Raft 共识
#数据结构 · #分布式 · #一致性Hash · #Raft · #共识算法 · #数据分片
从单机 Hash 表到分布式 Hash 表，数据分片与节点动态增减引入了新问题：如何让缓存在扩容时尽量不失效？多副本间如何保证数据一致？——一致性 Hash 和 Raft 分别解决这两个核心问题。
1. 一致性 Hash 深入
1.1 问题：为什么不用取模？
初始: 3 个缓存节点, hash(key) % 3 → 均匀分配
扩容: 添加第 4 个节点, hash(key) % 4 → ~75% 的 key 需要搬家
这意味着:
- 新增节点后, 缓存命中率近乎 0%
- 所有请求穿透到数据库 → 雪崩
- 要重新预热缓存, 代价极大1.2 环形 Hash 空间
mermaid
flowchart TD
subgraph Ring["Hash 环 0 到 2的32次方减1"]
direction LR
R1["0"] ~~~ R2["2^32-1"]
end将 hash 空间视为一个环 (0 → 2^32-1 → 0):
2^32-1 ─ 0
/ \
/ Hash 环 \
/ \
... N1 (hash(N1) = 1,000,000)
| / \
| / \
N3 (300M) / 这个区间归 N1 管
| /
| /
... N2 (hash(N2) = 500,000)
规则: key 映射到 hash 环上，顺时针找到的第一个节点负责该 key添加 N4 (hash = 2,000,000):
- N4 进入环 → N4 和 N1 之间多了一个节点
- 只有落在 N4→N1 之间的 key 需要重新分配给 N4
- 其他所有 key 不受影响 ✅
- 迁移量 ≈ 1/(n+1) 的数据 (~25%，远优于取模法的 75%)1.3 虚拟节点解决倾斜
mermaid
flowchart LR
subgraph Without["无虚拟节点: 不均匀"]
WA["A ████████████████ 40%"]
WB["B ██████████ 25%"]
WC["C ██████████████ 35%"]
end
subgraph With["150 虚拟节点: 均匀"]
VA["A ████████████ 33%"]
VB["B ████████████ 33%"]
VC["C ████████████ 34%"]
end
Without -.->|"虚拟节点"| With
style WA fill:#F44336,color:#fff
style VA fill:#4CAF50,color:#fff- 每个物理节点映射为 100~200 个虚拟节点分布到环上
- 虚拟节点越多，分布越均匀（但维护成本越大）
- 实践中 150 个虚拟节点 即足够，偏差 < 5%
为什么是 150-200 个虚拟节点？——数学推导
一致性哈希环上的负载均衡问题本质是"球入箱"模型:
- N 个物理节点，每个有 V 个虚拟节点 → 环上共 N×V 个点
- 假设 hash 函数均匀 → 这些点将环分成 N×V 个弧段
- 每个弧段的长度 ∝ 该虚拟节点负责的 key 数量
弧段长度的分布:
N×V 个均匀随机点将 [0, 2^32) 分成 N×V 段
每段长度服从 Exponential(N×V) 分布
一个物理节点负责 V 段 → 总负载 = V 个指数分布随机变量之和
→ 服从 Gamma(V, 1/(N×V)) 分布
期望负载 = 1/N (每个节点平均负责 1/N 的 key)
标准差 = 1/(N × √V)
变异系数 CV = 标准差/期望 = 1/√V
CV 与虚拟节点数的关系:
V = 50: CV = 1/√50 ≈ 14.1% → 最大偏差可能 ~30%
V = 100: CV = 1/√100 = 10% → 最大偏差可能 ~20%
V = 150: CV = 1/√150 ≈ 8.2% → 最大偏差可能 ~15%
V = 200: CV = 1/√200 ≈ 7.1% → 最大偏差可能 ~12%
V = 500: CV = 1/√500 ≈ 4.5% → 最大偏差可能 ~8%
V = 1000: CV = 1/√1000 ≈ 3.2% → 最大偏差可能 ~5%
工程目标: 最大偏差 < 10-15% → V ≈ 150 即可满足
但 V 不能无限大:
- 每个虚拟节点需要在环上维护一个条目
- 查找时需要在 N×V 个点中做二分查找: O(log(N×V))
- 节点增删时需要重新分配 V 个虚拟节点的 key
- 内存: 每个虚拟节点 ≈ 8B(hash) + 8B(指针) = 16B
N=100, V=200 → 100×200×16B = 320KB (可接受)
N=100, V=10000 → 16MB (可能过大)
最优选择:
V = 150~200: 偏差 < 10%，内存可控，查找 O(log(N×200)) 仍然很快
这就是为什么 Memcached、Ketama、Consul 等都默认 150-200 个虚拟节点
实际验证 (N=10 个节点, 100万个 key):
V=1: 最大节点负载 38.2%, 最小 2.1% → 极不均匀
V=10: 最大 15.3%, 最小 6.8% → 偏差大
V=50: 最大 12.1%, 最小 8.2% → 可接受
V=150: 最大 11.2%, 最小 9.1% → 良好 ✅
V=200: 最大 10.8%, 最小 9.3% → 优秀 ✅
V=1000: 最大 10.3%, 最小 9.7% → 接近完美（但维护成本高）1.4 三种一致性 Hash 变体对比
| 方案 | 状态 | 均匀度 | 增删成本 | 典型场景 |
|---|---|---|---|---|
| 环形 Hash + 虚拟节点 | 需维护环 | 好 (>100 vnode) | O(log n) 查找 | Redis Cluster, Memcached |
| Jump Hash | 无状态 | 好 | O(log n) 但不能删中间 | Google 负载均衡 |
| Rendezvous Hash | 无状态 | 好 | O(n) 但支持权重 | 数据中心间路由 |
| 取模法 | 无状态 | 完美 (不改动时) | O(1) 但全量迁移 | 固定分片 |
1.5 Redis Cluster 中的哈希槽（Hash Slot）
Redis Cluster 采用了介于取模和一致性 Hash 之间的方案：
16384 个 hash slot:
CRC16(key) % 16384 → slot 编号
每个节点负责一段连续的 slot:
Node A: slot 0-5460
Node B: slot 5461-10922
Node C: slot 10923-16383
添加新节点:
- 从每个已有节点各搬一部分 slot 给新节点
- 迁移以 slot 为最小单位（一个 slot 的 key 全部搬）
- 迁移期间 key 可继续访问（ASK 重定向）这比一致性 Hash 简单（固定 16384 个槽，不用虚拟节点），迁移粒度可控。
2. Raft — 分布式共识算法
为什么需要共识算法？ 分布式系统中，多副本（Leader+Followers）之间如何就"哪个值是正确的"达成一致？这就是共识问题。Raft 是目前工业界最广泛使用的共识算法（etcd、TiKV、Consul、NATS）。
2.1 角色与领导者选举
mermaid
flowchart TD
subgraph States["节点三种角色"]
L["Leader<br/>处理所有写请求<br/>发送心跳/日志复制"]
F["Follower<br/>接收 Leader 日志<br/>响应心跳"]
C["Candidate<br/>选举期间<br/>请求投票"]
end
F -->|"选举超时 150-300ms 随机"| C
C -->|"获得多数票"| L
C -->|"选举超时或平票"| C
L -->|"发现更高 Term"| F
L -.->|"心跳 每50ms"| F
style L fill:#4CAF50,color:#fff
style F fill:#2196F3,color:#fff
style C fill:#FF9800,color:#fff关键设计：
- 随机超时（150-300ms）：防止多个 Follower 同时变成 Candidate 导致平票。谁先超时谁先发起选举。
- Term（任期）：单调递增的逻辑时钟。每个 Term 最多一个 Leader。
- 心跳：Leader 周期性发送，Follower 收到后重置选举定时器。
2.2 日志复制
mermaid
sequenceDiagram
participant Client
participant Leader
participant F1 as Follower 1
participant F2 as Follower 2
Client->>Leader: SET x=1
Leader->>Leader: 追加到本地日志 term=1 idx=5 cmd=x1
Leader->>F1: AppendEntries logs term=1 idx=5
Leader->>F2: AppendEntries logs term=1 idx=5
F1-->>Leader: ACK - 已持久化
F2-->>Leader: ACK - 已持久化
Note over Leader: 多数 2/3 已确认, commitIndex 5
Leader->>Leader: 应用到状态机 x=1
Leader->>Client: OK
Leader->>F1: 下条心跳 AppendEntries 带 leaderCommit 5
F1->>F1: 应用到状态机关键保证：
- 当日志被多数节点持久化后才算 committed
- committed 的日志永不丢失（除非多数节点同时故障）
- Leader 的日志一定是最新的（选举限制：Candidate 的日志不能比投票者旧）
2.3 安全性保证
| 保证 | 如何实现 |
|---|---|
| 选举安全 | 每 Term 最多一个 Leader |
| Leader 日志完整性 | 投票者检查 Candidate 的日志不比自己的旧 |
| 日志匹配性 | 如果两个节点的日志在相同 index 和 term 一致，则之前的所有日志都一致 |
| Leader 从不覆盖日志 | Leader 只追加，不修改已存在的 entry |
| 状态机安全 | 所有节点最终以相同顺序应用相同的日志 |
2.4 领导者变更 — 5 个节点示例
初始: Term 5, Leader=S1, Followers=S2-S5
S1 宕机:
S2 选举超时 (180ms) → Term 6, Candidate
S2 收到 S3,S4 的投票 (3/5 > 半数) → 成为 Leader
S5 可能晚收到，但已不影响结果
S1 恢复:
发现 Term 6 > 自己的 Term 5
→ 自动降级为 Follower2.5 Raft vs 其他共识算法
| 算法 | 可理解性 | 领导者 | 日志 | 典型应用 |
|---|---|---|---|---|
| Raft | ⭐⭐⭐⭐⭐ 极易 | 强 Leader | 复制日志 | etcd, TiKV, Consul |
| Paxos | ⭐ 极难 | 多 Proposer | 单值 | Chubby |
| Multi-Paxos | ⭐⭐ 困难 | 弱 Leader | 复制日志 | Spanner, ZooKeeper |
| ZAB | ⭐⭐ 困难 | 强 Leader | 复制日志 | ZooKeeper |
| Viewstamped Replication | ⭐⭐⭐ 中等 | 强 Leader | 复制日志 | 学术 |
2.6 工程实践要点
Raft 的三大性能瓶颈与优化：
| 瓶颈 | 原因 | 优化 |
|---|---|---|
| 串行写入 | 所有写必须经过 Leader，单点瓶颈 | Multi-Raft（分 Region，每个 Region 独立 Raft 组） |
| 磁盘 fsync | 每条日志必须 fsync 才能返回 | 批量提交（Batch），pipeline 复制 |
| 领导者选举 | Leader 宕机后有不可用窗口（~1s） | Pre-Vote（防网络分区后的无效选举）、租约（Lease）读 |
| 成员变更 | 直接切配置可能产生双 Leader | Joint Consensus（两阶段过渡） |
成员变更 — Joint Consensus
这是 Raft 中最精妙也最容易被忽视的设计。如果直接从一个 3 节点集群（S1,S2,S3）切换到 5 节点（S1,S2,S3,S4,S5），在中间状态可能出现两个互不认识的多数派，分别选出不同的 Leader——这被称为"双主脑裂"。
Raft 通过 Joint Consensus 解决：引入一个过渡配置 C_old,new，在此期间老多数派和新多数派都必须同意才能提交：
mermaid
flowchart LR
Cold["C_old<br/>3节点 S1 S2 S3<br/>多数派 2"] -->|"写入 C_old_new"| ColdNew["C_old_new 过渡<br/>老3节点 + 新5节点<br/>多数派 3"]
ColdNew -->|"写入 C_new"| Cnew["C_new<br/>5节点 S1-S5<br/>多数派 3"]
Note["过渡期间:<br/>1. 日志复制需老新多数派都确认<br/>2. 选举需任一配置多数派投票<br/>保证不会有双 Leader"]
ColdNew --> Note简单理解：Joint Consensus 就像"改朝换代时的过渡期"——旧皇帝（C_old）还没退位，新皇帝（C_new）已经在逐步接管权力。在此期间，重要决策（日志提交）需要两朝元老（老多数派+新多数派）都同意，避免了权力真空。
Multi-Raft 示例 (TiKV)：
整个集群按 Key Range 分片:
Region 1 ["" - "m"): Raft Group 1 (Leader=S1)
Region 2 ["m" - "z"): Raft Group 2 (Leader=S4)
Region 3 ["z" - ∞): Raft Group 3 (Leader=S2)
每个 Region 独立选主、独立复制日志
→ 写入负载分散到所有节点日志压缩与快照（Snapshot）
Raft 日志会无限增长——必须通过快照截断：
时间线: ... [entry 1-5000] [entry 5001-10000] [entry 10001-15000]
↑ 已 applied，可以截断
Follower 落后太多时，Leader 不再逐条发 AppendEntries，
而是直接发送全量快照（InstallSnapshot RPC）：
1. Leader 对 applied 的日志做快照（状态机序列化 + 最后 applied index/term）
2. 发送 InstallSnapshot 给落后的 Follower
3. Follower 收到后：清空旧日志 → 加载快照 → 从快照的 index 之后开始接收新日志
实现要点：
- 快照频率：etcd 默认每 10000 条日志做一次快照
- 快照不宜太频繁（IO 开销），也不宜太稀（日志过长，恢复慢）
- etcd 的快照机制：boltDB 的 MVCC 层天然支持快照，一边服务读写一边做快照Lease Read — 绕过 Raft 日志的线性读优化
问题：etcd 的读操作默认也要走一遍 Raft——Leader 需要广播心跳确认自己还是 Leader 后才能返回读结果。这引入了网络往返延时。
mermaid
sequenceDiagram
participant Client
participant Leader
participant Followers
Note over Client,Followers: 默认 ReadIndex 方式 - 串行读
Client->>Leader: GET /key
Leader->>Leader: 记录当前 commitIndex
Leader->>Followers: 心跳广播，确认自己仍是 Leader
Followers-->>Leader: ACK 多数确认
Leader->>Leader: 等待 appliedIndex >= readIndex
Leader->>Client: 返回 value - 线性一致性保证
Note over Client,Followers: Lease Read 优化 - 减少一次网络往返
Leader->>Leader: 在 Lease 有效期内，跳过心跳确认
Leader->>Leader: 直接等待 appliedIndex >= readIndex
Leader->>Client: 返回 value, 假设 Lease 期间无新 LeaderLease Read 的安全前提：
Leader 租约时间 = 选举超时时间 - 一些缓冲（如 150ms 选举超时 → 100ms 租约）
在租约有效期内，Leader 可以安全地：
1. 跳过心跳确认 → 减少一次网络往返
2. 直接返回本地 applied 的数据
风险：如果发生了脑裂（旧 Leader 的网络分区），旧 Leader 在租约内
可能返回过期数据。但 etcd 通过以下方式规避：
- 新 Leader 当选后，在租约到期前不服务读请求
- 写请求始终走完整 Raft 流程（不受 Lease 影响）etcd 生产调优关键参数
| 参数 | 默认值 | 调优建议 |
|---|---|---|
| HeartbeatTick | 1（内部时钟） | 网络稳定调为 1（更快故障检测），跨地域调为 2-3 |
| ElectionTick | 10 | 公式：选举超时 = ElectionTick × HeartbeatTick × 时钟周期。跨地域建议调大（20-30） |
| MaxInflightMsgs | 256 | 高吞吐量场景调大（512-1024），减少 pipeline 等待 |
| SnapshotCount | 100000 | 根据写入量调整，写入密集降低到 50000 |
| MaxRequestBytes | 1.5 MB | gRPC 消息体限制，大批量场景调大 |
| QuotaBackendBytes | 2 GB | 数据库大小限制，超过则只读。生产建议 8 GB |
Paxos vs Raft — 本质区别展开
Paxos (Lamport, 1989):
- 两阶段：Prepare/Promise → Accept/Accepted
- 每个实例独立达成共识
- 多 Proposer 可以同时发起提案 → 活锁风险
- 论文极其晦涩，工程实现各有变体
Raft (Ongaro, 2014):
- 强 Leader 模型：所有日志通过 Leader 分发
- 日志连续性保证：Log Matching Property
- 角色分离：Leader / Follower / Candidate
- 设计目标：Understandable（可理解的）
核心差异：
1. Paxos 可以乱序提交（每个 instance 独立），Raft 必须顺序提交
→ Raft 简单但写入是串行的，Multi-Paxos 可以一定程度并行
2. Paxos 中 Leader 只是"加速器"（任何节点都可以发起提案）
Raft 中 Leader 是核心（只有 Leader 能发起日志复制）
3. Paxos 的日志可能不连续（holes），需要额外协议补齐
Raft 保证日志连续，通过 Log Matching Property 简化恢复
为什么工业界选 Raft？
- 正确性容易验证（TLA+ 形式化证明）
- 实现简单（etcd Raft 库 ~3000 行，Paxos 实现通常上万行）
- 工程化友好（成员变更、快照、配置变更都明确定义）3. 分布式 Hash 表与共识的结合应用
| 系统 | 数据分布 | 共识算法 | 说明 |
|---|---|---|---|
| etcd | 单 Raft 组 | Raft | 所有 key 在一个 Raft 组 |
| TiKV | Range 分片 + Raft | Multi-Raft | 每个 Region 一个 Raft 组 |
| Redis Cluster | Hash Slot | Gossip + 配置纪元 | 去中心化，无共识 |
| Apache Kafka | 分区 + ISR | 类 Raft (KRaft 3.3+) | 每个分区一个 Leader |
| Consul | 单 Raft 组 | Raft | 服务发现 + KV |
mermaid
flowchart LR
subgraph Dist["分布式数据系统设计三角"]
A["一致性 Hash<br/>数据如何分布到节点?"]
B["Raft / Paxos<br/>多副本间如何达成一致?"]
C["Gossip / SWIM<br/>节点如何发现彼此?"]
end
A <--> B
B <--> C
C <--> A
style A fill:#4CAF50,color:#fff
style B fill:#2196F3,color:#fff
style C fill:#FF9800,color:#fff参考
- Raft: In Search of an Understandable Consensus Algorithm — Diego Ongaro, 2014
- Raft 可视化 — 交互式理解 Raft
- TiKV Raft 实现 — Rust 生产的 Raft 库
- Consistent Hashing and Random Trees (Karger et al., 1997)
- Redis Cluster 规范
- Jump Consistent Hash (2014)
登录后即可发表评论 👇