Commit and rollback of data streams provided by partially trusted entities

• US 10,515,228 B2
• Filed: 07/13/2018
• Issued: 12/24/2019
• Est. Priority Date: 10/13/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Multani, Lakhan Arya, Girdhar, Sachin
• Primary Examiner(s): Singh, Gurkanwaljit
• Application Number:
  US16/035,486
• Publication Number:
  US 20180322301A1
• Time in Patent Office: 529 Days
• Field of Search: None
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06Q 10/06395 Quality analysis or management
• CPC Class Codes: H04L 41/04 Network management architectures or arrangements
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838

Abstract

A collection of key-value pairs may be maintained by a key-value database management system. Updates to the collection may be provided by a partially trusted entity. The updates to the collection may be stored in a series of transactions that are committed synchronously but associated with a second version of the collection of key-value pairs that is not immediately visible to a data consumer. The second version of the collection may initially be associated with an unaccepted state. The second version may be accepted and made available to the data consumer, or rejected and rolled back to the previous version.

Claims

1. A system, comprising:

at least one processor; and

at least one memory comprising instructions that, in response to being executed by the at least one processor, cause the system at least to;

maintain a first version of a collection of data on one or more storage devices;

associate the first version of the collection of data with information indicative of an accepted state of the first version of the collection, wherein the information indicative of the accepted state includes a first acceptance status indicator that indicates a first metatransaction has been accepted;

associate a second version of the collection of data with information indicative of an unaccepted state of the second version of the collection, the second version of the collection of data based on one or more transactions applied to the first version of the collection, wherein the information indicative of the unaccepted state includes a second acceptance status indicator that indicates a second metatransaction has not been accepted; and

in response to a request to access the collection of data, provide access to the first version of the collection of data based on determining that the second version is associated with an unaccepted state.

2. The system of claim 1, wherein the at least one memory comprises further instructions that, in response to being executed by the at least one processor, cause the system to at least store, in the collection of data, a value indexed in the collection by an extended key comprising an identifier of a version of the collection.

3. The system of claim 2, wherein the at least one memory comprises further instructions that, in response to being executed by the at least one processor, cause the system to at least store an association between the identifier of the version of the collection and data indicative of at least one of an accepted or unaccepted state of the version of the collection.

4. The system of claim 1, wherein the at least one memory comprises further instructions that, in response to being executed by the at least one processor, cause the system to at least roll back the second version of the collection by storing an association between an identifier of the second version of the collection and data indicative of a rejected state.

5. The system of claim 1, wherein the at least one memory comprises further instructions that, in response to being executed by the at least one processor, cause the system to at least provide, in response to a second request to access the collection of data, access to the second version of the collection of data based on determining that the second version is associated with an accepted state.

6. A method, comprising:

maintaining a first version of a collection of data on one or more storage devices;

associating the first version of the collection of data with information indicative of an accepted state of the first version of the collection;

associating a second version of the collection of data with information indicative of an unaccepted state of the second version of the collection, the second version of the collection of data based on one or more changes to the first version of the collection; and

in response to a request to access the collection of data, providing access to the first version of the collection of data based on determining that the second version is associated with an unaccepted state.

7. The method of claim 6, further comprising storing, in the collection of data, a value indexed in the collection by an extended key comprising an identifier of a version of the collection.

8. The method of claim 7, further comprising storing an association between the identifier of the version of the collection and data indicative of at least one of an accepted or unaccepted state of the version of the collection.

9. The method of claim 6, further comprising rolling back the second version of the collection by storing an association between an identifier of the second version of the collection and data indicative of a rejected state.

10. The method of claim 6, further comprising providing, in response to a second request to access the collection of data, access to the second version of the collection of data based at least in part on determining that the second version of the collection has been accepted.

11. The method of claim 6, further comprising deleting data in a version of the collection of data that is associated with a rolled-back state.

12. The method of claim 6, wherein data in the collection of data is indexed by an extended key comprising an original key and a version identifier.

13. The method of claim 12, wherein data in the collection is retrievable using the original key and is retrievable using the extended key.

14. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:

maintain a first version of a collection of data on one or more storage devices;

associate the first version of the collection of data with information indicative of an accepted state of the first version of the collection;

associate a second version of the collection of data with information indicative of an unaccepted state of the second version of the collection, the second version of the collection of data based on one or more transactions applied to the first version of the collection; and

in response to a request to access the collection of data, provide access to the first version of the collection of data based on determining that the second version is associated with an unaccepted state.

15. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to store, in the collection of data, a value indexed in the collection by an extended key comprising an identifier of a version of the collection.

16. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to store data indicative of at least one of an accepted or unaccepted state of a version of the collection.

17. The non-transitory computer-readable storage medium of claim 14, wherein data is added to the second version of the collection in response to determining that a source of the data is a partially trusted entity.

18. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to provide, in response to a second request to access the collection of data, access to the second version of the collection of data based on determining that the second version is associated with an accepted state.

19. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to delete data associated with a rolled-back version of a collection of data.

20. The non-transitory computer-readable storage medium of claim 14, wherein data in the collection of data is indexed by an extended key comprising an original key and a version identifier.