Paxos推导过程

paxos 是一个分布式共识算法, 就是用来解决分布式系统中, 多副本数据如何保证读写一致性的问题.

不完美的副本数据同步机制

假设我们有个分布式存储系统, 数据在写入时, 需要把数据写入到其他节点: 副本数据从一个节点复制到其他节点, 有几种复制办法:

• 同步复制
• 异步复制
• 半同步复制

同步复制

# node1, node2, node3 

a=x --> node1 --> node2
              ------> node3
                           --> done

数据在一次写入时, 需要同时写入 node1, node2, node3 三个节点, 写入完成才算是一次写入成功;

同步复制有什么问题:

1. 性能低下; 写入性能会受制于节点数量;
2. 没有容错, 任何一个节点写入失败, 则系统不可用;

异步复制

a=x --> node1 
             --> done
             async( node1  --> node2 ; node1  --> node3 ) 

数据在一次写入时, 只要写入一个节点, 则认定写入成功, node1 写入 node2; node1 写入 node3 是异步复制, 不影响整体写入结果;

异步复制有什么问题:

1. 数据可能存在不一致, 当 async( node1 –> node2) 写入失败时, node2 和 node1 上的数据就不一致;

半同步复制

数据在一次写入时, 数据必须写入一定量的副本(不是全部), 这样多副本则提供了较高的可靠性;

a=x --> node1 
              --> node2
                       --> done
                       async( node1  --> node3 )            

半同步复制存在什么问题:

1. 数据可能不一致, 但比纯异步复制要好, 保证尽可能多的节点能达到一致;

多副本同步如何保证读写一致性

基于以上三种复制的思路, 可以发现半同步复制是比纯异步和纯同步方式更优的解决方案, 可以基于这个思路继续推导;

在半同步复制中, 虽然最终所有节点也可能出现不一致, 但是可以保证大多数的节点达到数据一致, 如果在读取数据时, 也能保证从大多数节点中读, 那基于写入的“大多数一致性” , 数据在读取时, 也能做到读的 “大多数一致性” .

quorum

对于大多数节点的定义: 超过整个集合半数以上的节点, 可以被称为一个 多数派 Quorum , Quorumsize=(N/2)+1; （下文统称为 Quorum），例如，一个三个节点的系统，可能的 Quorum 有如下情况：

node1, node2, node3

1. node1, node2
2. node2, node3
3. node1, node3

在 Quorum 读取时, 可能出现以下情况:

       t1     t2
node1  a=x    a=y
node2  a=x    a=y
node3  a=x    a=x

• t1 时刻, node1, node2, node3 数据一致, 此时读取Quorum: a=x
• t2 时刻, node3 数据有落后, 此时读取Quorum时, 仅 (node1, node2) 这个子集能读取到一致的结果!

增加版本

针对上述这种情况, 考虑 t1 时刻, t2 时刻 node 中的数据存在变化, 其实数据就自然而然带上了版本的概念, 在读取时, 需选取最高版本的数据;

再来看一下 Quorum 的写入，假设有以下场景:

       t1      t2      t3
node1  a=x1    a=x2    a=x3
node2  a=x1    a=x2    a=x3
node3  a=x1    a=x1    [a=x3, a=x2]

• x1 表示第一个版本的x; x2 表示第二个版本的x, 以此类推…
• 数据加入版本之后, 在 t3 时刻, node3 接收到 a=x3, a=x2 两个请求:
• 当写入请求 a=x2 后到, 此时写入会导致 a=x3 被覆盖;

由于给数据加上版本后, 还需要保证数据不被历史版本的数据覆盖, 因此 每个 node 在接收写入请求时, 需要拒绝掉比当前版本更小的数据写入. 因此, 每个node 需要记录自己上一次写入数据的版本.

还有个关键问题是: 版本如何确定?

由于 node 记录了上一次写入的数据版本, 那么在 client 写入之前, 需要先去查询一下当前最新的版本, 版本号也需要遵循多数派Quorum和最新的原则, 然后 client 生成新的版本之后执行写入操作;

并发写入问题

假定此时有两个client p1, p2 并发向 node 写入:

t1 时刻, p1, p2 读取最新的版本, v=2

p1 ----------->    node1,  node2,  node3     <-----------p2   # t1 时刻
                   a=x1,   a=x2,   a=x2

t2 时刻, p1,p2 同时写入, 此时 p1 p2 的版本相同：v=3

p1 ----------->    node1,  node2,  node3     <-----------p2   # t2 时刻
   (v++;a=x3)      a=x1,   a=x2,   a=x2       (v++;a=y3)

t3 时刻, 如果此时 node1 接收了p1, node2 接收了p2, 此时节点的数据完全不一致!

p1 ----------->    node1,  node2,  node3     <-----------p2   # t3 时刻
     (v++;a=x3)    a=x3,   a=y3,   a=x2       (v++;a=y3)

如何解决并发写入的问题?

解决这个问题, node 需要拒绝掉同一个version下的其他 client 的写入, 也就是说 node 需要记录下来最新的verion中, 上一次它同意写入的 client, node 要记住的前提是client 需要提前告知node, 其实就是client 在 t2 时刻之前, 还需要进行一次 Quorum 读, 告诉node, I‘ll write !

