05丨Paxos算法（一）：如何在多个节点间确定某变量的值?

提到分布式算法，就不得不提 Paxos 算法，在过去几十年里，它基本上是分布式共识的代名词，因为当前最常用的一批共识算法都是基于它改进的。比如，Fast Paxos 算法、Cheap Paxos 算法、Raft 算法、ZAB 协议等等。而很多同学都会在准确和系统理解 Paxos 算法上踩坑，比如，只知道它可以用来达成共识，但不知道它是如何达成共识的。

兰伯特提出的Paxos算法包含2个部分：

1. 一个是Basic Paxos算法，描述的多节点之间如何就某个值（提案Value）达成共识；
2. 另一个是 Multi-Paxos 思想，描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。

可因为兰伯特提到的 Multi-Paxos 思想，缺少代码实现的必要细节（比如怎么选举领导者），所以在理解上比较难。

为了让你理解 Paxos 算法，分别以Basic Paxos 和 Multi-Paxos 为核心，带你了解 Basic Paxos 如何达成共识，以及针对 Basic Paxos 的局限性 Multi-Paxos 又是如何改进的。

在我看来，Basic Paxos 是 Multi-Paxos 思想的核心，说白了，MultiPaxos 就是多执行几次 Basic Paxos。所以掌握它之后，你能更好地理解后几讲基于 Multi-Paxos 思想的共识算法（比如 Raft 算法），还能掌握分布式共识算法的最核心内容，当现在的算法不能满足业务需求，进行权衡折中，设计自己的算法。

来看一道思考题

假设我们要实现一个分布式集群，这个集群是由节点A、B、C组成，提供只读KV存储服务。你应该知道，创建只读变量的时候，必须要对它进行赋值，而且这个值后续没办法修改。因此一个节点创建只读变量后就不能再修改它了，所以所有节点必须要先对只读变量的值达成共识，然后所有节点再一起创建这个只读变量。

那么，当有多个客户端（比如客户端1、2）访问这个系统，试图创建同一个只读变量（比如X），客户端1试图创建值为3的X，客户端2试图创建值为7的X，这样要如何达成共识，实现各节点上X值的一致呢？带着这个问题，我们进入今天的学习。

在一些经典的算法中，你会看到一些既形象又独有的概念（比如二阶段提交协议中的协调者），Basic Paxos算法也不例外。为了帮助人们更好地理解Basic Paxos算法，兰伯特在讲解时，也使用了一些独有而且比较重要的概念，提案、准备（Prepare）请求、接受（Accept）请求、角色等等，其中最重要的就是“角色”。因为角色是对 Basic Paxos 中最核心的三个功能的抽象，比如，由接受者（Acceptor）对提议的值进行投票，并存储接受的值。

你需要了解的三种角色

在Basic Paxos中，有提议者（Proposer）、接受者（Accetor）、学习者（Learner）三种角色，它们之间的关系如下：

看着是不是有些复杂，其实并不难理解：

1. 提议者（Proposer）：提议一个值，用于投票表决。为了方便演示，你可以把客户端 1 和 2 看作是提议者。但在绝大多数场景中，集群中收到客户端请求的节点，才是提议者。这样做的好处是，对业务代码没有入侵性，也就是说，我们不需要在业务代码中实现算法逻辑，就可以像使用数据库一样访问后端的数据。
2. 接受者（Acceptor）：对每个提议的值进行投票，并存储接受的值，比如 A、B、C 三个节点。 一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。
3. 学习者（Learner）：被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。一般来说，学习者是数据备份节点，比如“Master-Slave”模型中的 Slave，被动地接受数据，容灾备份。

讲到这儿，你可能会有疑惑：前面不是说接收客户端请求的节点是提议者吗？这里怎么又是接受者呢？这是因为一个节点（或进程）可以身兼多个角色。想象一下，一个 3 节点的集群，1 个节点收到了请求，那么该节点将作为提议者发起二阶段提交，然后这个节点和另外2 个节点一起作为接受者进行共识协商，就像下图的样子：

其实，这三个角色，在本质上代表的是三种功能：

1. 提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商；
2. 接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存；
3. 学习者代表存储数据，不参与共识协商，只接受达成共识的值，存值保存。

因为一个完整的算法过程是由这三个角色对应的功能组成的，所以理解这三种角色，是你理解Basic Paxos如何就提议的值达成共识的基础。那么接下来，咱们看看如何使用Basic Paxos达成共识，解决开篇提到的那道思考题。

如何达成共识？

想象这样一个场景，现在疫情这么严重，每个村的路都封得差不多了，就你的村委会不作为，迟迟没有什么防疫的措施。你决定给村委会提交个提案，提一些防疫的建议，除了建议之外，为了和其他村民的提案做区分，你的提案还得包含一个提案编号，来起到唯一标识的作用。

与你的做法类似，在 Basic Paxos 中，兰伯特也使用提案代表一个提议。不过在提案中，除了提案编号，还包含了提议值。为了方便演示，我使用[n, v]表示一个提案，其中 n 为提案编号，v 为提议值。

要强调一下，整个共识协商是分2个阶段进行的（也就是二阶段提交），那么具体要如何协商呢？

我们假设客户端1的提案编号为1，客户端2的提案编号为5，并假设节点A、B先收到来自客户端1的准备请求，节点C先收到来自客户端2的准备请求。

准备（Prepare）阶段

先来看第一个阶段，首先客户端 1、2 作为提议者，分别向所有接受者发送包含提案编号的准备请求：

你要注意，在准备请求中是不需要指定提议的值的，只需要携带提案编号就可以了，这是很多同学容易产生误解的地方。

接着，当节点A、B收到的提案编号为1的准备请求，节点C收到提案编号为5的准备请求后，将进行这样的处理：

1. 由于之前没有通过任何提案，所以节点A、B将返回一个“尚无提案”的响应。也就是说节点A和B在告诉提议者，我之前没有通过任何提案呢，并承诺以后不再响应提案编号小于等于1的准备请求，不会通过编号小于1的提案。
2. 节点C也是如此，它将返回一个“尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。

另外，当节点A、B收到编号为5的准备请求，和节点C收到提案编号为1的准备请求的时候，将进行这样的处理过程：

1. 当节点A、B收到提案编号为5的准备请求的时候，因为提案编号5大于它们之前响应的准备请求的提案编号1，而且两个节点都没有通过任何提案，所以它将返回一个“尚无提案”的响应，并承诺以后不再响应提案小于等于5的准备请求，不会通过编号小于 5 的提案。
2. 当节点C收到提案编号为1的准备请求的时候，由于提案编号1小于它之前响应的准备请求的提案编号5，所以丢弃该准备请求，不做响应。

接受（Accept）阶段

第二个阶段也就是接受阶段，首先客户端1、2在收到大多数节点的准备响应之后，会分别发送接收请求：

1. 当客户端1收到大多数的接受者（节点A、B）的准备响应后，根据响应中提案编号最大的提案的值，设置接受请求中的值。因为该值在来自节点A、B的准备响应中都为空（也就是“尚无提案”），所以就把自己的提议值3作为提案的值，发送接受请求[1, 3]。
2. 当客户端3收到大多数的接受者的准备响应后（节点A、B和节点C），根据响应中提案编号最大的提案的值，来设置接受请求中的值。因为该值来自节点A、B、C的准备响应中都为空（也就是“尚无提案”），所以就把自己的提议值7作为提案的值，发送接受请求[5, 7]。

当三个节点收到2个客户端的接受请求时，会进行这样的处理：

1. 当节点A、B、C收到接受请求[1, 3]的时候，由于提案的提案编号1小于三个节点承诺能通过的提案的最小提案编号5，所以提案[1, 3]将被拒绝。
2. 当节点 A、B、C 收到接受请求[5, 7]的时候，由于提案的提案编号5 不小于三个节点承诺能通过的提案的最小提案编号 5，所以就通过提案[5, 7]，也就是接受了值 7，三个节点就 X 值为 7 达成了共识。

讲到这儿我想补充一下，如果集群中有学习者，当接受者通过了一个提案时，就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案，那么它也通过该提案，接受该提案的值。

通过上面的演示过程，你可以看到，最终各节点就 X 的值达成了共识。那么在这里我还想强调一下，Basic Paxos 的容错能力，源自“大多数”的约定，你可以这么理解：当少于一半的节点出现故障的时候，共识协商仍然在正常工作。

内容小结

本节课我主要带你了解了 Basic Paxos 的原理和一些特点，我希望你明确这样几个重点。

1. 你可以看到，Basic Paxos 是通过二阶段提交的方式来达成共识的。二阶段提交是达成共识的常用方式，如果你需要设计新的共识算法的时候，也可以考虑这个方式。
2. 除了共识，Basic Paxos 还实现了容错，在少于一半的节点出现故障时，集群也能工作。它不像分布式事务算法那样，必须要所有节点都同意后才提交操作，因为“所有节点都同意”这个原则，在出现节点故障的时候会导致整个集群不可用。也就是说，“大多数节点都同意”的原则，赋予了 Basic Paxos 容错的能力，让它能够容忍
   少于一半的节点的故障。
3. 本质上而言，提案编号的大小代表着优先级，你可以这么理解，根据提案编号的大小，接受者保证三个承诺，具体来说：如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；如果接受请求中的提案的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息。

课堂思考

在示例中，如果节点 A、B 已经通过了提案[5, 7]，节点 C 未通过任何提案，那么当客户端 3 提案编号为 9 时，通过 Basic Paxos 执行“SET X = 6”，最终三个节点上 X 值是多少呢？为什么呢？

节点A、B、C上的X值都是7。

原因：在Prepare阶段，提议者（客户端3）发现已有大多数节点（A和B）接受了提案[5,7]（值7），因此必须选择值7（而不是6）进行提交，最终所有节点接受提案[9,7]。

06丨Paxos算法（二）：Multi-Paxos不是一个算法，而是统称

Basic Paxos 只能就单个值（Value）达成共识，一旦遇到为一系列的值实现共识的时候，它就不管用了。虽然兰伯特提到可以通过多次执行 Basic Paxos 实例（比如
每接收到一个值时，就执行一次 Basic Paxos 算法）实现一系列值的共识。但是，很多同学读完论文后，应该还是两眼摸黑，虽然每个英文单词都能读懂，但还是不理解兰伯特提到的 Multi-Paxos，为什么Multi-Paxos 这么难理解呢？

在我看来，兰伯特并没有把 Multi-Paxos 讲清楚，只是介绍了大概的思想，缺少算法过程的细节和编程所必须的细节（比如缺少选举领导者的细节）。这也就导致每个人实现的 Multi-Paxos 都不一样。不过从本质上看，大家都是在兰伯特提到的 Multi-Paxos 思想上补充细节，设计自己的 Multi-Paxos 算法，然后实现它（比如 Chubby 的
Multi-Paxos 实现、Raft 算法、ZAB 协议等）。

所以在这里，我补充一下：兰伯特提到的Multi-Paxos是一种思想，不是算法。而Multi-Paxos算法是一个统称，它是指基于Multi-Paxos思想，通过多个Basic Paxos实例实现一系列指的共识的算法（比如Chubby的Multi-Paxos实现、Raft算法等）。这一点尤其需要你注意。

为了帮你掌握 Multi-Paxos 思想，我会先带你了解，对于 Multi-Paxos 兰伯特是如何思考的，也就是说，如何解决 Basic Paxos 的痛点问题；然后我再以 Chubby 的 Multi-Paxos 实现为例，具体讲解一下。为啥选它呢？因为 Chubby 的 Multi-Paxos 实现，代表了 Multi-Paxos 思想在生产环境中的真正落地，它将一种思想变成了代码实现。

