Consistent query of local indexes

Patent metadata

Field	Value
Publication number	US-9922086-B1
Application number	US-201715400175-A
Country	US
Kind code	B1
Filing date	Jan 6, 2017
Priority date	Jan 6, 2017
Publication date	Mar 20, 2018
Grant date	Mar 20, 2018

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.

First claim

What is claimed is:

1. A database system, comprising:
a computing node comprising one or more storage devices storing a collection of items; and
memory coupled to one or more processors and storing program instructions that when executed on the one or more processors cause the system to:
receive a request to perform a database 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 computing node;
read a second value corresponding to the portion of the at least one item from a second data structure on the computing node; and
return, in response to the request, a view of the at least one item, including the projection and the second value, in response to determining that the second value:
conforms to the criteria,
supersedes the first value, and
is considered durable by a threshold number of computing nodes.

2. The system of claim 1 , further comprising:
one or more additional computing nodes that, in combination with the computing node, form a plurality of computing nodes configured to operate a distributed database management system; and
wherein when executed on the one or more processors the program instructions further cause the system to:
update the at least one item in the collection of items with the second value, wherein to update the at least one item the system is configured to:
write an entry in a log file;
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 plurality of computing nodes having written information indicative of the update to the at least one item to a log.

3. The system of claim 2 , wherein when executed on the one or more processors the program instructions further cause the system to:
write updates corresponding to the update to the at least one item subsequent to the read of the first value.

4. The system of claim 1 , wherein when executed on the one or more processors the program instructions further cause the system to:
read an indication of a deleted state of the at least one item from a third data structure on the computing node; and
determine not to return the view of the at least one item based at least in part on the indication of the deleted state of the at least one item.

5. A method, comprising:
performing a database query comprising criteria corresponding to at least one item in a collection of items, the performing of the database query comprising;
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; and
generating a view of the at least one item, including the projection and the second value, in response to determining that the second value:
conforms to the criteria,
supersedes the first value, and
is considered durable by a threshold number of computing nodes.

6. The method of claim 5 , further comprising:
updating the at least one item prior to performing the database query, comprising writing an entry in a log file corresponding to the updating of the at least one item.

7. The method of claim 6 , the updating of the at least one item further comprising:
determining that a threshold number of additional computing nodes have participated in the updating of the at least one item.

8. The method of claim 6 , further comprising:
writing updates to the one or more storage devices corresponding to the updating of the at least one item subsequent to performing the database query.

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. The method of claim 5 , further comprising:
reading an indication of a deleted state of the at least one item from a third data structure; and
determining not to generate the view of the at least one item base at least in part on the indication of the deleted state of the at least one item.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices implement:
performing a database query comprising criteria corresponding to at least one item in a collection of items, the performing of the database query comprising;
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; and
generating a view of the at least one item, including the projection and the second value, in response to determining that the second value:
conforms to the criteria,
supersedes the first value, and
is considered durable by a threshold number of computing nodes.

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

16. The non-transitory, computer-readable storage medium of claim 14 , wherein the second data structure comprises a complete representation of a state of the at least one item.

17. The non-transitory, computer-readable storage medium of claim 14 , wherein the program instructions when executed further implement:
determining not to generate the view of 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.

18. The non-transitory, computer-readable storage medium of claim 14 , wherein the program instructions when executed further implement:
completing a projection of the at least one item by accessing a record on the one or more storage devices corresponding to the at least one item.

19. The non-transitory, computer-readable storage medium of claim 14 , wherein the program instructions when executed further implement:
updating the at least one item prior to performing the database query, comprising writing an entry in a log file corresponding to the updating of the at least one item.

20. The non-transitory, computer-readable storage medium of claim 14 , wherein the program instructions when executed further implement:
writing updates to the one or more storage devices corresponding to the updating of the at least one item subsequent to performing the database query.

Assignees

• Amazon Tech Inc

Inventors

• Huang Xianglong
• Lutz David Alan
• Xiao Wei
• Maccanti Maximiliano
• Perianayagam Somasundaram
• Blackman Rande A
• Marshall Stuart Henry Seelye

Classifications

• G06F17/30451 Primary

  Physics · mapped topic

• G06F17/30312

  Physics · mapped topic

• G06F16/2379 Primary

  Updates performed during online database operations; commit processing · CPC title

• G06F16/2365

  Ensuring data consistency and integrity · CPC title

• G06F16/275

  Synchronous replication · CPC title