Paxos算法推导--《软件架构设计：大型网站技术架构与业务架构融合之道》

Paxos算法解析

本文是阅读自《软件架构设计：大型网站技术架构与业务架构融合之道》 这本书很喜欢，里面有很多干货，本文出自11.2小节

之前看Paxos的证明的时候，就是顺着P1、P2a、P2b、P2c的证明思路往下缕，整个证明过程看着欲仙欲死。而这次看的这个文章，是从一个实际的并发场景，引出Paxos要解决的问题，倒推要解决这个问题需要提供什么能力

Paxos解决什么问题

1. 一个基本的并发问题

先看一下最基本的并发问题，假如我们的集群是一个由单机组成的一个KV集群，那么当客户端并发的发送3个写请求时，最终get(X)时会返回几？

显然，答案是X=1、X=3、X=5都是可能的。这里假如最终X=1，那么其实对应了两种情况。

1. 情况1:集群是无状态的：这里如果集群是一个无脑接受客户端请求的服务的话，那么X=1则说明客户端Client1的请求是最后一个到达服务端的，即在这之前集群已经响应过Client2和Client3。
2. 情况2: 集群是有状态的：Client1的请求最先被响应，集群接受X=1，之后当收到Client2、Client3时，服务端拒绝了该请求并返回之前响应过的X=1。而这也是Paxos协议的一个特点。

###2.什么是“时序”

问题进一步细化，假设KV集群有3台机器，集群内各节点之间互相通信且无leader节点。客户端向集群发送的三个请求分别被三个节点响应并传播。

假设每台机器都把收到的请求按日志存下来（这里的请求可以是客户端向服务端发送的请求，或者是服务端其他Node节点广播下来的请求）。当三个请求执行完毕后，只要三台机器的日志顺序是如图三一样的，那么最终整个集群就是最终一致的集群，结果也就是正确的

通过这个简单的例子就能对“时序”有一个直观的了解：虽然三个客户端是并发的，没有先后顺序，但到了服务器的集群里必须保证三台机器的日志顺序是一样的，这就是所谓的“分布式一致性”。

2.Paxos解决什么问题

在例子中，Node1收到了X=1之后，复制给Node2和Node3；Node2收到X=3之后，复制给Node1和Node3；Node3收到X=5之后，复制给Node1和Node2。客户端是并发的，三个Node之间的复制也是并发的，如何保证三个Node最终的日志顺序是一样的呢？这正是接下来要讲的Paxos要解决的问题！

复制状态机

上文中，每个Node存储日志序列，Node之间保证日志序列完全一样即可。那么可能会有疑问，为啥存储日志，直接存储最终数据不好嘛？

（1）日志只有一种操作，就是append。而数据或状态一直在变化，可以add、delete、update。把三种操作转换成了一种，对于持久化存储来说简单了很多！（2）假如要做多机之间数据同步，如果直接同步状态，状态本身可能有一个很复杂的数据结构（比如关系数据库的关联表、树、图），并且状态也一直在变化，要保证多个机器数据一致，要做数据比对，就很麻烦；而如果同步日志，日志是一个一维的线性序列，要做数据比对，则非常容易！

状态机的原理是：一样的初始状态+一样的输入事件=一样的最终状态。因此，要保证多个 Node 的状态完全一致，只要保证多个Node的日志流是一样的即可！即使这个Node宕机，只需重启和重放日志流，就能恢复之前的状态

因此，就回到了上文最后的问题：复制日志=复制任何数据（复制任何状态机）。因为任何复杂的数据（状态机）都可以通过日志生成！

一个朴素而深刻的思想

当客户端发送3个请求的时候，上图所示的六种可能的序列都是对的。因此需要找一个算法保证虽然客户端是并发的发送请求，但最终集群的Node之间记录的日志序列是相同的。

这里就提出了一个朴素的思想，即全世界对1，2，3……n的顺序的认知是相同的，包括人与机器。即2一定是插在1和3之间。

