分布式协议paxos讲解

Posted on | Edited on

CAP

说到分布式，首先要说的是CAP。
CAP，指的是：

  • Consistency 一致性，所有节点之间数据是保持一致的。
  • Availability 可用性，向服务发起的请求可以立即得到非错的响应。
  • Partition tolerance 分区容错性，可以容忍由于分区导致的一些异常问题，比容网络延时、通讯异常、服务宕机等等。

CAP理论是由加州大学伯克利分校的计算机科学家埃里克·布鲁尔提出的猜想，时在一个分布式系统中，这三者无法同时满足。后续这个理论得到了证明从而成为一个定理。

CAP不可兼容

对于大多数系统，P分区容错性时最重要的性质（不然还讲分布式做什么:)）因此这套体系关键点在于C一致性和A可用性的矛盾。即在一个拥有大量节点的服务中，如果要保证高可用性，就要有一定的容灾能力，设计上数据存储在多个服务器当中。但在多节点的数据的传输随时可能由于节点宕机、网络延迟等等问题导致数据不可达，那么节点在响应数据请求时，响应结果可能会出现不一致的情况。 如果要保持一致，只能降低可用性（比如在数据不一致时服务不可用等等）。

现在流行的分布式协议，其实都是在CAP中，尤其是CA中找寻一个适当的平衡点，从而有了Base理论：既然无法做到高可用强一致性，那么就选择基本可用最终一致性。

  • BA Basically Available 基本可用性；
  • Soft 软状态；
  • Eventual Consistency 最终一致性。

AP和CP并非绝对

同时在笔者看来，CAP虽是一个定理，但每个分布式协议或者分布式实现，并不是非黑即白的。不是说一个协议，要么说CP，可用性不强，要么是AP，一致性不强。 而是会找寻一些平衡，按照自身的理念去提供最好的服务。

比如，zookeeper是哪种呢？网上大部分会说，zk是CP的， 但笔者看来却并不是。
之所以说zk是cp，是因为zk的writer是全部转发到leader来处理，并在大多数follower认可之后写入成功。因此只要写入了数据就一定是有效且不会丢失的。 但当leader服务宕机之后，需要重新选举leader，才可以继续提供服务，因此zk并不是高可用的。

但在read时，zk为了提高吞吐率，client只要读取follower的数据就ok，那么zk就并非一个强一致的应用。虽然可以通过follower的sync（实时获取leader的最新数据）来处理成读强一致性，但可用性就牺牲太大了。

同时，zk还提供了一种readonly状态机制，即使在zk 进行leader选举时，也可以提供只读服务。那么在一个read远远多于write的场景，zk甚至可以说是满足AP的，read弱一致性，但高可用。

这个世界上没有银弹，对于分布式尤其如此。 固然可能随着技术的更新换代，有些协议或者技术不符合当前场景，但大部分其实是没有优劣之分，只是各有取舍，根据业务的实际场景选择合适的技术方式方案，才是我们开发者所真正需要掌握的技能。

Paxos

paxos是1990年由莱斯利·兰伯特（英语：Leslie Lamport，LaTeX中的「La」）于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。

Basic Paxos

basic paxos是paxos的最初版本，也是最基础的分布式协议。
在协议中，会有几个角色：

  • proposer 提案者。
  • acceptor 提案处理者，针对提案进行判断，通过则提案成为决议。
  • learner 获取所有被批准的提案（决议），用于返回给请求方。

paxos决议的过程如下（摘自维基百科）：

  1. 准备（prepare）阶段：
    1. proposer选择一个提案编号n并将prepare请求发送给acceptors中的一个多数派；
    2. acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息(回复消息表示接受accept)，则acceptor将自己上次接受的提案回复给proposer，并承诺不再回复小于n的提案；
  2. 批准（accept）阶段：
    1. 当一个proposer收到了多数acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和根据P2c决定的value（如果根据P2c没有已经接受的value，那么它可以自由决定value）。
    2. 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即批准这个请求。

流程图如下：

