Raft实现⽇志复制同步
Raft 实现⽇志复制同步
本篇⽂章以和在 Youtube 上的讲解视频及 ppt 为蓝本，深⼊分析 Raft 的内部机制，并以⽇志复制同步（Replicated Logs）为背景，详细介绍使⽤ Raft 协议实现⽇志复制的共识性问题。
⽬标：⽇志复制同步
Raft 的⽬标是将⽇志完整地复制到集内的所有服务器，这些复制的⽇志会被状态机所使⽤。假设我们希望程序或应⽤能可靠地执⾏，能够实现的⼀种⽅式是保证集中所有服务器内的状态机都能按照相同的⽅式执⾏命令，这就是状态机复制同步的⽬的，这⾥的状态机通常指的是⼀个输⼊输出程序或应⽤。⽇志可以保证状态机执⾏相同的命令。下⾯介绍它的运作机制。 如果系统的客户端将要执⾏的命令传递给集中的⼀台服务器，假设命令是 X ，那么它会被该台服务器记录，然后命令会被发送到其他服务器，并被其他服务器上的⽇志所记录。⼀旦命令被安全的复制到⽇ 志中，那么它们就能被发送到状态机供执⾏。当其中的⼀台状态机完成了命令的执⾏，结果会被返回给客户端。可以注意到只要各个服务器上的⽇志是相同的，各个服务器上的状态机就能以相同的顺序执⾏相同的命令，这样它们执⾏的结果也都是⼀样的。所以共识性模块的任务就是管理这些⽇志，并保证它们正确的在集内复制并且决定何时将命令传送给状态机才是安全的。
我们将这⼀过程称为共识性⽅法的原因是我们不需要所有的服务器在任何时候都处于运⾏状态，实际上，系统只要在⼤多数服务器存活的状态下能继续正常运⾏和相互通信就可以。所以例如可能有 3 台服务器，那么我们就可以接受其中 1 台服务器宕机，只要有两台服务器是存活的即可；当服务器有 5 台时，我们就可以接受其中的 2 台服务器宕机，只要其中三台是正常运⾏的。
现在我们来简短地介绍希望系统能够处理的失败的情况。我们允许服务器崩溃，不过我们希望它们是 “失败-停⽌（fail-stop）” 的⽅式。也就是说，它们只是停⽌⼯作，或者在停⽌后⼜恢复，不过要求只要它们是处于运⾏状态的，它们的⾏为就必须正确。这个协议要求服务器不能有做⼀些错误的操作。我们还允许⽹络的通信可以被打断，消息可以出现延迟或丢失的状态，甚⾄出现消息到达处于⽆序的状态。⽹络也有可能出现隔离的情况，然后⼜恢复正常。
达成共识性的⽅式
防盗机箱
想要实现共识性算法主要有两种⽅式：第⼀种⽅式称为对称式或⽆主式，在这种⽅式下，所有的服务器都有相同的⾓⾊，它们有同等的权⼒，它们任何时候的⾏为⼏乎都是⼀样的，客户端可以与任何⼀台服务器进⾏通信。第⼆种⽅式称为⾮对称式或基于领导者（leader），服务器在任何时候都不是对等的，只有其中的⼀台服务器是领导者（leader），领导者负责集的所有操作，其他的服务器只是简单地服从领导者发出的指令，在这种系统下，客户端永远与领导者通信，只有领导者才与其他的服务器发送通信。 Raft 就是使⽤上⾯第⼆种⽅式。它将共识性算法的问题分解成两类不同的问题，⼀种是在领导者正常运⾏下，进⾏的普通操作；另⼀种是在领导者崩溃时，需要对领导者进⾏重新选举，这种⽅式有其优势，它让普通的操作变得⾮常简单，不需要关⼼是否有多个领导者相互发⽣冲突，或同时发出指令，只要有⼀个领导者控制全局，就可以完全按照它的指令来运⾏。Raft 算法的复杂之处在于领导者发⽣变化时，因为当领导者崩溃时，会使系统处于不⼀致的状态，后续被选举的领导者需要对此这些不⼀致状态进⾏清理。总体上说，基于领导者的⽅式要⽐⽆领导者的⽅式简单，因为⽆须担⼼不同服务器间会出现冲突，只须关⼼领导者发⽣变化的情况。
Raft 概览
Raft 算法共分成 6 个部分，⾸先我们要介绍的就是领导者的选举。
1. 如何从所有的服务器中选择领导者？如何在当作为领导者的服务器崩溃时能检测到故障并挑选另⼀个领导者来替代它？
2. 会介绍当领导者接收到客户端请求时，系统是如何处理正常操作的。这是 Raft 算法中最简单的部分。
3. 会讨论领导者发⽣改变的情况，这部分是 Raft 中最复杂的，也是保证整个系统⾏为最重要的部分。⾸先，会讨论什么叫做安全，如何
保证安全？其次，领导者是如何识别⽇志的⼀致性的，从⽽可以将系统恢复到处于⼀致状态下。
植物提取4. 会讨论领导者发⽣改变时的另⼀个问题。如何让曾经崩溃死机的⽼领导者，重新回归到集后集的状态仍然能保持⼀致。
5. 会谈论客户端是如何与集互的。关键点在于客户端是如何处理服务器崩溃，如何保证客户端发送的命令是线性的，即操作执⾏也
仅执⾏⼀次。
6. 最后会讨论如何处理配置变更的情况，即如何对集增加或移除服务器。
服务器的状态
在对这六步进⾏详细地介绍前，先来介绍⼀些总体信息。
任何时候，服务器都处于以下三种状态中的⼀种：
领导者（Leader）：如前⾯已介绍的，领导者处理所有客户端的交互以及⽇志的复制同步，在任何时候只能有⼀个领导者。
跟随者（Follower）：绝⼤多数的服务器在⼤多数时间下都处于跟随者的状态，这些服务器完全处于被动状态，它们不会发起任何RPC 调⽤，它们所做的只是对其他服务器发起的 RPC 调⽤做出响应。
候选者（Candidate）：它是处于领导者（Leader）与跟随者（Follower）之间的⼀种状态，它在只在选举新领导者的过程中临时出现，在系统处于普通状态下，只会有⼀个领导者，其他的服务器都是跟随者。
在上图最下⾯展现了⼀个状态图，它展⽰了三种状态，以及三种状态在不同条件下发⽣转变的情况。现在不会对此进⾏详细解释，但是在随后对算法作详细介绍时，就能发现它们之间的联系。
时序被分割为领导者任期，每段领导者任期都有⼀个序号，这些序号随着任期数的增加会⾃动增长，不会被重复使⽤。每段任期都分为两个部分，⾸先，任期是由选举开始的，这个过程会挑选任期内的领导者，如果选举成功，被选择的领导者会服务⾄本任期结束。在同⼀任期内，只有⼀台服务器可以被选择为领导者。不过也会存在某些任期没有任何领导者，如果出现分票就会出现这种情况，不存在获得⼤多数投票的领导者，当发⽣这种状况时，系统会即刻进⼊到下⼀个新的任期并尝试重新选举。在 Raft 系统的所有服务器都保持着⼀个被称为当前任期的值，这个信息必须存于服务器的可靠媒介中（如硬盘）。这样就能在服务器崩溃之后得以重启并恢复。任期这个概念⼗分重要，它使Raft 可以判断过期的信息。例如，如果⼀台服务器认为当前的任期号是 2 与另⼀台认为当前任期号为 3 的服务器进⾏通信，那么我们就能知道来⾃于服务器 2 的信息是过期的，我们只会使⽤来⾃于最新任期的信息。所以我们将会看到在某些情况下，会使⽤到任期来检查并消除过期的信息。
Raft 协议总览
上图是 Raft 协议的完整概括，⽬前还不会对它们进⾏详细的介绍，但是会简单介绍⼀些它的特性。
⾸先分别描述 Raft 协议⾥的三种⾓⾊：跟随者（Followers）、候选者（Candidates）和领导者（Leaders）。
其次描述需要在服务器磁盘上进⾏持久化存储的信息。
第三描述服务器是如何进⾏通信的，Raft 的所有通信都是基于远程过程调⽤的（RPCs），这⾥只有两种类型的调⽤：⼀种被称为远程过程调⽤投票（RequestVote RPC），它在选举的过程中被⽤来挑选领导者；另外⼀种远程过程调⽤是领导者⽤来执⾏正常操作，复制⽇志记录的。这是 Raft 系统使⽤的唯⼀两种远程过程调⽤的⽅式。这两种调⽤都可以很好的处理⽇志复制同步以及消息丢失等问题。
⼼跳检测及超时处理
现在让我来⼀⼀讲解 Raft 协议的六个组件。Raft 协议的第⼀个组件是选举。Raft 必须保证在任何时候只能有⼀台服务器作为集的领导者。服务是以跟随者⾓⾊启动的，处于这种状态时，它不会与其
他的服务器进⾏通信，跟随者完全是被动的，它只是简单地对来⾃于其他服务器的远程调⽤做出响应。不过，为了让跟随者⼀直处于跟随者的状态，必须使它们相信集有⼀个活跃的领导者存在。唯⼀能实现的⽅式就是，如果它接收到来⾃于其他服务器的通信，⽆论是领导者或是候选者，所以如果领导者想要保持它的领导地位，它就必须定期与集的其他服务器进⾏通信，如果它没有与其他服务器进⾏主动通信的需要，那么它也必须发送⼼跳检测的消息，在 Raft 协议中，这些⼼跳检查消息也只是⼀些不含任何数据信息的 AppendEntries 远程调⽤。如果在⼀段时间内，跟随者没有接收到任何的远程调⽤，那么它会假定集内没有可达或可⽤的领导者，所以它就会开始进⾏选举，看它是否有必要成为新的领导者。这段时间周期被称为选举超时（electionTimeout），通常集将这个时间定为 100ms 到 500ms 。所以当集启动时，所有的服务器都是作为跟随者的，没有领导者，所以它们都会等待这段超时，然后它们都会开始进⾏选举。
选举
现在让我们看看，选举是如何⼯作的。
人脸识别主机
当服务器开始进⾏选举的时候，它所做的第⼀件事情就是增加当前的任期号，创建⼀个⽐之前使⽤过的任何值都要⼤的新任期号。随后，服务器将它们⾃⼰从跟随者状态转换到候选者状态，在这种状态
下，它的⽬标就是要让⾃⼰当选为领导者，为了这么做，它需要接收来⾃于⼤多数服务器的投票。候选者要做的第⼀件事情就是给⾃⼰投票，然后它会给其他所有服务器发送投票请求的远程调⽤（RequestVote），通常这些请求是并⾏发出的。如果它没有获得响应，它就会持续发送重试的请求，直到获得响应为⽌。
最终会出现三种情况中的其中⼀种：
第⼀，在⼤多数情况下，也是我们希望出现的情况就是候选者得到了多数票，然后它会将⾃⼰的状态转换为领导者并⽴即向集其他服务器
发送⼼跳检测，这可以建⽴它的领导者地位，有效的标记领导者所管理的范围。
第⼆，可能出现有其他的候选者也同时在运⾏，或许它们也有可能获得多数票成为领导者，在这个点上，如果候选者收到来⾃于有效领导者的 RPC 调⽤，那么它会⽴即放弃成为领导者的可能，随即回到跟随者的状态。
第三，有可能没有任何服务器得以获胜，如果存在有多个服务器都同时成为候选者，它们会导致分票，没有服务器会获得多数选票。为了检测到出现这种状况的可能性，随着时间的推移，当没有出现以上第⼀、第⼆种情况时，它既没有成为领导者，也没能获得来⾃于其他领导者的响应，那么它就会假定出现分票的情况。在这种情况下，只要简单地增加任期号，重新选举即可。
选举的安全及可⽤
选举有两个重要的属性：安全（Safety）和可⽤（Liveness）
安全（Safety）指的是必须最多只有⼀个候选者可以在某⼀任期内赢得领导者地位。Raft 可以保证这件事。每台服务器只给⼀个候选者投票，⼀旦它投出选票，它就会拒绝来⾃其他候选者的任何请求。服务器并不关⼼它的票到底投给了哪台服务器。为了实现这种机制，服务器需要保证将⾃⼰的投票信息存储到磁盘，这样就能在服务器崩溃之后也能恢复到之前的状态。否则就会出现服务器已经作出投票，并在崩溃重启后，在同⼀任期内将票⼜投给了另外⼀个不同服务器的情况。因为每台服务器只能进⾏⼀次投票，⽽且每个候选者都必须获得多数票，也就可以发现，不可能出现两个候选者同时获胜的情况。
⽐⽅说有三台服务器在某⼀任期内进⾏选举，另外两台服务器显然⽆法获得多数票。不过后⾯会介绍不同任期间会出现不同候选者获胜的情况，但在某⼀确定的任期内，只有⼀个候选者可以被选举为领导者。
可⽤（Liveness）需要保证⼀定有获胜者，这样系统不会永远处于没有领导者的状态。问题在于理论
上，会反复出现分票的情况，多个候选者在同⼀任期内同时开始进⾏选举，这样就会导致分票，在超时之后，⼜进⾏新⼀轮的选举⼜再次出现分票，所以从理论上说这样的状态可以⽆限循环下去。Raft 需要分散出现超时的间隔，每台服务器都会随机的计算下次超时的间隔时间，这个时间间隔在 [T, 2T] 之间。T 代表着选举超时的时间，即服务器可能出现超时的最短时间。通过将超时时间分散，可以降低两台服务器同时开始选举的机率，先启动的那台有⾜够的时间向其他所有服务器发起请求，并在其他服务器参与竞争之前就完成选举这个过程。当这个超时间隔时间远⼤于⼴播投票请求的时间时，这个策略会变得更为有效。这⾥的⼴播时间指的是，⼀台服务器与其他所有服务器通信所需的时间。
⽇志的结构
现在进⼊ Raft 协议的第⼆部分，即领导者⽤普通操作来处理⽇志复制同步时使⽤的机制。
⾸先，让我们说说⽇志本⾝。每台服务器⽆论是领导者还是跟随者，都各⾃保存⼀个⽇志副本。⽇志本⾝被分成了多条记录（Entries），记录是由下标索引的位置来进⾏唯⼀标识的，在记录内部有两个主要信息：⾸先，每条记录都包括供状态机执⾏的⼀条命令，命令的格式可以是客户端与状态所达成⼀致的某种格式。其次，每条记录都包括⼀个任期号，这个任期号是该条记录创建时，领导者所处的任期，随着⽇志记录的增多，这个任期号也会单调上升。每台服务器都必须保证⽇志能在崩溃后还可
以恢复，所以⽇志本⾝通常是存于磁盘或其他⼀些稳定的存储介质中。⽆论服务器作何更新，它都需要在收到来⾃于其他服务器的响应之前，将内容写⼊到磁盘。如果某条记录已存储于⼤多数服务器，例如上图中的记录 7 （Entry-7），那么我们就称该条记录已提交（committed）。这是 Raft 协议⾥⾮常重要的⼀个属性。如果⼀条记录是已提交的，那么它就能安全被传送给状态机进⾏执⾏，Raft 可以保证该条记录的耐久性。在上图中记录 7 是已提交的，所有先于记录 7的记录也是已提交的状态，但是记录 8 还处于未提交状态，因为它只存储于两台服务器上。
现在需要注意的是，在稍后讨论如何管理跨服务器⽇志间的⼀致性的时候，我会对提交（commitment）这个概念的定义作些许修改。
普通操作
普通操作⽐较简单，客户端将命令发送给领导者，领导者⾸先将命令写⼊它⾃⼰的⽇志中，然后向所有其他的跟随者发送 AppendEntries 的远程调⽤。通常这些调⽤的消息会被同时发送所有服务器，以并⾏的⽅式执⾏，并等待这些消息的响应。⼀旦领导者收到⾜够多的响应，可以它认为该条命令已经在多数服务器上处于已提交状态时，那么该条命令就可以被执⾏。领导者这时会将命令发送给状态机，当执⾏结束后，它会将结果返回给客户端。不仅如此，⼀旦服务器知道某个记录已经处于提交状
态，它就会通过后续的 AppendEntries 远程调⽤告知其他的服务器。所以最终，每个跟随者都会知道该记录已提交，并且将该命令发送⾄⾃⼰本地的状态机执⾏。如果跟随者崩溃了或处于慢响应状态，领导者会反复重试这个调⽤，直到跟随者恢复后，领导者就能重试成功。但是领导者并不需要等待每个跟随者的响应，它只需要等到⾜够数量的响应，保证记录已被⼤多数服务器存储即可。所以这样就能在⼀般情况下获得很好的性能提升。也就是说，在通常情况下，只需要获得⼤多数最快的服务器的应答，领导者就可以⽴即执⾏命令，并将结果返回⾄客户端。例如，如果某个服务器很慢，这并不能影响客户端获得响应的速度，因为领导者并不需要⼀直等待该台服务器。
⽇志的⼀致性
mhhpa
Raft 期望能将集⽇志维持⾼⽔准的⼀致性。理想状态下，这些⽇志在任何时候都是相同的，甚⾄是服务器崩溃时也如此。Raft 会尽可能的保证在不同服务器上的⽇志是⼀样的。上图的内容会列出⼀些重要的属性，它们在任何时候都是有效的。硅酸盐水泥熟料
第⼀，⽇志记录的索引以及任期号的组合可以唯⼀标识⼀条⽇志记录。也就是说如果有两条记录的索引是⼀样的，任期号也是⼀样的，那么就可以保证它们所存储的命令也是相同的。除此之外，还能保证在这条记录之前的所有记录都能相互匹配。所以任期号和索引的组合可以唯⼀标识整个⽇志的起始
⾄该点的位置。如果某条记录是已提交的，那么其所有前序的记录都应该处于已提交状态。这也与之前介绍的规则⼀致，如果发现服务器存储记录（如上图的记录 5），因为有了以上规则，它们存储的前序记录也必须相同。所以这些前序记录也存在于集的⼤多数服务器上。
AppendEntries ⼀致性检查
这个属性强制在 AppendEntries 远程调⽤时进⾏检查，当领导者向跟随者发起 AppendEntries 调⽤时，除了新创建的新⽇志记录，它还包括两个值。他包括当前新记录前序记录的下标位置索引以及任期号，跟随者只会接受与它⽇志匹配的远程调⽤，如果跟随者的⽇志没有相应的记录，那么它会拒绝这个远程调⽤。
让我们来看⼀个例⼦，假设领导者从客户端接收到⼀个新命令 jmp ，它将这个命令以 AppendEntries 远程调⽤的⽅式发送给跟随者，包括它前序记录的下标位置索引以及任期号，这⾥下标位置索引是 Index-4 ，任期号是 Term-2 。这样跟随者会将此信息与它⾃⼰当前⽇志的记录匹配，然后接受创建新的记录。如上图下半部分，跟随者的当前最新记录与领导者的前序记录的信息不匹配，这样跟随者会拒绝接受远程调⽤的请求。
这个⼀致性检查的过程⾮常重要。可以将这个过程看作⼀个归纳的步骤，从⽽保证前⾯⼀致性⾥所讲的内容。它要求前序每条记录都能满⾜此条件，所以这意味着如果⼀个跟随者接受了来⾃领导者的新记录，它的⽇志记录也与领导者的⽇志记录是完全匹配的。
以上就对普通操作的介绍告⼀段落。接下来介绍领导者变更的情况。
领导者变更
当领导者发⽣变更时，新领导者⾯对的状态不⼀定是⼲净的，因为前⼀领导者可能在它完成复制同步之前就已经崩溃了，当 Raft 处理这个问题时，它在新的领导者被选出之前，不会有任何特别的操作，不会存在⼀个独⽴清理过程，清理过程是在普通操作过程中发⽣的。原因是当新领导者被选出后，某些服务器可能还处于宕机的状态，不可能⽴刻对它们的⽇志进⾏清理，必须能有操作恢复它们，⽽且在这些机器重新加⼊集之前可能会要等待很长⼀段时间，所以就必须对系统进⾏设计，要求普通操作最终能让所有的⽇志达成⼀致状态。为了达成这个⽬标，Raft 始终会认为领导者的⽇志总是正确的，所以对于所有领导者，它们必须时刻的让跟随者的⽇志与⾃⼰保持⼀致，但同时还是有可能出现在领导者未完成任务就崩溃的情况，所以就会出现⼀个⼜⼀个的新领导者。所以，在极端扭曲的状态下，⽇志记录会⽆限堆积并出现混乱的状态，就如上图所⽰的那样。
为了简单起见，上图中只显⽰了下标索引位置以及任期号，没有显⽰具体的命令信息。
当服务器 S4、S5 在任期 2、3、4 时是领导这，但是由于某些原因，它们⽆法完成对其他服务器（S1、S2、S3）上⽇志的复制同步，然后它们崩溃了，系统在⼀段时间内处于分隔状态，服务器 S1、S2、S3 在任期 5、6、7 内成为领导者，但同时也⽆法与服务器 S4、S5 进⾏通信，要求它们进⾏相应的清理操作。这就会出现上图中所⽰的状态，⽇志完全是混乱的。这⾥的关键在于 S1、S2、S3 的索引 1-3 以及S4、S5 的索引 1-2 区域。这些都是已提交状态的记录，所以我们必须保留它们，但其他的⽇志记录都是未提交的，所以到底是保留还是丢弃它们并不重要。我们还没有将它们传⼊状态机，也没有客户端得到了这些命令的执⾏结果。所以它们都是可以丢弃的。
例如，假设服务器 S4 是任期 7 的领导者，⽽且它可以与其他所有服务器通信，那么它最终会让集⾥其他服务器上的⽇志与它⾃⼰的保持⼀致，并删除那些与之冲突的记录。在介绍领导者是如何让其他服务器上⽇志与之保持⼀致前，⾸先需要介绍两个概念：正确性（Correctness）和安全性（Safety）。我们是如何知道系统的⾏为是正确的？如何知道它们没有丢失⼀些重要信息？因为这⾥可以看到，为了让集回到⼀致的状态，有些⽇志记录会被丢弃。我们是如何安全地做到这点的？
安全性的要求
⼏乎所有的⽇志复制同步系统都会对安全性有所要求，⼀旦某个状态机接收了⼀条⽇志记录并执⾏，我们必须保证不存在其他的状态机执⾏不同的命令。需要保证所有的状态机，以相同的顺序执⾏相同⽇志记录的命令。为了达成总体的安全性要求，Raft 实现了⼀个安全属性，⼀旦领导者决定某个特定记录已提交，那么 Raft 就需要保证该条记录会出现在它所有未来领导者的⽇志记录中，并且也处于已提交状态。如果我们可以让 Raft 遵从这个属性，那么它就⾃然可以保证以上的安全性要求。⾸先，领导者永远不会覆盖⽇志记录，它只会追加，正如我们所知，作为领导者时，这些⽇志记录永远不会被改变，其次，为了到达已提交的状态，记录必须在领导者⽇志中，这样就不会有其他值会被提交，第三，如果我们知道⽇志记录必须在发送给状态去执⾏之前被提交，所以将以上三点放在⼀起，我们就能使该属性可以满⾜安全性的要求。
⽬前为⽌，我们对 Raft 的描述还不能保证这个属性。下⾯我会来看看 Raft 是如何解决这个问题的。不过再次之前我们需要再看看，如果某条记录是已提交的，那么它在未来的领导者⽇志记录中也必须是已提交的。为了满⾜这个要求，我们会从两个⽅⾯对 Raft 算法作出修改。⾸先，我们会修改选举过程，将⽇志记录不正确的那些机器排除在选举之外，其次，会对已提交的定义做略微的调整。有时在知道安全之前，我们会延迟⼀条记录的提交。
下⾯会先介绍选举相关的问题
挑选最好的领导者
如何保证选择的领导者有所有已提交的⽇志记录？⾸先，这有点微妙，事实上我们⽆法辨别哪些记录是已提交的，假设有如上图的三台服务器，我们需要选择⼀个新的领导者，但其中的⼀台服务器不可⽤，那么只要在这个过程中，查看可⽤的服务器，我们此时是⽆法分辨记录 5是否已提交，它依赖于不可⽤服务器上存储的内容。在这个例⼦中，记录 5 是已提交的，但在其他情况下，可能不是。可以肯定的是我们⽆法知道哪些记录已被提交了。所以我们能做的就是到⼀个候选者，这个候选者很有可能包括所有已提交的记录，我先从直观上尝试解释如何做到的，然后在⽤精确的⽅式加以证明，我们是能够挑选到候选者存有所有已提交的记录的。
我们通过⽐较⽇志的⽅式来实现。当⼀个候选者发起投票请求，它会包括⾃⾝的⽇志记录信息，位置索引 index 以及该记录的任期号 term 。当响应投票的服务器接收到请求，它会将候选者的⽇志信息与⾃⼰的⽇志信息进⾏⽐较，如果投票者的⽇志更完整，那么它会拒绝投票（lastTerm v > lastTerm c）|| (lastTerm v == lastTerm c) && (lastIndex v > lastTerm c)。结果是赢得选举的服务器可以保证⽐⼤多数投票者有更完整的⽇志记录。
让我们看看实际到底是如何⼯作的。
在当前任期提交记录
最有趣的情况恰好是在领导者决定刚决定⽇志记录是已提交的时候，会有两种场景：
第⼀种：提交的记录是在当前任期
这⾥任期 2 以及领导者（S1）刚成功调⽤ AppendEntries ⾄ S3 ，此时它发现记录已在⼤多数服务器上存储，随即标记该记录是已提交的，并将其传送给状态机。此时这条记录是安全的，下⼀任期的领导者必须认定该记录的已提交状态。正如之前介绍的规则，S5 是⽆法成为下⼀任期的领导者，S4 也⽆法成为领导者，所以只有 S1、S2、S3 可能被选举成领导者，实际上，如果 S1 在它们中间，S1 ⼀定可以保证赢得选举，但 S2、S3 也可以通过获得其他服务器（S4、S5）的投票，获胜成为领导者。但在任意⼀种情况下，下⼀任期的领导者都必须包含该⽇志记录。
第⼆种：提交的记录是在前序任期
在这种状态下，领导者在任期 2 只复制了两台服务上的⽇志记录，随后任期 3 的领导出（S5）于某些原因没有关注到这些记录，在它本地创建了⼀些记录，然后崩溃了。然后在任期 4 上，领导者（S1）作为试图将其他服务器上的⽇志内容与它⾃⼰的达成⼀致。所以它让服务器 S3 复制了它⾃⼰ Term-2
记录，在这个点上，该记录已被领导者知道存于⼤多数服务器上，但该记录并没有安全的被提交。因为此时 S1 可能出现崩溃，S5 成为领导者，因为它的前序任期值 3 较⼤，所以它可以获得来⾃于 S2、S3、S4 的投票，如果它当选，那么它会试图将⾃⼰的⽇志推到其他的服务器，这也就意味着从 S1 - S4 下标位置索引 3 开始的所有记录都会被删除。所以此时我们还⽆法认定记录 3 是否已经提交。
新提交规则
在这种情况下，新的选举规则并不⾜以保证安全性（Safety），我们还需要修改提交的规则。到⽬前为⽌只要领导者发现记录已存于⼤多数服务器，那么它就认为该记录已被提交。但是为了保证安全性，我们需要增加另⼀条规则。除了上述规则，领导者必须能看见⾄少有⼀条来⾃于它本任期内的记录也存于⼤多数服务器。回到之前的例⼦，如果领导者完成了记录 3-2 的复制，它此时还⽆法提交该记录并将其发送给状态机，取⽽代之的是，它必须等待直到它当前任期内的第⼀条记录（4-4）提交并存于⼤多数的服务器。⾄此，两条记录才能都发送给状态机。这么做的原因在于，在这种状态下，服务器 S5 是不可能被选举为下届领导者的，因为有更多的服务器处于更近的任期（任期 4），服务器 S5 只能从服务器 S4 处得到选票。此时，记录 3 和 4 都是安全的。所以将新选举规则来⽐较⽇志与新提交规则相结合，我们就能保证 Raft 的安全属性总是有效的。即⼀旦领导者决定记录已提交，它就会对未来的所有领导者可见。这⾥我们展⽰的例⼦只说明，已提交的记录对下⼀任期的领导者可见，但
也可以很容易就证明，每个未来的领导者也会有相同的⽇志记录。
⽇志的不⼀致
合成氨催化剂现在我们可以保证安全性，也明⽩了⽇志是正确的。那么我们如何让所有跟随者的⽇志都与领导者保持⼀致呢？⾸先，让我们来看看⽇志不⼀致可以出现怎样的情况。
跟随者可能会丢失记录（如 (a)-10、(b)-5、(e)-8）
跟随者可能会有不同的记录（如 (d)-11、(f)-4、(c)-6）
需要做的是剔除所有不同的⽇志记录，并将所有丢失的记录根据领导者的⽇志填充完整。
修复跟随者的⽇志
要想恢复到⼀致状态，领导者会为每个跟随者维护⼀个状态变量，这个变量称为 nextIndex ，这个变量存储⽇志的下⼀条记录的下标位置索
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议