# US 2018/0324129 A1 · System and method for dequeue optimization using conditional iteration > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2018/0324129 A1 - Document ID: US20180324129A1 - Status: Published application - Kind: A1 - Application number: 15/588,477 - Filed: 2017-05-05 - Published: 2018-11-08 - Earliest claimed: 2017-05-05 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Krishnan Varadarajan; Jieqing Wang; Venkates Paramasivam Balakrishnan; Shane K. Mainali; Quan Zhang; Zichen Sun - Web page: https://patentgrep.com/patent/US20180324129A1 ## CPC - H04L 47/50: Queue scheduling - H04L 47/566: {Deadline varies as a function of time spent in the queue} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) 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. ### Claim 4 (depends on 3) 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. ### Claim 5 (depends on 3) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 6) 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. ### Claim 8 (depends on 1) 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. ### Claim 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. ### Claim 10 (depends on 9) 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. ### Claim 11 (depends on 10) 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. ### Claim 12 (depends on 9) 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. ### Claim 13 (depends on 9) 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. ### Claim 14 (depends on 13) 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. ### Claim 15 (depends on 9) 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. ### Claim 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. ### Claim 17 (depends on 16) 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. ### Claim 18 (depends on 16) 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. ### Claim 19 (depends on 16) 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. ### Claim 20 (depends on 16) 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.