Local emulation of distributed key-value data store

• US 9,235,609 B1
• Filed: 10/15/2013
• Issued: 01/12/2016
• Est. Priority Date: 10/15/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sivasubramanian, Swaminathan, Shams, Khawaja Salman, Yanacek, David Craig, Pandey, Prashant, Zaki, Omer Ahmed, Olson, Johanna S, de Kock, Hendrik Jacobus, Wu, Johnny Ying, Gupta, Aanchal
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US14/054,773
• Time in Patent Office: 819 Days
• Field of Search: 707/695
• US Class Current: 1/1
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems

Abstract

A local data store may also be configured to process updates using a common API with reference to a common schema. The common API and common schema may also be employed by hosted applications utilizing a remote distributed data store. Behavior of the remote distributed data store may be emulated by the local data store. Behaviors of the distributed data store that may be simulated include eventual consistency, provisioned throughput and latency based on horizontal partitioning.

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:

process one or more invocations of an application programming interface, the one or more invocations based at least in part on a first schema, wherein a first collection of items maintained on a distributed data store conforms to the first schema, the one or more invocations corresponding to one or more requests to read or write items of a second collection of items maintained on one or more computing devices remote to the distributed data store, the second collection of items conforming to a second schema, wherein processing the one or more invocations is based at least in part on mapping between the first schema and the second schema; and

emulate at least one behavior of the distributed data store by performing at least one of;

returning a version of an item of the second collection, the version of the item corresponding to a state of the item prior to processing the one or more invocations of the application programming interface;

determining to deny at least one of the requests to read or write items of the second collection of items, the determining based at least in part on throughput consumed by previously processed requests exceeding a threshold level, the threshold level based at least in part on a maximum throughput level permitted on the distributed data store;

or

simulating latency based at least in part on a horizontal partitioning of the distributed data store.

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

maintain one or more previous versions of the state of the item prior to processing the one or more invocations of the application programming interface.

3. The non-transitory computer-readable medium of claim 1, wherein the second collection of items is maintained on the second one or more computing devices by a relational database management system.

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

emulate a behavior of the distributed data store by returning, in response to a query, a set of items of the second collection of items based at least in part on a version of an index over the second collection of items, the version corresponding to a state of the index prior to processing the one or more invocations of the application programming interface.

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

emulate a behavior of the distributed data store by adding random latency to the processing of the one or more invocations of the application programming interface.

6. The non-transitory computer-readable medium of claim 5, wherein the latency is based at least in part on a replication scheme of the distributed data store.

7. The non-transitory computer-readable medium of claim 1, wherein mapping comprises associating a column of the items in the first collection of items with a column of items in the second collection of items.

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

determine a level of provisioned throughput for the distributed data store based at least in part on throughput consumed by processing the requests to read or write items of the second collection of items.

9. A method comprising:

processing one or more invocations of an application programming interface, the one or more invocations based at least in part on a first schema, wherein a first collection of items maintained on a distributed data store conforms to the first schema, the one or more invocations corresponding to one or more requests to read or write items of a second collection of items maintained on one or more computing devices remote to the distributed data store, the second collection of items conforming to a second schema; and

emulating at least one behavior of the distributed data store by performing at least one of;

returning a version of an item of the second collection, the version of the item corresponding to a state of the item prior to processing the one or more invocations of the application programming interface;

determining to deny at least one of the requests to read or write items of the second collection of items, the determining based at least in part on throughput consumed by previously processed requests exceeding a threshold level, the threshold level based at least in part on a maximum throughput level permitted on the distributed data store;

or

simulating a first latency based at least in part on a horizontal partitioning of the distributed data store.

10. The method of claim 9, further comprising:

determining the first latency based at least in part on a number of partitions spanned by a request.

11. The method of claim 9, further comprising:

maintaining one or more previous versions of the state of the item prior to processing the one or more invocations of the application programming interface.

12. The method of claim 9, wherein the second collection of items is maintained on the second one or more computing devices by at least one of a key-value database, a relational database, a document-oriented database, an object-oriented database, a JSON store, or an in-memory data structure.

13. The method of claim 9, further comprising:

emulating a behavior of the distributed data store by returning, in response to a query, a set of items of the second collection of items based at least in part on a version of an index over the second collection of items, the version corresponding to a state of the index prior to processing the one or more invocations of the application programming interface.

14. The method of claim 9, further comprising:

emulating a behavior of the distributed data store by adding latency to the processing of the one or more invocations of the application programming interface, the added latency based at least in part on a replication scheme of the distributed data store.

15. The method of claim 9, further comprising:

receiving information indicative of at least one of a horizontal partitioning scheme, an indexing scheme, or a replication scheme of the distributed data store.

16. A system comprising:

one or more computing nodes remote to a distributed data store maintaining a first collection of items conforming to a first schema, the one or more computing nodes maintaining a second collection of items conforming to a second schema;

a first one or more computing nodes configured at least to;

process one or more invocations of an application programming interface, the one or more invocations based at least in part on the first schema, the one or more invocations corresponding to one or more requests to read or write items of the second collection of items, wherein processing the one or more invocations is based at least in part on mapping between the first schema and the second schema; and

emulate at least one behavior of the distributed data store by performing at least one of;

returning a version of an item of the second collection, the version of the item corresponding to a state of the item prior to processing the one or more invocations of the application programming interface;

determining to deny at least one of the requests to read or write items of the second collection of items, the determining based at least in part on throughput consumed by previously processed requests exceeding a threshold level, the threshold level based at least in part on a maximum throughput level permitted on the distributed data store;

or

simulating a first latency based at least in part on a horizontal partitioning of the distributed data store.

17. The system of claim 16, the first one or more computing nodes further configured at least to:

receive, from the distributed data store, information indicative of at least one of a horizontal partitioning scheme, an indexing scheme, or a replication scheme.

18. The system of claim 16, the first one or more computing nodes further configured at least to:

determine the first latency based at least in part on a number of partitions spanned by a request.

19. The system of claim 16, the first one or more computing nodes further configured at least to:

maintain one or more previous versions of the state of the item prior to processing the one or more invocations of the application programming interface.

20. The system of claim 16, wherein mapping comprises associating a column of the items in the first collection of items with a column of items in the second collection of items.