分布式算法详解：从一致性 Hash 到 Snowflake

当一台机器扛不住负载时，我们把数据和服务拆到多台机器上。问题随之而来：缓存该落在哪台机器？多台机器如何对同一个值达成一致？主节点宕机后谁来接班？海量数据每条都需要一个全局唯一 ID，又该怎么发？

分布式算法正是为回答这些问题而生。本文讲透五类经典算法——一致性 Hash、Paxos、Raft、ZAB、Snowflake。它们覆盖了分布式系统里两个最核心的需求：数据如何分布，以及多节点如何达成共识与协作。我们会从最直观的一致性 Hash 讲起，逐步深入到以"难懂"著称的 Paxos，再到为可读性而生的 Raft，再到工程上应用最广的 ZAB，最后落到生成唯一 ID 的 Snowflake。

一、一致性 Hash 算法

1.1 从最朴素的取模说起

假设我们有 3 台缓存服务器，要把用户的请求均匀分发。最直接的做法是对用户 key 做哈希再取模：

serverIndex = hash(key) % 3

只要哈希函数足够均匀，3 台机器分到的请求量大致相等。这套方案在节点数量固定时工作得很好。

但分布式系统的常态是"节点会变"。当流量上涨，我们加一台机器变成 4 台，公式变成 hash(key) % 4。这时灾难出现了：几乎所有的 key 计算出的 serverIndex 都会改变，意味着几乎所有缓存都失效了。下一瞬间，海量请求穿透缓存直接打到数据库，这就是臭名昭著的缓存雪崩。

1.2 单调性问题

上述问题的根源在于算法不满足单调性（Monotonicity）：当节点数量变化时，原本已分配到某节点的 key，应该尽量仍然落在该节点（或新节点），而不是被随机重洗。

1997 年，麻省理工学院的 David Karger 等人提出了一致性哈希（Consistent Hashing），专门解决分布式缓存中的这个问题。

1.3 Hash 环的引入

一致性哈希的核心思路是：把"节点"和"数据"用同一个哈希函数映射到同一个环状地址空间里，再用一个简单的规则让它们配对。

具体做法分三步。

第一步，想象一个首尾相接的环，地址范围是 0 到 2^32 - 1（这是普通 32 位哈希的输出空间）。环上的每个点都是一个哈希值。

第二步，用同一个哈希函数（比如 MD5 或 CRC32）把每台服务器映射到环上的某个点。例如：

hash("ServerA") = 1_000_000
hash("ServerB") = 3_000_000
hash("ServerC") = 7_000_000

第三步，要确定一个 key 存到哪台服务器，同样把它映射到环上，然后沿顺时针方向找到的第一个服务器节点，就是它的归属。如果一直走到环的尽头还没遇到节点，就回到环的起点继续找。

环示意（顺时针方向）：

       0
       |
  ServerC (7,000,000)
       |
       ...
  ServerB (3,000,000) ---- key2 (4,500,000) → 归 ServerC
       |
  key1 (2,000,000) → 归 ServerB
       |
  ServerA (1,000,000)
       |
       ... (回到 0)

key1 落在 ServerA 和 ServerB 之间，顺时针第一个遇到的是 ServerB，所以归 ServerB。key2 落在 ServerB 和 ServerC 之间，顺时针第一个是 ServerC，所以归 ServerC。

1.4 为什么这样能保证单调性

现在往环里加一台服务器 D，hash("ServerD") = 2_500_000。它落在 ServerB（3,000,000）之前。重新看 key1（2,000,000）：原本顺时针遇到 ServerB，现在顺时针先遇到 ServerD，于是 key1 被重新分配给 ServerD。

关键在于：只有落在 ServerB 到 ServerD 这一小段弧上的 key 会迁移，环上其余所有 key 的归属都不变。这正是单调性的体现——新增节点只接管它所在那一段弧的数据，不会影响其他节点。

同理，当某台服务器宕机被移除，它负责的那段弧会被顺时针的下一个节点接管，其余 key 全部不受影响。相比"取模导致几乎全量迁移"，一致性哈希把迁移量降到了 1/N。

新增节点时的数据迁移范围如下图所示，只有新节点所在那一段弧上的 key 会被重新分配：

flowchart TD
    N[新增 ServerD<br/>hash=2,500,000] --> M{key 落在哪个弧段?}
    M -->|落在 A 到 D 之间| S1[仍归 ServerA<br/>归属不变]
    M -->|落在 D 到 B 之间<br/>原属 ServerB| S2[迁移到 ServerD]
    M -->|落在 B 到 C 及之后| S3[归属不变]
    style S2 fill:#fbb,stroke:#333

1.5 数据倾斜与平衡性问题

一致性哈希解决了单调性，却带来了新问题：倾斜（Skew）。

当节点数量较少时（比如只有 3 台），它们在环上的位置很可能极不均匀——三台服务器可能挤在环的一小段里，剩下的绝大部分弧段没有任何节点。结果是某台服务器分到了远超 1/3 的数据，其余两台却很空闲。这就违反了平衡性（Balance）：数据应该尽可能均匀地分布在所有节点上。

更糟的是，节点位置完全由哈希函数决定，是不可控的随机分布。

1.6 虚拟节点

解决办法是虚拟节点（Virtual Node）：让每台物理服务器在环上对应多个虚拟节点，而不是只有一个点。

