Support making atomic write requests idempotent

[empiredan]

Motivation

Pegasus does not support duplicating atomic write requests including incr, check_and_set and check_and_mutate since they are not idempotent. In practice, various applications use atomic write interfaces in many scenarios. However, such applications cannot use duplication to synchronize data, and therefore cannot benefit from the high performance that duplication provides.

Design

Due to the urgency of the requirements, the first version of the idempotent implementation for the atomic writes should be as simple as possible, without making fundamental changes to the write path.

Therefore, we decided to implement the idempotence of atomic write requests as follows: for each replica, ensure that only one atomic write request is being processed in the write pipeline at any given time. Once the replica server receives an atomic request, firstly it will be cached. It will not be pushed into the write pipeline until all requests before it have been applied. The write pipeline consists of the following stages:

1. read the current value from RocksDB, calculate the final value according to specific semantics of requested atomic write and build the idempotent request based on it;
2. append the corresponding mutation to plog;
3. broadcast the prepare requests to the secondary replicas;
4. apply the final result back to RocksDB ultimately.

The primary replicas have all 1 ~ 4 stages, and at last reply to the client while the secondary replicas only have stages 2 and 4.

Task List

Support idempotence in replica server

Make requests idempotent for incr, check_and_set and check_and_mutate

• [x] https://github.com/apache/incubator-pegasus/pull/2185
• [x] https://github.com/apache/incubator-pegasus/pull/2192
• [x] https://github.com/apache/incubator-pegasus/pull/2196
• [x] https://github.com/apache/incubator-pegasus/pull/2230
• [x] https://github.com/apache/incubator-pegasus/pull/2239
• [x] https://github.com/apache/incubator-pegasus/pull/2246
• [x] https://github.com/apache/incubator-pegasus/pull/2249

Infrastructure for idempotence

• [x] https://github.com/apache/incubator-pegasus/pull/2198
• [x] https://github.com/apache/incubator-pegasus/pull/2214
• [x] https://github.com/apache/incubator-pegasus/pull/2220
• [x] https://github.com/apache/incubator-pegasus/pull/2261

Support idempotence in meta server

• [x] https://github.com/apache/incubator-pegasus/pull/2205

Support idempotence in shell

• [x] https://github.com/apache/incubator-pegasus/pull/2221
• [x] https://github.com/apache/incubator-pegasus/pull/2229

Tests for idempotence

• [x] https://github.com/apache/incubator-pegasus/pull/2267