对于paxos的理解,以及一个简单的实现

为什么需要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失败的冲突的例子:

最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容