比如让每台真实服务器对应 150 个虚拟节点，把 ServerA 拆成 ServerA#0、ServerA#1、...、ServerA#149，分别哈希后映射到环上的 150 个位置。当 key 顺时针找到某个虚拟节点时，再还原出它对应的真实服务器。

虚拟节点映射：
  hash("ServerA#0")   = 1_230_000  → A
  hash("ServerA#1")   = 5_670_000  → A
  hash("ServerA#2")   = 8_910_000  → A
  ...
  hash("ServerB#0")   = 2_340_000  → B
  hash("ServerB#1")   = 4_560_000  → B
  ...

虚拟节点数量越大，节点在环上分布就越均匀，数据倾斜就越小。业界经验值是每台真实节点对应 150 到 200 个虚拟节点，此时数据分布的标准差可以控制在 5% 以内。Memcached、Redis Cluster、Cassandra 都采用了这一机制。

虚拟节点还带来一个额外好处：当某台物理节点宕机时，它对应的多个虚拟节点散布在环上各处，它们的负载会被分散到多个不同的下一跳节点，而不是全部压给一台机器，进一步均衡了压力。

1.7 一个简化的 Java 实现

下面是一段剥去工程细节的示意代码，帮助理解虚拟节点如何落地：

public class ConsistentHash {
    // 哈希环：用 TreeMap 的 tailMap 快速找到顺时针下一个节点
    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final int virtualCount = 150;

    // 使用 FNV-1a 这种分布均匀的哈希
    private int hash(String key) {
        int h = 0x811c9dc5;
        for (byte b : key.getBytes()) {
            h ^= b;
            h *= 0x01000193;
        }
        return h;  // 32 位无符号
    }

    // 加入一台真实服务器：在环上撒 virtualCount 个虚拟节点
    public void addNode(String node) {
        for (int i = 0; i < virtualCount; i++) {
            ring.put(hash(node + "#" + i), node);
        }
    }

    // 移除一台真实服务器：清掉它所有虚拟节点
    public void removeNode(String node) {
        for (int i = 0; i < virtualCount; i++) {
            ring.remove(hash(node + "#" + i));
        }
    }

    // key 落到哪台服务器：找环上 >= hash(key) 的第一个虚拟节点
    public String getServer(String key) {
        if (ring.isEmpty()) return null;
        int h = hash(key);
        // tailMap 返回所有 >= h 的入口，取第一个；没有就回到环首
        var tail = ring.tailMap(h, false);
        int nodeHash = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
        return ring.get(nodeHash);
    }
}

TreeMap.tailMap 让"顺时针找下一个节点"从 O(N) 降到 O(log N)，这是工程上把一致性哈希做快的关键。

1.8 小结

一致性 Hash 解决的是数据如何分布的问题。Hash 环保证单调性——节点增减时只有局部数据迁移；虚拟节点保证平衡性——让少量物理节点也能在环上均匀铺开。理解了这两点，再看 Redis Cluster 的 16384 个哈希槽、Memcached 的一致性哈希客户端，思路就一通百通。

二、Paxos 算法

2.1 一个被"垄断"的算法

如果说一致性 Hash 解决的是"数据往哪放"，那 Paxos 解决的是更难的问题：一群互不信任、可能宕机、通过网络异步通信的机器，如何对一个值达成一致。

Paxos 由 Leslie Lamport 在 1990 年提出（论文直到 1998 年才正式发表）。它是如此基础和重要，以至于 Lamport 在 2013 年获得了图灵奖。在 Raft 出现之前，Paxos 几乎是分布式一致性的代名词，后续的 Raft、ZAB、Chubby、Spanner 等多多少少都从它演变而来。

2.2 问题模型：为何这么难

考虑一个三节点集群，要就"下一个写入的值是 X 还是 Y"达成一致。难点有三个。

第一，异步网络：消息可能延迟、丢失、乱序，你永远无法区分"对方宕机了"还是"消息还在路上"。

第二，节点可能宕机：进程随时可能崩溃重启，恢复后需要重新参与。

第三，FLP 不可能性定理已经证明：在纯异步网络里，只要有一个节点可能宕机，就不存在一个确定性算法能保证在有限时间内达成共识。这意味着任何实用算法都必须做出妥协——通常是用"放宽终止性"换取"安全性"：保证已达成的共识不会被推翻，但不保证每次都能在有限时间内结束。

Paxos 给出的妥协方案是：多数派（Majority）。只要集群中过半数的节点还活着并且能互相通信，共识就一定能推进。任意两个多数派必然有交集，这保证了已选定的值不会被覆盖。

2.3 三个角色

Paxos 把参与者抽象为三类角色（一个真实进程可以同时扮演多个角色）。

• Proposer（提议者）：发起提案，提议某个值。
• Acceptor（接受者）：对提案投票，决定是否接受。
• Learner（学习者）：不参与投票，只在被通知后学习已选定的值。

2.4 算法的核心直觉

Paxos 的两阶段看起来绕，但抓住一个直觉就清晰了：用提案编号（Proposal Number）给所有提案排个全局顺序，编号大的提案"更有话语权"，但前提是它必须先听一听别人已经接受了什么。

第二个直觉是：一旦某个值被多数派接受，它就"锁定"了，后续任何提案都只能提议这个被锁定的值，不能改成别的值。这就保证了安全性——共识一旦达成就不会被篡改。

2.5 两个阶段

Paxos 分两个阶段运行。

阶段一：Prepare / Promise（准备 / 承诺）

