Network-independent programming model for online processing in distributed systems

• US 9,185,156 B2
• Filed: 02/14/2013
• Issued: 11/10/2015
• Est. Priority Date: 11/13/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Marty, Michael Roger, Kidd, Nicholas Andrew, Fontoura, Marcus, Acknin, Charles
• Primary Examiner(s): Gillis, Brian J
• Assistant Examiner(s): Lee, Gil H.
• Application Number:
  US13/767,286
• Publication Number:
  US 20140136590A1
• Time in Patent Office: 999 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

Systems and methods include a distributed system that uses a declarative language to separate application logic from the network technology used to communicate. For example, in a system with a plurality of processing nodes, each processing node may include at least one processor, a networking layer for communicating with other processing nodes, and a memory storing instructions that, when executed by the at least one processor, cause the processing node to perform operations. The operations may include receiving a processing plan using the networking layer and analyzing the processing plan to determine a service to perform and a number of inputs anticipated for the service. The operations may also include performing the determined service. The processing plan defines a processing tree comprising a subset of the plurality of processing nodes, the processing tree having unidirectional communication from the root to a final level of the tree.

Claims

1. A system comprising:

a memory storing a plurality of processing plans, each processing plan including of a series of operations to be performed, each operation including;

a service, and

an indication of at least one of a plurality of processing nodes for performing the service,

wherein at least one operation of the series of operations, also includes an indication of one or more inputs representing an output of another operation of the series of operations;

a first node of the plurality of nodes, wherein the first node includes at least one processor and a memory storing instructions that, when executed by the at least one processor, cause the first node to;

select a particular processing plan from the memory, and

distribute the particular processing plan to second nodes of the plurality of processing nodes, the second nodes being identified in at least one first operation of the particular processing plan, the first operation having no indication of a previous operation; and

the plurality of processing nodes, each processing node including at least one processor and a memory storing instructions that, when executed by the at least one processor, cause the processing node to;

receive a processing plan of the plurality of processing plans,

determine an anticipated number of inputs, each input being identified in the processing plan as an output from a previous operation,

determine whether the anticipated number of inputs has been received, and

perform the service indicated in the first operation of the received processing plan when it is determined that the anticipated number of inputs have been received.

2. The system of claim 1, each of the plurality of nodes including a networking layer for communicating the processing plans between the processing nodes.

3. The system of claim 1, wherein as part of determining whether the anticipated number of inputs has been received and performing the service, each of the plurality of nodes is further configured to:

determine whether a predetermined amount of time has passed prior to receiving the anticipated number of inputs; and

perform the service indicated with the received inputs when it is determined that the predetermined amount of time has passed.

4. The system of claim 1, wherein at least one of the operations in the series of operations in the received processing plan includes a partial service and, as part of performing the service, each of the plurality of nodes is further configured to:

perform the partial service using each of the anticipated inputs to create an output; and

use the output of the partial service as input to the service indicated in the received processing plan.

5. The system of claim 1, wherein the instructions, when executed by the at least one processor, cause the second processing nodes to perform the operations of:

receiving the particular processing plan from the first node;

executing the service indicated in the first operation to generate a particular output;

identifying at least one later operation identifying the first operation; and

sending the particular processing plan and the particular output to third processing nodes identified in the at least one later operation.

6. The system of claim 5, wherein the instructions, when executed by the at least one processor, cause the second processing nodes to perform the operations of:

removing at least one operation from the processing plan to generate a modified processing plan; and

sending the modified processing plan with the output to the third processing nodes.

7. The system of claim 5, wherein the second nodes are configured to begin execution of the service concurrently.

8. The system of claim 5, wherein as part of executing the service indicated in the first operation, at least one of the second processing nodes initiates another processing plan.

9. The system of claim 8, wherein as part of initiating the another processing plan, the at least one of the second processing nodes appends additional steps to the particular processing plan.

