• 1 Preface
  • 1.1 Consensus Problem
  • 1.2 The Part-Time Parliament
  • 1.3 Opinions on Paxos
• 2 Paxos
  • 2.1 A Simple Problem
  • 2.2 Roles
  • 2.3 Assumptions
  • 2.4 Safety and Liveness Properties
  • 2.5 Protocol
    • 2.5.1 How Many Acceptors?
  • 2.6 Summary
  • 2.7 Optimistic Concurrency Control
  • 2.8 Paxos
    • 2.8.1 Mapping
    • 2.8.2 Proposal ID
    • 2.8.3 Practices
• 3 Implementation
• 4 Summary

1 Preface

只要去了解分布式系统，都要知道Paxos算法，算法本身的描述很简单。

真正掌握一个东西，得要知道它为什么要这样做，这样就不用记住协议本身了，可能自己就能推导出来。

1.1 Consensus Problem

详见 https://en.wikipedia.org/wiki/Consensus_(computer_science)。

共识问题是分布式领域一个非常根本的问题。一组自治并发的实体(进程、代理、节点、服务器、微服务等)之间对一个单个的数值达成一致。有些进程可能会失效、出故障。

会不会出现一些虚假的信息呢？会不会说假话呢？这是另外一个假设，拜占庭问题。区块链也是一个共识问题，但它是拜占庭问题。

一般的分布式领域里，节点要么故障Crash掉，死了重启就完了，这样一种假设，非拜占庭。

因为节点、进程会故障，所以设计的协议算法一定要能容错。所有进程都不能死，可以的，但是适用性就窄了，要求高了，一旦出问题就不能用了，所以还是希望能够容错。

每个进程都可以发起提议，希望是这个值，然后它们之间互相通信，最终达成都是一个值。

分布式系统里所有问题都可以化为共识问题，它是一个非常基础的问题。

Lamport就是因为他在分布式系统中的贡献(vector clock(lamport clock)、Paxos算法)获得图灵奖。这些都是云计算的基石。

因为问题很基础很根本，所以Paxos算法很重要。

算法本身有一些属性，Safety属性和Liveness属性。Liveness属性是指算法一定会结束。Safety属性是指没有Bug，结束时答案是正确的。最终肯定要结束并且达成一个一致的值。不能随便搞一个值，必须是这几个提议的进程的某一个值。

1.2 The Part-Time Parliament

详见

• http://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
• https://www.microsoft.com/en-us/research/uploads/prod/2016/12/The-Part-Time-Parliament.pdf
• https://www.microsoft.com/en-us/research/publication/part-time-parliament/

怎么能够更高级地去学习这个协议呢？当然要了解它的历史、一些有趣的事情，这样能够帮助我们理解，说起来也会比较有趣。

这是一篇Lamport于1989年发表的论文。不是全时制议会，可能一会儿组建，一会儿拆了。这很像一个隐喻，一个集群，一会儿节点来了，一会儿节点没了。这篇论文是解决共识问题的。在一个分布式系统里，如果有节点会宕掉，那么共识问题到底有没有解，如果有解，它的条件是什么。Lamport是一个非常有趣的人，他讲了一个寓言故事。

这个想法怎么来的呢？有一个实验室，叫SRC，大概是80年代的时候，他们想做一个文件的容错系统。实验室的人说我们这个系统很厉害，可以容忍任意数目的节点，只要是非拜占庭错误，都可以保持一致，只要超过半数的节点活过来，系统就可以继续工作。如果系统本身不出错的话，保持一致性很简单。Lamport就想你这个问题到底行还是不行，他考虑了一下，认为肯定不可能，然后还去证明，在证明的过程里发明了Paxos算法，然后写了一篇论文。

他不喜欢呆板的论文写法，就写了一个寓言，杜撰了一个在希腊的小岛上有一个失落的文明，有一个议会，议员在选举，议员比较懒散，一会儿来一会儿不来，……。写完之后，他专门找了一个朋友，那位朋友是一个语言专家。小岛上的人原来都是用计算机科学家的名字起名，这个语言专家就帮他翻译成了另外一种语言。他讲的是算法，但别人对算法无感，就记得他讲的故事了。

