分布式系统的一致性算法

看到了自己项目中使用单个redis实例实现的分布式锁，因此就把redis相关的知识点，以及Redlock等记录了下来，就有了Redis基础这篇随笔。

在理解Redlock算法时，看到了很多关于分布式系统中的一致性算法的文章，于站在巨人的肩膀上，温故而知新，今天就来做些总结整理。

 

一：分布式系统和一致性问题

分布式系统就是将一个完整的系统，按照业务功能，拆分成一个个独立的子系统，对于后端服务器开发人员来说，SOA微服务的架构想必肯定不陌生，它的好处自不必多说。

那分布式系统有什么难题和挑战呢？

让我们设想一个具体的场景，比如三个人讨论中午去哪里吃饭，第一个人说附近刚开了一个火锅店，听说味道非常不错；但第二个人说，不好，吃火锅花的时间太久了，还是随便喝点粥算了；

而第三个人说，那个粥店我昨天刚去过，太难喝了，还不如去吃麦当劳。结果，三个人僵持不下，始终达不成一致。

有人说，这还不好解决，投票呗。于是三个人投了一轮票，结果每个人仍然坚持自己的提议，问题还是没有解决。

有人又想了个主意，干脆我们选出一个leader，这个leader说什么，我们就听他的，这样大家就不用争了。

于是，大家开始投票选leader。结果很悲剧，每个人都觉得自己应该做这个leader。三个人终于发现，「选leader」这件事仍然和原来的「去哪里吃饭」这个问题在本质上是一样的，同样难以解决。

 ACID：

事务四个特性，原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability），

众所周知，同时满足这四个特性才能保证系统的完整性。

那在分布式系统中，还可以同时满足这四个特性吗？

CAP定理：

指的是在一个分布式系统中， Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），三者不可得兼。

但是分布式系统必然会有多个节点，每个节点都有自己的事务要求，所有分区容错性不能放弃。

因此在C和A之间的抉择就是分布式系统需要解决的根本问题。

BASE理论：

BASE是Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）三个短语的简写，

也是对 CAP定理中的一致性和可用性进行一个权衡的结果。

分布式系统就是为了提高系统的HA，所有解决一致性问题(consensus problem)是分布式系统面临的一个核心问题。

下面我们就来看看常用的一致性协议与算法。

 

二：一致性协议与算法

1：2PC

两阶段提交过程：

阶段一：提交事务请求（投票阶段）

　　1：事务询问：协调者向所有的参与者发送事务内容，询问是否可以执行事务提交，等待参与者相应。

　　2：执行事务：各节点参与者执行本地事务，并记录Undo和Redo日志（未commit）

　　3：参与者反馈事务询问：如果成功执行事务，向协调者反馈Yes，否则反馈No

阶段二：执行事务提交（）

　　如果阶段一反馈都是Yes，则：

　　　　1：协调者发起事务提交请求

　　　　2：参与者提交事务（commit）

　　　　3：反馈事务提交结果

　　　　4：完成事务（根据上一步结果确定）

　　如果阶段一有反馈No，则：

　　　　1：协调者发送回滚请求

　　　　2：参与者事务回滚（rollback）

　　　　3：返回回滚事务结果

　　　　4：中断事务

优点：原理简单，实现方便

缺点：同步阻塞（事务操作全部处于阻塞状态，对于分布式系统来说，限制性能）

　　　单点问题（协调者单点）

　　   数据不一致（阶段二参与者真正执行commit时，不能保证所有节点都成功commit）

 

2：3PC

其实理解了2PC，就很容易理解3PC了

简单的画了三阶段提交的流程图，它其实就是二阶段提交的改进版，将2PC的阶段一（提交事务请求）分成了两步，CanCommit和PreCommit。

相比2PC，3PC最大的优点是降低了参与者事务提交的阻塞范围，但是同2PC一样还是可能出现数据不一致的问题。

 

3：Paxos

说到一致性算法就不得不说大名鼎鼎的Paxos了，（Chubby的作者曾说过：世上只有一种一致性算法，就是Paxos）。

在了解Paxos算法之前，先了解一下拜占庭将军问题(Byzantine Generals Problem)。这个问题也是由Paxos的作者Leslie Lamport提出的。

拜占庭帝国的有许多支军队分开驻扎，每一支军队由一位拜占庭将军(Byzantine general)率领。

为了制定出一个统一的作战计划，每一位将军需要通过信差(messenger)与其它将军互通消息。但是，在拜占庭将军之间可能出现了叛徒(traitor)。

这些叛徒将军的目的是阻挠其他忠诚的将军(loyal generals)达成一致的作战计划。为了这一目的，他们可能做任何事，比如串通起来，故意传出虚假消息，或者不传出任何消息。

