Scalable relational database service

• US 8,386,540 B1
• Filed: 03/31/2008
• Issued: 02/26/2013
• Est. Priority Date: 03/31/2008
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: McAlister, Grant A. M., Sivasubramanian, Swaminathan, Sheth, Rajesh S.
• Primary Examiner(s): Chen, Susan
• Application Number:
  US12/059,723
• Time in Patent Office: 1,793 Days
• Field of Search: None
• US Class Current: 707/899
• CPC Class Codes: G06F 16/256 in federated or virtual databases

Abstract

System and methods for providing a Scalable Relational Database Service (SRDBS) are disclosed. SRDBS may allow a subscriber to lease/rent a virtual relational database (a.k.a. namespace) with a specified allocation of disk space, CPU resources and/or I/O resources. The namespace may resemble a physical RDBMS, and may allow client applications to perform SQL queries. SRDBS may partition a subscriber'"'"'s database across multiple database servers automatically and may replicate each partition automatically. SRDBS may provide automatic routing of client queries to the appropriate database server holding the required data. The routing process may mask temporary data outages due to database replica failures, network failures, and/or repartitioning operations. SRDBS may employ partition maps to convey the location of data to client-side routing functions. These partition maps may use a multi-versioning scheme. SRDBS may provide a resource isolation mechanism that limits the resource utilization of each namespace to its specified allocation.

Claims

1. A computer-implemented method, comprising:

an administrative server receiving a request, made on behalf of a user of a service that provides relational database management services, for at least one of the relational database management services, wherein the request comprises data to be maintained by the service, a namespace identifier, and a partition key;

in response to said receiving, the administrative server automatically creating a virtual relational database associated with the namespace identifier, wherein said creating comprises;

dividing the data to be maintained by the service into two or more partitions, wherein the data is divided into the two or more partitions according to the partition key;

storing each partition of the data in a respective relational database on one of a plurality of computing nodes; and

storing a replica of each partition of the data in a respective relational database on a respective other one of the plurality of computing nodes;

a client library receiving a query request directed to the virtual relational database, wherein the query request comprises information usable to generate a value of the partition key for the query; and

in response to said receiving a query request, the client library;

generating the partition key value for the query; and

automatically routing the query request to at least one of the plurality of computing nodes dependent, at least in part, on the generated partition key value.

2. The method of claim 1, wherein the request for relational database management services further comprises one or more service level agreement parameter values, the method further comprising the administrative server allocating resources for the virtual database dependent, at least in part, on the one or more service level agreement parameter values.

3. The method of claim 2, wherein the one or more service level agreement parameter values comprise values indicating one or more of a quantity of requested CPU resources, a quantity of requested I/O resources, a quantity of requested database connections, or an amount of requested storage space.

4. The method of claim 1, further comprising the administrative server creating a partition map associated with the namespace and comprising information usable to identify the one of the plurality of computing nodes and the respective other one of the plurality of computing nodes storing each partition.

5. The method of claim 1, wherein said automatically routing comprises sending the query request to a gateway process configured to interact with the relational database on the one of the plurality of computing nodes or on the respective other one of the plurality of computing nodes storing the partition associated with the generated partition key value;

the method further comprising;

the gateway process accessing the relational database to execute the query request; and

the gateway process returning results of the query request.

6. The method of claim 1, wherein said automatically routing comprises consulting a partition map associated with the namespace to identify the one of the plurality of computing nodes or the respective other one of the plurality of computing nodes storing the partition associated with the generated partition key value.

7. The method of claim 6, wherein said automatically routing comprises sending the query request and a version identifier of the partition map to a gateway process configured to interact with the relational database on the one of the plurality of computing nodes or the respective other one of the plurality of computing nodes storing the partition associated with the generated partition key value, the method further comprising the gateway process determining, dependent on the version identifier, if the partition map is a current partition map.

8. The method of claim 7, further comprising, in response to determining that the partition map is a current partition map:

the gateway process accessing the relational database to execute the query request; and

the gateway process returning results of the query request.

9. The method of claim 7, further comprising, in response to determining that the partition map is not a current partition map, the gateway process performing, without executing the query request, one or more of:

returning an error or returning a current partition map.

10. The method of claim 9, further comprising the client library:

