Flexible partitioning of data

• US 8,793,250 B1
• Filed: 12/17/2010
• Issued: 07/29/2014
• Est. Priority Date: 12/17/2010
• Status: Expired due to Fees

• 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:
  US12/971,285
• Time in Patent Office: 1,320 Days
• Field of Search: 707/737
• US Class Current: 707/737
• 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 comprising:

code that generates a first version of mapping metadata that includes a first list of partitions of a data store and an approach for mapping key values of data items to one of the first list of partitions;

code that generates a second version of mapping metadata that includes a second list of partitions of the data store and an approach for mapping key values of data items to one of the second list of partitions, the second list of partitions differing from the first list of partitions and being generated after the first list of partitions;

code that identifies a key attribute for a type of data item according to a data access history associated with the type of data item;

code that determines a first partition of the data store by mapping a value of the key attribute of a data item of the type of data item according to the approach of the first version of mapping metadata;

code that determines a second partition of the data store by mapping the value according to the approach of the second version of mapping metadata; and

code that inserts another data item into a partition of the data store that is identified according to the approach for mapping that is included in the second version of mapping metadata.

2. The non-transitory computer-readable medium of claim 1, wherein the approach for mapping key values of data items to one of the first list of partitions corresponds to a modulo operation applied to a dividend corresponding to a numeric representation of a key value and a first divisor corresponding to a number of elements in the first list of partitions, and the approach for mapping key values of data items to one of the second list of partitions corresponds to the modulo operation applied to the dividend and a second divisor corresponding to a number of elements in the second list of 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

a data store management application executable in the at least one computing device, the data store management application comprising;

logic that identifies one of the partitions by mapping a key value of a data item to the one of the partitions according to one of a plurality of versions of mapping metadata, each of the versions of mapping metadata specifying a respective list of at least some of the partitions and an approach for mapping the key value to one of the at least some of the partitions, the versions of mapping metadata being concurrently available to the data store management application; and

logic that inserts the data item into the one of the partitions identified by the logic that identifies.

4. 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.

5. The system of claim 3, wherein the data item is an instance of a type of data item, and the data store management application further comprises:

logic that identifies a key attribute from a plurality of attributes of the type of data item based at least in part on a data access history associated with the type of data item; and

logic that determines the key value of the data item by determining a value of the key attribute for the data item.

6. The system of claim 3, wherein the approach for mapping the key value=corresponds to a modulo operation applied to a dividend corresponding to a numeric representation of the key value and a divisor corresponding to a number of elements in the respective list.

7. The system of claim 6, wherein the respective list includes at least one duplicated element.

8. The system of claim 3, wherein the data store management application further comprises:

logic that obtains a request to load the data item from the data store; and

logic that attempts to load the data item from a first partition that is identified by the logic that identifies in response to the request to load the data item, wherein the one of the versions of the mapping metadata corresponds to a first one of the versions of the mapping metadata, the first partition being one of the partitions.

9. The system of claim 8, wherein the data store management application further comprises:

logic that associates an identifier of the first partition with the data item when the data item is loaded from the first partition;

logic obtains a request to update the data item; and

logic that initiates an update of the data item in the first partition according to the identifier of the first partition that is associated with the data item.

10. The system of claim 8, wherein the data store management application further comprises:

logic that attempts to load the data item from a second partition that is identified by the logic that identifies when the data item cannot be obtained from the first partition, wherein the one of the versions of the mapping metadata corresponds to a second one of the versions of the mapping metadata, the second partition being one of the partitions.

11. The system of claim 3, wherein the data store management application further comprises:

logic that adds at least one other partition to the data store; and

logic that generates another one of the versions of mapping metadata, wherein the at least some of the partitions includes the at least one other partition.

12. The system of claim 3, wherein the data store management application further comprises:

logic that obtains a request to remove at least one of the partitions; and

logic that generates another one of the versions of mapping metadata, wherein the at least some of the partitions excludes the at least one of the partitions that is requested to be removed.

13. A method, comprising the steps of:

generating, in at least one computing device, a first version of mapping metadata that includes a first list of partitions of a data store and an approach for mapping data items to one of the first list of partitions;

generating, in the at least one computing device, a second version of mapping metadata that includes a second list of partitions of the data store and an approach for mapping data items to one of the second list of partitions, the second list of partitions differing from the first list of partitions, the first and second versions of mapping metadata existing concurrently;

determining, in the at least one computing device, a first partition of the data store by mapping a data item according to the approach of the first version of mapping metadata; and

determining, in the at least one computing device, a second partition of the data store by mapping the data item according to the approach of the second version of mapping metadata.

14. The method of claim 13, further comprising the steps of:

loading, in the at least one computing device, the data item from the first partition when the data item is stored in the first partition; and

loading, in the at least one computing device, the data item from the second partition when the data item is stored in the second partition.

15. The method of claim 14, further comprising the steps of:

storing, in the at least one computing device, an identifier corresponding to the first partition when the data item is loaded from the first partition;

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 first partition in response to the request and based at least in part on the identifier.

16. The method of claim 13, further comprising the step of:

obtaining, in the at least one computing device, a request to remove at least one partition of the data store; and

wherein the second version of the mapping metadata is generated in response to obtaining the request to remove the at least one partition, the first list of partitions includes the at least one partition, and the second list of partitions excludes the at least one partition.

17. The method of claim 13, further comprising the step of:

obtaining, in the at least one computing device, a request to add at least one partition to the data store; and

wherein the second version of the mapping metadata is generated in response to obtaining the request to add the at least one partition, the first list of partitions excludes the at least one partition, and the second list of partitions includes the at least one partition.

18. The method of claim 13, further comprising the steps of:

obtaining, in the at least one computing device, a request to insert another data item into the data store;

identifying, in the at least one computing device, an available partition of the data store into which the data item is to be inserted by mapping the another data item according to the approach of the second version of mapping metadata; and

wherein the second version of mapping metadata is generated after the first version of mapping metadata.

19. The method of claim 13, further comprising the step of:

obtaining, in the at least one computing device, a request to increase a quantity of data items mapped to a selected partition of the data store; and

wherein the second version of mapping metadata is generated in response to obtaining the request, the first list of partitions includes a first number of elements corresponding to the selected partition, the second list of partitions includes a second number of elements corresponding to the selected partition, and the second number is greater than the first number.

20. The method of claim 13, further comprising the step of:

obtaining, in the at least one computing device, a request to decrease a quantity of data items mapped to a selected partition of the data store; and

wherein the second version of mapping metadata is generated in response to obtaining the request, the first list of partitions includes a first number of elements corresponding to the selected partition, the second list of partitions includes a second number of elements corresponding to the selected partition, and the first number is greater than the second number.

21. The method of claim 13, further comprising the step of:

obtaining, in the at least one computing device, a request to modify a growth rate of a selected partition of the data store; and

wherein the second version of mapping metadata is generated in response to obtaining the request, the first list of partitions includes a first number of elements corresponding to the selected partition, the second list of partitions includes a second number of elements corresponding to the selected partition, and the second number is different from the first number.

22. The method of claim 13, wherein the approach for mapping data items to the one of the first list of partitions corresponds to a modulo operation applied to a dividend corresponding to a numeric representation of a key value of a specified data item and a divisor corresponding to a number of elements in the first list of partitions.