为什么需要paxos

在分布式环境下一份数据存多份. 多副本保证了可靠性, 而副本之间的一致, 就需要paxos这类分布式一致性算法来保证.

不靠谱的复制策略

主从异步复制

1. 主接到写请求
2. 主写入本磁盘
3. 主给客户端应答'ok'
4. 主复制数据到从库

缺点:主磁盘在复制前损坏,数据丢失.

主从同步复制

1. 主接到写请求
2. 主复制日志到从库
3. 从库可能堵塞
4. 客户端一直等待应答'ok',直到所有从库返回.

缺点:一个失联节点造成整个系统不可用.

主从半同步复制

1. 主接到写请求.
2. 主复制日志到从库.
3. 从库这时可能阻塞了.
4. 如果1<=x<=n个从库返回'ok',则返回客户端'ok'

缺点:可能任何从库数据都不完整.

改进复制策略

多数派读写

即每条数据必须写入半数以上的机器,每次读取必须检查半数以上的机器是否有这条
数据.

1. 客户端写入w>=n/2+1个节点,不需要主
2. 多数派读:w+r>n;r>=n/2+1
3. 最多容忍(n-1)/2个节点损坏

缺点:更新时数据不一致.

• 例子1:
  node-1, node-2都写入了a=x,
  下一次更新时node-2, node-3写入了a=y.
  这时, 一个要进行读取a的客户端如果联系到了node-1和node-2, 它将看到2条不同的数据.
  为了不产生歧义,需要添加一个全局时间戳,选择更大的时间戳,忽略更小的时间戳.
  这样就看到了 a=x1,a=y2,通过比较时间戳发现y是新数据所以忽略a=x1.

• 例子2:
  当客户端没有完成一多数派写入,客户端进程就挂掉了
  a=x₁写入了node-1和node-2, a=y₂时只有node-3 写成功了,
  然后客户端进程就挂掉了.
  这时另一个读取的客户端来了,
  如果它联系到node-1和node-2, 那它得到的结果是a=x₁.
  如果它联系到node-2和node-3, 那它得到的结果是a=y₂.
  整个系统对外部提供的信息仍然是不一致的.

image.png

设计一个存储系统

假定我们有一个存储服务

• 一个有3个阶段的存储服务集群
• 使用多数派读写的策略
• 只存储1个变量i
• i每次更新对应多个版本：i1，i2，i3...
• 支持三个命令
  get 获取最新的i。
  set<n> 设置下个版本的i的值为<n>，实现为多数派写。
  inc<n> 对i加<n>，就是生成1个新的版本。

微信图片_20250225175346.png

此时如果2个并发的客户端进程同时inc操作，在多数派读写的实现中，必然会产生客户端a覆盖客户端b的问题，从而导致了更新数据的丢失。

paxos就是为了解决这类问题提出的, 它需要让b能检测到这种并发冲突, 进而采取措施避免更新丢失.

微信图片_20250226182317.png

将上述问题转化一下，我们就得到一个系统设计，i的每个版本只能被写入一次，不允许修改。如果系统设计能满足找个需求，那么x和y的inc命令就可以正常执行了。

如何确定一个iⱼ已经被写入了

在写入前先做一次多数派读，以便确认是否有其他客户端进程已经在写了，如果有，则放弃。

微信截图_20250228111322.png

这里还有一个问题，当客户端x，y同时做写前读的时候，就会判断为没有其他进程写入，造成更新丢失。

微信图片_20250228112207.png

为了解决以上问题，存储节点需要增加一个功能，就是它必须记录谁最后做过一次 写前读 ，并且只允许最后一个完成 写前读 的进程可以进行后续的写入，同时拒绝之前做过 写前读 的进程的写入权限。

可以看到, 如果每个节点都记得谁读过, 那么当Y最后完成了写前读取的操作后, 整个系统就可以阻止过期的X的写入.

这个方法之所以能工作也是因为多数派写中, 一个系统最多只能允许一个多数派写成功. paxos也是通过2次多数派读写来实现的强一致.

微信截图_20250228114402.png

paxos

paxos可以认为是多数派读写的进一步升级, paxos中通过2次原本并不严谨的多数派读写, 实现了严谨的强一致共识算法，解决网络延迟/乱序的问题（所以存储必须是可靠的）。

• 一个可靠的存储系统：基于多数派读写
• 每个paxos实例用来存储一个值
• 用2轮rpc来确定一个值(写入)
• 一个值 确定 后不能修改
• 确定 指被多数派接受写入
• 强一致性

以上就是classic paxos的基本内容，对应的论文是《Paxos Made Simple》

优化

一些术语

• Proposer 可以理解为客户端.
• Acceptor 可以理解为存储节点.
• Quorum 在99%的场景里都是指多数派, 也就是半数以上的Acceptor（n/2+1）.
• Round 用来标识一次paxos算法实例, 每个round是2次多数派读写: 算法描述里分别用phase-1和phase-2标识. 同时为了简单和明确, 算法中也规定了每个Proposer都必须生成全局单调递增的round, 这样round既能用来区分先后也能用来区分不同的Proposer(客户端).
• last_rnd 是Acceptor记住的最后一次进行写前读取的Proposer(客户端)是谁, 以此来决定谁可以在后面真正把一个值写到存储中.
  v 是最后被写入的值.
  vrnd 跟v是一对, 它记录了在哪个Round中v被写入了

phase-1

微信图片_20250303183709.png

微信截图_20250304164859.png

当acceptor收到phase-1的请求时：

• 如果请求中rnd比acceptor的last_rnd小，则拒绝请求（说明请求已经过期，失效）
• 请求中的rnd保存到本地last_rnd，从此这个acceptor只接受带有这个last_rnd的phase-2请求。
• 返回应答，带上自己之前的last_rnd和之前已经接受的v。

