分布式 - Raft介绍和简单实现（MIT6.824/2023-lab2)

Raft

1. Raft简介

一种分布式集群内的共识算法

• 相比于Paxos，Raft最大的特性就是易于理解（Understandable）。为了达到这个目标，Raft主要做了两方面的事情：

1. 问题分解：把共识算法分为三个子问题，分别是领导者选举（leader election）、日志
   复制（log replication）、安全性（safety）
2. 状态简化：对算法做出一些限制，减少状态数量和可能产生的变动。

2. 复制状态机的实现

复制状态机（Replicated State Machine，简称RSM）是一种分布式系统的设计模式。在该模式下，一个服务或应用程序的状态机被复制到多个节点上并行处理，以提高可用性和性能。具体地说，采用复制状态机的系统中，对于某个特定的客户端请求，它将被发送到所有复制的状态机或者其中的一组。然后，每个状态机独立地执行相同的操作序列，并生成相同的结果。最终，生成的结果将会被汇总并返回给客户端。通过这种方式，复制状态机可以将单点故障风险降至最低并提高系统的可靠性。此外，由于并行执行相同的操作序列，该模式还能够提供更好的性能和可伸缩性。

复制状态机是一种常见的分布式系统设计模式，在诸如Google、Facebook和Amazon等互联网巨头公司的分布式系统中得到广泛应用。

我们使用共识算法，就是为了实现复制状态机。
一个分布式场景下的各节点间，就是通过共识算法来保证命令序列的一致，从而始终保持它们的状态一致，从而实现高可用的。

2.1 状态简化

在任何时刻，每一个服务器节点都处于leader，follower或candidate这三个状态之一。相比于Paxos，这一点就极大简化了算法的实现，因为Raft只需考虑状态的切换，而不用像Paxos那样考虑状态之间的共存和互相影响。

Raft把时间分割成任意长度的任期（term），任期用连续的整数标记。
• 每一段任期从一次选举开始。在某些情况下，一次选举无法选出leader（比如两个节点收到了相同的票数），在这种情况下，这一任期会以没有leader结束；一个新的任期（包含一次新的选举）会很快重新开始。Raft保证在任意一个任期内，最多只有一个
leader。

• Raft算法中服务器节点之间使用RPC进行通信，并且Raft中只有两种主要的RPC：

• RequestVote RPC（请求投票）：由candidate在选举期间发起。

• AppendEntries RPC（追加条目）：由leader发起，用来日志同步和提供一种心跳机制。

• 服务器之间通信的时候会交换当前任期号；如果一个服务器上的当前任期号比其他的小，该服务器会将自己的任期号更新为较大的那个值。

• 如果一个candidate或者leader发现自己的任期号过期了，它会立即回到follower状态。

• 如果一个节点接收到一个包含过期的任期号的请求，它会直接拒绝这个请求。

2.2 单点故障

前面几篇介绍过的复制系统，都存在单点故障问题(single point of failure)。

• mapreduce中的cordinator
• GFS的master
• VM-FT的test-and-set存储服务器storage

而上述的方案中，采用单机管理而不是采用多实例/多机器的原因，是为了避免**脑裂(split-brain)**问题。

不过大多数情况下，单点故障是可以接受的，因为单机故障率显著比多机出现一台故障的概率低，并且重启单机以恢复工作的成本也相对较低，只需要容忍一小段时间的重启恢复工作。

为什么单机管理能避免脑裂问题 ？

比如有两个strorage，要选出primary，那可能有网络分区的原因，storage两个分区产生两个primary控制与外界交互，对外界的client来说有两种不同的数据

2.3 大多数原则 majority rule

如何解决脑裂： 如果投票得大于一半，多数的那个成为leader，也就是多数的分区会继续运行，如果没有获得多少投票的Leader,系统不能运行

2.4 用Raft构造复制状态机RSM

这里raft就像一个library应用包。假设我们通过raft协议构造了一个由3台机器组成的K/V存储系统,以集群内机器数量是3为例

系统正常工作时，大致流程如下：

• Client向3台机器中作为leader的机器发查询请求
• leader机器将接收到的请求记录到底层raft的顺序log中
• 当前leader的raft将顺序log中尾部新增的log记录通过网络同步到其他2台机器
• 其他两台K/V机器的raft成功追加log记录到自己的顺序log中后，回应leader一个ACK，（如果有一台网络问题比较慢，那也达到了majority）
• leader的raft得知其他机器majority成功将log存储到各自的storage后，将log操作反映给自己的K/V应用（网慢的那台这时候才发ACK）
• K/V应用实际进行K/V查询，并且将结果响应给Client

