Method and structure for balanced queue communication between nodes in a distributed computing application

• US 5,916,307 A
• Filed: 06/05/1996
• Issued: 06/29/1999
• Est. Priority Date: 06/05/1996
• Status: Expired due to Term

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: New Era of Networks, Inc. (SAP SE)
• Inventors: Pelizzoli, Paolo Hendrik Natale, Mui, Gerald Sui, Piskiel, Harold Aron
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): COURTENAY III, ST JOHN
• Application Number:
  US08/658,382
• Time in Patent Office: 1,119 Days
• Field of Search: 707/1-10, 707/100-104, 395/671, 395/683, 395/680
• US Class Current: 719/314
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

Methods and associated structure providing a balanced queue communication system for the exchange of messages between an originating node and a receiving node in a distributed computing environment. A balanced queue comprises a pair of wraparound (circular) queues, one each associated with the originating node and the receiving node. A message is queued by the originating node in the queue associated therewith. Background processing within the originating node retrieves message queued therein and transmits the messages to the intended receiving node. The position in the originating node'"'"'s circular queue is pre-pended to the message and transmitted therewith. The receiving node places the received message in its circular queue in the position specified by the pre-pended location with each message. Background daemon and application processing within the receiving node then retrieves the queued messages for application specific processing. The queue control structures of the balanced queue are integrated with the transaction processing recovery management tables on each of the respective nodes to assure synchronization of the messaging queues of the balanced queue with the application specific processing. These methods and structures of the balanced queue assure robust exchange of messages, synchronized with the application'"'"'s database, while improving the message processing performance as compared to prior solutions. Messages are delivered "exactly once" while reducing overhead (thereby improving performance) as compared to prior techniques.

Claims

1. A balanced queue computer communication system for exchanging messages between an originating process and a receiving process, said balanced queue communication system comprising:

a first memory device associated with said originating process;

a second memory device associated with said receiving process;

a communication medium connecting said originating process and said receiving process for the exchange of messages therebetween;

a first wraparound queue associated with said originating process stored in said first memory device and having a plurality of locations;

a second wraparound queue associated with said receiving process stored in said second memory device and having a plurality of locations, wherein the number of locations in said second wraparound queue is equal to the number of locations in said first wraparound queue;

means associated with said originating process for retrieving a message from said first wraparound queue and for transmitting said message via said communication medium to said receiving process with indicia of the location from which said message was retrieved; and

means in said receiving process for receiving said message and said indicia and for storing said message in said second wraparound queue at a location corresponding to said indicia.

2. The system of claim 1 wherein said first wraparound queue includes:

pointer means for identifying a next available location in said first wraparound queue for the storage of one of said messages.

3. The system of claim 2 further comprising:

means within said originating process for storing said messages in said first wraparound queue at the next available location therein indicated by said pointer means; and

means within said originating process for modifying said pointer means to indicate the next available location in said first wraparound queue.

4. The system of claim 1 further comprising:

recovery management means for automatic recovery of data stored in said first memory device and in said second memory device.

5. The system of claim 4 wherein said means within said originating process are cooperatively operable with said recovery management means to ensure automatic recovery of said first wraparound queue in case of failure of said first memory device.

6. The system of claim 4 wherein said means within said originating process are cooperatively operable with said recovery management means to ensure automatic recovery of said first wraparound queue in case of failure of said communication medium.

7. In a distributed computing application having an originating process and a receiving process, a method for exchanging messages between said originating process and said receiving process comprising the steps of:

(a) storing a message in a first location of a first wraparound queue in association with operation of said originating process;

(b) retrieving said message from said first wraparound queue;

(c) transferring said message and indicia of said first location to said receiving process;

(d) storing said message in a pre-determined location of a second wraparound queue in association with operation of said receiving process, wherein said pre-determined location of said second wraparound queue is determined by said indicia of said first location; and

(e) retrieving said message from said second wraparound queue.

8. The method of claim 7 wherein said first location is the next available location as indicated by a next location indicia stored in association with said first wraparound queue, and wherein the storing step (a) includes the step of:

modifying said next location indicia to indicate the next available location in said first wraparound queue in response to the storage of said message in said first wraparound queue.

9. The method of claim 8 wherein said originating process is operable on a computing system having first recovery management techniques integrated therewith, and

wherein storing step (a) includes the step of committing changes in said first wraparound queue to said first recovery management techniques.

10. The method of claim 9 wherein said receiving process is operable on a computing system having second recovery management techniques integrated therein, and

wherein storing step (d) includes the steps of:

committing changes in said second wraparound queue to said second recovery management techniques; and

acknowledging, responsive to the commitment of changes in said second wraparound queue, said message to said originating process.

11. The method of claim 10 further comprising the steps of:

removing said message from said first wraparound queue in response to the acknowledgment of said message; and

committing changes in said first wraparound queue to said first recovery management techniques in response to the removal of said message therefrom.

12. The method of claim 10 wherein the retrieving step (e) includes the steps of:

removing said message from said second wraparound queue; and

committing changes in said second wraparound queue to said second recovery management techniques in response to the removal of said message therefrom.

13. A program storage device readable by a computer, tangibly embodying a program or instructions executable by the computer to perform method steps for exchanging messages in a distributed computing application between an originating process and a receiving process, said method steps comprising:

(a) storing a message in a first location of a first wraparound queue in association with operation of said originating process;

(b) retrieving said message from said first wraparound queue;

(c) transferring said message and indicia of said first location to said receiving process;

(d) storing said message in a pre-determined location of a second wraparound queue in association with operation of said receiving process, wherein said pre-determined location of said second wraparound queue is determined by said indicia of said first location; and

(e) retrieving said message from said second wraparound queue.

14. The program storage device of claim 13 wherein said first location is the next available location as indicated by a next location indicia stored in association with said first wraparound queue, and wherein the method storing step (a) includes the step of:

modifying said next location indicia to indicate the next available location in said first wraparound queue in response to the storage of said message in said first wraparound queue.

15. The program storage device of claim 14 wherein said originating process is operable on a computing system having first recovery management techniques integrated therewith, and

wherein the method storing step (a) includes the step of committing changes in said first wraparound queue to said first recovery management techniques.

16. The program storage device of claim 15 wherein said receiving process is operable on a computing system having second recovery management techniques integrated therein, and

wherein the method storing step (d) includes the steps of:

committing changes in said second wraparound queue to said second recovery management techniques; and

acknowledging, responsive to the commitment of changes in said second wraparound queue, said message to said originating process.

17. The program storage device of claim 16 the method further comprising the steps of:

removing said message from said first wraparound queue in response to the acknowledgment of said message; and

committing changes in said first wraparound queue to said first recovery management techniques in response to the removal of said message therefrom.

18. The program storage device of claim 16 wherein the method retrieving step (e) includes the steps of:

removing said message from said second wraparound queue; and

committing changes in said second wraparound queue to said second recovery management techniques in response to the removal of said message therefrom.

19. A system for transmission and reception of messages in a distributed processing environment, said system comprising:

a send queue, associated with an originating node, comprising at least one table having a plurality of entries in a first application database within said originating node, wherein each entry may store a message;

a first background processing element, operable within said originating node, which retrieves entries from said send queue and transmits a message stored in said retrieved entries to a receiving node;

a receive queue, associated with said receiving node, comprising at least one table having a plurality of entries in a second application database within said receiving node, wherein said receive queue adapted to receive and store a received message transmitted by said first background processing element; and

a second background processing element operable within said receiving node which monitors said receive queue to start processing received messages stored in entries of said receive queue,

wherein an index value indicative of the location of each entry retrieved from said send queue is transmitted with the message stored in the entry to said receiving node.

20. The system of claim 19 wherein said receiving node includes:

means for acknowledging to said originating node receipt of a transmitted message.

21. The system of claim 19 wherein said send queue and said receive queue have an identical number of entries and wherein said receive queue includes:

means for storing a received message in said receive queue in an entry location indicated by said index value received with said received message.