Priority queue using two differently-indexed single-index tables

• US 9,514,170 B1
• Filed: 05/15/2013
• Issued: 12/06/2016
• Est. Priority Date: 05/15/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Tillotson, Paul John
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US13/895,143
• Time in Patent Office: 1,301 Days
• Field of Search: 707/741
• US Class Current: 1/1
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

Methods and apparatus for efficient priority queues using single-index tables are disclosed. In response to a request to generate an instance of a priority queue using a database that permits no more than one index per table, an identifier-indexed table and a priority-indexed table are set up. In response to a request to insert a queue entry with a given identifier and a given priority, one tuple is inserted into each table. In response to a request to remove an entry with a specified identifier, a tuple with the specified identifier is removed from the identifier-indexed table, while the removal of the corresponding tuple from the priority-indexed table may be deferred.

Claims

1. A system, comprising:

one or more hardware computing devices configured to;

in response to a request to generate an instance of a priority queue using a provisioned-input-output (provisioned-I/O) database that permits no more than one index per database table, configure an identifier-indexed table and a priority-indexed table in the database, wherein each queue entry of the instance is represented by a pair of tuples comprising a tuple in the identifier-indexed table and a tuple in the priority-indexed table;

in response to a request to insert a queue entry into the instance, insert one tuple with a corresponding identifier into the identifier-indexed table and one tuple with the corresponding identifier into the priority-indexed table; and

in response to a request to remove a queue entry with a specified identifier from the instance,

identify, using an index lookup of the specified identifier, a first target tuple to be removed from the identifier-indexed table;

remove the first target tuple from the identifier-indexed table; and

defer a removal of a second target tuple from the priority-indexed table until, in response to a request to retrieve an identifier of a queue entry based at least in part on a priority criterion, a determination is made that the first target tuple has been removed from the identifier-indexed table.

2. The system as recited in claim 1, wherein the one or more hardware computing devices are further configured to:

in response to a request to generate a different instance of a priority queue, configure a different identifier-indexed table and a different priority-indexed table in the database, wherein each queue entry of the different instance is represented by a pair of tuples comprising a tuple in the different identifier-indexed table and a tuple in the different priority-indexed table;

in response to a request to insert a queue entry into the different instance, insert one tuple comprising a priority value into the different identifier-indexed table and one tuple into the different priority-indexed table; and

in response to a request to remove a queue entry with a specified identifier from the different instance,

identify a third target tuple to be removed from the different identifier-indexed table; and

in response to determining that contents of the third target tuple can be used to identify, via an index lookup, a fourth target tuple to be deleted from the different priority-indexed table, remove the third target tuple from the different identifier-indexed table and the fourth target tuple from the different priority-indexed table.

3. The system as recited in claim 1, wherein the one or more hardware computing devices are configured to:

in response to a request to retrieve an identifier of a queue entry based at least in part on a particular priority criterion,

identify a particular tuple corresponding to the particular priority criterion within the priority-indexed table, wherein the particular tuple includes a particular identifier;

determine whether the identifier-indexed table includes a tuple with the particular identifier;

in response to determining that the identifier-indexed table includes a tuple with the particular identifier, provide an indication of the particular identifier; and

in response to determining that the identifier-indexed table does not include a tuple with the particular identifier, remove the particular tuple from the priority-indexed table.

4. The system as recited in claim 3, wherein the request to retrieve the identifier indicates that the identifier of the queue entry with the highest priority among the queue entries of the instance is to be retrieved, and wherein, in response to determining that the identifier-indexed table does not include a tuple with the particular identifier, the one or more hardware computing devices are further configured to:

after removing the particular tuple from the priority-indexed table,

identify, from among the tuples of the priority-indexed table, a different tuple with a different identifier such that (a) the identifier-indexed table includes a tuple with the different identifier and (b) the different tuple has a higher priority than any other tuple in the priority-indexed table; and

provide an indication of the different identifier.

5. The system as recited in claim 1, wherein, in response to the request to insert the queue entry into the instance, the one or more hardware computing devices are further configured to:

determine a unique value for at least a priority field of the tuple inserted into the priority-indexed table, using one or more of (a) a timestamp (b) a sequence number or (c) a random string.

6. The system as recited in claim 1, wherein the one or more hardware computing devices are further configured to:

provide to a client, and indication of a cost associated with one or more types of queue operations, wherein the cost is expressed in units of I/O operations.

7. A method, comprising:

configuring, in response to a request to generate an instance of a priority queue using a database that permits no more than one index per database table, an identifier-indexed table and a priority-indexed table in the database, wherein each queue entry of the instance is represented by a pair of tuples comprising a tuple in the identifier-indexed table and a tuple in the priority-indexed table;

in response to a request to insert a queue entry into the instance, inserting one tuple with a corresponding identifier into the identifier-indexed table and one tuple with the corresponding identifier into the priority-indexed table; and

in response to a request to remove a queue entry with a specified identifier from the instance,

identifying, using the specified identifier, a first target tuple to be removed from the identifier-indexed table; and

removing the first target tuple from the identifier-indexed table;

wherein a removal of a second target tuple corresponding to the queue entry from the priority-indexed table is deferred until, in response to a request to retrieve an identifier of a queue entry based at least in part on a priority criterion, a determination is made that the first target tuple has been removed from the identifier-indexed table.

8. The method as recited in claim 7, further comprising:

in response to a request from a client to retrieve an identifier of a queue entry based on a particular priority criterion from the instance,

identifying a particular tuple corresponding to the particular priority criterion within the priority-indexed table, wherein the particular tuple includes a particular identifier;

determining whether the identifier-indexed table includes a tuple with the particular identifier;

in response to determining that the identifier-indexed table includes a tuple with the particular identifier, providing an indication of the particular identifier; and

