Granted Patent B2

US 12,298,966 · App. 18/418,097 · Granted May 13, 2025

Inventors: Graham Timothy Pople (Manchester, GB); Brett Phillip James Lawson (Surrey, CA); Matthew William Ingenthron (Huntington Beach, CA); David John Finlay (Mountain View, CA); Shivani Gupta (Irvine, CA); John Sae Liang (Palo Alto, CA); Stephen Ching-Sing Yen (Atherton, CA)

G06F16/2379G06F9/547G06F16/215G06F16/27

Abstract

Claims (80)

1. A non-transitory computer-readable storage medium for storing instructions that, when executed by a computer processor, cause the computer processor to perform steps comprising:

receiving a first request to execute a first transaction from a first client system at a database node of a distributed database system, the transaction describing a mutation of a record stored at the database node, wherein the record is associated with a check-and-set (CAS) value that is updated responsive to modifications to the record;

retrieving the record from the database node and sending the record to the first client system, causing the first client system to identify the CAS value from the received record;

receiving a second request to execute a second transaction from a second client system at the database node of the distributed database system;

retrieving the record from the database node and sending the record to the second client system, causing the second client system to identify the CAS value from the received record;

receiving a request from the first client system or the second client to attempt to stage a first mutation of the record based on the first transaction or a second mutation of the record based on the second transaction, the request comprising the CAS value received by the first client system or the second client system;

detecting whether a mismatch between the CAS value received with the request and a current CAS value of the record is present, the mismatch indicating that an additional mutation corresponding to an additional transaction has been staged for the record at the database node, the additional mutation conflicting with the first mutation or the second mutation corresponding to the request received from the first client system or the second client system;

responsive to detecting the mismatch, aborting the attempt to execute the first transaction or the second transaction corresponding to the request received from the first client system or the second client system; and

responsive to detecting no mismatch,

staging the first mutation or the second mutation corresponding to the request received from the first client system or the second client system; and

causing the CAS value associated with the record to be updated to a different CAS value.

2. The non-transitory computer-readable storage medium of claim 1 , wherein aborting execution of the transaction comprises:

modifying an active transaction record (ATR) entry for the transaction in an ATR on the distributed database system to indicate the transaction is in an aborted state.

3. The non-transitory computer-readable storage medium of claim 1 , wherein staging the first mutation or the second mutation comprises:

modifying active transaction record (ATR) entry for the transaction in an ATR on the distributed database system to indicate the transaction is in a changing state.

4. The non-transitory computer-readable storage medium of claim 1 , wherein the CAS value is stored with the record at the database node.

5. The non-transitory computer-readable storage medium of claim 1 , wherein the distributed database system comprises a second database node, and the steps further comprise:

receiving a third request to execute a third transaction from a third client system at the second database node of the distributed database system;

retrieving the from the second database node and sending the record to the third client system, causing the third client system to identify the CAS value from the received record;

receiving a request from the third client system to attempt to stage a third mutation of the record based on the third transaction, the request comprising the CAS value received by the third client system;

detecting whether a mismatch between the CAS value received with the request and a current CAS value of the record is present, the mismatch indicating that an additional mutation corresponding to an additional transaction has been staged for the record at the database node, the additional mutation conflicting with the first mutation or the second mutation corresponding to the request received from the first client system or the second client system;

responsive to detecting the mismatch, aborting the attempt to execute the third transaction;

responsive to detecting no mismatch,

staging the third mutation; and

causing the CAS value associated with the record to be updated to a different CAS value.

6. The non-transitory computer-readable storage medium of claim 1 , wherein aborting the attempt further comprises rolling back the attempt to execute the first transaction or the second transaction corresponding to the received request.

7. The non-transitory computer-readable storage medium of claim 6 , wherein staging the first mutation or the second mutation comprises generating a hidden record on the database node, and wherein rolling back the attempt to execute the first transaction or the second transaction further comprises:

removing the hidden record from the database node.

8. The non-transitory computer-readable storage medium of claim 1 , wherein the steps further comprise:

after aborting the attempt to execute the transaction, determining if the transaction has not expired; and

responsive to determining the transaction has not expired, reattempting to execute the transaction at the database node.

9. The non-transitory computer-readable storage medium of claim 8 , wherein reattempting to execute the transaction comprises:

delaying the reattempt to execute that transaction by a randomized time period.

10. The non-transitory computer-readable storage medium of claim 8 , wherein reattempting comprises reattempting for a threshold number of times.

11. A computing system comprising:

one or more processors; and

a non-transitory computer-readable storage medium for storing instructions that when executed by the one or more processors cause the one or more processors to perform steps comprising:

receiving a first request to execute a first transaction from a first client system at a database node of a distributed database system, the transaction describing a mutation of a record stored at the database node, wherein the record is associated with a check-and-set (CAS) value that is updated responsive to modifications to the record;

retrieving the record from the database node and sending the record to the first client system, causing the first client system to identify the CAS value from the received record;

receiving a second request to execute a second transaction from a second client system at the database node of the distributed database system;

retrieving the record from the database node and sending the record to the second client system, causing the second client system to identify the CAS value from the received record;

receiving a request from the first client system or the second client to attempt to stage a first mutation of the record based on the first transaction or a second mutation of the record based on the second transaction, the request comprising the CAS value received by the first client system or the second client system;

detecting whether a mismatch between the CAS value received with the request and a current CAS value of the record is present, the mismatch indicating that an additional mutation corresponding to an additional transaction has been staged for the record at the database node, the additional mutation conflicting with the first mutation or the second mutation corresponding to the request received from the first client system or the second client system;

responsive to detecting the mismatch, aborting the attempt to execute the first transaction or the second transaction corresponding to the request received from the first client system or the second client system; and

responsive to detecting no mismatch,

staging the first mutation or the second mutation corresponding to the request received from the first client system or the second client system; and

causing the CAS value associated with the record to be updated to a different CAS value.

12. The computing system of claim 11 , wherein aborting execution of the transaction comprises:

modifying an active transaction record (ATR) entry for the transaction in an ATR on the distributed database system to indicate the transaction is in an aborted state.

13. The computing system of claim 11 , wherein staging the first mutation or the second mutation comprises:

modifying active transaction record (ATR) entry for the transaction in an ATR on the distributed database system to indicate the transaction is in a changing state.

14. The computing system of claim 13 , wherein the CAS value is stored with the record at the database node.

15. The computing system of claim 11 , wherein the distributed database system comprises a second database node, and the steps further comprises:

receiving a third request to execute a third transaction from a third client system at the second database node of the distributed database system;

retrieving the from the second database node and sending the record to the third client system, causing the third client system to identify the CAS value from the received record;

receiving a request from the third client system to attempt to stage a third mutation of the record based on the third transaction, the request comprising the CAS value received by the third client system;

detecting whether a mismatch between the CAS value received with the request and a current CAS value of the record is present, the mismatch indicating that an additional mutation corresponding to an additional transaction has been staged for the record at the database node, the additional mutation conflicting with the first mutation or the second mutation corresponding to the request received from the first client system or the second client system;

responsive to detecting the mismatch, aborting the attempt to execute the third transaction;

responsive to detecting no mismatch,

staging the third mutation; and

causing the CAS value associated with the record to be updated to a different CAS value.

16. The computing system of claim 11 , wherein aborting the attempt further comprises rolling back the attempt to execute the first transaction or the second transaction corresponding to the received request.

17. The computing system of claim 11 , wherein staging the first mutation or the second mutation comprises generating a hidden record on the database node, and wherein rolling back the attempt to execute the first transaction or the second transaction further comprises:

removing the hidden record from the database node.

18. The computing system of claim 11 , wherein the steps further comprise:

after aborting the attempt to execute the transaction, determining if the transaction has not expired; and

responsive to determining the transaction has not expired, reattempting to execute the transaction at the database node.

19. The computing system of claim 11 , wherein reattempting to execute the transaction comprises:

delaying the reattempt to execute that transaction by a randomized time period.

20. A method comprising:

receiving a first request to execute a first transaction from a first client system at a database node of a distributed database system, the transaction describing a mutation of a record stored at the database node, wherein the record is associated with a check-and-set (CAS) value that is updated responsive to modifications to the record;

retrieving the record from the database node and sending the record to the first client system, causing the first client system to identify the CAS value from the received record;

receiving a second request to execute a second transaction from a second client system at the database node of the distributed database system;

retrieving the record from the database node and sending the record to the second client system, causing the second client system to identify the CAS value from the received record;

receiving a request from the first client system or the second client to attempt to stage a first mutation of the record based on the first transaction or a second mutation of the record based on the second transaction, the request comprising the CAS value received by the first client system or the second client system;

detecting whether a mismatch between the CAS value received with the request and a current CAS value of the record is present, the mismatch indicating that an additional mutation corresponding to an additional transaction has been staged for the record at the database node, the additional mutation conflicting with the first mutation or the second mutation corresponding to the request received from the first client system or the second client system;

responsive to detecting the mismatch, aborting the attempt to execute the first transaction or the second transaction corresponding to the request received from the first client system or the second client system; and

responsive to detecting no mismatch,

staging the first mutation or the second mutation corresponding to the request received from the first client system or the second client system; and

causing the CAS value associated with the record to be updated to a different CAS value.

Assignments (2)

Continuity (3)

References Cited (58)