系统出现异常时，发生如下事件：

• Client向leader请求
• leader向其他2台机器同步log并且获得ACK
• leader准备响应时突然宕机，无法响应Client
• 其他2台机器重新选举出其中1台作为新的leader
• Client请求超时或失败，重新发起请求，系统内部failover故障转移，所以这次Client请求到的是新leader
• 新leader同样记录log并且同步log到另一台机器获取到ACK
• 新leader响应Client

3. Raft的选举机制

初始状态，集群中的所有节点都是follower，在Raft中，每个节点等待Leader的心跳的超时时间都是随机的，这样，在节点都是follower的状态下，会有一个节点首先达到超时状态，这时它就会开启一轮选举，自己变成候选人，首先投自己一票，并增加当前的Term，并向其他节点发送选举请求，其他节点给他投票，如果票数超过一半则选举成功。每个节点只能投一票，所有最多只有一个合法的leader被选出来，且选举成功后的leader会定时向follower发heartbeat阻止新一轮的选举。

如果说节点A已经成功了，节点B还在请求选举，如果B在收到投票结果之前收到了A的心跳，那它会转变成follower，如果在收到心跳之前收到了投票结果，节点B也必然是失败的，因为同一任期内一个节点只能投一票，它的票数不够。

随机超时时间也是用来避免无限选举的情况。如果大家的超时时间都是一样的，那么它们会同时成为candidate，那么就很可能你一票我一票，大家都没有超过一半的票，就选不出来，下轮选举并且还有可能这样，所以用随机超时时间。

各类时间的要求：broadcastTime ≪ electionTimeout ≪ MTBF
broadcastTime 指的是RPC往返时间，MTBF指的是平均一个服务器的故障时间。

开始选举时机

Raft内部有一种心跳机制，如果存在leader，那么它就会周期性地向所有follower发送心跳，来维持自己的地位。如果follower一段时间没有收到心跳，那么他就会认为系统中没有可用的leader了，然后开始进行选举。

假设此时某个follower收不到leaders的心跳，election time超时，则该follwer会开始发起重新选举，直到选举产生新的Leader；

leader term机制确保Leader在当前时刻的唯一性：

如果产生了新的Leader,随着会产生新的leader term，这时候就算原leader接进来，也会发现是新的leader term，而退化为Follower

选举规则

开始一个选举过程后，follower先增加自己的当前任期号，并转换到candidate状态。然后投票给自己，并且并行地向集群中的其他服务器节点发送投票请求（RequestVote RPC）

处理别节点发来的RequestVote RPC时，需要检查限制，满足以下之一才能赞同票：

1. 候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号；或者
2. 候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号，且候选人的Log记录长度大于等于本地Log记录的长度

成为leader的限制：

1. 大多数原则
2. 当选的机器一定是具有最新的term的机器

因此，任何一个Server发起选举后，会产生三类结果一种：

• 1. 它获得超过半数选票赢得了选举 -> 成为主并开始发送心跳

• 2. 其他节点赢得了选举 -> 收到新leader的心跳后，如果新leader的任期号不小于自己当前的任期号，那么就从candidate回到follower状态。

• 3. 一段时间之后没有任何获胜者 -> 每个candidate都在一个自己的随机选举超时时间后增加任期号开始新一轮投票。

为什么会没有获胜者？比如有多个follower同时成为candidate，得票太过分散，没有任何一个candidate得票超过半数, 如果本轮Term没有选出leader, 那就会进入下一个Term继续选Leader。

防止选举死循环

如果两个followers的election time 几乎同时到齐，都成为candidate，那会一直竞争leader死循环;

解决方法： 一般采用election time为随机值，防止同时发起选举

选举超时时间

选举超时时间的设置是需要平衡的：

1. 选举超时时间太短会频繁选举，而选举过程中是对外宕机的情况，会导致降低系统的可用性；
2. 选举超时时间太长检测不到，发起选举的机器此时也是对外宕机的；

略大于心跳时间加入些随机数，防止分裂选举死循环

Raft论文进行了大量实验，以得到250ms～300ms这个在它们系统中的合理值作为eleciton timeout。

4. Raft的日志同步

Raft的log

集群中Leader接收到客户端的指令后，会把指令作为一个新的条目追加到日志中去。一条日志中需要具有三个信息：

1. 状态机指令
2. leader的任期号
3. 日志号（日志索引）

为了分布式集群的一致性，需要保证所有机器的log的一致性。

Leader并行发送AppendEntries RPC给follower，让它们复制该条目。当该条目被超过半数的follower复制后，leader就可以在本地执行该指令并把结果返回客户端。