obtaining a current partition map; and

automatically routing the query request to one of the plurality of computing nodes dependent, at least in part, on the generated partition key value and the current partition map.

11. The method of claim 1, further comprising the administrative server monitoring accesses to the virtual database, wherein said monitoring comprises monitoring one or more of current resource usage associated with the virtual database, resource usage trends associated with the virtual database, query frequency, query type frequency, or partition access frequency.

12. The method of claim 11, further comprising, in response to said monitoring, the administrative server limiting the resource usage associated with the virtual database for consistency with one or more service level agreement parameter values associated with the virtual database.

13. The method of claim 11, further comprising, in response to said monitoring, the administrative server:

re-partitioning the data of at least one of the two or more partitions into two or more new partitions according to the partition key;

storing each new partition of the data in a respective relational database on one of the plurality of computing nodes; and

storing a replica of each new partition of the data in a respective relational database on a respective other one of the plurality of computing nodes.

14. The method of claim 11, further comprising, in response to said monitoring, the administrative server allocating additional resources to the virtual database.

15. The method of claim 1, further comprising, in response to a failure of one or more computing nodes, the administrative server:

promoting a replica on a non-failing one of the plurality of computing nodes of a partition stored on a failed computing node to be a primary copy of the partition; and

storing an additional replica of the partition in a relational database on another non-failing one of the plurality of computing nodes.

16. The method of claim 1, further comprising,

the administrative server receiving a request to re-partition the data;

and

in response to said receiving a request to re-partition the data, the administrative server;

re-partitioning the data of at least one of the two or more partitions into two or more new partitions according to the partition key;

storing each new partition of the data in a respective relational database on one of the plurality of computing nodes; and

storing a replica of each new partition of the data in a respective relational database on a respective other one of the plurality of computing nodes.

17. The method of claim 1, further comprising the administrative server:

receiving a request for additional resources for the virtual database; and

in response to said receiving a request for additional resources, allocating additional resources to the virtual database.

18. The method of claim 1,

wherein the request for relational database management services further comprises a database schema for the virtual database;

and

wherein said storing each partition and said storing a replica of each partition are performed according to the database schema.

19. The method of claim 1, wherein said automatically routing comprises automatically routing the query request to two or more of the plurality of computing nodes dependent, at least in part, on the generated partition key value, the method further comprising:

the client library receiving partial results of the query request from two or more of the plurality of computing nodes; and

the client library concatenating the partial results into a unified result for the query request.

20. A computing system, comprising one or more computing nodes configured to implement:

a plurality of database servers;

an administrative server; and

a client library;

wherein the administrative server is configured to;

receive a request, made on behalf of a user of a service that provides relational database management services, for at least one of the relational database management services, wherein the request comprises data to be maintained by the service, a namespace identifier, and a partition key;

in response to said receiving, automatically create a virtual relational database associated with the namespace identifier, wherein said creating comprises;

dividing the data to be maintained by the service into two or more partitions, wherein the data is divided into the two or more partitions according to the partition key;

initiating storage of each partition of the data in a respective relational database on one of the plurality of database servers; and

initiating storage of a replica of each partition of the data in a respective relational database on a respective other one of the plurality of database servers;

wherein the client library is configured to;

receive a query request directed to the virtual relational database, wherein the query request comprises information usable to generate a value of the partition key for the query; and

in response to said receiving a query request;

generate the partition key value for the query; and

automatically route the query request to at least one of the plurality of database servers dependent, at least in part, on the generated partition key value.

21. The system of claim 20,

wherein the request for relational database management services further comprises one or more service level agreement parameter values;

wherein the one or more service level agreement parameter values comprise values indicating one or more of a quantity of requested CPU resources, a quantity of requested I/O resources, a quantity of requested database connections, or an amount of requested storage space;

wherein the administrative server is further configured to allocate resources for the virtual database dependent, at least in part, on the one or more service level agreement parameter values.

22. The system of claim 20, further comprising a gateway process configured to interact with the relational database on the one of the plurality of database servers or on the respective other one of the plurality of database servers storing the partition associated with the generated partition key value;

wherein to automatically route the query request, the client library is configured to;

determine the one of the plurality of computing nodes or the respective other one of the plurality of computing nodes storing the partition associated with the generated partition key value; and

