Linearizability

Warning: these are design notes from initial stages of LogCabin and are are probably not relevant any longer.

Append RPCs should be linearizable: the illusion that each operation takes effect instantaneously at some point between its invocation and response. Unlike ZooKeeper, we don't want a "you got disconnected from the leader, I don't know if your request went through, you're on your own" error, because that's not always easy for applications to deal with.

The client will assign each of its operations that modify the database a unique (client ID, transaction ID) pair. The client ID can be assigned uniquely by the current leader. The transaction IDs should start at 1 and increment. For every client ID, the servers will maintain the response to its latest transaction ID in a hash table. If a second request with the same (client ID, transaction ID) is processed, it will take no effect, and its response will be that found in the hash table.

This hash table will be cleaned very slowly. If a client talks to a server that is unaware of its client ID, this is because the client has been offline for too long; the client will be instructed to crash.

What about multi-threaded clients or clients doing asynchronous requests?