分布式系统是网络化的计算机系统，海量数据的互联网应用只能通过分布式系统协调大量计算机来支撑。微信后台存储大量使用了分布式数据存储方式的NoSQL集群，比如核心业务：账号、支付单据、关系链、朋友圈等。存储设备出现异常是必然，分布式系统通过多节点分布及冗余，避免个别异常节点影响到系统的正常服务，同时提供平行扩展能力。微信自研的分布式存储在发展的不同阶段，分别依赖过Paxos和Quorum两种方案维护一致性。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协议工程化。

我们实现Paxos存储做了一些改进，使用了无租约版Paxos分布式协议，参考Google MegaStore做了写优化，并通过限制单次Paxos写触发Prepare的次数避免活锁问题。虽然Paxos算法下只要多数派存在，就可以在分布式环境下达到严格的一致性。但是牺牲的性能代价可观，在大部分应用场景中，对一致性的要求并不是那么严格，这个时候有不少简化的一致性算法，比如Quorum。

简化的Quorum（NWR）算法
Quorum借鉴了Paxos的思想，实现上更加简洁，同样解决了在多个节点并发写入时的数据一致性问题。比如Amazon的Dynamo云存储系统中，就应用NWR来控制一致性。微信也有大量分布式存储使用这个协议保证一致性。Quorum最初的思路来自“鸽巢原理”，同一份数据虽然在多个节点拥有多份副本，但是同一时刻这些副本只能用于读或者只能用于写。

• Quorum控制同一份数据不会同时读写，写请求需要的副本数要求超过半数，写操作时就没有足够的副本给读操作；
• 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，也可能无法访问正确的数据节点副本。

后记
分布式存储选用不同的一致性算法，和业务的具体情况相关。我们的分布式存储在发展的不同阶段，使用过不同的算法：业务的发展初期使用Quorum算法，成本压力减少而业务稳定需求变大后，就开始使用Paxos算法。如果业务模型对数据一致性要求不高，使用Quorum则具有一定的成本和开发资源优势。

订阅2017年程序员（含iOS、Android及印刷版）请访问 http://dingyue.programmer.com.cn