这个算法本身是一个比较难的问题，别说一般的听众了，他把论文发给了业界几位分布式领域的顶级学者，这些人看完之后没反应，过了几个月他又给他们发邮件问了一个问题，你们能不能实现一个分布式数据库能够容忍任意数目节点的失效而且不丧失一致性，而且当超过半数的进程节点恢复之后，系统还能正常工作，没有数据丢失。邮件发完之后也没什么回应。没有任何人发现论文和问题之前的关联。可以看到，他的论文故事性有多强。

在1989年论文写完之后，审稿人说你这个文章写得很有趣，但不知道你想说什么，你能不能把寓言都去掉。Lamport没管。1989年论文就提交了，但是没有通过。过了近10年，另外一帮SRC的人开发另外一个分布式系统，要解决同样的问题，跟别人聊天，别人说私下里听Lamport说过他有一篇论文可以解决这个问题，这帮人一看这个就是我们要解决的问题。他们是带着问题的，所以一看寓言就知道这是我的事。如果没有问题，看了也不知道在说什么。这是很重要的一点。他们就把它拿来用，很好。这帮人又去跟别人说这件事，别人重新把论文拿出来看，才看懂论文说的是什么。1989年写的论文，十年之后才发表。

1.3 Opinions on Paxos

业界对Paxos的认识。可以看到，虽然目前有很多共识协议、共识算法，真正正确的共识算法只有一个——Paxos。现实环境有很多不同的约束，是可以做裁剪的，因为大家都觉得这个算法太难懂了，很容易实现错误，这是事实。Paxos算法即使你理解了，要能实现一个完全正确的、工程里没有问题的，也是很难的。Raft协议其实就是一个改良版的Paxos，让大家更好理解，但做了不同的假设，这些假设理论上可能有些缺点，但在现实里是完全可用的，没有任何问题。在工程层面上，好理解比什么都重要。这个东西我能理解的话就知道哪个地方会出问题，这个问题我能不能接受，能不能去补偿。如果不好理解，对错我也不知道，我不理解还去用这个东西，这是最可怕的事情，何况它是整个分布式系统的基石。

这个算法协议的地位是很高的。

2 Paxos

从问题出发，这些问题大家都碰到过，你是怎么解决问题的，能否进一步延伸一下，是否能导出同样的结论。

详见 https://en.wikipedia.org/wiki/Paxos_(computer_science)。

2.1 A Simple Problem

为了深入理解问题本身，先来看一个简单的问题。

绿框可以认为是一致性决策机制，黑箱，不知道怎么实现的。三个蓝框可以认为是三个Process、或三个客户端。它们要同时写一个值，分别是X = 3、X = 5、X = 8，可以认为是并发的，X到底等于几呢？这里是一轮，一轮只解决一个一致性问题。先看单值，先把单值问题解决好了，就可以看多值。现在考虑一个值。

假设只有一个进程来负责一致性决策机制的话，问题好解决，都发给我，我随便选一个就完了。三个并发进程给我一个进程发，我可以收到第一个就决策，后面两个扔掉就完了。举个例子，“X = 3”先发给我，就是3了，后面“X = 5”告诉你是3，“X = 8”也告诉你是3，那大家就都是3了。

问题好解决，但这有什么问题呢？不容错。

来说一下，一致性问题为什么是一个基础问题？

多个计算机的数据一致性问题。

一致性模型，线性一致性、顺序一致性等，一致性跟共识问题有什么区别和关联？

共识是一个手段，一致性是目标，通过共识手段可以达成一致性目标。不同的一致性只是达到不同的目的。达到目的的手段有很多，但强一致里容错本质上只有一个，就是Paxos协议，通过共识协议达到这个目标。

现在把问题稍微泛化一下。假设我能解决共识问题，那我是不是能够解决所有一致性问题呢？

有多个节点、多个进程，希望它们的数据状态一样。那么数据状态是怎么产生的呢？肯定是计算机做计算。我们把问题再一般化一下，就把一个计算机当成一个状态机。状态机是什么？它有自己的状态，输入，然后产生一个新的状态，可能做一些修改。目前的计算机都是确定有限状态机(量子计算机可能是非确定的)，只要输入一样、初始状态一样，无论几台计算机，所有的状态完全都一模一样。这是我们讲的一致性更基础的问题。Lamport曾经写过一篇论文，以状态机为基础。因为只要把状态机的一致性问题解决了，所有问题就都解决了，因为所有计算机都是计算，不管是写数据库也好、选Leader也好、Atomic Broardcast也好，其实都是在做计算，计算的根就是状态机。所以只要所有的计算机的状态机的初始状态、代码一样，能让指令日志大家都能够完全一致的话，所有的结果都是一样的。

