Ordered processing of groups of messages

• US 8,875,155 B2
• Filed: 07/16/2013
• Issued: 10/28/2014
• Est. Priority Date: 10/15/2010
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: Attivio, Incorporated
• Inventors: Johnson, William K. III, Serrano, Martin Anthony
• Primary Examiner(s): Ho, Andy
• Application Number:
  US13/943,624
• Publication Number:
  US 20140052798A1
• Time in Patent Office: 469 Days
• Field of Search: 719/314
• US Class Current: 719/314
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 51/043 using or handling presence information

Abstract

A data flow processing system represents processing by a directed graph including processing nodes that generate, and process, groups of dependent messages and that can process such groups of messages in order. To identify a group of messages, the system applies message identifiers to messages. Processing of a message may generate child messages. A child message is assigned a message identifier that incorporates the message identifier of the parent message. The message identifier of the parent message is annotated to indicate the number of related child messages. The processing node maintains a buffer to store messages in the group. When a message is received, its message identifier indicates whether it is in a group and information about the group. From this information the processing node determines whether all messages within the group have been received, at which time the processing node can process the messages in order.

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; and

a buffer manager configured to, for each message in a group of messages;

determine whether the message is a parent message, and

if the message is not a parent message, then place the message in the buffer, and

if the message is a parent message, then determine a number of child messages and place the message in the buffer.

2. The computer system of claim 1,

wherein each message has a unique identifier,

wherein within a group of messages the unique identifiers of the messages are represented by a tree.

3. The computer system of claim 2, wherein the unique identifier of a child message is indicative of a parent message, and the unique identifier of a parent message is indicative of a number of child messages.

4. The computer system of claim 1, wherein the first node comprises:

a message identifier generator having an input that receives a message identifier of a parent message and an output providing a message identifier for a child message; and

a message tagger having inputs that receive the message identifier for the child message, and the child message to be output by the first node, and which associates the message identifier with the child message.

5. The computer system of claim 1, wherein the buffer manager is configured to detect whether all messages from the group of messages have been received by the second node.

6. The computer system of claim 5, wherein the buffer manager detects whether all messages from the group of messages have been received by comparing a number of parent messages and child messages from the message identifiers to a number of messages in the buffer.

7. The computer system of claim 5, wherein the second node further comprises a message processor, wherein the message processor processes messages from the first node and the buffer, and wherein the message processor processes a group of messages in the buffer in order with respect to each other after the buffer manager detects whether all messages from the group of messages have been received.

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, and

a buffer manager configured to, for each message in a group of messages, determine whether the message is a parent message, and if the message is not a parent message, then place the message in the buffer, and if the message is a parent message, then determine a number of child messages 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 medium 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;

a buffer manager configured to, for each message in a group of messages;

determine whether the message is a parent message, and

if the message is not a parent message, then place the message in the buffer, and

if the message is a parent message, then determine a number of child messages and place the message in the buffer.

10. The computer program product of claim 9,

wherein each message has a unique identifier,

wherein within a group of messages the unique identifiers of the messages are represented by a tree.

11. The computer program product of claim 10, wherein the unique identifier of a child message is indicative of a parent message, and the unique identifier of a parent message is indicative of a number of child messages.

12. The computer program product of claim 9, wherein the first node comprises:

a message identifier generator having an input that receives a message identifier of a parent message and an output providing a message identifier for a child message; and

a message tagger having inputs that receive the message identifier for the child message, and the child message to be output by the first node, and which associates the message identifier with the child message.

13. The computer program product of claim 9, wherein the buffer manager is configured to detect whether all messages from the group of messages have been received by the second node.

14. The computer program product of claim 13, wherein the buffer manager detects whether all messages from the group of messages have been received by comparing a number of parent messages and child messages from the message identifiers to a number of messages in the buffer.

15. The computer program product of claim 13, wherein the second node further comprises a message processor, wherein the message processor processes messages from the input queue and the buffer, and wherein the message processor processes a group of messages in the buffer in order with respect to each other after the buffer manager detects whether all messages from the group of messages have been received.