Abstract:
Order associated with messages is preserved in an environment wherein a message includes an associated order identifier; a receiver is operable to receive a first message associated with a first order identifier and a selection component is operable to select a first entity for processing the first message. The system includes a determination component for determining whether a notification associated with completion of processing of the first message has been received by the receiver; and a controller for controlling the selection component to select a second entity for processing the second message, in response to a combination of receipt of the notification and a second message associated with the first identifier being received by the receiver preceding the receipt of the notification.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention relates to preserving message order in an asynchronous messaging system.  
       BACKGROUND OF THE INVENTION  
       [0002]     With reference to  FIG. 1 , in an asynchronous messaging system ( 100 ), a sending application (termed “producer” ( 105 ) herein) sends a message to a queue ( 115 ) of a receiving application (termed “consumer” ( 110 ) herein) for processing.  
         [0003]     When using an asynchronous messaging system, there is often a need for messages from a producer to be processed in the order in which they were sent. For example, if a set of messages represent inserts, updates, deletes etc. for a database, the results can be disastrous if the messages are processed out of order. For example, if an operation to insert a row, followed by an operation to delete a row is processed in the wrong order (i.e. the delete operation is processed before the insert operation), the result leaves a row that should have been deleted as remaining inserted.  
         [0004]     A producer naturally orders messages as they are produced. To assure the order is maintained, the most common solution is to configure a producer to send all its messages to a single queue associated with a single consumer. The single consumer processes all messages from the queue in the order in which the messages were placed in to the queue.  
         [0005]     Unfortunately, the consumer of such messages becomes a single point of failure. Furthermore, since only a single consumer is used, the system is not scalable. This solution restricts the ability to build dynamic, flexible, messaging architectures which can support different numbers of consumers. Advantageously, multiple consumers can aid with load balancing requirements, can be utilized to route around a failed consumer etc.  
         [0006]     Thus, to provide scalability in some asynchronous messaging systems, multiple consumers are employed to process messages stored in a shared queue. There is no guarantee that different consumers will process messages taken from a shared queue at the same rate. With reference to an asynchronous messaging system ( 200 ) in  FIG. 2 , if two consumers ( 210 ,  220 ) listen on a single queue ( 215 ), one consumer may process messages faster than the other consumer.  
         [0007]     For example, if Consumer  1  ( 210 ) executes operations at half the speed of Consumer  2  ( 220 ), Consumer  1  ( 210 ) can take twice as long as Consumer  2  ( 220 ) to process some messages. Furthermore, typically, Consumer  1  has no knowledge of the existence of Consumer  2 . Thus a message sequence m 1 , m 2 , m 3  may actually be processed in the order m 1 , m 3 , m 2  if Consumer  2  ( 220 ) retrieves and processes message m 1 ; Consumer  1  ( 210 ) retrieves m 2 ; Consumer  2  ( 220 ) retrieves and processes message m 3  before Consumer  1  ( 210 ) completes its processing of m 2 .  
         [0008]     In one prior art solution, a system is disclosed that can be used when multiple consumers process messages from a shared queue. In the prior art, messages of a particular kind are marked (e.g. by a producer, a filtering application etc.) with a globally unique sequence number (GUS). The multiple consumers must have access to a first relational database that stores data (e.g. GUS, message payload) associated with a last message that was processed and a second relational database that stores data (e.g. GUS) associated with an out of sequence message. Thus if produced messages m 1 , m 2  and m 3  are received in the order m 1 , m 3 , m 2 , then m 1  is processed first and is inserted in the first relational database. When m 3  is received, a query against the first relational database determines that m 3  is out of order. Message m 3  is inserted in the second relational database until m 2  is received. When m 2  is received, a query is executed against the first relational database to determine that m 1  has been processed. Thus, m 2  and m 3  can then be processed. The first relational database is then updated to reflect that m 2  and m 3  have been processed.  
         [0009]     The prior art solution allows messages to become out of order in transit and then allows for the order to be re-established by utilizing GUS and relational databases. However, there is a requirement for message payload to be stored, which creates resource-consuming overhead. There is also a requirement for consumers to share access to the relational databases—this can cause overhead and reduce scalability, since the number of consumers that can share access to the relational databases is limited.  
         [0010]     In some asynchronous messaging systems, multiple consumers are “clustered”, wherein each consumer has an associated queue. To preserve message ordering, some systems typically provide a feature wherein a producer can select a single instance of a consumer to which to send messages. However, if the message is to be sent via a chain of different, clustered, consumers, either the message ordering requirement must be sacrificed (i.e. allow later messages to overtake earlier messages so that each consumer in the chain can be selected dynamically for each message) or the ability to build dynamic, flexible, messaging architectures is sacrificed (i.e. wherein each component explicitly specifies the next component to which the message must be sent).  
       SUMMARY OF THE INVENTION  
       [0011]     The invention may be embodied as a system for preserving order associated with produced messages. In one embodiment, the invention is implemented in an environment wherein a message includes an associated order identifier. A receiver is operable to receive a first message associated with a first order identifier and a selection component is operable to select a first entity for processing the first message. The system includes a determination component for determining whether a notification associated with completion of processing of the first message has been received by the receiver; and a controller for controlling the selection component to select a second entity for processing the second message, in response to a combination of receipt of the notification and a second message associated with the first identifier being received by the receiver proceeding the receipt of the notification.  
         [0012]     Advantageously, message order is preserved and messages do not fall out of order upon transmission of the messages. Advantageously, different consumers can be selected to process messages associated with an order (if an acknowledgement associated with all outstanding messages that have been sent to a single consumer has been received). This allows a flexible architecture to be established to deal with problems such as a need to route around failed consumers and the like. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]     The present invention will now be described, by way of example only, with reference to preferred embodiments thereof, as illustrated in the following drawings:  
         [0014]      FIG. 1  is a block diagram of a producer and a single consumer instance;  
         [0015]      FIG. 2  is a block diagram of a producer and multiple consumer instances;  
         [0016]      FIG. 3  is a more detailed block diagram of a producer and multiple consumer instances;  
         [0017]      FIG. 4  is a flow chart showing the operational steps involved in a process executed by a producer;  
         [0018]      FIG. 5  is a block diagram of a producer, multiple intermediary instances and multiple consumer instances;  
         [0019]      FIG. 6  is a flow chart showing the operational steps involved in a process executed by an intermediary;  
         [0020]      FIG. 7  shows representations of a producer&#39;s log;  
         [0021]      FIG. 8  shows representations of a producer&#39;s log; and  
         [0022]      FIG. 9  shows representations of an intermediary&#39;s log.  
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0023]     A first embodiment will now be described with reference to  FIGS. 3 and 4 . In a first example, in  FIG. 4 , preferably, steps  400  to  450  are executed by a main thread associated with a producer ( 305 ) termed herein as “a producer ( 305 )”. Preferably, steps  455  to  480  are executed by a parallel producer thread that executes in parallel to the producer ( 305 ). In  FIG. 3 , there is shown an asynchronous messaging system ( 300 ) comprising a producer ( 305 ), that generates (step  400 ) at least one message (e.g. in response to an event). In a first example, the messages are associated with database operations against rows of a database (e.g. “insert”, “update”, “delete” etc.). Preferably, message order is preserved for messages generated by a single instance of a producer.  
         [0024]     The system ( 300 ) also includes a plurality of consumers clustered among a corresponding plurality of systems, namely, Consumer  1  ( 310 ) with an associated queue ( 315 ) and Consumer  2  ( 320 ) with an associated queue ( 325 ). Individual installations of a consumer are known as instances (i.e. Consumer  1  is an instance and Consumer  2  is an instance). In the first embodiment, each consumer instance processes a message, without forwarding the message onto another consumer.  
         [0025]     Typically, an asynchronous messaging application executes on the same system as each instance of a producer and a consumer.  
         [0026]     In a first embodiment, the producer ( 305 ) tags (step  405 ) each message with a sequence identifier and a sequence number. A sequence number is unique within a sequence identified by a sequence identifier and the value of the sequence number increases with time. In one example, a sequence identifier is unique to a producer (e.g. wherein the sequence identifier is unique to a task), such that more than one producer does not generate messages having the same sequence identifier. In another example, a sequence identifier can be unique to a producer and also unique to a consumer, such that more than one consumer does not receive messages having the same sequence identifier.  
         [0027]     In the first example, each database row has an associated sequence identifier and the producer ( 305 ) generates two messages. Thus, the ordering requirement can then be stated as follows: for a first message s 1 m 1  (wherein “s 1 ” is the sequence identifier; “m 1 ” is the sequence number and “insert row  1 ” is the message payload) and a second message s 1 m 2  (wherein “s 1 ” is the sequence identifier, “m 2 ” is the sequence number and “update row  1 ” is the message payload), s 1 m 1  must be processed before s 1 m 2  because s 1 m 1  has a sequence number that is less than the sequence number of s 1 m 2 .  
         [0028]     The task of generating appropriate sequence identifiers and sequence numbers can alternatively be performed either by the messaging application or by a combination of the producer and the messaging application. In the latter embodiment, a producer can specify a non-unique sequence identifier (e.g. a customer id—wherein more than one producer uses the customer id) and then the messaging application can qualify the sequence identifier such that the sequence identifier is unique to the producer. In yet another embodiment, multiple producers can collaborate to determine sequence identifiers unique to each producer.  
         [0029]     The producer ( 305 ) includes a selecting component for selecting a consumer instance to which to send the first message, s 1 m 1 , for processing. Alternatively, the messaging application can select a consumer instance based on load balancing techniques, availability requirements etc.  
         [0030]     In the first example, the producer ( 305 ) selects Consumer  1  ( 310 ) and sends (step  410 ) s 1 m 1  to the queue ( 315 ) associated with Consumer  1  ( 310 ). The producer ( 305 ) logs (step  415 ) message data associated with s 1 m 1  in a log.  
         [0031]     In the first example, the sequence identifier (i.e. s 1 ) and the sequence number of the most recent message that was sent (i.e. m 1 ) are logged. Alternatively, in addition, the message payload can also be logged. The producer ( 305 ) also logs (step  415 ) consumer data associated with Consumer  1  ( 310 ) (i.e. an identifier associated with Consumer  1 —in the first example, the identifier is “C 1 ”). A representation of the log is shown in Table  1  in  FIG. 7 .  
         [0032]     Preferably, the log associated with a producer is not persistent (i.e. written to disk) since there is no requirement to preserve message order between different instances of a producer. For example, a sequence identifier will be unique to a producer instance. Thus, if one instance of a producer finishes (e.g. crashes or ends normally) then, on re-start, a new instance of a producer is executed. Since there is no requirement to preserve message order between different instances of a producer, the new instance of a producer uses a new sequence identifier to the sequence identifier used by the previous instance of a producer and a producer instance does not need to persist any data across instances of the producer. Messages associated with the previous instance of the producer will still be processed.  
         [0033]     Alternatively, the log associated with a producer can be persistent (i.e. written to disk) in order to allow the producer to recover after failure. This allows the producer to continue without loss of sequencing. A producer can use this technique if the producer is generating messages in response to an external event.  
         [0034]     Next, the parallel producer thread associated with the producer ( 305 ) waits (step  455 ) for an acknowledgement from Consumer  1  ( 310 ) that s 1 m 1  has been processed. In the first example, an acknowledgement for a message having a particular sequence number y, serves to also acknowledge every message having a sequence number of y or less.  
         [0035]     It should be understood that the parallel producer thread can continuously execute in parallel, or can be invoked when an acknowledgement is to be received.  
         [0036]     In the first example, while the parallel producer thread is waiting for an acknowledgement from Consumer  1  ( 310 ) that s 1 m 1  has been processed; the producer ( 305 ) determines (step  425 ) whether there are any further messages to be sent for processing having a matching sequence identifier to the first message. In response to a determination that there are no further messages to be sent for processing, the parallel producer thread continues to wait (step  455 ) for an acknowledgement from Consumer  1  ( 310 ) that s 1 m 1  has been processed.  
         [0037]     In the first example, the producer ( 305 ) determines that there is another message (i.e. a second message s 1 m 2 ) to be sent for processing. Thus, in response to a determination that there are further messages to be sent for processing, the producer ( 305 ) determines the sequence identifier (i.e. s 1 ) associated with the further message. The producer ( 305 ) utilizes the sequence identifier to check its log (step  430 ) in order to determine (step  435 ) whether there is a record having a matching sequence identifier. In response to a determination that there are no records having a matching sequence identifier, the producer sends (step  410 ) the further message to a consumer.  
         [0038]     In the first example, the producer ( 305 ) determines that there is a record having a matching sequence identifier (i.e. the record in Table 1 having a sequence identifier “s 1 ”) and thus, in response to a determination that there is a record having a matching sequence identifier, the producer ( 305 ) determines (step  440 ) the associated consumer data (i.e. “C 1 ”). Note, that the producer ( 305 ) determines that there is a log record having a matching sequence identifier in the log, because since the parallel producer thread is waiting for an acknowledgement from Consumer 1 ( 310 ) that s 1 m 1  has been processed, the log record has not yet been purged.  
         [0039]     The producer ( 305 ) then sends (step  445 ) s 1 m 2  to the queue of the consumer associated with the determined consumer data (i.e. the queue ( 315 ) associated with Consumer  1  ( 310 )). It should be understood that Consumer  1  ( 310 ) is the same consumer instance that is processing the first message, s 1 m 1 , wherein s 1 m 1  has the same sequence identifier as the second message, s 1 m 2 . The producer ( 305 ) logs (step  450 ) message data associated with s 1 m 2 . In the first example, the data in the sequence identifier field (i.e. s 1 ) represented in Table 1 remains the same; the data in the sequence number field is overwritten (i.e. m 1  is overwritten with m 2 ) since m 2  is sequence number of the most recent message that was sent and the data in the consumer identifier field (i.e. C 1 ) represented in Table 1 remains the same.  
         [0040]     A representation of the updated producer log is shown in Table 2 in  FIG. 7 .  
         [0041]     In response to logging (step  450 ) data, the producer ( 305 ) determines (step  425 ) whether there are any more messages to be sent for processing having a matching sequence identifier to the first message. In the first example, the producer ( 305 ) determines that there are no further messages to be sent for processing and the parallel producer thread continues to wait (step  455 ) for acknowledgements from Consumer  1  ( 310 ) that s 1 m 1  and s 1 m 2  have been processed.  
         [0042]     In the first example, Consumer  1  ( 310 ) processes s 1 m 1  and then processes s 1 m 2  (wherein the order for processing is specified by the order in which the messages arrive on the queue ( 315 )). After s 1 m 2  has been processed, Consumer  1  ( 310 ) generates and sends an acknowledgement to the parallel producer thread, acknowledging that s 1 m 2  has been processed. Since in the first example, an acknowledgement for a message having a particular sequence number serves to also acknowledge every message having a lower sequence number, the acknowledgement also acknowledges that s 1 m 1  has been processed.  
         [0043]     It should be understood that alternatively, the messaging application can generate and transmit acknowledgments on behalf of a consumer instance.  
         [0044]     The parallel producer thread makes a determination (step  460 ) as to whether any acknowledgments have been received. If no acknowledgments are received, a generator generates (step  470 ) an alert, for example, so that a systems administrator can execute analysis (e.g. the systems administrator can force a purge of log records associated with outstanding messages associated with a sequence identifier).  
         [0045]     In the first example, the parallel producer thread makes a determination (step  460 ) that an acknowledgment has been received (e.g. wherein the parallel producer thread can wait for acknowledgements for a pre-determined time).  
         [0046]     In response to receiving the acknowledgment, the parallel producer thread checks (step  465 ) the log in order to determine (step  475 ) whether the producer ( 305 ) can “forget” log records associated with the outstanding messages associated with the sequence identifier. That is, the parallel producer thread compares the sequence identifier and associated sequence number in the acknowledgement with the sequence identifier data and associated sequence number data in the log records.  
         [0047]     If an acknowledgment has not been received for each outstanding message associated with a particular sequence identifier that was sent, a generator produces (step  470 ) an alert.  
         [0048]     If an acknowledgment has been received for each outstanding message associated with a particular sequence identifier that was sent, the parallel producer thread purges (step  480 ) the log records associated with the sequence identifier of the messages that have been processed (i.e. the log record in Table 2 associated with s 1 m 2  (and hence associated with s 1 m 1 )).  
         [0049]     In the first example, the acknowledgement for s 1 m 2  (and hence s 1 m 1 ) is compared against the log (as represented in Table 2). The sequence identifier of the acknowledgment matches the sequence identifier data in the log record. The sequence number of the acknowledgment matches the most recent sequence number data of the log record and thus, since the acknowledgment also acknowledges processing of every message with a sequence number of less than 2 in m 2 , the acknowledgment also acknowledges processing of m 1  (i.e. wherein m 1  has a sequence number of 1, which is less than 2).  
         [0050]     Thus the parallel producer thread purges (step  480 ) the log record associated with the sequence identifier of the messages that have been processed (i.e. the log record in Table 2 associated with s 1 m 2  (and hence s 1 m 1 )).  
         [0051]     It should be understood that the assignment of a sequence identifier and a sequence number to a message allows for an acknowledgment associated with that message to be identified (i.e. by comparing the sequence identifier and sequence number in the message to a sequence identifier and sequence number in the acknowledgement). It should be understood that a consumer guarantees order in its processing of messages because a single consumer processes messages in the order in which they are received on the single consumer&#39;s queue.  
         [0052]     Next, the producer ( 305 ) generates (step  400 ) a third message and tags (step  405 ) the message with a sequence identifier and a sequence number (in the first example—s 1 m 3 ). The producer ( 305 ) selects a consumer instance to which to send the third message, s 1 m 3  for processing. In the first example, the producer ( 305 ) selects Consumer  2  ( 320 ) and sends (step  410 ) s 1 m 3  to the queue ( 325 ) associated with Consumer  2  ( 320 ). The producer ( 305 ) logs (step  415 ) message data associated with s 1 m 3 —in the first example, the sequence identifier (i.e. s 1 ) and the sequence number of the most recent message that was sent (i.e. m 3 ) are logged. The producer ( 305 ) also logs (step  415 ) consumer data associated with Consumer  2  ( 310 ) (i.e. an identifier associated with Consumer  2 —in the first example, the identifier is “C 2 ”). A representation of the producer log is shown in Table 3 in  FIG. 7 .  
         [0053]     Next, the parallel producer thread waits (step  455 ) for an acknowledgement from Consumer 2 ( 310 ) that s 1 m 3  has been processed. In the first example, while the parallel producer thread is waiting for an acknowledgement from Consumer  2  ( 310 ) that s 1 m 3  has been processed; the producer ( 305 ) determines whether there are any further messages to be sent for processing having a matching sequence identifier to the third message. In the first example, as there are no further messages to be sent for processing, the parallel producer thread continues to wait (step  455 ) for an acknowledgement for Consumer  2  ( 310 ) that s 1 m 3  has been processed as described above.  
         [0054]     In the first example, Consumer  2  ( 320 ) processes s 1 m 3  and generates and sends an acknowledgement to the parallel producer thread, acknowledging that s 1 m 3  has been processed.  
         [0055]     The parallel producer thread makes a determination (step  460 ) as to whether any acknowledgments have been received. If no acknowledgments are received, a generator generates (step  470 ) an alert.  
         [0056]     In the first example, the parallel producer thread makes a determination (step  460 ) that an acknowledgment has been received. In response to receiving the acknowledgment, the parallel producer thread checks (step  465 ) the log in order to determine (step  475 ) whether the producer ( 305 ) can “forget” log records associated with the outstanding messages associated with the sequence identifier as described above.  
         [0057]     In the first example, the acknowledgement for s 1 m 3  is compared against the log (as represented in Table 3). The sequence identifier of the acknowledgment matches the sequence identifier data in the log record. The sequence number of the acknowledgment matches the most recent sequence number data of the log record. Thus the parallel producer thread purges (step  480 ) the log record associated with the sequence identifier of the message that has been processed (i.e. the log record in Table 3 associated with s 1 m 3 ).  
         [0058]     Thus, a producer is configurable to send all messages outstanding in the system having the same sequence identifier to the same instance of a consumer. This allows order to be preserved within the sequence, since a single consumer processes the messages in the order in which the messages arrive on its associated queue.  
         [0059]     Furthermore, only when acknowledgements for each outstanding message (i.e. m 1 , m 2 ) having the same sequence identifier (i.e. s 1 ) that has been sent to the same instance of a consumer (i.e. C 1 ) have been received, can a producer ( 305 ) “forget” that it has already chosen a consumer for any given sequence. The producer ( 305 ) can then select a new consumer instance (i.e. C 2 ) next time it sees a message (i.e. m 3 ) in that sequence (i.e. s 1 ). It should be understood that if a producer instance fails before receiving all acknowledgments for each outstanding message, the outstanding messages still get processed, but acknowledgments will not be sent back to the producer instance (because upon re-start, the producer instance is a new producer instance).  
         [0060]     Thus, for each sequence identifier having outstanding messages in the system, a route from a producer to a consumer is built up, which is reused while messages are outstanding in the system but is destroyed (and potentially later rebuilt) when messages in the sequence are no longer being processed.  
         [0061]     Thus, when a particular sequence has no outstanding messages, the preferred embodiment allows a new route to be built. Advantageously, the preferred embodiment allows for routing around any failed consumers in the system and helps maintain high-availability. Furthermore, should one of the consumers fail, only those messages associated with a sequence identifier that the failed consumer was processing at the time of failure will continue to be routed to the failed consumer (unless for example, a systems administrator intervenes and forces a purge of log records associated with outstanding messages associated with a sequence identifier). Messages associated with another sequence identifier can safely be routed around the failure, without compromising the message order requirement.  
         [0062]     Advantageously, the feature of forgetting a sequence once the current consumer instance has processed messages sent to it so far, means that the producer ( 305 ) does not build up an ever-increasing log of sequence identifiers and associated consumer identifiers.  
         [0063]     It should be understood that in the preferred embodiment all messages associated with a particular sequence identifier need not be processed by the same consumer instance, but they should be processed in a particular order. That is, messages are sent to the same consumer instance only when previous messages associated with a sequence identifier have been sent to the consumer instance but have not yet been processed by the consumer instance.  
         [0064]     It should be understood that an acknowledgement can be generated for every message processed. However, generation and receipt of acknowledgements can be optimized. As described above, in one example, a single acknowledgement for s(x), m(y) serves to acknowledge all messages with a sequence identifier of x and a sequence number of y or less. In another example, acknowledgement generation can be skipped such that an acknowledgment is generated for every other message processed. In yet another example, acknowledgment generation can be delayed (e.g. until a time when more bandwidth is available). In yet another example, an acknowledgement can be sent for a batch of messages in accordance with a timeout from receiving a first message in a batch. In yet another example, the messaging application can be configurable to determine whether further messages associated with a sequence identifier have been routed to a consumer instance but have yet to be processed. The messaging application can then be configurable to discard acknowledgements generated for sequence identifier which has outstanding messages waiting for the consumer instance until an acknowledgement for the last outstanding message has been generated. Alternatively, the messaging application can invoke the consumer instance to generate an acknowledgment(s) only when all outstanding messages have been processed.  
         [0065]     By preventing generation of an acknowledgment for every message processed, although further messages associated with a sequence identifier cannot be sent to another consumer instance (and thus, further messages cannot be routed around a failed consumer instance) until all appropriate acknowledgments are received and although a consumer instance may not be available when an acknowledgment needs to be generated, advantageously, this feature improves performance and minimizes overhead associated with acknowledgment generation and transmission.  
         [0066]     In another optimization example, acknowledgments can be non-persistent messages. Persistent messages (which a messaging system guarantees not to lose) must be written to disk and are therefore an overhead. Furthermore, extra network usage is required when handling persistent messages (e.g. it may be required that an acknowledgement needs to be sent from a receiver that receives a persistent message to the sender of the persistent message). Thus, should an acknowledgement for a message associated with a particular sequence identifier become lost, a further (non-outstanding) message associated with the particular sequence is still sent to the same consumer instance and so on until appropriate acknowledgements are received. This optimization feature may not be suitable for a sequence wherein messages are generated sparsely, since it may take time until a further (non-outstanding) message is generated and appropriate acknowledgements are received—thus, delaying the purging of log records associated with that sequence identifier.  
         [0067]     A second embodiment will now be described with reference to  FIGS. 4-6 . In a second example, in  FIG. 6 , steps  600  to  660  are executed by a main thread associated with Intermediary 1 ( 510 ) termed herein as “Intermediary  1  ( 510 )”. Preferably, steps  665  to  695  are executed by a parallel intermediary thread that executes in parallel to Intermediary  1  ( 510 ).  
         [0068]     In  FIG. 5 , there is shown an asynchronous messaging system ( 500 ) comprising a producer ( 505 ) which generates at least one inbound message (e.g. in response to an event). The term “inbound” herein refers to inbound to an intermediary. The system ( 500 ) also comprises a plurality of intermediaries clustered among a corresponding plurality of systems, namely, Intermediary  1  ( 510 ) with an associated queue ( 515 ) and Intermediary  2  ( 520 ) with an associated queue ( 525 ). The system ( 500 ) also comprises a plurality of consumers clustered among a corresponding plurality of systems, namely, Consumer  1  ( 530 ) with an associated queue ( 535 ) and Consumer  2  ( 540 ) with an associated queue ( 545 ). Individual installations of an intermediary or consumer are known as instances.  
         [0069]     Typically one type of intermediary can generate one or more outbound messages in response to an inbound message, wherein the term “outbound” herein refers to outbound to a consumer. Another type of intermediary can transform an inbound message from a producer and send the transformed message on to a consumer. For example, time data in a message is converted from British Summer Time (BST) to Greenwich Mean Time (GMT). Another type of intermediary can route inbound messages between different consumers. Particularly complex intermediaries can perform all of these operations.  
         [0070]     In the second example, an intermediary instance processes an inbound message and in response, introduces a plurality of outbound messages into the messaging network and can route these outbound messages to a consumer. In the second example, each consumer instance processes one or more outbound messages, without forwarding any outbound messages onto another consumer.  
         [0071]     Typically, an asynchronous messaging application executes on the same system as each instance of a producer, an intermediary and a consumer.  
         [0072]     In the second example, the producer ( 505 ) generates (step  400 ) two inbound messages, wherein the inbound messages are associated with database operations against rows of a database (e.g. “insert”, “update”, “delete” etc.).  
         [0073]     The producer ( 505 ) tags (step  405 ) each inbound message with a sequence identifier and a sequence number (wherein a sequence number is unique within a sequence identified by a sequence identifier and wherein the value of the sequence number increases with time).  
         [0074]     In the second example, each database row has an associated sequence identifier. Thus, the ordering requirement can then be stated as follows: for a first inbound message s 1 m 1  (wherein “s 1 ” is the sequence identifier; “m 1 ” is the sequence number and “insert row  1 ” is the message payload) and a second inbound message s 1 m 2  (wherein “s 1 ” is the sequence identifier; “m 2 ” is the sequence number and “update row  1 ” is the message payload), s 1 m 1  must be processed before s 1 m 2  because s 1 m 1  has a sequence number that is less than the sequence number of s 1 m 2 .  
         [0075]     The producer ( 505 ) comprises a selecting component for selecting an intermediary instance to which to send the first inbound message, s 1 m 1  for processing. Alternatively the messaging application can select an intermediary instance based on load balancing techniques, availability requirements etc.  
         [0076]     In the second example, the producer ( 505 ) selects Intermediary  1  ( 510 ) and sends (step  410 ) s 1 m 1  to the queue ( 515 ) associated with Intermediary  1  ( 510 ). The producer ( 505 ) logs (step  415 ) message data associated with s 1 m 1  in a log—in the second example, the sequence identifier (i.e. s 1 ) and the sequence number of the most recent inbound message that was sent (i.e. m 1 ) are logged. The producer ( 505 ) also logs (step  415 ) intermediary data associated with Intermediary  1  ( 510 ) (i.e. an identifier associated with Intermediary  1 —in the second example, the identifier is “I 1 ”). A representation of the log is shown in Table 4 in  FIG. 8 .  
         [0077]     Preferably, the log associated with a producer is not persistent (i.e. written to disk).  
         [0078]     The parallel producer thread associated with the producer ( 505 ) waits (step  455 ) for an acknowledgement from intermediary 1 ( 510 ) that s 1 m 1  has been processed.  
         [0079]     With reference to  FIG. 6 , in response to receiving (step  600 ) an inbound message, s 1 m 1 , Intermediary  1  ( 510 ) generates (step  605 ) two outbound messages. Intermediary  1  ( 510 ) maps the inbound sequence identifier and associated inbound sequence number with an outbound sequence identifier and at least one associated outbound sequence number.  
         [0080]     In the second example, Intermediary  1  ( 510 ) tags (step  610 ) each outbound message with an outbound sequence identifier that is associated with the inbound sequence identifier. Alternatively, the outbound sequence identifier can be the same as the inbound sequence identifier. Intermediary 1 ( 510 ) tags (step  610 ) each outbound message with an outbound sequence number that is associated with the inbound sequence number. The outbound sequence number is unique within a sequence identified by the outbound sequence identifier and the value of the outbound sequence number increases with time.  
         [0081]     In the second example, for the first inbound message s 1 m 1 , a first outbound message s 10 m 1  is generated (wherein “s 10 ” is the outbound sequence identifier; “m 1 ” is the outbound sequence number and “go to database A” is the message payload) and a second outbound message s 10 m 2  is generated (wherein “s 10 ” is the outbound sequence identifier; “m 2 ” is the outbound sequence number and “insert row  100 ” is the message payload). s 10 m 1  must be processed before s 10 m 2  because s 10 m 1  has an outbound sequence number that is less than the outbound sequence number of s 10 m 2 .  
         [0082]     Intermediary  1  ( 510 ) includes a selecting component for selecting a consumer instance to which to send the first and second outbound messages for processing. Alternatively the messaging application can select a consumer instance based on load balancing techniques, availability requirements etc.  
         [0083]     In the second example, Intermediary  1  ( 510 ) selects Consumer  1  ( 530 ) for processing the outbound messages (i.e. s 10 m 1  and s 10 m 2 ) and sends (step  615 ) s 10 m 1  and s 10 m 2  to the queue ( 535 ) associated with Consumer  1  ( 530 ).  
         [0084]     Intermediary  1  ( 510 ) forcibly logs (step  620 ) message data associated with s 1 m 1  in a log. In the second example, Intermediary  1  ( 510 ) logs: the sequence identifier of the first inbound message (i.e. s 1 ); the sequence identifier of the first and second outbound messages (i.e. s 10 ); the inbound sequence number of the most recent inbound message that was sent (i.e. m 1 ); producer data associated with the producer that generated the first inbound message (e.g. an identifier associated with the producer ( 505 )—in the second example, the identifier is “P 1 ”); the outbound sequence number of the most recent outbound message that was sent (i.e. m 2 ) and consumer data associated with the consumer that is processing the outbound messages (e.g. an identifier associated with Consumer  1  ( 530 )—in the second example, the identifier is “C 1 ”). A representation of the log is shown in Table 5 in  FIG. 9 .  
         [0085]     The log associated with an intermediary is persistent (i.e. written to disk) even across instances of an intermediary. This is because, in the event of failure, an intermediary needs to guarantee that messages will be processed and that the messages will be processed in the correct order.  
         [0086]     For example, an intermediary forwards a first message associated with a particular sequence identifier to a selected consumer and subsequently crashes. The consumer has not yet processed the first message (and therefore the consumer has not sent back an acknowledgement). The intermediary recovers and then receives a second message associated with the particular sequence identifier. Since the consumer has not yet acknowledged processing of the first message, the intermediary must forward the second massage to the same selected consumer (even though the selection was made during the previous instance of the intermediary. The log is used to store data associated with a selection, across instances of an intermediary.  
         [0087]     When an intermediary is re-run, it does not use new sequence identifiers (unlike a producer, which can use new sequence identifiers when re-run as described above).  
         [0088]     The parallel intermediary thread waits (step  665 ) for acknowledgements from Consumer  1  ( 530 ) that s 10 m 1  and S 10 m 2  have been processed.  
         [0089]     With reference to  FIG. 4 , in the second example, while the parallel producer thread is waiting for an acknowledgement from Intermediary  1  ( 510 ) that s 1 m 1  has been processed, the producer ( 505 ) determines (step  425 ) whether there are any further inbound messages to be sent for processing having a matching sequence identifier to the first inbound message. In response to a determination that there are no further inbound messages to be sent for processing, the parallel producer thread continues to wait (step  455 ) for an acknowledgement from Intermediary  1  ( 510 ) that s 1 m 1  has been processed.  
         [0090]     In the second example, the producer ( 505 ) determines that there is a further inbound message (i.e. a second inbound message s 1 m 2 ) to be sent for processing, thus, in response to a determination that there are further inbound messages to be sent for processing, the producer ( 505 ) determines the sequence identifier (i.e. s 1 ) associated with the second inbound message. The producer ( 505 ) utilizes the sequence identifier to check its log (step  430 ) in order to determine (step  435 ) whether there is a record having a matching sequence identifier. In response to a determination that there are no records having a matching sequence identifier, the producer ( 505 ) sends (step  410 ) the further message to a consumer.  
         [0091]     In the second example, the producer ( 505 ) determines that there is a record having a matching sequence identifier (i.e. the record in Table 4 having a sequence identifier “s 1 ”) and thus, in response to a determination that there is a record having a matching sequence identifier, the producer ( 505 ) determines (step  440 ) the associated intermediary data (i.e. “I 1 ”). Note, that the producer ( 505 ) determines that there is a log record having a matching sequence identifier in the log, because since the parallel producer thread is waiting for an acknowledgement from Intermediary  1  ( 510 ) that s 1 m 1  has been processed, the log record has not yet been purged.  
         [0092]     The producer ( 505 ) then sends (step  445 ) s 1 m 2  to the queue of the intermediary associated with the determined intermediary data (i.e. the queue ( 515 ) associated with Intermediary  1  ( 510 )). It should be understood that Intermediary  1  ( 510 ) is the same intermediary instance that is processing the first inbound message, s 1 m 1 , wherein s 1 m 1  has the same sequence identifier as the second inbound message, s 1 m 2 .  
         [0093]     The producer ( 505 ) logs (step  450 ) message data associated with s 1 m 2 . In the second example, the data in the sequence identifier field (i.e. s 1 ) represented in Table 4 remains the same; the data in the sequence number field is overwritten (i.e. m 1  is overwritten with m 2 ) since m 2  is sequence number of the most recent inbound message that was sent and the data in the intermediary identifier field (i.e. I 1 ) represented in Table 4 remains the same. A representation of the updated producer log is shown in Table 6 in  FIG. 8 .  
         [0094]     In response to logging (step  450 ) data, the producer ( 505 ) determines (step  425 ) whether there are any further inbound messages to be sent for processing having a matching sequence identifier to the first inbound message. In the second example, the producer ( 505 ) determines that there are no further inbound messages to be sent for processing and the parallel producer thread continues to wait (step  455 ) for acknowledgements from Intermediary  1  ( 510 ) that s 1 m 1  and s 1 m 2  have been processed.  
         [0095]     With reference to  FIG. 6 , while the parallel intermediary thread is waiting for an acknowledgement from Consumer  1  ( 530 ) that s 10 m 1  and s 10 m 2  have been processed, Intermediary  1  ( 510 ) determines (step  625 ) whether there are any further inbound messages to be sent for processing having a matching sequence identifier to the first inbound message (i.e. s 1 m 1 ). In response to a determination that there are no further inbound messages to be sent for processing, the parallel intermediary thread continues to wait (step  630 ) for an acknowledgement from Consumer  1  ( 530 ) that s 10 m 1  and s 10 m 2  have been processed.  
         [0096]     In the second example, intermediary 1 ( 510 ) determines that there is a further inbound message (i.e. a second inbound message, s 1 m 2 ) in its queue ( 515 ) to be sent for processing. Thus, in response to a determination that there are further inbound messages to be sent for processing, Intermediary  1  ( 510 ) determines the sequence identifier (i.e. s 1 ) associated with the second inbound message. Intermediary  1  ( 510 ) utilizes the sequence identifier to check (step  630 ) its log in order to determine (step  635 ) whether there is a record having a matching sequence identifier. In response to a determination that there are no records having a matching sequence identifier, Intermediary  1  ( 510 ) sends (step  615 ) the further inbound message to a consumer.  
         [0097]     In the second example, Intermediary  1  ( 510 ) determines that there is a record having a matching sequence identifier (i.e. the record in Table 5 having a sequence identifier “s 1 ”) and thus, in response to a determination that there is a record having a matching sequence identifier, Intermediary  1  ( 510 ) determines (step  640 ) the associated consumer data (i.e. “C 1 ”).  
         [0098]     Note, that Intermediary  1  ( 510 ) determines that there is a log record having a matching sequence identifier in the log because since the parallel intermediary thread is waiting for acknowledgements from Consumer  1  ( 530 ) that s 10 m 1  and s 10 m 2  have been processed, the log record has not yet been purged.  
         [0099]     In response to receiving s 1 m 2 , Intermediary  1  ( 510 ) generates (step  645 ) to outbound messages. Intermediary  1  ( 510 ) maps the inbound sequence identifier and associated inbound sequence number with an outbound sequence identifier and at least one associated outbound sequence number.  
         [0100]     In the first example, Intermediary  1  ( 510 ) tags (step  650 ) each outbound message with an outbound sequence identifier that is associated with the inbound sequence identifier and an outbound sequence number that is associated with the inbound sequence number. The outbound sequence number is unique within a sequence identified by the outbound sequence identifier and the value of the outbound sequence number increases with time.  
         [0101]     In the second example, for the second inbound message, s 1 m 2 , a third outbound message s 10 m 3  is generated (wherein “s 10 ” is the sequence identifier; “m 3 ” is the sequence number and “go to database B” is the message payload) and a fourth further message s 10 m 4  is generated (wherein “s 10 ” is the sequence identifier; “m 4 ” is the sequence number and “update row  75 ” is the message payload). s 10 m 3  must be processed before s 10 m 4  because s 10 m 3  has a sequence number that is less than the sequence number of s 10 m 4 . Furthermore, the value of the sequence number for the third outbound message associated with the second inbound message (i.e. 3 in s 10 m 3 ) must be more than the value of the sequence number for the second outbound message associated with the first inbound message (i.e. 2 in s 10 m 2 ) to preserve order.  
         [0102]     Intermediary  1  ( 510 ) then sends (step  655 ) s 10 m 3  and s 10 m 4  to the queue of the consumer associated with the determined consumer data (i.e. the queue ( 535 ) associated with Consumer  1  ( 530 )). It should be understood that Consumer  1  ( 530 ) is the same consumer instance that is processing the first and second outbound messages (i.e. s 10 m 1  and s 10 m 2 ), wherein s 10 m 1  and s 10 m 2  have the same sequence identifier as the third and fourth outbound messages, s 10 m 3  and s 10 m 4 .  
         [0103]     Intermediary  1  ( 510 ) forcibly logs (step  660 ) message data associated with s 1 m 2  in a log. In the second example, Intermediary  1  ( 510 ) logs: the sequence identifier of the second inbound message (i.e. s 1 ); the sequence identifier of the third and fourth outbound messages (i.e. s 10 ); the inbound sequence number of the most recent inbound message that was sent (i.e. m 2 ); producer data associated with the producer that generated the second inbound message (e.g. an identifier associated with the producer ( 505 )—in the second example, the identifier is “P 1 ”); the outbound sequence number of the most recent outbound message that was sent (i.e. m 4 ) and consumer data associated with the consumer that is processing the outbound messages (e.g. an identifier associated with Consumer  1  ( 530 )—in the second example, the identifier is “C 1 ”). A representation of the log is shown in Table 7 in  FIG. 9 .  
         [0104]     In response to logging (step  660 ) data, Intermediary  1  ( 510 ) determines (step  625 ) whether there are any further messages to be sent for processing having a matching sequence identifier to the first inbound message (i.e. s 1 m 1 ). In the second example, Intermediary  1  ( 510 ) determines that there are no further messages to be sent for processing and the parallel intermediary thread continues to wait (step  665 ) for acknowledgements from Consumer  1  ( 530 ) that s 10 m 1 , s 10 m 2 , s 10 m 3  and s 10 m 4  have been processed.  
         [0105]     In the second example, Consumer  1  ( 530 ) processes s 10 m 1 , s 10 m 2 , s 10 m 3  and s 10 m 4  (wherein the order for processing is specified by the order in which the messages arrive on the queue ( 535 )). After s 10 m 4  has been processed, Consumer  1  ( 510 ) generates and sends an acknowledgement to the parallel intermediary thread, acknowledging that s 10 m 4  has been processed. Since in the second example, an acknowledgement for a message having a particular sequence number serves to also acknowledge every message having a lower sequence number, the acknowledgement also acknowledges that s 10 m 1 , s 10 m 2  and s 10 m 3  have been processed. It should be understood that alternatively, the messaging application can generate and transmit acknowledgments on behalf of a consumer instance.  
         [0106]     The parallel intermediary thread makes a determination (step  670 ) as to whether any acknowledgments have been received. If no acknowledgments are received, a generator generates (step  695 ) an alert.  
         [0107]     In the second example, parallel intermediary thread makes a determination (step  670 ) that an acknowledgment has been received (e.g. wherein the parallel intermediary thread can wait for acknowledgements for a pre-determined time).  
         [0108]     In response to receiving the acknowledgment, the parallel intermediary thread checks (step  675 ) its log in order to determine (step  680 ) whether an acknowledgement acknowledging that one or more inbound messages have been processed can be sent to the producer ( 505 ).  
         [0109]     That is, the parallel intermediary thread compares the sequence identifier and associated sequence number in the acknowledgement with the sequence identifier data and associated sequence number data in the log records. In response to the comparison, if the parallel intermediary thread determines that an acknowledgement has not been received for each outstanding outbound message associated with a particular sequence identifier that was sent, a generator generates (step  695 ) an alert.  
         [0110]     In the second example, the parallel intermediary thread compares the acknowledgement for s 10 m 4  against the log (as represented in Table 7). The sequence identifier of the acknowledgement matches the outbound sequence identifier data in the log record. The sequence number of the acknowledgement matches the most recent outbound sequence identifier data in the log record and thus, since the acknowledgement also acknowledges processing of every message with a sequence number less than 4 in m 4 , the acknowledgement also acknowledges processing of s 10 m 1 , s 10 m 2  and s 10 m 3 .  
         [0111]     Thus, in response to the comparison, the parallel intermediary thread determines that an acknowledgement has been received for each outstanding outbound message associated with a particular sequence identifier that was sent. Thus, the parallel intermediary thread generates (step  685 ) an acknowledgment for the associated first and second inbound messages generated by the producer ( 505 ) i.e. s 1 m 1  and s 1 m 2 . Specifically, the parallel intermediary thread (step  685 ) an acknowledgment for s 1 m 2  (which serves to acknowledge processing of every message with a sequence number less than 2 in m 2  and thus, the acknowledgement also acknowledges processing of s 1 m 1 ).  
         [0112]     The parallel intermediary thread sends (step  685 ) the acknowledgment to the producer ( 505 ). It should be understood that alternatively, the messaging application can generate and transmit acknowledgments on behalf of an intermediary instance.  
         [0113]     Since an acknowledgement associated with each outstanding outbound message associated with a particular sequence identifier that was sent has been received, the parallel intermediary thread purges (step  690 ) the log record associated with the sequence identifier of the outbound messages that have been processed (i.e. the log record in Table 7 associated with s 10 m 4  (and hence associated with s 10 m 1 , s 10 m 2  and s 10 m 3 )). Thus, the intermediary can “forget” that it has already selected a consumer for any given sequence. The intermediary can then select a new consumer instance next time it sees a message in that sequence.  
         [0114]     With reference to  FIG. 4 , the parallel producer thread makes a determination (step  460 ) as to whether any acknowledgments have been received. If no acknowledgments are received, a generator generates (step  470 ) an alert.  
         [0115]     In the second example, the parallel producer thread makes a determination (step  460 ) that an acknowledgment has been received. In response to receiving the acknowledgment, the parallel producer thread checks (step  465 ) the log in order to determine (step  475 ) whether the producer ( 305 ) can “forget” log records associated with the outstanding messages associated with the sequence identifier as described above.  
         [0116]     In the second example, the acknowledgement for s 1 m 2  (and hence s 1 m 1 ) is compared against the log (as represented in Table 6). The sequence identifier of the acknowledgment matches the sequence identifier data in the log record. The sequence number of the acknowledgment matches the most recent sequence number data of the log record and thus, since the acknowledgment also acknowledges processing of every message with a sequence number of less than 2 in m 2 , the acknowledgment also acknowledges processing of m 1  (i.e. a sequence number of 1, which is less than 2).  
         [0117]     Thus the parallel producer thread purges (step  480 ) the log record associated with the sequence identifier of the messages that have been processed (i.e. the log record in Table 6 associated with s 1 m 2  (and hence s 1 m 1 )).  
         [0118]     Thus, a producer is configurable to send all messages outstanding in the system having the same sequence identifier to the same instance of an intermediary. This allows order to be preserved within the sequence, since a single intermediary processes the messages in the order in which the messages arrive on its associated queue. Furthermore, only when acknowledgements for each outstanding message (i.e. m 1 , m 2 ) having the same sequence identifier (i.e. s 1 ) that has been sent to the same instance of an intermediary (i.e. I 1 ) have been received, can a producer “forget” that it has already chosen an intermediary for any given sequence. The producer ( 505 ) can then select a new intermediary instance next time it sees a message in that sequence.  
         [0119]     This also applies to intermediaries, wherein an intermediary is configurable to all outbound messages outstanding in the system having the same sequence identifier to the same instance of a consumer. Furthermore, only when acknowledgements for each outstanding outbound message (i.e. m 1 , m 2 , m 3  and m 4 ) having the same sequence identifier (i.e. s 10 ) that has been sent to the same instance of an consumer (i.e. C 1 ) have been received, can an intermediary “forget” that it has already chosen a consumer for any given sequence. The intermediary can then select a new consumer instance next time it sees a message in that sequence.  
         [0120]     It should be understood, that the optimization of the generation and receipt of acknowledgements described above in relation to consumers, also applies to intermediaries.  
         [0121]     It should be understood the present invention can also be utilized in a system wherein multiple consumer or intermediary instances reside on a single physical computer system. Such a system is advantageous in that communications are quicker, since the processing occurs in memory. In this example, a dispatcher can select a consumer or intermediary instance in memory to which to send messages associated with a sequence identifier to, can log message data and consumer data or intermediary data and can receive acknowledgements from a consumer instance or an intermediary instance. It should be understood that the dispatcher can reside on the same physical computer system as the consumer or intermediary instances or can reside on a different physical computer system.  
         [0122]     It should be understood that the present invention is scalable to multiple (clusters) of intermediaries. For example, a first cluster of intermediaries can transform a message and send the message to a second cluster of intermediaries. The second cluster of intermediaries can log data associated with the message and forward the message to a consumer.