分布式一致性算法——Paxos简介

背景介绍

在分布式系统中，一个核心的问题就是数据一致性问题。Paxos一致性算法是分布式系统中的经典算法，由分布式大师Lamport提出，用来解决一个分布式系统中如何就某个决议（值）达成一致的问题，基于消息传递且具有高度容错性。用好理解的方式说，就是在一个选举过程中，让不同的选民最终做出一致的决定。Lamport本人也因其对分布式系统的杰出理论贡献获得了2013年的图灵奖。

Paxos is a mechanism for achieving consensus on a single value over unreliable communication channels.

Paxos算法分析

分布式一致性问题(The distributed consensus problem）

Consistency
Get multiple servers to agree on state.

Consistenty类型

Strong: 强一致性。要求无论更新操作是在哪一个副本执行，之后所有的读操作都要能获得最新的数据（对用户最友好，但是性能影响大）;

Weak:
弱一致性。用户读到某一操作对系统特定数据的更新需要一段时间，我们称这段时间为“不一致性窗口”。但经过“不一致时间窗口”这段时间后，后续对该数据的读取都是更新后的值 (best effort only, used for cache);

Eventually
最终一致性。是弱一致性的一种特例，保证用户最终能够读取到某操作对系统特定数据的更新(DNS是典型的最终一致性系统)。

在分布式系统中，我们如何能够在多个选项中选择一个单独的动作（action）呢？又该如何让这个动作能以容错（fault-tolerant）的方式来完成呢？这是分布式共识问题的基本问题。这个问题听起来似乎很简单：只需要选择一个节点来做决定嘛！但显然这会引入单点失效问题：如果这个唯一的决策者失效了，那所有其他节点就没有办法知道该采取哪个行动了（这其实违反了接下来要介绍的Paxos原则之一的存活性原则）。那在决策者失效时重新选择一个决策者会如何？但这可能会导致最终有两个决策者，而每个决策者可能做出不同的决定，导致共识不能达成。好吧这个问题似乎不那么简单。让我们来看看Paxos是如何解决这个问题的。

两个原则（requirements）

现在我们已经对这个一致性问题有了直觉上的认识，下面来阐述解决方案的两个原则：安全原则和存活原则。

安全原则 (safety)：系统不会产生“错误”的答案
- 只有被提议（proposed）的值才可能被选中（chosen)
- 只有一个值被选中
- 一个节点永远不会知道一个值已经被选择，除非它本身已经被选中（一旦达成共识，这个事实被公之于众，且不可更改(回退？)）
存活原则 (liveness)：只要多数节点存活并且彼此间可以通信，最终都要做到的事情（正常运行）
- 某个被提议的值最终将被选中
- 如果某个值已经被选中，那么其他节点最终可以学习到这个值

基本假设（assumptions）

除了上述的两条原则之外，我们还需要对分布式系统的工作原理以及可能失效的情形作出一些假设。分布式系统中的节点通信主要存在两种模型：共享内存和消息传递。Paxos算法基于消息传递。在基于消息传递的分布式系统中，不可避免地会出现消息延迟、丢失、重复的情形。此外，在消息传递模型中，节点故障可以分为失效停止（fail stop）和拜占庭错误（Byzantine Failure）（所有不是失效-停止的错误都可以归为拜占庭错误）两大类，基础Paxos算法不考虑拜占庭将军问题。更具体地，基础Paxos算法的基本假设具体如下。

失效-停止
- 失败-停止：当一个节点发生故障时，它将完全停止工作
- 重启：故障的节点重新启动时可以恢复正常操作
消息
- 消息可以丢失
- 消息可以重复发送
- 消息可以延迟(只要等待足够的时间，消息就会被送到),但是消息不会被篡改（即不考虑拜占庭错误）
稳定的存储 假定系统中的节点可以访问某种形式的稳定的存储器，这些存储器可以保存故障之前记录的信息，直到节点重启并从故障中恢复（为什么需要稳定的存储？因为每个节点以任意的速度异步操作，可能因为fail stop而重启。所以任何一个节点都可能会在提议被选择后停机再重启，因此解决方案要求节点必须要能够记忆某些信息，从而能在重启后重新载入）

基本概念

在《Paxos made simple》论文描述中将一致性算法中节点的角色分类3类：proposers, acceptors和learners。不同的角色对应于一致性算法中的不同职责。更具体的，算法描叙相关的基本概念如下：

proposal value: 提议的值
proposal number: 提议编号
proposal: 提议（= 提议编号 + 提议值）
proposor: 提议发起者，提出不同的建议值（proposoal）供决策者考虑。提议是<N, V>对
acceptor：提议接收者，负责达成共识。（接受符合一定限制的提案）
learner：最终决策学习者，不参与提议的处理，学习提议的处理结果。

