From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-f67.google.com (mail-lf1-f67.google.com [209.85.167.67]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 9EA894696C3 for ; Fri, 17 Apr 2020 13:10:19 +0300 (MSK) Received: by mail-lf1-f67.google.com with SMTP id g10so908715lfj.13 for ; Fri, 17 Apr 2020 03:10:19 -0700 (PDT) Date: Fri, 17 Apr 2020 13:10:17 +0300 From: Konstantin Osipov Message-ID: <20200417101017.GA17411@atlas> References: <20200403210836.GB18283@tarantool.org> <20200414125848.GA1249@pony.bronevichok.ru> <20200414144308.GC1734@tarantool.org> <6105DEEE-7332-4A14-B56E-A89D4B107D56@tarantool.org> <4CD8ED86-38D9-4564-89EF-935AF74F29A6@tarantool.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <4CD8ED86-38D9-4564-89EF-935AF74F29A6@tarantool.org> Subject: Re: [Tarantool-patches] [RFC] Quorum-based synchronous replication List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: "sergos@tarantool.org" Cc: =?utf-8?B?0J3QuNC60L7Qu9Cw0Lkg0JrQsNGA0LvQvtCy?= , Mons Anderson , tarantool-patches@dev.tarantool.org, =?utf-8?B?0KLQuNC80YPRgCDQodCw0YTQuNC9?= * sergos@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