Transactionally consistent indexing for data blobs

• US 8,510,304 B1
• Filed: 08/27/2010
• Issued: 08/13/2013
• Est. Priority Date: 08/27/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Briggs, Gregory J., Rohr, Vincent M.
• Primary Examiner(s): Jami, Hares
• Application Number:
  US12/870,587
• Time in Patent Office: 1,082 Days
• Field of Search: 707/705, 707/736, 707/741, 707/742, 707/743, 707/744, 707/745, 707/746, 707/999.1, 707/999.101, 707/999.102
• US Class Current: 707/736
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures

Abstract

A transactionally consistent indexer is a tiered middleware framework component that updates a transactional index for a data blob according to a data transaction requested by an application. The transactionally consistent indexer determines index entries to be added or removed from a transaction index based on the application request. The transactionally consistent indexer further inserts each index entry to be added into the transaction index. With respect to each index entry to be removed, the transactionally consistent indexer uses a time stamp or version number of the index entry for ensuring optimistic concurrency during deletion. The transactionally consistent indexer then updates a data blob that is associated with each index entry to be added or each index entry to be removed based on the application request.

Claims

1. One or more computer readable non-transitory memories storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

determining an index entry to be added to a transactional index and an index entry to be removed from the transactional index based at least in part on a received application request, each index entry having a “

maybe”

consistency state;

inserting the index entry to be added;

reading a time stamp of the index entry to be removed;

updating, based at least in part on the received application request, a data blob in a data store that is associated with the index entry to be added and a data blob in the data store that is associated with the index entry to be removed;

re-reading the time stamp of the index entry to be removed after the updating of a corresponding data blob;

when the time stamp matches the re-read time stamp, deleting the index entry to be removed from the transactional index; and

when the time stamp does not match the re-read time stamp, aborting a deletion attempt of the index entry to be removed.

2. The one or more computer readable non-transitory memories of claim 1, further comprising instructions that, when executed, cause the one or more processors to perform acts comprising performing a prefix query from an application on an identifier of each index entry in the transactional index, and returning data from each data blob whose corresponding index entry identifier matches the prefix query.

3. The one or more computer readable non-transitory memories of claim 2, wherein the returning includes verifying that a field in each matching data blob includes the data requested by the prefix query.

4. The one or more computer readable non-transitory memories of claim 1, wherein the determining comprises determining the index entry to be removed by receiving information regarding the index entry to be removed from an application, from reading a corresponding data blob, or from consulting a reverse index.

5. The one or more computer readable non-transitory memories of claim 1, wherein the updating includes one of creating the data blob, deleting the data blob, or modifying the data blob.

6. A computer-implemented method, comprising:

under control of one or more computing systems comprising one or more processors,

determining one or more index entries to be added to or one or more index entries to be removed from a transactional index based at least in part on an application request, wherein individual index entries have associated therewith a corresponding identifier;

performing at least one of inserting the one or more index entries to be added to the transactional index or reading a time stamp or a version number of the one or more index entries to be removed;

updating, in a data store, a data blob associated with one or more index entries to be added or the one or more index entries to be removed based at least in part on the application request; and

checking that an identifier of a particular index entry in the transactional index has a first value that matches a second value of a related data field in a corresponding data blob, and deleting the particular index entry when the first and the second values do not agree and an in-progress data transaction to the data store that corresponds to the index entry is absent.

7. The computer-implemented method of claim 6, further comprising deleting the one or more index entries to be removed from the transactional index using optimistic concurrency based at least in part on the corresponding time stamp or the corresponding version number of each of the one or more index entries.

8. The computer-implemented method of claim 6, wherein the determining comprises determining the one or more index entries to be removed by receiving information regarding an index entry to be removed from an application, from reading a corresponding data blob, or from consulting a reverse index.

9. The computer-implemented method of claim 6, wherein the updating includes one of creating the data blob, deleting the data blob, or modifying the data blob.

10. The computer-implemented method of claim 6, wherein individual index entries include a consistency state indicating that uncertainty exists as to an accuracy of a corresponding index entry, and the identifier included in each index entry further comprises a field name of the respective data field in the corresponding data blob.

11. The computer-implemented method of claim 6, further comprising:

performing a query for data from at least one data blob having a field that is untracked by the transactional index; and

returning the data from the untracked field when the untracked field is verified to include data requested by the query.

12. The computer-implemented method of claim 6, further comprising performing a prefix query from an application on the identifier of each index entry in the transactional index, and returning data from each data blob whose corresponding index entry identifier matches the prefix query.

13. The computer-implemented method of claim 12, wherein the returning includes verifying that a field in each matching data blob includes data requested by the prefix query.

14. The computer-implemented method of claim 6, wherein the corresponding identifier comprises a primary key that enables access to an associated data blob, and a field value in addition to the primary key that is from a respective data field in the associated data blob accessible via the primary key.

15. The computer-implemented method of claim 6, further comprising determining that the in-progress transaction to the data store that corresponds to the index entry is absent via one of:

determining that a data transaction to the data store that corresponds to the index entry is not in-progress when a time stamp of the index entry differs from a current time by a predetermined time amount;

forcing a data transaction corresponding to the index entry that is currently in progress to be aborted by an application via optimistic concurrency by performing a data transaction on the corresponding data blob;

stopping each data transaction to the data store momentarily at a same time for a predetermined time; and

determining that a data transaction to the data store that corresponds to the index entry is not in-progress when a time stamp of the index entry is older than an oldest active data transaction to the data store tracked by a supplemental index.

16. A computer-implemented method, comprising:

under control of one or more computing systems comprising one or more processors,