send the query request to the gateway process;

wherein the gateway process is further configured to receive the query request, and in response to receiving the query request to;

access the relational database to execute the query request; and

return results of the query request.

23. The system of claim 20, wherein the administrative server is further configured to create a partition map associated with the namespace and comprising information usable to identify the one of the plurality of database servers and the respective other one of the plurality of database servers storing each partition.

24. The system of claim 23, further comprising a gateway process configured to interact with the relational database on the one of the plurality of database servers or the respective other one of the plurality of database servers storing the partition associated with the generated partition key value;

wherein the client library is further configured to store a local copy of the partition map;

wherein to automatically route the query request, the client library is further configured to send the query request and a version identifier of the local copy of the partition map to the gateway process;

wherein the gateway process is configured to determine, dependent on the version identifier, if the local copy of the partition map is a current partition map.

25. The system of claim 24,

wherein, in response to determining that the local copy of the partition map is a current partition map, the gateway process is further configured to:

access the relational database to execute the query request; and

return results of the query request; and

wherein, in response to determining that the local copy of the partition map is not a current partition map the gateway process is further configured to perform one or more of;

returning an error without executing the query request or returning a current partition map.

26. The system of claim 20, wherein the administrative server is further configured to monitor accesses to the virtual database, wherein to monitor accesses, the administrative server is configured to monitor one or more of:

current resource usage associated with the virtual database, resource usage trends associated with the virtual database, query frequency, query type frequency, or partition access frequency.

27. The system of claim 26, wherein, in response to said monitoring, the administrative server is configured to perform one or more of:

re-partitioning the data of at least one of the two or more partitions into two or more new partitions according to the partition key, limiting the resource usage associated with the virtual database, or allocating additional resources to the virtual database.

28. The system of claim 20, wherein, in response to a failure of one or more database servers, the administrative server is further configured to promote a replica on a non-failing one of the plurality of database servers of a partition stored on a failed database server to be a primary copy of the partition.

29. The system of claim 20,

wherein the request for relational database management services further comprises a database schema for the virtual database;

and

wherein to initiate storage of each partition and a replica of each partition, the administrative server is further configured to initiate storage of each partition and a replica of each partition according to the database schema.

30. The system of claim 20,

wherein to automatically route, the client library is further configured to automatically route the query request to two or more of the plurality of database servers dependent, at least in part, on the generated partition key value;

and

wherein the client library is further configured to;

receive partial results of the query request from two or more of the plurality of database servers; and

concatenate the partial results into a unified result for the query request.

31. A computing system, comprising:

one or more processors; and

a memory coupled to the processor and configured to store program instructions executable by the one or more processors to implement;

an administrative server receiving a request, made on behalf of a user of a service that provides relational database management services, for at least one of the relational database management services, wherein the request comprises data to be maintained by the service, a namespace identifier, and a partition key;

in response to said receiving, the administrative server automatically creating a virtual relational database associated with the namespace identifier, wherein said creating comprises;

dividing the data to be maintained by the service into two or more partitions, wherein the data is divided into the two or more partitions according to the partition key;

initiating storage of each partition of the data in a respective relational database on one of a plurality of computing nodes; and

initiating storage of a replica of each partition of the data in a respective relational database on a respective other one of the plurality of computing nodes;

a client library receiving a query request directed to the virtual relational database, wherein the query request comprises information usable to generate a value of the partition key for the query; and

in response to said receiving a query request, the client library;

generating the partition key value for the query;

automatically routing the query request to at least one of the plurality of computing nodes dependent, at least in part, on the generated partition key value; and

returning results of the query request.

32. The system of claim 31,

wherein the request for relational database management services further comprises one or more service level agreement parameter values;

wherein the one or more service level agreement parameter values comprise values indicating one or more of a quantity of requested CPU resources, a quantity of requested I/O resources, a quantity of requested database connections, or an amount of requested storage space; and

wherein the program instructions are further executable to implement the administrative server allocating resources for the virtual database dependent, at least in part, on the one or more service level agreement parameter values.

33. The system of claim 31, wherein the program instructions are further executable to implement the administrative server creating a partition map associated with the namespace and comprising information usable to identify the one of the plurality of computing nodes and the respective other one of the plurality of computing nodes storing each partition.

