raft论文笔记

使用目的：Raft 算法是可以用来替代 Paxos 算法的分布式一致性算法，是用来管理复制日志（replicated log）的一致性协议。

复制状态机：复制状态机用于解决分布式系统中的各种容错问题。通常使用复制日志实现，每个服务器存储一个包含一系列命令的日志，其状态机按顺序执行日志中的命令。 每个日志中命令都相同并且顺序也一样，因此每个状态机处理相同的命令序列。 这样就能得到相同的状态和相同的输出序列。

State

Persistent state on all servers:

currentTerm     latest term server has seen (initialized to 0 on first boot, increases monotomically)
 voteFor    candidateId that received vote in current term (or null if none)
 log[]          log entries; each entry contains commend for state machine, and term when entry was received by leader ( first index is 1)

Volatile state in all servers:

commitIndex     index of highest logentry known to be committed ( initialized to 0, increases monotonically)
lastApplied index of highest log entry applied to state machine (initalized to 0, increases monotonically)

Volatile state on leaders:

nextIndex[] for each server, index of the next log entry to send to that server (intialized to leader last log index +1 )
matchIndex[]    for each server, index of highest log entry konwn to be replicated on server (initalized to 0 increases monotonically)

RequestVote RPC:
Invoked by candidates to gather votes

Arguments:

term    candidate's term
candidateId candidate reqyesting vote
lastLogIndex    index of candidate's last log entry
lastLogTerm     term of candidate's last log entry

Result:

term    currentTerm, for candidate to update itself
voteGranted true means candidate received vote

Receiver implementation:

1. Reply false if term < currentTerm
2. If voteFor is null or candidateId, and candidate's log is at least as up-to-date as receiver's log, grant vote

AppendEntries RPC
Invoked by leader to replicate log entries; also used as heart beat

Argument:

term    leader's term
leaderId    so follower can redirect clients
prevLogIndex    index of log entry immediately preceding new ones

prevLogTerm term of prevLogIndex entry
entries[]   log entries to store(empty for heartbeat; may send more than one for efficiency)

leaderCommit    leader's commitIndex 

Results:

term    currentTerm, for leader to update itself
success     true if follower contained entry matching prevLogIndex and prevLogTerm

Receiver implementation:

1.Reply false if term < currentTerm
2.Reply false if log doesn't contain an entry at prevLogIndex whose term matches prevLogTerm
3.if an existing entry conflicts with a new one (same index but different terms), delete the existing entry and all that follow it
4.Appebd any new entries not already in the log 
5.If leaderCommit > commitIndex, set commitIndex = min(leaderCommit, index of last new entry)

Rules for Servers

All Servers:

• If commitIndex > lastApplied: increment lastApplied, apply log[lastAppied] to state machine
• If RPC request or response contains term T > currentTerm: set currentTerm = T, converetf to follower

Followers:

• Respond to RPCs from candidates and leaders
• If election timeout elapses without receiving AppendEntries RPC from current leader orr granting vote to candidate: convert to candidate

Candidates:

• On conversion to candidate, start election:

  • Increment currentTerm
  • Vote for self
  • Reset election timer
  • Send RequestVote RPCs to all other servers

• If votes received from majority of servers: become leader

• If AppendEntries RPC received from new leader: convert to follower

• If election timeout elapses: start new election

Leader:

• Upon election: send initial empty AppendEntries RPCs(heartbeat) to each server; repeat during idle periods to prevent election timeouts

• If command received from client: append entry to local log, respond after entry applied to state machine

• If last log index >= nextIndex for a follower: send AppendEntries PRC with log entries starting at next Index

  • If successful: update nextIndex and matchIndex for follower
  • If AppendEntries fails because of log inconsistency: decrement nextIndex and retry
  • If there exists an N such that N > commitIndex, amajority of matchIndex[i] >= N, and log[N].term == currentTerm: set commitIndex = N

Election Safety: at most one leader can be elected in a given term.
Leader Append-Only: a leader never overwrites or deletes entries in its log; ig only appends new entries.
Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.
Leader Completeness: if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms.
State Machine Safety: if a server has applied alog entry at a given index to its state machine, no other server will ever apply a different log entry for the same index