兰伯特关于 Multi-Paxos 的思考

熟悉 Basic Paxos 的同学可能还记得，Basic Paxos 是通过二阶段提交来达成共识的。在第一阶段，也就是准备阶段，接收到大多数准备响应的提议者，才能发起接受请求进入第二阶段（也就是接受阶段）：

而如果我们直接通过多次执行Basic Paxos实例，来实现一系列指的共识，就会存在几个问题：

1. 如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。你想象一下，一个 5 节点的集群，如果 3 个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应（比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应）而准备失败，需要重新协商。
2. 2轮RPC通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大。你要知道，分布式系统的运行是建立在 RPC 通讯的基础之上的，因此，延迟一直是分布式系统的痛点，是需要我们在开发分布式系统时认真考虑和优化的。

那么如何解决上面的2个问题呢？可以通过引入领导者和优化Basic Paxos执行来解决，咱们首先聊一聊领导者。

领导者（Leader）

我们可以通过引入领导者节点，也就是说，领导者节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了：

在这里，我补充一点：在论文中，兰伯特没有说如何选举领导者，需要我们在实现 Multi-Paxos 算法的时候自己实现。 比如在 Chubby 中，主节点（也就是领导者节点）是通过执行 Basic Paxos 算法，进行投票选举产生的。

那么，如何解决第二个问题，也就是如何优化 Basic Paxos 执行呢？

优化Basic Paxos执行

我们可以采用“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，优化Basic Paxos执行。也就是说，领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。这时，领导者在提交命令时，可以省掉准备阶段，直接进入到接受阶段：

你看，和重复执行Basic Paxos相比，Multi-Paxos引入领导者节点之后，因为只有领导者节点一个提议者，只有它说了算，所以就不存在提案冲突。另外，当主节点处于稳定状态时，就省掉准备阶段，直接进入接受阶段，所以在很大程度上减少了往返的消息数，提升了性能，降低了延迟。

Chubby的Multi-Paxos实现

既然兰伯特只是大概的介绍了 Multi-Paxos 思想，那么 Chubby 是如何补充细节，实现 Multi-Paxos 算法的呢？

首先，它通过引入主节点，实现了兰伯特提到的领导者（Leader）节点的特性。也就是说，主节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了。

另外，在 Chubby 中，主节点是通过执行 Basic Paxos 算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期（Lease）。比如在实际场景中，几天内都是同一个节点作为主节点。如果主节点故障了，那么其他的节点又会投票选举出新的主节点，也就是说主节点是一直存在的，而且是唯一的。

其次，在 Chubby 中实现了兰伯特提到的，“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制。

最后，在 Chubby 中，实现了成员变更（Group membership），以此保证节点变更的时候集群的平稳运行。

在Chubby中，为了实现强一致性，读操作也只能在主节点上执行。 也就是说，只要数据写入成功，之后所有的客户端读到的数据都是一致的。具体的过程，就是下面的样子。

所有的读请求和写请求都由主节点来处理。当主节点从客户端接收到写请求后，作为提议者，执行Basic Paxos实例，将数据发送给所有的节点，并且在大多数的服务器接受了这个写请求之后，再响应给客户端成功：

当主节点接收到读请求后，处理就比较简单了，主节点只需要查询本地数据，然后返回给客户端就可以了：

Chubby 的 Multi-Paxos 实现，尽管是一个闭源的实现，但这是 MultiPaxos 思想在实际场景中的真正落地，Chubby 团队不仅编程实现了理论，还探索了如何补充细节。其中的思考和设计非常具有参考价值，不仅能帮助我们理解 Multi-Paxos 思想，还能帮助我们理解其他的 Multi-Paxos 算法（比如 Raft 算法）。

内容小结

本节课我主要带你了解了 Basic Paxos 的局限，以及 Chubby 的Multi-Paxos 实现。我希望你明确的重点如下：

1. 兰伯特提到的 Multi-Paxos 是一种思想，不是算法，而且还缺少算法过程的细节和编程所必须的细节，比如如何选举领导者等，这也就导致了每个人实现的 Multi-Paxos 都不一样。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列数据的共识的算法（比如 Chubby 的Multi Paxos 实现、Raft 算法等）。
2. Chubby 实现了主节点（也就是兰伯特提到的领导者），也实现了兰伯特提到的 “当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段” 这个优化机制，省掉 Basic Paxos 的准备阶段，提升了数据的提交效率，但是所有写请求都在主节点处理，限制了集群处理写请求的并发能力，约等于单机。
3. 因为在 Chubby 的 Multi-Paxos 实现中，也约定了“大多数原则”，也就是说，只要大多数节点正常运行时，集群就能正常工作，所以Chubby 能容错（n - 1）/2 个节点的故障。
4. 本质上而言，“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，是通过减少非必须的协商步骤来提升性能的。这种方法非常常用，也很有效。比如，Google 设计的QUIC 协议，是通过减少 TCP、TLS 的协商步骤，优化 HTTPS 性能。我希望你能掌握这种性能优化思路，后续在需要时，可以通过
   减少非必须的步骤，优化系统性能。

最后，我想说的是，我个人比较喜欢 Paxos 算法（兰伯特的 Basic Paxos 和 Multi-Paxos），虽然 Multi-Paxos 缺失算法细节，但这反而给我们提供了思考空间，让我们可以反复思考和考据缺失的细节，比如在 Multi-Paxos 中到底需不需要选举领导者，再比如如何实现提案
编号等等。

但我想强调，Basic Paxos 是经过证明的，而 Multi-Paxos 是一种思想，缺失实现算法的必须编程细节，这就导致，Multi-Paxos 的最终算法实现，是建立在一个未经证明的基础之上的，正确性是个问号。

与此同时，实现 Multi-Paxos 算法，最大的挑战是如何证明它是正确的。 比如 Chubby 的作者做了大量的测试，和运行一致性检测脚本，验证和观察系统的健壮性。在实际使用时，我不推荐你设计和实现新的 Multi-Paxos 算法，而是建议优先考虑 Raft 算法，因为 Raft 的正确性是经过证明的。当 Raft 算法不能满足需求时，你再考虑实现和优化 Multi-Paxos 算法。

课堂思考

既然，我提了 Chubby 只能在主节点上执行读操作，那么在最后，我给你留了一个思考题，这个设计有什么局限呢？

07丨Raf算法（一）：如何选举领导者？

Raft 算法属于 Multi-Paxos 算法，它是在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多。

除此之外，Raft算法是现在分布式系统开发首选的共识算法。绝大多数选用 Paxos 算法的系统（比如 Cubby、Spanner）都是在 Raft 算法发布前开发的，当时没得选；而全新的系统大多选择了 Raft 算法（比如 Etcd、Consul、CockroachDB）。

对你来说，掌握这个算法，可以的心应手地处理绝大部分场景的容错和一致性需求，比如分布式配置系统、分布式NoSQL存储等等，轻松突破系统的单机限制。

如果要用一句话概括 Raft 算法，我觉得是这样的：从本质上说，Raft算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。这句话比较抽象，我来做个比喻，领导者就是 Raft 算法中的霸道总裁，通过霸道的“一切以我为准”的方式，决定了日志中命令的值，也实现了各节点日志的一致。

会用三讲的时间，分别以领导者选举、日志复制、成员变更为核心，讲解 Raft 算法的原理，在实战篇中，会带你进一步剖析 Raft 算法的实现，介绍基于 Raft 算法的分布式系统开发实战。那么我希望从原理到实战，在帮助你掌握分布式系统架构设计技巧和开发实战能力的同时，加深你对 Raft 算法的理解。

在课程开始之前，我们先来看一道思考题。

既然要选举领导者，那要从哪些成员中选举呢？除了领导者，Raft 算法还支持哪些成员身份呢？这部分内容是你需要掌握的，最基础的背景知识。

有哪些成员身份？

成员身份，又叫做服务器节点状态，Raft 算法支持领导者
（Leader）、跟随者（Follower）和候选人（Candidate） 3 种状态。为了方便讲解，我们使用不同的图形表示不同的状态。在任何时候，每一个服务器节点都处于这 3 个状态中的 1 个。

1. 跟随者：就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。
2. 候选人：候选人将向其他节点发送请求投票（RequestVote）RPC消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。
3. 领导者：蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。”

需要你注意的是，Raft 算法是强领导者模型，集群中只能有一个“霸道总裁”。

选举领导者的过程

那么这三个成员是怎么选出来领导者的呢？为了方便你理解，我以图例的形式演示一个典型的领导者选举过程。
首先，在初始状态下，集群中所有的节点都是跟随者的状态。

Raft 算法实现了随机超时时间的特性。也就是说，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。通过上面的图片你可以看到，集群中没有领导者，而节点 A 的等待超时时间最小（150ms），它会最先因为没有等到领导者的心跳信息，发生超时。

这个时候，节点 A 就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者。

如果其他节点接收到候选人 A 的请求投票 RPC 消息，在编号为 1 的这届任期内，也还没有进行过投票，那么它将把选票投给节点 A，并增加自己的任期编号。
如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。

节点 A 当选领导者后，他将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举，篡权。

讲到这儿，你是不是发现领导者选举很容易理解？与现实中的议会选举也蛮类似？当然，你可能还是对一些细节产生一些疑问：

1. 节点间是如何通讯的呢？
2. 什么是任期呢？
3. 选举有哪些规则？
4. 随机超时时间又是什么？

选举过程四连问

节点间如何通讯？

在 Raft 算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），在领导者选举中，需要用到这样两类的 RPC：

1. 请求投票（Request Vote） RPC，是由候选人在选举期间发起，通知各节点进行投票；
2. 日志复制（Append Entries）RPC，是由领导者发起，用来复制日志和提供心跳消息。

我想强调的是，日志复制 RPC 只能由领导者发起，这是实现强领导者模型的关键之一，希望你能注意这一点，后续能更好地理解日志复制，理解日志的一致是怎么实现的。

什么是任期？

我们知道，议会选举中的领导者是有任期的，领导者任命到期后，要重新开会再次选举。Raft 算法中的领导者也是有任期的，每个任期由单调递增的数字（任期编号）标识，比如节点 A 的任期编号是 1。任期编号是随着选举的举行而变化的，这是在说下面几点。

1. 跟随者在等待领导者心跳信息超时后，推荐自己为候选人时，回增加自己的任期号，比如节点A的当前任期编号为0，那么在推荐自己为候选人时，会将自己的任期编号增加为 1。
2. 如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如节点 B 的任期编号是0，当收到来自节点 A 的请求投票 RPC 消息时，因为消息中包含了节点 A 的任期编号，且编号为 1，那么节点 B 将把自己的任期编号更新为 1。

我想强调的是，与现实议会选举中的领导者的任期不同，Raft 算法中的任期不只是时间段，而且任期编号的大小，会影响领导者选举和请求的处理。

1. 在Raft算法中约定，如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为 3 的领导者节点 B，收到来自新领导者的，包含任期编号为 4 的心跳消息，那么节点 B 将立即恢复成跟随者状态。
2. 还约定如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。比如节点 C 的任期编号为 4，收到包含任期编号为 3 的请求投票 RPC 消息，那么它将拒绝这个消息。

在这里，你可以看到，Raft 算法中的任期比议会选举中的任期要复杂。同样，在 Raft 算法中，选举规则的内容也会比较多。

选举有哪些规则

