US 2018/0324129 A1Published application

System and method for dequeue optimization using conditional iteration

AssigneeMicrosoft Technology Licensing, LLC

InventorsKrishnan Varadarajan, Jieqing Wang, Venkates Paramasivam Balakrishnan, Shane K. Mainali, Quan Zhang, Zichen Sun

Life of this patent

Estimating the term…

patentgrep

Loading patent…

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.

Claims20

Dependent claims

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.

13 more elements

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.

4 more elements

Dependencies are inferred from the claim text.