这就是我们讲的更基础的问题。假设有3个节点，给3个节点发不同的指令，第1个发“X=X-100”，第2个发“X=X*2”，第3个发“X=X+100”，3个节点的代码是一样的，只要每个机器上执行的顺序是一样的，结果肯定一样，不管想达到什么样的共识。Lamport论文里，叫“Replicated Log”，计算机当中的状态机，只要让Log一致了，肯定是一致的，所有问题都可以解决了。就像通用图灵机一样，不用关注特殊问题，只要关注一般化的问题就可以了。

3个客户发了3条指令，3条指令顺序执行。假设第1台机器先执行“X=X-100”、再执行“X=X*2”、再执行“X=X+100”，第2台机器先执行“X=X*2”、再执行“X=X-100”、再执行“X=X+100”，第3台机器先执行“X=X+100”、再执行“X=X-100”、再执行“X=X*2”，顺序不一样，结果肯定错了。通过共识协议，第1条指令都是“X=X*2”，第2条指令都是“X=X+100”，第3条指令都是“X=X-100”，结果肯定一致了。或者反过来，第1条指令都是“X=X-100”，第2条指令都是“X=X+100”，第3条指令都是“X=X*2”，结果也是一致的。顺序不要紧，结果要一致。并发问题，顺序本来就没法保证，只关心Order是否一致，而不关心具体什么Order。这就是前面讲的“Sequential Consistency”。单台机器上一定是有序的，多台机器上大家一致就行。

所有的更改无非就是操作，操作就是状态机的变迁，日志一样，计算结果肯定是一致的。

2.2 Roles

为了更好地说明“几个进程达成一致”这个问题，我们把角色明确一下。

• Client：发起请求。
• Proposer：提议者。
• Acceptor：做决策。
• Learner：结果通知给Learner。

都是不同的角色，上图红方框里的角色可以是一个进程，当然也可以是不同的进程，不影响正确性。可以让Proposer、Acceptor和Learner是不同的进程，也可以让它们是一个进程，可任意组合。

Client把提议交给Proposer，Proposer可以认为是一个客户代理，把提议交给一组Acceptor，一组Acceptor达成一致后，把结果通知Learner。

椭圆框表示Proposer、平行四边形框表示Acceptor。

Proposer是多个，Proposer和Client是对应的，并发地请求，在这次请求里达成一个结果，再请求达成第二个结果，……。

上图中3个进程，第1次先定一个，第2次再定一个，第3次再定一个。有3个Paxos实例，每个实例解决一次，每个Paxos对应日志中的一个序号。

一次Paxos得到一个值。可以认为指令都是有编号的，0、1、2、……，第1次只对0号位置的值达成一致，再对1号位置的值达成一致,再对2号位置的值达成一致。上图中，要通过3轮Paxos协议得到第0、1和2位置的值。

对于指令日志中的0号位置，第1个Client告诉2、3说0号位置应该是“X=X-100”，第2个Client告诉1、3说0号位置应该是“X=X*2”，第3个Client告诉1、2说0号位置应该是“X=X+100”，那0号位置到底应该是什么呢？通过Paxos协议定下来0号位置都是“X=X-100”。再来一轮，定下1号位置都是“X=X*2”。再来一轮，定下2号位置都是“X=X-100”。

在不同的节点之间对某个值达成一致。这是一种技术，可以用它来做数据一致性，比如主备，我们的主备只有主能写、备不能写，问题就简单多了。

现在的场景是3个节点都可以写。第1个节点收到消息要做“X=X-100”，第2个节点收到消息要做“X=X*2”，第3个节点收到消息要做“X=X+100”。X初值大家都一样，最终3个指令都要执行，每个节点上都有指令日志，希望3个指令日志一模一样，应该怎么解决呢？就是这样一个问题，这个问题更具一般性。所有其他问题都是它的特例或者简化。