在议会选举中，比成员的身份、领导者的任期还要重要的就是选举的规则，比如一人一票、弹劾制度等。“无规矩不成方圆”，在Raft算法中，也约定了选举规则，主要有这样几点。

1. 领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制 RPC 消息），通知大家我是领导者，阻止跟随者发起新的选举。
2. 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举。
3. 在一次选举中，赢得大多数选票的候选人，将晋升为领导者。
4. 在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举。
5. 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3，先收到了 1 个包含任期编号为 4 的投票请求（来自节点 A），然后又收到了 1 个包含任期编号为 4 的投票请求（来自节点 B）。那么节点 C 将会把唯一一张选票投给节点 A，当再收到节点 B 的投票请求 RPC 消息时，对于编号为 4 的任期，已没有选票可投了。

6. 当任期编号相同时，日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的候选人。比如节点 B、C 的任期编号都是 3，节点 B 的最后一条日志项对应的任期编号为 3，而节点 C 为 2，那么当节点 C 请求节点 B 投票给自己时，节点 B 将拒绝投票。

我想强调的是，选举是跟随者发起的，推举自己为候选人；大多数选票是指集群成员半数以上的选票；大多数选票规则的目标，是为了保证在一个给定的任期内最多只有一个领导者。

其实在选举中，除了选举规则外，我们还需要避免一些会导致选举失败的情况，比如同一任期内，多个候选人同时发起选举，导致选票被瓜分，选举失败。那么在 Raft 算法中，如何避免这个问题呢？答案就是随机超时时间。

如何理解随机超时时间

在议会选举中，常出现未达到指定票数，选举无效，需要重新选举的情况。在 Raft 算法的选举中，也存在类似的问题，那它是如何处理选举无效的问题呢？

其实，Raft 算法巧妙地使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况。

我想强调的是，在 Raft 算法中，随机超时时间是有 2 种含义的，这里是很多同学容易理解出错的地方，需要你注意一下：

1. 跟随者等待领导者心跳信息超时的时间间隔，是随机的；
2. 当没有候选人赢得过半票数，选举无效了，这时需要等待一个随机时间间隔，也就是说，等待选举超时的时间间隔，是随机的。

内容小结

本节课我主要带你了解了 Raft 算法的
特点、领导者选举等。我希望你明确这样几个重点。

1. Raft 算法和兰伯特的 Multi-Paxos 不同之处，主要有 2 点。首先，在 Raft 中，不是所有节点都能当选领导者，只有日志最完整的节点，才能当选领导者；其次，在 Raft 中，日志必须是连续的。
2. Raft 算法通过任期、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则等，保证了一个任期只有一位领导，也极大地减少了选举失败的情况。
3. 本质上，Raft 算法以领导者为中心，选举出的领导者，以“一切以我为准”的方式，达成值的共识，和实现各节点日志的一致。

在本讲，我们使用 Raft 算法在集群中选出了领导者节点 A，那么选完领导者之后，领导者需要处理来自客户的写请求，并通过日志复制实现各节点日志的一致（下节课我会重点带你了解这一部分内容）。

课堂思考

Raft 算法实现了“一切以我为准”的强领导者模型，那么你不妨思考，这个设计有什么限制和局限呢？

08丨Raf算法（二）：如何复制日志?

在Raft算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和提交日志项的过程。

那Raft是如何复制日志的呢？又如何实现日志的一致的呢？这些内容是Raft中非常核心的内容，也就是今天讲解的重点。

如何理解日志？

刚刚我提到，副本数据是以日志的形式存在的，日志是由日志项组成，日志项究竟是什么样子呢？

其实，日志项是一种数据格式，它主要包含用户指定的数据，也就是指令（Command），还包含一些附加信息，比如索引值（Log index）、任期编号（Term）。那你该怎么理解这些信息呢？

1. 指令：一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端指定的数据。
2. 索引值：日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码。
3. 任期编号：创建这条日志项的领导者的任期编号。

从图中你可以看到，一届领导者任期，往往有多条日志项。而且日志项的索引值是连续的，这一点你需要注意。

讲到这儿你可能会问：不是说Raft实现了各节点间日志的一致吗？那为什么图中4个跟随者的日志都不一样呢？日志是怎么复制的呢？又该如何实现日志的一致呢？

如何复制日志？

你可以把Raft的日志复制理解成一个优化后的二阶段提交（将二阶段优化成了一阶段），减少了一半的往返消息，也就是降低了一半的消息延迟。那日志复制的具体过程是什么呢？

首先，领导者进入第一阶段，通过日志复制（Append Entries） RPC消息，将日志项复制到集群其他阶段上。

接着，如果领导者接收到大多数的“复制成功”响应后，它将日志项提交到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的“复制成功”响应，那么就返回错误给客户端。

学到这里，有同学可能有这样的疑问了，领导者将日志项提交到它的状态机，怎么没通知跟随者提交日志项呢？

这是Raft中的一个优化，领导者不直接发送消息通知其他节点提交指定日志项。因为领导者的日志复制RPC消息或心跳消息，包含了当前最大的，将会被提交的日志项索引值。所以通过日志复制RPC消息或心跳消息，跟随者就可以直到领导者的日志提交位置信息。

因此，当其他节点接受领导者的心跳消息，或者新的日志复制RPC消息后，就会将这条日志项提交到它的状态机。而这个优化，降低了处理客户端请求的延迟，将二阶段提交优化为了一段提交，降低了一半的消息延迟。

为了帮你理解，我画了一张过程图，然后再带你走一遍这个过程，这样你可以更加全面地掌握日志复制。

1. 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
2. 领导者通过日志复制RPC，将新的日志项复制到其他的服务器。
3. 当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项提交到它的状态机中。
4. 领导者将执行的结果返回给客户端。
5. 当跟随者接收到心跳信息，或者新的日志复制RPC消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没提交，那么跟随者就将这条日志项提交到本地的状态机中。

不过，这是一个理想状态下的日志复制过程。在实际环境中，复制日志的时候，你可能会遇到进程崩溃、服务器宕机等问题，这些问题会导致日志不一致。那么在这种情况下，Raft 算法是如何处理不一致日志，实现日志的一致的呢？

如何实现日志的一致？

在 Raft 算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft 是通过以领导者的日志为准，来实现各节点日志的一致的。具体有 2 个步骤。

1. 首先，领导者通过日志复制RPC的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。
2. 然后，领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致。

我带你详细地走一遍这个过程（为了方便演示，我们引入 2 个新变量）。

1. PrevLogEntry：表示当前要复制的日志项，前面一条日志项的索引值。比如在图中，如果领导者将索引值为8的日志项发送给跟随者，那么此时PrevLogEntey的值为7。
2. PrevLogTerm：表示当前要复制的日志项，前面一条日志项的任期编号，比如在图中，如果领导者将索引值为 8 的日志项发送给跟随者，那么此时 PrevLogTerm 值为 4。

1. 领导者通过日志复制 RPC信息，发送当前最新日志项到跟随者（为了演示方便，假设当前需要复制的日志项是最新的），这个消息的 PrevLogEntry 值为 7，PrevLogTerm 值为 4。
2. 如果跟随者在它的日志中，找不到与PrevLogEntry值为7、PrevLogTerm值为4的日志项，也就是说它的日志和领导者的不一致了，那么跟随者就会拒绝接收新的日志项，并返回失败信息给领导者。
3. 这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，这个消息的 PrevLogEntry 值为 6，PrevLogTerm 值为3。
4. 如果跟随者在它的日志中，找到了 PrevLogEntry 值为 6、
   PrevLogTerm 值为 3 的日志项，那么日志复制 RPC 返回成功，这样一来，领导者就知道在 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的位置，跟随者的日志项与自己相同。
5. 领导者通过日志复制 RPC，复制并更新覆盖该索引值之后的日志项（也就是不一致的日志项），最终实现了集群各节点日志的一致。

从上面步骤中你可以看到，领导者通过日志复制 RPC 一致性检查，找到跟随者节点上与自己相同日志项的最大索引值，然后复制并更新覆盖该索引值之后的日志项，实现了各节点日志的一致。需要你注意的是，跟随者中的不一致日志项会被领导者的日志覆盖，而且领导者从来不会覆盖或者删除自己的日志。

内容小结

本节课我主要带你了解了在 Raft 中什么是日志、如何复制日志、以及如何处理不一致日志等内容。我希望你明确这样几个重点。

1. 在 Raft 中，副本数据是以日志的形式存在的，其中日志项中的指令表示用户指定的数据。
2. 兰伯特的 Multi-Paxos 不要求日志是连续的，但在 Raft 中日志必须是连续的。而且在 Raft 中，日志不仅是数据的载体，日志的完整性还影响领导者选举的结果。也就是说，日志完整性最高的节点才能当选领导者。
3. Raft 是通过以领导者的日志为准，来实现日志的一致的。

课堂思考

领导者接收到大多数的“复制成功”响应后，就会将日志提交到它自己的状态机，然后返回“成功”响应客户端。如果此时有个节点不在“大多数”中，也就是说它接收日志项失败，那么在这种情况下，Raft 会如何处理实现日志的一致呢？

09」Raf算法（三）：如何解决成员变更的问题?

在日常工作中，你可能会遇到服务器故障的情况，这时你就需要替换集群中的服务器。如果遇到需要改变数据副本数的情况，则需要增加或移除集群中的服务器。总的来说，在日常工作中，集群中的服务器数量是会发生变化的。

在开始今天内容之前，我先介绍一下“配置”这个词儿。因为常听到有同学说，自己不理解配置（Configuration）的含义，从而不知道如何理解论文中的成员变更。

的确，配置是成员变更中一个非常重要的概念，我建议你这么理解：
它就是在说集群是哪些节点组成的，是集群各节点地址信息的集合。比如节点 A、B、C 组成的集群，那么集群的配置就是[A, B, C]集合。

理解了这一点之后，咱们先来看一道思考题。

假设我们有一个由节点 A、B、C 组成的 Raft 集群，现在我们需要增加数据副本数，增加 2 个副本（也就是增加 2 台服务器），扩展为由节点 A、B、C、D、E， 5 个节点组成的新集群：

那么 Raft 算法是如何保障在集群配置变更时，集群能稳定运行，不出现 2 个领导者呢？带着这个问题，我们正式进入今天的学习。

成员变更的问题

在我看来，在集群中进行成员变更的最大风险是，可能会同时出现2个领导者。比如在进行成员变更时，节点A、B和C之间发生了分区错误，节点A、B组成旧配置中的“大多数”，也就是变更前的3节点集群中的“大多数”，那么这时的领导者（节点A）依旧是领导者。

另一方面，节点C和新节点D、E组成了新配置的“大多数”，也就是变更后的5节点中的“大多数”，它们可能会选举出新的领导者（比如节点C）。那么这时，就出现了同时存在2个领导者的情况。

如果出现了3个领导者，那么就违背“领导者的唯一性”的原则，进而影响到集群的稳定运行。你要如何解决这个问题呢？也许有的同学想到了一个解决方法。

因为我们在启动集群时，配置是固定的，不存在成员变更，在这种情况下，Raft 的领导者选举能保证只有一个领导者。也就是说，这时不会出现多个领导者的问题，那我可以先将集群关闭再启动新集群啊。也就是先把节点 A、B、C 组成的集群关闭，然后再启动节点 A、B、C、D、E 组成的新集群。

