Page Comparison

Reliable conditional write guarantee's correct behavior

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.

...

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. (Use window similar 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.