High-performance memory queue

• US 20020116538A1
• Filed: 02/22/2001
• Published: 08/22/2002
• Est. Priority Date: 02/22/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dryfoos, Robert O., Wang, Mei-Hui, Chen, Shawfu, Keenaghan, Jason A., Sutton, Peter G., Feldman, Allan, Hu, David Y.
• Granted Patent: US 7,089,564 B2
• Time in Patent Office: Days
• US Class Current: 719/314
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A highly available, high-performance memory queue. Locking of the queue is minimized in order to provide a highly available queue and to improve performance of the queue. Multiple updates of the queue can occur under a single lock. Further, messages of the queue are persistent. A time-initiated checkpointing process, as well as the storing of message information on a recovery log, ensures the persistence of the queue messages.

Claims

1. A method of managing queues, said method comprising:

issuing a transaction to access a queue resident in memory; and

selectively locking the queue during processing of said transaction, wherein the queue remains unlocked for one or more aspects of the transaction processing.

2. The method of claim 1, wherein the selectively locking comprises locking the queue to update the queue.

3. The method of claim 2, further comprising unlocking the queue substantially immediately after the update.

4. The method of claim 2, wherein the update comprises changing a status of one or more messages of the queue.

5. The method of claim 4, wherein the status is changed from unavailable to available.

6. The method of claim 2, wherein the update comprises removing a message from the queue.

7. The method of claim 2, wherein the transaction includes a request to place a message on the queue, and wherein the update comprises placing a pointer to the message on the queue.

8. The method of claim 7, wherein the update further comprises marking the message as unavailable.

9. The method of claim 2, wherein the transaction includes a request to retrieve a message from the queue, and wherein the update comprises marking the message as taken.

10. The method of claim 1, wherein the transaction includes a request to retrieve a message from the queue, and the selectively locking comprises:

one lock of the queue to mark the message as taken; and

another lock of the queue to remove the message from the queue.

11. The method of claim 1, wherein the transaction includes a request to place a message on the queue, and the selectively locking comprises:

one lock of the queue to include a pointer to the message on the queue and to mark the message as unavailable; and

another lock of the queue to change the message from unavailable to available.

12. The method of claim 1, wherein the transaction comprises a plurality of requests to update the queue, and wherein a plurality of updates are committed to the queue under a single lock obtained by the selectively locking.

13. The method of claim 12, wherein the committing of the plurality of updates is controlled by a resource manager.

14. The method of claim 1, wherein one or more messages of said queue are persistent.

15. The method of claim 14, further comprising maintaining the persistence of the one or more messages.

16. The method of claim 15, wherein said maintaining the persistence comprises:

performing a checkpoint of said queue at predefined time intervals; and

writing information regarding the one or more messages of the queue to a log.

17. The method of claim 15, wherein said maintaining the persistence comprises archiving information regarding the one or more messages of the queue using at least one of a log and one or more checkpoint records.

18. The method of claim 1, further comprising concurrently processing a plurality of transactions that are to access the queue.

19. The method of claim 1, further comprising processing another transaction that is to access the queue, wherein the another transaction is able to update the queue while said transaction is processing.

20. A method of managing queues, said method comprising:

requesting a plurality of updates to a queue in memory; and

committing the plurality of updates to the queue under a single lock of the queue.

21. The method of claim 20, wherein the requesting is part of a transaction, and wherein the queue remains unlocked for one or more aspects of processing the transaction.

22. The method of claim 20, further comprising obtaining said single lock.

23. The method of claim 22, wherein said obtaining and said committing are controlled by a resource manager.

24. The method of claim 20, wherein said requesting comprises issuing at least one of one or more requests to place a message on the queue and one or more requests to retrieve a message from the queue, and wherein the committing comprises at least one of changing a status of one or more PUT messages and removing one or more GET messages.

25. The method of claim 20, wherein one or more messages of the queue are persistent.

26. The method of claim 25, further comprising maintaining persistence of the one or more messages.

27. The method of claim 26, wherein the maintaining persistence comprises storing information regarding the one or more messages in at least one of a log and one or more checkpoint records.

28. The method of claim 20, further comprising concurrently processing a plurality of transactions that are to access the queue, wherein one transaction of said plurality of transactions includes the requesting.

29. A method of managing queues, said method comprising:

issuing a first transaction to access a queue in memory, wherein one or more messages of said queue are persistent messages;

issuing a second transaction to access the queue, wherein at least a part of processing of the second transaction is concurrent with at least a part of processing of the first transaction; and

obtaining a lock of the queue, during an aspect of processing of said first transaction, to commit a plurality of updates to the queue under the lock, wherein the queue remains unlocked for one or more other aspects of processing of the first transaction, and wherein said second transaction is capable of locking the queue to perform one or more updates of the queue when the queue is unlocked.

30. A system of managing queues, said system comprising:

means for issuing a transaction to access a queue resident in memory; and