Proposer 选一个全局唯一且递增的提案编号 n，向所有（或多数派）Acceptor 发送 Prepare(n)。

Acceptor 收到 Prepare(n) 后，检查 n 是否大于自己已经承诺过的最大编号。如果是，Acceptor 做两件事：承诺"以后不再接受编号小于 n 的提案"，并把自己已经接受过的编号最大的提案（如果有的话）一起告诉 Proposer。这个回复叫 Promise(n, acceptedProposal)。如果 n 不够大，Acceptor 拒绝或不予理会。

阶段二：Accept / Accepted（接受 / 已接受）

Proposer 收集到多数派的 Promise 后，决定要 Accept 的值。规则是：如果这些 Promise 里有任何一个带着"已接受的提案"，Proposer 必须采用其中编号最大的那个提案的值（不能再用自己原本想提的值）；如果所有 Promise 都没带已接受值，Proposer 才能用自己的值。

确定值后，Proposer 向 Acceptor 发送 Accept(n, value)。Acceptor 只要还没承诺过更大的编号，就接受这个提案，回复 Accepted(n, value)，并把值告诉 Learner。当多数派 Acceptor 都 Accepted 后，这个值就被选定（Chosen）。

把两个阶段串起来，整个流程如下：

flowchart TD
    P1[Proposer 选编号 n] -->|Prepare n| A1[Acceptor 们]
    A1 -->|Promise n, 已接受值| P2[Proposer 收到多数派 Promise]
    P2 --> D{Promise 是否带已接受值?}
    D -->|是| P3[采用编号最大的已接受值]
    D -->|否| P4[用自己的值]
    P3 --> P5[Accept n, value]
    P4 --> P5
    P5 --> A2[Acceptor 们]
    A2 -->|Accepted n, value| P6[多数派 Accepted<br/>值被选定]
    P6 --> L[Learner 学习该值]

2.6 用一个具体例子走一遍

三个 Acceptor：A1、A2、A3。两个 Proposer：P1 想提议值 X，P2 想提议值 Y。提案编号全局递增。

场景一：只有一个提议者，顺利通过

1. P1 选 n=1，向 A1、A2、A3 发 Prepare(1)。
2. 三个 Acceptor 都还没承诺过任何编号，都回复 Promise(1, null)（没有已接受值）。
3. P1 收到 A1、A2 的 Promise（多数派），发现都没带已接受值，于是用自己的值 X，发 Accept(1, X)。
4. A1、A2、A3 都没承诺过更大编号，都接受，回复 Accepted(1, X)。
5. A1、A2 已接受 → 多数派达成，X 被选定。Learner 学到 X。

场景一的交互时序如下：

sequenceDiagram
    participant P1 as Proposer P1
    participant A1 as Acceptor A1
    participant A2 as Acceptor A2
    participant A3 as Acceptor A3
    P1->>A1: Prepare(1)
    P1->>A2: Prepare(1)
    P1->>A3: Prepare(1)
    A1-->>P1: Promise(1, null)
    A2-->>P1: Promise(1, null)
    A3-->>P1: Promise(1, null)
    Note over P1: 多数派Promise，无已接受值，用X
    P1->>A1: Accept(1, X)
    P1->>A2: Accept(1, X)
    P1->>A3: Accept(1, X)
    A1-->>P1: Accepted(1, X)
    A2-->>P1: Accepted(1, X)
    A3-->>P1: Accepted(1, X)
    Note over P1: 多数派Accepted，X 被选定

场景二：两个提议者竞争，发生抢占

1. P1 发 Prepare(1)，A1、A2 回 Promise(1, null)。P1 还没来得及发 Accept。
2. P2 用更大的 n=2 发 Prepare(2)。A1、A2 此时承诺的最大编号还是 1，2>1，于是回 Promise(2, null)，并把自己对 2 的承诺记下。
3. P1 现在发 Accept(1, X)。但 A1、A2 已经承诺了 2，1<2，拒绝。P1 发现失败，用更大的编号 n=3 重新走阶段一。
4. P2 收到多数派 Promise（A1、A2），都无已接受值，于是发 Accept(2, Y)。A1、A2 已承诺 2，接受，回复 Accepted(2, Y)。Y 被选定。
5. P1 用 n=3 发 Prepare(3)。A1、A2 此时已接受过 (2, Y)，回 Promise(3, (2, Y))——带着已接受值。
6. P1 收到多数派 Promise，发现带着已接受值 (2, Y)，于是被迫采用 Y（不能用 X 了），发 Accept(3, Y)。最终选定的还是 Y。

第 6 步正是 Paxos 安全性的精髓：Y 已经被多数派选定，此后任何提案都只能继续提议 Y，X 永远无法被选定。无论提议者如何竞争、如何乱序，已选定的值不会被推翻。

两个提议者竞争的完整时序如下：

sequenceDiagram
    participant P1 as Proposer P1
    participant P2 as Proposer P2
    participant A1 as Acceptor A1
    participant A2 as Acceptor A2
    P1->>A1: Prepare(1)
    P1->>A2: Prepare(1)
    A1-->>P1: Promise(1, null)
    A2-->>P1: Promise(1, null)
    P2->>A1: Prepare(2)
    P2->>A2: Prepare(2)
    A1-->>P2: Promise(2, null)
    A2-->>P2: Promise(2, null)
    P1->>A1: Accept(1, X)
    Note over A1: 已承诺2，1<2，拒绝
    P2->>A1: Accept(2, Y)
    P2->>A2: Accept(2, Y)
    A1-->>P2: Accepted(2, Y)
    A2-->>P2: Accepted(2, Y)
    Note over P2: 多数派Accepted，Y 被选定
    P1->>A1: Prepare(3)
    P1->>A2: Prepare(3)
    A1-->>P1: Promise(3, (2,Y))
    A2-->>P1: Promise(3, (2,Y))
    Note over P1: 带已接受值，被迫采用Y
    P1->>A1: Accept(3, Y)