这一步本地执行指令，也就是leader应用日志与状态机这一步，称作提交Apply

日志的用途：持久化、顺序化的操作数据，方便重传，方面查看同步操作进行的情况

格式：有很多的log entry（入口），比如log index 、 leader term这些唯一标识；每个log entry 有 command 和 leader term信息；

日志覆写同步- 未优化版本

leader选出来后，需要保证所有server的log一致性，就会发送RPC进行日志同步

首先需要明确的是Leader上的允许Commit的日志都是正确的，因为这些日志都得到了超过一半的节点的响应。对于Follower日志的错误，本质就是要把他们强制修改为Leader允许Commit的日志。整体来说，分为两步：

• 通过AppendEntries 找到日志冲突点，就是follower从哪个位置开始和leader的日志不一致了。
• leader把follower日志冲突点以后的日志强行刷新成自己的。

具体细节就是leader会向follower不间断的发送AppendEntries请求，如果follower返回false的话，那就证明follower和leader不一致。那么leader发送的AppendEntries就会把 prevLogIndex减1再次发送，直至和follower匹配上。匹配成功以后，通过AppendEntries请求将leader上的entries同步至follower。

在所有raft节点维护两个Index

• nextIndex数组：乐观的变量，所有raft节点都维护nextIndex[followerId]用于记录leader认为followerId的下一个需要填充log的index。

  更新时间：每个leader当选之后都会乐观的认为所有的follower的nextIndex是自己的log最后的下一个，而在实际appendEntries或者installSnapshot的时候如果发现日志同步没有那么乐观就会根据情况减小next，把之前没有同步的log先同步上。

• matchIndex数组：悲观变量，，所有raft节点都维护matchIndex[followerId]用于记录leader认为followerId的已经确认的log最后一个的index，表示在此之前的log都是和当前的leader确认一致的。

  更新时间：每个leader当选之后都会悲观的认为自己已经确认过所有的follower的nextIndex是0，因为还没开始确认。

未优化版本的问题：Raft集群中有出现log落后很多的server，leader需要进行很多次请求才能将其log与自己对齐

日志擦除

新上任的leader发现其他follower有和自己不一样的log，就会把从那个log开始往后的logs都擦除，来保证leader的日志权威性一致性。

日志快速覆写同步-优化版本

落后较多的log（比如新机器接入、宕机恢复很久）要同步到现在leader一致的话，按照之前的逐步回退很慢，浪费网络资源。

如何优化？

当拒绝一个AppendEntries RPC的请求的时候，follower可以包含冲突条目的任期号和自己存储的那个任期的第一个index,借助这些信息，leader可以跳过那个任期内所有冲突的日志条目来减小nextIndex；这样就变成每个有冲突日志条目的任期需要一个AppendEntries RPC而不是每个条目一次。

论文里提到认为这种优化是没有必要的，因为失败不经常发生并且也不可能有很多不一致的日志条目；

lab2中会测试高频率的网络分区和机器故障，所以实现了日志快速覆写同步的功能。

优化后的log catch up quickly过程：

	logIndex1	logIndex2	logIndex3	logIndex4	logIndex5
S1	term4	5	5	5	5
S2	term4	6	6	6	6

1. S2的leader是term7当选，那nextIndex = 6，发送hearbeat随带log是(空, 6, 5)，意思是(当前nextIndex指向的term，nextIndex-1的term, nextIndex-1的值)
2. S1收到心跳，对比自己的logIndex为term5，与之前不同的是，除了no顺带回复自己的log信息(5,2), 意思是(请求中logIndex位置的值，当前值最早出现的logIndex位置)
3. S2收到回应后，把nextIndex改为2，下次附带([6,6,6,6],4,1), 意思是nextIndex之后的数据是[6,6,6,6]
4. S1收到后，检查logIndex1是term4对齐了，更新一致性

广播的时候，面对大量followers， 用每个go程单独处理followers

日志压缩

随着log数量的增大，log会占用大量空间，并且也会导致重放日志的时间变长。所以Raft需要定期做Snapshot，需要保存的信息：

• 状态机当前的状态（根据状态机而定）
• 状态机最后一条应用的 entry 对应的 index 和 term

需要注意的是状态机当前的状态的数据，Raft层是无法进行解析的，比如一个kv数据库，通常是保存各个kv对，这对于Raft层是透明，因此状态机当前状态的保存和解析是交给上层来完成的，Raft层只做到保存这些数据即可。

在安装快照时，是不允许新的log进行apply的，因为快照安装结束后会覆盖该条log

5. 数据持久化

