SYSTEM AND METHOD FOR DEQUEUE OPTIMIZATION USING CONDITIONAL ITERATION

• US 20180324129A1
• Filed: 05/05/2017
• Published: 11/08/2018
• Est. Priority Date: 05/05/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Varadarajan, Krishnan, Wang, Jieqing, Balakrishnan, Venkates Paramasivam, Mainali, Shane K., Zhang, Quan, Sun, Zichen
• Granted Patent: US 10,447,607 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/566 Deadline varies as a function of time spent in the queue

Abstract

Methods for dequeue optimizations in queues are performed by systems and apparatuses. The methods optimize dequeue operations using aggregation of expired messages enqueued in a queue and conditional iteration over enqueued messages based on the aggregation to service dequeue commands. Queues utilize page hierarchies such as root pages, index pages, and data pages. The aggregation of expired messages for pages in the queue determines the latest expired time for messages for a given page, and these latest expired times are stored in their respective pages, including data pages, index pages, and root pages, for use in the conditional iteration. The conditional iteration bypasses pages for which a latest expired time for all messages is prior to the current time when servicing dequeue requests for the queue.

Claims

1. A system for dequeuing messages in a queue that is temporally ordered, the system comprising:

at least one non-volatile storage device configured to store;

queue logic for providing and managing the queue, the queue being configured to include at least one data page; and

at least one processor configured to perform operations on the queue based on the queue logic, the queue logic comprising;

enqueue logic configured to enqueue at least one valid message, each having an expiry time, in a tail data page of the least one data page that includes a tail of the queue;

aggregator logic configured to;

for each of the at least one data page;

aggregate expired messages to determine an expiration time of the expired messages of the at least one data page; and

store a latest expiration time, the latest expiration time representing a latest value of the aggregated expired messages of its associated data page, with its associated data page;

dequeue logic configured to receive a request to dequeue a valid message of the at least one valid message; and

iterator logic configured to;

determine a queue location in one of the at least one data page for a next valid message based on a comparison of a current time and the latest expiration time for one or more of the at least one data page; and

bypass one or more of the at least one data page to dequeue the valid message from a data page that includes the queue location of the at least one data page.

2. The system of claim 1, wherein the queue is configured to include at least one index page and each of the at least one data page is uniquely linked to one of the at least one index page;

wherein the aggregator logic is configured to, for each of the at least one index page;

aggregate the latest expiration time for each of the at least one data page uniquely linked thereto to determine a latest index expiration time; and

store the latest index expiration time in its associated index page of the at least one index page according to the aggregated latest expired times; and

wherein the iterator logic configured to;

determine a queue location in one of the at least one data page for the next valid message based on a comparison of the current time and the latest index expiration time; and

bypass one or more of the at least one index page to dequeue the valid message.

3. The system of claim 2, wherein the queue is configured to include at least one root page to which each of the at least one index page is uniquely linked;

wherein the aggregator logic is configured to;

aggregate the latest index expiration time for each of the at least one index page to determine a latest root expiration time; and

store the latest index expiration time in its associated root page of the at least one root page according to the aggregated latest index expired times; and

wherein the iterator logic is configured to;

determine a queue location in one of the at least one data page for the next valid message based on a comparison of the current time and the latest root expiration time; and

bypass one or more of the at least one root page to dequeue the valid message.

4. The system of claim 3, further comprising dequeue logic configured to:

dequeue the valid message from the data page that includes the queue location; and

mark the dequeued valid message as having been dequeued and as invalid.

5. The system of claim 3, further comprising timeout logic configured to:

abort one or more operations of the iterator logic or the dequeue logic based on a timeout timer elapsing from a time of said receiving.

6. The system of claim 1, wherein the request comprises a message-specific value for the expiry time;

the system further comprising expiry logic configured to mark the next valid message as expired subsequent to the passage of the expiry time.

7. The system of claim 6, wherein at least one additional request also comprises the message-specific value for at least one respective expiry time;

wherein the expiry logic is configured to mark the at least one additional request as expired subsequent to the passage of the expiry time; and

wherein the aggregator logic is configured to aggregate messages that have a common expiry time together subsequent to expiring.

