Raft基本理论

阳光穿透心脏的1/2处 2022-05-29 13:29 168阅读 0赞

本文以问答的方式，总结Raft相关知识。  
所有信息来源于Raft论文

# 第一章 #

## 1.为什么要寻找一个新的一致性算法？ ##

Unfortunately, Paxos has two significant drawbacks.  
The first drawback is that Paxos is exceptionally difficult to understand.  
The second problem with Paxos is that it does not provide a good foundation for building practical implementations.  
（1）paxos算法比较难理解，即便有很多人尝试着用更容易理解的方式去解释它。education  
（2）paxos没有为实际实现打好基础，有许多细节问题没有公布，或者业内没有形成一致意见，以致于在实际构建和部署时，需要做复杂的变更。practice  
Because of these problems, we concluded that Paxos does not provide a good foundation either  
for system building or for education.  
Given the importance of consensus in large-scale software systems, we decided to see if we could design an alternative consensus algorithm with better properties than Paxos. Raft is the result of that experiment.

# 第二章 #

## 1.通常使用什么方法来解决分布式系统的容错问题？举例？ ##

复制状态机  
Replicated state machines are used to solve a variety of fault tolerance problems in distributed systems, as described in Section 2.2.  
Many large-scale storage systems that have a single cluster leader, such as GFS \[30\], HDFS \[105\], and RAMCloud \[90\], use this approach.

## 2.复制状态机如何实现？架构？ ##

使用replicated log实现  
Replicated state machines are typically implemented using a replicated log, as shown in Figure 2.1.  
![这里写图片描述][70]  
集群中的每台服务器上都有复制状态机，每个状态机按同样的顺序执行一串相同的命令，从而每个状态机的状态也是一致的。  
一致性模块接收客户端命令并将其写入到日志中，每个服务器中的一致性模块互相通信，保证每台服务器上写入日志的命令内容和顺序相同

# 第三章 Basic Raft algorithm #

## 1.如何实现易懂性？ ##

（1）将单个复杂的问题分解为若干可以独立解决，解释，理解的问题。–问题分解  
we divided problems into separate pieces that could be solved, explained, and understood relatively independently.  
（2）第二种方法是通过减少需要考虑的情况的数量来简化状态空间，使系统更加连贯并尽可能消除不确定性。–状态简化  
Our second approach was to simplify the state space by reducing the number of states to consider, making the system more coherent and eliminating nondeterminism where possible.

## 2.简单说一下Raft。概述。 ##

Raft实现一致性的方法是：首先选出一个server作为leader，让leader来全权负责replicate log的管理（利用leader来简化replicated log的管理）。leader从客户端接收日志条目，复制到其他服务器，并且告诉其他服务器什么时候将日志应用到状态机上才是安全的。数据流动的方向只会是从leader流向其他服务器。  
leader在决定将日志条目放在日志的哪个位置的时候，不需要和其他服务器商议。

有了在系统中使用leader的这个前提，Raft将一致性问题分解为三个相对独立的子问题：  
（1）Leader election  
（2）Log replication  
（3）Safety。（leader变更时的安全性）

### （1）leader election ————————- term ###

At any given time each server is in one of three states: leader, follower, or candidate.  
![这里写图片描述][70 1]  
通常只有一个leader，其余的都是follower。  
leader处理所有客户端请求，follower将来自客户端的请求转发到leader。  
follwoer只响应来自leader和candidate的请求。（passive）  
candidate用来选举新的leader。

Raft将时间分成任意长度的任期（term，连续的整数编号），每个term开始的时候都要进行选举（elect），一个或多个候选者参与选举，试图成为leader，赢得选举的server在这个任期的剩余时间内作为leader。某些情况下可能无法成功选出一个leader，所以一个term内最多只有一个leader。  
每个server都保存了当前term的数值，server之间通信时，会带上term的信息。

我们选择在Raft中将通信结构化为RPC，以简化其通信模式。  
server使用RPC进行通信，基本的一致性算法只需要两种RPC（RequestVote RPC和AppendEntries RPC），后续将要介绍的leader的资格转换会使用其他的RPC。  
RequestVote RPC：候选者在elect期间发出  
AppendEntries RPC：leader发出的，用于复制日志条目，和提供心跳机制。

Raft uses a heartbeat mechanism to trigger leader election.  
Raft使用心跳机制触发leader选举：  
server刚启动时，先以follower作为开始。leader会周期性的发送心跳信息到各个follower，维护自己作为leader的地位。如果follower从leader或者candidate收到RPC，则保持follower状态。如果follower在election timeout时间内没有收到心跳信息，则认为没有leader了，follower发起新的选举。

