System and method for implementing a scalable data storage service

• US 9,754,009 B2
• Filed: 08/29/2016
• Issued: 09/05/2017
• Est. Priority Date: 06/27/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sivasubramanian, Swaminathan, Stefani, Stefano, Buragohain, Chiranjeeb, Blackman, Rande A., Rath, Timothy Andrew, Bradford, Raymond S., MacDonald McAlister, Grant Alexander, Kulesza, Jakub, Hamilton, James R., Cabrera, Luis Felipe
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US15/250,435
• Publication Number:
  US 20160378845A1
• Time in Patent Office: 372 Days
• Field of Search: 707803, 707809, 707968, 707972
• CPC Class Codes: G06F 12/0848 Partitioned cache, e.g. separate instruction and operand caches
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/252 between a Database Management System and a front-end application
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: Y10S 707/968 Partitioning
• CPC Class Codes: Y10S 707/972 Partitioning

Abstract

A system that implements a scalable data storage service may maintain tables in a non-relational data store on behalf of clients. The system may provide a Web services interface through which service requests are received, and an API usable to request that a table be created, deleted, or described; that an item be stored, retrieved, deleted, or its attributes modified; or that a table be queried (or scanned) with filtered items and/or their attributes returned. An asynchronous workflow may be invoked to create or delete a table. Items stored in tables may be partitioned and indexed using a simple or composite primary key. The system may not impose pre-defined limits on table size, and may employ a flexible schema. The service may provide a best-effort or committed throughput model. The system may automatically scale and/or re-partition tables in response to detecting workload changes, node failures, or other conditions or anomalies.

Claims

1. A system, comprising:

a plurality of computing nodes, each comprising at least one processor and memory, that collectively implement a data storage service that provides a network-based interface through which service requests are received, wherein the data storage service comprises a plurality of storage nodes that collectively implement a non-relational data store;

the data storage service is configured to, in response to receipt of a service request to create a table on behalf of a storage service client, and wherein the service request specifies a committed throughput level for servicing requests directed to the table, allocate resources for the table at one or more of the plurality of storage nodes in the non-relational data store in order to create the table, wherein the allocated resources are sufficient for the table to meet the specified committed throughput level; and

the data storage service is configured to, subsequent to the allocation of resources for the table, modify the resources allocated to the table in response to receiving a request to modify the committed throughput level for the table.

2. The system of claim 1, wherein to allocate resources for the table, the data storage service is configured to:

determine a number of partitions of the table to create; and

create the determined number of partitions at the one or more storage nodes.

3. The system of claim 2, wherein to modify the resources allocated to the table, the data storage service is configured to modify the number of partitions of the table.

4. The system of claim 3, wherein to modify the number of partitions of the table, the data storage service is configured to perform at least one of:

add a partition for the table at one or more different storage nodes;

or

remove a partition for the table at one of the one or more storage nodes.

5. The system of claim 1, wherein in response to service request traffic directed to the table exceeding a current committed throughput level, the data storage service is configured to throttle at least a portion of service requests that are received in excess of the current committed throughput level, wherein the current committed throughput level is the specified committed throughput level or the increased committed throughput level.

6. The system of claim 1, wherein in response to service request traffic directed to the table exceeding a current committed throughput level, the data storage service is configured to service at least a portion of service requests that are received in excess of the current committed throughput level, wherein the current committed throughput level is the specified committed throughput level or the increased committed throughput level.

7. The system of claim 1,

wherein the data storage service is configured to receive a service request to decrease the committed throughput level for the table, wherein the request specifies a decreased committed throughput level for the table;

and

wherein, in response to receiving the request to decrease the committed throughput level for the table, the data storage service is configured to decrease the resources reserved for the table.

8. A method, comprising:

performing, by one or more computing devices;

receiving a request to create a table in a non-relational data store, wherein the request specifies a committed throughput level for servicing requests directed to the table, wherein the request is formatted according to a programmatic interface for the non-relational data store; and

in response to said receiving;

allocating resources for the table at one or more of a plurality of storage nodes implemented as part of the non-relational data store in order to create the table, wherein the allocated resources are sufficient for the table to meet the specified committed throughput level; and

subsequent to the allocation of resources for the table, modifying the resources allocated to the table in response to receiving a request to modify the committed throughput level for the table.

9. The method of claim 8, wherein allocating resources for the table comprises:

determining a number of partitions of the table to create; and

creating the determined number of partitions at the one or more storage nodes.

10. The method of claim 9, wherein modifying the resources comprises modifying the number of partitions of the table.

11. The method of claim 10, wherein modifying the number of partitions of the table comprises at least one of:

adding a partition for the table at one or more different storage nodes;

or

removing a partition for the table at one of the one or more storage nodes.

12. The method of claim 8, wherein the request to create a table specifies selection of a committed throughput model from among two or more throughput models supported by the data store, and wherein the two or more throughput models further comprise a best effort throughput model.

13. The method of claim 12, wherein said allocating comprises allocating storage resources for the table that provide lower latency accesses than storage resources allocated for tables being maintained by the data store under the best effort throughput model.

14. The method of claim 8, wherein the specified committed throughput level comprises a specified committed throughput level for read accesses and a separately specified committed throughput level for write accesses.

15. A non-transitory, computer-readable storage medium, comprising program instructions that when executed by one or more computing devices causing the one or more computing devices to implement:

receiving a request to create a table in a non-relational data store, wherein the request specifies a committed throughput level for servicing requests directed to the table, wherein the request is formatted according to a programmatic interface for the non-relational data store; and

in response to said receiving;

allocating resources for the table at one or more of a plurality of storage nodes implemented as part of the non-relational data store in order to create the table, wherein the allocated resources are sufficient for the table to meet the specified committed throughput level; and

subsequent to the allocation of resources for the table, modifying the resources allocated to the table in response to receiving a request to modify the committed throughput level for the table.

16. The non-transitory, computer-readable storage medium of claim 15, wherein, in allocating resources for the table, the program instructions cause the one or more computing devices to implement:

determining a number of partitions of the table to create; and

creating the determined number of partitions at the one or more storage nodes.

17. The non-transitory, computer-readable storage medium of claim 16, wherein, in modifying the resources, the program instructions cause the one or more computing devices to implement modifying the number of partitions of the table.

18. The non-transitory, computer-readable storage medium of claim 17, wherein, in modifying the number of partitions of the table, the program instructions cause the one or more computing devices to implement at least one of:

adding a partition for the table at one or more different storage nodes;

or

removing a partition for the table at one of the one or more storage nodes.

19. The non-transitory, computer-readable storage medium of claim 15, wherein, in modifying the resources allocated to the table, the program instructions cause the one or more computing devices to implement replacing a portion of the resources allocated to the table at one of the one or more storage nodes with a different one of the plurality of storage nodes.

20. The non-transitory, computer-readable storage medium of claim 19, wherein, in replacing the portion of the resources allocated to the table at the one of the one or more storage nodes with the different one of the plurality of storage nodes, the program instructions cause the one or more computing devices to implement copying one or more partitions of the table from the one storage node to the different storage node.