持久化原因：如果基于raft的服务器重新启动，它应该从停止的地方恢复服务，所以需要Raft将持久化状态写入磁盘，并在冲洗器你懂时从磁盘读取状态。

持久化就是把一些全局的变量（比如currentTerm）写到（持久化存储）磁盘里，当然是在操作回复之前写入，类似于同步过程。

一个Raft节点崩溃重启（和新加入节点一样）后，必须重新加入，除了重新加入重新执行本地的log，更偏向于快速重启，上次持久化快照位置开始，这就要考虑持久化一些状态量：

• vote for：投票情况，因为需要保证每轮term每个server只能投票一次
• log：崩溃前的log记录，因为我们需要保证(promise)已发生的(commit)不会被回退。否则崩溃重启后，可能发生一些奇怪的事情，比如client先前的请求又重新生效一次，导致某个K/V被覆盖成旧值之类的。
• current term：崩溃前的当前term值。因为选举(election)需要用到，用于投票和拉票流程，并且需要保证单调递增(monotonic increasing)，如果重启之后不知道任期号，很难确保任期只有一个leader
• lastIncludedIndex: 奔溃前的快照保存的最后一个log的index，到这个log位置都是保存在快照中的，也就是状态机的持久化数据，如果崩溃后重启就不用交这个log之前的log了，因为上层可以直接读取整个快照。
• lasIncludedIndex: 奔溃前的快照保存的最后一个log的term

6. 利用快照服务恢复

我们的日志肯定是不可以持续的增长下去的，因为当我们日志数量达到很大的时候，比如说我们的日志数据已经达到了几千万条的时候，我们和一个还没有多少数据的跟随者进行同步的话，需要将这些日志全部发送，其实是十分浪费资源和时间的。

那么我们其实可以使用快照，也就是对领袖某一个时刻它的状态机的数据进行保存，然后将这个快照发送给那些很落后的节点进行快速的同步，同时由于快照已经记录此时的所有必要数据，那么我们可以将这些日志删除，避免日志无限度的增长下去。

利用快照还可以帮助服务重启快速恢复，服务重启恢复时有两种策略：

1. 日志重放(replay log)：理论上将log中的记录全部重放一遍，能得到和之前一致的工作状态。这一般来说是很昂贵的策略，特别是工作数年的服务，从头开始执行一遍log，耗时难以估量。所以一般人们不会考虑策略1。
2. **周期性快照(periodic snapshots)**：假设在i的位置创建了快照，那么可以裁剪log，只保留i往后的log。此时重启后可以通过snapshot快照先快速恢复到某个时刻的状态，然后后续可以再通过log catch up或其他手段，将log同步到最新状态。（一般来说周期性的快照不会落后最新版本太多，所以恢复工作要少得多）

这里可以扩展考虑一些场景，比如Raft集群中加入新的follower时，可以让leader将自己的snapshot传递给follower，帮助follower快速同步到近期的状态，尽管可能还是有些落后最新版本，但是根据后续log catch up等机制可以帮助follower随后快速跟进到最新版本log。

使用快照时，需要注意几点：

• 需要拒绝旧版本的快照：有可能收到的snapshot比当前服务状态还老
• 需要保持快照后的log数据：在加载快照时，如果有新log产生，需要保证加载快照后这些新产生的log能够能到保留

7. 总结使用Raft流程

重新回顾一下服务使用Raft的大致流程

1. 应用程序中集成Raft相关的library包
2. 应用程序接收Client请求
3. 应用程序调用Raft的start函数/方法
4. 下层Raft进行log同步等流程
5. Raft通过apply channel向上层应用反应执行完成
6. 应用程序响应Client

• 并且前面提过，可能作为leader的Raft所在服务器宕机，所以Client必须维护server列表来切换请求的目标server为新的leader服务器。
• 同时，有时候请求会失败，或者Raft底层失败，导致重复请求，而我们需要有手段辨别重复的请求。通常可以在get、put请求上加上请求id或其他标识来区分每个请求。一般维护这些请求id的服务，被称为clerk。提供服务的应用程序通过clerk维护每个请求对应的id，以及一些集群信息。

Lab2 Raft具体实现

下面介绍下 Raft 复制状态机协议 的基本实现和遇到的一些问题

主要实现难点:

故障导致副本一致性受损的各种情况考虑，分布式调试也是比较复杂，因为并发环境下，由于消息通信需要时间，log甚至不可靠，很多条件是否成立需要在当前的环境下重新得到考量。

coding之前想清楚具体实现的逻辑并且考虑一些corner case是否覆盖到，coding过程中用打log方式调试，Debug考虑到测试环境，log不能打太多，也不能太少，最好是做到精准有效。