follower发起选举的过程：  
增加当前term –> 转换为candidate状态 –> 投票给自己 –> 发送RequestVote RPC给集群中其他服务器，会有三种结果：  
（a）赢得选举，成为leader。（相同的term内获得集群中多数选票）（在同一个term中，每个服务器最多只会投票给一个candidate，先收到谁的投票请求，就投票给谁。这保证了在同一个term中最多只有一个leader。当candidate成为leader之后会向集群中其他server发送信息，确保自己的leader地位，避免其他server发起新的选举。）safety  
（b）收到其他server以leader身份发来的信息，转变为follower。如果收到其他server作为leader发来的AppendEntries RPC信息，该信息中包含的term不小于自己的term，则承认其他server的leader地位，并转换为follower状态。如果收到的RPC信息中的term小于自己的term，则拒绝该RPC信息，保持candidate状态。（收到其他candidate发来的term大于自己的RequestVote RPC信息应该也会转变为follower吧？？？否则新一轮竞选的时候，还是无法选出leader）  
（c）在election timeout时间内，集群中没有选出新的leader。多个server同时转变为candidate发起竞选，可能没有一个candidate能赢得多数选票，则没有新的leader选出来。这种情况下，每个candidate在elect timeout之后增加自己的term，发起新一轮的竞选。（如果没有额外的机制，这种分裂选票导致的无法选出leader的情况可能会不断重复，解决办法是，每个candidate的elect timeout不相同，取150-300ms中的随机数，这样每个candidate超时的时间不相同，发起竞选的时间就会不同，最先发起竞选的很可能成为leader，在其他candidate超时之前，他就已经赢得选举并且发送心跳信息了。网络通信耗时一般在1ms以内，随机数之间的时间差距，提供了充足的选举时间。分裂选票的情况很少出现，并且能快速解决。）（曾经尝试使用给每个server指定一个rank的方式来减少split vote，但是遇到了很多问题，没成功。）We used randomization to simplify the Raft leader election algorithm.（看到的Raft资料中有考虑使用rank的方式）

### （2）Log replication ————— term & index ###

leader选出来之后，就开始处理客户端请求，客户端请求中包含需要执行的命令，leader将命令作为日志条目追加到日志中，然后并行发送给集群中的其他服务器（AppendEntries RPC），日志被安全的复制到其他服务器之后（判断条件？超过半数响应），leader将日志应用到状态机上，然后返回结果给客户端。如果有follower crash，或者运行慢，或者网络丢包的情况，leader会不断发送日志条目直到所有follower都存储了所有的日志条目。  
每个日志条目都包含客户端命令command，term，index。  
index用来确定日志条目在日志中的位置。  
log中的term用来检测不同server上的日志是否一致，以及确保一些算法的特性。

committed：A log entry is committed once the leader that created the entry has replicated it on a majority of the servers (e.g., entry 7 in Figure 3.5).多数服务器接收到日志之后，日志被提交，之前的所有日志也都提交。（safety）  
leader会记录已经提交了的日志条目的highest index，这个index也会包含在后续将要发送给follower的AppendEntries RPC（包括心跳）中，follower得知该日志条目被提交之后，将该日志条目应用到状态机。（何时应用日志是安全的）

Raft的日志机制：  
（1）不同server上的日志条目，如果term和index相同，则该条目中保存的命令也肯定相同。（leader在给定的term和index的位置，最多创建一个条目，并且日志条目的位置（term&index）是不会改变的）—-当前的  
（2）不同server上的日志条目，如果term和index相同，则该日志条目之前的所有的日志条目都相同。（AppendEntries RPC一致性检测，leader在发送AppendEntries RPC时，会将前一个entry的term和index也包含在其中。如果follower在自己的日志中没有找到对应的前一个entry，则拒绝新的entry。通过归纳法得知，如果leader发送的AppendEntries RPC返回成功的结果，则leader可以知道，截止到最新的entry，follower的日志和自己的日志是相同的。）—之前的

leader的crash可能导致leader和follower之间日志的不一致，旧的leader可能有一些日志条目没有复制出去。follower的日志可能比leader少，也可能比leader多。  
（1）follower的日志比leader少：  
（2）follower的日志比leader多：  
（3）以上两种都有  
![这里写图片描述][70 2]

Raft如何让follower的日志和leader的相同？引入match index的概念。  
Raft强制让follower的日志与leader相同，leader以此来解决日志不一致的问题。这就意味着follower中与leader不一致的日志会被覆盖。通过在leader的竞选过程中添加一些限制，可以保证这是安全的。（什么限制？后面safety部分详细描述。）  
leader首先在follower的日志中找到一个位置点match index，在这个点之前，leader和follower的日志相同，然后在follower中删除该点之后的所有的日志条目，然后将leader中该点之后的所有日志条目发送给follower，在此过程中AppendEntries RPC的一致性检查也会起作用，以此来保证leader和follower的日志相同。  
leader中会维护每个follower的nextindex，nextindex是leader将要发送给follower的下个日志条目的index。leader刚被选举出来的时候，会将它自己的日志中最后一个index的下一个index初始化为所有follower的nextindex（nextindex=latest index+1），然后对于每一个follower，leader向其发送AppendEntries时，根据日志一致性检测机制，如果follower的日志和leader的日志不同（检测term和index，follower.latest index=leader.follower.nextindex-1），则consistency check会失败，此时leader将该follower的nextindex减小，并且重新发送AppendEntries，一直重复这个过程，直到consistency check成功。当follower的日志和leader中记录的nextindex能够相匹配（nextindex=matchindex+1），然后follower中该index（matchindex）之后的日志被删除，leader发送follower缺少的日志，follower和leader中的日志最终达到一致。  
一些优化手段，可能没有必要，因为failure不会经常发生，也不会有那么多不一致的日志：  
（1）节省带宽：在leader找到与follower的matchindex之前，可以不发送包含真正log entry的RPC，只发送包含心跳信息的RPC（应该包含term和index），节省带宽。找到了matchindex之后，再发送log entry。  
（2）减少寻找matchindex时AppendEntries RPC被拒绝的次数：  
a.leader使用二分查找的方式，寻找follower日志中第一个与之不同的index  
b.follower在拒绝AppendEntries RPC时，将其日志中当前term的第一个index返回给leader。当有多个term的日志不一致时，每个term只需要一次比较，而不是将term中的每个log entry都进行比较。  
leader不需要执行特别的动作去保持日志的一致性，它永远不会删除或者覆盖自己日志中的条目。