另外, 同一个 version 下, node 记录多个 client 的写前读时, 只能记录最后一次的写前读的 client ;

改进后的流程如下:

t1 时刻, p1, p2 读取最新的版本, v=2

p1 ----------->    node1,  node2,  node3      <-----------p2  # t1 时刻
                   a=x1,   a=x2,   a=x2

t2 时刻, node 会记录下最后一次的写前读取的 client p2;

p1 ----------->    node1,  node2,  node3      <-----------p2  # t2 时刻, 写前读取
   (I'll write)    a=x1,   a=x2,   a=x2        (I'll write)
     
p1 <-----------    node1,  node2,  node3                      # t2.1 时刻, node record p1
   (ok)            a=x1,   a=x2,   a=x2
                                     
                   node1,  node2,  node3      ----------->p2  # t2.2 时刻, node record p2
                   a=x1,   a=x2,   a=x2           (ok)

t3 时刻, node 接受了 p2 的写请求, 对于 p1 的写入请求会拒绝, 最终一个 quorum 完成写入;

p1 ----------->    node1,  node2,  node3                      # t3 时刻, p1 写入
   (write,a=x3)    a=x1,   a=x2,   a=x2           
 
p1 <-----------    node1,  node2,  node3                      # t3.1 时刻, reject p1
   (reject)        a=x1,   a=x2,   a=x2

                   node1,  node2,  node3      <-----------p2  # t3.2 时刻, p2 写入
                   a=y3,   a=y3,   a=x2        (write,a=y3)

推导总结

基于上述推导, 如何保证副本同步的强一致性?

• 首先, 基于半同步复制, 通过一个 quorum 的读写, 唯一确认一个值, 当两个客户端同时写入 quorum, 为了防止后到的写入影响quorum的读, 需要给数据加上版本, 一个 quorum 的读写中, 冲突时选择最高版本的值;

• 由于数据加上版本, 所以在写入之前, client 需要通过一次 quorum 读确认最新的版本;

• 当多个 client 发起 quorum 写时, 存在并发问题, 如果两个 client 写前度拿到的最新的数据版本相同时, 此时需要唯一确认一个下次要写入的值, client 进行 quorum 写之前, 需要先通知 quorum, node 记录下次要写入的 client, 并拒绝掉其他的 client;

paxos 算法描述

角色划分

• Proposer：提案发起者，负责提出提案（Proposal）。
• Acceptor：提案接受者，负责对提案进行投票和存储。
• Learner：学习最终被接受的提案（通常是被动接收结果的节点，不参与投票）。

注意这里的三个角色里没有客户端的角色，三种角色都是服务端，算法的流程也是侧重于服务端多个node如何交互；

Client       Proposer          Acceptor          Learner
  |----写请求--->|                  |                |
  |             |---Prepare(n)---->|                |
  |             |<--Promise(n)-----|                |
  |             |---Accept(n,v)--->|                |
  |             |<--Accepted(n)----|                |
  |             |                  |----Learn(v)--->|
  |<----OK------|                  |                |

算法流程

• Prepare 阶段

  • Proposer 生成 全局唯一且递增的提案号 n，向所有 Acceptor 发送 Prepare(n)。
  • Acceptor 收到 Prepare(n) 后：
    • 若 n > max_received_n：
      ✅ 承诺 不再接受 <n 的提案，并返回已接受的最高编号提案 (max_accepted_n, value)。
      ✅ 更新 max_received_n = n。
    • 若 n ≤ max_received_n：
      ❌ 拒绝请求。

• Accept 阶段

  • Proposer 若收到 多数派 Acceptor 的 Prepare 响应：
    • 从所有响应中选择 最高 max_accepted_n 对应的 value 作为提案值。
    • 若所有响应无历史值，可自由决定 value。
    • 向 Acceptor 发送 Accept(n, value)。
  • Acceptor 收到 Accept(n, value) 后：
    • 若 n ≥ max_received_n：
      ✅ 接受 提案，持久化存储 (n, value)。
    • 否则：
      ❌ 拒绝请求。

• Learner 传播

  • 当 多数派 Acceptor 接受 (n, value) 后，Learner 将 value 广播为最终值。

max_received_n 是算法的核心机制，首先，其必须为单调递增，保证在多个提案中，总有一个最大的，也就是 Acceptor 只保留最大的提案号，并拒绝比本地记录小的提案，当一个提案被拒绝时，说明此时的提案号已经不是最新的了，需要重新生成提案；

在Accept阶段，读取提案的数据时，也需要读取 max_accepted_n 最大版本的数据 value ，保证数据是最新的；Acceptor 在此阶段接受到Accept请求时，也判断 n ≥ max_received_n，并且拒绝掉更小编号的提案，这就意味着在两个提案同时发生时，可能会有一个被拒绝：

1. Proposer A 发起提案n=5，进入Accept阶段。
2. Proposer B 发起提案n=6：
3. 在Prepare阶段，Acceptor承诺n=6。
4. Proposer B 发现大多数Acceptor承诺了n=6，进入Accept阶段。
5. Proposer A 的Accept请求因n=5 < 6被拒绝，需重新发起更高编号的提案（如n=7）。
6. 结果：提案n=6成功取代n=5。