System and method for dequeue optimization using conditional iteration

• US 10,447,607 B2
• Filed: 05/05/2017
• Issued: 10/15/2019
• 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
• Primary Examiner(s): Fan, Hua
• Application Number:
  US15/588,477
• Publication Number:
  US 20180324129A1
• Time in Patent Office: 893 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 computer readable storage medium 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.

2. The computer readable storage medium of claim 1, 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.

3. The computer readable storage medium of claim 1, 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.

4. The computer readable storage medium of claim 1, 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.

5. The computer readable storage medium of claim 1, 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.

6. The computer readable storage medium of claim 1, wherein the method further comprises:

aborting at least one of said determining or said bypassing based on a timeout timer elapsing from a time of receiving a request to dequeue the valid message.

7. A system comprising:

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

aggregate 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;

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

bypass 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.

8. The system of claim 7, wherein the program logic configured to:

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

determine the location by comparing the current time to the latest expiration time; and

bypass by bypassing the data page when the latest expiration time is before the current time.

9. The system of claim 7, wherein the program logic configured to:

store 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;

determine the location by comparing the current time to the latest expiration time; and

bypass by bypassing the index page when the latest expiration time is before the current time.

10. The system of claim 7, wherein the program logic configured to:

dequeue the valid message based on the location; and

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

wherein the queue comprises a tree structure.

11. The system of claim 7, wherein the program logic configured to:

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

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

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

12. The system of claim 7, wherein the program logic configured to:

abort at least one of said determining or said bypassing based on a timeout timer elapsing from a time of receiving a request to dequeue the valid message.

13. The system of claim 7, wherein the queue comprises a tree structure.

14. A computer-implemented 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.

15. The computer-implemented method of claim 14, 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.

16. The computer-implemented method of claim 14, 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.

17. The computer-implemented method of claim 14, 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.

18. The computer-implemented method of claim 14, 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.

19. The computer-implemented method of claim 14, wherein the method further comprises:

aborting at least one of said determining or said bypassing based on a timeout timer elapsing from a time of receiving a request to dequeue the valid message.

20. The computer-implemented method of claim 14, wherein the queue comprises a tree structure.