Flexible partitioning of data

• US 9,235,613 B2
• Filed: 07/25/2014
• Issued: 01/12/2016
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Gorde, Nitin B., Pathak, Sumedh S., Bhatia, Manish R.
• Primary Examiner(s): Spieler, William
• Application Number:
  US14/341,045
• Publication Number:
  US 20140337392A1
• Time in Patent Office: 536 Days
• 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/2291 User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations

Abstract

Disclosed are various embodiments of a flexible application-level partitioning scheme for data storage components. A data store is accessible by one or more computing devices and includes multiple partitions. One of the partitions is identified by mapping a key value of a data item to one of the partitions according to one of multiple versions of mapping metadata. Each of the versions of mapping metadata specifies a respective list of some or all of the partitions and an approach for mapping the key value to one of the partitions. The data item is inserted into the identified partition.

Claims

1. A non-transitory computer-readable medium embodying a program executable in a computing device, the program having instructions that perform a method comprising:

identifying one of a plurality of versions of mapping metadata concurrently available to a data management application, the plurality of versions of mapping metadata specifying a respective list of at least some of a plurality of partitions of a data store and a respective approach for mapping a key value to one of the at least some of the partitions;

determining one of the plurality of partitions by mapping an attribute of a data item, as the key value, to the one of the plurality of partitions according to the respective approach for mapping the key value corresponding to the identified one of the plurality of version of mapping metadata;

inserting the data item in the one of the plurality of partitions;

storing an identifier corresponding to the one of the plurality of partitions in response to a loading of the data item from the one of the plurality of partitions;

obtaining a request to update the data item; and

updating the data item in the one of the plurality of partitions in response to the request and based at least in part on the identifier.

2. The non-transitory computer-readable medium of claim 1, wherein the respective approach for mapping a key value to one of the at least some of the partitions corresponds to a modulo operation applied to a dividend corresponding to a numeric representation of the key value of the data item and a divisor corresponding to a number of elements at least some of the partitions.

3. A system, comprising:

at least one computing device;

a data store accessible by the at least one computing device and including a plurality of partitions; and

wherein the at least one computing device is configured to implement a method, comprising;

identifying, in response to a request to perform an action with respect to the data store, one of a plurality of versions of mapping metadata concurrently available to a data management application, the plurality of versions of mapping metadata specifying a respective list of at least some of the plurality of partitions and an approach for mapping a key value to one of the at least some of the partitions; and

performing, after the identifying, the action according to the one of the plurality of versions of mapping metadata.

4. The system of claim 3, wherein the action comprises inserting a data item into the data store, and the method further comprises:

selecting one of the partitions based at least in part on an attribute of the data item corresponding to the key value and the approach for mapping the key value for the one of the plurality of versions of mapping metadata; and

inserting the data item into the one of the partitions.

5. The system of claim 3, wherein the action comprises loading a data item from the data store, and the method further comprises:

selecting one of the partitions based at least in part on an attribute of the data item corresponding to the key value and the approach for mapping the key value for the one of the plurality of versions of mapping metadata; and

loading the data item from the one of the partitions.

6. The system of claim 5, wherein selecting one of the partitions further comprises:

determining whether the one of the partitions has been queried to load the data item;

identifying, responsive to the one of the partitions having been queried, another one of the plurality of versions of mapping metadata; and

selecting the one of the partitions based at least in part on the approach for mapping the key value for the other one of the plurality of versions of mapping metadata.

7. The system of claim 3, wherein the one of the versions of mapping metadata corresponds to a most recently created one of the versions of mapping metadata.

8. The system of claim 3, wherein the request is a first request, and the method further comprises generating, in response to a second request to add a new partition to the plurality of partitions, a new version of mapping metadata, the new version of mapping metadata including the new partition in the respective list of the at least some of the plurality of partitions.

9. The system of claim 8, wherein the method further comprises:

determining a data attribute most used in queries for a type of data; and

wherein the approach for mapping the key value of the new version of mapping metadata comprises the data attribute as the key value.

10. The system of claim 8, wherein the approach for mapping the key value of the new version of mapping metadata is configured to give greater weight to the new partition than others of the plurality of partitions.

11. The system of claim 3, wherein the method further comprises deleting, in response to a removal of data from the data store, at least one of the versions of mapping metadata.

12. The system of claim 11, wherein the at least one of the versions of mapping metadata deleted is based at least in part on a plurality of time stamps associated with the plurality of versions of mapping metadata.

13. The system of claim 3, wherein the request is a first request, and the method further comprises generating a new version of mapping metadata excluding a deleted partition from the respective list of the at least some of the plurality of partitions.

14. A method, comprising:

identifying, by at least one computing device, one of a plurality of versions of mapping metadata concurrently available to a data management application, the plurality of versions of mapping metadata specifying a respective list of at least some of a plurality of partitions of a data store and an approach for mapping a key value to one of the at least some of the partitions;

determining, by the at least one computing device, one of the plurality of partitions by mapping an attribute of a data item, as the key value, to the one of the plurality of partitions according to the approach for mapping the key value; and

inserting, by the at least one computing device, the data item in the one of the plurality of partitions.

15. The method of claim 14, further comprising:

storing, in the at least one computing device, an identifier corresponding to the one of the plurality of partitions in response to a loading of the data item from the one of the plurality of partitions;

obtaining, in the at least one computing device, a request to update the data item; and

updating, in the at least one computing device, the data item in the one of the plurality of partitions in response to the request and based at least in part on the identifier.

16. The method of claim 14, wherein the key value is based at least in part on a data access history associated with the data store.

17. The method of claim 16, wherein the key value comprises a most frequently accessed data attribute according to the data access history.

18. The method of claim 14, further comprising generating, in the at least one computing device, a new version of mapping metadata for inclusion in the plurality of versions of mapping metadata in response to a request to modify a growth rate of the plurality of partitions.

19. The method of claim 14, wherein the one of the plurality of versions of mapping metadata is determined based at least in part on a respective one of a plurality of time stamps corresponding to the plurality of versions of mapping metadata.

20. The method of claim 19, wherein the one of the plurality of versions of mapping metadata is determined as a most recent one of the plurality of versions of mapping metadata.