这就是著名的 ”拜占庭将军问题“。

我们来看一个简单的例子。假设有5位将军，他们投票来决定是进攻还是撤退。其中两位认为应该进攻，还有两位认为应该撤退，这时候进攻和撤退的票数是2:2打平了。

第五位将军恰好是个叛徒，他告诉前两位应该进攻，但告诉后两位应该撤退，结果前两位将军最终决定进攻，而后两位将军却决定撤退。没有达成一致的作战计划。

要解决这个问题，我们是希望能找到一个算法，保证在存在叛徒阻挠的情况下，我们仍然能够达成如下目标：

• A. 所有忠诚的将军都得到了相同（一致）的作战计划。比如都决定进攻，或都决定撤退，而不是有些将军认为应该进攻，其他将军却决定撤退。
• B. 忠诚的将军不仅得到了相同的作战计划，还应该保证得到的作战计划是合理的(reasonable)。比如，本来进攻是更有利的作战计划，但由于叛徒的阻挠，最终却制定出了一起撤退的计划。这样我们的算法也算失败了。

可以看出，上面的目标A，是比较明确的，至少给定一个算法很容易判定它有没有达到这个目标。但目标B却让人无从下手。一个作战计划是不是「合理」的，本来就不好定义。

即使没有叛徒的存在，忠诚的将军们也未必就一定能制定出合理的计划。这涉及到科学研究中一个非常重要的问题，如果一个事情不能用一种形式化的方式清晰的定义出来，

对于它的研究也就无从谈起，这个事情本身也无法上升到科学的层面。Lamport在对拜占庭将军问题的研究中，一个突出的贡献就是，把这个看似不太好界定的问题，

巧妙地归约到了一个能用数学语言精确描述的问题上去。下面我们就看一下这个过程是怎么做的。

首先我们考虑一下将军们制定作战计划的过程（先假设没有叛徒）。每一位将军根据自己对战局的观察，给出他建议的作战计划——是进攻还是撤退，这称为作战提议。

然后，每位将军把自己的作战提议通过信差传达给其他每一位将军。现在每一位将军都知道了其他将军的作战提议，再加上他自己的作战提议，他需要根据所有这些信息得到最终的一个作战计划。

为了表达上更清晰，我们给每位将军进行编号，分别是1, 2, …, n，每位将军提出的作战提议记为v(1), v(2), …, v(n)，一共是n个值，这其中有些代表「进攻」，有些代表「撤退」。

经过信差传递消息之后，每位将军都看到了相同的作战提议序列v(1), v(2), …, v(n)，当然这其中的一个是当前这位将军自己提出来的。

然后只要每位将军采用同样的方法，对所有的v(1), v(2), …, v(n)这些信息进行汇总，就能得到同样的最终作战计划。

比如，容易想到的一个方法是投票法，即对v(1), v(2), …, v(n)中不同的作战提议进行投票，最后选择得票最多的作为最终作战计划。

当然，这样得到的最终作战计划也不能保证就是最好的，但这应该是我们能做到的最好的了。我们现在仍然假设将军里没有叛徒。

我们发现，前面提到的目标A和目标B的要求可以适当「降低」一些：我们不再关注将军们是否能达成最终一致的作战计划，并且这个计划是不是「合理」；

我们只关注每个将军是否收到了完全相同的作战提议v(1), v(2), …, v(n)。只要每位将军收到的这些作战提议是完全相同的，他们再用同样的方法进行汇总，就很容易得到最终一致的作战计划。

至于这个最终的作战计划是不是最好的，那就跟很多「人为」的因素有关了，我们不去管它。

现在我们考虑将军中出现了叛徒。遵循前面的思路，我们仍然希望每位将军能够收到完全相同的作战提议v(1), v(2), …, v(n)。

现在我们仔细审视一下其中的一个值，v(i)，在前面的描述中，它表示来自第i个将军的作战提议。如果第i个将军是忠诚的，那么这个定义没有什么问题。

但是，如果第i个将军是叛徒，那么就有问题了。为什么呢？因为叛徒可以为所欲为，他为了扰乱整个作战计划的制定，完全可能向不同的将军给出不同的作战提议。

这样的话，不同的忠诚将军收到的来自第i个将军的v(i)可能是不同的值。这样v(i)这个定义就不对了，它需要改一改。

不管怎么样，即使存在叛徒，我们还是希望每位将军最终是基于完全相同的作战提议来做汇总，这些作战提议仍然记为v(1), v(2), …, v(n)。

不过，这里的v(i)不再表示来自第i个将军的作战提议，而是表示经过我们设计的某个一致性算法处理之后，每位将军最终看到的第i个提议。