当集群任一Node收到X=1的请求的时候，假设要把它存放到日志中的1号位置，在存放前都要询问集群剩余的机器是否可以把X=1存放在各自的1号位置上，如果1号位置被占用了则询问2号位置……依次类推。如果大家1号位置没有被占用那么就把X=1存放在自己的1号位置上并周知集群节点也把X=1存放在各自的1号位置上。

这里的关键思想就是，虽然每个Node接受到的请求不同，但大家对1号、2号、3号位置的认知是一样的，大家一起保证1号、2号、3号存储的数据一样即可。

这个例子中，每个Node在存储前，都要先询问一下其余Node，之后在得到肯定答复后再决定把这条日志写到哪个位置，这里有两个阶段，先问再决策，也就是Paxos 2PC的原型。

但这样有一个问题就是各个节点同时收到客户端的请求，在2PC的第一步询问时，1号位置都没有被实际占用呢，因此都准备把请求复制给其余节点，这就造成了冲突。还有另一个问题就是比如Node1询问Node2的1号位置是否空的时候Node2给了肯定答复，然后Node3再询问Node2的时候，Node2又同样给了肯定答复，这就导致Node1和Node3都得到了多数的认可并开始第二阶段。

Basic Paxos就是通过两个方法来解决这些问题。

第1，少数服从多数。Node1在填充1号位置时，发现1号位置的值被大多数人确定了，比如是X=5（Node3占领了这个位置且Node2跟从了Node3），那么Node1就要接受这个事实把自己的1号位置也塞成X=5。然后退而求其次去尝试占领2号位置，若2号位置也被占用则也要把它们的值塞进自己的2号位置去，再尝试看3号位置……

第2，当发现1号位置是空着的时候，就锁定这个位置不允许其余Node再占这个位置，除非它们的权利更大（怎么判断权利呢？没错，又回到上文的朴素思想，3>2>1）

如果发现1号位置为空，在提交的时候发现1号位置被其他Node占了，就会提交失败，重试，尝试第二个位置，第三个位置……所以，为了让1号位置日志一样，可能要重试好多次，每个节点都会不断重试2PC。这样不断重试2PC，直到最终各方达成一致的过程，就是Paxos协议执行的过程，也就是一个Paxosinstance，最终确定一个值。而 Multi Paxos 就是重复这个过程，确定一系列值，也就是日志中的每一条！

接下来将基于这种思想详细分析Paxos算法本身。

Basic Paxos算法

在前面的场景中提到三个Client并发地向三个Node发送三条写指令。对应到Paxos协议，就是每个Node同时充当了两个角色：Proposer和Acceptor

（内心OS：😹，最开始顺着读的时候，只介绍了Proposer和Acceptor两个角色，虽然当时也介绍了说这俩角色可以是同一个人，但其实还是有点懵逼了，在这本书里却实打实的了解了）

当Node1收到Client1发送的X=1的指令时，Node1就作为一个Proposer向所有的Acceptor （自己和其他两个Node）提议把X=1日志写到三个Node上面。

下面详细阐述Paxos的算法细节。首先，每个Acceptor需要持久化三个变量（minProposalId，acceptProposalId，acceptValue）。在初始阶段：minProposalId=acceptProposalId=0，acceptValue=null。然后，既然是2PC，那么自然算法有两个阶段：P1（Prepare阶段）和P2（Accept阶段）。

1.P1(Prepare阶段)

P1a：Proposer广播prepare（n），其中n是本机生成的一个自增ID，不需要全局有序，比如可以用时间戳+IP。

P1b：Acceptor收到prepare（n）

if n > minProposalId,回复 yes
		更新 minProposalId = n(持久化)
		返回(acceptProposalId,acceptValue)
else 
		回复 no

P1c：Proposer如果收到半数以上的yes，则取acceptorProposalId最大的acceptValue作为v，进入第二个阶段，即开始广播accept（n，v）。如果acceptor返回的都是null，则取自己的值作为v，进入第二个阶段！否则，n自增，重复P1a。

2.P2(Accept阶段)