in response to determining that the identifier-indexed table does not include a tuple with the particular identifier, removing the particular tuple from the priority-indexed table.

9. The method as recited in claim 8, wherein the request to retrieve the identifier indicates that the identifier of the queue entry with the highest priority among the queue entries of the instance is to be retrieved, and wherein, in response to determining that the identifier-indexed table does not include a tuple with the particular identifier, the method further comprises:

after removing the particular tuple from the priority-indexed table,

identifying, from among the tuples of the priority-indexed table, a different tuple with a different identifier such that (a) the identifier-indexed table includes a tuple with the different identifier and (b) the different tuple has a higher priority than any other tuple in the priority-indexed table; and

providing an indication of the different identifier.

10. The method as recited in claim 7, further comprising:

deferring the removal of the second target tuple from the priority-indexed table until (a) a request to retrieve an identifier of a queue entry based on a priority criterion from the instance is received, and (b) in response to the request to retrieve the identifier, a determination is made that the first target tuple has been removed from the identifier-indexed table.

11. The method as recited in claim 7, wherein the database comprises an I/O-provisioned database.

12. The method as recited in claim 7, further comprising:

providing, to a client, an indication of the number of I/O operations required to perform one or more queue management operations.

13. The method as recited in claim 7, wherein the database comprises a key-value store in which, within a particular table comprising a particular tuple and a different tuple, the particular tuple comprises a different set of fields than the different tuple.

14. A method, comprising:

configuring, in response to a request to generate an instance of a priority queue using a database that permits no more than one index per database table, an identifier-indexed table and a priority-indexed table in the database, wherein each queue entry of the instance is represented by a pair of tuples comprising a tuple in the identifier-indexed table and a tuple in the priority-indexed table;

in response to a request to insert a queue entry into the instance, inserting one tuple with a corresponding identifier into the identifier-indexed table and one tuple with the corresponding identifier into the priority-indexed table; and

in response to a request to remove a queue entry with a specified identifier from the instance,

identifying, using the specified identifier, a first target tuple to be removed from the identifier-indexed table;

determining, using contents of the first target tuple, a priority value usable for an index-based lookup of a second target tuple to be removed from the priority-indexed table; and

removing the first target tuple from the identifier-indexed table and the second target tuple from the priority-indexed table.

15. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors implement a priority queue service configured to:

in response to a request to establish a priority queue instance, configure an identifier-indexed table and a priority-indexed table in a database, wherein each queue entry of the instance is represented by a pair of tuples comprising a tuple with a corresponding identifier in the identifier-indexed table and a tuple with the corresponding identifier in the priority-indexed table; and

in response to a request to remove a queue entry with a specified identifier from the instance,

identify, using the specified identifier, a first target tuple to be removed from the identifier-indexed table;

in response to determining that contents of the first target tuple can be used to access, using an index lookup, a second target tuple to be deleted from the priority-indexed table, remove the first target tuple from the identifier-indexed table and the second target tuple from the priority-indexed table; and

in response to determining that contents of the first target tuple cannot be used to access the second target tuple using an index lookup, remove the first target tuple from the identifier-indexed table and defer a removal of the second target tuple until, in response to a request to retrieve an identifier of a queue entry based at least in part on a priority criterion, a determination is made that the first target tuple has been removed from the identifier-indexed table.

16. The non-transitory computer-accessible storage medium as recited in claim 15, wherein the priority queue service is configured to:

in response to a request from a client to retrieve an identifier of a queue entry based at least in part on a particular priority criterion from the instance,

identify a particular tuple corresponding to the particular priority criterion within the priority-indexed table, wherein the particular tuple includes a particular identifier;

determine whether the identifier-indexed table includes a tuple with the particular identifier;

in response to determining that the identifier-indexed table includes a tuple with the particular identifier, provide an indication of the particular identifier to the client; and

in response to determining that the identifier-indexed table does not include a tuple with the particular identifier, remove the particular tuple from the priority-indexed table.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the request from the client to retrieve the identifier indicates that the identifier of the queue entry with the highest priority among the queue entries of the instance is to be retrieved, and wherein, in response to determining that the identifier-indexed table does not include a tuple with the particular identifier, the priority queue service is configured to:

after removing the particular tuple from the priority-indexed table,

identify, from among the tuples of the priority-indexed table, a different tuple with a different identifier such that (a) the identifier-indexed table includes a tuple with the different identifier and (b) the different tuple has a higher priority than any other tuple in the priority-indexed table; and

provide an indication of the different identifier to the client.

18. The non-transitory computer-accessible storage medium as recited in claim 15, wherein in response to determining that contents of the first target tuple cannot be used to access the second target tuple using an index lookup, the priority queue service is configured to:

defer the removal of the second target tuple from the priority-indexed table until (a) a request to retrieve an identifier of a queue entry according to a particular priority criterion from the instance is received, and (b) in response to the request to retrieve the identifier, a determination is made that the first target tuple has been removed from the identifier-indexed table.

19. The non-transitory computer-accessible storage medium as recited in claim 15, wherein the priority queue service is configured to

in response to a request to insert a queue entry into the instance, insert one tuple into the identifier-indexed table and one tuple into the priority-indexed table.

20. The non-transitory computer-accessible storage medium as recited in claim 19, wherein, in response to the request to insert the queue entry into the instance, the priority queue service is further configured to:

determine a unique value for a priority field of the tuple inserted into the priority-indexed table.

21. The non-transitory computer-accessible storage medium as recited in claim 20, wherein, to determine the unique value, the priority queue service is further configured to:

determine at least a portion of the unique value using one or more of;

(a) a timestamp, (b) a sequence number or (c) a unique random string.