泽民博客 ☰ Menu

Paxos和Quorum

为什么需要Paxos或Quorum算法？分布式系统实现数据存储，是通过多份数据副本来保证可靠，假设部分节点访问数据失败，还有其他节点提供一致的数据返回给用户。对数据存储而言，怎样保证副本数据的一致性当属分布式存储最重要的问题。 一致性是分布式理论中的根本性问题，近半个世纪以来，科学家们围绕着一致性问题提出了很多理论模型，依据这些理论模型，业界也出现了很多工程实践投影。何为一致性问题？简而言之，一致性问题就是相互独立的节点之间，在可控的时间范围内如何达成一项决议的问题。



强一致写、多段式提交
强一致写
解决这个问题最简单的方法 ，就是强一致写。在用户提交写请求后，完成所有副本更新再返回用户，读请求任意选择某个节点。数据修改少节点少时，方案看起来很好，但操作频繁则有写操作延时问题，也无法处理节点宕机。



两段式提交（2PC 、Three-Phase Commit）
既然实际系统中很难保证强一致，便只能通过两段式提交分成两个阶段，先由Proposer（提议者）发起事物并收集Acceptor（接受者）的返回，再根据反馈决定提交或中止事务。
第一阶段：Proposer发起一个提议，询问所有Acceptor是否接受；
第二阶段：Proposer根据Acceptor的返回结果，提交或中止事务。如果Acceptor全部同意则提交，否则全部终止。
两阶段提交方案是实现分布式事务的关键；但是这个方案针对无反馈的情况，除了“死等”，缺乏合理的解决方案。 Proposer在发起提议后宕机，阶段二的Acceptor资源将锁定死等。如果部分参与者接受请求后异常，还可能存在数据不一致的脑裂问题。
三段式提交（3PC、Three-Phase Commit）
为了解决2PC的死等问题，3PC在提交前增加一次准备提交（prepare commit）的阶段，使得系统不会因为提议者宕机不知所措。接受者接到准备提交指令后可以锁资源，但要求相关操作必须可回滚。
但3PC并没有被用在我们的工程实现上，因为3PC无法避免脑裂，同时有其他协议可以做到更多的特性又解决了死等的问题。
主流的Paxos算法
微信后台近期开始主要推广Paxos算法用于内部分布式存储。Paxos是Leslie Lamport提出的基于消息传递的一致性算法，解决了分布式存储中多个副本响应读写请求的一致性，Paxos在目前的分布式领域几乎是一致性的代名词（据传Google Chubby的作者Mike Burrows曾说过这个世界上只有一种一致性算法, 那就是Paxos，其他算法都是残次品）。Paxos算法在可能宕机或网络异常的分布式环境中，快速且正确地在集群内部对某个数据的值达成一致，并且保证只要任意多数节点存活，都不会破坏整个系统的一致性。Paxos的核心能力就是多个节点确认一个值，少数服从多数，获得可用性和一致性的均衡。

