Light weight redundancy tool for performing transactions

Patent metadata

Field	Value
Publication number	US-11914569-B2
Application number	US-202217746644-A
Country	US
Kind code	B2
Filing date	May 17, 2022
Priority date	Jul 31, 2017
Publication date	Feb 27, 2024
Grant date	Feb 27, 2024

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 dedicated timelock node of dedicated timelock nodes, a request for one or more first timestamps, wherein the dedicated timelock nodes comprise a leader node and a non-leader node;
if the first dedicated timelock node is the non-leader node, assigning the request to the leader node;
writing, by the leader node to a datastore, an upper bound for the request;
determining that the leader node has failed during issuing of the one or more first timestamps;
in response to determining that the leader node has failed, reassigning the non-leader node as a new leader node; and
completing, by the new leader node, issuing of one or more first second timestamps, based on the upper bound;
receiving an indication that the leader node has returned to an operational status;
in response to receiving the indication, reassigning the new-leader node back to a non-leader node; and
completing, by the leader node, issuing of the one or more first timestamps and one or more third timestamps.

2. The system of claim 1 , wherein the instructions further cause the system to perform:
reserving, by the non-leader node, a range of timestamps defined by the upper bound; and
issuing, by the non-leader node, a first timestamp from the reserved range of timestamps.

3. The system of claim 1 , wherein the determining that the leader node has failed comprises determining that the leader node has entered a garbage collection cycle.

4. The system of claim 1 , wherein the determining that the leader node has failed comprises determining that the leader node has entered a sleep cycle.

5. The system of claim 1 , wherein the instructions further cause the system to perform:
assigning, based on a first consensus among the dedicated timelock nodes, a lock on the first timestamp; and
removing, based on a second consensus among the dedicated timelock nodes, the lock on the first timestamp.

6. The system of claim 1 , wherein the one or more first timestamps correspond to an operation comprising a data import, export, or modification, and the one or more third timestamps correspond to a result of the operation.

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 dedicated timelock node of dedicated timelock nodes, a request for one or more first timestamps, wherein the dedicated timelock nodes comprise a leader node and a non-leader node;
if the first dedicated timelock node is the non-leader node, assigning the request to the leader node;
writing, by the leader node to a datastore, an upper bound for the request;
determining that the leader node has failed during issuing of the one or more first timestamps;
in response to determining that the leader node has failed, reassigning the non-leader node as a new leader node; and
completing, by the new leader non leader node, the issuing of one or more second timestamps, based on the upper bound;
receiving an indication that the leader node has returned to an operational status;
in response to receiving the indication, reassigning the new-leader node back to a non-leader node; and
completing, by the leader node, issuing of the one or more first timestamps and one or more third timestamps.

8. The method of claim 7 , further comprising:
reserving, by the non-leader node, a range of timestamps defined by the upper bound; and
issuing, by the non-leader node, a first timestamp from the reserved range of timestamps.

9. The method of claim 7 , wherein the determining that the leader node has failed comprises determining that the leader node has entered a garbage collection cycle.

10. The method of claim 7 , wherein the determining that the leader node has failed comprises determining that the leader node has entered a sleep cycle.

11. The method of claim 7 , further comprising:
assigning, based on a first consensus among the dedicated timelock nodes, a lock on the first timestamp; and
removing, based on a second consensus among the dedicated timelock nodes, the lock on the first timestamp.

12. The method of claim 7 , wherein the one or more first timestamps correspond to an operation comprising a data import, export, or modification, and the one or more third timestamps correspond to a result of the operation.

13. A non-transitory computer readable medium comprising instructions that, when executed, cause one or more processors to perform:
receiving, by a first dedicated timelock node of dedicated timelock nodes, a request for one or more first timestamps, wherein the dedicated timelock nodes comprise a leader node and a non-leader node;
if the first dedicated timelock node is the non-leader node, assigning the request to the leader node;
writing, by the leader node to a datastore, an upper bound for the request;
determining that the leader node has failed during issuing of the one or more first timestamps;
in response to determining that the leader node has failed, reassigning the non-leader node as a new leader node; and
completing, by the new leader non leader node, the issuing of one or more second timestamps, based on the upper bound;
receiving an indication that the leader node has returned to an operational status;
in response to receiving the indication, reassigning the new-leader node back to a non-leader node; and
completing, by the leader node, issuing of the one or more first timestamps and one or more third timestamps.

14. The non-transitory computer readable medium of claim 13 , wherein the instructions further cause the one or more processors to perform:
reserving, by the non-leader node, a range of timestamps defined by the upper bound; and
issuing, by the non-leader node, a first timestamp from the reserved range of timestamps.

15. The non-transitory computer readable medium of claim 13 , wherein the determining that the leader node has failed comprises determining that the leader node has entered a garbage collection cycle.

16. The system of claim 1 , wherein the leader node is a leader for provision of timestamps, and the non-leader node is selected as a leader for provision of timelocks.

17. The system of claim 16 , wherein when the non-leader node becomes the new leader node, a different node besides the new leader node and the leader node is selected as a leader for provision of timestamps.

18. The system of claim 1 , wherein the first timestamps have a lower value than the second timestamps even though the first timestamps were issued at a later time compared to the second timestamps.

Assignees

• Palantir Technologies Inc

Inventors

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

Classifications

• G06F16/2308 Primary

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F9/466

  Transaction processing · CPC title

• G06F16/1774

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

• G06F16/2315

  Optimistic concurrency control · CPC title

• G06F16/2322

  using timestamps · CPC title