在我看来，这个方法不可行。 为什么呢？因为你每次变更都要重启集群，意味着在集群变更期间服务不可用，肯定不行啊，太影响用户体验了。想象一下，你正在玩王者荣耀，时不时弹出一个对话框通知你：系统升级，游戏暂停 3 分钟。这体验糟糕不糟糕？

既然这种方法影响用户体验，根本行不通，那到底怎样解决成员变更的问题呢？最常用的方法就是单节点变更。

如何通过单节点变更解决成员变更的问题？

单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要执行多次单节点变更。比如将 3 节点集群扩容为 5 节点集群，这时你需要执行 2 次单节点变更，先将 3 节点集群变更为 4 节点集群，然后再将 4 节点集群变更为 5 节点集群，就像下图的样子。

现在，让我们回到开篇的思考题，看看如何用单节点变更的方法，解决这个问题。为了演示方便，我们假设节点 A 是领导者：

目前的集群配置为[A, B, C]，我们先向集群中加入节点 D，这意味着新配置为[A, B, C, D]。成员变更，是通过这么两步实现的：

1. 第一步，领导者（节点A）向新节点（节点D）同步数据；
2. 第二步，领导者（节点A）将新配置[A, B, C, D]作为一个日志项，复制到新配置中所有节点（节点 A、B、C、D）上，然后将新配置的日志项提交到本地状态机，完成单节点变更。
   
   在变更完成后，现在的集群配置就是[A, B, C, D]，我们再向集群中加入节点 E，也就是说，新配置为[A, B, C, D, E]。成员变更的步骤和上面类似：
3. 第一步，领导者（节点 A）向新节点（节点 E）同步数据；
4. 第二步，领导者（节点 A）将新配置[A, B, C, D, E]作为一个日志项，复制到新配置中的所有节点（A、B、C、D、E）上，然后再将新配置的日志项提交到本地状态机，完成单节点变更。

这样一来，我们就通过一次变更一个节点的方式，完成了成员变更，保证了集群中始终只有一个领导者，而且集群也在稳定运行，持续提供服务。

我想说的是，在正常情况下，不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的。 也就是说，不会同时存在旧配置和新配置 2 个“大多数”：


从上图中你可以看到，不管集群是偶数节点，还是奇数节点，不管是增加节点，还是移除节点，新旧配置的“大多数”都会存在重叠（图中的橙色节点）。

需要你注意的是，在分区错误、节点故障等情况下，如果我们并发执行单节点变更，那么就可能出现一次单节点变更尚未完成，新的单节点变更又在执行，导致集群出现 2 个领导者的情况。

如果你遇到这种情况，可以在领导者启动时，创建一个 NO_OP 日志项（也就是空日志项），只有当领导者将 NO_OP 日志项提交后，再执行成员变更请求。这个解决办法，你记住就可以了，可以自己在课后试着研究下。具体的实现，可参考 Hashicorp Raft 的源码，也就是runLeader() 函数中：

noop := &logFuture{log: Log{Type: LogNoop,},
}
r.dispatchLogs([]*logFuture{noop})

当然，有的同学会好奇“联合共识”，在我看来，因为它难以实现，很少被 Raft 实现采用。比如，除了 Logcabin 外，未见到其他常用 Raft实现采用了它，所以这里我就不多说了。

内容小结

本节课我主要带你了解了成员变更的问题和单节点变更的方法，我希望你明确这样几个重点。

1. 成员变更的问题，主要在于进行成员变更时，可能存在新旧配置的2 个“大多数”，导致集群中同时出现两个领导者，破坏了 Raft 的领导者的唯一性原则，影响了集群的稳定运行。
2. 单节点变更是利用“一次变更一个节点，不会同时存在旧配置和新配置 2 个‘大多数’”的特性，实现成员变更。
3. 因为联合共识实现起来复杂，不好实现，所以绝大多数 Raft 算法的实现，采用的都是单节点变更的方法（比如 Etcd、Hashicorp Raft）。其中，Hashicorp Raft 单节点变更的实现，是由 Raft 算法的作者迭戈·安加罗（Diego Ongaro）设计的，很有参考价值。

除此之外，考虑到本节课是 Raft 算法的最后一讲，所以在这里，我想多说几句，帮助你更好地理解 Raft 算法。
有很多同学把 Raft 当成一致性算法，其实 Raft 不是一致性算法而是共识算法，是一个 Multi-Paxos 算法，实现的是如何就一系列值达成共识。并且，Raft 能容忍少数节点的故障。虽然 Raft 算法能实现强一致性，也就是线性一致性（Linearizability），但需要客户端协议的配合。在实际场景中，我们一般需要根据场景特点，在一致性强度和实现复杂度之间进行权衡。比如 Consul 实现了三种一致性模型。

1. default：客户端访问领导者节点执行读操作，领导者确认自己处于稳定状态时（在 leader leasing 时间内），返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端是可能读到旧数据的，比如此时发生了网络分区错误，新领导者已经更新过数据，但因为网络故障，旧领导者未更新数据也未退位，仍处于稳定状态。
2. consistent：客户端访问领导者节点执行读操作，领导者在和大多数节点确认自己仍是领导者之后返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端读到的都是最新数据。
3. stale：从任意节点读数据，不局限于领导者节点，客户端可能会读到旧数据。

一般而言，在实际工程中，Consul 的 consistent 就够用了，可以不用线性一致性，只要能保证写操作完成后，每次读都能读到最新值就可以了。比如为了实现冥等操作，我们使用一个编号 (ID) 来唯一标记一个操作，并使用一个状态字段（nil/done）来标记操作是否已经执行，
那么只要我们能保证设置了 ID 对应状态值为 done 后，能立即和一直读到最新状态值就可以了，也就通过防止操作的重复执行，实现了冥等性。

总的来说，Raft 算法能很好地处理绝大部分场景的一致性问题，我推荐你在设计分布式系统时，优先考虑 Raft 算法，当 Raft 算法不能满足现有场景需求时，再去调研其他共识算法。

比如我负责过多个 QQ 后台的海量服务分布式系统，其中配置中心、名字服务以及时序数据库的 META 节点，采用了 Raft 算法。在设计时序数据库的 DATA 节点一致性时，基于水平扩展、性能和数据完整性等考虑，就没采用 Raft 算法，而是采用了 Quorum NWR、失败重传、反熵等机制。这样安排不仅满足了业务的需求，还通过尽可能采用最终一致性方案的方式，实现系统的高性能，降低了成本。

一致性算法和共识算法是分布式系统中两个密切相关但有区别的概念。

一致性算法：关注如何在分布式系统中保持多个节点数据状态的一致，确保所有节点的数据副本最终达到相同的状态。
共识算法：关注如何使分布式系统中的多个节点就某个提案或状态达成一致，确保所有节点对同一状态的确认。

课程思考

强领导者模型会限制集群的写性能，那你想想看，有什么办法能突破 Raft 集群的写性能瓶颈呢？

10丨一致哈希算法：如何分群，突破集群的"领导者"限制?

如果我们通过 Raft 算法实现了 KV 存储，虽然领导者模型简化了算法实现和共识协商，但写请求只能限制在领导者节点上处理，导致了集群的接入性能约等于单机，那么随着业务发展，集群的性能可能就扛不住了，会造成系统过载和服务不可用，这时该怎么办呢？

其实这是一个非常常见的问题。在我看来，这时我们就要通过分集群，突破单集群的性能限制了。

说到这儿，有同学可能会说了，分集群还不简单吗？加个 Proxy 层，由 Proxy 层处理来自客户端的读写请求，接收到读写请求后，通过对Key 做哈希找到对应的集群就可以了啊。

是的，哈希算法的确是个办法，但它有个明显的缺点：当需要变更集群数时（比如从 2 个集群扩展为 3 个集群），这时大部分的数据都需要迁移，重新映射，数据的迁移成本是非常高的。那么如何解决哈希算法，数据迁移成本高的痛点呢？答案就是一致哈希（Consistent Hashing）。

在正式开始学习之前，我们先看一道思考题。
假设我们有一个由 A、B、C 三个节点组成（为了方便演示，我使用节点来替代集群）的 KV 服务，每个节点存放不同的 KV 数据：

那么，使用哈希算法实现哈希寻址时，到底有哪些问题呢？带着这个问题，让我们开始今天的内容吧。

使用哈希算法有什么问题？

使用哈希算法，当节点数量发生变更时，迁移成本是非常高昂的，这在实际生产环境中也是无法想象的。

如何使用一致哈希实现哈希寻址？

一致哈希算法也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 $2^{32}$ 进行取模运算。你可以想象下，一致哈希算法，将整个哈希值空间组织成一个虚拟的圆环，也就是哈希环：

从图中你可以看到，哈希环的空间是按顺时针方向组织的，圆环的正上方的点代表 0，0 点右侧的第一个点代表 1，以此类推，2、3、4、5、6……直到 $2^{32}-1$，也就是说 0 点左侧的第一个点代表 $2^{32}-1$。在一致哈希中，你可以通过执行哈希算法（为了演示方便，假设哈希算法函数为“c-hash()”），将节点映射到哈希环上，比如选择节点的主机名作为参数执行 c-hash()，那么每个节点就能确定其在哈希环上的位置了：

当需要对指定 key 的值进行读写的时候，你可以通过下面 2 步进行寻址：

1. 首先，将key作为参数执行c - hash()计算哈希值，并确定此key在环上的位置；
2. 然后，从这个位置沿着哈希环顺时针“行走”，遇到的第一个节点就是key对应的节点。

为了帮助你更好地理解如何通过一致哈希进行寻址，我举个例子。假设 key-01、key-02、key-03 三个 key，经过哈希算法 c-hash() 计算后，在哈希环上的位置就像下图的样子：

那么根据一致哈希算法，key-01 将寻址到节点 A，key-02 将寻址到节点 B，key-03 将寻址到节点 C。讲到这儿，你可能会问：“那一致哈希是如何避免哈希算法的问题呢？”

别着急，接下来我分别以增加节点和移除节点为例，具体说一说一致哈希是如何避免上面的问题的。假设，现在有一个节点故障了（比如节点 C）：

你可以看到，key-01和key-02不会受到影响，只有key-03的寻址被重定位到A。一般来说，在一致哈希算法中，如果某个节点宕机不可用了，那么受影响的数据仅仅是，会寻址到此节点和前一节点之间的数据。比如当节点 C 宕机了，受影响的数据是会寻址到节点 B 和节点C 之间的数据（例如 key-03），寻址到其他哈希环空间的数据（例如key-01），不会受到影响。

那如果此时集群不能满足业务的需求，需要扩容一个节点（也就是增加一个节点，比如 D）：

你可以看到，key-01、key-02 不受影响，只有 key-03 的寻址被重定位到新节点 D。一般而言，在一致哈希算法中，如果增加一个节点，受影响的数据仅仅是，会寻址到新节点和前一节点之间的数据，其它数据也不会受到影响。

让我们一起来看一个例子。使用一致哈希的话，对于 1000 万 key 的3 节点 KV 存储，如果我们增加 1 个节点，变为 4 节点集群，只需要迁移 24.3% 的数据。

你看，使用了一致哈希后，我们需要迁移的数据量仅为使用哈希算法时的三分之一，是不是大大提升效率了呢？

总的来说，使用了一致哈希算法后，扩容或缩容的时候，都只需要重定位环空间中的一小部分数据。也就是说，一致哈希算法具有较好的容错性和可扩展性。

需要你注意的是，在哈希寻址中常出现这样的问题：客户端访问请求集中在少数的节点上，出现了有些机器高负载，有些机器低负载的情况，那么在一致哈希中，有什么办法能让数据访问分布的比较均匀呢？答案就是虚拟节点。

