Lightweight redundancy tool for performing transactions

Patent metadata

Field	Value
Publication number	US-11334552-B2
Application number	US-201715795930-A
Country	US
Kind code	B2
Filing date	Oct 27, 2017
Priority date	Jul 31, 2017
Publication date	May 17, 2022
Grant date	May 17, 2022

Abstract

Systems, methods, and non-transitory computer readable media are provided for providing a redundancy tool for performing transactions. A transaction to be performed on a data stored in a database may be received. A timestamp may be assigned to the transaction. A lock may be assigned on the timestamp. The transaction may be performed on the data. The lock may be refreshed while performing the transaction on the data. A validity of the lock may be checked at after performing the transaction on the data. Responsive to the lock being valid, a result of performing the transaction on the data may be committed.

First claim

The invention claimed is:

1. A system comprising:
one or more processors;
memory storing instructions that, when executed by the one or more processors, cause the system to perform:
receiving, by a first set of service nodes, a first transaction of a plurality of transactions to be performed on data stored in a database, wherein the first set of service nodes is assigned to perform the first transaction, and a second set of service nodes is assigned to perform a second transaction of the plurality of transactions; selecting a number of dedicated timelock nodes that reduces a number of service nodes in at least one of the first set of service nodes or the second set of service nodes by one or more nodes;
receiving, by a first dedicated timelock node of a set of dedicated timelock nodes and from a first service node of the first set of service nodes, a request for a first timestamp, wherein each of the dedicated timelock nodes of the set of timelock nodes executes a respective timestamp service capable of determining and assigning timestamps for each of the plurality of transactions, and wherein the set of dedicated timelock nodes is designated to perform the respective timestamp services on behalf of and in lieu of the first set of service nodes and the second set of service nodes;
receiving, by the first dedicated timelock node, from a second service node of the second set of service nodes, a request for a second timestamp, wherein the request for the first timestamp and the request for the second timestamp are overlapping timestamp requests;
determining, in response to receiving the request for the first timestamp and based on a first majority consensus of the respective timestamp services of the set of dedicated timelock nodes, a value of the first timestamp;
determining, in response to receiving the request for the second timestamp and based on a second majority consensus of the respective timestamp services of the set of dedicated timelock nodes, a value of the second timestamp, wherein the first timestamp and the second timestamp are not monotonically increasing;
assigning, in response to determining the value of the first timestamp, the first timestamp to the first transaction;
assigning, in response to determining the value of the second timestamp, the second timestamp to the second transaction;
assigning a lock on the first timestamp, wherein assignment of the lock on the first timestamp indicates a validity of the first transaction for a time period during which the lock is held on the first timestamp;
performing the first transaction on the data;
refreshing the lock while performing the first transaction on the data;
determining that the first transaction is valid based on the refreshed lock held on the first timestamp; and
based at least in part on determining that the first transaction is valid, committing a result of performing the first transaction on the data.

2. The system of claim 1 , wherein the instructions further cause the system to perform:
responsive to the lock being invalid, removing the result of performing the first transaction on the data.

3. The system of claim 1 , wherein the lock is assigned on the first timestamp based on the set of dedicated timelock nodes.

4. The system of claim 1 , wherein the first transaction is performed by a second service node of the first set of service nodes while the first service node provides the request for the first timestamp to the first dedicated timelock node of the set of dedicated timelock nodes.

5. The system of claim 3 , wherein the set of dedicated timelock nodes includes a leader timelock node.

6. The system of claim 1 , wherein the first timestamp is assigned based on an order in which the first transaction is received with respect to the second transaction of the plurality of transactions.

7. A method implemented by a computing system including one or more processors and storage media storing machine-readable instructions, wherein the method is performed using the one or more processors, the method comprising:
receiving, by a first set of service nodes, a first transaction of a plurality of transactions to be performed on data stored in a database, wherein the first set of service nodes is assigned to perform the first transaction, and a second set of service nodes is assigned to perform a second transaction of the plurality of transactions;
selecting a number of dedicated timelock nodes;
based at least in part on the selected number of dedicated timelock nodes, reducing a number of service nodes in at least one of the first set of service nodes or the second set of service nodes by one or more nodes;
receiving, by a first dedicated timelock node of a set of dedicated timelock nodes from a first service node of the first set of service nodes, a request for a timestamp, wherein each of the dedicated timelock nodes executes a respective timestamp service capable of determining and assigning timestamps for each of the plurality of transactions, and wherein the set of dedicated timelock nodes is designated to perform the respective timestamp services on behalf of and in lieu of the first set of service nodes and the second set of service nodes;
receiving, by the first dedicated timelock node, from a second service node of the second set of service nodes, a request for a second timestamp, wherein the request for the first timestamp and the request for the second timestamp are overlapping timestamp requests;
determining, in response to receiving the request and based on a first majority consensus of the respective timestamp services of the set of dedicated timelock nodes, a value of the first timestamp;
determining, in response to receiving the request for the second timestamp and based on a second majority consensus of the respective timestamp services of the set of dedicated timelock nodes, a value of the second timestamp, wherein the first timestamp and the second timestamp are not monotonically increasing;
assigning, in response to determining the value of the first timestamp, the first timestamp to the first transaction;
assigning, in response to determining the value of the second timestamp, the second timestamp to the second transaction;
assigning a lock on the first timestamp, wherein assignment of the lock on the first timestamp indicates a validity of the first transaction for a time period during which the lock is held on the first timestamp;
performing the first transaction on the data;
refreshing the lock while performing the first transaction on the data;
determining that the first transaction is valid based on the refreshed lock held on the first timestamp; and
based at least in part on determining that the first transaction is valid, committing a result of performing the first transaction on the data.

8. The method of claim 7 , further comprising:
responsive to the lock being invalid, removing the result of performing the first transaction on the data.

9. The method of claim 7 , wherein the lock is assigned on the first timestamp based on the set of dedicated timelock nodes.

10. The method of claim 7 , wherein the first transaction is performed by a second service node of the first set of service nodes while the first service node provides the request for the first timestamp to the first dedicated timelock node of the set of dedicated timelock nodes.

11. The method of claim 9 , wherein the set of dedicated timelock nodes includes a leader timelock node.

12. The method of claim 7 , wherein the first timestamp is assigned based on an order in which the first transaction is received with respect to the second transaction of the plurality of transactions.

Assignees

• Palantir Technologies Inc

Inventors

• Grabham Benjamin
• Biddle Henry
• Kong Jeremy
• Lea Joseph
• Elliot Mark
• Chang Allen
• Carrino John

Classifications

• G06F16/2343 Primary

  Locking methods, e.g. distributed locking or locking implementation details · CPC title

• G06F16/1774

  Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files · CPC title

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title

• G06F9/466

  Transaction processing · CPC title

• G06F16/2322

  using timestamps · CPC title