Versioning of database partition maps

• US 9,558,207 B1
• Filed: 02/28/2013
• Issued: 01/31/2017
• 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:
  US13/781,345
• Time in Patent Office: 1,433 Days
• Field of Search: 707/4, 707/770, 707/899, 715/716
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools

Abstract

System and methods for managing versions of partition maps in a distributed data store are disclosed. A relational database may use partition maps to indicate the location of data in a particular partition, or in a replica thereof. These partition maps may be versioned using a two-stage mechanism in which partition map updates are communicated to all nodes, or to affected nodes only, and in which operation may continue without waiting for acknowledgment of their application to each node. The system may handle minor partition changes differently than major partition changes. For example, if a replica of a partition is promoted to be a primary copy due to hardware or network failures, partition map changes may only be propagated to nodes in the same replica group. For major partition changes (e.g., splits, moves, mergers, added partitions, or size change), a new partition map may be made available to all nodes.

Claims

1. A computing system, comprising:

a plurality of physical computing nodes that implement a distributed data store configured to;

receive a request to store data on behalf of one of a plurality of clients; and

in response to said receiving, create a virtual relational database in which to store the data, wherein in creating the virtual relational database, the plurality of computing nodes are collectively configured to;

divide the data into two or more partitions, and

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

subsequent to said creating;

monitor accesses to at least one of the partitions of the data that is stored in the virtual relational database;

determine, based at least in part on said monitoring, whether to change the partitioning of the data that is stored in the virtual relational database;

in response to determining that the partitioning of the data should be changed, automatically change the partitioning of at least a portion of the data that is stored in the virtual relational database.

2. The system of claim 1, wherein to automatically change the partitioning of at least a portion of the data that is stored in the virtual relational database, the plurality of computing nodes are configured to:

store a replica of each partition of the data that is stored in the virtual relational database in a respective relational database on one of the plurality of computing nodes.

3. The system of claim 1, wherein to automatically change the partitioning of data that is stored in the virtual relational database, the plurality of computing nodes are configured to:

re-partition the data of at least one of the two or more partitions into two or more new partitions, merge two or more partitions into a new partition, or move data from one or more partitions into a new partition; and

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

4. The system of claim 3,

wherein the plurality of computing nodes are further configured to store a replica of each new partition of the data in a respective relational database on one of the plurality of computing nodes.

5. The system of claim 1, wherein the plurality of computer nodes are further collectively configured to:

determine that there has been a failure of a component in the system; and

in response to determining that there has been a failure of a component in the system, automatically change partitioning of at least a portion of the data that is stored in the virtual relational database.

6. A computer-implemented method, comprising:

receiving a request to store data;

subsequent to said receiving, creating a virtual relational database in which to store the data, wherein said creating the virtual relational database comprises;

dividing data into two or more partitions;

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

subsequent to said creating;

monitoring accesses to at least one of the partitions of the data stored in the virtual relational database;

determining that partitioning of the data stored in the virtual relational database should be changed, said determining that the partitioning of the data should be changed is based, at least in part, on said monitoring; and

in response to determining that the partitioning of the data stored in the virtual relational database should be changed, automatically changing the partitioning of at least a portion of the data stored in the virtual relational database.

7. The method of claim 6, further comprising:

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

8. The method of claim 6, wherein said determining that the partitioning of the data stored in the virtual relational database should be changed comprises determining that a size of a given one of the two or more partitions of the data stored in the virtual relational database is larger than a pre-determined maximum partition size.

9. The method of claim 6, wherein said determining that the partitioning of the data stored in the virtual relational database should be changed comprises determining that there has been a change in performance for accesses directed to the virtual relational database.

10. The method of claim 6, wherein said determining that the partitioning of the data stored in the virtual relational database should be changed comprises determining that write accesses directed to a given one of the two or more partitions of data stored in the virtual relational database are more numerous or more frequent than write accesses to other ones of the two or more partitions of data stored in the virtual relational database.

11. The method of claim 6, further comprising:

determining that there has been a change in a parameter of a service level agreement associated with the virtual relational database; and

in response to determining that there has been a change in a parameter of a service level agreement associated with the virtual relational database, automatically changing the partitioning of at least a portion of the data stored in the virtual relational database.

12. The method of claim 6, further comprising:

storing one or more replicas of each of the two or more partitions in a respective relational database.

13. The method of claim 6, further comprising:

receiving a request for usage metrics associated with the virtual relational database; and

returning the requested usage metrics.

14. The method of claim 6,

wherein the request to store data specifies a partition key;

wherein dividing the data into two or more partitions comprises dividing the data into multiple partitions each corresponding to a different range of values for the partition key; and

wherein storing each of the two or more partitions in a respective relational database comprises determining a placement for each of the two or more partitions in a respective one of the plurality of database servers based, at least in part, on a hash of the partition key.

15. The method of claim 14, wherein said automatically re-partitioning at least a portion of the data comprises dividing a given one of the two or more partitions into two or more new partitions each corresponding to a smaller range of values for the partition key than the range of values for the partition key corresponding to the given partition.

16. The method of claim 6,

wherein the request to store data specifies a partition key;

wherein dividing the data into two or more partitions comprises dividing the data into multiple partitions each corresponding to a different range of values for the partition key; and

wherein said automatically re-partitioning at least a portion of the data comprises deleting data for which the partition key value will no longer be in a range of values corresponding to a given partition subsequent to the re-partitioning from the given partition.

17. 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:

creating a virtual relational database in which to store data on behalf of one or more clients, wherein said creating the virtual relational database comprises;

dividing the data into two or more partitions; and

storing each of the two or more partitions in a respective relational database; and

subsequent to said creating;

monitoring accesses to at least one of the partitions of the data stored in the virtual relational database;

determining that the data stored in the virtual relational database should be re-partitioned, said determining that the data stored in the virtual relational database should be re-partitioned is based, at least in part, on said monitoring; and

in response to determining that the data stored in the virtual relational database should be re-partitioned, automatically initiating a re-partitioning of at least a portion of the data stored in the virtual relational database.

18. The non-transitory, computer-readable storage medium of claim 17, wherein said determining that the data stored in the virtual relational database should be re-partitioned comprises one or more of:

determining that a size of a given one of the two or more partitions is larger than a pre-determined maximum partition size,

determining that there has been a change in performance for accesses directed to the virtual relational database,

determining that write accesses directed to a given one of the two or more partitions are more numerous or more frequent than write accesses to other ones of the two or more partitions,

determining that there has been a change in a parameter of a service level agreement associated with the virtual relational database, or

determining that there has been a failure of a component of a system on which the two or more partitions are hosted.

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

subsequent to said initiating a repartitioning;

creating a partition map comprising information reflecting the repartitioning;

sending an indication of the partition map to one or more components of a system on which the virtual relational database is hosted; and

receiving and servicing one or more queries directed to the virtual relational database without waiting for acknowledgement that a local partition map has been updated on the one or more components of the system to reflect the repartitioning.