2.7 活锁问题

Paxos 不保证终止性，最典型的失败模式是活锁（LiveLock）：P1 用 n=1 Prepare，P2 用 n=2 抢占，P1 用 n=3 反抢占，P2 用 n=4 再反抢占……两个 Proposer 不断用更大的编号互相打断，谁也走不到 Accept，算法无限循环。

工程上的解决办法很简单：每个 Proposer 在失败后随机等待一段时间再重试，让某一个先跑完两阶段。Lamport 自己也提到，这种随机退避足以打破活锁。

2.8 Multi-Paxos：从"选一个值"到"选一系列值"

Basic Paxos 只能对一个值达成共识。但真实系统（比如复制状态机）需要对一系列值（一条条日志）达成共识。如果每条日志都从头跑一遍两阶段，Prepare 的开销太大。

Multi-Paxos 的优化思路是：选出一个稳定的 Leader，由它独占提议权。一旦 Leader 选定，它在第一个提案做完 Prepare 后，后续提案就可以跳过阶段一，直接发 Accept——因为只要 Leader 不变，之前 Promise 的承诺就一直有效。

这正是后续 Raft、ZAB 的雏形：选主 + 日志复制。可以说，理解了 Paxos 的两阶段和"已选定值不可篡改"的安全性，就理解了所有共识算法的骨架。Paxos 的"难懂"，很大程度上在于它把所有工程细节都抽象掉了，只留下最精炼也最烧脑的数学本质。

三、Raft 算法

3.1 为可读性而生的算法

Paxos 之所以难懂，是因为 Lamport 追求最一般化的数学表达，把工程上常见的"选主""日志"等概念都隐藏在了抽象之下。2014 年，斯坦福的 Diego Ongaro 和 John Ousterhout 在论文《In Search of an Understandable Consensus Algorithm》中提出了 Raft，明确把可理解性作为第一设计目标。

Raft 的策略是：把共识问题分解成三个相对独立的子问题，每个子问题都有简单直观的解决方案。这三个子问题是：Leader 选举、日志复制、安全性。整个集群在任何时刻都由一个 Leader 主导，所有写请求都经过 Leader，结构远比 Paxos 的多 Proposer 竞争清晰。

3.2 三种角色与任期

Raft 把节点状态分为三种：

• Follower（跟随者）：被动接收 Leader 的请求，不主动发起。
• Candidate（候选人）：Follower 在选举超时后变成 Candidate，发起选举争夺 Leader。
• Leader（领导者）：处理所有客户端请求，复制日志到其他节点。

Raft 把时间切成一个个任期（Term），任期是单调递增的整数。每个任期最多有一个 Leader。Term 像一个逻辑时钟，所有 RPC 都携带 Term，节点收到更大的 Term 会立刻更新自己的 Term 并回到 Follower 状态。这一机制让"谁更新"有了全局可比的依据，避免了 Paxos 里提案编号竞争的复杂性。

三种角色之间的状态转换关系如下：

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: 选举超时未收到心跳
    Candidate --> Leader: 获得多数派选票
    Candidate --> Follower: 收到更高 Term 或发现合法 Leader
    Candidate --> Candidate: 选举超时重新发起
    Leader --> Follower: 收到更高 Term

3.3 Leader 选举

初始时所有节点都是 Follower。每个 Follower 有一个选举超时时间（Election Timeout），通常随机取 150~300 毫秒。如果在这个时间内没有收到 Leader 的心跳，Follower 就认为 Leader 挂了，自己变成 Candidate，发起新一轮选举。

选举流程：

1. Candidate 把自己的 Term 加 1，投票给自己，进入 Candidate 状态。
2. 向其他所有节点发送 RequestVote(term, candidateId, lastLogIndex, lastLogTerm)。
3. 收到请求的节点，按以下规则决定是否投票：
   • 如果请求的 Term 小于自己的当前 Term，拒绝。
   • 每个 Term 内，每个节点只能投一票（先到先得）。
   • 候选人的日志必须"至少和自己一样新"（比较最后一条日志的 Term 和 Index），否则拒绝——这保证了被选出的 Leader 一定拥有最完整的日志。
4. Candidate 收到多数派的赞成票，就成为该 Term 的 Leader。
5. 新 Leader 立刻向所有节点发心跳（空的 AppendEntries），巩固地位，阻止其他节点发起新选举。

为什么用随机超时？这是 Raft 解决"多个 Candidate 同时竞选导致没人拿到多数派"的关键。每个节点的超时是随机的，最先超时的那个节点大概率先发起选举并先拿到多数票，从而避免分裂投票反复发生。这是一种用随机性打破对称性的简洁手法，和 Paxos 用随机退避打破活锁异曲同工。

选举流程可用下图概括：

flowchart TD
    F[Follower] -->|选举超时| C[Candidate<br/>Term+1, 投自己]
    C -->|广播 RequestVote| V{收到多数派赞成票?}
    V -->|是| L[成为 Leader<br/>立即发心跳]
    V -->|否, 选举超时重来| C
    L -->|收到更高 Term| F
    style L fill:#bfb,stroke:#333

