学习MIT6.824分布式系统中的Raft论文与相关实验的总结。
Raft理解与实现过程中遇到的疑问
- 初始状态是什么：均为follower
- candidate如何在election过程中退化为follower：接收到其他Leader的heartBeats（在AppendEntry RPC中改变状态）；vote的reply中的term大于currentTerm
- 如果二次选举，其他follower的votedFor如何初始化：votedFor只是在当前term中所选择的candidate，当RequestVote RPC参数中的term大于当前term，直接认为当前server还没有vote，并更新term
- 脑裂问题：leader的AppendEntry的reply的term大于currentTerm，会使当前leader退化为follower，所以只会有一个有效的leader
- leader节点断开连接，它会有什么行为：它仍然觉得自己是leader
- commitIndex和applyIndex什么关系：commitIndex是leader确认有多数server复制了的日志lastIndex，准备apply到state machine，当applyIndex小于commitIndex时，会把相应的command apply到state machine
- 更新commitIndex时，为什么要满足log[commitIndex].term=currentTerm:figure8
- prevLog选什么：选要拷贝到server的日志的前一个log Entry，用于判断拷贝日志的位置是否合适正确
- 直接把follower冲突的logEntry直接覆盖合适吗：每个leader都会包含所有已经commit的log，覆盖follower的log不会造成不同server的command序列不同
- client没有发送到leader如何转发：从Lab2没有找到答案，测试用例时直接吧command提交到leader
- leader断开连接后接收到的log，在重新连接到集群中成为新的leader时包含与已经commit的command不符的log：加了相应的约束后，这种情况不存在
- 当网络存在failure时，goroutine数量会大量增加，超过go的限制：测试用例中只不再使用crash的raft实例时并没有停掉无用goroutine，自己在Kill（）中停掉相应的goroutine；AppendEntry RPC可能会非常慢，不应该启一个新的goroutine watiGroup，不需要等待所有server回复，直接根据matchIndex更新commitIndex即可
- Lab2的测试用例还是会有小概率不通过：1. failed to reach agreement，没有在timeout时间内apply指令到state machine，应该是有一些性能上，选主上有一些问题：之前复制log有冲突时的解决机制有问题，造成无法复制到follower；candidate回退到follower没有重置选举时间，会立刻转换为candidate，可能会造成无法选出leader的情况 2. apply error：不同的server 的command序列不同，怀疑是旧的leader回退follower过程，更新term后成功向其他server AppendEntry或者是遗漏了一些持久化的时机，fix：之前退化的时候会向channel传送数据，用于通知其他goroutine leader已经退化，不需要再发送心跳，但是其他goroutine是通过len（ch）来判断的，这种方式可能不够及时，还是通过rf的state是否时leader来判断，不需要其他额外方式 3. 资源竞争：在使用RPC参数的时候出现竞争，不太清楚如何在模拟RPC过程中应该对args，reply做同步处理
- 跑Lab3A的测试用例时，会有client不再继续commit命令，并且goroutine数量不断的增多： 在server接收apply时有直接return的逻辑，造成channel没有接收者，raft的apply过程阻塞了；只在apply在lock过程中，造成无法产生新的Start
- lab3b中每个server存储snapshot的时机？只有apply的entry可以存入snapshot？snapshot中只保存中间状态？还可以看到之前完整的log列表吗？：保存snapshot的时机由kvraft server决定，它会检测持久化的raft state是否超过阈值，超过时就会保存snapshot，并通知raft server丢弃之前的log；因为是在kvraft server中进行保存snapshot，一定只会丢弃已经apply到state machine的log；在Lab3B中是只保存中间状态
- 如何控制snapshot的大小（用于判断是否是重复的请求的备份也需要存入snapshot）？：使用更高效的重复请求检测的方法，目前仍然是使用uuid来检测每个请求，所以需要一个不断增长的map
- leader向follower发送installSnapshot RPC的时机？：leader向follower 发送appendEntries RPC请求时，如果prevIndex，term冲突，leader会减小prevIndex，term并继续请求，如果使用leader的snapshot中的index和term作为参数仍然存在冲突，则说明follower需要进行install snapshot
- server恢复时，commitIndex如果从0开始，会apply重复的log到state machine：state machine也会恢复到快照状态，所以这样时正常的，不会影响最后的状态
- 被install snapshot的server，apply到state machine后应该是什么操作，只覆盖之前的snapshot就可以了吗：还需要立刻更新到这个snapshot的状态
- raft中如何读取snapshot中的lastIndex和lastTerm，现在是硬编码直接通过gob读取
Raft选主流程（Lab2A）
server有三个状态：follower，candidate，leader
Raft把整个时间分成多个term，每个term包含选举过程，选举成功后会有一个正常操作过程（一个leader和多个follower）直到term结束
- 初始状态所有server均为follower，随机生成超时时间
- follower在超时时间内没有接收到leader的heartBeats或者是candidate的requestVote，转换为candidate。初始状态下因为没有leader和candidate，所有的server都会有转换为candidate的趋势，随机的超时时间会使转换时间不同，大大减少无法选出leader的可能性
- 转换为candidate后
- 增加自己的term，进入新的一轮选举
- 投票给自己
- 重置选举超时时间
- 向所有其他server发送requestVote
- 选举结果：
- candidate赢得大部分（大于总数量的一半）的server投票后，转换为leader，leader会定时的向其他server发送heartBeats
- 在选举过程中接收到新的leader的heartBeats时要回退到follower状态
- requestVote的回复中term要大于当前term时要回退到follower状态
- 当在选举超时时间中还未得到选举胜者，则再重新开始一个选举过程，term也增加
- 投票规则：
- 只投给当前term的第一个向自己发送投票请求的candidate
- 在更新term时，重置所投票的server
- 所有的server当RPC的请求或回复的term大于当前term，说明当前server还处于上一次term中。做更新term操作，并退回到follower状态。解决leader断开连接后依然认为自己是leader，再接入到集群中后的问题。
Raft日志复制（Lab2B）
- leader不会删除或替换log，只会添加
- leader接收到client的command，加入到日志list中
- leader通过AppendEntry RPC向各个server复制所添加的日志
- RPC参数包含所复制日志前一个日志的index和term，如果匹配，则agree，把日志复制到本地，并根据新日志中最后的index和leader的commitIndex更新本地commitIndex（取较小值）
- leader会维护一个nextIndex[]，记录每个server所复制日志的起始index，在选举后成为leader时初始化为末尾日志index+1。当成功复制到server时，更新nextIndex，否则自减继续请求复制
如果集群中大部分server都成功复制并回复，则leader更新自己的commitIndexleader维护一个matchIndex[]，记录每个server成功复制的日志最后一个index，在AppendEntry RPC成功回复时更新，在选举后成为leader时初始化为0， leader自己的matchIndex也要相应的更新。当matchIndex中,对于某个值$N$,大部分的server有$Index \ge N$，且leader的commitIndex要小于$N$，且log[N].term=leader.currentTerm,也就是该entry是当前leader创建的，该则更新commitIndex为$N$。- 所有server中当lastApplied小于commitIndex时，则增加lastApplied的值并apply command，可以batch apply，每次循环不只apply一个command，减少测试用例中
failed to reach agreement的概率
Raft safety（Lab2B）
不同的state machine应该以相同的顺序执行相应的command，不过只按照上述的选主和日志复制策略的话还是做不到的。比如，一个follower与集群断开连接，再接入到集群后被选为leader，该server的command序列就可能与之前集群中的server不同了。
Raft在选举过程中加了一些约束，server回复RequestVote的时候除了之前提到的只投给首次请求自己的candidate外，还需要candidate至少与自己一样up-to-date，即比较最后一个log Entry的index和term：
- term更大的说明更加up-to-date
- 相同term的话，index越大越up-to-date
保证了新的leader包含之前已经commit到state machine的log Entry，可以通过反证法证明这个论点
假设$leader_T$(term T的leader)在term T中commits了一个log entry，简称$Log_C$，但是在未来的term中存在leader没有保存$Log_C$，假设$leader_U(U > T)$是不包含$Log_C$的leader中term最小的
- $leader_U$在选举时不包含$Log_C$，因为leader只会添加log entry，不会删除或替换entry
- $Log_C$在大多数server有拷贝，$leader_U$也获得了大多数server的投票，所以至少有一个server是同时有$Log_C$并给$leader_U$进行了投票，该server称为voter
- voter是先接收的$Log_C$再给$leader_U$投票，否则voter的term会更新为U，造成$leader_T$的AppendEntry失败
- voter在给$leader_U$投票的时候包含$Log_C$，因为根据假设所有中间leader都包含$Log_C$（根据假设$leader_U$是第一个不包含的），leader不会移除log，也只有与follower冲突的时候才会移除
- voter给$leader_U$投票，根据约束，$leader_U$与voter一样up-to-date，这就造成了两个矛盾
- 如果最后log的term相同，则$leader_U$应该比voter长（index更大），则$leader_U$应该包含vote所有log内容，这与假设就矛盾了
- 如果$leader_U$的最后log的term更大，而voter的最后log的term至少为T（因为包含$Log_C$），所以创建$leader_U$的最后log的leader的term大于T小于U，一定包含$Log_C$（根据假设$leader_U$是第一个不包含的），根据Log Matching Property，$leader_U$也必须包含$Log_C$，这也与假设矛盾了
- 所以所有term大于T的leader都会包含在之前commited的log
Raft持久化 （Lab2C）
server crash之后希望重启并再再次加入到集群中，所以需要对一些数据做持久化，包括：
- currentTerm：现在所处的term
- votedFor：当前所投票的candidateId
- log：日志
持久化的时机是在这些数据改变之后：
- RequestVote，AppendEntry RPC回复之前
- 接收到RPC reply，更新currentTerm后
- leader接收到client的command加入到log后
对于一些非持久化的数据的更新要注意是否使用可以通过自增，可能会造成错误，比如leader加入新的log Entry后更新自己的matchIndex时应该直接通过log的长度更新，而不是自增1
RaftKV（Lab3A）
利用Lab2实现一个简单的分布式KV数据库，client可以有Get，Put和Append指令，server回复client相应操作后的结果
- client通过RPC向server发送指令请求，如果server不是leader或者RPC没有得到正常回复，则向其他server请求
- client可以记录上次成功请求的server id，减少每次请求重新寻找leader所消耗的时间
- 因为其中
Append指令并不是幂等的（多次执行不影响结果），还需要考虑leader在其apply指令前断开与client的连接，造成多次重复的Append的请求。从at least once的策略改为at most once是比较好的。client请求的时候带一个unique ID，重新发送时ID不变，server通过unique ID来判断是否时重读的请求 - server维护KV数据结构以及unique为key的指令执行结果map
- server通过raft的
Start（）来提交指令，如果不是leader立刻回复client；如果是leader则等待执行结果回复client（通过结果map是否包含ID的key值判断） - 创建新的server时，启一个goroutine，遍历等待（range）applyCh，等待raft得到共识后，apply相应的指令。server执行相应的指令修改KV，存入结果map
- 如果server接收client请求时发现ID已经存在在结果map中，则直接回复；range applyCH时如果发现ID已经存在在结果map中，则直接continue，不做任何操作
RaftKV（Lab3B）
Raft的log会越来越大，这对性能会有较大的影响，需要有相应的策略对log进行压缩，Raft使用了快照技术。state machine的最终状态是由初始状态执行相应的指令序列得到的，所以保存某个中间状态，丢弃掉之前的指令仍然可以做到最终状态一致。快照技术就是使用了这种机制来对日志进行压缩。
- kvraft server对持久化的log进行检测，当长度大于阈值时，保存当前快照并通知raft server丢弃之前的log
- 快照内容：状态（keyValue），lastIndex和lastTerm（丢弃log中最后的index和term，用于raft中的冲突检查，比如appendEntries就需要prevIndex），用于重复请求检测的map（这个仍然会越来越大，并且无法过snapshotSize的测试用例，应该用其他更合适的检测方法）
- 大部分时间保存快照是每个server独立进行的，但是可能会有新的server或者长时间断开连接的server，造成部分log leader还未复制到follower中就丢弃了。所以还需要leader向follower按照snapshot的RPC
- snapshot可能较大，install RPC应该分块发送，以免造成follower转换为candidate
- 从leader接收到的snapshot通过applyCh提交到kvraft server来进行保存
- leader通过appendEntries来验证follower是否需要install snapshot：snapshot中index，term作为prevIndex，prevTerm都还有冲突的时候则需要install snapshot
- follower接收snapshot时先拷贝的临时空间，接收完毕之后再拷贝到相应空间等待apply到state machine
- 通过一些策略来避免重复的install操作：leader通过flag来标记；follower通过当前是否有待提交的snapshot
- kvraft接收到snapshot保存后，应当更新到这个snapshot的状态
- 因为snapshot的存在，第一个log entry的index不一定为1，之前不应该直接把raft中的一些index直接作为slice index使用，应该根据首尾entry的index计算出slice index。