1
2
3
4
5
6
7
8
9
10
假设之前的最新提案号是N-1
Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | 
   X-------->|          |  |  |       |  |  Request 提交数据变更V
   |         X--------->|->|->|       |  |  Prepare(N) prepare1.1 proposer进行提案。新的提案号为N
   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc}) prepare1.2 三台Acceptor发现都是最新的版本，因此做出承诺（不再											   回复小于N的提案）
   |         X--------->|->|->|       |  |  Accept!(N,V) accept1.1 proposer发现多数acceptors回复通过，则提交批准请求
   |         |<---------X--X--X------>|->|  Accepted(N,V) acceptor批准请求，并同步到learners
   |<---------------------------------X--X  Response learners处理准备的决议（V），并返回给客户端,该流程有6步。
   |         |          |  |  |       |  |

流程通过时比较顺利，但在并发环境下，可能会出现资源浪费和活锁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
假设当前最新提案号都是N-1
Client   Proposer      Acceptor     Learner
 | |       | |          |  |  |       |  | 
 X ------->| |          |  |  |       |  |  Request(V) Client1 提交数据变更V
 | X-------->|          |  |  |       |  |  Request(W) Client2 提交数据变更W
 | |	   X----------->|->|->|       |  |  Prepare(N,V) proposer1进行提案，新的提案号是N 
 | |       |<-----------X--X--X       |  |  Promise(N,V) prepare1.2 三台Acceptor发现都是最新的版本，因此做出承诺（不再回复小于N的提案）
 | |       | X--------->|->|->|       |  |  Prepare(N,W) proposer2进行提案，此时并不知道p1的提案，因此提案号也是N。
 | |       | |<---------X--X--X       |  |  Reject(N,W) 根据prepare1.2的协议，acceptors已经回复了proposer1编号为N的提案，针对proposer2,直接否决，并返回最新的提案号为N。
 | |       | X--------->|->|->|       |  |  Prepare(N+1,W) proposer2发现最新的提案号是N，自己保留的已经失效，因此更新提案号(N+1)重新提案。
 | |       | |<---------X--X--X       |  |  Promise(N+1,W) Acceptor判断新的提案编号较新，因此做出承诺（不再回复小于N+1的提案）
 | |       X----------->|->|->|       |  |  Accept!(N,V) 此时proposer1对于proposer2的提交号全局编号的变化并不知情，只知道自身之前提交的prepare已经被acceptors promise了，因此发起批准请求。
 | |       |<-----------|<-|<-|       |  |  Reject(N,V) accept1.2 根据协议，由于acceptors批准p1的请求会违背对于proposer2的承诺，因此拒绝，并返回最能的编号N+1
 | |       X----------->|->|->|       |  |  Prepare(N+2,V) proposer1发现最新的提案号时N+1，自己的已经实效，因此更新提案号(N+2)重新提案。
 .......................

以此类推，proposer1和proposer2的循环由于prepare阶段和accept阶段的交替进行可能无限下去。之所以是活锁是因为如果某个proposer在prepare之后马上accept，则可以解开这个循环。 不过随着节点和并发请求的增多，即使不会出现活锁，也会有大量的资源消耗。

Multi-Paxos

Basic-Paxos之所以出现活锁和计算浪费，是由于basic-paxos有两个阶段，多个proposer会提交多个提案，这些版本在不同阶段中会出现时序上的冲突。

Multi-Paxos为了解决这个问题，设定了一个leader角色。所有的提案，都由leader来发起。同时，由于只有一个proposer（就是leader）来进行提案，避免了编号紊乱的问题，因此可以跳过prepare阶段，直接进行accept:

1
2
3
4
5
6
7
8
9
10
11
Client     Leader       Acceptor     Learner
 X---------->|          |  |  |       |  |  Request(V) 
 | X-------->|          |  |  |       |  |  Request(W)
 | |         X--------->|->|->|       |  |  Accept!(N,I+1,V)  进行提案，新的轮次是N，编号I+1
 | |         |<---------X--X--X------>|->|  Accepted(N,I+1,V) 有两个请求到达leader，但leader先处理第一个
 |<-----------------------------------X--X  Response(V)  client1 的请求处理完成，之后在提案第二个。
 | |         X--------->|->|->|       |  |  Accept!(N,I+2,W) 
 | |         |<---------X--X--X------>|->|  Accepted(N,I+2,W)
 | |<---------------------------------X--X  Response(W) 该流程有4步（注意，这里有两个提交,每个提交时4步）
 | |         |          |  |  |       |  |
