Consistent query of local indexes

• US 9,576,038 B1
• Filed: 04/17/2013
• Issued: 02/21/2017
• Est. Priority Date: 04/17/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Huang, Xianglong, Lutz, David Alan, Xiao, Wei, Maccanti, Maximiliano, Perianayagam, Somasundaram, Blackman, Rande A., Marshall, Stuart Henry Seelye
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US13/865,113
• Time in Patent Office: 1,406 Days
• Field of Search: 707/626
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

A distributed database management system may comprise a plurality of computing nodes. A request to update an item maintained by the system may be acknowledged as durable and committed once an entry corresponding to the request has been written to a log file and quorum among the computing nodes has been achieved. Improved consistency may be achieved by maintaining snapshots of committed item states within queryable in-memory snapshot data structures. Range queries may be performed by merging a secondary index with the snapshots and applying filters. Projections may be completed by retrieving additional data from an item collection maintain on one or more storage devices.

Claims

1. A system for storing and retrieving data, the system comprising:

a first computing node comprising a first one or more storage devices and a memory, the one or more storage devices having stored thereon a collection of items; and

one or more non-transitory memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to;

receive from a client a request to perform a database query, the query comprising information indicative of a range of at least one item in the collection of items and information indicative of a projection of the at least one item;

read a first value corresponding to a portion of the at least one item stored in a first data structure on the one or more storage devices;

read a second value corresponding to the portion of the at least one item from a second data structure stored in the memory; and

return to the client a view of the at least one item, the view including the projection and the second value instead of the first value in response to determining that the second value is considered durable by a threshold number of computing nodes, and to determining that the second value is consistent with the information indicative of the range.

2. The system of claim 1, further comprising:

one or more additional computing nodes, the first computing node and the one or more additional computing nodes configured to operate a distributed database management system; and

one or more non-transitory memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to;

receive from the client a request to update the at least one item with the second value, prior to the request to perform the database query;

write an entry in a log file corresponding to the request to update the at least one item;

determine that the update to the at least one item is treatable as committed, based at least in part on a threshold number of the additional computing nodes having written information indicative of the update to the at least one item to a log; and

return to the client an acknowledgement of the request to update the at least one item, based at least in part on the determination that the update to the at least one item is treatable as committed.

3. The system of claim 2, further comprising one or more non-transitory memories having stored thereon computer-readable instructions that, upon execution, cause the system to at least:

write updates corresponding to the request to update the at least one item subsequent to receiving the request to perform the database query.

4. The system of claim 1, wherein the view is based at least in part on the projection and a second portion of the at least one item from the collection of items on the one or more storage devices, the second portion corresponding to the projection.

5. A computer-implemented method for storing and retrieving data, the method comprising:

receiving from a client a request to perform a database query, the database query comprising information indicative of a range of at least one item in a collection of items;

reading a first value corresponding to a portion of the at least one item stored in a first data structure on one or more storage devices;

reading a second value corresponding to the portion of the at least one item from a second data structure stored in a memory; and

returning to the client a view of the at least one item, the view including the second value instead of the first value in response to determining that a threshold number of computing nodes have written information indicative of the second value to a log file, and to determining that the second value is consistent with the information indicative of the range.

6. The method of claim 5, further comprising:

receiving from the client a request to update the at least one item, prior to the request to perform the database query;

writing an entry in a log file corresponding to the request to update the at least one item; and

returning to the client an acknowledgement of the request to update the at least one item.

7. The method of claim 6, further comprising:

determining that a threshold number of additional computing nodes have participated in the request to update the at least one item.

8. The method of claim 6, further comprising writing updates corresponding to the request to update the at least one item after returning the acknowledgment to the client.

9. The method of claim 5, wherein the first data structure is a secondary index.

10. The method of claim 5, wherein the second data structure is a snapshot indicative of a committed state of the at least one item.

11. The method of claim 5, wherein the second data structure comprises a complete representation of a state of the at least one item.

12. The method of claim 5, further comprising:

completing a projection of the at least one item by accessing a record on the one or more storage devices, the record corresponding to the at least one item.

13. A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by a computing device, cause the computing device at least to:

receive from a client a request to perform a database query, the database query comprising information indicative of a range of at least one item in a collection of items;

read a first value corresponding to a portion of the at least one item stored in a first data structure on one or more storage devices;

read a second value corresponding to the portion of the at least one item from a second data structure stored in a memory; and

return to the client a view of the at least one item comprising the second value instead of the first value in response to determining that a threshold number of computing nodes have written information indicative of the second value to a log file, and to determining that the second value is consistent with the information indicative of the range.

14. The computer-readable medium of claim 13, wherein the second data structure is a snapshot indicative of a committed state of the at least one item.

15. The computer-readable medium of claim 13, wherein the second data structure comprises a complete representation of a state of the at least one item.

16. The computer-readable medium of claim 13, having stored thereon further instructions that, upon execution by a computing device, cause the computing device to at least:

determine not to return the at least one item when a third data structure stored in the memory is indicative of a deleted state of the at least one item.

17. The computer-readable medium of claim 13, having stored thereon further instructions that, upon execution by a computing device, cause the computing device to at least:

complete a projection of the at least one item by accessing a record on the one or more storage devices, the record corresponding to the at least one item.

18. A system for storing and retrieving data, the system comprising:

a first computing node comprising a first one or more storage devices and a memory, the one or more storage devices having stored thereon a collection of items; and

one or more non-transitory memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to;

perform a database query, the query comprising criteria corresponding to at least one item in the collection of items and information indicative of a projection;

read a first value corresponding to a portion of the at least one item stored in a first data structure on the one or more storage devices;

read a second value corresponding to the portion of the at least one item from a second data structure stored in the memory; and

form a view of the at least one item, the view including the projection and the second value instead of the first value in response to determining that the second value is considered durable by a threshold number of computing nodes, and to determining that the second value conforms to the criteria.

19. The system of claim 18, wherein the criteria corresponds to values in a secondary index.

20. The system of claim 18, further comprising one or more non-transitory memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to:

form the view based at least in part on the first data structure.

21. The system of claim 18, wherein the second data structure comprises an indication of a version.

22. The system of claim 21, further comprising one or more non-transitory memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to:

select the second data structure based at least in part on the indication of the version.