最近在思考一致性的问题，网上有很多这方面的资料了，这里谈谈我对一致性以及paxos算法的理解。

1 一致性

什么是一致性，所谓一致性就是数据保持一致，在分布式系统中，可以理解为多个节点中数据的值是一致的。在单机系统中多线程程序其实也有一致性的问题，两个线程对一个变量的访问，在JAVA程序中我们有volatile关键字保证内存的一致性，也就是说当一个线程修改一个共享变量时，我们要确保另外一个线程能读到这个修改的值，当然我们还有有其他各种同步机制。在单机上的一致性这个其实非常好理解。

在分布式系统中，为了提供可用性，通常我们的数据在不同节点上会有多个备份，我们是没办法保证对所有副本同时更新，这样不同client在读不同副本的时候就可能出现读取的值不一致的情形。根据CAP理论，一致性，可用性，分区容忍性，三者只能取其二，三者不可兼得。通常分布式系统都要容忍分区（即分区隔离情况下也必须能工作），这样在工程实践上就变成了一致性和可用性只能取其一。理论上讲，如果保证100%可用性的情况下不可能达到强一致，但是这并不意味着就没有了一致性，一致性可以分为几种：强一致，弱一致，最终一致性等等。

强一致-总是能读到最近一次写的值；

弱一致性-可能读到旧(Stale)的值;

最终一致性-在一段时间窗口内可能读到旧的值，最终会读到新的值。

对于应用开发人员来说都是希望强一致的，我写下去的值我希望立刻能读到，但是强一致系统往往性能不太好（相对而言）， 于是就只能tradeoff，几乎所有流行的NoSQL系统为了追求性能，都牺牲了部分一致性，实现成一个弱一致或最终一致性系统，

即BASE（BasicallyAvailable,Soft state,Eventualconsistency），BASE的含义就是指“NoSQL数据库设计可以通过牺牲一定的数据一致性和容错性来换取高性能的保持甚至提高”。

我们看看工业界的存储系统，其实可以分为CP系统以及AP系统。追求极致可用性（AP）的常见系统包括：

AmazonS3

AmazonDynamo DB

MongoDB/Redis为代表的NoSQL

……

追求强一致的CP系统，比如：

GoogleMegastore / Spanner

MicrosoftAzure Storage

TiDB/CockroachDB

AmazonAurora

……

2 如何实现强一致性

2.1 协议

分布式系统实现强一致的需要某种协议来保证，经典的两阶段提交2PC虽然解决了强一致的问题，但是可用性很差，因为2PC在协调者（TM）宕机时无法决定事务状态，系统阻塞，需要等待协调者（TM)恢复才能继续下去。

在工作中会议室预定系统就是一个2PC系统，会议发起方（TM）会询问所有会议参与者是否有空，如果所有参会者都有空（OK），那么提交(commit)此次预订，此次会议预定成功。如果有任意一个参会者(RM)没空，那次此次预定失败。这里有个问题是，假设在与会者回应之后，会议发起方中途有事离开，那么与会者是没法知道此次预定是否成功的，没法完成也没法中途取消，系统会阻塞，必须等等发起方回来之后才能继续下去。

后续改良版的三阶段提交（3PC）增加了一个中间状态方便判断事务状态，协调者宕机，选出新的协调者，新的协调者不用等宕机者恢复就能决定事务状态，但是在网络分区的情况下，可能出现不一致的问题。比如在某些情况下可能会出现，比如两个节点都宣称自己是新的协调者的情况，这时候3PC仍然没有提出一个好的解决办法。因此可以说2PC/3PC都存在一些先天缺陷，2PC有可用性的问题，3PC有一致性的缺陷。于是Lamport大神提出的Paxos协议就可以派上用场，发挥它的威力了。

2.2 Paxos协议

Paxos协议是Lamport大神在80年代提出的解决分布式一致性多个节点之间就某个值达成一致的经典通信协议。协议也分为两个阶段：

第一阶段P1 Prepare阶段

P1a：Proposer发送Prepare请求

Proposer发送全局唯一且递增的提案ID(Proposal ID或者叫Ballot)，向所有节点（即Acceptor）发送Prepare Request,这里无需提交提案内容，只需要携带Proposal ID即可。

P1b : Acceptor应答Prepare Request

Acceptor收到Prepare Request之后，检查自己之前是否接受过大于等于该提案ID(ProposalID或者Ballot)的请求，如果没有，则Accept该Prepare请求，并且做出以下两个承诺：

第二阶段P2 Accept阶段

P2a：Proposer发送Accept请求

首先，Proposer根据P1b结果决定是否继续到下一阶段，即第二阶段。如果在P1b阶段没有收到多数Acceptor的相应，此次Paxos实例结束。如果收到了多数Acceptor节点应答的PrepareResponse，才会进入到P2a阶段。在P2a阶段，proposal发起Accept请求，该Accept请求除了携带当前ProposalID,即在P1阶段被多数节点接受的Proposal ID,还需要携带提案内容。注意，此处提案内容不是随心所欲，提案内容的生成是有规则的，这个规则就是：

Proposer收集到多数派应答的PrepareResponse后，从中选择proposalid最大的提案内容，作为要发起Accept的提案，如果这个提案为空，则proposer可以随意决定提案内容.

这个规则非常重要，是paxos算法保证准确性的最重要的原则，需要好好理解。

