Ordered processing of groups of messages
First Claim
1. A computer system for processing data using messages, comprising:
- a plurality of independent, asynchronous processing nodes, the processing nodes comprising one or more computer programs running on one or more computers, the processing nodes interconnected in a manner represented by a directed graph;
wherein the plurality of processing nodes includes a first node configured to output groups of messages; and
wherein the plurality of processing nodes includes a second node configured to process messages within a group of messages output by the first node in order;
wherein the second node comprises;
a buffer in memory for storing messages in a group of messages;
an input queue in memory for storing other messages;
a buffer manager configured to;
detect whether an input message is in a group of messages, andif the message is in a group of messages, then determine whether the message is a parent node, andif the message is not a parent node, then place the message in the buffer, andif the message is a parent node, then determine the number of child nodes and place the message in the buffer.
2 Assignments
0 Petitions
Accused Products
Abstract
A highly parallel, asynchronous data flow processing system in which processing is represented by a directed graph model, can include processing nodes that generate, and process, groups of dependent messages and that process messages within such groups in order. Other messages can be processed in whatever order they are received by a processing node. To identify a group of dependent messages, message identifiers are applied to a message. Processing of a message may generate child messages. A child message is assigned a message identifier that incorporates the associated message identifier of the parent message. The message identifier of the parent message is annotated to indicate the number of related child messages. When a group of messages is to be processed by a processing node in order, the processing node maintains a buffer in which messages in the group are stored. When a message is received, its message identifier indicates whether it is in a group, its parent node, if any, and the number of child nodes it has if it is a parent node. From this information, it can be determined whether all messages within the group have been received. When all of the messages within the group have been received, the processing node can process the messages in order.
-
Citations
15 Claims
-
1. A computer system for processing data using messages, comprising:
-
a plurality of independent, asynchronous processing nodes, the processing nodes comprising one or more computer programs running on one or more computers, the processing nodes interconnected in a manner represented by a directed graph; wherein the plurality of processing nodes includes a first node configured to output groups of messages; and wherein the plurality of processing nodes includes a second node configured to process messages within a group of messages output by the first node in order; wherein the second node comprises; a buffer in memory for storing messages in a group of messages; an input queue in memory for storing other messages; a buffer manager configured to; detect whether an input message is in a group of messages, and if the message is in a group of messages, then determine whether the message is a parent node, and if the message is not a parent node, then place the message in the buffer, and if the message is a parent node, then determine the number of child nodes and place the message in the buffer. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer system for processing data using messages, wherein each message has a unique identifier, comprising:
-
a plurality of independent, asynchronous processing nodes, the processing nodes comprising one or more computer programs running on one or more computers, the processing nodes being interconnected in a manner represented by a directed graph, including; at least one first node comprising; an input for receiving an input message, wherein the input message is a parent message with a unique identifier, a first message processor for processing the parent message and having an output providing one or more child messages within a group of messages, and an output providing the child messages, wherein each child message has a unique identifier which is indicative of the parent message, and the unique identifier of a parent message is modified to be indicative of a number of child messages; at least one second node comprising; a buffer in memory for storing messages in a group of messages, an input queue in memory for storing other messages, a second message processor, wherein the message processor processes messages from the input queue and the buffer, and a buffer manager configured to detect whether an input message is in a group of messages, and if the message is in a group of messages, then determine whether the message is a parent node, and if the message is not a parent node, then place the message in the buffer, and if the message is a parent node, then determine the number of child nodes and place the message in the buffer, wherein the buffer manager is further configured to detect whether all messages from the group of messages have been received by the second node, and wherein the message processor processes a group of messages in the buffer in order after the buffer manager detects whether all messages from the group of messages have been received.
-
-
9. A computer program product, comprising:
-
a computer-readable storage device; computer program instructions stored on the computer-readable storage device that when processed by a computer instruct the computer to implement a system for processing data using messages, the system comprising; a plurality of independent, asynchronous processing nodes, the processing nodes comprising one or more computer programs running on one or more computers, the processing nodes being interconnected in a manner represented by a directed graph; wherein the plurality of processing nodes includes a first node configured to output groups of messages; and wherein the plurality of processing nodes includes a second node configured to process messages within a group of messages output by the first node in order; wherein the second node comprises; a buffer in memory for storing messages in a group of messages; an input queue in memory for storing other messages; a buffer manager configured to; detect whether an input message is in a group of messages, and if the message is in a group of messages, then determine whether the message is a parent node, and if the message is not a parent node, then place the message in the buffer, and if the message is a parent node, then determine the number of child nodes and place the message in the buffer. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
Specification