P2a：Proposer广播accept（n，v）。这里的n就是P1阶段的n，v可能是自己的值，也可能是第1阶段的acceptValue。

P2b：Acceptor收到accept（n，v），做如下决策：

if n > minProposalId,回复 yes
		更新 minProposalId = acceptProposalId = n(持久化)
		accpetValue = value
		return minProposalId
else 
		回复 no

P2c：Proposer如果收到半数以上的yes，并且minProposalId=n，则算法结束。否则，n自增，重复P1a。

Multi Paxos算法

1.活锁问题

在前面已经知道，Basic Paxos是一个不断循环的2PC。所以如果是多个客户端写多个机器，每个机器都是 Proposer，会导致并发冲突很高，也就是每个节点都可能执行多次循环才能确定一条日志。极端情况是每个节点都在无限循环地执行2PC，也就是所谓的“活锁问题”。

为了减少并发冲突，可以变多写为单写，选出一个Leader，只让Leader充当Proposer。其他机器收到写请求，都把写请求转发给Leader；或者让客户端把写请求都发给Leader。

leader的选举方式可以自定义，可以简单的无脑取编号最大的节点做leader，leader节点周期的向别的节点发送心跳，比如周期是T，如果一个节点在2T内没有收到比自己编号更大的节点的心跳，那么自己变为leader。这个方案虽然可能造成脑裂问题，但反正Basic Paxos就是无leader的，所以这里及时短暂的出现了脑裂，但只是增大了并发冲突的概率，并不影响算法正确性

2. 性能问题

我们知道Basic Paxos是一个无限循环的2PC，一条日志的确认至少需要两个RTT+两次落盘（一次是 Prepare 的广播与回复，一次是 Accept 的广播与回复）

而Multi Paxos在选出Leader之后，它先广播一次Prepare，一旦超过半数同意，之后对于收到的每条日志直接执行Accept操作。在这里，Perpare不再是对一条日志的控制了，而是相对于拿到了整个日志的控制权。一旦这个Leader拿到了整个日志的控制权，后面就直接略过Prepare，直接执行Accept。从而可以把2PC优化成1PC，也就只需要一个RTT+一次落盘了。

如果有新的Leader出现怎么办呢？新的Leader肯定会先发起Prepare，导致minProposalId变大。这时旧的 Leader 的广播 Accept 肯定会失败，旧的 Leader 会自己转变成一个普通的Acceptor，新的Leader把旧的顶替掉了。

3.被choose的日志，状态如何同步出去

对于Multi Paxos由于是Leader节点不断的广播Accept请求，那么对于一条日志，只有Proposer（也就是Leader） 接收到多数派对Accept请求的同意后，知道这条日志被“choose”了。而各个Accepotor只是被动的接受请求，只能说某个日志该Accept接受了但并不知道是否被集群接受。那么如何把这个信息传递给其他Accepotor。

1. Proposer主动通知

在accept原有的(n,v)基础上，再增加一个参数firstUnchooseIndex

Proposer在广播accept的时候，额外带来一个参数firstUnchosenIndex=7。意思是7之前的日志都已经“choose”了。Acceptor收到这种请求后，检查7之前的日志，如果发现7之前的日志符合以下条件：acceptedProposal[i]==request.proposal（也就是第一个参数n），说明1～6的日志都是来自这个Proposer广播的，leader未发生过切换，那么就把该日志的状态置为choose。

2. Acceptor被动查询

当一个Acceptor被选为Leader后，对于所有未确认的日志，可以逐个再执行一遍Paxos，来判断该条日志被多数派确认的值是多少。比如还是刚才收到firstUnchosenIndex=7的那个Acceptor，当他又收到7～9这三条日志后，被选为Leader，那么就对这3条日志逐个广播确认看看大家是否存储的事一致的

因为Basic Paxos有一个核心特性：一旦一个值被确定后，无论再执行多少遍Paxos，该值都不会改变！因此，再执行1遍Paxos，相当于向集群发起了一次查询！

至此，Multi Paxos算法就介绍完了。