raft算法问题（系统设计基础知识）

raft算法问题（系统设计基础知识）系统设计基础知识(八)了解IP地址和端口系统设计基础知识(七)—代理系统设计基础知识(四)—系统可用性系统设计基础知识(五)—缓存系统设计基础知识(六)—缓存区

系统设计基础知识系列第十二章Raft算法。你可以阅读我以前的文章

系统设计基础知识(一) - 网络

系统设计基础知识(二)—数据库

系统设计的基础知识(三)吞吐量和延迟

系统设计基础知识(四)—系统可用性

系统设计基础知识(五)—缓存

系统设计基础知识(六)—缓存区

系统设计基础知识(七)—代理

系统设计基础知识(八)了解IP地址和端口

系统设计基础知识(九)—负载均衡器

系统设计基础知识(十)—DNS

系统设计基础知识(十一)—WebSocket协议

要理解共识算法，我们必须区分一致性问题和共识问题。

一致性是熟悉的事务 ACID 特性之一。它必须满足事务从一种状态到另一种状态转换的完整性约束。

共识是指分布式系统中的节点如何就某事达成共识，它可以是一个值、一系列动作或一个决策。

一致性：状态转换的完整性约束

共识：集群中节点对某事达成的共识

Raft算法背景

在Raft 协议诞生之前，Paxos 算法垄断了共识算法领域，几乎成为共识协议的代名词。但是，Paxos 算法太难以理解，难以实现。因此，斯坦福大学的 2 位教授（Diego Ongaro和John Ousterhout）提出了 Raft 算法。

Raft 算法与多 Paxos 具有相同的功能和效率，但其组织结构与 Paxos 不同。与直接衍生自分布式共识问题的 Paxos 算法不同，Raft 算法是从多副本状态机的角度衍生出来的，用于管理复制的日志。

由于系统可用性和容错性，需要分布式共识协议。为了避免单节点故障导致整个系统不可用，多节点部署中的数据复制已经实践。但是一旦数据有多个副本，就需要解决并发控制的共识问题。

为了解决多副本数据的分布式共识问题，我们可以将其简化为多副本状态机的共识问题。对于客户端发送的一系列指令，只要指令按照唯一确定的顺序发送到所有节点，并且每个状态机的初始状态相同，最终必然会达到相同的状态并达成共识指令被执行。

高可用数据库管理系统一般将复制内置到存储引擎的日志管理器模块中，通常使用Paxos多副本模式来维护高可用

Raft算法概述

Raft 算法有 3 个新特性

1. 强领导者模型——日志条目只会从领导者同步到其他节点
2. 领导者选举——随机计时器用于控制选举。
3. 成员变更——使用联合共识机制，使得集群在集群配置发生变化（添加/删除节点）时可以正常工作

架构

它是解决容错问题的复制状态机

• 每个服务器存储一个日志
• 共识模块选择领导者，管理客户端发送的指令的复制日志，并与其他节点同步日志
• 每个日志条目都包含一个命令。可用于达成共识、同步、广播、分发或提交命令
• 每个节点上的状态机都有一个数据集的副本，它按顺序执行命令，以便它可以产生相同的结果

过程

1. 节点上的共识模块接收客户端的命令，将命令写入本地日志，并与其他节点上的共识模块进行通信，以便在其他节点上进行日志复制。因此，即使某些节点崩溃了，该节点日志中的命令顺序仍然是一样的。
2. 每个节点上的日志以相同的顺序存储相同的命令。节点上的状态机可以产生确定的结果。
3. 命令成功复制到其他节点后，每个节点的状态机按照相同的顺序处理命令，并将确定的结果返回给客户端。

Raft算法概念

Raft 将共识分解为多个共识的关键要素，如领导人选举、日志复制、安全、日志压缩和成员更改。它加强了一致性，以减少必须考虑的状态数量。

Raft 集群大小

集群中的节点数量可以自由定义，但通常为5个。当集群由5个节点组成时，可以容忍2个节点的宕机时间。只要没有3个节点同时出现故障，3个节点同时宕机的概率很小。如果集群中的一两个节点宕机，集群就有足够的时间进行修复。如果集群中的节点数量过多，可能会拖慢整个系统对客户端的命令处理速度。

角色

Raft 将角色划分为领导者、追随者和候选人

1. 领导者：每个集群只有 1 个领导者。它接受客户端请求，管理日志复制，并将请求日志与follower同步。数据从领导者单向流向其他节点（追随者）。
2. Follower：接受并持久化leader同步的日志，在leader指示后提交。它不会响应其他追随者的请求，而只会响应领导者和候选人的请求。如果follower收到客户端的请求，会返回leader的信息给客户端，客户端联系leader。当它在一定时间内没有收到日志复制时，就会超时，成为候选。
3. 候选人：它向其他节点发送请求投票的 RPC 消息。如果它赢得多数，它就会成为新的领导者。

