System and method for distributing data in a parallel processing system

• US 7,873,650 B1
• Filed: 06/11/2004
• Issued: 01/18/2011
• Est. Priority Date: 06/11/2004
• Status: Active Grant

• Current Assignee: LexisNexis Risk Data Management, Inc. (RELX PLC)
• Original Assignee: Seisint, Inc.
• Inventors: Halliday, Gavin C., Poulsen, Ole D., Bayliss, David A., Hicks, Nigel G., Cobbett-Smith, Jacob, Chapman, Richard K.
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Bibbee; Jared M
• Application Number:
  US10/866,620
• Time in Patent Office: 2,412 Days
• Field of Search: 707/100, 707/104.1, 707/764, 707/797
• US Class Current: 707/764
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A parallel-processing system that is capable of dynamically creating a distributed tree for distributing data. The system includes a plurality of first nodes. Each of the plurality of first nodes is capable of establishing a connection with at least one of the plurality of first nodes to form at least a portion of a dynamically created distribution tree. The system also includes a second node that is capable of receiving data for distribution within the parallel-processing system. The second node is also capable of establishing a connection with at least two of the plurality of first nodes. In this particular embodiment, the second node and the plurality of first nodes operate to form the dynamically created distribution tree. Moreover, the second node also operates to distribute the data to each of the plurality of first nodes through the dynamically created distribution tree.

Claims

1. A parallel-processing system, including memory and at least one processor, capable of dynamically creating a distributed tree for distributing data to the parallel-processing system, comprising:

a plurality of child master nodes operable to;

establish connections among the plurality of child master nodes, and

distribute a received pre-compiled query to the plurality of child master nodes; and

a plurality of parent master nodes operable to;

receive the pre-compiled query from a client for distribution within the parallel-processing system,

identify at least two child master nodes allocated to the parent master node for the dynamically created distribution tree,

establish connections with the identified at least two child nodes to form the dynamically created distribution tree,

receive from the identified at least two child master nodes polling information,

determine, based on the received polling information, a percentage of master nodes in the parallel-processing system that are connected to the dynamically created distribution tree,

determine whether the percentage of master nodes in the parallel-processing system connected to the dynamically created distribution tree is above a threshold percentage, and

responsive to a determination that the percentage of master nodes in the parallel-processing system connected to the distribution tree is above the threshold percentage, pre-key the identified at least two child nodes by distributing the pre-compiled query to the identified at least two child master nodes,

wherein the connections between the plurality of parent master nodes and the identified at least two child master nodes operate to form the dynamically created distribution tree,

the identified at least two child master nodes operate to further distribute the pre-compiled query to additional master nodes through the dynamically created distribution tree, and

the pre-compiled query is distributed in advance of a user providing a request to the parallel-processing system.

2. The system of claim 1, wherein each of the plurality of child master nodes is capable of distributing the data to one or more slave nodes.

3. The system of claim 1, wherein the plurality of parent master nodes are capable of distributing the data to one or more slave nodes.

4. The system of claim 1, wherein each of the plurality of parent master nodes is allocated one or more of the plurality of child master nodes to connect with when forming the dynamically created distributed tree.

5. The system of claim 4, wherein each of the plurality of parent master nodes has access to an index that identifies the allocated connections within the dynamically created tree.

6. The system of claim 1, wherein the plurality of parent master nodes operate to communicate a request for the polling information to the identified child master nodes.

7. The system of claim 1, wherein the pre-compiled query operates to resolve routine data requests that are capable of having variations in input parameters.

8. The system of claim 1, wherein the pre-compiled query comprises an annotated query execution graph and one or more executables.

16. The parallel-processing system of claim 1, wherein the threshold percentage is about 50%.

9. A computer-implemented method for distributing data within a parallel-processing system including a plurality of parent master nodes and a plurality of child master nodes, the method performed by at least one of the parent master nodes and comprising:

receiving a pre-complied query representation for distribution within the parallel-processing system;

dynamically creating a distribution tree for distributing the precompiled query within the parallel-processing system, comprising;

identifying at least two of the plurality of child master nodes allocated to the parent master node for the dynamically created distribution tree; and

establishing connections with the identified at least two child master nodes to form at least a portion of a dynamically created distribution tree;

receiving from the identified at least two child master nodes polling information;

determining, based on the received polling information, a percentage of master nodes in the parallel-processing system that are connected to the dynamically created distribution tree;

determining whether the percentage of master nodes in the parallel processing system connected to the dynamically created distribution tree is above a threshold percentage; and

when it is determined that the percentage of master nodes in the parallel processing system connected to the dynamically created distribution tree is above the threshold percentage, pre-keying the identified at least two child master nodes by distributing to the identified at least two child master nodes the pre-compiled query,

wherein the connections between the at least one parent master node and the identified at least two child master nodes operate to form the dynamically created distribution tree, and

the at least one parent master node and the identified at least two child master nodes operate to store the pre-compiled query in advance of a user providing a request to the parallel-processing system.

10. The method of claim 9, wherein the dynamic creation of the distributed tree further comprises communicating a request for the polling information to the identified at least two child master nodes.

11. The method of claim 9, wherein the plurality of parent master nodes and the plurality of child master nodes are capable of distributing the pre-complied query to one or more slave nodes.

12. The method of claim 9, wherein the plurality of parent master nodes are allocated one or more of the plurality of child master nodes to connect with when forming the dynamically created distributed tree.

13. The method of claim 12, wherein the plurality of parent master nodes have access to an index that identifies allocated connections within the dynamically created tree.

14. The method of claim 9, further comprising distributing the pre-complied query to the plurality of child master nodes through the dynamically created distribution tree.

17. The method of claim 9, wherein the threshold percentage is about 50%.

15. A system for dynamically creating a distribution tree for distributing data within a parallel-processing system including a plurality of parent master nodes and a plurality of child master nodes, the system comprising:

one or more computer processors associated with at least one of the plurality of parent master nodes operable to;

receive a pre-complied query representation for distribution within the parallel-processing system;

create the dynamic distribution tree, including;

identifying at least two of the plurality of child master nodes allocated to the at least one parent master node for the dynamically created distribution tree;

establishing connections with the identified at least two child master nodes to form at least a portion of a dynamically created distribution tree;

receiving from the identified at least two child master nodes polling information;

determining, based on the received polling information, a percentage of master nodes in the parallel-processing system that are connected to the dynamically created distribution tree;

determining whether the percentage of master nodes in the parallel-processing system connected to the dynamically created distribution tree is above a threshold percentage; and

in response to a determination that the percentage of master nodes in the parallel-processing system connected to the dynamically created distribution tree is above the threshold percentage, pre-keying the identified at least two child master nodes by distributing to the identified at least two child nodes the pre-compiled query,

wherein the connections between the at least one parent master node and the identified at least two child master nodes operate to form the dynamically created distribution tree, and

the at least one parent master node and the identified at least two child master nodes operate to store the pre-compiled query in advance of a user providing a request to the parallel-processing system.

18. The system of claim 15, wherein the threshold percentage is about 50%.