System and method for implementing a scalable data storage service

• US 8,918,435 B2
• Filed: 11/25/2013
• Issued: 12/23/2014
• 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, Blackman, Rande A., Rath, Timothy Andrew, Bradford, Raymond S., McAlister, Grant Alexander MacDonald, Kulesza, Jakub, Hamilton, James R., Cabrera, Luis Felipe, Buragahain, Chiranjeeb
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US14/088,786
• Publication Number:
  US 20140082028A1
• Time in Patent Office: 393 Days
• Field of Search: 707/803, 707/804, 707/809, 707/968, 707/972
• US Class Current: 707/803
• 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;

wherein, 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 table name and a primary key by which to partition and index items stored in the table, the data storage service is configured to;

initiate performance of an asynchronous table creation workflow at a workflow component in order to create a scalable table in the non-relational data store, wherein the scalable table is configured to store a plurality of items each of which comprises a value for the primary key, and wherein the scalable table does not have a pre-determined size limit; and

subsequent to detection of the scalable table having been created, the data storage service is configured to programmatically cause the scalable table to be sized or partitioned in response to detection of an anomaly in the system or in response to receipt of one or more service requests to store, retrieve, modify, or delete items in the scalable table.

2. The system of claim 1,

wherein in response to receipt of a service request to describe one or more tables maintained by the data storage service, the data storage service is configured to return information about the one or more tables, wherein the information about the one or more tables comprises information indicating whether the scalable table has been successfully created by the asynchronous table creation workflow.

3. The system of claim 1,

wherein in response to receipt of one or more service requests to store a plurality of items in the scalable table, the data storage service is configured to:

determine whether the plurality of items can be stored in a single partition of the scalable table; and

in response to a determination that the plurality of items cannot be stored in a single partition of the scalable table, the data storage service is configured to perform said programmatic partition of the scalable table.

4. The system of claim 1,

wherein the primary key comprises a single attribute that is designated as a hash key attribute;

and

wherein to partition the scalable table, the data storage service is configured to divide the items in the scalable table into two or more partitions dependent on a hash of their respective hash key attribute values.

5. The system of claim 1,

wherein the service request to create a table further comprises an indication of one or more user preferences, wherein the one or more user preferences comprise a preferred service request throughput level or a service request throughput level for which a guarantee is requested;

and

wherein the data storage service is configured to programmatically cause the scalable table to be sized or partitioned in response to detecting that one or more of the user preferences is not being met.

6. The system of claim 1, wherein programmatically causing the scalable table to be partitioned is performed in response to receipt of an increasing number of requests targeting items in the scalable table, items in a particular partition of the scalable table, or items stored on a same computing node as at least a subset of the items in the scalable table.

7. A method, comprising:

performing by one or more computers;

receiving a request to create a table in a non-relational data store, wherein the request specifies an identifier of the table and a primary key by which to index items stored in the table; and

in response to said receiving;

initiating performance of an asynchronous table creation workflow to create a scalable table in the non-relational data store, wherein the scalable table is configured to store a plurality of items each of which comprises a value for the primary key, and wherein the scalable table does not have a pre-determined size limit;

detecting that the scalable table is successfully created upon completion of the asynchronous table creation workflow; and

subsequent to said detecting that the scalable table is successfully created, programmatically causing at least one of sizing or partitioning the scalable table in response to detection of an anomaly in the system or in response to receipt of one or more service requests to store, retrieve, modify, or delete items in the scalable table.

8. The method of claim 7, wherein the asynchronous table creation workflow comprises:

gathering information reflecting the status of one or more of the plurality of computing nodes; and

determining one or more computing nodes on which to create the scalable table dependent on the gathered information.

9. The method of claim 7,

wherein the method further comprises:

receiving a request to describe one or more tables maintained in the non-relational data store; and

in response to receiving the request to describe one or more tables, returning information about the one or more tables, wherein the information about the one or more tables comprises information indicating whether the scalable table has been successfully created by the asynchronous table creation workflow.

10. The method of claim 7,

wherein the primary key comprises a single attribute that is designated as a hash key attribute;

wherein each of the items stored in the scalable table comprises a respective value for the hash key attribute; and

wherein programmatically partitioning the scalable table comprises dividing the items in the scalable table into two or more partitions dependent on a hash of their respective hash key attribute values.

11. The method of claim 7, wherein said programmatically partitioning the scalable table comprises moving or splitting a partition of the scalable table while one or more replicas of the partition continue to accept and process requests.

12. The method of claim 7, wherein said programmatically partitioning the scalable table is performed in response to receiving an increasing number of requests targeting items in the scalable table, items in a particular partition of the scalable table, or items stored on a same computing node as at least a subset of the items in the scalable table, or in response to receiving a decreasing number of requests targeting items in the scalable table, items in a particular partition of the scalable table, or items stored on a same computing node as at least a subset of the items in the scalable table.

13. The method of claim 7,

wherein the request to create a table further comprises an indication of one or more user preferences, wherein the one or more user preferences comprise a preferred service request throughput level or a service request throughput level for which a guarantee is requested;

and

wherein said programmatically performing at least one of sizing or partitioning the scalable table is performed in response to detecting that one or more of the user preferences is not being met.

14. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

receiving a service request to create a table on behalf of a storage service client, wherein the service request specifies an identifier of the table and a primary key by which to index items stored in the table; and

in response to said receiving;

initiating performance of an asynchronous table creation workflow to create a scalable table in a non-relational data store, wherein the scalable table is configured to store a plurality of items each of which comprises a value for the primary key, and wherein the scalable table does not have a pre-determined size limit;

detecting that the scalable table is successfully created upon completion of the asynchronous table creation workflow; and

subsequent to said detecting that the scalable table is successfully created, programmatically causing at least one of sizing or partitioning the scalable table in response to detection of an anomaly in the system or in response to receipt of one or more service requests to store, retrieve, modify, or delete items in the scalable table.

15. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions when executed on the one or more computers cause the one or more computers to further perform:

generating metadata associated with the scalable table; and

storing the metadata in another scalable table in the non-relational data store.

16. The non-transitory, computer-readable storage medium of claim 15,

wherein the asynchronous table creation workflow comprises:

upon successful creation of the scalable table, updating a table state in the metadata associated with the scalable table in the other scalable table to indicate the scalable table is successfully created;

wherein, in said detecting that the scalable table is successfully created, the program instructions when executed on the one or more computers cause the one or more computers to perform;

evaluating the table state in the metadata associated with the scalable table to determine that the scalable table is successfully created.

17. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions when executed on the one or more computers cause the one or more computers to further perform:

in response to receiving a request to delete the scalable table, initiating performance of an asynchronous delete table workflow to delete the scalable table from the non-relational data store.

18. The non-transitory, computer-readable storage medium of claim 14,

wherein the primary key comprises an attribute that is designated as a hash key attribute and another attribute designated as a range key attribute;

wherein each of the items stored in the scalable table comprises a respective value for the hash key attribute and a respective value for the range key attribute;

wherein the range key attribute value uniquely identifies a particular item from among all items in the scalable table having a same hash key attribute value, wherein the items having the same hash key are ordered according to their respective range key attribute values; and

wherein, in said programmatically partitioning the scalable table, the program instructions when executed on the one or more computers cause the one or more computers to perform dividing items in the scalable table having a same hash key attribute value into two or more partitions dependent on their respective range key attribute values.