Improved putMessage algorithm in messaging system
Original Publication Date: 2001-Oct-14
Included in the Prior Art Database: 2003-Jun-20
In certain messaging products, when a message is put to a queue it is necessary to search the queue to establish whether the message already exists on the queue. The good path is that the message is not already on the queue, so the entire queue has to be searched. In one implementation, searching the queue takes O(n) time, where n is the number of messages already on the queue. As the number of messages on the queue increases, so the time to search the queue, and hence the time to put an additional messages, increases linearly. Hence the time to put a single additional message on the queue increases with the number of messages already on the queue. The time taken to put n messages to an initially empty queue is O(n^2). A message is uniquely identified by a pair of fields (the UniqueID) which it carries. The UniqueID comprises the name of the originating queue manager, and creation timestamp. There should be no other message in the system with an identical pair of fields. Messages created on a queue manager have monotonically increasing timestamps the "younger" the message, the higher its timestamp. If a message already on a queue has the same UniqueID, then it is deemed to be the same message, and the attempt to put that message to the queue will be rejected as an attempt at duplication on the queue.