Raft的日志机制保持了不同server之间日志的连贯性，这个机制不仅简化了系统的行为，使系统的行为可预测，同时它也是保证安全性的一个重要组成部分。  
在多数服务器正常运行的条件下，Raft就可以接受，复制，应用新的log entry。每个entry只需要一轮RPC即可复制到多数server上，单个慢的follower不影响整体性能。  
日志复制算法比较容易实现，因为leader不会为了赶进度而在单个AppendEntries request中发送超过一个entry。有的算法需要通过网络发送整个日志，真正实现需要很多优化，负担比较大。

（3）Safety ——-如何选出包含所有已提交日志的server作为leader  
可能会出现什么问题？  
之前的部分介绍了Raft如何选择leader和复制日志，但是没有充分的保证每个状态机按照同样的顺序执行同样的命令。比如，一个follower落后leader很多，leader很多提交了的日志并没有复制到该follower上，但是该follower可能会被选为leader，然后覆盖掉原来的leader上面那些已经被提交的日志，这可能导致不同的状态机执行了不同的命令。新的leader缺少部分已提交的日志。

如何解决这个问题？思路。  
Raft算法对于leader的选举添加了一些限制，以保证新的leader的日志中包含所有之前已经提交的日志。每次选新的leader，term的值都会增加，也就是说，新的leader的日志中包含所有以前的term中已经提交了的日志。

如何实现？  
其他算法的实现：不包含所有已提交的日志的candidate也能被选为leader，在选举的过程中或者稍后，通过额外的机制确定缺失的日志，并传输到新选出的leader上面。增加了需要考虑的机制及复杂性。  
Raft的实现：使用一个简单的方法，保证被选出来的leader，包含之前term中已经提交的所有entry。由此，这意味着日志流动的方向只有一个，即从leader流向follower。leader不需要删除或覆盖自己的日志。  
Raft在选举的过程中避免了不包含全部已提交日志的candidate成为leader。Candidate只有获得集群中的多数voter的选票才能成为leader，在这些voter至少会有一个包含所有已提交的entry。如果Candidate的日志，至少和集群中多数voter的日志一样新（与集群中多数server中的日志相比，相同或者更新），则其必然包含所有已提交了的日志信息。

具体实现方式：  
Candidate发送的RequestVote RPC中包含其log的信息（已提交日志的term & index ，不是现有日志的term & index），如果voter中的日志比candidate中的更新，则voter不会投票给该candidate。——-一定要注意，是比较已提交日志的term和index，比较未提交的日志没什么意义。  
如何比较两个日志谁更新？最后一个日志条目的term和index。先比较term，再比较index。  
Raft determines which of two logs is more up-to-date by comparing the index and term of the  
last entries in the logs.

复制到多数server上的entry就一定提交了？  
一个entry，即便被复制到了集群中的多数机器上，但是如果leader在提交之前宕机，该entry仍有可能被删除或覆盖。  
换句话说，新term中选出来的leader，无法判断出上一个term中的entry是否已经提交，即便该entry已经复制到了集群中的多数机器上。  
图3.7.举例说明。（此情况比较复杂，但是解释的很清楚，是必须要考虑到的情况。）  
![这里写图片描述][70 3]  
如何解决？  
Raft不会使用计算副本数量的方式来提交前面term中的日志。只有当前term中的日志，才采用计算副本数量的方式来提交。—-以前的term中的日志不会直接提交，会间接提交。  
一旦当前term中的entry提交了，由于日志匹配属性（Log Matching Property）之前term中的entry也就被间接提交了。  
有时候，leader可以安全的判断出entry已经被提交了，但是为了简单起见，Raft采取更保守的方法。

