Support duplicated requests

[akiradeveloper]

$6.3 of the Raft author's thesis describes at-least-semantics which is not suitable for real use.

The figure below well explains the problem: What if the leader is dead before response and the client "re"send the request to other node? The expectation is that the new leader responds with ok as leader transition has been done "transparently".

I have no clue about the implementation detail so I made a question to community but no answer yet. So here I describe the implementation detail which is now in my mind.　

My idea exploits replication. It wraps RaftStorage with thin layer so to attach new attributes (client_id, seq_num) in each entry. This way, the log entry will be logically (clock, command, client_id, seq_num) but the persistent layer only holds the two in front. (because it is too nonsense to have such temporary attributes in disks) Then the attributes are replicated to followers.

Now, servers find the relationship index -> (client_id, seq_num). When a server applies command(index) then it can memoize (client_id, seq_num) -> response but only the first time. In the second time, it "skips" application and responds with the memoized response.

[akiradeveloper]

// This saved in RaftStorage
struct Entry0 {
  // (Term, Index)
  clock: Clock,
  // Command to execute in RaftApp
  command: Bytes,
}

// This is replicated among servers
struct Entry {
  clock: Clock,
  command: Bytes,
  // request of this command
  client_id: String,
  // the sequence number of this command
  seq_num: u64,
}

[akiradeveloper]

A table (client_id, seq_num) -> response is maintained in the servers but can erase once responded to the client.

here is a pseudo code:

in applying Entry
  command_key = (client_id, seq_num)
  if not resp_table.contains(command_key)
    resp = app.exec(command)
    resp_table.insert(command_key, resp)
  if let Some(completion) = completions.contains(command_index)
    completion.complete_with(resp)
    send(self, RemoveResponse { command_key })

in committing RemoveResponse { command_key }
  resp_table.remove(command_key)

[akiradeveloper]

Done.

The writer request to the cluster now has a request_id which should be unique to the request.

message WriteRequest {
  bytes message = 1;
  // unique identifier of this request
  // duplicated requests with the same unique identifier are only executed once.
  string request_id = 2;
}

The server can distinguish two requests with the request_id and if the two have the same one, they are executed only once.

For the deduplication, the application now has a response cache

    response_cache: spin::Mutex<HashMap<String, Bytes>>,

which memoizes the response data with the request_id as a key.