means for selectively locking the queue during processing of said transaction, wherein the queue remains unlocked for one or more aspects of the transaction processing.

31. The system of claim 30, wherein the means for selectively locking comprises means for locking the queue to update the queue.

32. The system of claim 31, further comprising means for unlocking the queue substantially immediately after the update.

33. The system of claim 31, wherein the update comprises means for changing a status of one or more messages of the queue.

34. The system of claim 33, wherein the status is changed from unavailable to available.

35. The system of claim 31, wherein the update comprises means for removing a message from the queue.

36. The system of claim 31, wherein the transaction includes a request to place a message on the queue, and wherein the update comprises means for placing a pointer to the message on the queue.

37. The system of claim 36, wherein the update further comprises means for marking the message as unavailable.

38. The system of claim 31, wherein the transaction includes a request to retrieve a message from the queue, and wherein the update comprises means for marking the message as taken.

39. The system of claim 30, wherein the transaction includes a request to retrieve a message from the queue, and the means for selectively locking comprises:

one lock of the queue to mark the message as taken; and

another lock of the queue to remove the message from the queue.

40. The system of claim 30, wherein the transaction includes a request to place a message on the queue, and the means for selectively locking comprises:

one lock of the queue to include a pointer to the message on the queue and to mark the message as unavailable; and

another lock of the queue to change the message from unavailable to available.

41. The system of claim 30, wherein the transaction comprises a plurality of requests to update the queue, and wherein a plurality of updates are committed to the queue under a single lock obtained by the means for selectively locking.

42. The system of claim 41, wherein the committing of the plurality of updates is controlled by a resource manager.

43. The system of claim 30, wherein one or more messages of said queue are persistent.

44. The system of claim 43, further comprising means for maintaining the persistence of the one or more messages.

45. The system of claim 44, wherein said means for maintaining the persistence comprises:

means for performing a checkpoint of said queue at predefined time intervals; and

means for writing information regarding the one or more messages of the queue to a log.

46. The system of claim 44, wherein said means for maintaining the persistence comprises means for archiving information regarding the one or more messages of the queue using at least one of a log and one or more checkpoint records.

47. The system of claim 30, further comprising means for concurrently processing a plurality of transactions that are to access the queue.

48. The system of claim 30, further comprising means for processing another transaction that is to access the queue, wherein the another transaction is able to update the queue while said transaction is processing.

50. The system of claim 49, wherein the plurality of updates are part of a transaction, and wherein the queue remains unlocked for one or more aspects of processing the transaction.

51. The system of claim 49, further comprising means for obtaining said single lock.

52. The system of claim 51, wherein said means for obtaining and said means for committing are controlled by a resource manager.

53. The system of claim 49, wherein said means for requesting comprises means for issuing at least one of one or more requests to place a message on the queue and one or more requests to retrieve a message from the queue, and wherein the means for committing comprises at least one of means for changing a status of one or more PUT messages and means for removing one or more GET messages.

54. The system of claim 49, wherein one or more messages of the queue are persistent.

55. The system of claim 54, further comprising means for maintaining persistence of the one or more messages.

56. The system of claim 55, wherein the means for maintaining persistence comprises means for storing information regarding the one or more messages in at least one of a log and one or more checkpoint records.

57. The system of claim 49, further comprising means for concurrently processing a plurality of transactions that are to access the queue, wherein one transaction of said plurality of transactions includes the plurality of updates.

49. A system of managing queues, said system comprising:

means for requesting a plurality of updates to a queue in memory; and

means for committing the plurality of updates to the queue under a single lock of the queue.

58. A system of managing queues, said system comprising:

means for issuing a first transaction to access a queue in memory, wherein one or more messages of said queue are persistent messages;

means for issuing a second transaction to access the queue, wherein at least a part of processing of the second transaction is concurrent with at least a part of processing of the first transaction; and

means for obtaining a lock of the queue, during an aspect of processing of said first transaction, to commit a plurality of updates to the queue under the lock, wherein the queue remains unlocked for one or more other aspects of processing of the first transaction, and wherein said second transaction is capable of locking the queue to perform one or more updates of the queue when the queue is unlocked.

59. A system of managing queues, said system comprising:

a transaction to access a queue resident in memory; and

at least one manager used to selectively lock the queue during processing of said transaction, wherein the queue remains unlocked for one or more aspects of the transaction processing.

60. A system of managing queues, said system comprising:

a plurality of updates to be made in a queue in memory; and

a manager used to commit the plurality of updates to the queue under a single lock of the queue.

61. A system of managing queues, said system comprising:

a first transaction to access a queue in memory, wherein one or more messages of said queue are persistent messages;

a second transaction to access the queue, wherein at least a part of processing of the second transaction is concurrent with at least a part of processing of the first transaction; and