通过leader对时序的管理，省略了prepare步骤，减少了2步消息的传输，并且不会出现活锁。

其中，leader的产生是由选举算法产生（下文讲述）。每一轮选举，N递增。 在此维度上增加I，（在某轮选举中递增的编号）。

Fast-Paxos

在并发提交时，会产生大量的冲突，因此Multi-Paxos增加了独一无二的leader角色负责提案。而Fast-Paxos的设计是，客户端直接提交请求导acceptors，减少一步leader的转发；只有当出现消息冲突时，再由leader来负责协调。 这种方式，非常适合并发冲突不严重时处理。
fast-paxos有两个分支，一个有leader的协调者机制，一个是无leader角色的自动协调机制。
我们先看有leader的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Client  Leader      Acceptor      Learner
   |      |        |  |  |  |      |  |
   |      |        |  |  |  |      |  |
   X-------------->|->|->|->|      |  |  Accept!(N,I,W)  直接提案
   |      |<-------X--X--X--X----->|->|  Accepted(N,I,W) 提案确认，成为决议
   |<------------------------------X--X  Response(W)  可以看到，在没有冲突时，该流程有3步,会比multi-paxos减少一步流程。
   |      |        |  |  |  |      |  |
 | X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)  client1 提案V
 X----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)  client2 提案w
 | |      |        |  |  |  |      |  |
 | |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 | |      |<-------X--X->|->|----->|->|  Accepted(N,I,V) client1 的提案V被前两个acceptors批准，并通知leader和learner
 | |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W) client2 的提案W被后两个acceptors批准，并通知leader和learner
 | |      |        |  |  |  |      |  |  由于acceptors的意见不一致，并且没有一个获得多数派，因此learner不会做处理。
 | |      |        |  |  |  |      |  |  !! Detect collision & recover
 | |      X------->|->|->|->|      |  |  Accept!(N+1,I,W) leader发现无法没有一个决议形成多数派，那么根据协调算法，指定W作为提案，重新提交。N+1，用来标识更高的优先级。
 | |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)  acceptors获取到leader的提案，并且编号时N+1（这时client无论再如何重复提交，也无法影响这个决议，因为cleint的提案只能是（N,I+X,X）），N的优先级更高，I增加到多少都无用。
 |<--------------------------------X--X  Response(W)  learner 发现多数派决议，并返回客户端。 这里可以看到，出现冲突时，流程的复杂度时比multi更高。

上述的fast和multi,都有一个leader角色。但leader从哪里来呢，当leader宕机时该怎么产生新的leader呢？这就是分布式中比较有名的选举算法，而fast-paxos的另一个分支—无leader角色的自动协调机制就是为了解决这个问题。 zk的zab协议，以及etcd的raft协议，都是默认采用fast-paxos的这个分支为基础进行leader选举的。

无leader的自动协调，其实就是协调一种固有的机制，那zk为例子，当出现冲突时：

  • 优先选择事务zxid更大的。 zxid是一个64位的数据，前32位是epoch（选举轮次），后32位是事务Id。服务重启时，各个server的zxid相同，只有服务正在运行中leader宕机时，zxid才会不同。通过这个机制，会选择zxid更大的服务器作为leader（zxid最大，数据也最新）
  • 如果zxid相同，优先选择serverId更大的。 serverId是服务器的唯一id，可以区分大小。

通过这种机制，没有leader，也可以合并client和learner:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Client         Servers
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V) client2 提案V
 X-----------?|-?|-?|-?|  Accept!(N,I,W) client1 提案W
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X<>X->|->|  Accepted(N,I,V) 前两台servers批准了V，并向其它servers发送提案。
 |  |         |<-|<-X<>X  Accepted(N,I,W) 后两台servers批准了W，并想其它servers发送提案。
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |  |         X<>X<>X<>X  Accepted(N+1,I,W)  servers都收到到其它servers的提案，由于没有形成大多数，因此进行自动协调，由于N和I相同，因此假设根据后两台servers的机器编号更大，修正提案，批准后两台机器的提案W。
 |<-----------X--X--X--X  Response(W)  W提案形成大多数，形成决议，回复W。
 |  |         |  |  |  |

这里只是一个大体的流程，实际上X<>X<>X<>X Accepted(N+1,I,W) 这一步远比流程中复杂的多，如果有机会再进行说明吧。