determining whether a new index entry is to be added to a transactional index based at least in part on an application request;

determining whether an existing index entry is to be removed from a transaction index based at least in part on the application request;

responsive to determining that the new index entry is to be added, inserting the new index entry to be added to the transactional index, wherein the new index entry includes a consistency state indicating that the new index entry is being created to track a respective field property value that is being added to a corresponding data blob, and, responsive to determining that the existing index entry is to be removed, reading a time stamp of the existing index entry to be removed and changing a consistency state of the existing index entry to be removed to a consistency state indicating that the existing index entry is to be deleted;

updating, in a data store, a data blob associated with the new index entry to be added or the existing index entry to be removed based at least in part on the application request; and

responsive to determining that the new index entry is to be added, changing, using optimistic concurrency, a consistency state of the new index entry to a consistency state indicating that the new index entry is accurate, and, responsive to determining that the existing index entry is to be removed, deleting, using optimistic concurrency, the existing index entry with the consistency state indicating that the existing index entry is to be deleted.

17. The computer-implemented method of claim 16, wherein if the changing is performed, the changing includes changing a consistency state of the new index entry when the new index entry has a time stamp that is ascertained to be unchanged at time of the changing.

18. The computer-implemented method of claim 16, wherein if the deleting is performed, the deleting includes deleting an existing index entry when the existing index entry has a time stamp that is ascertained to be unchanged at time of the deleting.

19. The computer-implemented method of claim 16, wherein the determining the existing index entry to be removed includes receiving information regarding the existing index entry to be removed from an application, from reading a corresponding data blob, or from consulting a reverse index.

20. The computer-implemented method of claim 16, wherein the updating includes one of creating the data blob, deleting the data blob, or modifying the data blob.

21. The computer-implemented method of claim 16, wherein each index entry includes an identifier that comprises a field property name of a corresponding data blob, a field property value of the corresponding data blob, and a primary key that enables access to the corresponding data blob.

22. The computer-implemented method of claim 16, further comprising performing a prefix query from an application on an identifier of each index entry in the transactional index, and returning data from each data blob whose corresponding identifier matches the prefix query.

23. The computer-implemented method of claim 22, wherein the returning includes at least one of:

returning data from a first matching data blob when its corresponding index entry has the consistency state indicating that the index entry is accurate;

or

verifying that a field in a second matching data blob includes the data requested by the prefix query prior to the returning when its corresponding index entry has the consistency state indicating that the index entry is creating or the consistency state indicating that the index entry is to be deleted.

24. The computer-implemented method of claim 16, further comprising:

performing a query for data from at least one data blob having a field that is untracked by the transactional index; and

returning the data from the untracked field when the untracked field is verified to include data requested by the query.

25. The computer-implemented method of claim 16, wherein if the inserting is performed, the inserting each index entry includes inserting each index entry by updating a time stamp of an existing index entry with an identical identifier using optimistic locking when (1) the existing index entry has the consistency state indicating that the index entry is being created or the consistency state indicating that the index entry is accurate, and (2) a time stamp of the existing index entry differs from a current time by more than a predetermined time amount.

26. The computer-implemented method of claim 16, further comprising aborting an insert of an index entry to be added to the transactional index when (1) an existing index entry with an identical identifier has the consistency state indicating that the index entry is being created or the consistency state indicating that the index entry is accurate, and (2) a time stamp of the existing index entry differs from a current time by less than or a predetermined time amount.

27. The computer-implemented method of claim 16, wherein if the inserting the new index entry is performed, the inserting the new index entry includes updating a time stamp of an additional existing index entry with an identical identifier using optimistic locking when the additional existing index entry has the consistency state indicating that the index entry is to be deleted.

28. The computer-implemented method of claim 16, further comprising performing maintenance on the transactional index, the performing the maintenance including:

checking that an identifier of an index entry in the transactional index has a value that matches a value of a related field in a corresponding data blob;

changing the consistency state of the index entry to indicate that the index entry is accurate when the values do agree, and the index entry initially has the consistency state indicating that the index entry is being created;

deleting the index entry using optimistic concurrency when the values do not agree, the index entry initially having the consistency state indicating that the index entry is being created, and an in-progress data transaction to a data blob that corresponds to the index entry is absent;

changing the consistency state of the index entry to indicate that the index entry is accurate using optimistic concurrency when the values do agree, and the index entry initially has the consistency state indicating that the index entry is to be deleted, and an in-progress data transaction to the data blob that corresponds to the index entry is absent; and

deleting the index entry when the values do not agree and the index entry initially has the consistency state indicating that the index entry is to be deleted.

29. The computer-implemented method of claim 28, further comprising determining that the in-progress transaction to the data blob that corresponds to the index entry is absent via at least one of:

determining that a data transaction to the data store that corresponds to the index entry is not in-progress when a time stamp of the index entry differs from a current time by a predetermined time amount;

forcing a data transaction corresponding to the index entry that is currently in progress to be aborted by an application via optimistic concurrency by performing a data transaction on the corresponding data blob;

stopping each data transaction to the data store momentarily at a same time for a predetermined time;

or

determining that a data transaction to the data store that corresponds to the index entry is not in-progress when a time stamp of the index entry is older than an oldest active data transaction to the data store tracked by a supplemental index.

30. The computer-implemented method of claim 28, wherein the performing maintenance on the transactional index further includes deleting the index entry using optimistic concurrency when the values do not agree, the index entry initially having a consistency state indicating that uncertainty exists as to an accuracy of the index entry, and an in-progress data transaction to the data store that corresponds to the index entry is absent.