在处理客户端请求时，需要在响应请求之前更新所有节点的持久状态：

• currentTerm: 节点的最新术语
• votedFor：当前任期内节点投票的候选人
• log[]：它由日志条目组成，每个条目都包含状态机中的一个命令

在处理客户端请求时，需要在响应请求之前更新所有节点的非持久状态：

• commitIndex: 最后提交条目的索引
• lastApplied: 最后应用条目的索引

在处理客户端请求时，需要在响应请求之前更新跨领导者的非持久状态：

• nextIndex[]：对于每个节点，发送下一个日志条目时的索引。
• matchIndex[]：对于每个节点，最后一个成功复制的条目的已知索引。

Term

时间分为任期，每个任期都以选举开始。

1. 一名或多名候选人正试图成为领导者。
2. 当追随者成为候选人或候选人开始新一轮选举时，当前任期为n 1。
3. 选举成功后，候选人将成为该任期的领导人。领导者将管理整个集群，直到下一个任期出现。
4. 有时，选举会失败（分票），导致任期内没有领导（多个候选人获得相同票数）。在这种情况下，候选人将再次超时，任期将直接结束，并进行下一轮选举。
5. raft算法保证每个term最多有1个leader。

• 例如，在第 3 学期，没有选举出领导人。因此，多名候选人进入第 4 任期的选举。
• Served by Server A 观察到 term 的变化可能是：term 1 -> term 2 -> term 3
• Served by Server B 观察到 term 的变化可能是：term 1 -> term 3
• 因此，集群中每台服务器观察到的术语切换可能不同
• Raft 协议中术语的概念实际上类似于逻辑时钟的概念。它允许每个节点检测过时的信息，例如过时的领导者。

Term工作流程

1. 每个节点都会存储一个允许增加但不允许减少的变量号<current term>
2. 当集群中的各个节点向客户端发送请求时，请求中会携带变量<current term>的值
3. 节点间通信时，节点会将自己的信息放在变量<current term>上
4. 如果变量A（已存储）<变量B（已接收），则节点A更新为节点B。如果此时节点A的身份为candidate，将立即失去资格，成为follower
5. 如果Variable A = Variable B，则请求可以正常处理
6. 如果变量 A > 变量 B，则直接拒绝请求

节点间通信

集群中的节点相互进行远程过程调用 (RPC)。有 2 个 RPC。

• RequestVote RPC：由候选人调用，请求其他节点为自己投票。
• AppendEntries RPC：被Leader调用以复制日志并用作消息通知。

选举

过程

领导者在任期内会定期与其他追随者沟通，以维持其职位。如果follower发现leader与自己断开连接，随机等待一段时间，follower会发起选举，成为候选人，竞选leader。

1. Term，n 1
2. 追随者成为候选人
3. 节点为自己投票，重置选举计时器并请求其他节点投票
4. 节点一直处于候选状态，直到选出领导者

原则

1. 每个节点每学期只能投票一次，先到先得
2. 如果一个候选人被选举为领导者，它将通知其他节点以避免重新选举
3. 在等待其他节点的投票时，候选人可能会收到来自另一个节点的声称是领导者的请求
4. 一个节点成为领导者，所有其他节点成为追随者。
5. 一段时间过后没有节点赢得选举，候选人超时并开始新一轮选举，所有Term为n 1

投票后，有3 种可能的选举结果。

1. 候选人赢得选举

• 获得超过50%的选票
• 保证同一任期内最多可以选举1个leader。一旦候选人赢得选举，它将通知其它节点。

2.有其他节点被选举为leader，但选举可能失败

• 在获得超过 50% 的选票之前，候选人会收到来自另一个节点的自称是领导者的请求。
• 系统将其他节点提供的变量<current term>与候选者进行比较，
• 如果一个变量（其他节点）≥变量（候选人），候选人再次成为追随者
• 如果变量（其他节点）≤变量（候选人），候选人拒绝请求，保持候选人状态，等待选票收集完成

3.没有节点被选为leader（分裂投票）

• 如果多个追随者同时成为参加选举的候选人，则没有一个获得超过 50% 的选票。
• 由于选票超时，每位候选人将开始新一轮的选举。
• 这会导致选举领导者的延迟，从而影响集群的可用性。
• 为了解决无限分裂投票的问题，Raft 协议采用了随机选举超时策略。
• 在follower状态下，从某个固定时长（150-300ms）中随机选择一个选举超时时间，使得节点的超时时间相对分散。在大多数情况下，最多可以同时使用1个节点超时，并且节点在其他节点超时之前赢得了选举。
• 在候选人状态下，它在每轮选举开始时随机重置其选举超时，并等待到新的选举，减少新一轮选举中出现分裂投票的可能性。

