Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Improved putMessage algorithm in messaging system

IP.com Disclosure Number: IPCOM000015189D
Original Publication Date: 2001-Oct-14
Included in the Prior Art Database: 2003-Jun-20
Document File: 2 page(s) / 30K

Publishing Venue

IBM

Abstract

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Improved putMessage algorithm in messaging system

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.

     The invention eliminates in most cases the need to search
the entire queue to determine whether the message is already on
the queue. This makes the putMessage algorithm run in O(1) time -
constant time regardless of the number of messages already on the
queue.

     Additional state information is added to each queue. In
addition to prior art implementations, a queue according to the
invention will have a Table, each entry within which maps an
originating Queue Manager name to the highest timestamp of any
message already put to the queue for that queue manager.

     Since messages tend to be created and then put to a queue in
order, it is usually the case that a message being put to a queue
will be "younger" (have a later creation timestamp) than all the
previous messages put to the queue for that queue manager.

     According to the invention, the putMessage algorithm
includes a shortcut. When a message is to be put to a queue then
the Queue Manager name cont...