Distributed transactions across multiple consensus groups

Patent metadata

Field	Value
Publication number	US-12216679-B2
Application number	US-201916403341-A
Country	US
Kind code	B2
Filing date	May 3, 2019
Priority date	Feb 4, 2016
Publication date	Feb 4, 2025
Grant date	Feb 4, 2025

Abstract

Methods, systems, and computer-readable media for distributed transactions across multiple consensus groups are disclosed. A distributed transaction system comprises a proposer and a plurality of consensus groups, including a first consensus group comprising a first plurality of members and a second consensus group comprising a second plurality of members. The proposer proposes a transaction to at least a portion of the first consensus group and at least a portion of the second consensus group. A majority of the members in the first consensus group agree to perform the transaction, where the transaction is selected from a plurality of proposed transactions involving the first consensus group. A majority of the members in the second consensus group also agree to perform the transaction. The members of the first and second consensus groups perform the transaction to update a plurality of stored replicas.

First claim

What is claimed is:

1. A system, comprising:
a plurality of computing devices configured to implement a distributed transaction system operating on a data set, the distributed transaction system comprising a proposer and a plurality of consensus groups including a first consensus group comprising a first plurality of members storing respective replicas of the data set and a second consensus group comprising a second plurality of members storing respective replicas of the data set, wherein individual ones of the plurality of consensus groups participate in different respective subsets of a plurality of transactions operating on the data set, wherein the proposer, the first plurality of members, and the second plurality of members implement a consensus protocol, and wherein the distributed transaction system is configured to:
send, from the proposer to at least a portion of the first consensus group and at least a portion of the second consensus group, a prepare-transaction request for a transaction, wherein a transaction group for the transaction comprises the first consensus group and the second consensus group, wherein the prepare-transaction describes the transaction comprising one or more data updates to be performed by individual members of the transaction group, and wherein a positive response to the prepare-transaction request by an individual member of the transaction group indicates acceptance of the transaction by the individual member; and
perform the transaction comprising the one or more data updates of the transaction on the data set based at least in part on one or more positive responses to the prepare-transaction request, wherein at least some of the one or more positive responses identify an additional transaction, and wherein to perform the one or more data updates of the transaction the distributed transaction system is configured to:
determine, based at least in part on the one or more positive responses to the prepare-transaction request as part of the consensus protocol, that the identified additional transaction, different from the transaction, has been accepted by a particular consensus group of the transaction group, wherein the acceptance locks the particular consensus group from performance of the transaction, wherein the additional transaction involves another transaction group comprising the particular consensus group and one or more additional consensus groups of the plurality of consensus groups; and
unlock, responsive to the determining, performance of the transaction for the particular consensus group, wherein to unlock performance of the transaction the distributed transaction system is configured to send an abort-transaction request of the additional transaction as part of the consensus protocol from the proposer to the particular consensus group of the transaction group.

2. The system as recited in claim 1 , wherein the prepare-transaction request, the one or more positive responses to the prepare-transaction request, and the abort-transaction request are sent using the consensus protocol and without centralized coordination external to the proposer and the first and second consensus groups.

3. The system as recited in claim 1 , wherein the additional transaction is chosen based at least in part on a transaction number for the additional transaction being higher than a transaction number for the transaction.

4. The system as recited in claim 1 , wherein the prepare-transaction request comprises data identifying individual members in the first and second consensus groups to which the prepare-transaction request is sent.

5. A computer-implemented method, comprising:
performing, by a plurality of computing devices that collectively implement a distributed transaction system operating on a data set and comprising a proposer and a plurality of consensus groups including a first consensus group comprising a first plurality of members storing respective replicas of the data set and a second consensus group comprising a second plurality of members storing respective replicas of the data set:
sending, from the proposer to at least a portion of the first consensus group and at least a portion of the second consensus group as part of a consensus protocol, a prepare-transaction request for a transaction, wherein a transaction group for the transaction comprises the first consensus group and the second consensus group, wherein the first consensus group and the second consensus group respectively participate in different respective subsets of a plurality of transactions, including the transaction, operating on the data set, wherein the prepare-transaction describes the transaction comprising one or more data updates to be performed by individual members of the transaction group, and wherein a positive response to the prepare-transaction request by an individual member of the transaction group indicates acceptance of the transaction by the individual member; and
performing the transaction comprising the one or more data updates of the transaction on the data set based at least in part on one or more positive responses to the prepare-transaction request, wherein at least some of the one or more positive responses identify an additional transaction of the plurality of transactions, and wherein the performing comprises:
determining, based at least in part on one or more positive responses to the prepare-transaction request as part of the consensus protocol, that the identified additional transaction, different from the transaction, has been accepted by a particular consensus group of the transaction group, wherein the acceptance locks the particular consensus group from performance of the transaction, wherein the additional transaction involves another transaction group comprising the particular consensus group and one or more additional consensus groups of the plurality of consensus groups; and
unlocking, responsive to the determining, performance of the transaction for the particular consensus group, comprising sending an abort-transaction request of the additional transaction as part of the consensus protocol from the proposer to the particular consensus group of the transaction group.

6. The method as recited in claim 5 , wherein the prepare-transaction request, the one or more responses to the prepare-transaction request, and the abort-transaction request are sent using the consensus protocol and without centralized coordination external to the proposer and the first and second consensus groups.

7. The method as recited in claim 5 , wherein the additional transaction is chosen based at least in part on a transaction number for the additional transaction being higher than a transaction number for the transaction.

8. The method as recited in claim 5 , further comprising:
sending, from a second proposer to at least a portion of a third consensus group and at least a portion of a fourth consensus group, a second prepare-transaction request for a second transaction, wherein the second prepare-transaction request comprises a second transaction number, wherein the third consensus group comprises a third plurality of members and the fourth consensus group comprises a fourth plurality of members, wherein the second proposer and the third plurality of members and the fourth plurality of members implement the consensus protocol;
sending, from a majority of the third consensus group to the second proposer, but not from a majority of the fourth consensus group, positive responses to the second prepare-transaction request; and
retrying the second transaction using a third prepare-transaction request comprising a third transaction number, wherein the third transaction number is higher than the second transaction number.

9. The meth

Assignees

• Amazon Tech Inc

Inventors

• Chen Tao
• Jain Divya Ashok Kumar
• Ping Fan
• Brooker Marc John

Classifications

• G06F16/273 Primary

  Asynchronous replication or reconciliation · CPC title