这里需要分两种情况讨论。首先第一种情况，如果第i个将军是忠诚的，那么我们自然希望这个v(i)就是第i个将军发送出来的作战提议。

换句话说，我们希望经过一致性算法处理之后，第i个将军如果是忠诚的，那么它的提议能够被如实地传达给其他将军，而不会被叛徒的行为所干扰。

这是可能制定出「合理」作战计划的前提。第二种情况，如果第i个将军是叛徒，那么他有可能向不同的将军发送不同的提议。

这时候我们不能够只听他的一面之词，而是希望经过一致性算法处理之后，各个将军之间充分交换意见，然后根据其他各个将军转述的信息，综合判断得到一个v(i)。

这个v(i)是进攻还是撤退，并不太重要，关键是要保证每位将军得到的v(i)是相同的。只有这样，各位将军经过汇总所有的v(1), v(2), …, v(n)之后才能得到最终的完全一致的作战计划。

根据上面的分析，我们发现，在这两种情况中，我们都只需要关注单个将军（也就是第i个将军）所发出的提议如何传达给其他将军。重点终于来了！

至此，我们就能够把原来的问题归约到一个子问题上。这个子问题，才是Leslie Lamport在他的论文中被真正命名为「拜占庭将军问题(Byzantine Generals Problem)」的那个问题。

在这个问题中，我们只关注发送命令的单个将军，称他为主将(commanding general)，而其他接受命令的将军称为副官(lieutenant)。下面是「拜占庭将军问题」的精确描述。

一个主将发送命令给n-1个副官，如何才能确保下面两个条件：

• (IC1) 所有忠诚的副官最终都接受相同的命令。
• (IC2) 如果主将是忠诚的，那么所有忠诚的副官都接受主将发出的命令。

这其实正好对应了我们前面已经讨论过的两种情况。如果主将是忠诚的，那么条件IC2保证了命令如实地传递，这时候条件IC1自然也满足了；

如果主将是叛徒，那么条件IC2没有意义了，而条件IC1保证了，即使叛徒主将对每个副官发出不同的命令，每个副官仍然能最终获得一致的命令。

这里有两个地方可能让人产生疑惑。

第一，有些人会问了，难道主将还能是叛徒？主将都是叛徒了，还有啥搞头啊？其实是这样的，这个「拜占庭将军问题」只是原问题的一个子问题。

当n个将军通过传递消息来决策作战计划的时候，可以分解成n个「拜占庭将军问题」，即分别以每位将军作为主将，以其余n-1位将军作为副官。

如果有一个算法能够解决「拜占庭将军问题」，那么同时运行n个算法实例，就能使得每位将军都获得完全相同的作战提议序列，即前面我们提到的v(1), v(2), …, v(n)。

最后，每位将军将v(1), v(2), …, v(n)使用相同的方法进行汇总（比如按多数投票），就能得到最终的作战计划。

第二，当主将是叛徒的时候，他可以向不同的副官发送不同的命令，怎么可能每个副官仍然能最终获得一致的命令呢？这正是算法需要解决的。

其实这也容易解释（我们前面也提到过这个思路），由于主将可能向不同的副官发送不同的命令，所以副官不能直接采用主将发来的命令，而是也要看看其他副官转述来的主将的命令是什么。

然后，一个副官综合了由所有副官转述的命令（再加上主将直接发来的命令）之后，就可能得到比较全面的信息，从而做出一致的判断（在实际中是个不断迭代的过程）。

好了，我们用了这么多篇幅，终于把「拜占庭将军问题」本身描述清楚了。这实际上也是最难的部分。

只要问题本身分析清楚了，如何设计一个能解决它的算法就只是细节问题了。我们这里不深入算法的细节了，感兴趣的读者可以去查阅下列论文：

• 《The Byzantine Generals Problem》，下载地址：http://lamport.azurewebsites.net/pubs/byz.pdf
• 《Reaching Agreement in the Presence of Faults》，下载地址：http://lamport.azurewebsites.net/pubs/reaching.pdf

我们这里只提一下论文给出的算法的结论。

使用不同的消息模型，「拜占庭将军问题」有不同的解法。

• 如果将军之间使用口头消息(oral messages)，也就是说，消息被转述的时候是可能被篡改的，那么要对付m个叛徒，需要至少有3m+1个将军（其中至少2m+1个将军是忠诚的）。
• 如果将军之间使用签名消息(signed messages)，也就是说，消息被发出来之后是无法伪造的，只要被篡改就会被发现，那么对付m个叛徒，只需要至少m+2个将军，也就是说至少2个忠诚的将军（如果只有1个忠诚的将军，显然这个问题没有意义）。这种情况实际相当于对忠诚将军的数目没有限制。

 

