Paxos issue

  • Hard to understand
  • Difficult to build
    • Why collect log independently and combine?
    • Why peer-to-peer?

Implementation

Raft2.png
Raft3.png
Raft4.png

  • ^ If a majority has one entry of the current term
    Raft5.png

State

  • Leader
    • Transfer to follower if see higher term
  • Follower
    • issue no RPC
  • Candidate

Joint consensus

  • Log entries replicated to all servers (across both configurations)
  • Any server may be leader
  • Agreement require majorities from both old and new config
  • First commit $C_{old,new}$ then commit $C_{new}$
  • Additional phase for new servers to catch up
  • Leader steps down if not in $C_{new}$
  • Ignore removed server’s RequestVote if receive real leader’s heartbeat

Snapshot

  • Snapshot independently on clients
    • Snapshot and delete old log
  • Leader can send snapshots to lagging clients

Client

  • Prevent invoking same command
    • Add unique id form each command in log
  • Read only op?
    • Leader commit noop to make sure which logs are committed
    • Also check if it is still the leader

In Class

  • Appealing Properties
    • Simplify state space
      • Logs cannot have holes
      • Randomized timeout
  • State
    • 1 Leader, N-1 followers, 0 Candidates
  • Term
    • identify obsolete information
  • Heartbeats
    • Followers need to know leader is alive
    • Servers start up as followers
    • Followers expect to receive RPCs from leader or candidate
    • Leaders must send heartbeats to maintain authority
      • (empty AppendEntry RPC)
    • IF election timeout elapse with no RPCS
      • Follower assumes leader has crashed start new election
  • Election
    • Increment current term
    • Change to Candidate state
    • Vote for self
    • Send RequestVote
    • Safety: Allow at most one winner per term
    • Liveness: Some candidate must eventually win
  • Log entry
    • Log entry = index, term, command
  • One RPC round trip