安丘做网站的公司,做网站页面用什么,广州互联网广告推广,四川省住建设厅网站前言 在正式开始介绍 Raft 协议之间#xff0c;我们有必要简单介绍一下其相关概念。在分布式系统中#xff0c;一致性是比较常见的概念#xff0c;所谓一致性指的是集群中的多个节点在状态上达成一致。在程序和操作系统不会崩溃、硬件不会损坏、服务器不会掉电、网络绝对可靠…前言 在正式开始介绍 Raft 协议之间我们有必要简单介绍一下其相关概念。在分布式系统中一致性是比较常见的概念所谓一致性指的是集群中的多个节点在状态上达成一致。在程序和操作系统不会崩溃、硬件不会损坏、服务器不会掉电、网络绝对可靠且没有延迟的理想情况下我们可以将集群中的多个节点看作一个整体此时要保证它们的一致性并不困难。
但是在现实的场景中很难保证上述极端的条件全部满足节点之间的一致性也就很难保证这样就需要 Paxos、 Raft 等一致性协议。一致性协议可以保证在集群中大部分节点可用的情况下集群依然可以工作并给出一个正确的结果从而保证依赖于该集群的其他服务不受影响。这里的“大部分节点可用”指的是集群中超过半数以上的节点可用例如集群中共有 5个节点此时其中有 2 个节点出现故障宕机剩余的可用节点数为 3此时集群中大多数节点处于可用的状态从外部来看集群依然是可用的。
常见的一致性算法有 Paxos、 Raft 等Paxos 协议是 Leslie Lamport 于1990年提出的一种基于消息传递的、具有高度容错特性的一致性算法Paxos 算法解决的主要问题是分布式系统内如何就某个值达成一致。在相当长的一段时间内Paxos 算法几乎成为一致性算法的代名词但是 Paxos 有两个明显的缺点第一个也是最明显的缺点就是 Paxos 算法难以理解Paxos 算法的论文本身就比较晦涩难懂要完全理解 Paxos 协议需要付出较大的努力很多经验丰富的开发者在看完 Paxos 论文之后无法将其有效地应用到具体工程实践中这明显增加了工程化的门槛也正因如此才出现了几次用更简单的术语来解释 Paxos 的尝试。Paxos 算法的第二个缺点就是它没有提供构建现实系统的良好基础也有很多工程化 Paxos 算法的尝试但是它们对 Paxos 算法本身做了比较大的改动彼此之间的实现差距都比较大实现的功能和目的都有所不同同时与Paxos算法的描述有很多出入。例如著名 Chubby它实现了一个类Paxos的算法但其中很多细节并未被明确。本章并不打算详细介绍 Paxos 协议的相关内容如果读者对Paxos感兴趣则可以参考Lamport发表的三篇论文《The Part-Time Parliament》、《Paxos made simple》、《Fast Paxos》。
正因为上述的缺点导致 Paxos 协议处于一种比较尴尬的境地在理论上 Paxos 算法是正确可行的但是实际的工程中很少有与 Paxos 算法类似的实践。很多工程实践包括上面提到的Chubby都是从 Paxos 协议的研究开始的然后在实践的过程中发现很多难题之后通过各种技巧和手段进行改进最后开发出一种与 Paxos 明显不同的东西这就导致最终开发出来的程序建立在一个未经证明的协议之上。也正因为如此人们开始寻找新的一致性算法寻找的结果也就是本章介绍的重点 Raft 协议。
Raft 算法是一种用于管理复制日志的一致性算法其功能与 Paxos 算法相同类似但其算法结构和 Paxos 算法不同在设计 Raft 算法时设计者就将易于理解作为其目标之一这使得 Raft 算法更易于构建实际的系统大幅度减少了工程化的工作量也方便开发者此基础上进行扩展。虽然 Raft 论文已经很好理解但是本章并不打算直接翻译 Raft 论文而是尽可能通过示例介绍 Raft 协议如何处理各种不同的场景并且重点介绍 Raft 协议中的 Leader 选举和日志复制等方面的内容。
Leader 选举 Raft 协议的工作模式是一个 Leader 节点和多个 Follower 节点的模式也就是常说的 Leader - Follower 模式。在 Raft 协议中每个节点都维护了一个状态机该状态机有三种状态分别是 Leader 状态、 Follower 状态和 Candidate 状态在任意时刻集群中的任意一个节点都处于这三个状态之一。各个状态和转换条件如图2-1所示。 图2-1
在多数情况下集群中有一个 Leader 节点其他节点都处于 Follower 状态下面简单介绍一下每个状态的节点负责的主要工作。
Leader 节点负责处理所有客户端的请求当接收到客户端的写入请求时 Leader 节点会在本地追加一条相应的日志然后将其封装成消息发送到集群中其他的 Follower 节点。当 Follower 节点收到该消息时会对其进行响应。如果集群中多数超过半数节点都已收到该请求对应的日志记录时则 Leader 节点认为该条日志记录已提交committed可以向客户端返回响应。Leader 还会处理客户端的只读请求其中涉及一个简单的优化后面介绍具体实现时再进行详细介绍。Leader 节点的另一项工作是定期向集群中的 Follower 节点发送心跳消息这主要是为了防止集群中的其他 Follower 节点的选举计时器超时而触发新一轮选举。Follower 节点不会发送任何请求它们只是简单地响应来自 Leader 或者 Candidate 的请求 Follower 节点也不处理 Client 的请求而是将请求重定向给集群的 Leader 节点进行处理。Candidate 节点是由 Follower 节点转换而来的当 Follower 节点长时间没有收到 Leader 节点发送的心跳消息时则该节点的选举计时器就会过期同时会将自身状态转换成 Candidate 发起新一轮选举。选举的具体过程在下面详细描述。
了解了 Raft 协 议中节点的三种状态及各个状态下节点的主要行为之后我们通过一个示例介绍 Raft 协议中 Leader 选举的大致流程。为了方便描述我们假设当前集群中有三个节点A、B、C如图2-2所示。 图2-2
在 Raft 协议中有两个时间控制 Leader 选举发生其中一个是选举超时时间election timeout每个 Follower 节点在接收不到 Leader 节点的心跳消息之后并不会立即发起新一轮选举而是需要等待一段时间之后才切换成 Candidate 状态发起新一轮选举。这段等待时长就是这里所说的 election timeout后面介绍etcd的具体实现时会提到 Follower 节点等待的时长并不完全等于该配置。之所以这样设计主要是 Leader 节点发送的心跳消息可能因为瞬间的网络延迟或程序瞬间的卡顿而迟到或是丢失因此就触发新一轮选举是没有必要的。election timeout一般设置为 150ms300ms 之间的随机数。另一个超时时间是心跳超时时间heartbeat timeout也就是 Leader 节点向集群中其他 Follower 节点发送心跳消息的时间间隔。
集群启动时 Leader 选取
当集群初始化时所有节点都处于 Follower 的状态此时的集群中没有 Leader 节点。当 Follower 节点一段时间选举计时器超时内收不到 Leader 节点的心跳消息则认为 Leader 节点出现故障导致其任期Term过期 Follower 节点会转换成 Candidate 状态发起新一轮的选举。所谓 “任期Term”实际上就是一个全局的、连续递增的整数在 Raft 协议中每进行一次选举任期Term加一在每个节点中都会记录当前的任期值currentTerm。每一个任期都是从一次选举开始的在选举时会出现一个或者多个 Candidate 节点尝试成为 Leader 节点如果其中一个 Candidate 节点赢得选举则该节点就会切换为 Leader 状态并成为该任期的 Leader 节点直到该任期结束。
回到前面的示例中此时节点 A 由于长时间未收到 Leader 的心跳消息就会切换成为 Candidate 状态并发起选举节点A的选举计时器election timer已被重置。在选举过程中节点A首先会将自己的选票投给自己并会向集群中其他节点发送选举请求Request Vote以获取其选票如图2-31所示此时的节点B和节点C还都是处于Term0的任期之中且都是 Follower 状态均未投出Term1任期中的选票所以节点B和节点C在接收到节点A的选举请求后会将选票投给节点A另外节点B、C在收到节点A的选举请求的同时会将选举定时器重置这是为了防止一个任期中同时出现多个 Candidate 节点导致选举失败如图2-32所示。注意节点B和节点C也会递增自身记录的Term值。 图2-3
在节点 A 收到节点 B、C 的投票之后其收到了集群中超过半数的选票所以在 Term1这个任期中该集群的 Leader 节点就是节点A其他节点将切换成 Follower 状态如图2-4所示。另外需要读者了解的是集群中的节点除了记录当期任期号currentTerm还会记录在该任期中当前节点的投票结果VoteFor。 图2-4
继续前面的示例成为Term1任期的 Leader 节点之后节点A会定期向集群中的其他节点发送心跳消息如图2-51所示这样就可以防止节点B和节点C中的选举计时器election timer超时而触发新一轮的选举当节点B和节点C Follower 收到节点A的心跳消息之后会重置选举计时器如图2-52所示由此可见心跳超时时间heartbeat timeout需要远远小于选举超时时间election timeout。 图2-5
到这里读者可能会问如果有两个或两个以上节点的选举计时器同时过期则这些节点会同时由 Follower 状态切换成 Candidate 状态然后同时触发新一轮选举在该轮选举中每个 Candidate 节点获取的选票都不到半数无法选举出 Leader 节点那么 Raft 协议会如何处理呢这种情况确实存在假设集群中有4个节点其中节点A和节点B的选举计时器同时到期切换到 Candidate 状态并向集群中其他节点发出选举请求如图2-61所示。
这里假设节点A发出的选举请求先抵达节点C节点B发出的选举请求先抵达节点D如图2-62所示节点A和节点B除了得到自身的选票之外还分别得到了节点C和节点D投出的选票得票数都是2都没有超过半数。在这种情况下Term4这个任期会以选举失败结束随着时间的流逝当任意节点的选举计时器到期之后会再次发起新一轮的选举。前面提到过 election timeout 是在一个时间区间内取的随机数所以在配置合理的时候像上述情况多次出现的概率并不大。 图2-6
继续上面的示例这里假设节点A的选举计时器再次到期此次节点B、C、D 的选举计时器并未到期它会切换成 Candidate 状态并发起新一轮选举Term5如图2-71所示其中节点B虽然处于 Candidate 状态但是接收到Term值比自身记录的Term值大的请求时节点会切换成 Follower 状态并更新自身记录的Term值所以该示例中的节点B也会将选票投给节点A如图2-72所示。 图2-7
在获取集群中半数以上的选票并成为新任期Term5的 Leader 之后节点 A 会定期向集群中其他节点发送心跳消息当集群中其他节点收到 Leader 节点的心跳消息的时候会重置选举定时器当 Follower 节点每次收到心跳消息时都会重置选举定时器如图2-8所示。 图2-8
Lerder 节点宕机后重新选取
介绍完集群启动时的 Leader 选举流程之后下面分析 Leader 节点宕机之后重新选举的场景。继续上述4节点集群的示例在系统运行一段时间后集群当前的 Leader 节点A因为故障而宕机此时将不再有心跳消息发送到集群的其他 Follower 节点节点B、C、D一段时间后会有一个 Follower 节点的选举计时器最先超时这里假设节点D的选举计时器最先超时然后它将切换为 Candidate 状态并发起新一轮选举如图2-91所示。 图2-9
当节点B和节点C收到节点D的选举请求后会将其选票投给节点D由于节点A已经宕机没有参加此次选举也就无法进行投票但是在此轮选举中节点D依然获得了半数以上的选票故成为新任期Term6的 Leader 节点并开始向其他 Follower 节点发送心跳消息如图2-10所示。 图2-10
当节点A恢复之后会收到节点D发来的心跳消息该消息中携带的任期号Term6大于节点A当前记录的任期号Term5所以节点A会切换成 Follower 状态。在 Raft 协议中当某个节点接收到的消息所携带的任期号大于当前节点本身记录的任期号那么该节点会更新自身记录的任期号同时会切换为 Follower 状态并重置选举计时器这是 Raft 算法中所有节点都要遵循的一条准则。
最后请读者考虑一个场景如果集群中选出的 Leader 节点频繁崩溃或是其他原因导致选举频繁发生这会使整个集群中没有一个稳定的 Leader 节点这样客户端无法与集群中的 Leader 节点正常交互也就会导致整个集群无法正常工作。
Leader 选举是 Raft 算法中对时间要求较为严格的一个点一般要求整个集群中的时间满足如下不等式
广播时间 选举超时时间 平均故障间隔时间
在上述不等式中广播时间指的是从一个节点发送心跳消息到集群中的其他节点并接收响应的平均时间平均故障间隔时间就是对于一个节点而言两次故障之间的平均时间。为了保证整个 Raft 集群可用广播时间必须比选举超时时间小一个数量级这样 Leader 节点才能够发送稳定的心跳消息来重置其他 Follower 节点的选举计时器从而防止它们切换成 Candidate 状态触发新一轮选举。在前面的描述中也提到过选举超时时间是一个随机数通过这种随机的方式会使得多个 Candidate 节点瓜分选票的情况明显减少也就减少了选举耗时。另外选举超时时间应该比平均故障间隔时间小几个数量级这样 Leader 节点才能稳定存在整个集群才能稳定运行。当 Leader 节点崩溃之后整个集群会有大约相当于选举超时的时间不可用这种情况占比整个集群稳定运行的时间还是非常小的。
广播时间和平均故障间隔时间是由网络和服务器本身决定的但是选举超时时间是可以由我们自己调节的。一般情况下广播时间可以做到0.5ms50ms选举超时时间设置为200ms1s之间而大多数服务器的平均故障间隔时间都在几个月甚至更长很容易满足上述不等式的时间需求。
日志复制 通过上一节介绍的 Leader 选举过程集群中最终会选举出一个 Leader 节点而集群中剩余的其他节点将会成为 Follower 节点。
日志复制过程
日志复制过程如下
Leader 节点除了向 Follower 节点发送心跳消息还会处理客户端的请求并将客户端的更新操作以消息Append Entries 消息的形式发送到集群中所有的 Follower 节点。当 Follower 节点记录收到的这些消息之后会向 Leader 节点返回相应的响应消息。当 Leader 节点在收到半数以上的 Follower 节点的响应消息之后会对客户端的请求进行应答。最后 Leader 会提交客户端的更新操作该过程会发送 Append Entries 消息到 Follower 节点通知 Follower 节点该操作已经提交同时 Leader 节点和 Follower 节点也就可以将该操作应用到自己的状态机中。
上面这段描述仅仅是 Raft 协议中日志复制部分的大致流程下面我们依然通过一个示例描述该过程为了方便描述我们依然假设当前集群中有三个节点A、B、C其中A是 Leader 节点B、C是 Follower 节点此时有一个客户端发送了一个更新操作到集群如图 2-111所示。前面提到过集群中只有 Leader 节点才能处理客户端的更新操作这里假设客户端直接将请求发给了节点A。当收到客户端的请求时节点A会将该更新操作记录到本地的Log中如图2-112所示。 图2-11
之后节点A会向其他节点发送Append Entries消息其中记录了 Leader 节点最近接收到的请求日志如图2-121所示。集群中其他 Follower 节点收到该Append Entries消息之后会将该操作记录到本地的Log中并返回相应的响应消息如图2-122所示。 图2-12
当 Leader 节点收到半数以上的响应消息之后会认为集群中有半数以上的节点已经记录了该更新操作 Leader 节点会将该更新操作对应的日志记录设置为已提交committed并应用到自身的状态机中。同时 Leader 节点还会对客户端的请求做出响应如图 2-131所示。同时 Leader 节点也会向集群中的其他 Follower 节点发送消息通知它们该更新操作已经被提交 Follower 节点收到该消息之后才会将该更新操作应用到自己的状态机中如图2-132所示。 图2-13
nextIndex 和 matchIndex 数组
在上述示例的描述中我们可以看到集群中各个节点都会维护一个本地 Log 用于记录更新操作除此之外每个节点还会维护 commitIndex 和 lastApplied 两个值它们是本地Log 的索引值其中 commitIndex 表示的是当前节点已知的、最大的、已提交的日志索引值lastApplied 表示的是当前节点最后一条被应用到状态机中的日志索引值。当节点中的 commitIndex 值大于 lastApplied 值时会将 lastApplied 加1并将 lastApplied 对应的日志应用到其状态机中。
注当 commitIndex 值大于 lastApplied 值时说明日志被写入当前节点但未提交
在 Leader 节点中不仅需要知道自己的上述信息还需要了解集群中其他 Follower 节点的这些信息例如 Leader 节点需要了解每个 Follower 节点的日志复制到哪个位置从而决定下次发送 Append Entries 消息中包含哪些日志记录。为此 Leader 节点会维护 nextIndex[] 和 matchIndex[] 两个数组这两个数组中记录的都是日志索引值其代表含义如下
nextIndex[] 数组记录了需要发送给每个 Follower 节点的下一条日志的索引值matchIndex[] 表示记录了已经复制给每个 Follower 节点的最大的日志索引值
这里简单看一下 Leader 节点与某一个 Follower 节点复制日志时对应 nextIndex 和 matchIndex 值的变化Follower 节点中最后一条日志的索引值大于等于该 Follower 节点对应的 nextIndex 值那么通过 Append Entries 消息发送从 nextIndex 开始的所有日志。之后 Leader 节点会检测该 Follower 节点返回的相应响应如果成功则更新相应该 Follower 节点对应的 nextIndex 值和 matchIndex 值如果因为日志不一致而失败则减少 nextIndex 值重试。
示例
下面我们依然通过一个示例来说明 nextIndex[] 和 matchIndex[] 在日志复制过程中的作用假设集群现在有三个节点其中节点A是 Leader 节点Term1而 Follower 节点C因为宕机导致有一段时间未与 Leader 节点同步日志。此时节点C的 Log 中并不包含全部的已提交日志而只是节点A的 Log 的子集节点C故障排除后重新启动当前集群的状态如图2-14所示这里只关心 Log、nextIndex[]、matchIndex[]其他的细节省略另外需要注意的是图中的Term1表示的是日志发送时的任期号而非当前的任期号。 图2-14
A作为 Leader 节点记录了nextIndex[] 和 matchIndex[]所以知道应该向节点C发送哪些日志在本例中 Leader 节点在下次发送 Append Entries 消息时会携带 Index2 的消息这里为了描述简单每条消息只携带单条日志 Raft 协议采用批量发送的方式这样效率更高如图2-151所示。当节点C收到 Append Entries 消息后会将日志记录到本地 Log 中然后向 Leader 节点返回追加日志成功的响应当 Leader 节点收到响应之后会递增节点 C 对应的 nextIndex 和 matchIndex这样 Leader 节点就知道下次发送日志的位置了该过程如图2-152所示。
在上例中当 Leader 节点并未发生过切换所以 Leader 节点始终准确地知道节点C对应 nextIndex 值和 matchIndex 值。
如果在上述示例中在节点C故障恢复后节点A宕机后重启并且导致节点B成为新任期Term2的 Leader 节点则此时节点 B 并不知道旧 Leader 节点中记录的 nextIndex[] 和 matchIndex[] 信息所以新 Leader 节点会重置 nextIndex[] 和 matchIndex[]其中会将 nextIndex[] 全部重置为其自身 Log 的最后一条已提交日志的 Index 值而 matchIndex[] 全部重置为0如图2-16所示。 图2-15 图2-16
随后新任期中的 Leader 节点会向其他节点发送 Append Entries 消息如图2-171所示节点A已经拥有了当前 Leader 的全部日志记录所以会返回追加成功的响应并等待后续的日志而节点C并没有 Index2 和 Index3 两条日志所以返回追加日志失败的响应在收到该响应后 Leader 节点会将 nextIndex 前移如图2-172所示。 图2-17
然后新 Leader 节点会再次尝试发送 Append Entries 消息循环往复不断减小 nextIndex值直至节点C返回追加成功的响应之后就进入了正常追加消息记录的流程不再赘述。
Follower 节点投票
了解了 Log 日志及节点中基本的数据结构之后请读者回顾前面描述的选举过程其中 Follower 节点的投票过程并不像前面描述的那样简单先收到哪个 Candidate 节点的选举请求就将选票投给哪个 Candidate 节点 Follower 节点还需要比较该 Candidate 节点的日志记录与自身的日志记录拒绝那些日志没有自己新的 Candidate 节点发来的投票请求确保将选票投给包含了全部已提交committed日志记录的 Candidate 节点。这也就保证了已提交的日志记录不会丢失 Candidate 节点为了成为 Leader 节点必然会在选举过程中向集群中半数以上的节点发送选举请求因为已提交的日志记录必须存在集群中半数以上的节点中这也就意味着每一条已提交的日志记录肯定在这些接收到节点中的至少存在一份。也就是说记录全部已提交日志的节点和接收到 Candidate 节点的选举请求的节点必然存在交集如图2-18所示。 图2-18
如果 Candidate 节点上的日志记录与集群中大多数节点上的日志记录一样新那么其日志一定包含所有已经提交的日志记录也就可以获得这些节点的投票并成为 Leader 。
日志新旧比较策略
在比较两个节点的日志新旧时 Raft 协议通过比较两节点日志中的最后一条日志记录的索引值和任期号以决定谁的日志比较新首先会比较最后一条日志记录的任期号如果最后的日志记录的任期号不同那么任期号大的日志记录比较新如果最后一条日志记录的任期号相同那么日志索引较大的比较新。
这里只是大概介绍一下 Raft 协议的流程和节点使用的各种数据结构读者需要了解的是 Raft 协议的工作原理如果对上述数据结构描述感到困惑在后面介绍 etcd-raft 模块时还会再次涉及这些数据结构到时候读者可以结合代码及这里的描述进一步进行分析。
注日志较旧的节点可能发生过宕机等故障导致当前节点可能存在与集群其他节点数据不一致问题所以不能担任 leader 节点
网络分区的场景 接下来我们来看一下 Raft 协议是如何处理网络分区情况的。
网络分区概念在一个集群中如果有部分节点的网络发生故障与集群中另一部分节点的连接中断就会出现网络分区如图2-19所示集群有A、B、C、D、E五个节点其中节点A、B相互之间网络连通节点C、D、E相互之间网络连通但是这两部分节点之间出现网络故障这就形成了网络分区。 图2-19
网络分区下 Leader 选举及日志复制
这里依然通过一个示例来说明 Raft 协议对网络分区场景的处理。假设集群中节点 A 是 Leader 节点它会向其他四个节点发送 Append Entries 消息和心跳消息如图2-201所示。当出网络分区时节点A的心跳消息只有节点B才能收到而集群中的其他节点收不到如图2-202所示图中节点A发往节点C、D、E的消息由于网络分区并不会抵达节点C、D、E故未在图中画出。 图2-20
Leader 节点划分到节点较多的分区中
随着时间的流逝集群中与 Leader 节点隔离的网络分区C、D、E中会率先有一个节点的选举计时器election timer超时这里假设该节点是E此时的节点E就会切换成 Candidate 状态并发起下一轮选举如图2-211所示。由于网络分区当前集群中只有节点C、D能够收到节点E的选举请求这里假设节点C、D都会将选票投给节点E如图2-212所示。 图2-21
到此为止节点 E 在此次选举中收到了得到三票其中包括它本身的一票达到集群半数以上所以节点E成为新任期Term2的 Leader 节点如图2-22所示 图2-22
当网络故障被修复时上述的网络分区也就会消失此时节点 A任期 Term1 的 Leader 节点发送的心跳消息会被节点C、D、E接收到图2-22中虽然省略了这些由于网络分区而无法送达的心跳消息但实际上节点A依然认为自己是 Leader 节点在发送心跳消息时也会向节点C、D、E发送心跳消息但是这些心跳消息中携带的Term值小于当前C、D、E节点的Term值会被C、D、E节点忽略同时节点ETerm2任期的 Leader 节点发送的心跳消息会被节点 A、B 接收到图2-22 中同样省略了这些无法送达的心跳消息不同的是这些心跳消息携带的Term值大于当前A、B节点的Term值所以节点A、B会切换成 Follower 状态这样整个集群中的 Leader 节点依然是节点E。
注当 Follower 节点收到比自己Term小的节点的心跳消息时此心跳消息会被忽略
Leader 节点划分到节点较少的分区中
读者可能会问如果网络分区时 Leader 节点划分到节点较多的分区中如图2-23所示此时节点较少的分区中会有节点的选举计时器超时切换成 Candidate 状态并发起新一轮的选举。但是由于该分区中节点数不足半数所以无法选举出新的 Leader 节点。待一段时间之后该分区中又会出现某个节点的选举计时器超时会再次发起新一轮的选举循环往复从而导致不断发起选举Term号不断增长。
在 Raft 协议中对这种情况有一个优化当某个节点要发起选举之前需要先进入一个叫作 PreVote 的状态在该状态下节点会先尝试连接集群中的其他节点如果能够成功连接到半数以上的节点才能真正发起新一轮的选举。通过这种方式就可以解决上述的问题在后面分析 etcd-raft 模块时还会详细介绍其具体实现。 图2-23
回到前面的示例简单来介绍网络分区恢复时的相关处理。当网络分区恢复时集群中存在新旧两个 Leader 节点A和E其中节点E的Term值较高会成为整个集群中的 Leader 节点。但是由于之前的网络分区节点A、B的本地 Log 中可能存在未提交的日志记录如图2-241所示此时节点A和B会回滚未提交的日志记录并重新复制新 Leader 节点的日志如图2-24 2所示。 图2-24
这样在网络分区恢复之后整个集群的日志又会恢复一致。到此为止网络分区场景下的 Leader 选举及日志复制过程就介绍完了希望通过对这种特殊场景的介绍读者能够更深刻地了解 Raft 协议的工作原理。
网络分区下客户端与集群的交互及日志复制
另一个需要介绍的问题是网络分区场景下客户端与集群的交互过程及日志复制的过程。这里我们先简单介绍一下客户端如何与集群进行交互并找到集群的 Leader 节点。在前面提到过集群中只有 Leader 节点可以处理客户端发来的请求当 Follower 节点收到客户端的请求时也必须将 Leader 节点信息告知客户端然后由 Leader 节点处理其请求具体步骤如下
1当客户端初次连接到集群时会随机挑选一个服务器节点进行通信。
2如果客户端第一次挑选的节点不是 Leader 节点那么该节点会拒绝客户端的请求并且将它所知道的 Leader 节点的信息返回给客户端。
3当客户端连接到 Leader 节点之后即可发送消息进行交互。
4如果在交互过程中 Leader 节点宕机那么客户端的请求会超时客户端会再次随机挑选集群中的节点并从步骤1重新开始执行。
注未发生网络分区时客户端把请求直接发送到 Leader 节点
网络未分区客户端与集群的交互及日志复制
这里依然通过一个示例来介绍整个过程假设集群依然有五个节点在未发生网络分区时节点A为集群的 Leader 节点此时的客户端请求会发送到节点A经过前面描述的日志复制过程后节点A也会向客户端返回响应与如图2-251和2所示。 图2-25
网络分区客户端与集群的交互及日志复制
当节点A、B与节点C、D、E之间发生网络分区之后客户端发往节点 A的请求将会超时这主要是因为节点A无法将请求发送到集群中超过半数的节点上该请求相应的日志记录也就无法提交从而导致无法给客户端返回相应的响应该过程如图2-261和2所示。
注Leader 节点在收到客户端请求后会将请求发送到集群中的 Follower 节点只有在收到半数以上 Follower 节点的响应后Leader 节点才会给客户端相应的响应 图2-26
前面已经介绍了网络分区之后的 Leader 选举过程这里不再赘述该示例中假设节点E被选举为新任期Term2的 Leader 节点。当请求超时之后客户端会重新随机选择一个节点并获取新 Leader 节点的信息客户端最终会连接到节点E并发送请求而该网络分区中有超过半数的节点请求对应的日志记录可以提交所以客户端的请求不会再次出现超时之后客户端会一直与节点E进行交互直至下次请求超时。上述过程的如图2-2714所示。 图2-27 图2-27续
在 Raft 协议的论文中还给出了另一种 proxy 的方案假设客户端连接到集群中的某个 Follower 节点该 Follower 节点会将客户端发送的所有请求转发给 Leader 节点进行处理当 Leader 节点响应 Follower 节点之后再由 Follower 节点响应客户端。当出现请求超时的情况时客户端同样需要随机选择新的节点进行连接。
日志压缩与快照 通过前面章节的描述可知随着客户端与集群不断地交互每个节点上的日志记录会不断增加但是服务器的空间都是有限的日志量不能无限制地增长。另外在节点重启时会重放日志记录如果日志记录过多则需要花费较长的时间完成重放操作。这就需要压缩和清除机制来减少日志量从而避免上述情况。
定期生成快照是最常见也是最简单的压缩方法。在创建快照文件时会将整个节点的状态进行序列化然后写入稳定的持久化存储中这样在该快照文件之前的日志记录就可以全部丢弃了。例如集群中变量 a 的值为100客户端发送了一个更新请求将变量 a 更新为13经过前面描述的日志复制过程之后该请求对应的日志记录最终被提交并应用到集群中的每个节点中。此时每个节点中维护的变量 a 都是 13而 a13 这条日志记录就无须继续保留。在 ZooKeeper、Chubby 和 etcd 中都有类似上述的快照处理逻辑这里只是介绍创建快照文件和压缩日志的基本逻辑在后面的章节会具体介绍其实现。
在快照中除了节点当前的数据状态还包含了其最后一条日志记录的任期号和索引号如图2-28所示该快照包含了6条日志记录在快照的元数据中记录了第6条日志记录的任期号和索引号在生成快照文件之后即可将16条日志记录丢弃了。 图2-28
一般情况下集群中的每个节点都会自己独立、定时地创建快照在其状态恢复时都会使用自己本地最新的快照数据。如果 Follower 节点长时间宕机或是刚刚加入集群的新节点就有可能导致其日志记录远远落后于当前的 Leader 节点与此同时 Leader 节点中陈旧的日志记录已被删除了。在这种场景下为了将该 Follower 节点恢复到正确的状态 Leader 节点会将快照发送给该 Follower 节点 Follower 节点会使用该快照数据进行状态恢复。当 Leader 节点需要向 Follower 节点发送快照时会发送一种特殊的消息类型快照消息。etcd 的网络层为了高效地传输消息会将快照的发送与普通消息Append Entries消息、心跳消息等的发送分开在不同的消息通道中完成在后面介绍 etcd 网络层时会详细介绍。
当 Follower 节点接收到该快照消息时必须决定如何处理已存在的日志记录在快照中之所以保留前面介绍的一些元数据其作用之一就是为了在 Follower 节点收到快照之后进行一致性检查。一般情况下快照已包含了该 Follower 节点中不存在的日志记录此时 Follower 节点直接丢弃其所有的日志记录因为这些日志最终会被 Leader 传递来的快照所代替。如果 Follower 节点接收到的快照只包含了自己本地日志的一部分那么被该快照所包含的全部日志记录会被全部删除但是快照之后的日志则会保留。
有的读者可能会考虑过另一种替代方案即只有 Leader 节点创建快照然后发送给所有的 Follower 节点。但是该方案有几个缺点首先就是快照数据会比较大并且发送快照数据是比较浪费网络带宽的也比较耗时这显然比 Follower 节点从本地直接加载要耗时很多其次就是 Leader 的实现会更加复杂。
在 Raft 协议中每个节点都会创建快照所以创建快照的时机决定了快照的性能。如果创建快照过于频繁那么就会消耗大量的资源导致每个节点的性能下降如果创建快照的频率过低那么两次创建快照之间积累的日志记录会比较多快照就无法为节点节约内存等资源。所以我们要在两者之间进行权衡常见的策略是当日志记录个数达到一个固定阈值的时候就触发一次创建快照的操作生成相应的快照文件我们可以通过调节该阈值来控制创建快照的频率。
其他技术点 linearizable 语义、只读请求、PreVote 状态、Leader 节点转移都是针对 Raft 协议的一些优化
linearizable 语义
Raft 协议的目标是实现 linearizable 语义即在客户端每次向集群发送一次读请求时该请求只会被执行一次。但是根据前面的描述客户端虽然只是想发送一次请求但是集群可能多次收到该请求。例如 Leader 节点负责提交日志记录通知了其他 Follower 节点并将日志记录应用到了其状态机中但是在向客户端返回相应的响应消息之前宕机了那么客户端会连接到新的 Leader 节点并重发对应的请求这就导致该请求再次被执行。或者网络出现故障导致请求丢失或是延迟如图2-29所示就会导致同一条请求被执行两次。 图2-29
通过序列号去重常见的解决方案就是客户端对于每个请求都产生一个唯一的序列号然后由服务端为每个客户端维护一个Session并对每个请求进行去重。当服务端接收到一个请求时会检测其序列号如果该请求已经被执行过了那么就立即返回结果而不会重新执行。
linearizable 语义目标在客户端每次向集群发送一次读请求时该请求只会被执行一次
只读请求
在介绍 Raft 协议的日志复制时提到请求对应的日志记录会写入 Leader 节点的本地 Log 中并完成复制到集群中半数以上的节点之后才会真正提交并应用到状态机中。为了提高只读请求的性能我们可以考虑直接处理而不记录对应的日志记录也不会经过日志复制的过程。但是在不增加任何限制的情况下这么做可能会冒着返回脏数据的风险因为 Leader 节点响应客户端请求时可能已经故障或是已经发生了网络分区集群已经选出了新的 Leader 节点但是旧的 Leader 节点自身还不知道。
为了不返回脏数据同时为了保证 linearizability 语义 Raft 协议在处理只读请求时除了直接读取 Leader 节点对应的状态信息还需要使用额外的措施。
处理只读请求的大致逻辑如下
1 Leader 节点必须有关于已提交日志的最新信息虽然在节点刚刚赢得选举成为 Leader 时拥有所有已经被提交的日志记录但是在其任期刚开始时它可能不知道哪些是已经被提交的日志。为了明确这些信息它会在其任期开始时提交一条空日志记录这样上一个任期中的所有日志都会被提交。
2 Leader 节点会记录该只读请求对应的编号作为 readIndex当 Leader 节点的提交位置commitIndex达到或是超过该位置之后即可响应该只读请求。
3 Leader 节点在处理只读的请求之前必须检查集群中是否有新的 Leader 节点自己是否已经被作废如果该节点已经不再是集群的 Leader 节点则该节点中日志记录就可能包含脏数据必须由新 Leader 节点来处理此次只读请求。 Raft 协议中通过让 Leader 节点在处理只读请求之前先和集群中的半数以上的节点交换一次心跳消息来解决这个问题。如果该 Leader 节点可以与集群中半数以上的节点交换一次心跳则表示该 Leader 节点依然为该集群最新的 Leader 节点。这样readIndex 值也就是整个集群中所有节点所能看到的最大提交位置commitIndex。
4随着日志记录的不断提交 Leader 节点的提交位置commitIndex最终会超过上述 readIndex此时 Leader 就可以响应客户端的只读请求了。 只读请求目标服务端直接处理只读请求而不记录对应的日志以提高只读请求的性能 这里简单介绍一下 linearizability 的含义线性化linearizability是分布式系统中比较重要的概念。linearizability 是对单对象上的单个操作的一种顺序保证它提供了对于同一个对象的一系列读写操作都是按照实时时间排序的保证。简单地说linearizability 保证对于一个对象的写操作一旦完成需要立即被后续的读操作看到即读操作一定是读到该对象的最新的值。从该角度来看linearizability 与 atomic consistency 是同义词也是CAP原则中的Cconsistency。另外并且 linearizability 是可组合的如果系统中每个对象的操作都是 linearizable则系统中所有操作是 linearizable。
PreVote 状态
在前面介绍网络分区场景时提到在节点数不足集群半数的网络分区中始终没有节点可以获取半数以上的选票成为 Leader 节点所以每过一段时间就有节点的选举计时器超时并切换成 Candidate 状态发起新一轮的选举。
这虽然不影响集群的使用在节点超过半数的网络分区中已经成功选举出 Leader 节点并对外提供服务但是会导致不断发起选举的节点的 Term 号不断增长。当网络分区结束时由于该节点的 Term 值高于集群当前的 Leader 节点的 Term 值就会迫使当前 Leader 节点发生状态切换并重新发起一次新的选举。
Raft 协议为了优化此次无意义的选举给节点添加了一个 PreVote 的状态当某个节点要发起选举之前需要先进入 PreVote 的状态。在 PreVote 状态下的节点会先尝试连接集群中的其他节点如果能够成功连接到半数以上的节点才能真正切换成 Candidate 状态并发起新一轮的选举。在后面分析etcd-raft模块时我们可以看到相关实现。 PreVote 目标避免无效选举 Leader 节点转移
通过前面的介绍我们知道 Leader 节点在整个集群中的作用至关重要。但是在有的场景中需要对 Leader 节点进行手动切换。例如我们要将 Leader 节点所在的机器进行系统升级或是停机维护等。此时我们可能需要集群中指定的 Follower 节点成为新的 Leader 节点继续对外提供服务。在原 Leader 节点所在的机器维护结束之后我们可能还需要将 Leader 节点再转移到该机器上可能该机器的配置等条件优于集群中的其他机器更适合做 Leader 节点。这种场景下就需要特定的 Follower 节点成为下一任期的 Leader 节点。根据前面介绍的 Leader 选举过程我们知道Leader 节点的选举在本质上是随机的无法满足上述需求。
Raft 协议给出的方案是首先暂停接收客户端请求让一个指定的 Follower 节点的本地日志与当前的 Leader 节点完全同步在完成同步之后该特定的 Follower 节点立刻发起新一轮的选举。由于其Term值较大原 Leader 节点自然被其替换下来。该方案需要控制好选举计时器及特定 Follower 与 Leader 节点同步的时间防止其他 Follower 节点在这段时间内发起选举当然发生这种情况的概率还是比较低的。 Leader 节点转移目标手动切换 Leader 节点和 Follower 节点 在实现 Raft 协议的时候除了上面提到的扩展点和优化点在 Raft 大论文中还提到一些其他的相关内容非常值得参考。笔者也极力推荐读者亲自阅读该论文毕竟本书篇幅有限无法将其内容逐一介绍。
本章小结 本章主要介绍了 Raft 协议的基本概念和基本流程其中包括 Leader 节点的选举、节点间的复制、日志的压缩、快照的生成以及网络分区等场景的介绍最后还介绍了在实现 Raft 协议时可能会遇到的特殊问题的相关方案。在本章中介绍每个流程时都是通过示例方式进行描述的希望读者在阅读完本章后对 Raft 协议有一个初步的了解为后面分析etcd-raft模块打下基础。在后面分析 etcd-raft 模块时也建议读者回顾本章 Raft 算法的实例了解 etcd 实现与 Raft 算法的细微差异。