1. Raft数据结构

type Raft struct {
	mu        sync.Mutex          // to protect shared acLockcess to this peer's state
	peers     []*labrpc.ClientEnd // RPC end points of all peers
	persister *Persister          // Object to hold this peer's persisted state
	me        int                 // this peer's index into peers[]
	dead      int32               // set by Kill()

	commitIndex int   // 已经commit的最后一个log的index，每个节点的值不一样，但是最后趋于相同
	lastApplied int   // 已经appliy到状态机的最后一个log的index,也就是被执行的指令，每个节点相同
	nextIndex   []int // leader认为的所有server下次需要新得到的log的index,乐观值
	matchIndex  []int // leader保证的所有server的log一致的最后一个，悲观值

	state       uint32  // 0 follower 1 candidata 2 leader
	logs        []Entry // 日志数组
	currentTerm int     // 当前任期
	voteFor     int     // 当前任期收到选票的candidateId

	electionTime  time.Time     // 下一次选举的时间点
	heartbeatTime time.Duration // 心跳时间间隔

	applyCh    chan ApplyMsg // 提交操作的应用通道
	applyVCond *sync.Cond    // 提交操作的通道使用的条件变量

	//2D
	LastIncludedIndex int // 快照保存的最后一个log的index
	LastIncludedTerm  int // 快照保存的最后一个log的term
}

2. RPC的处理

每个RPC应该在自己的goroutine中发送并处理回复，因为：

1. 到不了的peer不会延迟收集选票的过程
2. electiontime和heartbeattime可以继续在任何时候计时

election是并行的给集群中的其它机器发送 RequestVote RPCs

选取投票的写法： 一个函数开始投票，分出很多go程每个单独对接，每个函数对接发RPC和后处理

考虑RPC发送时间

三个时间的比较： broadcastTime 100 « electionTimeout 200-400 « 平均故障时间

两个RPC ： AppendEntriesRPCs是 leader进行日志复制和心跳时使用的 << RequestVoteRPCs是候选在这选举过程中使用的

两个时间驱动用单独的goroutine驱动

定时的设置考虑到广播时间和超时事件的区别，把elctiontime作为下一个选举的时间点，定期检查是否超过这个时间点，如果超过了就要选举，heartbeattime设置为随机范围内的时间长度，用sleep相应长度然后发送heartbeat

一个RPC重试的BUG

原来的实现：

​ 如果appendEntriesLeader发现follower的日志不同步，重新修改后递归appendEntriesLeader，也就是重发RPC直到同步完成。但是因为本身就是上锁的函数，递归调用自己，还要解锁再加锁，就算这样了递归调用不知道有错，错误不匹配后retry，但是第二次还出错会到导致不再retry了。

修改后的实现：

​ retry可能会导致死锁。修改为如果同步失败，则修改nextIndex，等着下一次心跳或者快照来同步。也就是修改为用RPC交互通知Leader下一次尝试发送的log条目的起始位置，这一点在日志快速同步的也使用了

3.RequestVote

安全性的限制：Raft使用选举过程来保证一个候选者必须包含有所有已提交的日志才能胜出；请求中包含了 leader的日志信息，如
果投票者的日志比候选者的日志更新，那么它就拒绝投票 :

1. 候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号；或者
2. 候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号，且候选人的Log记录长度大于等于本地Log记录的长度

成为leader的限制：

1. 大多数原则
2. 当选的机器一定是具有最新的term的机器

type RequestVoteArgs struct {
	// Your data here (2A, 2B).
	Term         int
	CandidataId  int
	LastLogIndex int
	LastLogTerm  int
}
type RequestVoteReply struct {
	// Your data here (2A).
	Term        int
	VoteGranted bool // 如果canditate当选为true
}

4. AppendEntries

完成了leader election之后，leader会立刻触发一次心跳包，随后在每个心跳周期发送心跳包，来阻止新一轮leader election。
Figure 2中Rules for Servers的Leaders部分将心跳称为initial empty AppendEntries RPCs (heartbeat)，将包含log的RPC称为AppendEntries RPC with log entries starting at nextIndex。这种描述听起来像是用了两段不同的代码。
而实际上因为这里的心跳有两种理解：每个心跳周期，发送一次AppendEntries RPC，当这个RPC不包含log时，这个包被称为心跳包。所以也有可能发生这么一种情况：触发了一次心跳，但是带有log（即心跳周期到了，触发了一次AppendEntries RPC，但是由于follower落后了，所以这个RPC带有一段log，此时这个包就不能称为心跳包）。