安全性证明过程：  
根据上面给出的完整的Raft算法，可以更详细的证明Leader Completeness Property成立。（好麻烦）  
先假设Leader Completeness Property不成立，然后证明这是矛盾的。  
假设在term T中，leader提交了一个entry，但是这个entry没有被复制到后来的Term U选出的leader中。  
1.由于leader不会删除或者覆盖自己的日志，故在leaderU竞选leader时，其日志中没有该entry。  
2.leaderT将该entry复制到了集群中的多数server上。leaderU获得了集群中多数server的投票。因此，至少有一个server，既保存了leaderT提交的entry，又投票给了leaderU。—-这个voter是造成矛盾的关键点。  
3.这个voter在投票给leaderU之前，必然已经接收了leaderT发来的提交了的entry。否则就是拒绝了leaderT发来的AppendEntries request（此时它的term大于T）。  
4.voter依旧存储了这个entry，因为介于U和T之间的每一个leader都存储了该entry。leader不会删除或覆盖自己的日志。follower只删除与leader相冲突的日志。  
5.voter投票给了leaderU ，所以leaderU的日志和voter一样内保持最新。这导致两个矛盾。  
6.首先，如果voter和leaderU有相同的term，那么leaderU的日志至少和voter的一样新，所以leaderU的日志包含了voter的log中的每个entry。这是矛盾的，因为我们假设voter包含了已经提交的entry，但是leaderU不包含。  
7.Otherwise, leaderU’s last log term must have been larger than the voter’s. Moreover, it was  
larger than T, since the voter’s last log term was at least T (it contains the committed entry  
from term T). The earlier leader that created leaderU’s last log entry must have contained the  
committed entry in its log (by assumption). Then, by the Log Matching Property, leaderU’s  
log must also contain the committed entry, which is a contradiction.  
否则，leaderU的最后一个日志term必须大于voter的日志term。 此外，leaderU的term大于T，因为voter的最后一个日志term至少是T（它包含了来自termT的承诺条目）。 创建leaderU最后一个日志条目的之前的leader必须在其日志中包含这个已提交的条目（通过假设）。 然后，通过日志匹配属性，leaderU的日志也必须包含这个已提交的条目，这是一个矛盾。  
8.这就形成了矛盾。 因此，term大于T的leader，必然包含了termT期间所有提交的entry。  
9.日志匹配属性保证了后来的leader必然包含之前间接提交的日志条目。

这就证明了leader完整属性，这也证明了状态机安全属性（如果一个server按照给的顺序应用了log正的entry，则其他server会以同样的顺序执行日志。每个server上的日志是相同的。）  
========================回头再仔细看证明过程===============================

## 3.7 Follower and candidate crashes ##

follower和candidate的crash比leader的crash处理起来要简单很多，它俩采用相同的处理方式。  
follower和candidate crash之后，发送给他们的RequestVote和AppendEntries RPC信息会返回失败的结果，Raft会不定期的重试发送这些信息，直到follower/candidate重启，RPC返回成功的结果。  
如果server在接收到RPC之后，还没来得及响应就crash了，则在server重启之后，会再次收到相同的RPC，但是这不会产生什么危害。Raft RPCs have the same effect if repeated, so this causes no harm.如果follower收到与日志中已经存在的entry相同的AppendEntries request，会忽略这些request中的entry。

## 3.8 Persisted state and server restarts ##

Raft服务器必须将足够的信息持久化到稳定的存储器中，以便安全地重新启动服务器。（举例：term，vote， entry）  
特别是term和vote，这是为了防止在一个term内投票两次（vote），或者新的leader产生的日志entry将以前的leader产生的log entry替换掉。  
每个server中的log entry在提交之前必须持久化，避免server重启后，提交了的entry丢失或者变为未提交的状态。

其他的信息可以重新创建，重启不会引起问题。  
举例：commit index，即便所有server同时重启也不会有问题。服务器重启先将commit index初始化为0，在leader选出之后提交新的log entry时，commit index会变成真实的值，并且将该值传播到所有follower。（应该可以读取自己的日志，获得真正的commit index）

状态机可以是易失性的或持久性的。  
易失性状态机：最新快照+重新应用log entry  
持久性状态机：记录last applied index，重启之后应用该index之后的entry

如果服务器所有的持久化状态都丢失了，则无法以其先前的身份安全地重新加入群集。 这种服务器通常可以通过调用集群成员资格更改的方式，以新的身份重新添加到集群中。 但是，集群中的多数服务器丢失了持久化状态，则已经提交的日志条目可能会丢失，集群成员资格更改的也无法进行。如果要系统继续运行，则系统管理员需要承认数据丢失的可能性。

## 3.9 Timing and availability ##

不管系统中的事件发生的是快还是慢，系统都不能产生不正确的结果。（安全性与时间无关）  
但是可用性与时间有关。举例：server间消息传递需要的时间，如果大于server crash的时间间隔，则无法选出可用的leader，没有leader，Raft无法正常工作。

在Raft的leader选举中，时间很重要。Raft能够选出并且保持一个稳定的leader的时间要求：  
broadcastTime << electionTimeout << MTBF  
broadcastTime：Server发送RPC并接受响应的时间，要比election timeout至少小一个数量级，以便leader能够可靠的发送心跳信息，防止follower开始新的选举。结合election timeout的随机方法，可以尽量避免split vote。  
electionTimeout ：超过该时间，如果follower没有收到心跳信息的话，则发起新的elect。当leader crash时，系统大概有electionTimeout的时间是不可用的。  
MTBF：单个server平均故障间隔时间

broadcastTime和MTBF都是与系统属性，只有election timeout是我们必须设定的。  
接收者需要将RPC中的信息持久化到存储上，所以broadcastTime大概在0.5-2ms，根据系统存储的性能而定。因此election timeout可以选择在10–500ms之间。MTBF一般为几个月或更长时间。

