[Tarantool-patches] [RFC] Quorum-based synchronous replication
Konstantin Osipov
kostja.osipov at gmail.com
Fri Apr 17 13:10:17 MSK 2020
* sergos at tarantool.org <sergos at tarantool.org> [20/04/15 17:51]:
> ### Quorum commit
This part looks correct. It only describes two paths out of many
though:
- leader is able to collect the majority
- leader is not able to collect the majority
What happens when a leader receives a message for a round which is
complete?
How does a replica which missed a round catch up?
What happens if replica fails to apply txn 1 (e.g. because of a
duplciate key), but confirms txn 2?
What happens if txn1 gets no majority at the leader, but txn 2
gets a majority? How are the followers rolled back?
> The main idea behind the proposal is to reuse existent machinery as much
> as possible. It will ensure the well-tested and proven functionality
> across many instances in MRG and beyond is used. The transaction rollback
> mechanism is in place and works for WAL write failure. If we substitute
> the WAL success with a new situation which is named 'quorum' later in
> this document then no changes to the machinery is needed. The same is
> true for snapshot machinery that allows to create a copy of the database
> in memory for the whole period of snapshot file write. Adding quorum here
> also minimizes changes.
>
> Currently replication represented by the following scheme:
> ```
> Customer Leader WAL(L) Replica WAL(R)
> |------TXN----->| | | |
> | | | | |
> | [TXN Rollback | | |
> | created] | | |
> | | | | |
> | |-----TXN----->| | |
> | | | | |
> | |<---WAL Ok----| | |
> | | | | |
> | [TXN Rollback | | |
> | destroyed] | | |
> | | | | |
> |<----TXN Ok----| | | |
> | |-------Replicate TXN------->| |
> | | | | |
> | | | [TXN Rollback |
> | | | created] |
> | | | | |
> | | | |-----TXN----->|
> | | | | |
> | | | |<---WAL Ok----|
> | | | | |
> | | | [TXN Rollback |
> | | | destroyed] |
> | | | | |
> ```
>
> To introduce the 'quorum' we have to receive confirmation from replicas
> to make a decision on whether the quorum is actually present. Leader
> collects necessary amount of replicas confirmation plus its own WAL
> success. This state is named 'quorum' and gives leader the right to
> complete the customers' request. So the picture will change to:
> ```
> Customer Leader WAL(L) Replica WAL(R)
> |------TXN----->| | | |
> | | | | |
> | [TXN Rollback | | |
> | created] | | |
> | | | | |
> | |-----TXN----->| | |
> | | | | |
> | |-------Replicate TXN------->| |
> | | | | |
> | | | [TXN Rollback |
> | |<---WAL Ok----| created] |
> | | | | |
> | [Waiting | |-----TXN----->|
> | of a quorum] | | |
> | | | |<---WAL Ok----|
> | | | | |
> | |<------Replication Ok-------| |
> | | | | |
> | [Quorum | | |
> | achieved] | | |
> | | | | |
> | [TXN Rollback | | |
> | destroyed] | | |
> | | | | |
> | |---Confirm--->| | |
> | | | | |
> | |----------Confirm---------->| |
> | | | | |
> |<---TXN Ok-----| | [TXN Rollback |
> | | | destroyed] |
> | | | | |
> | | | |---Confirm--->|
> | | | | |
> ```
>
> The quorum should be collected as a table for a list of transactions
> waiting for quorum. The latest transaction that collects the quorum is
> considered as complete, as well as all transactions prior to it, since
> all transactions should be applied in order. Leader writes a 'confirm'
> message to the WAL that refers to the transaction's LSN and it has its
> own LSN. This confirm message is delivered to all replicas through the
> existing replication mechanism.
>
> Replica should report a positive or a negative result of the TXN to the
> leader via the IPROTO explicitly to allow leader to collect the quorum
> or anti-quorum for the TXN. In case a negative result for the TXN is
> received from minor number of replicas, then leader has to send an error
> message to the replicas, which in turn have to disconnect from the
> replication the same way as it is done now in case of conflict.
>
> In case leader receives enough error messages to do not achieve the
> quorum it should write the 'rollback' message in the WAL. After that
> leader and replicas will perform the rollback for all TXN that didn't
> receive quorum.
>
> ### Recovery and failover.
>
> Tarantool instance during reading WAL should postpone the commit until
> the 'confirm' is read. In case the WAL eof is achieved, the instance
> should keep rollback for all transactions that are waiting for a confirm
> entry until the role of the instance is set. In case this instance
> become a replica there are no additional actions needed, since all info
> about quorum/rollback will arrive via replication. In case this instance
> is assigned a leader role, it should write 'rollback' in its WAL and
> perform rollback for all transactions waiting for a quorum.
>
> In case of a leader failure a replica with the biggest LSN with former
> leader's ID is elected as a new leader.
As long as multi-master is not banned, there may be multiple
leaders. Does this proposal suggest multi-master is banned? Then
it should describe the implementation of this, and in absense of
transparent query forwarding it will break all clients.
> The replica should record
> 'rollback' in its WAL which effectively means that all transactions
> without quorum should be rolled back. This rollback will be delivered to
> all replicas and they will perform rollbacks of all transactions waiting
> for quorum.
>
> An interface to force apply pending transactions by issuing a confirm
> entry for them have to be introduced for manual recovery.
>
> ### Snapshot generation.
>
> We also can reuse current machinery of snapshot generation. Upon
> receiving a request to create a snapshot an instance should request a
> readview for the current commit operation. Although start of the
> snapshot generation should be postponed until this commit operation
> receives its confirmation. In case operation is rolled back, the snapshot
> generation should be aborted and restarted using current transaction
> after rollback is complete.
>
> After snapshot is created the WAL should start from the first operation
> that follows the commit operation snapshot is generated for. That means
> WAL will contain 'confirm' messages that refer to transactions that are
> not present in the WAL. Apparently, we have to allow this for the case
> 'confirm' refers to a transaction with LSN less than the first entry in
> the WAL.
>
> In case master appears unavailable a replica still have to be able to
> create a snapshot. Replica can perform rollback for all transactions that
> are not confirmed and claim its LSN as the latest confirmed txn. Then it
> can create a snapshot in a regular way and start with blank xlog file.
> All rolled back transactions will appear through the regular replication
> in case master reappears later on.
>
> ### Asynchronous replication.
>
> Along with synchronous replicas the cluster can contain asynchronous
> replicas. That means async replica doesn't reply to the leader with
> errors since they're not contributing into quorum. Still, async
> replicas have to follow the new WAL operation, such as keep rollback
> info until 'quorum' message is received. This is essential for the case
> of 'rollback' message appearance in the WAL. This message assumes
> replica is able to perform all necessary rollback by itself. Cluster
> information should contain explicit notification of each replica
> operation mode.
>
> ### Synchronous replication enabling.
>
> Synchronous operation can be required for a set of spaces in the data
> scheme. That means only transactions that contain data modification for
> these spaces should require quorum. Such transactions named synchronous.
> As soon as last operation of synchronous transaction appeared in leader's
> WAL, it will cause all following transactions - matter if they are
> synchronous or not - wait for the quorum. In case quorum is not achieved
> the 'rollback' operation will cause rollback of all transactions after
> the synchronous one. It will ensure the consistent state of the data both
> on leader and replicas. In case user doesn't require synchronous operation
> for any space then no changes to the WAL generation and replication will
> appear.
>
> Cluster description should contain explicit attribute for each replica
> to denote it participates in synchronous activities. Also the description
> should contain criterion on how many replicas responses are needed to
> achieve the quorum.
>
> ## Rationale and alternatives
>
> There is an implementation of synchronous replication as part of gh-980
> activities, still it is not in a state to get into the product. More
> than that it intentionally breaks backward compatibility which is a
> prerequisite for this proposal.
>
>
--
Konstantin Osipov, Moscow, Russia
More information about the Tarantool-patches
mailing list