在一致哈希中，如果节点太少，容易因为节点分布不均匀造成数据访问的冷热不均，也就是说大多数访问请求都会集中少量几个节点上：

你能从图中看到，虽然有 3 个节点，但访问请求主要集中的节点 A上。那如何通过虚拟节点解决冷热不均的问题呢？

其实，就是对每一个服务器节点计算多个哈希值，在每个计算结果位置上，都放置一个虚拟节点，并将虚拟节点映射到实际节点。比如，可以在主机名的后面增加编号，分别计算 “Node-A-01”“Node-A02”“Node-B-01”“Node-B-02”“Node-C-01”“Node-C-02”的哈希值，于是形成 6 个虚拟节点：

你可以从图中看到，增加了节点后，节点在哈希环上的分布就相对均匀了。这时，如果有访问请求寻址到“Node-A-01”这个虚拟节点，将被重定位到节点 A。你看，这样我们就解决了冷热不均的问题。最后我想说的是，可能有同学已经发现了，当节点数越多的时候，使用哈希算法时，需要迁移的数据就越多，使用一致哈希时，需要迁移的数据就越少。

当我们向 10 个节点集群中增加节点时，如果使用了哈希算法，需要迁移高达 90.91% 的数据，使用一致哈希的话，只需要迁移 6.48% 的数据。

我希望你能注意到这个规律，使用一致哈希实现哈希寻址时，可以通过增加节点数降低节点宕机对整个集群的影响，以及故障恢复时需要迁移的数据量。后续在需要时，你可以通过增加节点数来提升系统的容灾能力和故障恢复效率。

课堂思考

Raft 集群具有容错能力，能容忍少数的节点故障，那么在多个 Raft 集群组成的 KV 系统中，如何设计一致哈希，实现当某个集群的节点出现了故障时，整个系统还能稳定运行呢？

11丨Gossip协议：流言语，原来也可以实现一致性

有一部分同学的业务在可用性上比较敏感，比如监控主机和业务运行的告警系统。这个时候，相信你希望自己的系统能在极端情况下（比如集群中只有一个节点在运行）也能运行。回忆了二阶段提交协议和Raft 算法之后，你发现它们都需要全部节点或者大多数节点正常运行，才能稳定运行，那么它们就不适合了。而根据 Base 理论，你需要实现最终一致性，怎么样才能实现最终一致性呢？

在我看来，你可以通过 Gossip 协议实现这个目标。

Gossip 协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。对你来说，掌握这个协议不仅能很好地理解这种最常用的，实现最终一致性的算法，也能在后续工作中得心应手地实现数据的最终一致性。

Gossip的三板斧

Gossip的三板斧分别是：直接邮寄（Direct Mail）、反熵（Antientropy）和谣言传播（Rumor mongering）。

直接邮寄：就是直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。从图中你可以看到，节点A直接将更新数据发送给了节点B、D。

直接邮寄虽然实现起来比较容易，数据同步也很及时，但可能会因为缓存队列满了而丢数据。也就是说，只采用直接邮寄是无法实现最终一致性的，这一点我希望你能注意到。

那如何实现最终一致性呢？答案就是反熵。本质上，反熵是一种通过异步修复实现最终一致性的方法（关于异步修复，你可以回顾一下04讲）。常见的最终一致性系统（比如 Cassandra），都实现了反熵功能。

反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性：

从图中可以看到，节点 A 通过反熵的方式，修复了节点 D 中缺失的数据。那具体怎么实现的呢？

其实，在实现反熵的时候，主要有推、拉和推拉三种方式。我将以修复下图中，2 个数据副本的不一致为例，具体带你了解一下。

推方式，就是将自己的所有副本数据，推给对方，修复对方副本中的熵：

拉方式，就是拉取对方的所有副本数据，修复自己副本中的熵：

理解了推和拉之后，推拉这个方式就很好理解了，这个方式就是同时修复自己副本和对方副本中的熵：

因为反熵需要节点两两交换和比对自己所有的数据，执行反熵时通讯成本会很高，所以我不建议你在实际场景中频繁执行反熵，并且可以通过引入校验和（Checksum）等机制，降低需要对比的数据量和通讯消息等。

虽然反熵很实用，但是执行反熵时，相关的节点都是已知的，而且节点数量不能太多，如果是一个动态变化或节点数比较多的分布式环境（比如在 DevOps 环境中检测节点故障，并动态维护集群节点状态），这时反熵就不适用了。那么当你面临这个情况要怎样实现最终一致性呢？答案就是谣言传播。

谣言传播，广泛地散播谣言，它指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据：

从图中你可以看到，节点 A 向节点 B、D 发送新数据，节点 B 收到新数据后，变成活跃节点，然后节点 B 向节点 C、D 发送新数据。其实，谣言传播非常具有传染性，它适合动态变化的分布式系统。

如何使用Anti-entropy实现最终一致

在分布式存储系统中，实现数据副本最终一致性，最常用的方法就是反熵了。为了帮你彻底理解和掌握在实际环境中实现反熵的方法，我想以自研 InfluxDB 的反熵实现为例，具体带你了解一下。

在自研 InfluxDB 中，一份数据副本是由多个分片组成的，也就是实现了数据分片，三节点三副本的集群，就像下图的样子：

反熵的目标是确保每个 DATA 节点拥有元信息指定的分片，而且不同节点上，同一分片组中的分片都没有差异。比如说，节点 A 要拥有分片 Shard1 和 Shard2，而且，节点 A 的 Shard1 和 Shard2，与节点B、C 中的 Shard1 和 Shard2，是一样的。

那么，在 DATA 节点上，存在哪些数据缺失的情况呢？也就说，我们需要解决哪些问题呢？
我们将数据缺失，分为这样 2 种情况。

1. 缺失分片：也就是说，在某个节点上整个分片都丢失了。
2. 节点之间的分片不一致：也就是说，节点上分片都存在，但里面的数据不一样，有数据丢失的情况发生。

第一种情况修复起来不复杂，我们只需要将分片数据，通过 RPC通讯，从其他节点上拷贝过来就可以了：

第二种情况修复起来要复杂一些。我们需要设计一个闭环的流程，按照一个顺序修复，执行完流程后，也就是实现了一致性了。具体是怎么设计的呢？

它是按照一定顺序来修复节点的数据差异，先随机选择一个节点，然后循环修复，每个节点生成自己节点有、下一个节点没有的差异数据，发送给下一个节点，进行修复（为了方便演示，假设 Shard1、Shard2 在各节点上是不一致的）：

从图中可以看到，数据修复的起始节点为节点 A，数据修复是按照顺时针顺序，循环修复的。需要你注意的是，最后节点 A 又对节点 B 的数据执行了一次数据修复操作，因为只有这样，节点 C 有、节点 B 缺失的差异数据，才会同步到节点 B 上。

学到这里你可以看到，在实现反熵时，实现细节和最初算法的约定有些不同。比如，不是一个节点不断随机选择另一个节点，来修复副本上的熵，而是设计了一个闭环的流程，一次修复所有节点的副本数据不一致。

为什么这么设计呢？因为我们希望能在一个确定的时间范围内实现数据副本的最终一致性，而不是基于随机性的概率，在一个不确定的时间范围内实现数据副本的最终一致性。

这样做能减少数据不一致对监控视图影响的时长。而我希望你能注意到，技术是要活学活用的，要能根据场景特点权衡妥协，设计出最适合这个场景的系统功能。最后需要你注意的是，因为反熵需要做一致性对比，很消耗系统性能，所以建议你将是否启用反熵功能、执行一致性检测的时间间隔等，做成可配置的，能在不同场景中按需使用。

内容总结

本节课我主要带你了解了 Gossip 协议、如何在实际系统中实现反熵等。我希望你明确这样几个重点：

1. 作为一种异步修复、实现最终一致性的协议，反熵在存储组件中应用广泛，比如 Dynamo、InfluxDB、Cassandra，我希望你能彻底掌握反熵的实现方法，在后续工作中，需要实现最终一致性时，优先考虑反熵。
2. 因为谣言传播具有传染性，一个节点传给了另一个节点，另一个节点又将充当传播者，传染给其他节点，所以非常适合动态变化的分布式系统，比如 Cassandra 采用这种方式动态管理集群节点状态。

在实际场景中，实现数据副本的最终一致性时，一般而言，直接邮寄的方式是一定要实现的，因为不需要做一致性对比，只是通过发送更新数据或缓存重传，来修复数据的不一致，性能损耗低。在存储组件中，节点都是已知的，一般采用反熵修复数据副本的一致性。当集群节点是变化的，或者集群节点数比较多时，这时要采用谣言传播的方式，同步更新数据，实现最终一致。

课堂思考

既然使用反熵实现最终一致性时，需要通过一致性检测发现数据副本的差异，如果每次做一致性检测时都做数据对比的话，肯定是比较消耗性能的，那有什么办法降低一致性检测时的性能消耗呢？

12丨Quorum NWR算法：想要灵活地自定义一致性，没问题！

你开发实现了一套 AP 型的分布式系统，实现了最终一致性。业务也接入了，运行正常，一起看起来都那么美好。
可是，突然有同事说，我们要拉这几个业务的数据做实时分析，希望数据写入成功后，就能立即读取到新数据，也就是要实现强一致性（Werner Vogels 提出的客户端侧一致性模型，不是指线性一致性），数据更改后，要保证用户能立即查询到。这时你该怎么办呢？

首先你要明确最终一致性和强一致性有什么区别。

1. 强一致性能保证写操作完成后，任何后续访问都能读到更新后的值；
2. 最终一致性只能保证如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值。也就是说，写操作完成后，后续访问可能会读到旧数据。

其实，在我看来，为了一个临时的需求，我们重新开发一套系统，或者迁移数据到新系统，肯定是不合适的。因为工作量比较大，而且耗时也长，而我建议你通过 Quorum NWR 解决这个问题。
也就是说，在原有系统上开发实现一个新功能，就可以满足业务同学的需求了。因为通过 Quorum NWR，你可以自定义一致性级别，通过临时调整写入或者查询的方式，当 W + R > N 时，就可以实现强一致性了。

其实，在 AP 型分布式系统中（比如 Dynamo、Cassandra、InfluxDB 企业版的 DATA 节点集群），Quorum NWR 是通常都会实现的一个功能，很常用。对你来说，掌握 Quorum NWR，不仅是掌握一种常用的实现一致性的方法，更重要的是，后续用户可以根据业务的特点，灵活地指定一致性级别。

为了帮你掌握 Quorum NWR，除了带你了解它的原理外，我还会以InfluxDB 企业版的实现为例，带你看一下它在实际场景中的实现，这样你可以在理解原理的基础上，掌握 Quorum NWR 的实战技巧。
首先，你需要了解 Quorum NWR 中的三个要素，N、W、R。因为它们是 Quorum NWR 的核心内容，我们就是通过组合这三个要素，实现自定义一致性级别的。

Quorum NWR的三要素

N 表示副本数，又叫做复制因子（Replication Factor）。也就是说，N 表示集群中同一份数据有多少个副本，就像下图的样子：

从图中你可以看到，在这个三节点的集群中，DATA-1 有 2 个副本，DATA-2 有 3 个副本，DATA-3 有 1 个副本。也就是说，副本数可以不等于节点数，不同的数据可以有不同的副本数。

