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

• feat(make_idempotent): support making incr request idempotent in pegasus_write_service::impl #2185
• feat(make_idempotent): support making incr request idempotent in pegasus_write_service #2192
• feat(make_idempotent): support making incr request idempotent in pegasus_server_write and replication_app_base #2196
• feat(make_idempotent): support making check_and_set request idempotent in pegasus_write_service::impl #2230
• feat(make_idempotent): support making check_and_set request idempotent in pegasus_write_service #2239
• feat(make_idempotent): support making check_and_mutate request idempotent in pegasus_write_service::impl #2246
• feat(make_idempotent): re-adapt make_idempotent() and put() to support batched single-update requests for atomic writes #2249
• perf(make_idempotent): improve performance of idempotent writes by reducing deserialization and removing the mapping table for atomic write handlers #2261

Infrastructure for idempotence

• feat(make_idempotent): support making write requests idempotent for primary replicas #2198
• perf(make_idempotent): introduce row lock to improve 2PC for idempotent atomic writes #2214
• feat(make_idempotent): sync atomic_idempotent from meta server into .app-info file for each replica #2220

Support idempotence in meta server

• feat(make_idempotent): introduce new table-level APIs to meta servers to list/control idempotence for atomic writes #2205

Support idempotence in shell

• feat(make_idempotent): support atomic_idempotent for create and ls commands on shell #2221
• feat(make_idempotent): support getting/enabling/disabling atomic_idempotent on shell #2229

Tests for idempotence

• test(make_idempotent): support testing idempotent writes in function tests and add idempotent write test cases for incr requests #2267