## 3.10 Leadership transfer extension （可选的扩展） ##

两种情况下需要用到leader转换：  
1.leader必须下台（重启维护或从集群中移除）。leader下台，会有election timeout的时间系统是不可用的，直到其他的server超时，发起新的选举并赢得选举。  
在下台之前，leader将其角色转移到其他server，可以尽量避免这段系统不可用的时间。  
2.其他server更适合作为leader。举例：负载高的服务器不适合作为leader。广域网中，主数据中心的服务区更适合作为leader以尽可能减少客户端和leader之间的网络延迟。（其他算法可能在选举阶段就选出了更合适的leader，但是Raft由于要选举包含最完整日志的server作为leader，被选举出来的可能不是最优的server。Raft的leader会不时的去检测follower中有没有更适合作为leader的server，并且将leader的角色转给该server，人工操作。）

详细的leadership transfer步骤：  
1.原leader停止接受客户端的新请求。  
2.原leader将所有已提交的log entry传输到目标server，保证原leader和目标server日志一致（正常的日志复制机制，没有其他特殊操作）。  
3.原leader向目标server发送一个TimeoutNow的请求，这个请求可以使目标server立即发起一轮新的选举，而不需要等待election timeout的时间。（目标server增加term的值，转换为candidate状态）  
这样基本能保证目标server在其他server election timeout之前就发起新的election并且成为leader。目标server发送给原leader的信息中也会包含新的term，使原leader下台。此时，leadership transfer完成。

如何保证transfer异常的情况下尽快恢复响应客户端请求？–只提供了思路，还没有真正去实现这个功能。  
如果leadership transfer这个操作在一个election timeout的时间内没有完成，则原leader终止此操作，并重新接受客户端请求，防止客户端请求被长期阻塞。如果目标server实际上已经成为leader，但是原leader依旧错误的终止了transfer的操作，则最坏的情况也就是多进行一次选举，然后就又可以响应客户端请求了。

## 3.11 Conclusion ##

本章解决了一致性相关的所有问题。Raft超越了single-decree Paxos中对于单一值实现一致性的机制，实现了不断增长的日志的一致性，这是建立复制状态机所必须的。它将所有节点达成一致的消息发送到其他服务器，让其他服务器知道log entry已经提交。Raft通过选择一个集群leader，由该leader单独做决定，并由leader向集群其他成员发送日志信息的方式，高效的，可行的实现了一致性。  
Raft仅使用少量机制来解决完全一致的问题。 例如，它只使用两个RPC（RequestVote和AppendEntries）。 创建一个紧凑的算法/实现并不是Raft的最直接的目标，相反，这是设计易懂性的结果，每一个机制都必须充分激活和解释。 我们发现冗余或曲折机制很难激发，所以它在设计过程中自然会被清除。  
对于不会影响大部分Raft部署的问题，我们没有在Raft中解决它，所以Raft中有的部分可能不够成熟（幼稚，比如leader选举还可以改进，但是在增加复杂性的同时并没有带来多少实际的好处），有的又比较保守（比如leader只能提交当前term下生成的日志）。为了让读者更容易理解，放弃了一些不成熟的优化手段。  
本章不可避免的会遗漏一些功能或优化，这些功能或优化在实践中非常有用。 随着实施者获得更多的Raft经验，他们将了解何时以及为什么某些附加功能可能会有用，并且他们可能需要在实际部署中实施这些功能。 在整个章节中，我们勾勒了一些我们认为不必要的可选扩展，但如果需要的话，这可能有助于指导实施者。 通过关注可理解性，我们希望为实施者根据他们的经验调整Raft提供坚实的基础。 由于Raft在我们的测试环境中工作，我们期望这些是简单直接的扩展，而不是根本性的变化。

# 第四章 Cluster membership changes #

在此之前，我们一直假定集群成员配置是不变的，但是在实际环境中，集群配置偶尔需要改变，比如踢除出问题的成员，或者添加新的成员。  
有两种解决办法：  
1.将集群中所有成员关闭，更改集群配置，然后重启集群。在集群关闭这段时间，整个集群不可用。  
2.新的server获取到某个成员的网络地址，以取代该集群成员。必须保证被替代的server不会再回来，否则系统的安全属性无法保证。  
这两种集群成员变更的方法都有很大缺陷。

如何解决这些问题？  
配置变更自动化，将其合并到Raft一致性算法中。只需要对基本的一致性算法进行一些扩展，同时成员变更的过程中，集群正常运行。

具体实现？  
AddServer RPC：将新的server添加到现有集群。  
RemoveServer RPC：将server从现有集群中移除。

## 4.1 Safety ##

为了防止配置变更时，针对相同的term选出两个leader的情况，不能使用一次添加或删除多个server的方式。同时添加或删除多个server造成集群选出多个leader的情况见下图：  
![这里写图片描述][70 4]  
Raft最初的也在设计如何解决一次添加多个server造成两个不相交的多数成员的办法。后来发现一个更简单的办法：一次只能添加或删除一个server，复杂的变更可以由一系列单个server的变更来实现。同时单server变更的方法也更容易理解。

每次添加或删除一个server，则旧的集群中的多数成员，和新的集群中的多数成员肯定有交集，以此来避免新旧集群被分裂成两个互相独立的多数派。

