分布式协议Paxos学习笔记

       申明：本文大多数理解和部分图都是本人多standford关于Paxos的学习后，或是翻译或者整理，结合本人自己的理解写下的这篇文章。

       最近几年分布式协议在数据库产品中飞速发展，各大公司都有基于特定场景相应的分布式数据产品出现，国内典型的包括腾讯的基于Paxos的PhxSQL，阿里的X-Paxos AliSQL，以及官方的Group Replication，还有percona 分支的基于Galera 协议的PXC。因此，理解分布式协议尤其重要，深入的理解之后，才能知道它存在的适用场景，才能在合适的业务上充分发挥它的功能。

      本文不讲解其他的分布式协议，包括zookeeper的ZAB协议，以及Paxos的简化版raft的协议，重在讲解分布式协议的始祖Paxos。文中对于Paxos的协议的理解，主要是结合本人在standford的视频课程中的一些学习心得，如果有错误的地方，还请批评指正

      根据CAP协议，在设计系统时，我们知道CA，CP，AP我们只能选一样。当然，在大多数场景下，我们会选择AP（Available，Partition Tolerance ）。在MySQL Group Replication 问世以前，其实官方的版本也做不到强一致性。因为少了强一致性，因此给数据库产品带来了很多诟病。比如，master-slave之间数据有延迟，对于强一致性要求比较高的业务只能读master (比如支付业务部分场景)，虽然MySQL提供了semi-sync功能，但该功能也可能在出现网络问题，或者从库响应过慢等场景下降级为async。除了这些问题外，由于无法做到强一致性，很可能master发生故障是，导致数据还未同步到从库，从而导致数据永久丢失。

那么，paxos协议解决了上述哪些关键的问题：

Paxos协议在节点宕机恢复、消息无序或丢失、网络分化的场景下能保证决议的一致性。

首先，我们来对paxos进行一下分解：

Basic Paxos 可以简单的这么描述 :
              1.一个或多个服务器可以同时发起提议（propose）。
              2.系统必须同意一个被选中的值。
              3.只有一个值被选中。

用一个美国竞选总统的案列来说明上述满足的条件。
           1.一个或多个美国公民可以发起总统选举投票。
             2. 投票委员会必须同意被选中的候选人当选总统。
             3. 只能有一个候选人最终能被选中。

Basic Paxos需要满足的条件

Safety
      1.只有一个值可能被选中。（不可能两个人同时在一次选举中被选为总统）。
       2.服务器永远不会知道一个值被选中，除非它真的被选中（Proposer通过Accept返回值获得选中信息）。

Liveness 
     1. 一些提议的值最终有一个会被选中 （某些提议的候选人中，最终会有一个当选为总统）。
      2.如果一个值被选中，最终会被其他服务器知道 （如果一个候选人被当选为总统，美国公民最终会知道这个结果）。

也就是说，只有一个值被选中。而且这个值只有在被选中以后才能被其他服务器知晓。同时，被选中值的后必须是提议的候选值，一旦被选中，其他服务器最终会知道这个情况。

由此，我们看到，Paxos最终包含二个阶段：发起提议，接受提议值。这里，我们把发起提议的一方称之为 Proposers,把接受提议的一方称之为 Acceptors。

Proposers 
          1.主动：发起一个提议
          2.处理来自用户的请求