这里再思考一下，为什么需要两个阶段？第一个阶段Prepare的目的是什么？其实可以这样想，两个阶段目的就是是为了解决提案冲突，试想如果只用一个阶段一次提交提交显然无法达到一致的状态。而两个阶段各有作用，第一个阶段Prepare的作用其实就是拿到一个授权，谁的Prepare ID最大谁就有权利去发起第二个阶段的accept请求。而第二个阶段，有权利的节点发生accept请求，该请求内容可能不是自己的，而是从所有已经accept中的提案选出提案号最大的那个，这就保证了最终被接受的提案的唯一性，换句话说，如果一个提案被大多数节点同意(accepted)了，那么该提案一定会被最终popugate到所有节点，而这样的提案只可能有一个，这样就保证了正确性(safety)。

可能这样解释还是很抽象，举个生活中的例子。很多同事中午吃饭都有一个疑惑，不知道午饭到哪里吃，一群人需要决定到哪家餐馆吃午饭，对这个问题达成一致，这其实就是一个典型的一致性问题。让我们用paxos协议来决定午饭到哪里吃。假设有5位同学A,B,C,D,E,有这样几种情形：

情形一：

A提议说："我来说个餐厅吧？"（P1a)

BCDE四个同学自己也没有想法，那就同意吧："听你的。"(P1b)

A说：“去吃望湘源吧？”（P2a）

BC没有想法：“好吧，就吃望湘源”。（P2b）

DE没有说话。A看看大家的结果，BC同意，包括自己总共3个人同意，已经达到多数票，那就这样决定了，然后A告诉所有人中午一起去吃望湘源了。

情形二：

A提议说："我来说个餐厅吧？"（P1a)(Ballot=1)

B,C说：“好啊”。（P1b）

但是E不同意了，E马上说：“不行，昨天吃你推荐的望湘源把我辣死啦，还是不听你的了”。（P1b，A的Prepare请求被E拒绝）

A看看其他3个人没有反对自己，仍然固执地提出自己的想法：“我们今天不吃辣的，吃本帮菜，丰收日怎么样？”。（P2a）

B表示同意：“丰收日不错的”（P2b）

E把手举得高高的说：“还是我来推荐个人气餐厅吧”（P1a，Ballot=2）

C,D两位同学说：“好啊，你说吃啥？”(P1b,由于C,D响应了E的请求，将不再响应A的请求)

B说：“我已经答应A去吃丰收日了耶”

E看看提议号最高并且已经接受过的应答中（Ballot=1优先级最高），B已经接受请求了，那勉为其难的说：“好吧，丰收日就丰收日吧”

C，D：“行！”

于是大家就愉快地去丰收日了。

注意这里很重要的一点，也是理解paxos的核心，就是按照提案生成规则，当E看到别人已经接受的请求了，就不能提出自己的请求。但是假设E没有听到B的回答，而是只听到C,D同意的响应，E仍然可以提出自己的想法。这两种情况，虽然结果不一样，但是都达成一致了。

上述是basic paxos的理论模型，在工程实践上实现paxos是有很多坑，google的megastore和chubby，以及后来的spanner实现都采用了paxos，在其论文'Paxos made live'也描述了工程实现上遇到的问题。

3 Leader or not Leader

经典的paxos协议是没有leader的概念的，各个角色完全对等，任何节点都可以发起proposal请求，但这样的实现往往性能不会太好。在具体工程应用中大多会考虑Leader based的paxos实现，完全没有leader的paxos目前仅仅存在于理论上。根据Leader的作用，具体可以分为两类：强leader和弱leader。

所谓leader，实际就将第一阶段的prepare的权利赋予某一个节点，即Leader，又称coordinator,或者叫Master。这样由于系统中只有一个节点有发起提议的权利，就无需运行paxos的第一阶段P1，直接进行第二阶段accept，除非有冲突发生。所谓冲突就是accept过程发现有其他并发请求，这样就必须回退到第一阶段。另外在原Leader节点宕机，就需要重新选Leader，当然重新选Leader期间系统是不可服务的。Multi-Paxos是基于强Leader的实现，依靠leader进行日志复制同步和恢复。

在Paxos早期应用中 像Google的Meagstore是最早将Paxos协议大规模应用在工程实践中的系统，从Megastore论文可以看出其paxos实现，其弱化了Leader（coordinator）的作用，其coorinator只是用来保存哪些replica是up-to-date的，如果是，则直接进行local read，不需要再走paxos流程来获得最新的数据。其Fast Write优化是如果当前这轮paxos写成功，将自动获得下一轮paxos写的prepapre的权利，这样下轮写直接accept。这样实现的好处是多点可写，不需要一个delicated的leader，服务实现完全的高可用。当然缺点也是很明显的，当存在写冲突时就会大量重试导致冲突进一步加剧，甚至“雪崩”，因此Megastore论文中也提到限制单个Entity Group的写频率来降低冲突。

Google后来的Spanner系统重新了设计Paxos的工程实现，采用了“long-lived Paxos Leader”，所有的写都从Leader发起，保证顺序apply。这样大大降低latency，提高系统throughput。

再换个角度想想Leader的作用，第一点，leader必须要有全局视角，拥有最新的信息；第二点，将所有的写请求串行化，避免了冲突。对照现实生活中，leader就像没有红绿灯时十字路口的交警，没有交警维护交通秩序，交通会非常拥挤。

4 总结

总体来说，Paxos是一个经典的一致性协议，目前已经成为分布式系统的实现高可用强一致的标配，由于其实现的复杂性，工程应用中层出不穷出现Paxos的各种变种和优化，包括Raft其也是paxos的一种简化实现。Leader or not Leader这只是工程实现上的选择，不影响正确性，各自有优缺点，但可以说Leader base的实现还是目前工程实践中的大多数系统的选择以及未来的方向。

Reference: