MIT6.824-Raft笔记:脑裂、Majority Vote(过半投票/过半选举)

本部分主要是问题引入，以及给出一个解决方案

1 脑裂（Split Brain）

replication system的共同点：单点

前面几个容错特性（fault-tolerant）的系统，有一个共同的特点。

• MapReduce复制了计算，但是复制这个动作，或者说整个MapReduce被一个单主节点控制。
• GFS以主备（primary-backup）的方式复制数据，会实际的复制文件内容，但它也依赖一个单主节点，来确定每一份数据的主拷贝的位置。
• VMware FT在一个Primary虚机和一个Backup虚机之间复制计算相关的指令。当其中一个虚机出现故障时，为了能够正确的恢复，需要一个Test-and-Set服务来确认，Primary虚机和Backup虚机只有一个能接管计算任务。

它们都是一个多副本系统（replication system），背后存在一个共性：它们需要一个单节点来决定，在多个副本中，谁是主（Primary）。使用一个单节点的好处是，它不可能否认自己，因为只有一个节点，它的决策就是整体的决策；缺点是，它本身又是一个单点故障（Single Point of Failure），将系统容错的关键点，转移到了这个单点上。在系统出现局部故障时，通过primary copy继续工作。使用单点是为了避免脑裂（Split-Brain）。当出现故障时，要极其小心的决定数据的主拷贝，否则需要面临脑裂的场景。

这里主要说明多副本系统，虽然是多副本，但是最终还是搞了一个单点来做决定，而这样做的目的是为了避免脑裂；同样单点故障又可以通过新的primary继续工作。
下面通过示例可以得知，如果是多副本系统，要么同时等待所有副本响应，这样还不如单点，因为多个是一个出现问题的多倍；要么不等待多个，那这样就会出现脑裂，根源也很简单，在分布式系统中，根本无法确定你连接不上的这个服务到底是宕机了，还是仅仅你连接不上而其它服务可以。

脑裂带来的问题及其严重性

这里通过将单点Test-and-Set服务设计为多副本，说明为什么出现故障时，很难避免脑裂。
VMware FT中的Test-and-Set之前是一个单点服务，而VMware FT依赖这个Test-and-Set服务来确定Primary虚机，为了提高系统的容错性构建一个多副本的Test-and-Set服务。网络里面有两个服务器（S1，S2）都是Test-and-Set服务的拷贝，还有两个客户端（C1，C2），它们需要通过Test-and-Set服务确定主节点是谁。在这个例子中，这两个客户端本身就是VMware FT中的Primary和Backup虚拟机。
这两个Test-and-Set服务器中的数据记录将从0开始，任意一个客户端发送Test-and-Set指令，这个指令会将服务器中的状态设置成1，两个服务器都应该设置成1，然后将旧的值0，返回给客户端。本质上来说，这是一种简化了的锁服务。
**当一个客户端可以与其中一个服务器通信，但是不能与另一个通信时，有可能出现脑裂的问题。**假设客户端需要将请求同时发送给两个服务器。这时就需要考虑脑裂问题，即会出现各种情况的网络分区，以及服务器不响应需要如何处理。

• 如果我们只将C1的请求设置给S1，而不设置给S2，会导致S2的数据不一致。或许应该规定，对于任何操作，客户端必须总是与两个服务器交互，而不是只与其中一个服务器交互。**但是这是一个错误的想法，因为这里根本就没有容错，甚至比只使用一个服务器更糟。**因为当两个服务器中的一个故障了或者失联了，我们的系统就不能工作了。对于一个单点的服务，我们只依赖一个服务器。现在我们有两个服务器，并且两个服务器都必须一致在线，这里的难度比单个服务器更大。
• 如果客户端不能同时与两个服务器交互，那它就与它能连通的那个服务器交互，同时认为另一个服务器已经关机了。这也是一个错误的答案呢？我们的故障场景是，另一个服务器的状态无从知晓，实际可能是网络线路出现了故障，从而导致C1可以与S1交互，但是不能与S2交互。同时C2可以与S2交互，但是不能与S1交互。如果一个客户端连接了两个服务器，为了达到一定的容错性，客户端只与其中一个服务器交互也应该可以正常工作。但是这样就不可避免的出现了这种情况：假设这根线缆中断了，将网络分为两个部分。C1发送Test-and-Set请求给S1，S1将自己的状态设置为1，并返回之前的状态0给C1。C1对应的虚拟机会认为自己可以成为主节点。但是同时S2里面的状态仍然是0。如果现在C2也发送了一个Test-and-Set请求，本来应该发送给两个服务器，但是现在从C2看来，S1不能访问，根据之前定义的规则，那就发送给S2吧。同样的C2也会认为自己持有了锁。如果这个Test-and-Set服务被VMware FT使用，那么这两个VMware 虚机都会认为自己成为了主虚拟机而不需要与另一个虚拟机协商，这是一个错误的场景。

这里主要是针对上面的共同点，通过举反例说明单点的必要性。
实际上Lecture4中最后也提到 test and set 应该也是具有容错性的服务，而不是某个单点。

**在有两个拷贝副本的配置中，看起来我们只有两种选择：要么等待两个服务器响应，那么这个时候就没有容错能力；要么只等待一个服务器响应，那么就会进入错误的场景（通常称为脑裂）。**这基本是上世纪80年代之前要面临的挑战。多副本系统时，需要排除脑裂的可能，这里有两种技术：

• 构建一个不可能出现故障的网络。比如电脑中，连接了CPU和内存的线路就是不可能出现故障的网络。如果网络不会出现故障，这样就排除了脑裂的可能。当网络不出现故障时，那就意味着，如果客户端不能与一个服务器交互，那么这个服务器肯定是关机了。这里假设有足够多的资金，就能接近这个假设。

