Ordered message processing

• US 20100005147A1
• Filed: 06/17/2009
• Published: 01/07/2010
• Est. Priority Date: 06/17/2008
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: Attivio, Incorporated
• Inventors: Serrano, Martin Anthony, Johnson, William Kimble III
• Granted Patent: US 9,009,235 B2
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 51/00 User-to-user messaging in packet-switching networks, transmitted according to store-and-forward or real-time protocols, e.g. e-mail
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

Messages are processed to guarantee proper work scheduling and allow for cyclic and conditional processing. A processing node requiring ordered processing of messages is configured to operate within a plurality of successive processing nodes not requiring ordering processing of messages. Nodes upstream of the ordered node (i) monitor skew between the messages being processed and messages that are ordered after the messages still being processed and that have been forwarded downstream of the node and (ii) pause processing upon reaching skew limits. The nodes upstream of the ordered node limit output of messages to be within a delta of other messages as defined by message IDs. In addition, messages removed from a flow path are replaced by Null messages for ordered processing. Child messages are encoded to incorporate parent IDs preserving ordering systems.

Claims

1. A system for processing messages, the system comprising:

a first node that removes a message of ordered messages from a flow path, the first node inserting a Null message for the removed message; and

an ordered processing node that processes messages in order in the flow path and that recognizes the Null message in place of the removed message.

2. The system of claim 1 further comprising an assigning node configured to assign message IDs to the messages.

3. The system of claim 1 wherein the Null message is assigned a message ID matching the removed message.

4. The system of claim 1 wherein the Null message is configured to indicate a destination node.

5. The system of claim 1 wherein the first node removes the messages in response to an unrecoverable processing error of the message.

6. The system of claim 1 wherein the first node removes the messages in response to branching of the flow path.

7. The system of claim 6 further comprising ajoining node configured to recombine messages due to branching of the flow path and delete Null messages based on the indicated destination node.

8. The system of claim 1 further comprising:

a processing node configured to process messages and generate child messages from parent messages, and annotate parent IDs to indicate the number of child messages; and

an assigning node configured to assign message IDs to the child messages, wherein the child message IDs are encoded to incorporate associated parent IDs.

9. The system of claim 1 further comprising an identifying node configured to identify groups of messages containing related documents.

10. The system of claim 1 further comprising:

a plurality of successive processing nodes configured to process the messages, including the first node and the ordered processing node;

and the first node further configured to allow output of messages out of order but limiting output of such messages to be within a delta of other messages.

11. The system of claim 10 wherein limiting output of messages includes pausing processing of messages outside the delta of other messages as defined by message IDs.

12. The system of claim 10 wherein each processing node is configured to process messages using asynchronous data transmission and further configured to recognize and process the Null messages.

13. A method for processing messages, the method comprising, in an electronic processing system:

in a first node, removing a message of ordered messages from a flow path and inserting a Null message for the removed message; and

in an ordered processing node, processing messages in order and recognizing the Null message in the flow path in place of the removed message.

14. The method of claim 13 further comprising assigning message IDs to the messages.

15. The method of claim 14 wherein the Null message is assigned a message ID matching the removed message.

16. The method of claim 13 wherein the Null message is configured to indicate a destination node.

17. The method of claim 13 wherein removing the message includes removing the message in response to an unrecoverable processing error of the message.

18. The method of claim 13 wherein removing the message includes removing the message in response to branching of the flow path.

19. The method of claim 18 further comprising recombining messages due to branching of the flow path and deleting Null messages based on the indicated destination node.

20. The method of claim 14 further comprising:

processing messages and generating child messages from parent messages, and annotating parent IDs to indicate the number of child messages; and

assigning message IDs to the child messages, wherein the child message IDs are encoded to incorporate associated parent IDs.

21. The method of claim 13 further comprising identifying groups of messages containing related documents.

22. The method of claim 13 further comprising:

processing the messages, allowing for output of messages out of order; and

limiting output of such messages to be within a delta of other messages.

23. The method of claim 22 wherein limiting output of messages includes pausing processing of messages outside the delta of other messages as defined by message IDs.

24. The method of claim 22 further comprising processing messages using asynchronous data transmission and recognizing and processing the Null messages.

25. An article of manufacture having computer-readable program portions embedded thereon for processing messages, the program portions comprising instructions for:

in a first node, removing a message of ordered messages from a flow path and inserting a Null message for the removed message; and

in an ordered processing node, processing messages in order and recognizing the Null message in the flow path in place of the removed message.

26. The article of manufacture of claim 25 further comprising assigning message IDs to the messages.

27. The article of manufacture of claim 26 wherein the Null message is assigned a message ID matching the removed message.

28. The article of manufacture of claim 25 wherein the Null message is configured to indicate a destination node.

29. The article of manufacture of claim 25 wherein removing the message includes removing the message in response to an unrecoverable processing error of the message.

30. The article of manufacture of claim 25 wherein removing the message includes removing the message in response to branching of the flow path.

31. The article of manufacture of claim 30 further comprising recombining messages due to branching of the flow path and deleting Null messages based on the indicated destination node.

32. The article of manufacture of claim 26 further comprising:

processing messages and generating child messages from parent messages, and annotating parent IDs to indicate the number of child messages; and

assigning message IDs to the child messages, wherein the child message IDs are encoded to incorporate associated parent IDs.

33. The article of manufacture of claim 25 further comprising identifying groups of messages containing related documents.

34. The article of manufacture of claim 25 further comprising:

processing the messages, allowing for output of messages out of order; and

limiting output of such messages to be within a delta of other messages.

35. The article of manufacture of claim 34 wherein limiting output of messages includes pausing processing of messages outside the delta of other messages as defined by message IDs.

36. The article of manufacture of claim 34 further comprising processing messages using asynchronous data transmission and recognizing and processing the Null messages.

37-58. -58. (canceled)

59. A system for processing messages, the system comprising a plurality of processing nodes, the nodes comprising:

a document type node configured to (i) split the message into constituent message nodes based on document types included with the message, (ii) forward the message nodes to downstream processing nodes, and (iii) create Null messages for forwarding to downstream processing nodes for which no message node was identified;

a plurality of document processing nodes, each document processing node configured to process message nodes having a particular document type; and

a joiner node configured to receive the constituent message nodes processed at the document processing nodes and delete Null messages.

60. The system of claim 59 wherein the document processing nodes are further configured to transmit the message back to the document type node for subsequent processing if one of the message nodes comprises an attachment and annotate the message indicating the message has one or more child messages associated therewith.

61. The system of claim 59 wherein the downstream processing queue comprises a document store ingestion queue.