Acceptors 
         1.被动：回应Proposers的请求
           2.对Proposers的请求进行判定
           3.存储被选中的值，存储决策过程的状态
           4.希望知道哪个值被选中

 我们首先来看看能否通过一次信息交互来完成提议被选中的情况： 

 分裂
 
 我们可以看到，如果通过一次信息交互，我们无法避免多个值被同时选中的情况。

  冲突1
  

  S3 既接受了S1(red)的提议，又接受了S5(blue)的提议，产生了提议冲突的情况。如果通过一次信息交互，我们无法避免选中的值冲突的情况。

    
  冲突2
  

  S3先接受了S5(blue)的提议，又接受了S1(red)的提议。如果通过一次信息交互，我们无法避免选中的值冲突的情况。

  

    从上述的分析我们可以看到，经过一次信息交互无法避免提议冲突的情况，这个集群中(S1,S2,S3,S4,S5)可能存在多个值被选中的情况。这违背了Paxos关于数据强一致性的要求(只有一个值被选中)。这样的集群在实际的生产环境中也没有太大的意义(在不同的数据库节点中，看到不一样的值)。因此，为了避免这种情况，需要多一次的信息交互来做提前检查，如果已经有数据被确定了，就不在更改。如果还没有值被选中，就使用当前的值作为选中的值。当然，这里存在提议冲突的情况的，如果提议出现了冲突，最后以哪个数据为准呢 ？我们可以通过版本来确定，每一个提议我们给一个版本号，当多个版本出现冲突时，我们可以选择一个大的版本号对应的提议，假设这里的版本号为编号。 我们可以为每个提议设定一个编号，同时编号满足：
             1.每个提议都有一个唯一的编号
             2.大编号的提议优先级比小编号的提议优先级更高
             3.一个提议者可以选择一个新的提议编号，且新的提议编号比它曾见过或使用过的提议编号更大

我们可以这样来定义一个提议编号（Proposal Number):Round Number + Server Id。同时，每个服务器存储 maxRound : 到目前为止所见过的最大的 Round Number。Server Id在集群中每个机器上是唯一的，同时Round Number保持单调递增。这样，既保证了递增关系，同时也保证了每次提议编号唯一。

接下来我们定义如何产生一个新的 Proposal Number: Incr maxRound + Server Id。同时，我们要保证 maxRound 持久化到磁盘上，这样每次crash或者重启后，能保证 Proposal Number不会重复。

有了提议编号，我们继续看看Basic Paxos 如何通过两次交互解决上述冲突的问题 ：

1.Proposal 通过 RPCs广播提议编号。 【Prepare阶段】
             1.找出被确定的值
               2.阻止旧的，未完成的提议继续进行 

2.Proposal 通过 RPCs广播进行进行数据存储。【Accept阶段】
             1.请求 Acceptor接受特定的值

 整个交互Basic Paxos的Lifecycle可以描述如下：

 

在整个paxos两阶段过程中，有三个特别重要的值 : acceptedProposal,acceptedValue,minProposal  ， 每次发起提议都会用到这三个值，并根据这三个值的不同情况做不同的判定。所以，这三个值每次产生之后都需要持久化到磁盘上。这样，才能在服务器restart或者故障情况下，能够正确的执行paxos的二阶段来保证强一致性。整个Lifecycle我们可以这么来理解，每次去提交一个值(Accept)之前，我们需要先检查集群中大多数节点是否之前已经通过对这个值的提议。一旦有某一个节点反馈这个值之前被接受，那我们认为之前对这个值发起过提议，并被某个节点接受。因此，我们选择返回的提议号最大的值替换我们当前的值，也就是最后一次Accept的值来作为当前发起Accept 请求的值。

接下来，我们列举几种可能出现的情况，并看看Basic Paxos 协议是如何来进行实际处理的。

1.如果一个提议发起之前，对应的值已经被大多数Accept，那么这个提议必须使用已经被Accept的值。

2.如果之前提议的值已经被部少分节点Accept，但是还没有被选中。新的提议可以看到之前少部分节点Accept的值。则这个Accept的值会作为新的提议Accept请求的值。

在S5发起编号为4.5的提议之后，Accept 之前，S1的Accept 请求并未被大多数接受。此时，只有S3接受了S1编号为3.1的Accept 请求。在这种情况下，

S5的Parepare 提议返回 AcceptValue 为X，并将X作为Accept的请求值进行提交。

3.如果之前的提议被部分节点Accept，但是还没有被选中。新的提议看不到之前提议的Accept的值。则新的提议的Accept的请求会使用自己的值。

S1的编号为3.1的Accept请求到了S3服务器，但是S3服务器接收到Accept请求后，发现已经存在其他的Prepare请求，且编号为4.5 > 3.1,所以拒绝了S1的Accept的请求。所以

S1收到S3返回的minProposal,发现minProposal（4.5） > 3.1，所以调整自己的Proposal Number，重新发起提议。

通过上面我们可以看到，经过Basic Paxos的两阶段信息交互可以很好的解决冲突产生的情况，并最终就某个值达成一致。当然，由于并发Accept 对冲突进行了重新提议，