需要你注意的是，在实现 Quorum NWR 的时候，你需要实现自定义副本的功能。也就是说，用户可以自定义指定数据的副本数，比如，用户可以指定 DATA-1 具有 2 个副本，DATA-2 具有 3 个副本，就像图中的样子。

当我们指定了副本后，就可以对副本数据进行读写操作了。那么这么多副本，你要如何执行读写操作呢？先来看一看写操作，也就是 W。

W，又称写一致性级别（Write Consistency Level），表示成功完成 W 个副本更新，才完成写操作：

从图中你可以看到，DATA-2 的写副本数为 2，也就说，对 DATA-2 执行写操作时，完成了 2 个副本的更新（比如节点 A、C），才完成写操作。

那么有的同学会问了，DATA-2 有 3 个数据副本，完成了 2 副本的更新，就完成了写操作，那么如何实现强一致性呢？如果读到了第三个数据副本（比如节点 B），不就可能无法读到更新后的值了吗？别急，我讲完如何执行读操作后，你就明白了。

R，又称读一致性级别（Read Consistency Level），表示读取一个数据对象时需要读 R 个副本。你可以这么理解，读取指定数据时，要读 R 副本，然后返回 R 个副本中最新的那份数据：

从图中你可以看到，DATA-2 的读副本数为 2。也就是说，客户端读取DATA-2 的数据时，需要读取 2 个副本中的数据，然后返回最新的那份数据。

这里需要你注意的是，无论客户端如何执行读操作，哪怕它访问的是写操作未强制更新副本数据的节点（比如节点 B），但因为 W(2) + R(2) > N(3)，也就是说，访问节点 B，执行读操作时，因为要读 2 份数据副本，所以除了节点 B 上的 DATA-2，还会读取节点 A 或节点 C 上的 DATA-2，就像上图的样子（比如节点 C 上的 DATA-2），而节点 A 和节点 C 的 DATA-2 数据副本是强制更新成功的。这个时候，返回给客户端肯定是最新的那份数据。

你看，通过设置 R 为 2，即使读到前面问题中的第三份副本数据（比如节点 B），也能返回更新后的那份数据，实现强一致性了。

除此之外，关于 NWR 需要你注意的是，N、W、R 值的不同组合，会产生不同的一致性效果，具体来说，有这么两种效果：

1. 当 W + R > N 的时候，对于客户端来讲，整个系统能保证强一致性，一定能返回更新后的那份数据。
2. 当 W + R < N 的时候，对于客户端来讲，整个系统只能保证最终一致性，可能会返回旧数据。

你可以看到，Quorum NWR 的原理并不复杂，也相对比较容易理解，但在这里，我想强调一下，掌握它的关键在于如何根据不同的场景特点灵活地实现 Quorum NWR，所以接下来，我带你具体问题具体分析，以 InfluxDB 企业版为例讲解一下。

如何实现 Quorum NWR？

在 InfluxDB 企业版中，可以在创建保留策略时，设置指定数据库（Database）对应的副本数，具体的命令，就像下面的样子：

1. create retention policy “rp_one_day” on “telegraf” duration 1d replication 3

通过 replication 参数，指定了数据库 telegraf 对应的副本数为 3。

需要你注意的，在 InfluxDB 企业版中，副本数不能超过节点数据。你可以这么理解，多副本的意义在于冗余备份，如果副本数超过节点数，就意味着在一个节点上会存在多个副本，那么这时冗余备份的意义就不大了。比如机器故障时，节点上的多个副本是同时被影响的。

InfluxDB 企业版，支持“any、one、quorum、all”4 种写一致性级别，具体的含义是这样的。

1. any：任何一个节点写入成功后，或者接收节点已将数据写入Hinted-handoff 缓存（也就是写其他节点失败后，本地节点上缓存写失败数据的队列）后，就会返回成功给客户端。
2. one：任何一个节点写入成功后，立即返回成功给客户端，不包括成功写入到 Hinted-handoff 缓存。
3. quorum：当大多数节点写入成功后，就会返回成功给客户端。此选项仅在副本数大于 2 时才有意义，否则等效于 all。
4. all：仅在所有节点都写入成功后，返回成功。

对时序数据库而言，读操作常会拉取大量数据，查询性能是挑战，是必须要考虑优化的，因此，在 InfluxDB 企业版中，不支持读一致性级别，只支持写一致性级别。另外，我们可以通过设置写一致性级别为 all，来实现强一致性。

你看，如果我们像 InfluxDB 企业版这样，实现了 Quorum NWR，那么在业务临时需要实现强一致性时，就可以通过设置写一致性级别为 all，来实现了。

内容小结

明确这样几个重点。

1. 一般而言，不推荐副本数超过当前的节点数，因为当副本数据超过节点数时，就会出现同一个节点存在多个副本的情况。当这个节点故障时，上面的多个副本就都受到影响了。
2. 当 W + R > N 时，可以实现强一致性。另外，如何设置 N、W、R 值，取决于我们想优化哪方面的性能。比如，N 决定了副本的冗余备份能力；如果设置 W = N，读性能比较好；如果设置 R = N，写性能比较好；如果设置 W = (N + 1) / 2、R = (N + 1) / 2，容错能力比较好，能容忍少数节点（也就是 (N - 1) / 2）的故障。

最后，我想说的是，Quorum NWR 是非常实用的一个算法，能有效弥补 AP 型系统缺乏强一致性的痛点，给业务提供了按需选择一致性级别的灵活度，建议你的开发实现 AP 型系统时，也实现 Quorum NWR。

课堂思考

提到实现 Quorum NWR 时，需要实现自定义副本的能力，那么，一般设置几个副本就可以了，为什么呢？

13丨PBFT算法：有人作恶，如何达成共识?

口信消息型拜占庭问题之解在实际项目中是如何落地的呢？

不过事实上，它很难在实际项目落地，因为口信消息型拜占庭问题之解是一个非常理论化的算法，没有和实际场景结合，也没有考虑如何在实际场景中落地和实现。

比如，它实现的是在拜占庭错误场景下，忠将们如何在叛徒干扰时，就一致行动达成共识。但是它并不关心结果是什么，这会出现一种情况：现在适合进攻，但将军们达成的最终共识却是撤退。

很显然，这不是我们想要的结果。因为在实际场景中，我们需要就提议的一系列值（而不是单值），即使在拜占庭错误发生的时候也能被达成共识。那你要怎么做呢？答案就是掌握 PBFT 算法。

PBFT 算法非常实用，是一种能在实际场景中落地的拜占庭容错算法，它在区块链中应用广泛（比如 Hyperledger Sawtooth、Zilliqa）。为了帮助你更好地理解 PBFT 算法，在今天的内容中，我除了带你了解 PBFT 达成共识的原理之外，还会介绍口信消息型拜占庭问题之解的局限。相信学习完本讲内容后，你不仅能理解 PBFT 达成共识的基本原理，还能理解算法背后的演化和改进。

在开始今天的学习之前，咱们先看一道思考题：假设苏秦再一次带队抗秦，这一天，苏秦和 4 个国家的 4 位将军赵、
魏、韩、楚商量军机要事，结果刚商量完没多久苏秦就接到了情报，情报上写道：联军中可能存在一个叛徒。这时，苏秦要如何下发作战指令，保证忠将们正确、一致地执行下发的作战指令，而不是被叛徒干扰呢？

带着这个问题，我们正式进入今天的学习。

首先，咱们先来研究一下，为什么口信消息型拜占庭问题之解很难在实际场景中落地，除了我在开篇提到的非常理论化，没有和实际的需求结合之外，还有其他的原因么？

其实，这些问题是后续众多拜占庭容错算法在努力改进和解决的，理解了这些问题，能帮助你更好地理解后来的拜占庭容错算法（包括 PBFT 算法）。

口信消息型拜占庭问题之解的局限

我想说的是，这个算法有个非常致命的缺陷。如果将军数为 n、叛将数为 f，那么算法需要递归协商 f+1 轮，消息复杂度为 O(n ^ (f + 1))，消息数量指数级暴增。你可以想象一下，如果叛将数为 64，消息数已经远远超过 int64 所能表示的了，这是无法想象的，肯定不行啊。

另外，尽管对于签名消息，不管叛将数（比如 f）是多少，经过 f + 1 轮的协商，忠将们都能达成一致的作战指令，但是这个算法同样存在“理论化”和“消息数指数级暴增”的痛点。

讲到这儿，你肯定明白为什么这个算法很难在实际场景中落地了。可技术是不断发展的，算法也是在解决实际场景问题中不断改进的。那么 PBFT 算法的原理是什么呢？为什么它能在实际场景中落地呢？

PBFT 是如何达成共识的？

我们先来看看如何通过 PBFT 算法，解决苏秦面临的共识问题。先假设苏秦制定的作战指令是进攻，而楚是叛徒（为了演示方便）：

需要你注意的是，所有的消息都是签名消息，也就是说，消息发送者的身份和消息内容都是无法伪造和篡改的（比如，楚无法伪造一个假装来自赵的消息）。
首先，苏秦联系赵，向赵发送包含作战指令“进攻”的请求（就像下图的样子）。

当赵接收到苏秦的请求之后，会执行三阶段协议（Three-phase protocol）。

1. 赵将进入预准备（Pre-prepare）阶段，构造包含作战指令的预准备消息，并广播给其他将军（魏、韩、楚）。
   
   那么在这里，我想问你一个问题：魏、韩、楚，收到消息后，能直接执行指令吗？

答案是不能，因为他们不能确认自己接收到指令和其他人接收到的指令是相同的。比如，赵可能是叛徒，赵收到了 2 个指令，分别是“进攻”和“准备 30 天的粮草”，然后他给魏发送的是“进攻”，给韩、楚发送的是“准备 30 天粮草”，这样就会出现无法一致行动的情况。那么他们具体怎么办呢？我接着说一下。
2. 接收到预准备消息之后，魏、韩、楚将进入准备（Prepare）阶段，并分别广播包含作战指令的准备消息给其他将军。比如，魏广播准备消息给赵、韩、楚（如图所示）。为了方便演示，我们假设叛徒楚想通过不发送消息，来干扰共识协商（你能看到，图中的楚是没有发送消息的）。

然后，当某个将军收到 2f 个一致的包含作战指令的准备消息后，会进入提交（Commit）阶段（这里的 2f 包括自己，其中 f 为叛徒数，在我的演示中是 1）。在这里，我也给你提一个问题：这个时候该将军（比如魏）可以直接执行指令吗？

答案还是不能，因为魏不能确认赵、韩、楚是否收到了 2f 个一致的包含作战指令的准备消息。也就是说，魏这时无法确认赵、韩、楚是否准备好了执行作战指令。那么怎么办呢？别着急，咱们继续往下看。

1. 进入提交阶段后，各将军分别广播提交消息给其他将军，也就是告诉其他将军，我已经准备好了，可以执行指令了。

2. 最后，当某个将军收到 2f + 1 个验证通过的提交消息后（包括自己，其中 f 为叛徒数，在我的演示中为 1），也就是说，大部分的将军们已经达成共识，这时可以执行作战指令了，那么该将军将执行苏秦的作战指令，执行完毕后发送执行成功的消息给苏秦。

最后，当苏秦收到 f+1 个相同的响应（Reply）消息时，说明各位将军们已经就作战指令达成了共识，并执行了作战指令（其中 f 为叛徒数，在我的演示中为 1）。你看，经过了三轮协商，是不是就指定的作战指令达成了共识，并执行了作战指令了呢？

在这里，苏秦采用的就是简化版的 PBFT 算法。在这个算法中：