事实上，大多数分布式系统都是在一个局域网中，所以消息被篡改或者消息不完整都是可以排除或者避免的。

而Paxos算法（Paxos Made Simple）就解决了在消息没有损坏（corrupted）的可信任环境的前提下，保证系统一致性。

根据Paxos的论文所说，Paxos的设计是基于异步(asynchronous)、非拜占庭(non-Byzantine)的系统模型，即：

• 节点可以以任意速度运行，可能宕机、重启。但是，算法执行过程中需要记录的一些变量，在重启后应该能够恢复。
• 消息可以延迟任意长时间，可以重复(duplicated)，可以丢失(lost)，但不能损坏(corrupted)。

通常把能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」，简称为BFT。

BFT的算法应该可以解决任何错误下的分布式一致性问题，也包括Paxos所解决的问题，而Paxos只能容忍非拜占庭错误。

但是，在只有非拜占庭错误出现的前提下，Paxos基于异步模型，是比同步模型更弱的系统假设，因此算法更鲁棒(Robust)。当然，Paxos也更高效。

Google Chubby 是基于Paxos算法的一个工程实践。

 

4：Raft

Raft is a consensus algorithm for managing a replicated log.

继续阅读之前，先看一下Raft动画原理（http://thesecretlivesofdata.com/raft/）

在Raft中，节点有三种角色：

• Leader：负责接收客户端的请求，将日志复制到其他节点并告知其他节点何时应用这些日志是安全的

• Candidate：用于选举Leader的一种角色

• Follower：负责响应来自Leader或者Candidate的请求

　　　　　　　　　　　　　　不同角色之间的转换

 

 Raft实现一致性的最重要两个功能就是：

1. 选主 Leader Election
2. 复制日志 Log Replication

Redis中哨兵集群中的哨兵领导者选举和Redis-Cluster中的主节点选举都是基于Raft算法实现的。

 

5：ZAB

作为一个高效且可靠分布式协调服务，Zookeeper可谓是大名鼎鼎，提供了诸如统一命名服务，配置管理，分布式锁等基础服务。

Zookeeper集群没有采用典型的Master\Slave模式，而是引入了Leader、Follower、Observer三种角色，

其中Leader为客户端提供读和写服务，而Follower和Observer只提供读服务，两者区别是，Observer不参与Leader选举。

ZAB(ZooKeeper Atomic Broadcast)是为ZooKeeper专门设计的一种支持崩溃恢复的原子广播协议。

ZAB协议对数据事务的处理请求方式为：

所有事务请求必须由一个全局唯一的服务器来协调处理，这个服务器被称为Leader（只有一个），而余下的服务器被称为Follower。

Leader负责将一个客户端的事务请求转换为一个事务提议（Proposal），并将该Propsal分发给集群中的所有Follower。

之后等待所有Follower的反馈，一旦超过单数的Follower进行了正确的反馈，那么Leader会再次向所有Follower发起Commit消息，

要求将上一次Proposal进行提交。

消息广播：

类似于2PC的原子广播协议，由Leader将事务Proposal分发给集群中的所有Follower，Leader收集Follower的ACK，最后进行事务提交（commit）。

其中Leader会保证每个事务Proposal都有一个全局递增的唯一ID（ZXID），而且Leader分发给Follower的消息会放入一个单独的队列里，保证消息FIFO。

但与2PC不同的是，Follower对Leader发起的Proposal的反馈，要么是正常反馈，要么就抛弃Leader。

这意味着Leader在收到超过一半的Follower的正常反馈后，就可以继续提交事务的commit了。

好处是可用性更高，但是如果Leader崩溃了，那么很多Follwer出现数据不一致，整个集群数据也就不一致了。

崩溃恢复

为了解决Leader崩溃，出现的数据不一致情况，因此需要一个可靠高效的Leader选举算法。

初始阶段Leader选举

　　此时节点状态为election，投票（myid,ZXID），ZXID大的优先作为Leader，如果ZXID相同myid大的优先作为Leader，

　　此时服务器状态分别为leading、following。

运行期间Leader选举

　　当Leader崩溃后，开始Leader选举，首先服务器状态改变，所有非Observer服务器状态变为looking，

　　同样节点发起投票（myid,ZXID），统计投票，最后选出Leader。　

从3.4.0版本开始，ZooKeeper的选举算法只保留了TCP版本的FastLeaderElection算法。

（算法实现细节，可以参考：ZooKeeper’s atomic broadcast protocol：http://www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf）

 

三：参考文献

1：《从 Paxos 到 Zookeeper——分布式一致性原理和实践》

2：漫谈分布式系统、拜占庭将军问题与区块链

3：共识算法：Raft