SYSTEM AND METHOD FOR DEQUEUE OPTIMIZATION USING CONDITIONAL ITERATION

2018

Online Patent

Zugriff:

Zum Volltext

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.

Titel:	SYSTEM AND METHOD FOR DEQUEUE OPTIMIZATION USING CONDITIONAL ITERATION
Link:	Zum Volltext
Veröffentlichung:	2018
Medientyp:	Patent
Sonstiges:	Nachgewiesen in: USPTO Patent Applications Sprachen: English Document Number: 20180324129 Publication Date: November 8, 2018 Appl. No: 15/588477 Application Filed: May 05, 2017 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. Current International Class: 04

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.