34. The system of claim 31, wherein the program instructions are further executable to implement the administrative server monitoring accesses to the virtual database, wherein said monitoring comprises monitoring one or more of:

current resource usage associated with the virtual database, resource usage trends associated with the virtual database, query frequency, query type frequency, or partition access frequency.

35. The system of claim 34, wherein the program instructions are further executable to implement, in response to said monitoring, the administrative server performing one or more of:

re-partitioning the data of at least one of the two or more partitions into two or more new partitions according to the partition key, limiting the resource usage associated with the virtual database, or allocating additional resources to the virtual database.

36. The system of claim 31, wherein, in response to a failure of one or more computing nodes, the program instructions are further executable to implement the administrative server promoting a replica on a non-failing one of the plurality of computing nodes of a partition stored on a failed database server to be a primary copy of the partition.

37. The system of claim 31,

wherein the request for relational database management services further comprises a database schema for the virtual database;

and

wherein said initiating storage of each partition and said initiating storage of a replica of each partition comprise initiating storage of each partition and each replica according to the database schema.

38. The system of claim 31,

wherein said automatically routing comprises routing the query request to two or more of the plurality of computing nodes dependent, at least in part, on the generated partition key value;

and

wherein the program instructions are further executable to implement;

the client library receiving partial results of the query request from two or more of the plurality of computing nodes; and

the client library concatenating the partial results into a unified result for the query request.

39. A non-transitory, computer-readable storage medium storing program instructions computer-executable to implement:

an administrative server receiving a request, made on behalf of a user of a service that provides relational database management services, for at least one of the relational database management services, wherein the request comprises data to be maintained by the service, a namespace identifier, and a partition key;

in response to said receiving, the administrative server automatically creating a virtual relational database associated with the namespace identifier, wherein said creating comprises;

dividing the data to be maintained by the service into two or more partitions, wherein the data is divided into the two or more partitions according to the partition key;

initiating storage of each partition of the data in a respective relational database on one of a plurality of computing nodes; and

initiating storage of a replica of each partition of the data in a respective relational database on a respective other one of the plurality of computing nodes;

a client library receiving a query request directed to the virtual relational database, wherein the query request comprises information usable to generate a value of the partition key for the query; and

in response to said receiving the query request, the client library;

generating the partition key value for the query;

automatically routing the query request to at least one of the plurality of computing nodes dependent, at least in part, on the generated partition key value; and

returning results of the query request.

40. The storage medium of claim 39,

wherein the request for relational database management services further comprises one or more service level agreement parameter values;

wherein the one or more service level agreement parameter values comprise values indicating one or more of a quantity of requested CPU resources, a quantity of requested I/O resources, a quantity of requested database connections, or an amount of requested storage space; and

wherein the program instructions are further executable to implement the administrative server allocating resources for the virtual database dependent, at least in part, on the one or more service level agreement parameter values.

41. The storage medium of claim 39, wherein the program instructions are further executable to implement the administrative server creating a partition map associated with the namespace and comprising information usable to identify the one of the plurality of computing nodes and the respective other one of the plurality of computing nodes storing each partition.

42. The storage medium of claim 39, wherein the program instructions are further executable to implement the administrative server monitoring accesses to the virtual database, wherein said monitoring comprises monitoring one or more of:

current resource usage associated with the virtual database, resource usage trends associated with the virtual database, query frequency, query type frequency, or partition access frequency.

43. The storage medium of claim 42, wherein the program instructions are further executable to implement, in response to said monitoring, the administrative server performing one or more of:

re-partitioning the data of at least one of the two or more partitions into two or more new partitions according to the partition key, limiting the resource usage associated with the virtual database, or allocating additional resources to the virtual database.

44. The storage medium of claim 39, wherein, in response to a failure of one or more computing nodes, the program instructions are further executable to implement the administrative server promoting a replica on a non-failing one of the plurality of computing nodes of a partition stored on a failed database server to be a primary copy of the partition.

45. The storage medium of claim 39,

wherein the request for relational database management services further comprises a database schema for the virtual database;

and

wherein said initiating storage of each partition and a replica of each partition comprises initiating storage of each partition and a replica of each partition according to the database schema.