Paxos可以说是多节点交互的二段提交算法，Basic Paxos内的角色有Proposer（提议者）、Acceptor（接受提议者）、Learner（学习提议者），以提出Proposal（提议）的方式寻求确定一致的值。
第一阶段（Prepare）：Proposer对所有Acceptor广播自己的Proposal（值+编号）。Acceptor如果收到的Proposal编号是最大的就接受，否则Acceptor必须拒绝。如果Proposer之前已经接受过某个Proposal，就把这个Proposal返回给Proposer。在Prepare阶段Acceptor始终接受编号最大的Proposal，多个Proposer为了尽快达成一致，收到Acceptor返回的Proposal编号比自己的大，就修改为自己的Proposal。因此为了唯一标识每个Proposal，编号必须唯一。如果Proposer收到过半数的Acceptor返回的结果是接受，算法进入第二阶段。
第二阶段（Accept）：Proposer收到的答复中，如果过半数的Acceptor已经接受，Proposer把第一阶段的Proposal广播给所有Acceptor。而大多Acceptor已经接受了其他编号更大的Proposal时，Proposer把这个Proposal作为自己的Proposal提交。Acceptor接到请求后，如果Proposal编号最大则确认并返回结果给所有Proposer，如果Proposer得到多数派回复，则认为最终一致的值已经确定（Chosen）。Learner不参与提议，完成后学习这个最终Proposal。
Paxos确认这个值利用的是“抽屉原理”，固定数量的节点选取任意两次过半数的节点集合，两次集合交集必定有节点是重复的。所以第一阶段任何已经接受的提议，在第二阶段任意节点宕机或失联，都有某节点已经接受提议，而编号最大的提议和确定的值是一致的。递增的编号还能减少消息交互次数，允许消息乱序的情况下正常运行。就一个值达成一致的方式（Basic Paxos）已经明确了，但实际环境中并不是达成一次一致，而是持续寻求一致，读者可以自己思考和推导，想深入研究建议阅读Leslie Lamport的三篇论文《Paxos made simple》、《The Part-Time Parliament》、《Fast Paxos》。实现多值方式（原文为Multi Paxos），通过增加Leader角色统一发起提议Proposal，还能节约多次网络交互的消耗。Paxos协议本身不复杂，难点在如何将Paxos协议工程化。
简化的Quorum（NWR）算法
Quorum借鉴了Paxos的思想，实现上更加简洁，同样解决了在多个节点并发写入时的数据一致性问题。比如Amazon的Dynamo云存储系统中，就应用NWR来控制一致性。微信也有大量分布式存储使用这个协议保证一致性。Quorum最初的思路来自“鸽巢原理”，同一份数据虽然在多个节点拥有多份副本，但是同一时刻这些副本只能用于读或者只能用于写。
Quorum又被称为NWR协议：R表示读取副本的数量；W表示写入副本的数量；N表示总的节点数量。
假设N=2，R=1，W=1，R+W=N=2，在节点1写入，节点2读取，无法得到一致性的数据；
假设N=2，R=2，W=1，R+W>N，任意写入某个节点，则必须同时读取所有节点；
假设N=2，W=2，R=1，R+W>N，同时写入所有节点，则读取任意节点就可以得到结果。
要满足一致性，必须满足R+W>N。NWR值的不同组合有不同效果，当W+R>N时能实现强一致性。所以工程实现上需要N>=3，因为冗余数据是保证可靠性的手段，如果N=2，损失一个节点就退化为单节点。写操作必须更新所有副本数据才能操作完成，对于写频繁的系统，少数节点被写入的数据副本可以异步同步，但是只更新部分节点，读取则需要访问多个节点，读写总和超过总节点数才能保证读到最新数据。可以根据请求类型调整BWR，需要可靠性则加大NR，需要平衡读写性能则调整RW。



微信有大量分布式存储（QuorumKV）使用这个算法保证一致性，我们对这个算法做了改进，创造性地把数据副本分离出版本编号和数据存到不同设备，其中N=3（数据只有2份，版本编号有3份），在R=W=2时仍然可以保证强一致性。因为版本编号存放3份，对版本编号使用Quorum方式，通过版本编号协商，只有版本序号达成一致的情况下读写单机数据，从而在保证强一致性的同时实现高读写性能。实际数据只写入一台数据节点，使用流水日志的方式进行同步，并更新版本编号。但是我们的分布式存储（QuorumKV）仍存在数据可靠性比Paxos低的问题，因为数据只写一份副本，依靠异步同步。如果数据节点故障，故障节点上没有同步到另一个节点，数据将无法访问。版本节点故障时，如果Quorum协议没有设置W=3，也可能无法访问正确的数据节点副本。



3PC标准协议是canCommit/preCommit/doCommit三个阶段，2PC是preCommit和doCommit两个阶段，Paxos算是比较典型的2PC,在preCommit阶段voting
3PC之于2PC的差异在于多了第一次canCommit通讯，使得Coordinator和Cohorts能够按照约定在相应阶段的timeout时做出准确的操作，而避免了2PC改中coordinator在超时发生时不知所措的窘态
统一思想，做出统一决策–解决脑裂问题->Paxos算法
思路：信使就是消息传递，也就是通过网络将消息传递给其他人的机制；通过parliament（议会）做出决议，基于“少数服从多数”
假设有两个机房，A机房和B机房，A机房有5台机器，B机房有3台机器，他们的网络被物理隔离了，我们来看看有哪些选择：
1.A，B机房独立的都可以提供服务。
这种方式明显是不靠谱的，会出现不可逆转的不一致问题。
2.A，B机房都不可以提供服务
合理的方式，但在高可用上是0分，只保持了一致性而已
3.让B机房的机器服务
好吧，你真的认为剩下三台机器提供服务的安全性比5台高
4.让A机房的机器服务
“民主并不是什么好东西，但它是我们迄今为止所能找到的最不坏的一种”
这就是quorum产生的核心原因