实践中，我在每个心跳周期和收到新的command之后各会触发一次AppendEntries RPC。然而仔细读论文后发现，论文中并没有只说了心跳会触发AppendEntries RPC，并没有说收到客户端的指令之后应该触发AppendEntries RPC。

我甚至认为在理论上AppendEntries可以完全交给heartbeat周期来触发，即收到command后，并不立刻发送AppendEntries，而是等待下一个心跳。这种方法可以减少RPC的数量，并且通过了连续1000次测试。但是代价就是每条command的提交周期变长。

具体实现：

每次当 leader发送 AppendEntries RPCs请求的时候，请求中会包含当前nextIndex后面的日志记录 和 他直接前继的任期和索引，

1. 如果存在一条日志索引和 prevLogIndex相等，但是任期和 prevLogItem不相同的日志，需要删除这条日志及所有后继日志。

2. 如果 leader复制的日志本地没有，则直接追加存储。

以上两条需要分别进行，如果直接用leader发来的日志记录覆盖follower的日志，那会产生bug，因为这个RPC可能是过时的RPC，所以需要严格保存这两条的分别执行。

type AppendEntriesArgs struct {
	Term         int
	LeaderId     int
	PrevLogIndex int
	PrevLogTerm  int
	Entries      []Entry
	LeaderCommit int
}
type AppendEntriesReply struct {
	Term    int
	Success bool // 是否follower包含prevLogIndex和preLogItem的日志
	Xindex  int  // 告诉leader期望下次发过来的nextIndex
	Xterm   int
}

5. applyCh

作为一个ApplyMsg的chan，日志提交之后 需要添加发送的条目

需要用单独的goroutine实现，因为可能阻塞，必须是一个不然难以确保按照日志顺序发送

go程用sync.Cond在不满足发送条件的时候等待, 需要提交的时候唤醒

1. leaderCommit() 的提交log需要检查和当前的term是否一致，如果一致则提交，如果不一致不管。

2. 当leader提交新的log，那么之前的log间接提交，因为 log Matching Property

6. 日志设置

log entry

• entry：Raft 中，将每一个事件都称为一个 entry，每一个 entry 都有一个表明它在 log 中位置的 index（之所以从 1 开始是为了方便 prevLogIndex 从 0 开始）。只有 leader 可以创建 entry。entry 的内容为 <term, index, cmd>，其中 cmd 是可以应用到状态机的操作。在 raft 组大部分节点都接收这条 entry 后，entry 可以被称为是 committed 的。
• logs：由 entry 构成的数组，只有 leader 可以改变其他节点的 log。 entry 总是先被 leader 添加进本地的 log 数组中去，然后才发起共识请求，获得 quorum 同意后才会被 leader 提交给状态机。follower 只能从 leader 获取新日志和当前的 commitIndex，然后应用对应的 entry 到自己的状态机

日志同步

nextIndex是leader认为的下次发给其他follower新log的首位置，在当选的时候会自认为所有follower的nextIndex都和自己一样，是自己日志的记录的最后一条的+1位置；

commitIndex是每个server被提交日志后最新log的索引。

lastApplied是每个server提交状态机的最新log的索引。

Raft 保证下列两个性质：

• 如果在两个日志（节点）里，有两个 entry 拥有相同的 index 和 term，那么它们一定有相同的 cmd；
• 如果在两个日志（节点）里，有两个 entry 拥有相同的 index 和 term，那么它们前面的 entry 也一定相同。

通过”仅有 leader 可以生成 entry”来确保第一个性质， 第二个性质则通过一致性检查（consistency check）来保证，该检查包含几个步骤：

leader 在通过 AppendEntriesRPC 和 follower 通讯时，会带上上一块 entry 的信息， 而 follower 在收到后会对比自己的日志，如果发现这个 entry 的信息（index、term）和自己日志内的不符合，则会拒绝该请求。一旦 leader 发现有 follower 拒绝了请求，则会与该 follower 再进行一轮一致性检查， 找到双方最大的共识点，然后用 leader 的 entries 记录覆盖 follower 所有在最大共识点之后的数据。

寻找共识点时，leader 还是通过 AppendEntriesRPC 和 follower 进行一致性检查， 方法是发送再上一块的 entry， 如果 follower 依然拒绝，则 leader 再尝试发送更前面的一块，直到找到双方的共识点。 因为分歧发生的概率较低，而且一般很快能够得到纠正，所以这里的逐块确认一般不会造成性能问题。当然，在这里进行二分查找或者某些规则的查找可能也能够加速一致化。

边界条件考虑

初始存入 0 0 空作为第一个log，作为dummy节点。

