raft 小论文笔记

request vote rpc

各 follower 超时之后，变为 candidate，向其它成员发送 request vote，请求成为 leader。request vote rpc 需要的参数如下：

• candidate id，标识自己是谁。
• term，标识自己当前的任期。
• lastLogIndex，自己拥有的最大的 log index。
• lastLogTerm，自己拥有的最大的 log term。

回复格式参数如下：

• term，reciever 的 term 信息，如果 reciever term > sender term，则 voteGranted 必为 false，sender candidate 需要更新自己的 term 信息，并重新转化为 follower。
• voteGranted，为 true 需要满足三个条件，一个是当前 reciever 没有给其它 candidate 投过票，即 voteFor 为 null 或者 sender candidate id，一个是 term，一个是 log index。

append entry rpc

用于复制日志。

request rpc 格式：

• logEntry[]，复制的日志内容，其中包含 term 和 index。
• term，leader term。
• leaderId，用于重定向到 leader。
• prevLogIndex，上一次复制请求包含的最新 log index。
• prevLogTerm，上一次复制请求包含的最新 log term。
• leaderCommit，leader's commit index。

prevLogIndex 和 prevLogTerm 用于判断 follower 上的日志是否跟上了 leader 的进度。类似于 offset。

response 格式：

• term
• success

reciever implementation。

• if currentTerm > term，reply false。
• logTerm 相同，logIndex 不存在，说明进度落后，返回 false。logTerm 落后，也返回 false。
• 日志有冲突，logIndex 相同，但 term 不同，删掉对应日志以及之后的所有日志，并返回 false。
• append 新的日志，并返回 true。
• 如果 commitIndex < leaderCommit，set commitIndex = min(leaderCommit, index of last log entry)。

server 的行为

All servers:

• if commitIndex > appliedIndex，increment appliedIndex，write log[appliedIndex] to state machine.
• if term in request or response greater currentTerm，set currentTerm to it and becomes follower.

follower:

• response to rpc from leader and candidate。
• 长时间没有收到 leader 发来的 headbeat 或者 candidate 发来的 request vote，则变为 follower。

candidate:

• 成为 candidate 之后

  • currentTerm + 1

  • vote for self

  • send request vote rpc to others

  • reset timer

• if recievers major votes，become leader

• if recieves appendEntries rpc, become follower

• if timeout, start a new election

leader:

• Upon leader: send initial empty AppendEntries rpc and repeat，主要是为了维持 leader 的稳定。
• 处理写请求，写日志，写状态机，都完成之后向 client 返回。
• if last log index >= nextIndex，send AppendEntry rpc。何时发送 log，发送成功/失败状态如何更新。
  • success -> update next and match.
  • failed -> decrease next and retry.
• 何时更新 commitIndex。这个更新了之后才能触发写状态机的操作。

membership change

• log replicated to both old and new configurations.
• election and replication need majority of both.
• any server can be elected as leader.

problems to solve:

• new server may not store any logs.
• cluster leader may not be part of the new conf.
• removed servers may disrupt the cluster. 一个 server 如果在最小超时时间内收到了 RequestVote RPC，它不会更新 term 或者 grant vote.