Cluster configurations are stored and communicated using special entries in the replicated log.（也就是上面提到的两种RPC）

leader收到添加或删除server的请求后，就将新的配置Cnew添加到自己的log中并使用普通的Raft日志复制机制复制该日志条目。Cnew中的server在接受到该log entry之后，配置立即生效（无需等待该entry提交，也就是说server始终使用接收到的最新的集群成员配置），Cnew中的多数派决定该log entry是否提交。  
Cnew的entry被提交后，集群成员变更就完成了。此时Cnew中的多数成员已经采用了新的Cnew配置，并且不包含在Cnew中的server无法组成多数派去选出另外一个leader了。（可以结合图4.2讲解）

Cnew被提交之后  
1.leader可以确认集群变更成功  
2.被移除出集群的server可以被关闭  
3.可以开始新的集群变更。为什么？解释如下：  
因为每个server都会使用接收到的最新的配置Cnew，不管它是否已经提交。所以为了防止出现上面截图中出现的集群被分为两个多数派的情况，在Cnew被提交之前，不能开始新的集群变更。

server在响应收到的RPC request时不需要理会自己当前的集群配置，而是要使用调用者的配置（也就是发送request的server的配置）。  
为什么这么设计？有两点原因  
1.添加新server。server可以接受自己存储的集群配置之外的leader发来的AppendEntries requests，否则新的server永远也无法添加到集群中（也就是说如果server的log中没有集群配置，那么她就无法接受任何log entry，但是集群配置也是通过log entry发来的，也就是说它也无法接收集群配置，这样，新的server的log是空的，没有记录任何集群配置信息，也就不可能接受任何log entry，也就无法加入到集群了。综上，server必须能接受自己记录的集群配置之外的leader发来的log entry）。  
2.投票。server可以投票给自己保存的集群配置列表之外的server（前提条件时被选举的server包含足够新的已提交日志）。这个机制有时候用来保证集群的可用性。比如往三个server组成的集群中添加第四个server，此时原有三个server中的一个宕机了，剩余的两台server不能在四server的集群中形成多数派，也就无法选出新的leader，所以需要新的server的投票。—-是否可以用后面提到的日志

## 4.2 Availability ##

保证集群可用性的措施：  
1.在将server添加到集群中之前，先让新的server追赶上集群中已有的server，避免新的server导致新加入到log中的entry无法提交（无法接收最新的日志，导致日志副本无法形成多数派，无法提交）。  
添加没有任何日志的新server可能威胁到集群的可用性。图4.4的两种情况解释：  
一个新的server在加入到集群之前，一般都没有任何日志。如果以这种状态加入到集群中，有两种可能会导致集群不可用：  
（1）三server的集群，加入第四个没有任何日志，或者日志远远落后于原有集群的server。此时三server中的一个failure了，则新添加到log中的entry不能提交（不满足多数原则），此时系统不可用，直到新添加的server日志追上原有集群的日志。  
（2）三server的集群，连续加入三个新的server。新的entry提交时，由于不满足多数派原则（不够四个），entry不能提交，系统不可用。  
以上两种情况，在新的server日志追赶上原有集群成员日志之前，集群是不可用的。

如何解决这个问题，避免可用性出现gap？  
引入新的机制。在执行配置变更之前的阶段，新加入的server不参与投票。在这个阶段中，leader向新加入的server发送日志，使其能够追上集群中现有server，但是新的server不参与选leader时的投票以及日志提交时计算副本数量。一旦新的server追上了原有的server，才开始上面提到的配置变更过程。（也就是在这个准备阶段，配置变更的信息不会写入到leader的日志的中并复制到集群其他服务器上）  
—————–这项技术也可以应用在对一致性要求不太高的只读查询上，减少集群负载。

如何判断新的server已经追上了原来的server并且可以开始进行集群变更？  
因为过早添加进集群容易造成可用性问题。  
所以我们的目标是让集群不可用的时间小于election timeout的时间，因为客户端必须能够接受偶然的非常短暂的不可用（election timeout数量级不可用，比如leader 失败）  
尽可能的让新server的日志接近原有server的日志  
————–如果新添加的server出了问题，或者永远也不可能追上现有的server，则leader终止添加server这个过程。

如何追日志？如何判断新server的日志已经足够追上现有server了？  
可以将日志复制分成10轮，第一轮复制截止到复制开始的时间点的已有的全部日志，第二轮复制第一轮日志复制期间追加的日志，后面每轮重复这个过程，每一轮复制的时间会越来越短。如果最后一轮复制日志的时间小于election timeout的时间，则将server添加到集群中。这也不会造成长时间的不可用问题。  
如果最后一轮复制时间仍大于election timeout的时间，则leader终止配置更新过程并报错。  
但是用户可以再次执行配置变更操作，因为之前的操作已经把大部分日志复制过来了，再次执行变更的话，每轮的时间就更少了。重复这个过程，直到将新server添加到集群中。  
第一步：对于新添加的server，其日志必须是空的， AppendEntries 的consistency check会一直失败直到nextindex减小到1,。nextindex会有一个先减小到1，然后随着日志的传输不断增加的过程，这个过程是影响server添加性能的主要因素。在第三章中，介绍过获得server的nextindex的更高效的办法，针对添加新server这个特殊场景，有一种最简单的办法，就是让follower直接返回自己log的长度，leader可以由此直接确定follower的nextindex。

