Commit and rollback of data streams provided by partially trusted entities

• US 10,025,943 B1
• Filed: 10/13/2014
• Issued: 07/17/2018
• 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:
  US14/513,070
• Time in Patent Office: 1,373 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 non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by one or more computing devices, cause the one or more computing devices at least to:

maintain on one or more storage devices a first version of a collection of key-value pairs, first version of the collection comprising a first version of a value;

store a second version of the value in response to a request comprising a key and the second version of the value;

associate an identifier of a second version of the collection with information indicative of an unaccepted state of the collection;

store, on the storage device, a mapping between an extended key and the second version of the value, the extended key comprising the identifier of the second version of the collection and the key;

access the first version of the value based at least in part on using the extended key to determine that the second version of the value is associated with the unaccepted state, wherein the extended key is identified by a subset of the extended key corresponding to the key;

associate the identifier of the second version of the collection with information indicative of an accepted state in response to receiving information indicative of the second version of the collection being accepted; and

access the second version of the value based at least in part on using the extended key to determine that the second version of the value is associated with an accepted state.

2. The non-transitory computer-readable storage medium of claim 1, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

add an entry to an index structure maintained on the one or more storage devices, the entry comprising the extended key; and

access the second version of the value by traversing the index structure and locating the entry based at least in part on the identifier of the second version of the value and the key.

3. The non-transitory computer-readable storage medium of claim 2, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

access the first and second versions of the value by traversing the index structure and locating the first and second versions of the value using the key.

4. The non-transitory computer-readable storage medium of claim 1, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

associate the first version of the collection with information indicative of a time; and

associate the first version of the collection with information indicative of a rejected state, based at least in part on using the information indicative of the time to locate the first version of the collection.

5. The non-transitory computer-readable storage medium of claim 1, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

in response to receiving information indicative of a partial acceptance of the second version of the collection, the partial acceptance including the value, form an additional version of the collection by at least forming an additional extended key comprising an identifier of the additional version of the collection and the key; and

associate the identifier of the additional version of the collection with an accepted state.

6. The non-transitory computer-readable storage medium of claim 1, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

store the mapping between the extended key and the second version of the value in a first transaction context; and

store a mapping between an additional extended key and an additional version of the value in a second transaction context, wherein the additional extended key comprises the identifier of the second version of the collection.

7. The non-transitory computer-readable storage medium of claim 1, wherein the second version of the collection of key-value pairs corresponds to a plurality of updates to the first version of the collection of key-value pairs, the plurality of updates transmitted by a partially trusted entity.

8. The non-transitory computer-readable storage medium of claim 1, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

cause a rollback of updates associated with the second version of the collection by at least associating the identifier of the second version of the collection with information indicative of a rejected state of the collection.

9. The non-transitory computer-readable storage medium of claim 8, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

execute a background task to delete key-value pairs associated with the second version of the collection, based at least in part on the identifier of the second version of the collection being associated with the rejected state.

10. A method for performing a metatransactional commit on data received from a partially trusted entity, the method comprising:

maintaining on one or more storage devices a first version of a collection of key-value pairs, the first version of the collection comprising a first version of a value;

storing a second version of the value in response to a request comprising a key and the second version of the value;

associating an identifier of a second version of the collection with information indicative of an unaccepted state of the collection;

storing, on the one or more storage devices, a mapping between an extended key and the second version of the value, the extended key comprising the identifier of the second version of the collection and the key;

accessing the first version of the value based at least in part on using the extended key to determine that the second version of the value is associated with the unaccepted state, wherein the extended key is identified by a subset of the extended key corresponding to the key;

associating the identifier of the second version of the collection with information indicative of an accepted state in response to receiving information indicative of the second version of the collection being accepted; and

accessing the second version of the value based at least in part on using the extended key to determine that the second version of the value is associated with an accepted state.

11. The method of claim 10, further comprising:

adding an entry to an index structure maintained on the one or more storage devices, the entry comprising the extended key;

accessing the second version of the value by traversing the index structure and locating the entry based at least in part on the identifier of the second version of the value and the key; and

accessing the first and second versions of the value by traversing the index structure and locating the first and second versions of the value using the key.

12. The method of claim 10, further comprising:

associating the first version of the collection with information indicative of a time; and

associating the first version of the collection with information indicative of the trusted entity rejecting the first version of the collection, based at least in part on using the information indicative of the time to locate the first version of the collection.

13. The method of claim 10, further comprising:

receiving, from a trusted entity data indicative of a partial acceptance of the second version of the collection, the data including the value;

forming an additional version of the collection by at least forming an additional extended key comprising an identifier of the additional version of the collection and the key; and

associating the identifier of the additional version of the collection with information indicative of an accepted state.

14. The method of claim 10, further comprising:

associating the identifier of the second version of the collection with information indicative of a rejected state of the collection.

15. The method of claim 10, further comprising:

permitting access to the second version of the value when the first version of the collection is associated with the unaccepted state, based at least in part on the access being requested by the trusted entity.

16. A system comprising:

at least one processor; and

at least one memory having stored thereon computer-readable instructions that, upon execution by the at least one processor, cause the system at least to;

store a first version of a value in a first version of a collection of key-value pairs;

store a second version of the value in a second version of the collection of key-value pairs, the second version of the collection stored with information indicative of an unaccepted state of the second version of the collection;

store a mapping between an extended key and the second version of the value, the extended key comprising an identifier of the second version of the collection and a key associated with the second version of the value;

access the first version of the value based at least in part on using the extended key to determine that the second version of the value is associated with the unaccepted state;

store information indicative of an accepted state of the second version of the collection; and

access the second version of the value based at least in part on using the extended key to determine that the second version of the value is associated with the accepted state.

17. The system of claim 16, wherein the at least one memory has stored thereon further computer-executable instructions that, upon execution by the at least one processor, cause the system at least to:

split the second version of the collection into a plurality of collections based at least in part on a partial rejection of the second version of the collection.

18. The system of claim 16, wherein the second version of the value is stored in response to a request from a partially trusted entity.

19. The system of claim 16, wherein a request to accept the second version of the collection is associated with a trusted entity.

20. The system of claim 16, wherein the at least one memory has stored thereon further computer-executable instructions that, upon execution by the at least one processor, cause the system at least to:

store information indicative of a rejected state of the second version of the collection.