日志组织结构

每个条目都有一个按顺序编号的索引。每个条目包含：

1. 条目的术语编号
2. 具体命令

• 顶部代表日志索引，保证唯一性。
• 每个块代表客户端请求的数据操作指令，并在复制状态机中执行。

日志复制

当一个节点成为领导者时，它开始接收和处理所有客户端请求。

• 将所有客户端命令追加到日志中，并通知其他节点并行追加日志
• 日志被其他节点复制后，领导者将指令应用到状态机并将结果返回给客户端
• 如果出现问题，AppendEntries RPC即使在回复客户端之后，领导者也会继续重复，直到所有追随者都附加了日志。

日志提交

• 每个客户端请求都包含一个命令、术语号和日志的前一个日志索引。
• 领导者决定何时将日志条目提交到状态机，以便所有提交的日志都是持久的并由所有状态机执行
• leader不断更新最大的commited index，并把这个值通知follower去执行状态机中的entry
• 在提交条目之前，领导者必须将条目复制到大多数节点。
• 当领导者提交一个条目时，它也会间接提交日志中所有以前的条目，包括其他领导者创建的条目。
• 领导者记录最大提交索引并通知所有节点，以便其他节点知道领导者的提交位置，并按日志顺序将它们应用到他们的状态机。它被称为leadercommit。

日志一致性/日志匹配

• 日志匹配的属性由以下方式保证：

1. 如果不同日志中的两个条目具有相同的索引和任期号，则存储的命令相同，这是由领导者保证的；
2. 如果不同日志中的两个条目具有相同的索引和任期号，则它们之间的所有条目完全相同，这是由日志复制规则保证的
3. 在追加的日志中，领导者在日志中附加上一个条目和新条目的索引和任期号。
4. 如果follower的日志中相同的index位置没有entry，或者有entry但是term不同，follower拒绝新的entry

• 所以，有一些规则：
• 1）leader只能将之前的日志追加到当前日志，不能覆盖日志
• 2）只能提交leader的日志条目，follower不能接收请求和提交日志
• 3) 只有已经提交的日志条目才能应用到状态机
• 4）限制新的leader日志包含选举期间所有提交的日志条目
• 追加日志的一致性检查：正常情况下，leader和follower的日志可以保持一致。但是，在某些情况下，日志中会出现不一致的情况。例如，领导者在将其日志中的条目复制到其他节点之前崩溃。

• ab：条目丢失
• cd：额外的未提交条目
• ef：出现以上两种情况
• 从 term 2 开始，node F 成为 leader 并在其 log 中附加了一些条目（紫色），但在提交之前它崩溃了，然后在重新启动后在 term 3 中迅速再次成为 leader，然后添加了一些条目（橙色）到它自己的日志，在提交第 2 和第 3 学期的条目之前再次崩溃。
• 所以，领导者强迫追随者复制自己的日志来解决不一致的问题。follower中所有与leader冲突的日志都会被覆盖。
• 1）找到leader和follower的最后一个共同入口
• 2) 删除关注者日志中从他的条目开始的所有条目
• 3）将leader日志中的所有条目从他的条目开始同步到follower
• 这样，领导者永远不会覆盖或删除自己日志中的条目，只会将领导者日志中的所有条目同步到跟随者日志中。所以，日志一致性通过一致性检查机制。

日志不一致

• 在正常情况下，一致性检查不会失败。但是，当领导者日志没有完全复制时，可能会导致日志不一致。例如，follower 可能没有新领导者具有的条目，或者可能具有新领导者没有的条目。

综上所述，Raft 协议始终保证以下属性

1. 一个任期内最多选举一个领导人
2. 领导者永远不会覆盖或删除自己的日志条目，只会将新条目附加到自己的日志条目中
3. 如果不同日志中的两个条目具有相同的索引和任期号，则存储的命令相同，这是由领导者保证的；
4. 如果不同日志中的两个条目具有相同的索引和任期号，则它们之间的所有条目完全相同，这是由日志复制规则保证的
5. 如果一个条目在一个任期内被提交，它将出现在所有任期较大的领导者的日志中
6. 如果一个节点将提交的日志条目应用到复制状态机，其他节点将不会在同一索引上应用不同的条目

如果你发现我的任何文章对你有帮助或有用，麻烦点赞或者转发。 谢谢！