3.4 日志复制

Leader 选出来后，所有客户端请求都发给 Leader。一条写请求的处理流程如下：

1. 客户端发命令 SET x=3 给 Leader。
2. Leader 把命令追加到自己的日志末尾，此时这条日志处于未提交状态。
3. Leader 并行地向所有 Follower 发送 AppendEntries(term, prevLogIndex, prevLogTerm, entries[], leaderCommit)，把这条日志复制过去。
4. Follower 检查 prevLogIndex/prevLogTerm 是否和自己日志对应位置一致（日志匹配属性）。一致就追加日志，回复成功；不一致就拒绝，Leader 会回退 nextIndex 重试更早的日志。
5. 当 Leader 收到多数派的成功回复，就认为这条日志安全提交，把它应用到状态机，并向客户端返回成功。
6. Leader 在后续的 AppendEntries（包括心跳）里携带最新的 leaderCommit，Follower 收到后也把对应日志应用到状态机。

sequenceDiagram
    participant C as 客户端
    participant L as Leader
    participant F1 as Follower1
    participant F2 as Follower2
    C->>L: SET x=3
    L->>L: 追加日志(未提交)
    par 并行复制
        L->>F1: AppendEntries(entries, prevLogIndex)
        L->>F2: AppendEntries(entries, prevLogIndex)
    end
    F1-->>L: 成功(日志匹配)
    F2-->>L: 成功(日志匹配)
    Note over L: 多数派OK，提交，应用到状态机
    L-->>C: OK
    L->>F1: 下次心跳带 leaderCommit
    L->>F2: 下次心跳带 leaderCommit
    Note over F1,F2: 应用到状态机

这里有个精妙之处：Leader 从不覆盖或删除自己的日志，只会强制 Follower 的日志和自己一致。这避免了日志冲突的复杂性，代价是 Leader 必须是最完整的——这正是选举时"候选人日志至少和自己一样新"这一规则保证的。

3.5 安全性

Raft 用几条不变量保证安全性，最关键的是Leader 完整性：一旦某条日志被提交，它在所有后续 Term 的 Leader 日志里都一定存在。这条性质由两个机制共同保证：

• 选举时，候选人必须拥有"至少和自己一样新"的日志才能获得选票。
• 一个日志条目只有被多数派复制后才算提交，而新的 Leader 必然从那个多数派中的某个节点选出，因此它一定包含已提交的日志。

有了 Leader 完整性，状态机的线性一致性就有了保障：所有节点按相同顺序应用相同的已提交日志，最终状态一致。

3.6 成员变更与日志压缩

真实系统还要处理两个问题。

成员变更：往集群里加减节点。直接切换配置有风险——可能同时出现两个不相交的多数派，导致同一个 Term 选出两个 Leader。Raft 用**联合一致（Joint Consensus）**过渡：先发布一个"旧配置 + 新配置"的联合配置，等它提交后再切换到纯新配置，保证过渡期任意时刻都只有一个多数派能达成共识。

日志压缩：日志会无限增长。Raft 用**快照（Snapshot）**解决：定期把已应用的日志状态打包成快照，然后丢弃快照点之前的所有日志。Follower 落后太多时，Leader 直接发送整个快照，而不是逐条回放日志。

3.7 与 Paxos 的对比

Raft 在数学上等价于 Multi-Paxos，但工程表达大不相同：

可以说，Raft 把 Paxos 的"Leader + 日志复制"骨架显式化、规范化了，让工程师能直接照着实现。这正是它今天几乎成为新系统首选共识算法的原因。

四、ZAB 算法

4.1 生产环境里应用最多的一致性协议

Raft 虽好，但在它普及之前，生产环境里应用最广的分布式一致性协议其实是 ZAB（Zookeeper Atomic Broadcast，Zookeeper 原子广播协议）。原因很简单：它专为 Apache Zookeeper 设计，而 Zookeeper 几乎是所有大数据和分布式协调场景的标配——Kafka 用它选 Controller，HBase 用它做 Master 选举，Dubbo 用它做注册中心。生态的庞大让 ZAB 走进了无数生产集群。

4.2 它要解决什么

Zookeeper 提供的是一棵类似文件系统的"数据树"（znode），客户端可以创建、删除、修改节点，也可以监听节点变化。所有写操作必须保证全局一致——所有服务器看到写操作的顺序完全相同。

ZAB 协议保证的核心性质是主备一致性：Leader 把写请求按顺序广播，所有 Follower 严格按相同顺序应用。这比通用 Paxos 更具体，也比 Raft 更强调"顺序保证"——Zookeeper 的 znode 版本号、Watch 通知都依赖这种严格的顺序。

4.3 zxid：贯穿全局的事务 ID

ZAB 用一个 64 位的 zxid（Zookeeper Transaction ID）标识每一次状态变更。zxid 分成两部分：

| 高 32 位：epoch（纪元） | 低 32 位：counter（计数器） |

• epoch：每次 Leader 切换时递增，相当于 Raft 的 Term，标识"第几代 Leader"。
• counter：在同一 epoch 内单调递增，标识该 Leader 任期内第几个事务。

zxid 之所以设计成这种"epoch + counter"的两段式，是为了让两个 zxid 可以直接比较：先比 epoch，epoch 大的一定更新；epoch 相同时比 counter。这在新 Leader 选举时极有用——节点持有更大 zxid 意味着它见过更多/更新的数据，更适合当 Leader。

