Dynamic balancing of operations by selecting subsets of nodes

Patent metadata

Field	Value
Publication number	US-10757181-B1
Application number	US-201815980591-A
Country	US
Kind code	B1
Filing date	May 15, 2018
Priority date	Mar 14, 2018
Publication date	Aug 25, 2020
Grant date	Aug 25, 2020

Abstract

Systems, methods, and non-transitory computer readable media are provided for load balancing of operations. A set of operation nodes may be run. The set of operation nodes may include operation nodes configured to perform operations. A set of clients that uses one or more of the operations may be identified. Loads of operations associated with the set of clients may be determined. Subsets of operation nodes to be assigned to subsets of clients may be identified based on the loads of operations associated with the set of clients. The subsets of operation nodes may include a given subset of operation nodes to be assigned to a given subset of clients. The subsets of operation nodes may be assigned to the subsets of clients such that the given subset of operation nodes is assigned to perform one or more of the operations for the given subset of clients.

First claim

The invention claimed is:

1. A system comprising:
one or more processors;
a memory storing instructions that, when executed by the one or more processors, cause the system to perform:
running a set of operation nodes, the set of operation nodes including operation nodes configured to perform operations;
identifying a set of clients that uses one or more of the operations;
determining loads of operations associated with the set of clients;
identifying subsets of operation nodes to be assigned to subsets of clients based on the loads of operations associated with the set of clients, comprising:
determining a cost from obtaining a consensus among the subsets of operation nodes during one or more operations of the subsets of clients; and
identifying subsets of operation nodes to be assigned to subsets of clients based on the determined cost,

the subsets of operation nodes including a given subset of operation nodes to be assigned to a given subset of clients; and
assigning the subsets of operation nodes to the subsets of clients such that the given subset of operation nodes is assigned to perform one or more of the operations for the given subset of clients.

2. The system of claim 1 , wherein the loads of operations are determined based on historical operation usage information for the set of clients.

3. The system of claim 2 , wherein the historical operation usage information includes information relating to request rates, processing loads, and latency measurements of historical operation usage by the set of clients.

4. The system of claim 1 , wherein the operations include assigning a timestamp to a transaction associated with a given client, assigning a lock on the timestamp, refreshing the lock on the timestamp during execution of the transaction, and removing the lock on the timestamp.

5. The system of claim 4 , wherein one or more of the operations are performed by the given subset of operation nodes based on a consensus of operation nodes within the given subset of operation nodes.

6. The system of claim 4 , wherein the transaction is facilitated by a transaction layer built on top of a key value store.

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:
running a set of operation nodes, the set of operation nodes including operation nodes configured to perform operations;
identifying a set of clients that uses one or more of the operations;
determining loads of operations associated with the set of clients;
identifying subsets of operation nodes to be assigned to subsets of clients based on the loads of operations associated with the set of clients, comprising:
determining a cost from obtaining a consensus among the subsets of operation nodes during one or more operations of the subsets of clients; and
identifying subsets of operation nodes to be assigned to subsets of clients based on the determined cost,

the subsets of operation nodes including a given subset of operation nodes to be assigned to a given subset of clients; and
assigning the subsets of operation nodes to the subsets of clients such that the given subset of operation nodes is assigned to perform one or more of the operations for the given subset of clients.

8. The method of claim 7 , wherein the loads of operations are determined based on historical operation usage information for the set of clients.

9. The method of claim 8 , wherein the historical operation usage information includes information relating to request rates, processing loads, and latency measurements of historical operation usage by the set of clients.

10. The method of claim 7 , wherein the operations include assigning a timestamp to a transaction associated with a given client, assigning a lock on the timestamp, refreshing the lock on the timestamp during execution of the transaction, and removing the lock on the timestamp.

11. The method of claim 10 , wherein one or more of the operations are performed by the given subset of operation nodes based on a consensus of operation nodes within the given subset of operation nodes.

12. The method of claim 10 , wherein the transaction is facilitated by a transaction layer built on top of a key value store.

13. A non-transitory computer readable medium comprising instructions that, when executed, cause one or more processors to perform:
running a set of operation nodes, the set of operation nodes including operation nodes configured to perform operations;
identifying a set of clients that uses one or more of the operations;
determining loads of operations associated with the set of clients;
identifying subsets of operation nodes to be assigned to subsets of clients based on the loads of operations associated with the set of clients, comprising:
determining a cost from obtaining a consensus among the subsets of operation nodes during one or more operations of the subsets of clients; and
identifying subsets of operation nodes to be assigned to subsets of clients based on the determined cost,

the subsets of operation nodes including a given subset of operation nodes to be assigned to a given subset of clients; and
assigning the subsets of operation nodes to the subsets of clients such that the given subset of operation nodes is assigned to perform one or more of the operations for the given subset of clients.

14. The non-transitory computer readable medium of claim 13 , wherein the loads of operations are determined based on historical operation usage information for the set of clients.

15. The non-transitory computer readable medium of claim 14 , wherein the historical operation usage information includes information relating to request rates, processing loads, and latency measurements of historical operation usage by the set of clients.

16. The non-transitory computer readable medium of claim 13 , wherein the operations include assigning a timestamp to a transaction associated with a given client, assigning a lock on the timestamp, refreshing the lock on the timestamp during execution of the transaction, and removing the lock on the timestamp.

17. The non-transitory computer readable medium of claim 16 , wherein one or more of the operations are performed by the given subset of operation nodes based on a consensus of operation nodes within the given subset of operation nodes.

18. The system of claim 1 , wherein the subsets of operation nodes to be assigned to subsets of clients are identified further based on whether any of the clients or any of the operation nodes is suspended, and wherein the cost is determined based on a latency of a timelock operation.

19. The system of claim 1 , wherein the subsets of operation nodes to be assigned to subsets of clients are identified further based on a size of the subsets of operation nodes and a size of the subsets of clients.

20. The system of claim 1 , wherein the instructions further cause the system to perform:
selecting an operation node of the subsets of operation nodes to be a leader for provision of timestamps and timelock.

Assignees

• Palantir Technologies Inc

Inventors

• Kong Jeremy
• Boam Thomas
• Hero Robert

Classifications

• H04L67/60

  Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources (admission control or resource allocation H04L47/70) · CPC title

• H04L67/104

  Peer-to-peer [P2P] networks · CPC title

• G06F16/2322 Primary

  using timestamps · CPC title

• G06F16/2343

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

• H04L67/1031 Primary

  Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests · CPC title