proposer-x收到多数(quorum)个应答, 就认为是可以继续运行的.如果没有联系到多于半数的acceptor, 整个系统就阻塞了, 这也是paxos声称的只能运行少于半数的节点失效.

此时proposer面临2种情况：

• 所有应答中都没有任何非空的v，这表示系统之前是干净的，没有值被其他paxos客户端完成了写入，这时候proposer-x继续将它要写的值在phase-2中真正写入到多余半数以上的acceptor中。
• 如果收到了某个应答包含被写入的v和vrnd，这时proposer-x必须假设没有其他客户端正在运行（并发写入），虽然proposer-x不知道对方是否已经成功结束，但任何已经写入的值都不能被修改，所以proposer-x必须保持原有的值，此时proposer-x将看到的最大的vrnd对应的v，作为phase-2阶段将要写入的值，也就是proposer-x执行了一次（不知道是否已经中断的）其他客户端的写入的修复。

当proposer收到phase-1的响应时：

• 如果响应中的last_rnd大于发出的rnd：退出
• 从所有响应中选择vrnd最大的v
• 如果所有响应的v都是空，可以选择自己写入v
• 如果响应不够多数派，

phase-2

微信截图_20250304155953.png

Proposer X将它选定的值写入到Acceptor中, 这个值可能是它自己要写入的值, 或者是它从某个Acceptor上读到的v(修复).

微信截图_20250304160434.png

当然这时(在proposer-x收到phase-1应答, 到发送phase-2请求的这段时间),可能已经有其他proposer又完成了一个rnd更大的phase-1, 所以这时x不一定能成功运行完phase-2.

acceptor通过比较phase-2请求中的rnd, 和自己本地记录的rnd, 来确定X是否还有权写入. 如果请求中的rnd和acceptor本地记录的rnd一样, 那么这次写入就是被允许的, acceptor将v写入本地, 并将phase-2请求中的rnd记录到本地的vrnd中.

例子1（无冲突）

微信截图_20250304164859.png

微信截图_20250304160434.png

例子2（有冲突）

微信截图_20250304172454.png

• x成功完成了写前读取(phase-1), 将rnd=1写入到左边2个acceptor.
• y用更大的rnd=2, 覆盖了x的rnd, 将rnd=2写入到右边2个acceptor.
• x以为自己还能运行phase-2, 但已经不行了, x只能对最左边的acceptor成功运行phase-2, 而中间的acceptor拒绝了x的phase-2.
• y对右边2个acceptor成功运行了phase-2, 完成写入v=b, vrnd=2.

继续上面的例子, 看X如何处理被抢走写入权的情况:

• x成功在左边2个acceptor上运行phase-1之后, x发现了2个被写入的值: v=a, vrnd=1 和 v=b, vrnd=2; 这时x就不能再写入自己想要写入的值了. 它这次paxos运行必须不能修改已存在的值, 这次x的paxos的运行唯一能做的就是, 修复(可能)已经中断的其他proposer的运行.
• 这里v=b, vrnd=2 是可能在phase-2达到多数派的值. v=a, vrnd=1不可能是, 因为其他proposer也必须遵守算法约定, 如果v=a, vrnd=1在某个phase-2达到多数派了, y一定能在phase-1中看到它, 从而不会写入v=b, vrnd=2.

微信图片_20250304182215.png

补充

• paxos还有一个不重要的角色learner,acceptor发送phase-3到所有的learner，让leanrner知道一个值被确定了。
• 多数场合proposer就是1一个learner。
• livelock：
  多个proposer并发对1一个值运行paxos，可能会互相覆盖对方rnd，然后提升自己的rnd再次尝试，然后再次产生冲突，一直无法完成。

multi paxos

约为1轮rpc，确定一个值。

paxos诞生之初为人诟病的一个方面就是每写入一个值就需要2轮rpc:phase-1和phase-2. 因此一个寻常的优化就是用一次rpc为多个paxos实例运行phase-1.

比如, proposer x可以一次性为i₁~i₁₀这10个值, 运行phase-1, 例如为这10个paxos实例选择rnd为1001, 1002…1010. 这样就可以节省下9次rpc, 而所有的写入平均下来只需要1个rpc就可以完成了.

fast paxos

没冲突：1轮rpc，确定一个值。
有冲突：2轮rpc，确定一个值。

fast-paxos通过增加quorum的数量来达到一次rpc就能达成一致的目的. 如果fast-paxos没能在一次rpc达成一致, 则要退化到classic paxos.

• proposer直接发送phase-2
• fast paxos的rnd是0
  0保证他一定小于任何一个classic rnd，所以可以在出现冲突时安全的回退到classic paxos。
• acceptor只在v是空时才接受fast phase-2请求
• 如果发生冲突，回退到classic paxos，开始用一个rnd>0来运行。

微信截图_20250306172103.png

如果fast的多数派也是n/+1=3，当上图中发生冲突的时候回退到classic paxos时，y无法确定那个值是被 确定 的：x0 或者 y0.

如果我们把 fast-quorum 设置为n, 也就是全部的acceptor都写入成功才认为fast-round成功(实际上是退化到了主从同步复制). 这样, 如果X和Y两个proposer并发写入, 谁也不会成功, 因此X和Y都退化到classic paxos进行修复, 选任何值去修复都没问题. 因为之前没有Proposer认为自己成功写入了.

解决方案就是让未确定的值不占据n/2+1个节点中的多数派：

• fast的多数派必须 > n*¾
• fast paxos里的值被 确定 的条件是被 n*¾+1 个acceptor接受。

下面是一个fast-round中X成功, Y失败的冲突的例子: