Method and system for preserving message order when parallel processing messages

• US 7,240,097 B2
• Filed: 02/28/2002
• Issued: 07/03/2007
• Est. Priority Date: 12/12/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Holdsworth, Simon A J, MacFarlane, Peter R
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): SALL, EL HADJI MALICK
• Application Number:
  US10/085,300
• Publication Number:
  US 20030110230A1
• Time in Patent Office: 1,951 Days
• Field of Search: 709/207, 709/231, 709/205, 375/363, 375/240.01
• US Class Current: 709/207
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/565 Conversion or adaptation of application format or content adding application control or application functional data H04L67/561
• CPC Class Codes: H04L 67/566 Grouping or aggregating service requests, e.g. for unified processing
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A method and system for preserving message order when parallel processing messages by: providing a marker (H) in each message (M) for identifying a source of messages for which it is required to preserve the message order; and dispatching (D) each message in accordance with its marker to one of a plurality of parallel processors (P1–P3) so that processing is preserved for messages processed through the plurality of parallel processors. The dispatcher (D) retains a list of all markers of messages that are being processed in parallel, and when a message becomes available to the dispatcher for processing, the dispatcher inspects the list of messages that are currently being processed to determine whether the marker of this message is in the list, and if so delays initiating parallel processing for this message until the marker is no longer in the list. This technique allows a stream of messages originating from multiple sources to be processed with the advantages of parallel processing, while preserving the order of a subset of these messages.

Claims

1. A method for preserving message order when parallel processing messages, comprising:

receiving messages each including a marker for identifying a message source;

responsive to receipt of a message, using the marker to identify the source of the message and determining whether it is required to preserve the message order; and

dispatching each message in accordance with its marker to one of a plurality of parallel processing threads such that processing order is preserved when required for messages processed through the plurality of parallel processing threads, wherein

a predetermined value of the marker indicates that ordering is not required; and

retaining a list of all markers of messages that are being processed in parallel;

determining whether the marker of a new message is present in the list; and

delaying initiating parallel processing of the new message until the marker is no longer in the list.

2. The method of claim 1 further comprising maintaining an ordered queue for each marker that is in the list of messages being processed, and, when message processing by one of the plurality of parallel processing threads completes for a marker, dispatching to said one of the plurality of parallel processing threads the next message in the ordered queue for said marker.

3. The method of claim 1 wherein the marker is derived from characteristics of the source of the ordered messages.

4. The method of claim 3 wherein the characteristics include at least one of:

an identifier of the user originating the message;

an identifier of a repository on which message is put;

an identifier associated with a respective input node receiving the message; and

an identifier associated with the mode of processing.

5. The method of claim 4 wherein the characteristics include:

an identifier of the user originating the message;

an identifier associated with a respective input node receiving the message; and

an identifier associated with the mode of processing.

6. The method of claim 4 wherein the characteristics include:

an identifier of the user originating the message;

an identifier of a repository on which message is put; and

an identifier associated with the mode of processing.

7. The method of claim 1 wherein the marker comprises a hash code.

15. A computer program product comprising program code recorded on a machine readable recording medium, for controlling the operation of a data processing system on which the program code executes, to perform the method of claim 1.

8. A system for preserving message order when parallel processing messages, comprising:

means for receiving messages;

means, responsive to a marker within a received message, for identifying a source of the message and determining whether it is required to preserve the message order; and

a dispatcher for dispatching each message in accordance with its marker to one of a plurality of parallel processing threads such that processing order is preserved when required for messages processed through the plurality of parallel processing threads, wherein

a predetermined value of the marker indicates that ordering is not required; and

means for accessing a list of all markers of messages that are being processed in parallel;

means for determining whether the marker of a new message is present in the list; and

means for delaying initiating parallel processing of the new message until the marker is no longer in the list.

9. The system of claim 8, further comprising an ordered queue for each marker that is in the list of messages being processed, and the dispatcher comprises means for, when message processing by one of the plurality of parallel processing threads completes for a marker, dispatching to said one of the plurality of parallel processing threads the next message in the ordered queue for said marker.

10. The system of claim 8 wherein the marker is derived from characteristics of the source of the ordered messages.

11. The system of claim 10 wherein the characteristics include at least one of:

an identifier of the user from whom the message originates;

an identifier of a respective input node receiving the message;

an identifier of a repository on which message is put; and

an identifier associated with the mode of processing.

12. The system of claim 11 wherein the characteristics include:

an identifier of the user from whom the message originates;

an identifier of a respective input node receiving the message; and

an identifier associated with the mode of processing.

13. The system of claim 11 wherein the characteristics include:

an identifier of the user from whom the message originates;

an identifier of a repository on which message is put; and

an identifier associated with the mode of processing.

14. The system of claim 8 wherein the marker comprises a hash code.