分布式算法：Paxos 是如何达成共识的？-工具盒子

你好，我是猿java。

提到分布式算法，就不得不说 Paxos算法，曾在一段时间里，Paxos 几乎成了分布式共识的代名词，现如今很多流行的算法，
比如：ZAB，Raft 都是基于 Paxos 改进而来，这足以看出 Paxos的重要性。
但是，由于 Paxos算法比较晦涩难懂，令很多人望而却步。今天我们就来讨论这个为分布式共识算法奠定了基石的开山之作。

申明：

本文的理解是基于作者的原作：https://lamport.azurewebsites.net/pubs/paxos-simple.pdf

因为 Paxos算法涉及到很多专有名词，所以本文尽量保持专有名词的英文格式而非翻译后的中文格式。

Paxos算法是什么 {#1-Paxos算法是什么}

Paxos 发音：[ˈpæksoʊs]，它是由2013年图灵奖获得者，美国科学家 Leslie Lamport(莱斯利·兰伯特)发明的。

首先，Paxos是一种很抽象的学术性算法，作者 Leslie Lamport 本人也是连发三篇文章，以不同的形式来向读者传达其精髓，但是结果并不理想。最终，因为 Google 的行业影响力，才把 Paxos推向了大众的视野。

其次：Paxos是一种共识算法，主要是用于解决分布式系统中，多个节点如何达成一致的问题。比如：从5个人里面选一个Leader，一致性算法就是要保证要么顺利选出一个Leader，
要么因为异常选不出 Leader，而不会选出2个或多个 Leader。

最后：本文章是抽丝剥茧，尽量把学术性的晦涩以更生动形象的图文方式展示。

莱斯利·兰伯特描述的 Paxos算法包括两个部分：

Basic Paxos，也叫做 single-decree Paxos，解决的对单值提案达成共识问题；
Multi-Paxos，主要是分析如何通过执行多个Basic Paxos，解决一系列值达成共识问题；

Basic Paxos {#2-Basic-Paxos}

2.1 三种角色 {#2-1-三种角色}

Basic Paxos算法存在三种角色：Proposer(提议者)、Acceptor(决策者/接受者)、Learner(学习者)。3种角色之间的关系如下图：

Proposer(提议者)：Proposal(提案)的发起者。
Acceptor(接受者)：接收和响应 Proposer(提议者)的PrepareRequest 和 AcceptRequest 请求，参与 Proposer(提议者) 提案的决策。
Learner(学习者)：接受和保存 Proposal(提案)结果，不参与提案和决策过程。

2.2 如何达成共识 {#2-2-如何达成共识}

在分析如何达成共识之前，先看一张 Paxos算法核心工作流程图：

从核心工作流程图可以看出，Basic Paxos算法是分3个阶段来工作：前 2 个阶段围绕某个值达成共识，第 3 个阶段是将共识结果通知所有的副本。
作者莱斯利·兰伯特使用 Proposal[n,v] 代表一个提案,其中 n 为提案编号，v 为提议值。整个流程可以描述如下：

目标：Proposer 需要对 V(default) 达成共识

Prepare phase(准备阶段):

Proposer(提议者) 生成提案编号n，然后向所有的 Acceptor(接受者) 广播 PrepareRequest[n] 准备请求，
Acceptor(接受者) 接收到 PrepareRequest[n] 准备请求后，会做如下处理：

|---------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 | if (n > max(rx'd PrepareRequest)){ if(has accept proposal[m,w]){ promise(承诺)不再响应小于编号n的 PrepareRequest; promise(承诺)不再 accept(接受)小于等于编号m的提案值; return PrepareResponse[Proposal[m, w]]; }else { promise(承诺)不再响应小于编号n的 PrepareRequest; promise(承诺)不再 accept(接受)小于等于编号n的的提案值; return PrepareResponse[None]; } }else { 丢弃请求,不做响应 } |

Accept phase(接受阶段)

当 Proposer(提议者) 收到了大多数 Acceptor(接受者)的 PrepareRequestResponse 响应后，会做如下的操作：

|---------------------|-----------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 | if(PrepareResponse has acceptValue]){ set v = max number's acceptValue }else { set v = Vdefault } broadcast AcceptRequest[n,v]; |

Acceptor(接受者) 在收到大多数 Acceptor的 AcceptResponse[m,w] 响应后，会做如下的操作：

|-----------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 | if(AcceptResponse has any rejections){ set v = max rejections number's acceptValue Re-establish consensus with v; // 重新对reject中的值进行共识 }else { consensus success and commit consensus value; // 共识成功，通知其他的副本 } |

Commit Phase(提交阶段)

当集群对提案值v 达成共识后，需要通知其他所有副本。

下面通过一个由节点1，节点2，节点3，节点4，节点5 五个节点组成的集群进行详细描述：

场景1：只有一个Proposer(提议者)

客户端A 向节点1发起"设置name=猿java"的请求。因此，节点1被提为 Proposer(提议者)，集群中的所有节点(包括节点1)称为"决策者"，如下图：

准备阶段

Proposer(提议者) 也就是节点1，生成提案编号n，并向所有的 Acceptor(接受者) 广播 PrepareRequest[n] 请求，当 Acceptor(接受者) 接收到 PrepareRequest[n]请求后，会作出如下响应：

由于节点1、节点2、节点3之前未响应任何 PrepareResponse 和 AcceptResponse 请求。因此，在收到 PrepareRequest[n] 请求后，会直接给出一个 PrepareResponse[n,none] 的响应，并且承诺不会接受比编号n更小的提案。
此时，节点4、节点5 未对 PrepareRequest[n] 做出响应。

准备阶段后，各节点的提案编号和提案值分别为：

| 节点名 | 节点1 | 节点2 | 节点3 | 节点4 | 节点5 | |------|-----|-----|-----|-----|-----| | 提议编号 | n | n | n | 无 | 无 | | 提议值 | 无 | 无 | 无 | 无 | 无 |

注意：准备阶段，只需要向决策者发送提案编号，不需要发送提案值；

接受阶段

Proposer(提议者) 在收到大多数 Acceptor 的 PrepareResponse 响应后，判断响应的编号都是n，因此向所有的 Acceptor 广播 AcceptRequest[n,猿java] 的请求；
由于节点1、节点2、节点3之前未响应任何的 AcceptResponse请求，因此收到 PrepareRequest[n,猿java] 请求后，会直接给出一个 AcceptResponse[n,猿java] 的响应，并且承诺，不再accept 比编号n更小的值；
此时，Proposer(提议者) 收到了节点4的 PrepareResponse[n,none] 响应，因为 Proposer(提议者) 已经对编号n 广播了AcceptRequest，所以该响应会被直接忽略；
Proposer(提议者) 收到了大多数 Acceptor(接受者) 的 AcceptResponse[n,猿java] 响应后，会对响应中的 number 进行判断，发现number == n，因此对"value = 猿java" 达成共识；

因此接受阶段过后，各个节点的提议编号和提议值如下表：

| 节点名 | 节点1 | 节点2 | 节点3 | 节点4 | 节点5 | |------|-------------|-------------|-------------|-----|-----| | 提议编号 | n | n | n | n | n | | 提议值 | [n,猿java] | [n,猿java] | [n,猿java] | 无 | 无 |

提交阶段

前面2个阶段已经对"value = 猿java" 达成共识，因此需要将共识结果告知所有的副本，因此提交阶段过后，各节点的提议编号和提议值如下表：

| 节点名 | 节点1 | 节点2 | 节点3 | 节点4 | 节点5 | |------|-------------|-------------|-------------|-------------|-------------| | 提议编号 | n | n | n | n | n | | 提议值 | [n,猿java] | [n,猿java] | [n,猿java] | [n,猿java] | [n,猿java] |

场景2：多个Proposer(提议者)

客户端A 向节点1发起"设置name=猿java" 请求，同时客户端B 向节点5发起"设置name=猿" 的请求。因此，节点1和节点5都被提为 Proposer(提议者)，集群中的所有节点(包括节点1)称为"决策者"，如下图：

准备阶段

Proposer(提议者) 节点1生成提案编号n，节点5生成提案编号m，m > n。并分别向所有的 Acceptor(接受者) 广播 PrepareRequest[n]请求，当 Acceptor(接受者) 接收到 PrepareRequest[n]请求后，会作出如下响应：

由于节点1、节点2之前未做 PrepareResponse 和 AcceptResponse 响应，在收到 PrepareRequest[n] 请求后，会直接给出一个 Proposer(提议者)节点1 PrepareResponse[n,none] 的响应，并且承诺不会接受比编号n更小的提案。
由于节点3、节点4、节点5之前未做 PrepareResponse 和 AcceptResponse 响应，在收到 PrepareRequest[m] 请求后，会直接给出一个 Proposer(提议者)节点5 PrepareResponse[m,none] 的响应，并且承诺不会接受比编号m更小的提案。
此时，节点3在收到 PrepareRequest[n] 请求后，因为响应并承诺过不会响应小于m的请求，所以该请求会被直接丢弃。

准备阶段后各个节点的提案编号和提案值分别为：

| 节点名 | 节点1 | 节点2 | 节点3 | 节点4 | 节点5 | |------|-----|-----|-----|-----|-----| | 提议编号 | n | n | m | m | m | | 提议值 | 无 | 无 | 无 | 无 | 无 |

注意：准备阶段，只需要向决策者发送提案编号，不需要发送提案值；

接受阶段

Proposer(提议者)节点5 收到大多数的 PrepareResponse 响应后，会对响应里面的 number、value进行判断。发现所有的 number=n，value=none。
因此把value设置成v=Vdefault=猿，向所有的 Acceptor(接受者) 广播 AcceptRequest[m,v] 请求，Acceptor(接受者) 收到请求后，作如下操作：

由于节点3、节点4、节点5之前未做 AcceptResponse 响应，在收到 PrepareRequest[m,v] 请求后，会直接给出一个 AcceptResponse[m,v] 的响应。
Proposer(提议者) 收到了大多数 Acceptor(接受者) 的 AcceptResponse后，会对响应中的 number 进行判断，如果 number == m，达成共识，否则，重新对新的value进行共识。

因此接受阶段过后，各个节点的提议编号和提议值如下表：

| 节点名 | 节点1 | 节点2 | 节点3 | 节点4 | 节点5 | |------|-----|-----|---------|---------|---------| | 提议编号 | n | n | n | n | n | | 提议值 | 无 | 无 | [n,猿] | [n,猿] | [n,猿] |

提交阶段

前面2个阶段已经对"value = 猿java" 达成共识，因此需要将共识结果告知所有的副本，因此提交阶段过后，各节点的提议编号和提议值如下表：

| 节点名 | 节点1 | 节点2 | 节点3 | 节点4 | 节点5 | |------|---------|---------|---------|---------|---------| | 提议编号 | m | m | m | m | m | | 提议值 | [n,猿] | [n,猿] | [n,猿] | [n,猿] | [n,猿] |

Multi-Paxos {#3-Multi-Paxos}

在上面的「多个Proposer」案例中，当集群中出现2个或者2个以上的Proposer时，会导致共识失败，需要重新共识，针对这些问题，就需要 Multi-Paxos，它是基于 Basic Paxos 改进而来，主要的改进点为：

只能有一个提议者，角色为Leader，解决了多个提议者同时提交提案带来的冲突甚至活锁的问题；
可以对一系列值达成一致共识；

核心流程图如下：

通过上图，我们可以看到，引入Leader(主节点)后，整个共识过程就变得很简单，整个集群只有 Leader节点能够发起提案，此时系统若要对某个值达成一致，只需要进行一次批准的交互即可。
可是，Leader(主节点)是如何选择出来的呢？在作者的文章中并没有详细的说明，不过，Raft算法是对 Multi-Paxos思想经典的实现，会在后续的文章中进行深入讲解。