在添加快照功能之后需要把logs[0].index改成lastIncludedIndex。在这之前，保持dummy节点作为锚点不被改变。

快速同步

实现的主要方法是在reply中添加一个Xindex，每次RPC结束后都通知leader更新nextIndex[serverID]。

如果落后的较多，则返回Xindex为最后一个log的index + 1通知leader发送下次从这个Xindex开始日志串

如果index匹配了，但是term不一致，则按照论文给出的优化方法，找到这个term对应的第一个日志并放到Xindex中存起来，这样 leader接受到响应后，就可以直接跳过所有冲突的日志（其中可能包含了一致的日志）。这样就可以减少寻找一致点的过程。

7.日志提交的一致性如何保证

leader知道有log entry到达majority servers，他就会commit这个log。

有特殊情况是达到了majority servers但还没commit的leader crash，所以不通过判断majority servers来判断是不是该commit，因为就算达到了majority server之后的leader可能还会全部覆盖。Raft采用只有的currentTerm的leaders的logs被提交，因为选主过程中的Log Matching Property原则就已经保证了选出的leader在整个集群中日志的完整性。

Log Matching Property：

1. 如果两个日志的两条日志记录有相同的索引和任期，那么这两条日志记录中的命令必然也是相同的。
2. 如果两个日志的两条日志记录有相同的索引和任期，那么这两个日志中的前继日志记录也是相同的

applier日志

1. 如果上任leader在提交日志之前宕机，下一任 leader将尝试完成日志的复制。这时候，如果有rf.logs[%v].Term: %v != rf.currentTerm的情况，因为新的leader不能准确判断这个log是不是已经提交，就不能去提交这个log，也就是只提交当前term的日志；
2. 如果在上个term残留的日志后面有新的日志满足提交的条件，因为Log Matching Property已经保证了在此之前的日志都是一致性的，那就会把新日志之前的所有log都保证提交，顺便也提交了之前的term残留的log。

8. 锁的使用

1. 考虑修改server的状态变量的时候一定要上锁，
2. 在可能需要wait的操作不要上锁：channel的读写，等待timer，sleep()，发送RPC ，重传RPC（已经删除）
3. 先考虑大粒度的锁，不要提前优化，不过大粒度的锁也要考虑死锁问题

9. 2C persistence

由于我们现在都是保存在内存中的，那么断电即失，因此我们肯定是需要持久化保存起来的，比如说写入磁盘中。由于lab测试方便，官方提供的是一个类Persister来模拟持久化存储的容器，实际上这部分可以换成直接对磁盘的写入进行持久化。

对以下的数据进行更改的时候，都需要进行一次持久化：

• vote for：投票情况，因为需要保证每轮term每个server只能投票一次
• log：崩溃前的log记录，因为我们需要保证(promise)已发生的(commit)不会被回退。否则崩溃重启后，可能发生一些奇怪的事情，比如client先前的请求又重新生效一次，导致某个K/V被覆盖成旧值之类的。
• current term：崩溃前的当前term值。因为选举(election)需要用到，用于投票和拉票流程，并且需要保证单调递增(monotonic increasing)，如果重启之后不知道任期号，很难确保任期只有一个leader
• lastIncludedIndex: 奔溃前的快照保存的最后一个log的index，到这个log位置都是保存在快照中的，也就是状态机的持久化数据，如果崩溃后重启就不用交这个log之前的log了，因为上层可以直接读取整个快照。
• lasIncludedIndex: 奔溃前的快照保存的最后一个log的term

2CBUG：

TestFigure8Unreliable2C，leader commit判断通过之后，还没有applier就断了或者applier了之后断了，这样一千次

解决: 我理解是考验日志同步速度的问题，添加了快速覆写同步功能，RPC回复校验了冲突的log index来直接发送冲突的日志开始的日志片段，加快log同步速度。 然后我自己考虑了超时时间和心跳时间的设置，也一定程度加快了一致化的速度。

10. 2D 快照

InstallSnapshot

用于日志压缩，拍摄快照以存储当前的状态，那么这个点之前的日志就可以删除。

一般机器单独的进行快照，除非有一个很慢或者新加入的follower需要leader网络发送快照来使其快速追赶

InstallSnapshot RPC

leader发送快照RPC，followers来决定使用；

1. 如果快照包含新信息超过follower的logs, 那会完全选择快照覆盖和logs删减；
2. 如果快照比follower的logs短，那prefix覆盖，之后的保留

type InstallSnapshotArgs struct {
	Term              int
	LeaderId          int
	LastIncludedIndex int
	LastIncludedTerm  int
	Data              []byte // 快照数据
}
type InstallSnapshotReply struct {
	Term    int
	Success bool // 快照应用情况
	Xindex  int  // 期待下次发过来的log的index
}