实际实现中，一个节点往往同时扮演这多个角色（通常是3个）。当在某个提议值上达成共识时我们就说这个值被选出来了。简单起见，在下面的算法分析中，我们只考虑Basic Paxos算法（没有learner这个角色）。

提议编号

Paxos能在不可靠的通信信道上进行操作的关键之一是为每个proposal分配一个唯一的ID。Proposal ID是什么以及为什么重要的细节将在稍后带来，这里我们先将这些ID视为与时间戳（timestamps）类似的角色：它们不仅让peers能从逻辑上判断一条消息是否比另一条消息更新，而且绕开了分布式系统中一致的、共享的时间概念（notions of time）所固有的复杂性。

Proposal ID的常见实现是一个简单的整数和一个用于确保唯一性的一个“tie-breaker”组成数对。这里使用的ID的pair的组合模式是 < Integer, 节点的ID（具有唯一性）>，例如，（1，A）。这些ID是可比较的。为了确定哪个ID在逻辑上更新，第一个整数首先以正常的方式进行比较，并且如果它们相等，则将这些唯一的ID字符串进行字典序比较以打破不分胜负的局面，因而有（5，B）>（4，B）>（4，A）。

ID的主要目的是保护算法免受延迟和/或重复的消息的影响。 Paxos使用一个非常简单的规则来实现这一点。如果新收到的消息的ID大于上一个处理的消息的ID，则对其进行处理。否则忽略这条消息。忽略延迟信息的动机并不像忽略重复消息那样显而易见，其原因来自于在Paxos这样一个多步骤的算法中, 与旧的和过期的step相关的消息不被允许干扰当前active step的消息。

Paxos算法流程

Paxos算法具体分为两个阶段。

第一阶段（prepare）：提议者选择一个全局唯一的建议值n，并向多数的（过半）接受者（majority of acceptors）发送一个准备请求（prepare request）：prepare(n)。如果一个接受者接收到一个值为n的准备请求，且该请求值比它看到的任何请求值都大，那么它对该请求作出确认答复promise(n)，承诺不再接收任何小于这个n的提议（并且包括它已经接收了的编号最高的提案（如果有的话））
第二阶段（accept）：如果proposer收到过半的acceptor的确认消息表示他们不会接受n以下的提议, 那么这个proposer给这些acceptor返回附带他的建议值v的确认消息（Accept(n, v)）. 如果一个acceptor收到这样的确认消息{n, v}, acceptor就会接受它(Accepted(n, v)). （除非在此期间acceptor又收到了一个比n更大的提议.）

Basic Paxos算法流程具体流程如下图：

这里还需要对一个提议值被选择的概念做一个阐述：一个提议值value被选择当且仅当在上述算法的第二阶段超过半数的接收者接收了该值。这里有必要对Paxos算法里的这个majority这个概念多加阐述。

强大多数（Strong Majority/Quorum): 一组由一半以上的接受者组成的集合。

通过上面的描述可知，在节点间达成共识的关键思想就是这个“强大多数”的概念。这个概念的特殊之处在于：任意两个“强大多数”的集合都至少有一个共同的成员节点。Paxos算法通过让提议者向“强大多数”的接收者发送提议来利用这个特性：如果我们可以得到超过半数的节点来对某个单一的提议值达成共识，那么我们已经达成一致；因为所有其他Quorum将包含至少一个此Quorum的节点，而交集内的进程就可以保证正确性被继承，以后被传播出去。同时，这也意味着我们一次可以容忍的错误节点的数量：若正常工作的节点小于等于半数个节点，就不可能形成多数。

那为什么要分为两个阶段呢？先说一下prepare阶段的作用。第一，检查是有已经有被批准的值，如果有的话，就用被批准的值。第二，如果之前存在提议还没有被接受，则干掉他们（以便不让他们和我们发生竞争）。

第一阶段中proposal ID (即prepare()发送的n)有什么特性呢？Paxos算法要求Proposal ID全局唯一且递增。为什么要这样设计呢？这个ID实际上相当于一个虚拟时钟（virtual clock), 所有的acceptors都会使用这个ID，用来保证当它收到任意节点发来的消息时，该消息是最新的（或者说是目前处于Paxos算法最新一轮的消息）而不是过时的消息（系统异步环境下消息的允许任意延迟）。事实上，全局唯一ID（且递增）的生成本身是需要一定的技术来保证的：毕竟需要同时满足高并发、高可用、低延迟这样的需求可不简单，例如，微信的seqvr系统就是专门用来做这种序列生成的。