3台机器，每台机器都可以接受请求，每台机器都有Log。一台机器收到请求以后，会把请求同步到另外两台机器上。第1台机器收到“X=X-100”的请求，它会把这个请求同步到另外2台机器上去。第2台机器收到“X=X*2”的请求，它会把这个请求同步到另外2台机器上去。第3台机器收到“X=X+100”的请求，它会把这个请求同步到另外2台机器上去。最终每台机器上都有3条Log，问题在于这3台机器上的3条Log怎么才能达成一致。

一致性决策机制可以任意实现，结果是希望大家的Log一致，3条Log的具体顺序不重要，但3台机器的3条Log顺序要一致。

2.3 Assumptions

学习一个算法，一定要知道它的假设，否则算法没法用。

Processor，可以认为是Process：

• 是异步的，没有同步时钟，每一步时间不确定。
• 会失败，但失败是非拜占庭的，即不能篡改、要么死要么重启。
• 有持久化存储，重启之后应该记住之前的序号和信息。如果没有持久化存储，这个协议是达不成的。
• 不会做假，不会两个Processor商量一下做个假。

Network：

• 网络是互通的，任何一个Processor都可以给另外一个Processor发消息。
• 消息是异步发送的，时延可以任意长。
• 消息可能会丢、重排、乱序、重复。这才是现实。
• 消息不能被篡改，所以要加校验，保证消息不会被篡改。

这是一个很典型的现实问题，所以这个协议完全可以在现实里用。

2.4 Safety and Liveness Properties

只能选一个值，而且是提议的值，而且一定有结果。

2.5 Protocol

2.5.1 How Many Acceptors?

有很多proposer，通过某种协议，提议一个值发给下面的框，由框中的acceptor来做决策，所有的acceptor达成一致了，就达成一致了。先来看看Acceptor数目的问题。

当acceptor数目为1时，好办，有proposer发1， 有proposer发2，那这个acceptor说几就是几。说是3，告诉Learner，就结束了。但是不容错，acceptor一死就没法用了。

所以acceptor数目一定要大于1。

假设有3个acceptor，第1个proposer给第1个acceptor提议“X=1”，第2个proposer给第3个acceptor提议“X=3”。假设第1个acceptor收到“X=1”了，第3个acceptor收到“X=3”了，这两个消息都到第2个acceptor了(第1个acceptor和第3个acceptor都会给第2个acceptor发消息)，第2个acceptor该怎么办呢，它的X是几呢，冲突了。

数目 > 1 加锁

数组：要么全1，要么全3

3把锁

两类锁，违反Safety属性，要么做不了，但做了错了不能忍受。

不能借助全局锁。

超过半数就有原子性。 保证不会出错，不一定有结果。

通过半数，把锁编程atomic锁。

但是，锁了，设值，过程中acceptor挂了，怎么办？

悲观锁、乐观锁

把锁抢占了再说。

超时：定时器、同步，违反假设。

Paxos里不能有定时器。

要加锁，锁必须是可抢占的。

假设后来的锁比之前的锁优先级高，可以抢占。

要加锁，可抢占锁，看是否Accepted过。

acceptor内部是不并发的。

2.6 Summary

奇数：单个独立的锁形成一个大锁。

锁加到全部，就不容错了。

锁怎么保证全局有序。

2.7 Optimistic Concurrency Control

获得锁 -> 改数据 -> 释放锁

先读数据和版本号 -> 改数据的时候，看一下数据有没有改掉，

CAS：Compare and swap

写冲突少的情况下，极大提升性能。

把version当锁，锁是资源决定的、acceptor决定的。

反过来想，proposer生成version，不同的proposer之间version是可以比较的，而且越来越大。

要做一把可抢占的锁，新锁淘汰老锁。

只要是我的锁，或者更新的锁，都能设置值。但值可能是你给我的(Accepted)。 加锁时，如果成功了，Accepted的时候，会把值给我。

2.8 Paxos

换一个名词

在各种容易出错的情况下解决容错、原子性、收敛的问题。

2.8.1 Mapping

2.8.2 Proposal ID

设计一个东西，要先考虑希望他具有什么样的性质，然后再看具体实现。

2.8.3 Practices

两个Client，值分别是X和Y

S1-5是服务器

P是lock ok A是Acceptor消息

假设集群的个数是知道的。

Livelock 不会错，但会出现Livelock。

两篇论文：Lamport

3 Implementation

4 Summary