Methods and systems for partitioning data in parallel processing systems

• US 20070226744A1
• Filed: 03/23/2006
• Published: 09/27/2007
• Est. Priority Date: 03/23/2006
• Status: Active Grant

• Current Assignee: Chicago Mercantile Exchange, Inc. (CME Group Incorporated), International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Callaway, Paul, Parr, Francis, Iyengar, Arun, Thiruthuvadoss, Agnes, Goldman, Stephen, Cutinho, Sunil, Dantzig, Paul
• Granted Patent: US 8,443,372 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Techniques are disclosed for processing requests in a data processing system. While the principles of the invention are not limited to a particular domain, they are particularly suitable for use in an electronic trading system. By way of example of one aspect of the invention, a method for directing requests to at least one node in a system comprising multiple nodes and a plurality of requests comprises associating a number to each request, assigning at least one number to each node so as to balance a load across the nodes, and sending a request to a node based on the number associated to the request. Various other aspects are disclosed.

Claims

1. A method for directing requests to at least one node in a system comprising multiple nodes and a plurality of requests, the method comprising the steps of:

associating a number to each request;

assigning at least one number to each node so as to balance a load across the nodes; and

sending a request to a node based on the number associated to the request.

2. The method of claim 1, further comprising the step of dynamically adjusting at least one number assigned to at least one node to improve a load balance across the nodes or to respond to a change in workload.

3. The method of claim 1, wherein the numbers comprise prices.

4. The method of claim 1, further comprising the step of storing information across the nodes based on the numbers.

5. The method of claim 1 further comprising the steps of:

the system receiving a large number of requests associated with a narrow number range; and

associating a node with at least part of the narrow number range and assigning a small quantity of numbers to the node to balance load.

6. A method for storing information across nodes in a system comprising multiple nodes, the method comprising the steps of:

assigning different prices to different parts of the information; and

storing the information across the nodes based on the prices.

7. The method of claim 6, further comprising the step of sending a request to one of the nodes based on a price associated with the request.

8. The method of claim 7, further comprising the step of storing the information so as to balance a request load across the nodes.

9. The method of claim 6, further comprising the step of dynamically adjusting at least one price assigned to at least one node so as to improve a load balance across the nodes or to respond to a change in workload.

10. The method of claim 7, further comprising the steps of:

the system receiving a large number of requests associated with a narrow price range; and

associating a node with at least part of the narrow price range and assigning a small number of prices to the node to balance load.

11. A method for balancing load across nodes in a system comprising multiple nodes, the method comprising the steps of:

storing multiple data objects among the plurality of nodes; and

in response to a node becoming overloaded, migrating at least one data object from the overloaded node to a second node.

12. The method of claim 11, further comprising the steps of:

maintaining an estimate of load associated with each data object; and

selecting the at least one data object to migrate based on the estimates of load.

13. The method of claim 12, wherein the estimate of load associated with each data object is correlated with a frequency with which a data object is accessed or a frequency with which transactions associated with a data object are received.

14. A method for balancing load across nodes in a system comprising multiple nodes and multiple data objects, the method comprising the steps of:

maintaining an estimate of load associated with each data object; and

using the estimates of load associated with each data object to store the data objects among the plurality of nodes so as to balance load among the nodes.

15. The method of claim 14, wherein the data objects are stored among the nodes so that sums of estimates of load for data objects stored on a particular node are similar across all nodes.

16. The method of claim 14, wherein the estimate of load associated with each data object is correlated with a frequency with which a data object is accessed or a frequency with which transactions associated with a data object are received.

17. The method of claim 14, further comprising the step of, in response to a node becoming overloaded, migrating at least one data object from the overloaded node to a second node.

18. The method of claim 14, wherein at least one data object comprises at least one of:

(i) a portion of an order book relating to one or more financial instruments; and

(ii) a substantially whole order book relating to one or more financial instruments.

19. The method of claim 14, wherein the system comprises an electronic trading system.

20. The method of claim 14, wherein the maintaining step and the using step are implementable in accordance with a machine readable medium containing one or more programs which when executed implement said steps.