是不是算法已经完全没有问题了呢？根据上述过程，当一个proposer发现存在编号更大的提案时将终止提案。这意味着提出一个编号更大的提案会终止之前的提案过程。如果两个节点在这种情况下都转而提出一个编号更大的提案，就可能陷入活锁（live lock），违背了liveness的原则。这种情况下的解决方案是选举出一个leader（leader election），仅允许leader提出提案。但是由于消息传递的不确定性（异步通信模型），可能有多个proposer自认为自己已经成为leader,也就是没有达成谁是leader的consensus。

一个示例（不考虑failures）

2个proposor, 3个acceptor, 1个learner.

Phase 1: Prepare/Promise

Proposor A和Proposal B分别向3个acceptors发送准备请求prepare(2)和prepare(4).

Prepare(2)率先到达Acceptor X,Y. 这两个acceptor向A作出确认答复Promise(0,null)。
Prepare(4)率先到达Acceptor Z. Z向B作出确认答复Promise(0,null)。

Proposor B的Prepare(4)之后于A到达Acceptor X,Y. X,Y检查发现该请求值（4）比它看到的任何请求值都大（最大是之前A发来的prepare(2)）,那么它对该请求作出确认答复promise(2,null)。

Proposor A的Prepare(2)之后于B到达Acceptor Z.因为请求值（2）小于之前处理的最大请求值4，该消息被忽略。

Phase 2: Accept/Accepted

Proposal A收到了2/3(超过半数)的promise消息，于是给这些acceptor返回附带他的建议值v的确认消息Accept(2,100). 因为在phase1之后所有的acceptor都看到了目前最大的promise值是B发来的4，所以A本次发给acceptors的accept消息都将被忽略。

Proposal B也收到了3/3(超过半数)的promise消息，于是给这些acceptor返回附带他的建议值v的确认消息Accept(4,50). Acceptor X，Y, Z检查本地最大提议值和Accept的ID相同，于是将<4,50>写入本地，并返回Accepted（）消息表示确认接受。Learner会学习到这一情况并把value=50被选择的情况记录下来，并告知proposer A.

Paxos的属性

Paxos的属性论文里有详细列出，为了完整起见，我还是列在这里，完整的推导过程可以参见维基百科上的Paxos算法。

P1：一个acceptor必须接受（accept）第一次收到的提案。
P2：一旦一个具有value v的提案被批准（chosen），那么之后批准（chosen）的提案必须具有value v。
- P2a：一旦一个具有value v的提案被批准（chosen），那么之后任何acceptor再次接受（accept）的提案必须具有value v。
- P2b：一旦一个具有value v的提案被批准（chosen），那么以后任何proposer提出的提案必须具有value v。
- P2c：如果一个编号为n的提案具有value v，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于n
  的任何提案，要么他们已经接受（accept）的所有编号小于n的提案中编号最大的那个提案具有value v。

Paxos算法主要贡献

Paxos算法是第一个被证明的一致性算法，也是最著名的分布式一致性算法。Google的粗粒度锁服务Chubby的底层一致性实现就是以Paxos算法为基础。用户只需调用Chubby的锁服务接口就能够实现分布式系统中多个进程之间粗粒度的同步控制，从而保证分布式数据的一致性。Chubby的开发者对Paxos曾有过这样的评价：“所有的一致性协议本质上要么是Paxos，要么就是其变体”。

小结

Paxos算法可以说是分布式系统中最重要的一个算法。虽然Lamport在《Paxos made simple》中声称“Paxos is among the simplest and most obvious of distributed algorithms”, 但是个人在仔细研读几遍这篇论文后，还是觉得文章还是比较晦涩难懂的，虽然全文没有涉及到一个数学公式，都是文字描述，但是也没有直观的图来说明，最后还是查阅了其他各路资料，其中Chris Colohan在油管上一个关于paxos的lectture帮助很大。感觉Paxos最难理解的地方就在于要能搞清楚是什么因素导致该协议以这种方式呈现，而非其最终协议本身的内容。结合具体的应用场景来理解Paxos或许更好一点。

在本篇讨论中，实际上是讨论了Basic Paxos算法。而Basic Paxos只是理论模型，实际中使用的性能上更好的Multi-Paxos。Multi Paxos基于Basic Paxos, 将原来的2阶段过程（至少需要2次网络交互 + 2次本地持久化）简化为1个阶段，从而加速了提交速度。但是由于Multi-Paxos在理解和实现的复杂性，另一个改进版的一致性协议——Raft应运而生。Raft相比Paxos而言更加健全，更加易懂，虽然其在核心协议上基本是继承了Paxos中基于多数派的协议，但是其核心的贡献在于定义了易于实现的分布式一致性协议的事实标准。从某种意义上说，Raft不能算是一个新的协议，而是Paxos的一个具体化和简单化版本。