Ordered message processing

• US 9,009,235 B2
• Filed: 06/17/2009
• Issued: 04/14/2015
• Est. Priority Date: 06/17/2008
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: Attivio, Incorporated
• Inventors: Johnson, William Kimble III, Serrano, Martin Anthony
• Primary Examiner(s): Algibhah, Hamza
• Assistant Examiner(s): COX, NATISHA D
• Application Number:
  US12/456,517
• Publication Number:
  US 20100005147A1
• Time in Patent Office: 2,127 Days
• Field of Search: 709/206
• 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 along a first flow path through which ordered messages flow;

the first node configured to receive a message of the ordered messages, the received message having content;

the first node configured to remove the received message from the first flow path and divert the removed message to a second flow path for processing, the first node inserting a Null message in the first flow path in place of the removed message; and

an ordered processing node that processes messages in order in the first 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 received message in response to an unrecoverable processing error of the received message.

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

7. The system of claim 6 further comprising a joining node configured to recombines the removed message due to branching of the first 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 received 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.

37. The system of claim 1 wherein the second flow path is configured to allow recursive processing of the removed message.

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

in a first node along a first flow path through which ordered messages flow, receiving a message of the ordered messages, the message having content;

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

diverting the removed message to a second flow path for processing; and

in an ordered processing node, processing messages in order and recognizing the Null message in the first 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 received message includes removing the received message in response to an unrecoverable processing error of the received message.

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

19. The method of claim 18 further comprising recombining messages due to branching of the first 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.

38. The method of claim 13 wherein the second flow path is configured to allow recursive processing of the removed message.

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 along a first flow path through which ordered messages flow, receiving a message of the ordered messages, the received message having content;

the first node configured to remove the received message from the first flow path and inserting a Null message for the removed message, where the removed message is diverted to a second flow path for processing; and

in an ordered processing node, processing messages in order and recognizing the Null message in the first 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 received message includes removing the received message in response to an unrecoverable processing error of the received message.

30. The article of manufacture of claim 25 wherein removing the received message includes removing the received 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.

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

a first node along a first flow path through which ordered messages flow;

the first node configured to receive a message of the ordered messages, the received message having content;

the first node configured to remove the received message from the first flow path to diver the removed message to a second flow path for processing;

the first node configured to insert, in place of the removed message, in the first flow path a Null message that is assigned a message ID matching the removed message; and

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