序

在上一篇文章中我主要就分布式系统中的CAP和BASE理论进行了介绍，之后围绕分布式中的一致性协议详细介绍了2pc、3pc的基本理论知识。今天我将接着上一篇中剩下来的内容，继续聊聊paxos算法。

Paxos算法

Paxos算法是由Leslie Lamport于1990年提出的一种基于消息传递的一致性算法，一直以来该算法以难以理解著称，一是因为其Lamport的论文过于抽象，另外一个是因为这真的是一个难以理解的算法。

其实，在查阅了很多的资料之后，我的第一感觉是放弃……但是靠着再看一点可能就能理解的想法，最终还是入了该算法的门。

本篇文章仅仅是作为Paxos算法的入门科普文章，不会涉及到算法的验证，所以我尽可能将算法的运行流程讲解清楚。

前提

首先，需要明确的是Paxos算法不考虑拜占庭将军问题（即消息传递可靠性有保障），Paxos算法假定消息在传递的过程中可以出现任意时长的延迟，可能会重复，会消息丢失，但是消息不会被损坏，即消息内容不会被篡改。

场景

在介绍算法之前，我们先来看一个场景，请你看看这样的场景下是否会出现问题，然后你该如何解决问题：

有个数据存储系统（假设这个系统数据都是存在每台机器上，不会存储到外部数据库中），为了避免系统因为机器宕机而无法对外提供服务，为此该系统采用集群方案，让整个系统以多个节点的方式对外提供服务，集群内每一个节点上都记录了这个系统内的所有数据，这样即使集群中部分节点出现宕机，整个系统依然可以对外提供服务。

集群内的每一个节点都可以单独对外提供服务，即每一个节点都可以接收外部的请求，然后执行相关指令操作，等操作完成之后再将数据同步到其他节点上。

此时就会出现一种情况，当两个请求同时向不同节点（节点A和节点B）发送请求修改相同数据，假设节点A接收的请求是将编号为M的数据金额设置为100，而节点B接收的请求是将编号为M的数据金额设置为300，那么此时两个节点修改各自节点数据之后，向其他节点同步数据的时候就会出现数据不一致问题。

对于上面的问题，你的心里是否有答案能否解决？

解决方案

针对上述问题，我们可以想到的解决方案如下：

每一个节点处理完请求开始同步到其它节点的时候，需要向某个特定的协调者（我们这里暂称为Acceptor）发起请求，告知自己需要开始同步数据，而Acceptor接收同步请求处理逻辑是每一次会接收一个同步请求，然后告知所有节点同时同步该节点发送的同步请求，这样每次先发起请求同步的节点便可以优先将自己的数据同步到其他节点上，而最终所有的点上存储的数据顺序也会是一致的。

遗憾

这样的解决方案看起来还是不错的，但是我们这里考虑的是Acceptor只有一个节点的时候解决方案，而为了保证高可用，Acceptor是万万不可能只有一个节点的，那么如果Acceptor是多个节点的话，上面我们讨论的解决方案还有效吗？十分遗憾，答案是无效。

当存在多个Acceptor节点的时候，如果还是按照上述方案进行节点数据同步的话，数据同步依然会存在问题，因为每一个Acceptor接收到的请求顺序是会存在不同的，所以此时直接同步数据的话，最终的数据是无法保持一致性的。

Paxos算法

针对上述问题，Paxos算法应运而生，Paxos算法主要就是在上述的解决方案基础上，通过多个Acceptor来实现最终的数据一致性，那么我们就来看看Paxos算法是如何实现的。

概念

先来看几个概念，这几个概念会在我们后续的分析中使用到。

• Instance：实例，每一个Paxos的实例都将执行Paxos算法的两个阶段过程，并最终选出唯一的决议（因为我们下文讨论的Paxos算法都是在讨论一个实例内部的两个阶段，所以下文中的讨论都是围绕产生一个提案来的，等到这个提案结束下来之后，如果需要讨论新的提案，就需要在另外一个Instance中）。

• Proposal：提案，类似我们上面说的“请求”。

• Proposer：发起提案（Proposal）的“人”，属于节点中的一个角色

• Acceptor：存储节点，接受、处理和存储消息，属于节点中的一个角色

• Learner：不参与提案和投票，仅仅作为同步数据的节点，Acceptor告诉Learner哪个Value被选定，Learner就认为哪个Value被选定，属于节点中的一个角色

• 每一个节点其自身可以具有多个角色，例如一个节点作为Proposer的同时，这个节点其实也是一个Acceptor。

约束

为了保障Paxos算法的严谨性，我在这里还是要先提一下，后续所有的节点都将按照这一规则执行：

• 只有被提出的提案才有可能被选定（Chosen），如果一个提案没有被提出，那么就永远不会被选定。
• 在每一次的投票阶段，最终有且只有一个提案会被选定，不会出现多个提案被同时选定的情况。
• 如果某个节点认为某个提案被选定了，那么这个提案就必须是真的被选定的那个提案（这里意思是当某个提案被选定之后，你访问任意一个节点获得的提案一定就是被选定的那个提案，不用怀疑）
• 一个Acceptor必须批准它收到的第一个提案。
• 如果编号为M0、Value为V0的提案（即[M0, V0]）被选定了，那么所有比编号M0更高的，且被选定的提案，其Value的值也必须是V0。

执行步骤

Paxos算法也是分为两个阶段，第一个阶段生成提案，第二阶段接受提案，这里截取了Lamport的paxos make simple论文中的阐述。

阶段一：

1. Proposer接收外部client发送的请求，选择一个提案编号n，然后向半数以上的Acceptor发送编号为n的**Prepare请求**

2. 如果一个Acceptor收到一个编号为n的**Prepare请求**，且该编号大于该Acceptor**已经响应过**的所有**Prepare请求编号**，那么就会将它**已经接受过（Accepted）的编号**最大提案作为响应反馈给Preposer，同时该Acceptor将会承诺不再接受任何编号小于n的编号。

   （举个例子，假设该Acceptor已经响应过的提案编号为1，5，7，然后此时编号8的提案过来，那么Acceptor就会将自己响应的编号为7的提案反馈给Proposer，需要注意提案是包含提案编号和提案值的，但是Acceptor不关注提案的值，这里的值最终还是给到Proposer的，也就是最终反馈的是类似[Mn，Vn]的结果）

阶段二：

1. 如果Preposer收到来自半数以上的Acceptor对于其发出的编号为n的Prepare请求的响应，那么它就会发送一个针对[n，Vn]的提案的Accept请求给半数以上的Acceptor。这里的**Vn的值**就是当前**Proposer收到的所有响应中编号最大的提案的value**，如果所有响应没有包含任何提案，那么value的值就由该Proposer自身决定。
2. 如果Acceptor收到一个针对编号为n的提案的Acceptor请求，只要该Acceptor没有对编号大于n的Prepare请求作出响应，它就接受该提案。

下面我们用图表方式来总结一下该算法：

以上就是Paxos算法的执行过程，上面的过程还是存在一些问题的，比如每一个Proposer需要两次rcp请求，两个Proposer提案可能会发生活锁等等，所以上面的Paxos算法也被称为Basic Paxos算法，基本上不会直接应用到真实的工业级环境中。

总的来说Paxos算法主要概念还是比较容易理解的，难的是这个算法的推导和证明过程，但是本文作为科普文章不会去展开推导Paxos算法。