快照和一致性的冲突的：
虽然违背了只有leader修改logs的强领导原则，但是快照的时候一致性已经达成了，所以没有决定是冲突的，数据流还是leader流向follower

快照的时机

快照拍摄： 状态机发现自己的目前的存储数据过大，那么就保存当前的状态机必须状态以及日志和Raft的必须状态到快照中。然后通知Raft对自己的日志进行丢弃，也就是调用Raft的Snapshot()。(日志数组第一位要么为空占位日志，也就是一次快照都没进行的时候日志数组下标为0位置的日志，要么为快照后索引为lastIncludeIndex的日志)

快照接收： 当领袖发送ApppendEntries RPC的时候，发现需要跟随者的nextIndex <= 日志数组中第一个日志的索引的时候，也就是需要发送的日志已经被丢弃了，那么就调用InstallSnapshot()来安装快照。

当跟随者接收到领袖发来的快照的时候，若快照是正确的，那么就接收，并通过applyCh传递给状态机。

状态机接收到安装快照的请求，进行快照数据的应用，并且通知Raft去更新到该快照。也就是调用Raft的installSnapshotLeader()。

Raft被调用installSnapshotLeader()之后，对响应的日志进行丢弃。

bug - 日志压缩后需要修改index

因为压缩之后logs数组的下标就不是index了，需要修改为真正的index

1. lastLog的index可能变成了以一个dummy节点，index = 0，需要改成nextIncludedIndex，因为在选举的时候需要判断

2. nextIndex 等等也需要改

3. 添加一个接口，然后一个个测，改掉所有的下标

   func (rf *Raft) GetRealLastLogIndex() int {

   return Max(rf.logs[len(rf.logs)-1].Index, rf.LastIncludedIndex)

   }

2d-快照bug

1. 先写所有server的快照功能，需要大改下标

   解决： 主要是加了rf.GetRealLastLogIndex()函数

2. 快照之后，上一次append还没发出去的Entry会被部分覆盖，也就是说在go程去append 的时候args被其他线程修改了

   解决：这个bug改了好久，对go不熟悉，并发的问题，因为之前args.Entry的创建直接用数组切片初始化Entries: rf.logs[nextindex-rf.LastIncludedIndex:]，可能编译器折叠args.Entry为切片的表达式，也就是并发过程中切片本身变化可能会导致args.Entry的变化。

   之后改成了make空间，然后用copy(args.Entries, rf.logs[nextindex-rf.LastIncludedIndex:])赋值，bug解决

3. crash后恢复的server需要把之前的log重新应用到状态机（这里重新应用logs应该采用提交快照应用），否则直接往后提交新追加的logs是无法提交的，因为lastApplied没有持久化时恢复的时候是0，用日志applier的方式会从log1开始交，但是lastIncludedindex之前的log已经被快照剪短了。

改成make的时候lastApplied和commitIndex都初始化为lastIncludedindex，但是这时候也可能会出现直接提交新的log，而没有实现重新应用之前的log到状态机。这里测试能通过，不清楚什么原因？可能是之前的状态也持久化了？

这里一直有个误区时把加载快照和重新log跑一遍搞混淆了，加载快照后，得到的状态就是快照的最后一个log执行完后的状态，也就是不需要再跑最后一个log之前的log中的命令了。

也即是说真正的原因是在2D之后已经持久化了快照，那服务器重启的时候上层状态机就可以直接读取硬盘中存储的快照（之前的logs的总和操作），对于重启的server只需要继续添加之后的log就可以了。

总结

1. 现实中raft集群一般是3 5 个，单数防止脑裂，一个服务器损坏的平均情况大概是几个月一次，所以3 5 个足够修复恢复了
2. 服务器遇到的问题会有网络分区联系不上、机器故障挂了等，需要考虑很多种极端情况，比如TestFigure8Unreliable2C当选leader会频繁的掉线，我们需要保证在1000次混乱后还能让raft在10s内成功提交日志， 每一次尝试必须在2s的时间成功提交，对日志同步速度要求很高。
3. 千万不要过早优化。直接使用函数粒度的锁，细粒度的锁在提升性能的同时，会增加复杂度，尤其debug的难度，并且这个难度在复杂的高并发+不可靠的网络背景下可以无限上升。等待debug难度过大，就只能删掉重构了。

实现了Raft支持的Leader选举、日志复制、Snapshot、异步Apply等基本功能, 有空看看Paxos，因为这是最经典的一致性算法