学习MIT6.824时，想从socket开始写起，构建网络层，RPC层，Raft层，到应用层的k/v缓存。想自己实现去感受一下各个部分到底是如何运作的，以学习和练习为主，并且为之后的学习打好基础。
参考资料：
网络库：主要参考muduo，事件驱动的非阻塞网络库
RPC : protobuf https://developers.google.com/protocol-buffers/docs/reference/cpp/google.protobuf.service
可视化：https://raft.github.io/
可视化: http://thesecretlivesofdata.com/raft/
论文原版：https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf
论文中文翻译: https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
MIT6.824 Lab2 :https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
github:https://github.com/JiaMing5139/DistributedSystem
一.Raft中数据结构的定义，对应论文中Figure2
1.RPC消息格式 （protobuf）
message LogEntry{
int64 index = 1;
int64 term = 2;
string commandName =3 ;
bytes command = 4;
}
message AppendEntriesRequest {
int64 term = 1;
string leaderId = 2;
int64 prevLogIndex = 3;
int64 prevLogTerm =4;
repeated LogEntry LogEntries = 5;
int64 leaderCommit;
}
message AppendEntriesResponse {
int64 Term = 1;
int64 Index = 2;
int64 CommitIndex =3;
bool Success = 4;
}
论文Figure写 Response中包括 Success 和term
但只靠success 分别不出来一种状态，就是对端是否确认有一个新的log被match，原地不动和有新logMatch都返回true，所以需要本地再维护一个状态判断是否又新log被发出
加上Index，对端直接返回自己match的序号，更简单
message RequestVoteRequest {
uint64 Term=1;
uint64 LastLogIndex=2;
uint64 LastLogTerm=3;
string CandidateName=4;
}
message RequestVoteResponse {
uint64 Term=1;
bool VoteGranted=2;
}
service RaftService {
rpc AppendEntries(AppendEntriesRequest) returns(AppendEntriesResponse);
rpc Vote(RequestVoteRequest) returns(RequestVoteResponse);
}
2. 每个Raft实例需要维护的变量
class Client{
int64_t nextIndex_ = 0;
int64_t matchIndex_ = 0;
bool voteGranted_ = false;
std::string ClientName;
}
class Raft{
int64_t currentTerm_; // 当先raft的term
State currentState_; //当前状态
int votedNum_;//收集到的投票
string votedFor_; //当前term给谁投的票
vector<Client> clients_//其他节点
}
一.领导人选择的限制条件
- Raft为了保证同一Term只有一个Leader被选出，选举时需要什么条件？
过半结点投票同意，每个任期只能投票一次。如果出现等票情况
则electiontimeout过期自动开启新一轮Term的领导人选举
成为leader后立马发出appendEntry 限制新的candidatate出现
- 为了保证安全性，选举时需要条件？
安全性就是指提交后的日志，不会被再次覆盖
因为必须超过半数才能当领导人，两个任期内必定会有一个完整的结点是重合的。
所以不论怎么发生网络划分，都必须让那个两个任期中重复的，也是日志最完整的结点当Leader，才能保证不会被其他的日志覆盖，所以要进行限制
一种临界情况：
S1 S5 结点的Term为45
S2 S3 S4 的Term为2，已经有三个日志确认提交，返回给客户端成功
此时RAFT必须保证三条日志不会丢失
为了保证RAFT正常工作，必须有3个及以上的结点正在运行，才能选出Leader正常运行
这时候S3 S4两个保证完整结点死掉，S1 S5重启成功，这时候仅剩1个S2保存着正常结点
为了让这个运行着的RAFT返回正确的结果，必须让S2当结点Leader，保证日志的完整性
状态转移表：
| event\state | follower |
|---|---|
| electionTimeout | 清空上一个任期内的记录 this.currentTerm++ this.currentState=Candidate votedFor = selfname for c in clients to c.requestRpc() |
| RequestVoteRpc | 如果日志不是最新的，返回false Term的三种情况: 1.localterm大于peerterm，说明收到的请求是过期的candidate返回false 2.localterm等于peerterm，说明同一时间有两个candidate再发送投票请求，只投一个 3.localterm小于peerterm,说明这是一个新Term的请求，且是第一个到的，将之设置为自己的Term，返回true |
| VoteResponseRpc | 如果peertrm > localterm localterm = peerterm |
| event\state | candidate |
|---|---|
| electionTimeout | 清空上一个任期内的记录 this.currentTerm++ this.currentState=Candidate votedFor = selfname for c in clients to c.requestRpc() （有人瓜分选票，没有出现leader，再次重复给没有voteGranted为false的client发送s） |
| RequestVoteRpc | 处理同follower，但肯定反回false,因为成为candidate必然已经投票给了自己 |
| VoteResponseRpc | if（RequestVoteResponse.VoteGranted == true）{ client.voteGranted=true 查看有多少client的voteGranted为true if 超过一半 this.currentState=Leader start AppendEntriesTimer 让所有client中的nextinex = commitedIndex + 1 } if (RequestVoteResponse.Term > currentTerm) current =Term |
| event\state | Leader |
|---|---|
| electionTimeout | Leader不会有electionout |
| RequestVoteRpc | 如果peerTerm比较大，说明自己是一个过期的Leader，将状态变为Follower，然后像一半的follower投同意票 |
| VoteResponseRpc | 丢弃？ |
二.日志提交的限制条件
日志提交指的是，已经给客户端返回成功，保证该日志永远不会丢失。
-
如何判断多数结点都已经在N处保存了log？
多数client的matchIndex >= N
-
为了保证安全性，需要什么限制条件？
不提交之前任期的日志
-
日志复制中需要用到的各个参数的变化时机
- client.nextindex 用于推测client中需要下一个日志的位置
1.初始化为最后一个日志的坐标+1
2.当AppendEntry返回True时，nextIndex可能+1
3.当 AppendEntry返回false时， nextIndex - 1 - client.matchindex 保证matchIndex已经被该客户端所保存
1.初始化为0
2.当AppendEntry返回时，matchIndex=peer.matchIndex
用来保证安全，用来保守的表示从头数已经共享到第几个log给字节点，
| event\state | Leader |
|---|---|
| heartBeatTimeout | 1.设置preIndex和preTer (preLogindex,preTerm = locallogs[client.nextIndex - 1].index,term) 2. 如果nextIndex在log的范围内，且matchIndex + 1 = nextindex?{ 则说明已经匹配上位置,并添加nextIndex位置的log到rpc中 } 3.重设heartBeat定时器 |
| AppendEntryRpc | 产生leader后，同一个term只有一个leader，所以leader不可能会收到另一个leader发来同一任期的AppendEntryRpc if peerterm>localterm leader变为follower，设置自己term] |
| AppendResponseRpc | 1.如果peerTerm>localTerm 则一定返回的是false，自己是一个过期Leader，状态变为follower 2.如果peerTerm<=localTerm ，且成功则可以开始继续处理，否则对应client的nextIndex-1，matchIndex = response.matchIndex(0) 3.如果是一个新match的log，则让client.match++ client.nextIndex = client.match+1 4.如果最新match的日志是在自己任期内，则开始进行commited判断 |
| event\state | Follower |
|---|---|
| heartBeatTimeout | |
| AppendEntryRpc | 0. 重置electionTimer 1.term检查，失败返回false 2.if preIndex preTerm匹配检查，response.matchIndex = 0失败返回false 3.else 匹配成功，如果日志不为空，则将日志添加,且进行commindex更新（leadercommit和logs.back().index中的较小值） |
| AppendResponseRpc |
| event\state | Candidate |
|---|---|
| heartBeatTimeout | |
| AppendEntryRpc | 0. 重置electionTimer,设置状态为follower 1.term检查，失败返回false 2.if preIndex preTerm匹配检查，response.matchIndex = 0失败返回false 3.else 匹配成功，如果日志不为空，则将日志添加,且进行commindex更新（leadercommit和logs.back().index中的较小值） |
| AppendResponseRpc |
三.与客户端的交互