1. 你可以将赵、魏、韩、楚理解为分布式系统的四个节点，其中赵是主节点（Primary node），魏、韩、楚是从节点（Secondary node）；
2. 将苏秦理解为业务，也就是客户端；
3. 将消息理解为网络消息；
4. 将作战指令“进攻”，理解成客户端提议的值，也就是希望被各节点达成共识，并提交给状态机的值。

在这里我想说的是， PBFT 算法是通过签名（或消息认证码 MAC）约束恶意节点的行为，也就是说，每个节点都可以通过验证消息签名确认消息的发送来源，一个节点无法伪造另外一个节点的消息。最终，基于大多数原则（2f + 1）实现共识的。

需要你注意的是，最终的共识是否达成，客户端是会做判断的，如果客户端在指定时间内未收到请求对应的 f + 1 相同响应，就认为集群出故障了，共识未达成，客户端会重新发送请求。

另外需要你注意的是，PBFT 算法通过视图变更（View Change）的方式，来处理主节点作恶，当发现主节点在作恶时，会以“轮流上岗”方式，推举新的主节点。

最后我想说的是，尽管 PBFT 算法相比口信消息型拜占庭之解已经有了很大的优化，将消息复杂度从 O(n ^ (f + 1)) 降低为 O(n ^ 2)，能在实际场景中落地，并解决实际的共识问题。但 PBFT 还是需要比较多的消息。比如在 13 节点集群中（f 为 4）。

1. 请求消息：1
2. 预准备消息：3f = 12
3. 准备消息：3f * (3f - f) = 96
4. 提交消息：(3f - f + 1) * (3f + 1)= 117
5. 回复消息：3f - 1 = 11

也就是说，一次共识协商需要 237 个消息，你看，消息数还是蛮多的，所以我推荐你，在中小型分布式系统中使用 PBFT 算法。

内容小结

以上就是本节课的全部内容了，本节课我主要带你了解了口信消息型
拜占庭问题之解的局限和 PBFT 的原理，我希望你明确这样几个重
点。

1. 不管口信消息型拜占庭问题之解，还是签名消息型拜占庭问题之解，都是非常理论化的，未考虑实际场景的需求，而且协商成本非常高，指数级的消息复杂度是很难在实际场景中落地，和解决实际场景问题的。
2. PBFT 算法是通过签名（或消息认证码 MAC）约束恶意节点的行为，采用三阶段协议，基于大多数原则达成共识的。另外，与口信消息型拜占庭问题之解（以及签名消息型拜占庭问题之解）不同的是，PBFT 算法实现的是一系列值的共识，而不是单值的共识。

最后，我想说的是，相比 Raft 算法完全不适应有人作恶的场景，PBFT 算法能容忍 (n - 1)/3 个恶意节点 (也可以是故障节点)。另外，相比 PoW 算法，PBFT 的优点是不消耗算力，所以在日常实践中，PBFT 比较适用于相对“可信”的场景中，比如联盟链。

需要你注意的是，PBFT 算法与 Raft 算法类似，也存在一个“领导者”（就是主节点），同样，集群的性能也受限于“领导者”。另外，O(n ^ 2) 的消息复杂度，以及随着消息数的增加，网络时延对系统运行的影响也会越大，这些都限制了运行 PBFT 算法的分布式系统的规模，也决定了 PBFT 算法适用于中小型分布式系统。

课堂思考

当客户端在收到了 f + 1 个结果，就认为共识达成了，那么为什么这个值不能小于 f + 1 呢？

14丨PoW算法：有办法黑比特币吗?

谈起比特币，你应该再熟悉不过了，比特币是基于区块链实现的，而区块链运行在因特网上，这就存在有人试图作恶的情况。口信消息型拜占庭问题之解、PBFT 算法虽然能防止坏人作恶，但只能防止少数的坏人作恶，也就是 (n - 1) / 3 个坏人 (其中 n 为节点数)。可如果区块链也只能防止一定比例的坏人作恶，那就麻烦了，因为坏人可以不断增加节点数，轻松突破 (n - 1) / 3 的限制。

那区块链是如何改进这个问题的呢？答案就是 PoW 算法。

在我看来，区块链通过工作量证明（Proof of Work）增加了坏人作恶的成本，以此防止坏人作恶。比如，如果坏人要发起 51% 攻击，需要控制现网 51% 的算力，成本是非常高昂的。为啥呢？因为根据Cryptoslate 估算，对比特币进行 51% 算力攻击需要上百亿人民币！

那么为了帮你更好地理解和掌握 PoW 算法，我会详细讲解它的原理和 51% 攻击的本质。希望让你在理解 PoW 算法的同时，也了解 PoW 算法的局限。

首先我来说说 PoW 的原理，换句话说，就是 PoW 是如何运行的。

如何理解工作量证明？

什么是工作量证明 (Proof Of Work，简称 PoW) 呢？你可以这么理解：就是一份证明，用来确认你做过一定量的工作。比如，你的大学毕业证书就是一份工作量证明，证明你通过 4 年的努力完成了相关课程的学习。

那么回到计算机世界，具体来说就是，客户端需要做一定难度的工作才能得出一个结果，验证方却很容易通过结果来检查出客户端是不是做了相应的工作。

比如小李来 BAT 面试，说自己的编程能力很强，那么他需要做一定难度的工作（比如做个编程题）。根据做题结果，面试官可以判断他是否适合这个岗位。你看，小李做个编程题，面试官核验做题结果，这就是一个现实版的工作量证明。

具体的工作量证明过程，就像下图中的样子：

请求方做了一些运算，解决了某个问题，然后把运算结果发送给验证方，进行核验，验证方根据运算结果，就能判断请求方是否做了相关的工作。

需要你注意的是，这个算法具有不对称性，也就是说，工作对于请求方是有难度的，对于验证方则是比较简单的，易于验证的。

既然工作量证明是通过指定的结果，来证明自己做过了一定量的工作。那么在区块链的 PoW 算法中需要做哪些工作呢？答案是哈希运算。区块链是通过执行哈希运算，然后通过运算后的结果值，证明自己做过了相关工作。为了帮你更好地理解哈希运算，在介绍哈希运算之前，咱们先来聊一聊哈希函数。

哈希函数（Hash Function），也叫散列函数。就是说，你输入一个任意长度的字符串，哈希函数会计算出一个长度相同的哈希值。假设我们对任意长度字符串（比如"geektime"）执行 SHA256 哈希运算，就会得到一个 32 字节的哈希值。

那我们如何通过哈希函数进行哈希运算，从而证明工作量呢？为了帮你理解这部分内容，我举个具体的例子。

我们给出的工作量要求是，基于一个基本的字符串（比
如"geektime"），你可以在这个字符串后面添加一个整数值，然后对变更后（添加整数值) 的字符串进行 SHA256 哈希运算，如果运算后得到的哈希值（16 进制形式）是以"0000"开头的，就验证通过。为了达到这个工作量证明的目标，我们需要不停地递增整数值，一个一个试，对得到的新字符串进行 SHA256 哈希运算。

按照这个规则，我们需要经过 35024 次计算，才能找到恰好前 4 位为 0 的哈希值。

"geektime0" => 01f28c5df06ef0a575fd0e529be9a6f73b1
"geektime1" => a2567c06fdb5775cb1e3ce17b72754cf146
...
"geektime35022" =>
8afc85049a9e92fe0b6c98b02b27c09fb869fbfe273d0ab84a
"geektime35023" =>
0000ec5927ba10ea45a6822dcc205050ae74ae1ad2d9d41e97

通过这个示例你可以看到，工作量证明是通过执行哈希运算，经过一段时间的计算后，得到符合条件的哈希值。也就是说，可以通过这个哈希值，来证明我们的工作量。

关于这个规则，我也想多说几句，这个规则不是固定的，在实际场景中，你可以根据场景特点，制定不同的规则，比如，你可以试试分别运行多少次，才能找到恰好前 3 位和前 5 位为 0 的哈希值。

现在，你对工作量证明的原理应该有一定的了解了，那么有同学肯定好奇了，在区块链中是如何实现工作量证明的呢？

区块链如何实现 PoW 算法的？

区块链也是通过 SHA256 来执行哈希运算的，通过计算出符合指定条件的哈希值，来证明工作量的。因为在区块链中，PoW 算法是基于区块链中的区块信息，进行哈希运算的，所以我先带你回顾一下区块链的相关知识。

区块链的区块，是由区块头、区块体 2 部分组成的，就像下图中的样子。

1. 区块头（Block Head）：区块头主要由上一个区块的哈希值、区块体的哈希值、4 字节的随机数（nonce）等组成的。
2. 区块体（Block Body）：区块包含的交易数据，其中的第一笔交易是 Coinbase 交易，这是一笔激励矿工的特殊交易。

我想说的是，拥有 80 字节固定长度的区块头，就是用于区块链工作量证明的哈希运算中输入字符串，而且通过双重 SHA256 哈希运算（也就是对 SHA256 哈希运算的结果，再执行一次哈希运算），计算出的哈希值，只有小于目标值（target），才是有效的，否则哈希值是无效的，必须重算。

学到这儿你可以看到，在区块链中是通过对区块头执行 SHA256 哈希运算，得到小于目标值的哈希值，来证明自己的工作量的。

计算出符合条件的哈希值后，矿工就会把这个信息广播给集群中所有其他节点，其他节点验证通过后，会将这个区块加入到自己的区块链中，最终形成一串区块链，就像下图的样子：

最后，我想说的是，算力越强，系统大概率会越先计算出这个哈希值。这也就意味着，如果坏人们掌握了 51% 的算力，就可以发起 51% 攻击，比如，实现双花（Double Spending），也就是说，同一份钱花 2 次。

具体说的话，就是攻击者掌握了较多的算力，能挖掘一条比原链更长的攻击链，并将攻击链向全网广播，这时呢，按照约定，节点将接受更长的链，也就是攻击链，丢弃原链。就像下图的样子：

需要你注意的是，即使攻击者只有 30% 的算力，他也有可能连续计算出多个区块的哈希值，挖掘出更长的攻击链，发动攻击； 另外，即使攻击者拥有 51% 的算力，他也有可能半天无法计算出一个区块的哈希值，也就是攻击失败。也就是说，能否计算出符合条件的哈希值，有一定的概率性，但长久来看，攻击者攻击成功的概率等同于攻击者算力的权重。

内容小结

以上就是本节课的全部内容了，本节课我主要带你了解了 PoW 算法的原理，和 51% 攻击，我希望你明确这样几个重点。

1. 在比特币的区块链中，PoW 算法，是通过 SHA256 进行哈希运算，计算出符合指定条件的哈希值，来证明工作量的。
2. 51% 攻击，本质是因为比特币的区块链约定了“最长链胜出，其它节点在这条链基础上扩展”，攻击者可以通过优势算力实现对最长链的争夺。
3. 除了通过 PoW 算法，增加坏人作恶的成本，比特币还通过“挖矿得币”奖励好人，最终保持了整个系统的运行稳定。

因为本讲是拜占庭容错算法的最后一讲，我想多说几句：学完了 01 讲的同学，应该还记得，我们提到 Raft 算法是非拜占庭容错算法。那么如果我们把 Raft 算法用于拜占庭场景中，会怎么样呢？

比如，在比特币中，我们采用了 Raft 算法实现共识，而不是基于 PoW 算法的区块链，那么，就会出现这样的情况，当恶意节点当选为领导者后，他可以不断地告诉其他节点，这些比特币都是我的，按照 Raft 的约定，其他节点也就只能接受这种情况，谁让恶意节点是领导者呢？最终就会出现，所有的比特币都被恶意节点盗走的情况，完全乱套了。

