侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

Paxos

林贤钦
2022-04-24 / 0 评论 / 1 点赞 / 168 阅读 / 2,553 字
温馨提示:
本文最后更新于 2022-04-24,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Paxos

一、Paxos是什么

Paxos算法是基于消息传递且具有高度容错特性的一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一。Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。

虽然Mike Burrows说得有点夸张,但是至少说明了Paxos算法的地位。然而,Paxos算法也因为晦涩难懂而臭名昭著。

分布式问题产生的背景

在常见的分布式系统中,总会发生诸如机器宕机或网络异常(包括消息的延迟、丢失、重复、乱序,还有网络分区)等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中,快速且正确地在集群内部对某个数据的值达成一致,并且保证不论发生以上任何异常,都不会破坏整个系统的一致性。

注:这里某个数据的值并不只是狭义上的某个数,它可以是一条日志,也可以是一条命令,根据应用场景不同,某个数据的值有不同的含义。

image-20220424195030400

Paxos算法运行在允许宕机故障的异步系统中,不要求可靠的消息传递,可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了2F+1的容错能力,即2F+1个节点的系统最多允许F个节点同时出现故障。

二、Paxos相关概念

  • Acceptor:Acceptor 有 N 个,Proposer 提出的 value 必须获得 Quorum的 Acceptor批准后才能通过。Acceptor 之间完全对等独立。
  • Proposer:Proposer 可以有多个,Proposer 提出议案(value)。所谓 value,可以是任何操作,比如“设置某个变量的值为 value”。不同的 Proposer 可以提出不同的 value。但对同一轮 Paxos 过程,最多只有一个 value 被批准。
  • Learner:上面提到只要 Quorum 的 Accpetor 通过即可获得通过,那么 Learner 角色的目的就是把通过的确定性取值同步给其他未确定的 Acceptor。

在具体的实现中,一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。

一个很重要的概念叫提案(Proposal)。最终要达成一致的value就在提案里,Proposer可以提出(propose)提案;Acceptor可以接受(accept)提案;如果某个提案被选定(chosen),那么该提案里的value就被选定了。

”对某个数据的值达成一致“,指的是Proposer、Acceptor、Learner都认为同一个value被选定(chosen)。那么,Proposer、Acceptor、Learner分别在什么情况下才能认为某个value被选定呢?

三、Paxos问题描述

假设有一组Proposer可以提出(propose)value的进程集合。一个一致性算法需要保证提出的这么多value中,只有一个value被选定(chosen)。

  • 如果没有value被提出,就不应该有value被选定, 只有被提出的value才能被选定。
  • 如果一个value被选定,那么所有进程都应该能 学习(learn) 到这个被选定的value。

我们不去精确地定义其活性(liveness)要求。我们的目标是保证最终有一个提出的value被选定。当一个value被选定后,进程最终也能学习到这个value。

Paxos的目标:保证最终有一个value会被选定,当value被选定后,进程最终也能获取到被选定value。

假设不同角色之间可以通过发送消息来进行通信,那么:

  • 每个角色以任意的速度执行,可能因出错而停止,也可能会重启。一个value被选定后,所有的角色可能失败然后重启,除非那些失败后重启的角色能记录某些信息,否则等他们重启后无法确定被选定的值。
  • 消息在传递过程中可能出现任意时长的延迟,可能会重复,也可能丢失。但是消息不会被损坏,即消息内容不会被篡改(拜占庭将军问题)。

四、Paxos算法描述

Paxos算法分为两个阶段。具体如下:

阶段一:

  • Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求
  • 如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案

阶段二:

  • 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对**[N,V]提案Accept请求半数以上**的Acceptor。
  • 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求做出过响应,它就接受该提案

注意:V就是收到的响应编号最大的提案的value,如果响应中不包含任何提案,那么V就由Proposer自己决定

image-20220424203258330

Learner学习被选定的value

image-20220424203736008

五、如何保证Paxos算法的活性

image-20220424203803973

通过选取主Proposer,就可以保证Paxos算法的活性。至此,我们得到一个既能保证安全性,又能保证活性的分布式一致性算法——Paxos算法。

六、Multi-Paxos

Multi-Paxos 可以并发执行多个 Paxos 协议,它优化的重点是把 Propose 阶段进行了合并,这就引入了一个 Leader 的角色,也就是领导节点。而后读写全部由 Leader 处理,Leader 也有任期的概念,Leader 与其他节点之间也用心跳进行互相探活。

另外 Multi-Paxos 引入了两个重要的概念:replicated log 和 state snapshot。

  1. replicated log:值被提交后写入到日志中。这种日志结构除了提供持久化存储外,更重要的是保证了消息保存的顺序性。而 Paxos 算法的目标是保证每个节点该日志内容的强一致性。
  2. state snapshot:由于日志结构保存了所有值,随着时间推移,日志会越来越大。故算法实现了一种状态快照,可以保存最新的日志消息。当快照生成后,我们就可以安全删除快照之前的日志了。
1

评论区