主要还是，只要有网络的情况下，节点A和节点B连接异常，但是B本身是什么样的，节点B和其他节点是什么样的是未知的。

• 人工解决问题，不要引入任何自动完成的操作。默认情况下，客户端总是要等待两个服务器响应，如果只有一个服务器响应，永远不要执行任何操作。之后通过运维人员检查，进行关机等处理，这里本质上把人作为了一个决策器，这个人也是个单点。

很长一段时间内，人们都使用以上两种方式中的一种来构建多副本系统。这虽然不太完美，因为人工响应不能很及时，不出现故障的网络又很贵，但是这些方法至少是可行的。

2 Majority Vote (quorum)

尽管存在脑裂的可能，人们发现哪怕网络可能出现故障，可能出现分区，实际上是可以正确的实现能够自动完成故障切换的系统。这种能自动恢复，同时又避免脑裂的多副本系统，关键点在于多数投票（Majority Vote）。这也是用来构建Raft的一个基本概念。
网络分区（Partition）：当网络出现故障将网络分割成两半，网络的两边独自运行且不能访问对方。
多数投票系统的第一步在于，服务器的数量要是奇数，而不是偶数。如果只有两个服务器，被网络故障分隔的两边，它们看起来完全是一样的，它们运行了同样的软件，它们也会做相同的事情，这样不太好（会导致脑裂）。但如果服务器的数量是奇数的，那么当出现一个网络分割时，两个网络分区将不再对称，这是多数投票吸引人的地方。首先你要有奇数个服务器。然后为了完成任何操作，例如Raft的Leader选举，例如提交一个Log条目，在任何时候为了完成任何操作，你必须凑够过半的服务器来批准相应的操作。

如果是偶数会如何呢，这里举两个例子：

1. 2副本，那么如果分区，就要等待过半投票，即2/2 + 1 = 2，也就是每一个都要等待2个的响应，那这个和6.1中第二小节示例中的方案一：必须与所有副本通信，又有何区别，反而提高了故障概率。
2. 4副本，过半投票 4/2+1=3，这里好一些了，能够容忍1个的故障，但是这和3副本相比，并不能提高容错概率，还不如之间5副本或者3副本，浪费反而不会提高容错。

综上：偶数情况下，如果被网络故障均分，那么整个系统依然是不可用的。

这里背后的逻辑是，如果网络存在分区，最多只有一个分区能够拥有过半的服务器。这里有一点需要明确，当我们在说过半的时候，我们是在说所有服务器数量的一半，而不是当前开机服务器数量的一半。这个点困扰了我（Robert教授）很长时间，如果你有一个系统有3个服务器，其中某些已经故障了，如果你要凑齐过半的服务器，你总是需要从3个服务器中凑出2个，即便你知道1个服务器已经因为故障关机了。过半总是相对于服务器的总数来说。

服务器的总数：一是因为实际上很难完全知道具体出现故障的机器到底是怎么了，另一方面是因为为了后面的过半更新+过半选举，这样选出来的leader一定包含有最新数据。

个人思考：

1. 这里的开机，在有网络的情况下，A连接不上B，无法判断B是否开机，B和C是否连接？
2. 需要及时处理故障机
3. 需要提供快速的数据恢复

对于多数投票，可以用一个更通用的方程式来描述：如果系统有 2 * F + 1 个服务器，那么系统最多可以接受F个服务器出现故障，仍然可以正常工作。这也被称为多数投票（quorum）系统，因为3个服务器中的2个，就可以完成多数投票。
有关多数投票系统的一个特性就是，最多只有一个网络分区会有过半的服务器，我们不可能有两个分区可以同时完成操作。这里背后更微妙的点在于，如果你总是需要过半的服务器才能完成任何操作，同时你有一系列的操作需要完成，其中的每一个操作都需要过半的服务器来批准，例如选举Raft的Leader，那么每一个操作对应的过半服务器，必然至少包含一个服务器存在于上一个操作的过半服务器中。任意两组过半服务器，至少有一个服务器是重叠的。实际上相比其他特性，Raft更依赖这个特性来避免脑裂。
例如，当一个Raft Leader竞选成功，那么这个Leader必然凑够了过半服务器的选票，而这组过半服务器中，必然与旧Leader的过半服务器有重叠。新的Leader必然知道旧Leader使用的任期号（Term ID），因为新Leader的过半服务器必然与旧Leader的过半服务器有重叠，而旧Leader的过半服务器中的每一个必然都知道旧Leader的任期号。类似的，任何旧Leader提交的操作，必然存在于过半的Raft服务器中，而任何新Leader的过半服务器中，必然有至少一个服务器包含了旧Leader的所有操作。这是Raft能正确运行的一个重要因素。
在多数投票这种思想的支持下，大概1990年的时候，有两个系统基本同时被提出。这两个系统指出，你可以使用这种多数投票系统，从某种程度上来解决之前明显不可能避免的脑裂问题，例如，通过使用3个服务器而不是2个，同时使用多数投票策略。两个系统中的一个叫做Paxos（1989），Raft论文对这个系统做了很多的讨论；另一个叫做ViewStamped Replication（VSR， 1988）。尽管Paxos的知名度高得多，Raft从设计上来说，与VSR更接近。VSR是由MIT发明的。
学生提问：可以为Raft添加服务器吗？
Rober教授：Raft的服务器是可以添加或者修改的，Raft的作者提出了方法来处理这种场景，但是比较复杂。

参考文献：
https://pdos.csail.mit.edu/6.824/schedule.html
https://mit-public-courses-cn-translatio.gitbook.io/mit6-824/