Reliable conditional write

Problem:

Conditional write RPC on Ramcloud returns the result by success or failure of the conditional write.
The flow of control of the client may depend on the result of conditional write.

If the master fails between succeeding the conditional write and responding back to client the result, current Ramcloud RPC protocol thinks the request was not delivered to client and retries the conditional write. In that case, recovered master already contains the new version of value (after the conditional write) and the retried request will be rejected since the version number doesn't match. Here, the correct response value should be success since the conditional write RPC was already done before the crash.

To handle this problem, I propose the following design.

In a client,

1. Each RPC gets assigned for a unique rpc_id. (Unique within a client)
2. As client receives the response from master, it logs it. (Similar to TCP)
3. Each RPC from client contains the highest ACK number for the rpc_id.

In a master server,

1. Log in master now contains <Client id, RPC id, ACK id>
2. A master keeps an array of processed_lists <Client id, <list of rpc id pairs>> (See figure 1)
3. As a new RPC comes in, the master checks the rpc_id is inside the processed_list. If it is, just return success. If it isn't, process the rpc as normal.

When a crash happens

1. When a recovery server replay's its log, it reconstructs the processed table by following rpc_id and ack_id in log elements.

Log cleaner

1. When a tombstone is found, for each log regarding the object,
   
   1. if recent ack_id of its client is higher than rpc_id of the log element, delete the whole log element.
   2. if it is lower than rpc_id, just delete object in log and compact. Leave metadata <table_id, keyHash> and <client_id, rpc_id, ack_id>.

Figure 1. Processed table: Each master keeps processed_lists for each client. The processed_list tracks the processed rpc_id (only not yet ACKed) by keeping sequence start and end.

Figure 2. Log structure with RPC id and ACK id.