10. The system of claim 9, wherein as part of initiating the another processing plan, the at least one of the second processing nodes modifies the indication of the one or more inputs of the later operation in the processing plan.

11. The system of claim 1, wherein the first node is configured to send the processing plan to the second nodes without receiving an acknowledgement from the second nodes.

12. A computer-implemented method comprising:

receiving a processing plan at a processing node, the processing plan including a series of operations to be performed, each operation including;

a service for the operation, and

an indication of one or more processing nodes for performing the service,

wherein at least one operation also includes an indication of a prior operation, so that the at least one operation uses an output of the prior operation as input;

determine an anticipated number of inputs for a particular operation, the particular operation identifying the processing node in the processing plan, each input being identified in the processing plan as an output from a previous operation;

determine whether the anticipated number of inputs has been received;

performing a service indicated in the particular operation at the processing node when the anticipated number of inputs has been received;

determining a next operation based on the processing plan, the next operation having an indication of the particular operation; and

sending the processing plan from the processing node to another processing node, the another processing node being identified in the next operation.

13. The method of claim 12, wherein the series of operations is an array of operations and the indication of a prior operation is an index into the array.

14. The method of claim 12, wherein the processing plan includes a partial service and the method further comprises performing the partial service on an input as it arrives at the processing node, prior to performing the service.

15. The method of claim 12, wherein the processing plan specifies that the processing nodes are replicated and performing the service further comprises:

cancelling the performing of the service at other processing nodes identified in the particular operation after completion of the service.

16. The method of claim 12, wherein the operations of the processing plan are stored in reverse topological order.

17. The method of claim 16, wherein the method further comprises:

pruning operations occurring after the next operation from the processing plan prior to sending the processing plan to the another processing node.

18. The method of claim 12, wherein the processing node sends the processing plan to the another processing node without expecting a reply from the another processing node as a result of the another processing node performing the service indicated in the next operation.

19. The method of claim 12, wherein the indication of the one or more processing nodes in the processing plan is a naming service.

20. The method of claim 12, wherein the indication of the one or more processing nodes in at least one operation of the processing plan represents a plurality of processing nodes.

21. A distributed processing system comprising:

a plurality of processing nodes, each processing node including;

at least one processor,

a networking layer for communicating with other processing nodes of the plurality of processing nodes; and

a memory storing instructions that, when executed by the at least one processor cause the processing node to;

use the networking layer to receive a processing plan that includes a series of operations to be performed,

analyze the processing plan to determine a service to perform and a number of inputs anticipated for the service, each input being identified in the processing plan as an output of a previous operation, and

perform the service when the anticipated number of inputs has been received,

wherein the processing plan defines a processing tree comprising a subset of the plurality of processing nodes, the processing tree having unidirectional communication from the root to a final level of the tree.

22. The system of claim 21, wherein the distributed processing system includes a root node, the root node including:

at least one processor,

a networking layer for communicating with the plurality of processing nodes; and

a memory storing instructions that, when executed by the at least one processor cause the root node to;

select the processing plan,

send the processing plan to a next node using the networking layer, the next node being a child of the root node in the processing tree,

wherein the next node performs a service indicated by the processing plan.

23. The system of claim 21, wherein as part of performing the service the memory of at least one processing node further includes instructions that, when executed by the at least one processor, cause the at least one processing node to initiate execution of another processing plan, the another processing plan providing an output to children of the at least one processing node, the children being determined by the processing tree.

24. The system of claim 21, wherein as part of analyzing the processing plan the memory further includes instructions that, when executed by the at least one processor, cause the processing node to:

determine a partial service to perform;

perform the partial service on the anticipated inputs as they arrive; and

use output of the partial service as input for the service.

25. The system of claim 21, wherein as part of performing the service the memory further includes instructions that, when executed by the at least one processor, cause the processing node to:

determine whether a predetermined amount of time has passed prior to receiving a first input of the anticipated number of inputs; and

perform the service without receiving the first input.