Paxos
当机器变得更多的时候Observer不能只有一个，必须有更多个Observer，但Observer多了，到底听谁的又成了问题。这时候，我们就需要“少数服从多数”。这就是quorum模型。
我们假定有A，B，C，D，E五台机器，KV系统需要put一个数据[key=Whisper,val=3306]到我们这5台机器上，要保证只要反馈为真，任意两台机器挂掉都不会丢失数据，并且保证高可用。怎么做：
1.首先，客户端随机选择一个结点，进行写入提交，这里我们随机选择了C这个结点，这时候C结点就是这次提议的发起人(也叫proposer,在老的2pc协议里也叫coodinator),当C收到这个提议的时候，C首先要做的事情是根据当前结点的最新全局global id,做一次自增操作。我们假定，在当时的全局global id为0，所以，这个议案就被对应了一个编号：1–>[key=Whisper,val=3306].
这里有两个我们经常犯的错误：
1)global id问题，在老的论文里，Lamport没有描述这个自增id是怎么生成的。从我目前能够看到的所有实现里面，基本上就是选择哪一台机器，就是以那台机器当前所保持的全局id(可能不是全局来看的最高值)，然后做一下自增就行了。我们后面会看到协议如何保证非全局最高值的globalID提议会被拒绝以至于不能形成决议。
2)golbal id只是对paxos协议有意义，对于数据库，其实只需要关心KeyValue即可，golbal id的作用只是告诉你这些数据的顺序是按照global id来排列的
回到文中，我们已经将这个新的议案标记了从C这台机器看起来最大的global id:1–>[key=Whisper,val=3306].然后，它会尝试将这个信息发送给其余的A，B，D，E这几台机器。
在这个过程中，Paxos将A，B，D，E叫做accepter(老的协议叫做参与者，cohorts),他们的行为模式如下：
如果A，B，D，E这几台机器的globalID小于C给出的决议的GID(1–>[key=Whisper,val=3306]),那么就告诉C，这个决议被批准了。而如果A,B,D,E这几台机器的globalID大于或等于C给出决议的GID，那么就告诉C这个决议不能被批准
我们假定A，B两台机器当时的Max(GID)是0，而D，E的Max(GID)是1。那么，A，B两台机器会反馈给C说协议被接受，这时候，C的议案有3票：A，B，C（算自己的）。所以这个议案有三票，5台机器的半数是3，超过法定人数，于是决议就被同意了。
我们保持这个上下文，来看看D，E这边的情况。首先，要思考的问题是，为什么D，E的Max(GID)是1呢？
其实很简单，D可能在C发起决议的同时，也发起了一个决议，我们假定这个决议是由D发起的，决议是1–>[key=taobao,val=1234].既然D,E的Max(GID)是1，那么意味着E已经告知D，它同意了D的决议，但D马上会发现，A，B，C里面的任意一个都返回了不同意，它的议案只拿到两票，没有通过。
这时候C的决议已经被多数派接受，所以它需要告诉所有人，我的议案1–>[key=Whisper,val=3306]已经被接受，你们去学习吧
这时候还有一个问题是需要被考虑的，如果在C已经达到法定人数，在告知所有人接受之前，C挂了，应该怎么办？
为了解决这个问题，需要要求所有的accepter在接受某个人提出的议案后，额外的记录一个信息：当前accepter接受了哪个提议者的议案。
为什么要记录这个？很简单，我们看一下上面出现这个情况时候的判断标准
A机器：角色accepter,批准的议案1–>[key=Whisper,val=3306],提议人：C
B机器：角色accepter,批准的议案1–>[key=Whisper,val=3306],提议人：C
C机器：角色proposer,挂了
D机器：角色accepter,批准的议案1–>[key=taobao,val=1234],提议人：自己
E机器：角色proposer,“提议的”议案1–>[key=taobao,val=1234],提议人：D
因为有了提议人这个记录，所以在超时后很容易可以判断，议案1–>[key=Whisper,val=3306]是取得了多数派的议案，因为虽然D，E两台机器也是可以达成一致的议案的，但因为有个人本身是提议者，所以可以算出这个议案是少数派。
在这之后，提议者还需要做一件事，就是告诉D，E，被决定的决议已经是什么了。这个过程在文章中叫做Learn。D，E被称为Learner。
这个过程是变数最大的过程，有不少方法可以减少网络传输的量