4.4 两个阶段：崩溃恢复与消息广播

ZAB 把运行过程分成两个不断交替的阶段。

阶段一：消息广播（Broadcast）——正常运行时

这是 ZAB 最常见的状态，流程类似一个简化版的两阶段提交（2PC），但用"多数派"代替"全部确认"：

1. Leader 收到写请求，为它分配一个递增的 zxid，生成事务 Proposal，写入本地日志（不立即落盘）。
2. Leader 把 Proposal 放进每个 Follower 对应的 FIFO 队列，按顺序发送。FIFO 队列保证了发送顺序就是应用顺序。
3. Follower 收到 Proposal，写入本地日志后回复 ACK。
4. Leader 收到过半数ACK（包括自己）后，认为这个 Proposal 可以提交，发送 COMMIT 给所有 Follower。
5. Follower 收到 COMMIT 后，把 Proposal 应用到内存中的数据树。

注意第 2 步的 FIFO 队列是关键：它保证了所有 Follower 收到 Proposal 的顺序完全一致，再加上按序 COMMIT，最终所有节点应用事务的顺序也完全一致。这是 ZAB 比 Paxos 更"专一"的地方——它不追求最通用的一致性，只追求"严格按序广播"这一具体语义。

消息广播阶段的交互时序如下：

sequenceDiagram
    participant L as Leader
    participant F1 as Follower1
    participant F2 as Follower2
    L->>L: 分配zxid, 生成Proposal, 写本地日志
    par FIFO队列按序发送
        L->>F1: Proposal(zxid)
        L->>F2: Proposal(zxid)
    end
    F1->>F1: 写本地日志
    F2->>F2: 写本地日志
    F1-->>L: ACK
    F2-->>L: ACK
    Note over L: 过半ACK(含自己), 发COMMIT
    L->>F1: COMMIT
    L->>F2: COMMIT
    Note over F1,F2: 应用到数据树

阶段二：崩溃恢复（Recovery）——Leader 挂了时

当 Leader 宕机或网络分区导致过半 Follower 联系不上 Leader，集群进入崩溃恢复阶段，要选出新 Leader 并让集群重新一致。恢复分两步。

第一步是发现与选举：各节点互相交换自己见过的最大 zxid，zxid 最大的节点优先成为 Leader 候选（因为它持有最新数据）。经过类似 FastLeaderElection 的投票过程，选出新 Leader。新 Leader 的 epoch 加 1。

第二步是同步：这是 ZAB 最巧妙的部分。新 Leader 上任后，要让所有 Follower 的日志和自己完全一致。它把自己日志里那些已经被过半数节点 ACK 但还没来得及 COMMIT 的 Proposal 重新广播给 Follower；对于 Leader 自己有但还没被过半数 ACK 的 Proposal，直接丢弃（因为它们没形成多数派，不属于已确认事务，丢弃不影响一致性）。同步完成后，新 Leader 才进入广播阶段，对外提供服务。

这种"已确认的补提交、未确认的丢弃"的策略，保证了 Leader 切换后集群状态严格一致，不会出现某个事务在某些节点应用了、在另一些节点没应用的情况。

崩溃恢复阶段的整体流程如下：

flowchart TD
    A[Leader 宕机] --> B[进入崩溃恢复]
    B --> C[各节点交换见过的最大 zxid]
    C --> D[zxid 最大者优先当选新 Leader<br/>epoch+1]
    D --> E{日志同步}
    E -->|已过半ACK但未COMMIT的 Proposal| F[重新广播并补发 COMMIT]
    E -->|未过半ACK的 Proposal| G[直接丢弃]
    F --> H[同步完成, 进入广播阶段]
    G --> H
    style D fill:#bbf,stroke:#333
    style H fill:#bfb,stroke:#333

4.5 一个选举同步的具体例子

假设 5 节点集群，Leader L1 在处理事务 zxid=100（epoch=1, counter=100）时刚把 Proposal 发出去，还没收到多数派 ACK 就宕机了。此时：

• L2 收到了 zxid=100 的 Proposal 并 ACK 了，但没收到 COMMIT。
• L3 也收到了并 ACK 了。
• L4、L5 还没来得及收到 zxid=100。

现在 L1 宕机，进入恢复阶段。各节点把自己最大的 zxid 报上来：L2、L3 是 100，L4、L5 是 99（上一条已提交的）。L2、L3 的 zxid 更大，但 zxid=100 这条 Proposal 实际上没拿到过半数 ACK（只有 L1 自己、L2、L3 三个 ACK，假设 L1 宕机前也算自己的，那确实过半——这里换个例子：只有 L2 一个 ACK，没过半）。

假设只有 L2 一个 ACK，那 zxid=100 没过半，属于"未确认事务"。新 Leader（比如 zxid=99 的 L4 当选，因为它最稳定）会丢弃 zxid=100，让 L2 把这条未确认的 Proposal 也丢弃，从而所有节点回到 zxid=99 的一致状态。

如果 zxid=100 已经过半 ACK（L1、L2、L3 三个 ACK），那它属于"已确认但未提交"。新 Leader（这时会是 L2 或 L3，因为它们 zxid 最大）会重新广播 zxid=100 并补发 COMMIT，让 L4、L5 也应用它，保证这条已确认事务最终被所有节点应用。

4.6 与 Paxos、Raft 的关系