2.如何将集群中现有leader逐步移除出集群？  
分两步：  
第一步，将当前leader的资格转移到其他server上。  
第二步，将该server按照普通的成员变更的办法移除。

3.如何避免已被移除集群的server干扰现有的集群？  
被移除出集群的server无法收到entry，也就无法知道自己已经被踢出集群了，也无法收到心跳信息及日志信息，因此会election timeout，然后使用新的term发起选举，然后集群当前的leader会被下台变成follower。最终会从Cnew里面选出一个leader，然后被踢出的服务器再次timmeout开始选举，如此循环，极大降低了可用性。  
Pre-Vote也不能解决这个问题。（被踢出集群的server可能包含最新的日志，有资格竞选leader）  
解决办法：使用心跳。  
server收到RequestVote RPC的时间距离上次收到leader发来的heartbeat信息不超过minimum election timeout时间的话，投票请求被拒绝或推迟，这两种处理方式，结果是一样的。也就是说每个server至少要等待minimum election timeout时间才能开始投票。这不会影响正常的投票，因为正常投票server发起选举的时间肯定要大于minimum election timeout的。  
意思也就是，如果一个leader能够正常给集群中的server发送心跳信息，该leader不会被废除。

这与第三章提到的leadership transfer有冲突（没有election timeout也可以投票），处理方式就是，在leadership transfer的RequestVote RPC信息中添加一个flag，表明是leader允许该server发起的投票。

4.集群成员变更算法如何在变更的过程中充分保证集群的可用性？  
证明集群成员变更期间，依旧可以正常响应客户端请求并完成集群成员变更操作。  
（假设旧配置和新配置中的多数服务器都可用）  
1.配置变更的任何一个步骤中都可以选择新的leader  
Cnew中包含最新日志的server可以被选为leader  
Cnew未提交的话，既在Cnew中，又在Cold中的包含最新日志的server，既能得到大部分Cnew的选票，又能得到到部分Cold的选票，所以不管用什么配置，都能选出新的leader

2.leader在能正常发送心跳的情况下是不会变的，除非它不在Cnew中并且Cnew已经提交（自己愿意下台）。  
leader正常发送心跳，自己和follower不会接受新的term投票请求。  
leader将自己剔除出集群的情况下，先提交Cnew然后下台。Cnew很可能选出一个leader完成配置变更。  
但是这会有一小小危险，被踢出出去的leader会再次成为leader，然后确认已经提交的Cnew，然后下台。然后Cnew中的server选leader。？？？？？？？？？？？？？？？？与上面的第3个问题是一样的，有点不好理解，需要再想想。

3.leader可以在配置变更的整个过程中响应客户端请求  
4.leader可以推动并完成配置变更

## 4.3 Arbitrary configuration changes using joint consensus ##

多个server一起添加或删除的实现方式——不需要仔细研究

# 第五章 Log compaction #

随着日志不断增长，如何删除不需要的日志。避免存储空间满了导致系统不可用，或者日志太多，启动时间太长。

原则：过时的，不需要的日志，可以删除。  
1.更看重实现的简单性，还是性能？  
2.状态机的大小，存放在磁盘还是内存中？

主要责任在于状态机，负责将状态写入到磁盘并简化日志

四种实现方式：基于内存，基于磁盘，基于增量，基于日志。  
不同实现方式的共同点：  
1.每个server独立的处理（简化截断）自己的日志。（除了第四种）  
2.Raft发送日志给状态机。在将来的某一时刻，状态机将状态持久化到磁盘，然后通知Raft丢弃相应的日志。Raft会记录被丢弃的日志的term和index（与持久化了的状态相关对应）。同时Raft也会记录该时刻的集群配置信息。  
3.Raft删除以前的日志之后，状态机的责任有两个：server重启后加载磁盘中的状态并应用日志；创建发送给其他follower的一致性映像。

1.基于内存的状态机，将快照保存到存储上之后，快照生成点之前的日志都可以删除。 1G-10G  
（之前的快照也可以删除了）  
InstallSnapshot RPC，用来发送最新的快照到其他follower。  
follower收到snapshot之后，删除snapshot之前的日志，应用snaphsot之后的日志。  
如何并行的生成快照，尽量减小对客户端响应的影响？  
写磁盘时间太长。使用copy-on-write技术实现。fork。子进程写快照，父进程响应客户请求。  
需要额外内存空间。  
什么时候生成快照？  
太频繁占有磁盘带宽，太少则重启的时候需要时间长。  
只有在需要发送一致性映像文件到其他server的时候才需要快照。  
简单的办法，当日志增大到某个值的时候生成快照。—值设的太大，节省了磁盘带宽，但日志占用空间可能偏大。  
更好的办法是当前日志大小是当前快照大小的N倍时生成快照，但是计算当前快照大小太麻烦。  
合理的办法是使用上一个快照的大小来计算是否该生成快照，而不是当前快照的大小。  
leader生成快照之前，可以先执行leadership transfer。  
不要有大于或等于半数的server同时生成快照，防止影响客户端响应。（只需要多数派就可以提交日志）