下面，我们讨论下载2pc/3pc中面临的问题，在paxos里面是怎么被解决的
2pc最主要的问题是死等、脑裂，两个问题。
对于脑裂，paxos给出的解决方案是，少数服从多数，决议发给所有人，尽一切努力送达，总有一个决议会得到多数派肯定，所以，不在纠结于某一台机器的反馈，网络无响应？没有就没有吧，其他人有反馈就行了。
所以，如果出现机房隔离的情况，比如A，B，C在机房1，D，E在机房2，机房1和机房2物理隔离了，那么你会发现，D，E永远也不可能提出能够得到多数派同意的提案。
所以，少数派的利益被牺牲了，换来了多数派的可用性。这是唯一能够既保证数据的一致性，又尽可能提高可用性的唯一方法。
而对于死等问题，解决方法也是一样的，对于某一台机器的无响应，完全不用去管，其他机器有响应就可以了，只要能拿到多数。
阶段一：系统只有一个数据结点，不存在数据一致性的问题，但在可用性和可靠性上存在较大的问题，先说可用性，随着系统用户规模（或者说是TPS）的升高，很快就会达到系统瓶颈，延迟增大，响应性急速下降，最终导致系统可用性下降，或不可用。再说可靠性，很明显，数据结点存在单点问题
阶段二：系统有两个数据结点（master-slave模式），提升了系统的可靠性，可以做读写分离，提升系统的可用性，但随着写压力的上升，master很快就会达到瓶颈
阶段三：系统中多个数据结点，没有主次之分，平等关系，这样的分布式系统设计是scalable的，大大的提升了系统的可用性和可靠性，但多个结点数据的一致性问题暴露了出来；但如果要求系统结点的强一致性，那么在数据的同步过程中，系统的可用性就会降低（CAP理论）
而Paxos算法就是为了在分布式系统中的系统可用性和一致性之间寻求一种平衡
Paxos算法是一种基于消息传递的一致性算法（一致性算法有两种实现方式：通过基于锁的共享内存和消息传递），用来解决在分布式系统中的数据一致性问题。
Paxos算法的思想是基于Quorum（法定人数）机制，少数服从多数，对于少数结点的网络异常、宕机、数据不一致，it doesn’t matter,消息尽一切努力送达，数据达到最终一致性
实际案例：
分布式系统中数据存储采用多份数据副本来提供可靠性。当用户提交了一次修改后，那么原先保存的副本显然就和当前数据不一致了。解决这个问题最简单的方案是read only after write all，就是在用户提交修改操作后，系统确保存储的数据所有副本全部完成更新后，再告诉用户操作成功；而读取数据的时候只需要查询其中一个副本数据返回给用户就行了。在很少对存储的数据进行修改的情况下，这种方案很好。但遇到经常需要修改的情形，写操作时延迟就很明显，系统可用性下降。
那么有没有一种方案能够不需要更新完全部数据，但又保证返回给用户的是有效的数据的方案呢？Quorum机制（鸽笼原理）便是其中一种选择，其实质是将write all负载均衡到read only上。
假设共有N个数据副本，其中K个已经更新，N-K个未更新，那么我们任意读取N-K+1个数据的时候就必定至少有一个是属于更新了的K个里面的，也就是quorum的交集，我们只需要比较读取的N-K+1中版本最高的那个数据返回给用户就可以得到最新更新的数据了（满足W+R>N，集群的读写就是强一致的）。
对于写模型，我们只需要完成K个副本的更新后，就可以告诉用户操作完成而不需要write all了，当然告诉用户完成操作后，系统内部还是会慢慢的把剩余的副本更新，这对于用户是透明的。即write上的部分负载转移到了read身上。至于具体转移多少负载比较合适，取决于系统的读写访问比。



那么Paxos有没有什么值得改进的地方？有的，很简单，你会发现，如果在一个决议提议的过程中，其他决议会被否决，否决本身意味着更多的网络io，意味着更多的冲突，这些冲突都是需要额外的开销的，代价很大。
为了解决类似的问题，所有才会有zookeeper对paxos协议的改进。zookeeper的协议叫zab协议
其实，这也是在我们现实生活中经常能够发现的，如果每个议案都要经过议会的讨论和表决，那么这个国家的决策无疑是低效的，怎么解决这个问题呢？弄个总统就行了。zab协议就是本着这个思路来改进paxos协议的



