Maelstrom Distributed Systems Workbench

When a node becomes a candidate, it must broadcast a request_vote RPC to all other nodes in the cluster.

The request_vote message body should include:

• type: 'request_vote'
• term: The candidate's current term
• candidate_id: The ID of the candidate
• last_log_index: The index of the candidate's last log entry
• last_log_term: The term of the candidate's last log entry

Nodes should also implement a maybe_step_down!(remote_term) check: if a received message contains a term higher than the current term, the node must advance its term and transition to the :follower state.

# Request that other nodes vote for us as a leader.
def request_votes!
  @lock.synchronize do
    votes = Set.new [@node.node_id]
    term = @term

    @node.brpc!(
      type: 'request_vote',
      term: term,
      candidate_id: @node.node_id,
      last_log_index: @log.size,
      last_log_term: @log.last[:term]
    ) do |res|
      @lock.synchronize do
        body = res[:body]
        maybe_step_down! body[:term]
        if @state == :candidate && @term == term && @term == body[:term] && body[:vote_granted]
          votes << res[:src]
          @node.log "Have votes: #{votes}"
        end
      end
    end
  end
end

Leaders must periodically replicate unacknowledged log entries to followers using append_entries RPCs. This process also serves as a heartbeat mechanism.

Replication Logic

1. Check Timing: Only replicate if the node is a :leader and @min_replication_interval has elapsed.
2. Determine Entries: For each peer, determine the next index to send (@next_index[node]) and retrieve entries from the log using Log#from_index.
3. Send RPC: If there are new entries or if the @heartbeat_interval has passed, send an append_entries RPC containing:
   • type: 'append_entries'
   • term: current term
   • leader_id: current node ID
   • prev_log_index: ni - 1
   • prev_log_term: term of the entry at ni - 1
   • entries: the slice of log entries
   • leader_commit: current @commit_index
4. Handle Response:
   • If success is true: Advance @next_index[node] and @match_index[node] to the new end of the replicated segment.
   • If success is false: Decrement @next_index[node] and retry.
   • If the response contains a higher term, the leader must step down.

  def replicate_log!(force)
    @lock.synchronize do
      elapsed_time = Time.now - @last_replication
      replicated = false
      term = @term

      if @state == :leader and @min_replication_interval < elapsed_time
        @node.other_node_ids.each do |node|
          ni = @next_index[node]
          entries = @log.from_index ni

          if 0 < entries.size or @heartbeat_interval < elapsed_time
            @node.log "Replicating #{ni}+ to #{node}"
            replicated = true

            @node.rpc!(node, {
              type:           'append_entries',
              term:           @term,
              leader_id:      @node.node_id,
              prev_log_index: ni - 1,
              prev_log_term:  @log[ni - 1][:term],
              entries:        entries,
              leader_commit:  @commit_index
            }) do |res|
              body = res[:body]
              @lock.synchronize do
                maybe_step_down! body[:term]
                if @state == :leader and body[:term] == @term
                  reset_step_down_deadline!
                  if body[:success]
                    @next_index[node] = [@next_index[node], (ni + entries.size)].max
                    @match_index[node] = [@match_index[node], (ni + entries.size - 1)].max
                    @node.log "Next index: #{@next_index}"
                  else
                    @next_index[node] -= 1
                  end
                end
              end
            end
          end
        end
      end

      if replicated
        @last_replication = Time.now
      end
    end
  end

To improve request success rates, implement a mechanism where nodes proxy client requests to the known leader instead of failing.

1. Maintain a @leader variable in the Raft state.
2. Reset @leader to nil on state transitions (e.g., become_follower!, become_candidate!, become_leader!).
3. Update @leader when receiving an append_entries request from a valid leader.
4. In the client request handler (client_req!), if the current node is not the leader but @leader is set, use @node.rpc! to proxy the request to the leader.

# Example of proxying logic in client_req!
def client_req!(msg)
  @lock.synchronize do
    if @state == :leader
      # ... handle as leader
    elsif @leader
      # Proxy to the known leader
      @node.rpc! @leader, msg[:body] do |res|
        @node.reply! msg, res[:body]
      end
    else
      raise RPCError.temporarily_unavailable "not a leader"
    end
  end
end