另外我想说的是，因为拜占庭容错算法（比如 PoW 算法、PBFT 算法），能容忍一定比例的作恶行为，所以它在相对开放的场景中应用广泛，比如公链、联盟链。非拜占庭容错算法（比如 Raft）无法对作恶行为进行容错，主要用于封闭、绝对可信的场景中，比如私链、公司内网的 DevOps 环境。我希望你能准确理解 2 类算法之间的差异，根据场景特点，选择合适的算法，保障业务高效、稳定的运行。

课堂思考

既然，我提了如何通过计算得到"0000"开头的哈希值，来做实现工作量证明，那么你不妨思考下，如果约定是更多“0”开头的哈希值，比如“00000000”，工作量是增加了还是减少了，为什么呢？

15丨ZAB协议：如何实现操作的顺序性?

很多同学应该使用过 ZooKeeper，它是一个开源的分布式协调服务，比如你可以使用它进行配置管理、名字服务等等。在 ZooKeeper 中，数据是以节点的形式存储的。如果你要用 ZooKeeper 做配置管理，那么就需要在里面创建指定配置，假设创建节点"/geekbang"和"/geekbang/time"，步骤如下：

[zk: localhost:2181(CONNECTED) 7] create /geekbang
Created /geekbang
[zk: localhost:2181(CONNECTED) 8] create /geekbang
Created /geekbang/time

我们分别创建了配置"/geekbang" 和"/geekbang/time"，对应的值分别为 123 和 456。那么在这里我提个问题：你觉得在 ZooKeeper 中，能用兰伯特的 Multi-Paxos 实现各节点数据的共识和一致吗？

当然不行。因为兰伯特的 Multi-Paxos，虽然能保证达成共识后的值不再改变，但它不管关心达成共识的值是什么，也无法保证各值（也就是操作）的顺序性。这是为什么呢？这个问题是 ZAB 协议着力解决的，也是理解 ZAB 协议的关键。

不过，虽然大家都在提 ZAB 协议，但是在我看来，ZAB 协议和ZooKeeper 代码耦合在一起，也就是说，你是无法单独使用 ZAB 协议的，所以一般而言，只需要理解 ZAB 协议的架构和基础原理就可以了，不需要对代码和细节做太多的深究。所以，我会从 ZAB 协议的最核心设计目标（如何实现操作的顺序性）出发，带你了解它的基础原理。

为什么 Multi-Paxos 无法实现操作顺序性？

兰伯特的 Multi-Paxos 解决的是一系列值如何达成共识的问题，它关心的是，对于指定序号的位置，最多只有一个指令（Command）会被选定，但它不关心选定的是哪个指令，也就是说，它不关心指令的顺序性（也就是操作的顺序性）。

这么说可能比较抽象，为了方便你理解，我举个具体的例子演示一下（一个 3 节点的 Multi-Paxos 集群），为了演示方便，我们假设当前所有节点被选定的指令的最大序号为 100，也就是说，新提议的指令对应的序号将为 101。

首先节点 A 是领导者，提议了指令 X、Y，但是因为网络故障，指令只成功复制到了节点 A。

假设这时节点 A 故障了，新当选的领导者为节点 B。节点 B 当选领导者后，需要先作为学习者了解目前已被选定的指令。节点 B 学习之后，发现当前被选定指令的最大序号为 100（因为节点 A 故障了，它被选定指令的最大序号 102，无法被节点 B 发现），那么它可以从序号 101 开始提议新的指令。这时它接收到客户端请求，并提议了指令 Z，指令 Z 被成功复制到节点 B、C。

这时节点 B 故障了，节点 A 恢复了，选举出领导者 C 后，节点 B 故障也恢复了。节点 C 当选领导者后，需要先作为学习者，了解目前已被选定的指令，这时它执行 Basic Paxos 的准备阶段，就会发现之前选定的值（比如 Z、Y），然后发送接受请求，最终在序号 101、102处达成共识的指令是 Z、Y。就像下图的样子。

在这里，你可以看到，原本预期的指令是 X、Y，最后变成了 Z、Y，也就是说，虽然 Multi-Paxos 能就一系列值达成共识，但它不关心达成共识后的值是什么，这显然不是我们想要的结果。

比如，假设在 ZooKeeper 中直接使用了兰伯特的 Multi-Paxos，这时咱们创建节点"/geekbang"和"/geekbang/time"，那么就可能出现，系统先创建了节点"/geekbang/time"，这样肯定就出错了：

[zk: localhost:2181(CONNECTED) 6] create /geekbang
Node does not exist: /geekbang/time

因为创建节点"/geekbang/time"时，找不到节点"/geekbang"，所以就会创建失败。

在这里我多说几句，兰伯特有很多关于分布式的理论，这些理论都很经典（比如拜占庭将军问题、Paxos），但也因为太早了，与实际场景结合的不多，所以后续的众多算法是在这个基础之上做了大量的改进（比如，PBFT、Raft 等）。

另外我还想补充一下，在我看来，在ZAB 论文中，关于 Paxos 问题的分析是有争议的。因为 ZooKeeper 当时应该考虑的是 Multi-Paxos，而不是有多个提议者的 Basic Paxos。对于 Multi-Paxos而言，领导者作为唯一提议者，不存在同时多个提议者的情况。也就是说，Multi-Paxos 无法保证操作的顺序性的问题是存在的，但原因不是文中演示的原因，本质上是因为 Multi-Paxos 实现的是一系列值的共识，不关心最终达成共识的值是什么，不关心各值的顺序。

既然 Multi-Paxos 不行，ZooKeeper 怎么实现操作的顺序性的呢? 答案是它实现了 ZAB 协议。

你可能会说了：Multi-Paxos 无法实现操作的顺序性，但 Raft 可以啊，为什么 ZooKeeper 不用 Raft 呢？这个问题其实比较简单，因为 Raft 出来的比较晚，直到 2013 年才正式提出，在 2007 年开发 ZooKeeper 的时候，还没有 Raft 呢。

ZAB 是如何保证操作的顺序性的？

与兰伯特的 Multi-Paxos 不同，ZAB 不是共识算法，不基于状态机，而是基于主备模式的原子广播协议，最终实现了操作的顺序性。

这里我说的主备，就是 Master-Slave 模型，一个主节点和多个备份节点，所有副本的数据都以主节点为准，主节点采用二阶段提交，向备份节点同步数据，如果主节点发生故障，数据最完备的节点将当选主节点。而原子广播协议，你可以理解成广播一组消息，消息的顺序是固定的。

需要你注意的是，ZAB 在这里做了个优化，为了实现分区容错能力，将数据复制到大多数节点后（也就是如果大多数节点准备好了），领导者就会进入提交执行阶段，通知备份节点执行提交操作。在这一点上，Raft 和 ZAB 是类似的，我建议你可以对比着 Raft 算法来理解ZAB。

讲到这儿我再多说一句，前面几讲的留言中有同学问状态机的事情：在 Multi-Paxos、Raft 中为什么需要状态机？这是一个很棒的问题，为你的深入思考点个赞！所以咱们先来看一下这个问题。

什么是状态机？

本质上来说，状态机指的是有限状态机，它是一个数学模型。你可以这么理解：状态机是一个功能模块，用来处理一系列请求，最大的特点就是确定性，也就是说，对于相同的输入，不管重复运行多少次，最终的内部状态和输出都是相同的。

就像你敲击键盘，在 Word 文档上打字一样，你敲击键盘的顺序决定了 Word 文档上的文字，你按照相同的顺序敲击键盘，一定能敲出相同的文字，这就是一个现实版的状态机。那么为什么在 Multi-Paxos、Raft 中需要状态机呢？

你想一下，Multi-Paxos、Raft 都是共识算法，而共识算法是就一系列值达成共识的，达成共识后，这个值就不能改了。但有时候我们是需要更改数据的值的，比如 KV 存储，我们肯定需要更改指定 key（比如 X）对应的值，这时我们就可以通过状态机来解决这个问题。比如，如果你想把 X 的值改为 7，那你可以提议一个新的指令“SET X = 7”，当这个指令被达成共识并提交到状态机后，你查询到的值就是 7 了，也就成功修改了 X 的值。

讲到这儿，你应该理解什么是状态机，为什共识算法需要状态机了吧？在解决这个问题之后，咱们说回刚刚的话题：ZAB 协议如何保证操作的顺序性？

如何实现操作的顺序性？

首先，ZAB 实现了主备模式，也就是所有的数据都以主节点为准：

其次，ZAB 实现了 FIFO 队列，保证消息处理的顺序性。

另外，ZAB 还实现了当主节点崩溃后，只有日志最完备的节点才能当选主节点，因为日志最完备的节点包含了所有已经提交的日志，所以这样就能保证提交的日志不会再改变。

你看，ZAB 协议通过这几个特性就能保证后来的操作不会比当前的操作先执行，也就能保证节点"/geekbang"会在节点"/geekbang/time"之前创建。

学到这里，想必你已经发现了，这些特性好像和 Raft 很像。是的，因为在前面几讲，我们已经学习了 Raft 算法，所以你可以类比 Raft 来理解，在 Raft 中：

1. 所有日志以领导者的为准；
2. 领导者接收到客户端请求后，会基于请求中的指令，创建日志项，并将日志项缓存在本地，然后按照顺序，复制到其他节点和提交 ;
3. 在 Raft 中，也是日志最完备的节点才能当选领导者。

内容小结

本节课我主要带你了解了状态机、为什么 Multi-Paxos 无法实现操作的顺序性，以及 ZAB 协议如何保证操作的顺序性。我希望你明确这样几个重点。

1. 状态机最大的特点是确定性，对于相同的输入不管运行多少次，最终的内部状态和输出都是相同的。需要你注意的是，在共识算法中，我们可以通过提议新的指令，达成共识后，提交给状态机执行，来达到修改指定内容的效果，比如修改 KV 存储中指定 key 对应的值。
2. ZAB 是通过“一切以领导者为准”的强领导者模型和严格按照顺序提交日志，来实现操作的顺序性的，这一点和 Raft 是一样的。

最后我想说的是，兰伯特的 Multi-Paxos 只考虑了如何实现共识，也就是，如何就一系列值达成共识，未考虑如何实现各值（也就是操作）的顺序性。最终 ZooKeeper 实现了基于主备模式的原子广播协议，保证了操作的顺序性，而且，ZAB 协议的实现，影响到了后来的共识算法，也就是 Raft 算法，Raft 除了能就一些值达成共识，还能保证各值的顺序性。

学习完本讲内容后，你可以看到，Raft 算法和 ZAB 协议很类似，比如主备模式（也就是领导者、跟随者模型）、日志必须是连续的、以领导者的日志为准是日志一致等等。你可以想一下，那为什么它们会比较类似呢？

我的看法是，“英雄所见略同”。比如 ZAB 协议要实现操作的顺序性，而 Raft 的设计目标，不仅仅是操作的顺序性，而是线性一致性，这两个目标，都决定了它们不能允许日志不连续，要按照顺序提交日志，那么，它们就要通过上面的方法实现日志的顺序性，并保证达成共识（也就是提交）后的日志不会再改变。

课堂思考

我提到在 ZAB 中，写操作必须在主节点上执行，主节点是通过简化版的二阶段提交向备份节点同步数据。那么如果读操作访问的是备份节点，能保证每次都能读到最新的数据吗？为什么呢？