ZAB 不是 Paxos 的简单变种，它和 Paxos 有本质差异：

• Paxos 是 per-instance 的一致性，每个 slot 独立达成共识，不强调全局顺序。
• ZAB 是 primary-backup 模型，强调主节点顺序广播，保证全局操作顺序。
• Raft 也走 Leader + 日志复制路线，和 ZAB 在结构上最接近，但 Raft 的日志匹配靠 prevLogIndex/prevLogTerm 校验，ZAB 靠 FIFO 队列 + zxid。

一个常被忽略的细节：ZAB 的崩溃恢复比 Raft 更"激进"地依赖 zxid 全序比较来选 Leader，而 Raft 用"日志至少一样新 + 随机超时"。两者目标一致——选出数据最全的 Leader——但实现哲学不同。

五、Snowflake 算法

5.1 为什么需要分布式 ID

前面四个算法解决的是"共识"问题，而 Snowflake 解决的是一个看似简单却处处是坑的问题：在分布式环境下，如何给每条数据生成一个全局唯一、趋势递增的 ID。

数据库自增主键在单库时很好用，但分库分表后多库各自自增就会冲突；UUID 能保证唯一，但它完全无序，作为数据库主键会导致 B+ 树索引频繁页分裂，写入性能急剧下降。Twitter 在 2010 年开源了 Snowflake 雪花算法，给出了一种工程上近乎完美的折中方案。

5.2 64 位的精巧切分

Snowflake 把一个 64 位的长整数划分成几段，每段承载不同含义：

 0 | 00000000000000000000000000000000000000000 | 0000000000 | 000000000000
↑     41 bit 时间戳（毫秒级）                  | 10 bit机器 | 12 bit序列号
符号位                                          |   ID       |
(1 bit, 恒为 0)                                 |            |

• 第 1 位：符号位，固定为 0，保证 ID 是正数。
• 第 2~42 位（41 bit）：时间戳，单位毫秒。41 位能表示 2^41 - 1 毫秒，约 69.7 年。一般以某个起始时间（比如系统上线日）为基准计算差值，避免 41 位很快用完。
• 第 43~52 位（10 bit）：机器 ID，能表示 1024 台机器。实际中常拆成 5 bit 数据中心 ID + 5 bit 机器 ID，支持 32 个数据中心、每中心 32 台机器。
• 第 53~64 位（12 bit）：序列号，同一毫秒同一机器内的递增计数，能表示 4096 个。也就是说单机每毫秒最多生成 4096 个 ID。

用图来看 64 位的切分更直观：

graph LR
    S["1 bit<br/>符号位<br/>恒为0"] --- T["41 bit<br/>时间戳<br/>(毫秒)"]
    T --- D["5 bit<br/>数据中心ID"]
    D --- W["5 bit<br/>机器ID"]
    W --- Q["12 bit<br/>序列号"]
    style S fill:#f9f,stroke:#333
    style T fill:#bbf,stroke:#333
    style D fill:#bfb,stroke:#333
    style W fill:#bfb,stroke:#333
    style Q fill:#fbb,stroke:#333

这种切分的精妙之处在于：时间戳占高位，所以 ID 天然趋势递增，写入数据库索引时基本是顺序追加，不会引起页分裂；机器 ID 保证不同机器不冲突；序列号保证同毫秒内不冲突。整个生成过程无需任何节点间通信，纯本地计算，性能极高。

5.3 算一算容量

单机单毫秒 4096 个 ID，换算下来单机每秒约 409 万个 ID。1024 台机器合计每秒约 41.9 亿个 ID——对绝大多数业务绰绰有余。而 41 位时间戳支撑 69 年，足以覆盖任何系统的生命周期。

5.4 一个 Python 实现骨架

class Snowflake:
    # 各字段位数
    WORKER_ID_BITS = 5
    DATACENTER_ID_BITS = 5
    SEQUENCE_BITS = 12

    # 最大值（位掩码）
    MAX_WORKER_ID = -1 ^ (-1 << WORKER_ID_BITS)        # 31
    MAX_DATACENTER_ID = -1 ^ (-1 << DATACENTER_ID_BITS) # 31
    SEQUENCE_MASK = -1 ^ (-1 << SEQUENCE_BITS)          # 4095

    # 位移
    WORKER_ID_SHIFT = SEQUENCE_BITS                     # 12
    DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS          # 17
    TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS  # 22

    # 起始时间戳（假设 2024-01-01）
    TWEPOCH = 1704067200000

    def __init__(self, worker_id, datacenter_id):
        if worker_id > self.MAX_WORKER_ID or worker_id < 0:
            raise ValueError("worker_id 超出范围")
        if datacenter_id > self.MAX_DATACENTER_ID or datacenter_id < 0:
            raise ValueError("datacenter_id 超出范围")
        self.worker_id = worker_id
        self.datacenter_id = datacenter_id
        self.sequence = 0
        self.last_timestamp = -1

    def _now_ms(self):
        import time
        return int(time.time() * 1000)

    def _next_millis(self, last_timestamp):
        ts = self._now_ms()
        while ts <= last_timestamp:
            ts = self._now_ms()
        return ts

    def next_id(self):
        timestamp = self._now_ms()

        # 时钟回拨检查
        if timestamp < self.last_timestamp:
            raise RuntimeError(f"时钟回拨 {self.last_timestamp - timestamp} 毫秒")

        if timestamp == self.last_timestamp:
            # 同一毫秒内，序列号递增
            self.sequence = (self.sequence + 1) & self.SEQUENCE_MASK
            if self.sequence == 0:
                # 序列号耗尽，等到下一毫秒
                timestamp = self._next_millis(self.last_timestamp)
        else:
            self.sequence = 0

        self.last_timestamp = timestamp

        return (
            (timestamp - self.TWEPOCH) << self.TIMESTAMP_SHIFT
            | (self.datacenter_id << self.DATACENTER_ID_SHIFT)
            | (self.worker_id << self.WORKER_ID_SHIFT)
            | self.sequence
        )