需要考虑的问题：  
内存与磁盘文件之间的流接口等等等等。。。

2.基于磁盘的状态机，只要日志应用完成了，就可以删除了。10G-100G  
日志应用之后即可删除。  
写缓存可以提升效率。  
copy-on-write生成一致映像发送给follower。需要额外的存储空间。

3.增量方法，如日志清除，LSM tree。  
比快照方式复杂。  
使用日志存储state，使用索引结构来记录数据的位置。

log cleaning  
具体算法：  
（1）选择废弃的条目最多的segment  
（2）将上一步选择的segment中，有效的条目，全部移动到日志的最前面  
（3）最后，释放该segment的存储空间，使其可以用来存储新的segment。

状态机负责决定entry是否live。

LSM tree  
树形结构的，存储排序后的键值对。  
一小段log存储最近写的key。当日志增大到某个值时，将log中的key排序然后写入到一个文件，叫做run。run不能被修改。多个run被周期性的合并成新的run，并且将旧的run删除。  
读取时，先查找最近修改的log中有没有查询的key，然后查找每个run（使用布隆过滤，快速确定run中有没有需要的查找的值）

4.直接将快照存储在日志中。效率高，但只适用于小状态机。  
基于leader的办法，与之前三个都不相同。  
直接将快照放到log中复制到follower。分成多个chunk，与客户端请求命令交替存放。  
一旦snapshot被commit，之前的日志都可以放弃。

# 第六章 Client interaction #

## 1.客户端如何寻找到集群，集群成员有可能变更 ##

广播 ，DNS

## 2.客户端请求如何路由给leader处理 ##

如何寻找leader？  
a.先随便连一个serve，不是leader的话，就再随机连一个，平均次数（n+1）/2  
b.先随便连一个server，如果不是leader，server拒绝连接，在回复clint的拒绝信息中，包含leader的地址。  
或者将客户端的请求代理转发给leader，只读请求自己处理，写请求转发给leader。

## 3.Raft如何提供语义线性一致性 ##

过滤掉重复的请求？
    服务端对每个session保存一个序列号并发送给客户端，客户端在提交请求时会带上该序列号，和命令一起发送给server。
    当重复提交命令时，也会发送相同的序列号给server，server判断该序列号是否已经处理过了。
    如果已经处理过了，则不需要再次执行，直接返回处理结果。
    
    Session不可能永远保存着，导致两个问题：
    （1）server如何对session过期达成一致？
           设置非活动客户端过期时间，根据LRU算法清理。
           活动客户端发送keep-alive requests保持客户端活动。
    （2）session已经过期的活跃客户端如何处理？
            这属于异常情况，肯定有风险。
            如果新建一个session，可能导致之前过期的session执行过的命令重复执行。
            如何改进：
            新启动的客户端连接时发送RegisterClient RPC，server创建新的session，返回客户端的identifier。如果收到一个没有记录的session发来的命令，则不处理并返回报错信息。客户端也会被清理。

## 4.Raft如何处理只读请求 ##

只读，不修改，是否可以绕过Raft log？
    只读请求如果绕过log，可能读到的是被踢出集群的server中的数据，不是最新提交的数据。
    如果server在不咨询其他server的情况下就返回结果，可能返回过时的结果。因为server可能被踢出集群了，但是自己不知道。
    
    如何解决这个问题？（leader端）（不知道自己是否被踢出集群的leader）（增加了返回查询结果延迟）
    1.新term选出的leader会提交一个空的不做任何操作的entry。只要确认了这个entry提交了，则说明这个leader已经包含了所有已提交的entry，日志是最新的。并记录这个commit index。
    2.用一个本地变量read index保存commit index的值。作为查询的最小版本号。
    3.leader发送心跳，确认自己没有被新的leader取代。确认之后，此时，这个read index是所有server能看到的最大commit index。
    4.leader等待他的状态机至少执行到read index，这时可以满足线性一致性。
    5.leader查询状态机，返回结果给客户端。

这种解决方式，避免了将查询命令写入日志，避免了写磁盘的操作。  
可以一次心跳之后，执行多个累积的查询。

如何替leader分担压力，提高吞吐率？（follower端）
    follower去查询leader的read index。
    上面的1-3步骤leader执行，4-5步follower执行

因为在返回查询结果之前需要先执行心跳，所以增加了查询延迟。

其他方法：使用时钟的方式来避免发送心跳信息。心跳信息会形成一个租约时间（election timeout），在租约时间内，leader认为不会有新的leader出现。在这段时间内，leader会直接回复查询结果，不需要先与其他server通信。

[70]: /images/20220529/09ef6847aa4d44ae9ddc476406e6aa76.png
[70 1]: /images/20220529/a6daab9a33484899906d70e1e4b17df0.png
[70 2]: /images/20220529/c1ede220e2f6445c8bec6efae29c120b.png
[70 3]: /images/20220529/5db6610071814126bcee24ea16c8eee1.png
[70 4]: /images/20220529/f143bfe6d9e645168024d5f46140ebba.png