8. The system of claim 1, the system further comprising:

a storage tree configured to store and maintain the queue and zero or more additional queues, the queue being configured as a tree structure; and

wherein the iterator logic is configured to locate the queue in the storage tree based on a name of the queue provided in the request.

9. A computer-implemented method for dequeuing messages in a queue that is temporally ordered, the method comprising:

in the queue that includes a first index page of the queue linked with a first data page of the queue and a second data page of the queue, and having first expired messages that were previously queued stored in the first data page, queuing at least one valid message, each having an expiry time, in the second data page;

aggregating the first expired messages for the first data page to determine a first latest expiration time for the first expired messages in the first data page;

storing the first latest expiration time in the first data page and in the first index page based on the aggregating;

receiving by the queue a dequeue request to dequeue a valid message of the at least one valid message;

determining a next valid message is in the second data page based on a comparison of a current time and at least the first latest expiration time; and

bypassing the first data page to dequeue the valid message, corresponding to the dequeue request, from the second data page.

10. The computer-implemented method of claim 9, the method further comprising:

dequeuing the valid message from the second data page; and

marking the dequeued valid message as having been dequeued and as invalid.

11. The computer-implemented method of claim 10, wherein one or more of said determining, said bypassing, or said dequeuing is aborted based on a timeout timer elapsing from a time of said receiving.

12. The computer-implemented method of claim 9, wherein the second data page includes the at least one valid message and at least one second expired message;

wherein said aggregating further comprises aggregating the at least one second expired message for the second data page to determine a second latest expiration time for the at least one second expired message; and

wherein said storing further comprises storing the second latest expiration time in the second data page based on the aggregating.

13. The computer-implemented method of claim 9, further comprising:

receiving at least one enqueue request to queue the at least one valid message, each of the at least one enqueue request including a message-specific value for the expiry time; and

marking the valid message as expired subsequent to the passage of the expiry time.

14. The computer-implemented method of claim 13, wherein two of the at least one enqueue request comprise the message-specific value for at least one respective expiry time;

and

the method further comprising marking the two of the at least one enqueue request as expired subsequent to the passage of the expiry time, wherein the two of the at least one enqueue request that have a common expiry time are aggregated together, subsequent to expiring, during said aggregating.

15. The computer-implemented method of claim 9, wherein the queue is maintained in a storage tree comprising zero or more additional queues, and wherein the queue has a tree structure;

and

wherein the dequeue request comprises a name of the queue;

the method further comprising;

locating the queue in the storage tree based on the name of the queue prior to said determining.

16. A computer readable memory storing program instructions that, when executed by one or more processing devices, perform a method, the method comprising:

aggregating expired messages in a queue to determine expiration times for the expired messages, the queue comprising a first index page, and a first data page and a second data page linked with the first index page;

determining a location in the queue for a next valid message based on a comparison of a current time and the expiration times; and

bypassing at least one of an index page of the queue, or a data page of the queue to dequeue a valid message based on the location.

17. The computer readable memory of claim 16, the method further comprising:

storing a latest expiration time of the expiration times for the data page in the data page based on the aggregating;

wherein said determining comprises comparing the current time to the latest expiration time; and

wherein said bypassing comprises bypassing the data page when the latest expiration time is before the current time.

18. The computer readable memory of claim 16, the method further comprising:

storing a latest expiration time of the expiration times for one or more data pages linked to the index page, including the data page, in the index page based on the aggregating;

wherein said determining comprises comparing the current time to the latest expiration time; and

wherein said bypassing comprises bypassing the index page when the latest expiration time is before the current time.

19. The computer readable memory of claim 16, the method further comprising:

dequeuing the valid message based on the location; and

marking the dequeued valid message as having been dequeued and as invalid;

wherein the queue comprises a tree structure.

20. The computer readable memory of claim 16, the method further comprising:

receiving a request to enqueue the next valid message that comprises a message-specific value for an expiry time;

marking the next valid message as expired responsive to the passage of the expiry time; and

subsequently aggregating the expired messages in the queue again to determine updated expiration times for the expired messages.