核心就是 next_id 里那段位运算：把时间差左移 22 位、数据中心 ID 左移 17 位、机器 ID 左移 12 位，再或上序列号，拼成一个 64 位整数。

5.5 时钟回拨：最棘手的问题

Snowflake 最大的隐患是时钟回拨（Clock Rollback）。系统时钟可能因为 NTP 校时、虚拟机迁移、人为调整等原因向后跳。如果当前时间比上次生成 ID 的时间还早，时间戳这一段就会"倒退"，可能生成和过去某个时刻完全相同的 ID，破坏唯一性。

回拨幅度不同，处理策略也不同。

小幅回拨（几毫秒到几十毫秒）：最简单是直接抛异常或短暂等待，等时钟追上 last_timestamp 再继续。上面的代码就是这种策略。代价是这段时间内无法生成 ID。

中等回拨：可以借用 UUID v1 的思路，分配一段位数做"时钟序列"——每次检测到回拨就把这段加 1，相当于给回拨后的 ID 打个不同的"批次标记"，避免和回拨前的 ID 冲突。代价是占用一部分位数，减少时间戳或序列号位数。

大幅回拨（秒级以上）：通常是系统配置错误或虚拟机迁移，单纯等待不可接受。这时要依赖运维告警，甚至考虑切换到备用的 ID 生成器。工程上一般会把 NTP 配置成"只向前校时、不向后跳"（ntpd -x 的 slewing 模式），从源头避免大回拨。

5.6 缓冲设计提高性能

单纯按上面代码每来一个请求生成一个 ID，在 QPS 极高时仍可能成为瓶颈（频繁取系统时间、加锁）。生产环境常用**缓冲（Buffer）**优化：后台线程批量预生成一批 ID 放进内存队列，业务线程直接从队列取，避免每次生成都走锁和时间调用。

更进一步，类似美团 Leaf 的 Leaf-Snowflake 方案会用双 Buffer：当第一个 Buffer 消耗到一定阈值时，异步启动第二个 Buffer 的预生成；第一个用完无缝切换到第二个。这样即便某次预生成因时钟回拨等卡顿，也有第二个 Buffer 顶住，业务无感知。

flowchart LR
    B[业务线程] -->|取 ID| A[Buffer A<br/>10000个预生成ID]
    A -->|余量低于 20%| T[异步预生成 Buffer B]
    A -->|A 耗尽| SW{无缝切换}
    T --> SW
    SW --> B2[业务线程取 ID ← Buffer B]
    B2 -->|同时| T2[后台再生成新的 A]
    style A fill:#bbf,stroke:#333
    style B2 fill:#bfb,stroke:#333

这种"空间换时间、双 Buffer 平滑切换"的思路，是 Snowflake 在工程上从"能跑"到"扛得住百万 QPS"的关键一跃。

5.7 Snowflake 的思想价值

Snowflake 给出的不仅是一个 ID 生成算法，更是一种思路：把一个长整数按位切分成含义不同的几段，让每段独立承担一种职责（时间、机器、序号），通过位运算高效拼接。这种思路衍生出大量变体——百度 UidGenerator、美团 Leaf、滴滴 TinyID，都基于同样的"位段切分"哲学，只在位数分配、时钟处理、缓冲策略上各有取舍。理解了 Snowflake，再读这些工业级实现就轻车熟路。

六、横向对比与选型

五个算法解决的问题其实分属两类。一致性 Hash 和 Snowflake 处理的是"数据如何分布与标识"，不涉及多节点共识；Paxos、Raft、ZAB 处理的是"多节点如何达成共识"。把它们放在一起对比：

如果要做技术选型：

• 需要把数据均匀分到多台缓存/存储节点，用一致性 Hash。
• 需要一个强一致的 KV / 配置中心，且想自己实现，选 Raft（可读性最好，生态最丰富）。
• 已有 Zookeeper 生态或需要严格顺序广播，用 ZAB（直接用 Zookeeper）。
• 理论研究或对算法通用性有极致要求，研究 Paxos。
• 需要全局唯一、趋势递增的 ID，用 Snowflake 或其工业变体。

结语

这五个算法看似各管一摊，实则共享分布式系统的几条底层逻辑：用多数派对抗少数派故障（Paxos/Raft/ZAB）、用随机性打破对称性死锁（Raft 选举、Paxos 退避）、用分段编码承载多重语义（Snowflake 位段、zxid 两段式、一致性 Hash 虚拟节点）。理解了这些共通的思想，再面对新的分布式场景，就不会被具体算法的名字吓住——它们不过是同一套哲学在不同问题上的投影。

从一致性 Hash 的"环"，到 Paxos 的"两阶段"，再到 Raft 的"强 Leader"、ZAB 的"顺序广播"、Snowflake 的"位段切分"，每个算法都是前人针对一个具体痛点打磨出的解。把它们串起来读，就是一部分布式系统从"能跑"到"可靠"的演进史。