zab协议把整个过程分为两个部分，第一部分叫选总统，第二部分叫进行决议。
选总统的过程比较特殊，这种模式，相对的给人感觉思路来源于lamport的面包房算法，选择的主要依据是：
1.如果有gid最大的机器，那么它就是主机
2.如果好几台主机的gid相同，那么按照序号选择最小的那个
所以，在开始的时候，给A,B,C,D,E进行编号，0,1,2,3,4.第一轮的时候，因为大家的Max(gid)都是0，所以自然而然按照第二个规则，选择A作为主机
然后，所有人都知道A是主机以后，无论谁收到的请求，都直接转发给A，由A机器去做后续的分发，这个分发的过程，叫进行决议。
进行决议的规则就简单很多了，对其他机器进行3pc提交，但与3pc不同的是，因为是群发议案给所有其他机器，所以一个机器无反馈对大局是没有影响的，只有当在一段时间以后，超过半数没有反馈，才是有问题的时候，这时候要做的事情是，重新选择总统。
具体过程是，A会将决议precommit给B,C,D,E。然后等待，当B,C,D,E里面的任意两个返回收到后，就可以进行doCommit()。否则进行doAbort()
为什么要任意两个？原因其实也是一样的，为了防止脑裂，原则上只能大于半数，因为一旦决议成立的投票数少于半数，那么就存在另立中央的可能，两个总统可不是闹着玩的。
定两个，就能够保证，任意“两台”机器挂掉，数据不丢，能够做到quorum.
写zab协议的人否认自己的协议是paxos变种，其实他们是针对一个问题的两种解决方法：
因为他们解决的问题的领域相同
解决网络传输无响应这个问题的方法也一样：也即不在乎一城一池的得失，尽一切努力传递给其他人，然后用少数服从多数的方式，要求网络隔离或自己挂掉的机器，在恢复可用以后，从其他主机那里学习和领会先进经验。
并且也都使用了quorum方式防止脑裂的情况
核心思路是类似的，但解决问题的方法完全是两套。
ps:
活锁，指的是任务或执行者没有被阻塞，由于某些条件没有满足，导致一直重复尝试，活锁可以自行解开，可以认为是一种特殊的饥饿。活锁的进程不会block,这会导致耗尽CPU资源。



Dynamo and Cassandra
共性1:
W+R>N
N表示集群中副本的总数
W表示写入的份数
R表示一次一致性读所需要的份数
这个公式表示为：如果满足W+R>N(W,R,N属于不为负数的整数且R,W小于N，那么集群的读写是强一致的。
共性2:
gossip算法（适用于数据之间冲突很小的情况）
有“流言蜚语，谣言”的意思，A gossip protocol is a style of computer-to-computer communication protocol inspired by a form of gossip seen in social network.应该降低节点之间的沟通频率，否则网络开销较大。
gossip算法被称为反熵(Anti-Entropy)，熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻居节点，只要这些节点可以通过网络连通，最终他们的状态都是一致的。即使有的节点因宕机而重启，有新节点加入，但经过一段时间后，这些节点的状态也会与其他节点达成一致，即Gossip天然具有分布式容错的优点。
Gossip是一个带冗余的容错算法，也是一个最终一致性算法。因为Gossip不要求节点知道所有其他节点，因此具有去中心化的特点，节点之间完全对等，不需要任何的中心节点。
但Gossip的缺点也很明显，冗余通信会对网络带宽、CPU资源造成很大的负载，而这些负载又受限于通信频率，该频率又影响着算法收敛的速度。
根据原论文，Gossip的两个节点（A,B）存在三种通信方式：
push:A节点将数据(key,value,version)推送给B节点，B节点更新A中比自己新的数据（一次通信）
pull:A仅将数据key,version推送给B，B将本地比A新的数据(key,value,version)推送给A,A更新本地（两次通信）
push/pull:与pull类似，只是多了一步，A再将本地比B新的数据推送给B，B更新本地（三次通信）



dynamo,数据同步使用了gossip+Merkletree,使用vector clock来标记冲突数据，冲突数据会交给用户做出处理。
cassanra,与dynamo类似，在选择上，放弃了vectorclock,使用timestamp来进行冲突合并



Category zookeeper