分布式系统的一致性协议—Paxos、Raft介绍

什么是分布式系统？

说到系统，接触过计算机的人可能并不陌生，首先联想到的就是计算机操作系统，最熟悉的如Windows、Linux等等。可以在硬件设备上安装操作系统，有了系统就可以安装并运行应用，这些系统有一个共同的特点就是只能安装到一台硬件设备。如果应用越来越多，应用不断更新，需要的计算能力越来越高，我们的电脑就会变的很慢，这时我们只有两种解决办法：初始化系统或换一台高配主机，但是这两种方法只是治标不治本，需要周期性频繁操作。对服务器来说，这两种方法代价都很高，那是否可以将大量廉价设备关联起来，共同构成一套系统。

分布式系统是一个硬件或软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统。分布式系统的出现是为了用廉价的、普通的机器完成单个计算机无法完成的计算、存储任务。其目的是利用更多的机器，处理更多的数据。

谈到分布式系统，就不得不提Google的三驾马车：Gfs，Mapreduce，Bigtable。 虽然Google没有公布这三个产品的源码，但是他发布了这三个产品的详细设计论文。而且，Yahoo资助的Hadoop也有按照这三篇论文的开源Java实现：Hadoop对应Mapreduce，Hadoop Distributed File System (HDFS)对应Google fs，Hbase对应Bigtable。

GFS是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进行访问的应用。它运行于廉价的普通硬件上，提供容错功能。

Mapreduce是针对分布式并行计算的一套编程模型，本身离线计算，无需低延迟。

Bigtable就像文件系统需要数据库来存储结构化数据一样，GFS也需要Bigtable来存储结构化数据。

分布式系统的一般特征

任何分布式系统都需要完成两个基本任务：存储和计算。

在这两个基本任务下，要实现可扩展性、高性能、可用性、一致性。这几个特性也是分布式系统的衡量指标，正是为了在不同的程度上满足这些特性（或者说达到这些指标），才会设计出各种各样的算法、协议，然后根据业务的需求在这些特性间平衡。

FLP Impossibility（FLP不可能性）是分布式领域中一个非常著名的定理。它给出了一个令人吃惊的结论：在异步通信场景，即使只有一个进程失败了，没有任何算法能保证非失败进程能够达到一致性！这意味着，在假设网络可靠、节点只会因崩溃而失效的最小化异步模型系统中，仍然不存在一个可以解决一致性问题的确定性算法。无论是Paxos 算法还是Raft 算法。在现实中，我们都使用了TCP协议（保证了消息健壮、不重复和不乱序），每个节点都有NTP 时钟同步（可以使用超时），纯的异步场景相对比较少。

CAP理论就是说分布式数据存储，最多只能同时满足一致性（C，Consistency）、可用性（A， Availability）、分区容错性（P，Partition Tolerance）中的两者。

CAP三个特性只能满足其中两个，那么取舍的策略就共有三种： CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但放弃P的同时也就意味着放弃了系统的扩展性，也就是分布式节点受限，没办法部署子节点，这是违背分布式系统设计的初衷的。 CP without A：如果不要求A（可用），相当于每个请求都需要在服务器之间保持强一致，而P（分区）会导致同步时间无限延长(也就是等待数据同步完才能正常访问服务)，一旦发生网络故障或者消息丢失等情况，就要牺牲用户的体验，等待所有数据全部一致了之后再让用户访问系统。设计成CP的系统其实不少，最典型的就是分布式数据库，如Redis、HBase等。对于这些分布式数据库来说，数据的一致性是最基本的要求，因为如果连这个标准都达不到，那么直接采用关系型数据库就好，没必要再浪费资源来部署分布式数据库。 AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。典型的应用就如某米的抢购手机场景，可能前几秒你浏览商品的时候页面提示是有库存的，当你选择完商品准备下单的时候，系统提示你下单失败，商品已售完。这其实就是先在 A（可用性）方面保证系统可以正常的服务，然后在数据的一致性方面做了些牺牲，虽然多少会影响一些用户体验，但也不至于造成用户购物流程的严重阻塞。

Paxos算法

解决分布式系统的一致性的问题，是一种基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。算法就必须保证其安全性和活性。 安全性：只有被提出的提案才能被选定，并且只有一个提案被选定。 活性：最终保证会有一个提案被选定（选主）。 安全性和活性的组合结果就是：最终有且只有一个被提出的提案被选定。

Paxos算法利用的是选举，少数服从多数的思想，只要2N+1个节点中，有N个以上同意了某个决定，则认为系统达到了一致，并且按照Paxos原则，最终理论上也达到了一致，不会再改变。

Paxos算法中，有几个角色：

在具体的实现中，一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。还有一个很重要的概念叫提案（Proposal）。最终要达成一致的value就在提案里。

Paxos算法分为两个阶段：第一阶段选举，还没有提出提议；第二阶段主要是根据第一阶段的结果，明确接受谁的提议和提议的内容。具体如下： 阶段一： (a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。 (b) 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。 阶段二： (a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。 (b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

算法演示

Raft算法 与Paxos不同Raft强调的是易懂，Raft和Paxos一样只要保证n/2+1节点正常就能够提供服务，问题较为复杂时可以把问题分解为几个小问题来处理，Raft也使用了分而治之的思想把算法流程分为三个子问题：选举（Leader election）、日志复制（Log replication）、安全性（Safety）三个子问题。 每个节点有三种状态，在选举期间转换，Raft运行时提供服务的时候只存在Leader与Follower两种状态。

leader选举，开始时状态都为Follower，选举由定时器来触发，每个节点的选举定时器时间都是不一样的，倒计时结束后，节点状态由Follower转为Candidate，向其他节点发起RequestVote RPC请求，接收到n/2+1（过半数）个节点的投票，状态由Candidate转为Leader。Election timeout发生则Term递增，重新发起选举，在一个Term期间每个节点只能投票一次。

日志复制（Log Replication） 日志复制（Log Replication）主要作用是用于保证节点的一致性，这阶段所做的操作也是为了保证一致性与高可用性；当Leader选举出来后便开始负责客户端的请求，所有事务（更新操作）请求都必须先经过Leader处理，这些事务请求或说成命令也就是这里说的日志，我们都知道要保证节点的一致性就要保证每个节点都按顺序执行相同的操作序列，日志复制（Log Replication）就是为了保证执行相同的操作序列所做的工作；在Raft中当接收到客户端的日志（事务请求）后先把该日志追加到本地的Log中，然后通过heartbeat把该Entry同步给其他Follower，Follower接收到日志后记录日志然后向Leader发送ACK，当Leader收到大多数（n/2+1）Follower的ACK信息后将该日志设置为已提交并追加到本地磁盘中，通知客户端并在下个heartbeat中Leader将通知所有的Follower将该日志存储在自己的本地磁盘中。

安全性（Safety） 安全性是用于保证每个节点都执行相同序列的安全机制，如当某个Follower在当前Leader commit Log时变得不可用了，稍后可能该Follower又会被选举为Leader，这时新Leader可能会用新的Log覆盖先前已committed的Log，这就是导致节点执行不同序列；Safety就是用于保证选举出来的Leader一定包含先前 commited Log的机制。 选举安全性（Election Safety）：每个Term只能选举出一个Leader Leader完整性（Leader Completeness）：这里所说的完整性是指Leader日志的完整性，当Log在Term1被Commit后，那么以后Term2、Term3…等的Leader必须包含该Log；Raft在选举阶段就使用Term的判断用于保证完整性：当请求投票的该Candidate的Term较大或Term相同Index更大则投票，否则拒绝该请求。

END