Granted Patent B2

US 11,334,552 · App. 15/795,930 · Granted May 17, 2022

Inventors: Benjamin Grabham (London, GB); Henry Biddle (London, GB); Jeremy Kong (London, GB); Joseph Lea (London, GB); Mark Elliot (New York, NY); Allen Chang (Sunnyvale, CA); John Carrino (Menlo Park, CA)

Assignee: Palantir Technologies Inc.

G06F16/2308G06F9/466G06F16/1774G06F16/2322G06F16/2343G06F16/2379

Abstract

Claims (67)

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.

13. The method of claim 7 , wherein the lock is stored in random access memory.

14. The method of claim 7 , further comprising:

reserving, by a leader dedicated timelock node, a range of timestamps;

writing, by the leader dedicated timelock node, an upper bound for the range of timestamps to a persistent data store prior to issuing the first timestamp; and

issuing, by the leader dedicated timelock node, the first timestamp from the reserved range of timestamps.

15. A non-transitory computer readable medium comprising instructions that, when executed, cause one or more processors 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;

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 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 first 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;

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.

16. The non-transitory computer readable medium of claim 15 , wherein the instructions further cause the one or more processors to perform:

responsive to the lock being invalid, removing the result of performing the first transaction on the data.

17. The non-transitory computer readable medium of claim 15 , wherein the lock is assigned on the first timestamp based on the set of dedicated timelock nodes.

18. The non-transitory computer readable medium of claim 15 , 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.

19. The non-transitory computer readable medium of claim 17 , wherein the set of dedicated timelock nodes includes a leader timelock node.

Assignments (8)

Continuity (2)