那么可能存在下面一种情况:

可以看到，Accept 请求失败，需要不断的重新发起提议。而每次服务器接收到Accept请求后，发现有比Accept 编号大的提议已经Prepare了，所以Proposer（这里为S1,S5）不断的重新发起提议。这种情况被称之为Livelock。

那么，如何避免这种情况的发生呢 ？ 
           1.每次失败后，重新发起提议前，随机delay一段时间。
            2.通过Leader选举，只有Leader有权发起提议。

到这里，针对一个提议的确认（Basic Paxos）就算讲完了。其实，我们看到对一个提议 Basic Paxos 经过了2个阶段。

第一阶段 Prepare 阶段，广播自己的编号到集群中的其他Server，收到提议的Server 如果发现这个提议编号比自己记录的minProposal 大，则将minProposal的值修改为该值。可以认为，接受提议的Server

都会尝试修改自己的minProposal。

第二阶段 Accept 阶段：
      1.(发起端）如果第一阶段有返回 (AcceptedProposal,AcceptedValue)，则选择返回中 AcceptedProposal 最大的AcceptedValue 作为此次Accept 请求的value。否则，使用提议者自己的value。
       2.(接收端）服务器接收到Accept请求后，会将发起者的编号和自己的minProposal进行对比。如果大于等于自己的编号，则认为此次请求有效，进行更改。否则，认为此次请求是一个古老的请求，不予修改。并返回对应的minPorposal给发起方。
       3.(发起端）发起端收到大多数回复后，如果有任何服务器拒绝 Accept (result > 提议编号)，则递增编号，重新发起提议。否则，认为此次提议通过。

这里稍微总结一下 ：

其实，对于除发起提议者以外的其他服务器来说，他们并不知道一个值是否最终被确认。尽管某个值可能被自己Accept，但是是否被大多数Server Accept它是不知道的。只有发起提议方根据返回的结果能确认这个提议是被通过的。简而言之，一个除发起方以外的服务器，如果想知道哪个提议被选中，必须自己亲自执行一遍Paxos协议 。

好了，上面个讲的是对同一个记录如何做到强一致性，也就是Basic Paxos协议的精髓所在。但是在现实的生活的场景中，经常需要对多个不同的记录进行判定。比如我们经常说的MySQL Group Replication，多个节点可以同时写入不同的记录，在这种情况下，如何做到分布式集群间的强一致性呢 ？ 所以这里需要引入日志或者队列，只要保证所有的记录在所有的节点上的日志或者队列中是一致的，最终按照日志或队列的顺序执行，那么数据就一定是一致的。这种对多个不同的记录分别进行Paxos协议的过程，我们称之为Multi Paxos。

当然，要做到分布式集群中日志或队列的一致性，首先要解决记录在日志中位置的问题： 
         如何知道一条记录在日志的位置 ？ （集群中每个节点该日志记录的位置是一致的）

通过之前的Basic Paxos协议，我们知道，每个Server 其实是知道自己发起的提议中，哪些提议是被最终通过的。因此，我们找到我们的日志中第一个没有被确认的提议的位置。将该位置通过Paxos协议广播到集群中的其他节点：

1.如果收到集群中大部分节点返回，这个位置的值是被Accepted 的，则将返回的AcceptedValue 填补在该位置，并将该位置标记为已经通过提议，接着下个位置继续这样查找。如果最终找到一个位置，则通过Accepted请求，尝试将该值存储在集群中节点的这个位置。

如下图：

我们来解释下上述这张图，1，2 ，6，7四个位置，是S1已知的被选中的值位置（通过之前的Paxos协议，并且通过的Accept请求的位置）。3是一个被S2,S3 Accepted，但是并没有确认的位置 。

这个时候，客户端向S1发起了一个新的请求，比如为 insert 记录 M 。这时，S1收到这个请求后，会根据Paxos协议首先发起一个Prepare 广播【Prepare (提议编号，第一个未被确认的位置）】，这里假设编号为1.1，则发起的Prepare过程如下 ：
        1. S1 发起 Prepare (1.1，3)  广播 到集群中所有的Server。
         2. S1，S2，S3 接收到 Prepare 请求后，对比自己记录的minProposal，如果发现自己日志条目的minProposal < 1.1，则记录 minProposal = 1.1 。同时，如果自己对应的日志位置 3上有记录被Accepted过的Value，则返回这个(AcceptedProposal，AcceptedValue）。
         3. S1  接收到大部分节点的回复，并且有节点返回AcceptedValue，将最大的AcceptedProposal对应的AcceptedValue设置为 该日志对应位置 (这里为3)  的值 （这里为C） 。并用该值发起Accept 请求 Accept (1.1, 3, 'C')。
         4. S2，S3 接收到请求后，记录下minProposa=1.1,且直接返回 minProposal （1.1)。S1 接收到请求后，将该位置的值设置为 'C'，并返回 minProposal (1.1)。假设s1,s2,s3 对应位置的minProposal<1.1
         5. S1继续进行 Prepare (2.1，4) 的广播。
         6. S1，S2，S3 接收到请求后，检查自己的日志位置，发现自己日志条目的minProposal < 2.1，则记录 minProposal = 2.1 。同时，如果自己对应的日志位置 4上有记录被Accepted过的Value，则返回这个(AcceptedProposal，AcceptedValue），这里为 (NULL,NULL)。
         7. S1 接收到大部分节点的回复，发现没有节点返回AcceptedValue，则发起Accept 请求。Accept (编号，日志位置，对应的值) = Accept (2.1, 4, 'M' ) 。
         8. S1 接收到大部分节点的回复，并且返回的所有的minProposal中，没有大于发起提议的Proposal Number。此次操作成功结束。

最终日志的记录如下 (此时 S1上第一个未被确认的位置为8)：

到这里，我们已经引入了日志来保证多节点写入通过Paxos协议来保证数据的强一致性。这个时候，我们其实可以看到日志成了整个系统设计的核心。之前Basic Paxos对一条记录的确认，这里变成了对一个Log index 对应记录的确认 。

虽然日志完成了Multi Paxos 来实现多点写入同时保证强一致性的实现，但是同时，对于每条不同的记录都需要进行Basic Paxos 协议来进行判定，在高并发的场景中会带来大量冲突，同时导致大量的重新进行Basic Paxos协议进行判定的情况。而且，每次进行2PC（Prepare, Accept) 也增加了性能开销。那么，有没有什么办法能够提高Multi Paxos协议的性能呢 ？  
          1.选一个Leader，任一时间内只能有Leader发起提议。 
            2.消除大量的Prepare 过程。两阶段变成一阶段。

关于选举Leader，Lamport 老爷的一个简单的实现如下： 
          1.用有最大的ID的Server 作为Leader。 
            2.每一个Server 每隔 T ms都会和集群中的其他节点发送心跳信息。 
            3.如果一个Server 在 2T ms 内没有收到来自 最大ID的Server的 心跳信息，则自己提升为Leader。
            4.作为Leader 可以接受客户端的请求，同时可以作为提议者 (Proposer )和 接受者 (Accepter) 。集群中其他的非Leader节点 如果收到客户端的请求，将会将请求转发到Leader 节点上。 

所以，通过这种方式，就避免了多个节点同时对同一条记录进行写入，产生大量冲突，从而要再次走Basic Paxos 协议的流程。

关于消除大量的Prepare 过程，将两阶段变为一阶段：

1、将对单个记录的提议编号，转变成对整个日志的提议编号。一次提议后获取了整个日志的访问权，后续直接发起Accept 请求。只有在初始阶段发起一次两阶段请求 (Propose，Accept)。

2、Accept 请求除了返回最大的Proposal Number外，还返回noMoreAccepted，表示在这个Proposal Number之后没有提议了。

通过第一种方式，我们就可以将大量的两阶段请求变为一阶段。当我们经过初始的提议后，整个日志记录了该提议者的提议编号。后续这个提议者的请求，都会直接进行Accept。相当于我们进行一次完整的Paxos协议后，获得了整个日志的访问权。这种方式只适合在Leader 写入的环境中，在多master写入环境中，会存在更大的性能损耗。

通过第二种方式，作为发起提议方，可以简单的认为，这个提议之后没有发起过新提议了，因此可以直接Accept。直到Accept被拒绝，则重新发起Prepare 。在集群中只有一个Leader情况下，如果收到大多数节点的回复 noMoreAccepted，则后续无需在进行Prepare 阶段，对于每条日志记录，只需要进行一次Accept就足够了。

到目前为止，整个Multi Paxos 能够在多节点写入或者Leader 写入的情况下正常的运行了。同时还对两阶段做了不同场景的优化。但是，有前面种种信息我们知道，信息在整个集群中其实不是完整的：
      1.日志条目在多数节点执行后就认为成功，就是说还有少部分节点没有收到日志的情况。
      2.只有提议的发起者知道被选中的日志条目。

那么我们怎么让集群中的每个节点都能收到日志，并且知道被选中的日志条目呢 ？ 

       1.后台不断进行Accept 过程，只到集群中所有Server 都收到了日志记录。
       2.跟踪被选中日志的情况。

对于第一点这里不多说了，对于第二点怎么做到呢 ？ 

我们在提议的发起方，将已经被Accepted的日志记录的提议编号 修改为 无穷大 (AcceptedProposal[i] = ∞)。集群中的每个Server 维护一个firstUnchosenIndex，即最早的未被选中的日志记录。有了这两个信息，我们在来看看这怎么通过这两个信息来实现让所有的Server 都知道被选中的日志记录。

      提议者主动Accept通知自己选中的日志记录：
          1.提议者在Accept 请求中包含自己的firstUnchosenIndex
            2.接受到Accept请求的Server，标记所有满足以下条件的日志记录 i 为选中状态 :
                  a.  i < request.firstUnChosenIndex 
                  b.  acceptedProposal[i]  == request.proposal 

       提议者通过发送Accept的方式，告诉其他节点我当前被选中的值。通过后台不断的发送Accept 请求，最终，所有的节点将会了解到日志记录中大部分已经被确认的记录。

       假设有某台Server上有如下日志记录（方框里的值表示的是Accepted的提议编号） 。

从日志中，我们知道 Log Index 1，2，3，5的记录是已经被确认的。4，6 是未被确认的。此时，如果S4 发送一个Accept 来将提议编号为3.4的确认消息告诉 该Server，则发送的信息为：

       Accept (Proposal = 3.4，index = 8 ,value = V,firstUnchosenIndex=7 ) ,这条消息包含的意思为 ： 提议Server的小于7的索引记录都是已经被确认的。如果你有一条编号为3.4的记录，且这条记录的日志索引小于7，那么将这条记录标记为确认 。

这样，这条index 为6，且编号为 3.4的消息在 该Server上就标记为确认了。但同时，在编号为8的索引上，额外引入了一条记录。那么为什么编号为3.4的消息能够被确认呢 ？ 这主要是因为发起提议的一方，已经承诺它自己的日志记录所有小于 7的记录已经全部得到了确认。同时，由于3.4的编号和发起提议的编号相同，可以认为这个提议本来就是发起方提议并确认的编号，而且发起方已经对这个提议进行了确认。因此，这里只需要简单的标记为确认就好了。

       通过这种主动告知的方式，能够解决索引为6的日志记录确认问题。但是索引为4的记录仍然无法得到确认。业务这个索引为4，编号为2.5的记录并没有得到确认，可能在发起方数据已经被覆盖了，可能并不存在提议编号为2.5的记录了。面对这种问题，通过主动告知的方法显然解决不了，这个时候可能还需要另一种被动手段，接受者接收到主动告知Accept 请求后，回复它自身的 FristUnchosenIndex。这样，如果发起者的firstUnchosenIndex > Accepter的firstUnchosenIndex，发起提议的一方不断的在后台发送RPC消息（Success 消息）告知Acceptor 该index上已经被确认的值。

因为 Proposal 的firstUnchosenIndex > Accepter的firstUnchosenIndex，所以Accepter的 firstUnchosenIndex 到 Proposal 的firstUnchosenIndex之间的值在 Proposal 里都已经得到了确认 。因此，Proposal只需要将这之间的值发送给Accepter，Accepter接受到之后更新相应索引条目的记录就好了。即

Proposal 发送 Success (Index,v) 通知Accepter 选中的值

Accepter 接受到之后，将日志索引条目对应的记录更新为已确认 ：
        1.acceptedValue [ index ] = v
          2.acceptedProposal [ index ] = ∞
          3.return firstUnchosenIndex
          4.Proposer 根据返回的firstUnchosenIndex 决定是否继续发送 Success 消息到 Accepter 

讲完了服务端的的强一致性，以及如何通知选中的日志记录扩散到其他的节点，如何将数同步到所有节点。接下来在来说说客户端的协议：

       1.发送命令到Leader节点，如果不知道谁是Leader节点，发送给集群中的任一节点。接收到客户端消息的节点，如果不是Leader节点，将请求转发到Leader节点。
        2.Leader节点阻塞等待，一直到客户端命令被选中，并且被大多数节点执行。
        3.如果客户端命令超时 (比如：Leader节点Crash），客户端重新向其他节点执行命令，最终被重定向到新的Leader，并在新的Leader上重新执行。

      最后讲一讲配置的变更，比如节点id的变化，ip地址的变化，以及集群节点数量的变化对整个Paxos协议的影响。在分布是环境中，因为每个节点都有可能出现故障。因此，整个集群必须有自动剔除故障节点，自动增加或者缩减节点功能，同时不影响真个集群的可用性，而且必须满足集群的安全性。假设集群目前3个节点，要扩容到5个节点，那么对同一个日志索引条目进行Paxos协议流程的过程中，必须对大多数这个概念有一个一致的认知。不能一个提议在配置变更前，大多数为2。一个提议在配置变更后，大多数为3的情况发生。即：

 我们可以看到，同一个索引条目由于提议发起者的配置不同，最后在不同的节点上被确认为不同的值。因此，违背了Paxos协议本身强一致性的初衷。所以，必须通过某种手段来杜绝这种情况发生。

 Paxos解决方案：通过日志来管理配置的变更 :
      配置的变更当做日志记录存储在日志文件中，并和其他日志记录一样复制到集群中的其他节点上。为了避免上述不一致的现象发生，所以必须在配置全部落到每个节点之后，才能使用新的配置。这里使用一种延迟配置生效的机制，确保新的配置能在所有的节点执行成功。即配置信息所对应的日志记录执行后并不会马上生效，而是在执行完后续的 α 条记录之后才使用新的配置 （即第i条记录的配置取决以i-α，假设这里的α=3）。

这里 α =3 ，因此c1执行后，并不是马上生效，需要到第 1+3=4 个索引对应的日志条目发起提议时才生效。c2需要第 5+3=8 个索引对应的日志条目发起提议时才生效。同样，这也就限制了第 i 条 记录未执行前，第 i+α 条记录无法执行。否则，会导致 第  i+α 本来应该用新的配置，但由于新的配置还未执行，最终使用了老的配置，从而再次产生上述新老配置同时生效，从而导致数据不一致的现象产生。在实际的环境中，可以根据并发的要求设置合理的α值，设置的太小，会导致并发严重受限，从而严重影响性能。设置的太大，又会导致配置不能及时生效。当然，在一些紧急情况下，如果α过大，又希望配置能及时生效，可以人为的执行一些空的操作，从而加快配置的生效。 

总结：

Basic Paxos 通过两阶段 Prepare +Accept来保证数据的强一致性。而在实际生产环境中，多个不同的，相互不关联的提议会同时产生，这个时候为了保证强一致性就需要有一个地方能够按照一定的顺序存储操作命令，从而保证集群中所有的节点都按照相同的顺序执行命令，从而来保证数据的强一致性，这就是为什么要引入日志来实现的原因，而数据在日志的中的有序实现就变成了对每个日志条目执行 Basic Paxos协议。同时为了提高Paxos协议的性能又提出了Leader选举以及通过特殊的技巧将Paxos的两阶段变为一阶段来提升Paxos协议的性能。最后介绍了客户端的实现，以及如何实现动态配置的变更，从而不影响集群的对强一致的苛刻要求。本文只是个人对standford关于Paxos学习的一个笔记，文中很多描述可能不太严谨，或者不太清楚，希望看到此篇文章的同学多多提出一些宝贵的意见。