前言
KaiwuDB 的事务在实现时使用了时间戳、MVCC、Raft 等组件，本文将重点介绍 Raft 在事务实现中的作用以及在 KaiwuDB 事务中的应用实现方式。
Raft 概述
KaiwuDB的事务使用Raft协议来实现数据的一致性，下面先介绍Raft协议的主要工作过程。
Raft是经典的分布式一致性算法，它的主要特征有：
- 选举唯一的leader处理读写请求并创建新的raftlog，其它节点作为follower接收leader同步的raftlog；
- Leader不修改或删除自身的raftlog，只增加；follower可以删除和leader冲突的raftlog；
- Raftlog严格串行增加。两个节点上的某对raftlog是一致的，那么这对raftlog之前的所有raftlog都一致；
- Raftlog被同步到超过一半的节点后就被视为已提交（committed），已提交的raftlog不会丢失；
Raft协议的工作过程主要是选举和日志提交，成功且安全的选举是raft可以工作的前提。
选举
在集群刚启动，或follower节点发现leader心跳异常时，就会开始一轮选举。每一轮选举对应着一轮任期（term），发现当前集群没有leader的节点变为候选者（candidate），自身缓存的任期+1，并给自己投票，然后向其它节点发送RequestVote RPC拉取选票。
RequestVote RPC中携带候选者的信息以帮助收到请求的节点决定是否投票，主要信息有：候选者当前的任期，候选者最新的raftlog的任期以及编号。节点会检查这些信息，并判断是否投票：
- 候选者的任期若小于自身的任期则不投票；
- 当前任期已投过票则不再投票；
- 候选者的最新raftlog比自身的最新raftlog老则不投票；
当以上情况都不存在时，则节点为候选者投一票，并缓存投票信息，并更新自身的任期。
候选者获取超过一半的投票之后，包括自己投的一票，则认为已当选为leader。之后立即开始向其它节点发送心跳，以防止选举超时，出现新一轮的选举。其它节点收到心跳后则停止选举，原先是候选者的节点自动变更为follower，所有follower检查自身的任期并和leader对齐，准备接收leader同步的raftlog。
日志提交
Leader选出来之后就需要负责处理用户的读写请求。每个写请求会被包装成raftlog，其中包含请求的命令和数据；当前的任期term；当前raftlog在所有的raftlog中的位置，即index；前一个raftlog的term和index，即prevLogTerm和prevLogIndex。然后通过AppendEntries RPC发送给follower节点，follower回复消息通知leader是否复制成功。当有超过一半的节点（包括leader）复制成功后，则这条raftlog就是已提交的状态，不会再被修改或丢失。
Follower节点收到AppendEntries RPC后不是无条件复制raftlog，它将检查自身最新的raftlog的term和index是否和最新的raftlog中带来的prevLogTerm和prevLogIndex一致。如果一致则将收到的raftlog追加到本地的raftlog最后，回复leader结果为成功；否则则回复失败。并且如果出现冲突，即prevLogIndex小于等于本地raftlog的index时，删除本地所有冲突的raftlog。
Leader收到失败的回复后，会重新发送更老的raftlog给follower，直到follower上的raftlog完成了同步。
AppendEntries RPC中还会携带当前已经提交的最新的raftlog的index，follower根据它来判断自身是否需要apply某些raftlog，即执行已经提交的raftlog中的命令，将数据落盘。心跳是特殊的AppendEntries RPC，其中没有raftlog，但是也包含了最新提交的index，通过心跳可以使follower更及时地落盘数据。
以上就是Raft协议的基本内容，关于Raft针对部分特殊情况的处理，比如raftlog未提交而leader宕机，以及增删节点等情况本文不做赘述，感兴趣的话可以直接阅读原论文。
