Transactions

[Hoverbear]

In general, the sender of a RemoteProcedureCall must have some way of identifying it's corresponding RemoteProcedureResponse.

We could use uuid::Uuid (as suggested by @manishearth) to uniquely identify a RemoteProcedureCall and RemoteProcedureResponse pair... But it's possibly unnecessary in some cases, see below.

General Implementation Details

A RemoteProcedureResponse::{Accepted, Rejected} is required:

• When a Follower is making an AppendEntries for their client (and is not part of the paper... be careful here!)
  • The Leader should not be attempting issue RequestVotes to it's Followers, it's already the leader. It will send AppendEntries to it's Followers to re-establish it's leadership.
  • The Follower will know the Leader sent this response by inspecting the source.
• When making a RequestVote. This, obviously, requires a response. Only the latest RequestVote must be tracked for each node.
• When the Leader is making a AppendEntries to the Followers. It requires a response so it knows when a majority of it's Followers have replicated the data.
• We use UDP, the protocol is specified to accommodate this, nothing depends on reliable communication. So we don't care if a RemoteProcedureResponse actually arrives. The requester will send another request soon after and it can be responded to appropriately.

  Handling Two Variants

  AppendEntries: Use a storage backing for entries

The paper states that the entries in a RaftNode should back their replicated log onto a persistent storage. The storage will be interfaced with via u64 indexes, and the items in the log are known to be RustcEncodable and RustcDecodable.

The protocol keeps the state of the last_applied and commit_index indices into the log. All indices before the commit_index are known to be committed to the backing storage.

Leader Implementation Details

• We don't necessarily care at the RemoteProcedureCall level, we care about the index level, as an AppendEntries call make have several entries (or none!) and some of them may be repeated indices we have already sent.
• The AppendEntries log items will always be contiguous and start from what the Leader thinks is the index of the next log entry the Follower does not yet have.
• The Leader tracks the index of the highest entry known to be replicated on each Follower.
• If a Follower issues an Accept of an AppendEntries it means that all entries up to that point have been successfully replicated (and thus confirmed).
• If a RemoteProcedureResponse is sent to the Leader and it's not received we will be sending another AppendEntries with the logs anyways, and the Follower will (hopefully) be able to respond to that.

  Follower Implementation Details

• Accepting the latest AppendEntries means that all entries before it are confirmed as well.
• Any RemoteProcedureResponses that fail to reach the Leader will have the corresponding logs resent, the storage backing needs to account for this.
• (Not in paper) If passing on an AppendEntries request to the Leader, we need some way to wait for (and identify) the appropriate response.

  RequestVote: Use a disposable data store.

This should be tracked by the Candidate state and disposed of afterwards, it's not persistent information and is only O(n) in storage, where n is the number of nodes. HashMaps has good performance in this setting and being able to lookup by u64 will be convenient.

Candidate Implementation Details

• Create a new enum Vote which has variants Polling, Accepted, Rejected
• Nodes can be uniquely identified via u64, and we will only send one RequestVote per term to a given node. However, a node might respond after we've started a new election, so we need to know if it's a stale vote. (I think... I did not catch anything in the paper about this.)
• Use a Vec<(Uuid, Transaction)> to track transactions. Keep it for the duration of the Candidate state of the Node. Probably stuff it into the enum variant.
  • We'll lookup based on the Node's ID which is u64. Then we check the Uuid is what we expect and bump the Transaction.

    Follower Implementation Details

• Respond appropriately to the RequestVote with a RemoteProcedureResponse.
• No need to track RequestVote calls.

[Hoverbear]

Woo!