a manager used to obtain a lock of the queue, during an aspect of processing of said first transaction, to commit a plurality of updates to the queue under the lock, wherein the queue remains unlocked for one or more other aspects of processing of the first transaction, and wherein said second transaction is capable of locking the queue to perform one or more updates of the queue when the queue is unlocked.

62. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of managing queues, said method comprising:

issuing a transaction to access a queue resident in memory; and

selectively locking the queue during processing of said transaction, wherein the queue remains unlocked for one or more aspects of the transaction processing.

63. The at least one program storage device of claim 62, wherein the selectively locking comprises locking the queue to update the queue.

64. The at least one program storage device of claim 63, wherein said method further comprises unlocking the queue substantially immediately after the update.

65. The at least one program storage device of claim 63, wherein the update comprises changing a status of one or more messages of the queue.

66. The at least one program storage device of claim 65, wherein the status is changed from unavailable to available.

67. The at least one program storage device of claim 63, wherein the update comprises removing a message from the queue.

68. The at least one program storage device of claim 63, wherein the transaction includes a request to place a message on the queue, and wherein the update comprises placing a pointer to the message on the queue.

69. The at least one program storage device of claim 68, wherein the update further comprises marking the message as unavailable.

70. The at least one program storage device of claim 63, wherein the transaction includes a request to retrieve a message from the queue, and wherein the update comprises marking the message as taken.

71. The at least one program storage device of claim 62, wherein the transaction includes a request to retrieve a message from the queue, and the selectively locking comprises:

one lock of the queue to mark the message as taken; and

another lock of the queue to remove the message from the queue.

72. The at least one program storage device of claim 62, wherein the transaction includes a request to place a message on the queue, and the selectively locking comprises:

one lock of the queue to include a pointer to the message on the queue and to mark the message as unavailable; and

another lock of the queue to change the message from unavailable to available.

73. The at least one program storage device of claim 62, wherein the transaction comprises a plurality of requests to update the queue, and wherein a plurality of updates are committed to the queue under a single lock obtained by the selectively locking.

74. The at least one program storage device of claim 73, wherein the committing of the plurality of updates is controlled by a resource manager.

75. The at least one program storage device of claim 62, wherein one or more messages of said queue are persistent.

76. The at least one program storage device of claim 75, wherein the method further comprises maintaining the persistence of the one or more messages.

77. The at least one program storage device of claim 76, wherein said maintaining the persistence comprises:

performing a checkpoint of said queue at predefined time intervals; and

writing information regarding the one or more messages of the queue to a log.

78. The at least one program storage device of claim 76, wherein said maintaining the persistence comprises archiving information regarding the one or more messages of the queue using at least one of a log and one or more checkpoint records.

79. The at least one program storage device of claim 62, wherein said method further comprises concurrently processing a plurality of transactions that are to access the queue.

80. The at least one program storage device of claim 62, wherein said method further comprises processing another transaction that is to access the queue, wherein the another transaction is able to update the queue while said transaction is processing.

81. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of managing queues, said method comprising:

requesting a plurality of updates to a queue in memory; and

committing the plurality of updates to the queue under a single lock of the queue.

82. The at least one program storage device of claim 81, wherein the requesting is part of a transaction, and wherein the queue remains unlocked for one or more aspects of processing the transaction.

83. The at least one program storage device of claim 81, wherein said method further comprising obtaining said single lock.

84. The at least one program storage device of claim 83, wherein said obtaining and said committing are controlled by a resource manager.

85. The at least one program storage device of claim 81, wherein said requesting comprises issuing at least one of one or more requests to place a message on the queue and one or more requests to retrieve a message from the queue, and wherein the committing comprises at least one of changing a status of one or more PUT messages and removing one or more GET messages.

86. The at least one program storage device of claim 81, wherein one or more messages of the queue are persistent.

87. The at least one program storage device of claim 86, wherein said method further comprising maintaining persistence of the one or more messages.

88. The at least one program storage device of claim 87, wherein the maintaining persistence comprises storing information regarding the one or more messages in at least one of a log and one or more checkpoint records.

89. The at least one program storage device of claim 81, wherein said method further comprises concurrently processing a plurality of transactions that are to access the queue, wherein one transaction of said plurality of transactions includes the requesting.

90. An article of manufacture, comprising:

at least one computer usable medium having computer readable program code means embodied therein for causing the managing of queues, the computer readable program code means in said article of manufacture comprising;

computer readable program code means for causing a computer to issue a first transaction to access a queue in memory, wherein one or more messages of said queue are persistent messages;

computer readable program code means for causing a computer to issue a second transaction to access the queue, wherein at least a part of processing of the second transaction is concurrent with at least a part of processing of the first transaction; and

computer readable program code means for causing a computer to obtain a lock of the queue, during an aspect of processing of said first transaction, to commit a plurality of updates to the queue under the lock, wherein the queue remains unlocked for one or more other aspects of processing of the first transaction, and wherein said second transaction is capable of locking the queue to perform one or more updates of the queue when the queue is unlocked.