# US 8,150,870 B1 · Scalable partitioning in a multilayered data service framework

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,150,870 B1
- Document ID: US8150870B1
- Status: Granted
- Kind: B1
- Application number: 11/615,841
- Filed: 2006-12-22
- Granted: 2012-04-03
- Earliest claimed: 2006-12-22
- Assignees: Amazon Technologies, Inc.
- Inventors: Nicholas K. Peddy; Chelsea C. Krueger; Michael J. McCann; Suguna Subramaniam; W. Cary Hall; Sasan Dashtinezhad; Guy Bialostocki
- Web page: https://patentgrep.com/patent/US8150870B1

## CPC

- G06F 16/487: using geographical or spatial information, e.g. location
- G06F 16/119: {Details of migration of file systems (migration mechanisms in storage systems G06F3/0647)}
- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- Y10S 707/968: Partitioning
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A method and system is provided for maintaining customer data in a data store system utilizing a scalable partitioning framework. More specifically, the data store of a customer service system is partitioned (divided) into multiple partitions by a partitionable key of customer data so that each partition owns a subset of the customer data. By maintaining several partitions that store a subset of the customer data exclusive to each other, blackout or brownout problems can be local to one partition and, thus, the availability for the entire system will be increased. Moreover, a set of partitionable keys, a minimal unit to be moved between partitions, is grouped and associated with a partition. By eliminating direct dependencies between the partitions and the partitionable keys, the system can have great flexibility with regard to migrating customer data between partitions and adding a new partition.

## Claims

### Claim 1

A computer-implemented method for accessing information about a customer stored in a plurality of data stores, the computer-implemented method comprising:
under control of instructions that are executed by one or more computing devices:
receiving, at a first data store of the plurality of data stores, a request to access information about the customer,
wherein the information about the customer is stored in one of the plurality of data stores,
wherein each of the plurality of data stores has a plurality of partitions,
wherein each partition of the plurality of partitions includes a plurality of buckets associated therewith,
wherein each bucket of the plurality of buckets contains a plurality of partitionable keys related to a subset of customers whose customer information is stored in the partition such that the bucket represents a portion of the customer information stored in the partition,
wherein each of the plurality of data stores is associated with a set of customers based, at least in part, on a geographic location associated with each of the set of customers, and
wherein each geographic location is associated with a single data store from the plurality of data stores;
identifying from the received request a partitionable key from the plurality of partitionable keys related to the subset of customers related to the customer;
identifying from the identified partitionable key the single data store from the plurality of data stores which contains the identified partitionable key, wherein the identification is based at least in part on a determined geographical location of the customer;
if the identified single data store corresponds to the first data store:
using the identified partitionable key to identify the bucket within the first data store that contains the identified partitionable key;
performing a bucket mapping using the identified bucket to determine the partition within the first data store with which the identified bucket is associated;
determining whether the portion of the customer information stored in the partition represented by the identified bucket is accessible for the received request; and
if it is determined that the portion of the customer information represented by the identified bucket is accessible for the received request:
sending to a data partition service that manages the determined partition an access request for the information about the customer; and
obtaining, from the data partition service, a result of the sent access request; and
if the identified single data store does not correspond to the first data store:
forwarding the received request to access information about the customer to the identified single data store.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the using the identified partitionable key to identify the bucket includes applying a bucket hash function to the identified partitionable key, and
wherein the applied bucket hash function returns a bucket identifier of the bucket that contains the identified partitionable key.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein the sent access request is one of a read request, a query request, an update request, or a create request.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3, further comprising:
the determining of the partition within the first data store with which the identified bucket is associated using a first lookup table based on the returned bucket identifier and the identified partitionable key,
wherein the first lookup table represents a bucket to partition mapping.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4, further comprising:
if the sent access request is corresponds to an update request, determining whether the identified bucket which contains the identified partitionable key is locked,
wherein a determination that the identified bucket which contains the identified partitionable key is locked indicates a process of migration of the customer information represented by the identified bucket.

### Claim 6 (depends on 5)

The computer-implemented method of claim 5, further comprising:
if the determination that the identified bucket which contains the identified partitionable key is locked and the determined partition is a partition from which the customer information represented by the identified bucket is migrating, denying the update request.

### Claim 7 (depends on 5)

The computer-implemented method of claim 5, further comprising:
if the determination that the identified bucket which contains the identified partitionable key is locked and the determined partition is a partition to which the customer information represented by the identified bucket is migrating, forwarding the update request to the determined partition.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, further comprising:
if the partitionable key related to the customer cannot be identified from the received request, identifying a non-partitionable key of the customer from the received request; and
obtaining the partitionable key of related to the customer from a second lookup table based on the identified non-partitionable key of the customer,
wherein the second lookup table represents a non-partitionable key-to-partitionable key mapping.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, further comprising:
if the non-partitionable key of the customer cannot be identified from the received request, broadcasting the access request to each partition of the plurality of partitions in the plurality of data stores and aggregating a result from each partition.

### Claim 10 (depends on 1)

The computer-implemented method of claim 1, wherein each partition of the plurality of partitions is managed by a separate data partition service that is configured to manage the partition.

### Claim 11

A computer system for accessing information about a customer stored in a plurality of customer data stores, wherein each customer data store from the plurality of customer data stores is associated with a distinct customer category, the computer system comprising:
at least one memory for storing a first customer data store of the plurality of customer data stores,
wherein each customer data store includes a plurality of partitions,
wherein each customer data store is associated with one or more customer categories, and
wherein each customer category from the one or more customer categories is associated with a single customer data store; and
one or more computing devices in communication with the at least one memory, wherein the one or more computing devices are configured to implement a plurality of components, including:
a customer service component associated with the first customer data store, wherein the customer service component comprises computer-executable code that, when executed by the one or more computing devices, carries out a method comprising:
receiving a service request to access information about the customer,
wherein the information about the customer is stored in one of the plurality of partitions of one of the plurality of customer data stores,
wherein each partition of the plurality of partitions has a plurality of buckets associated therewith, and
wherein each bucket from the plurality of buckets contains a plurality of partitionable keys related to a subset of customers whose customer information is stored in the partition such that each bucket represents a portion of the customer information stored in the partition; and
a partitioning service component associated with the first customer data store, wherein the partitioning service component comprises computer-executable code that, when executed by the one or more computing devices, carries out a method comprising:
processing the received service request to identify a partitionable key related to the customer;
using the identified partitionable key to identify a customer data store of the plurality of customer data stores associated with the customer based at least in part on a customer category from the one or more customer categories associated with the customer; and
if the identified customer data store corresponds to the first data store:
identifying a bucket of the first customer data store that contains the identified partitionable key;
performing a bucket mapping using the identified bucket to determine a partition of the first customer data store with which the identified bucket is associated; and
determining whether the portion of the customer information stored in the determined partition represented by the identified bucket is accessible for the received service request;
if it is determined that the portion of the customer information represented by the identified bucket is accessible for the received service request, sending, by the partitioning service component, to a data partition service configured to manage the determined partition an access request for the information about the customer; and
if the identified customer data store does not correspond to the first customer data store, forwarding the received service request to a partitioning service component associated with the identified customer data store.

### Claim 12 (depends on 11)

The computer system of claim 11, wherein the data partition service configured to manage the determined partition accesses the information about the customer in accordance with the sent access request.

### Claim 13 (depends on 12)

The computer system of claim 12, wherein the partitioning service component returns a result of the sent access request which is obtained from the determined partition.

### Claim 14 (depends on 11)

The computer system of claim 11, wherein each partition of the plurality of partitions is associated with at least one bucket that contains partitionable keys for a plurality of customers.

### Claim 15 (depends on 11)

The computer system of claim 11, wherein the plurality of components further comprises:
a global data service component, wherein the global data service component comprises computer-executable code that, when executed by the one or more computing devices, causes maintaining a plurality of mapping tables, wherein each mapping table from the plurality of mapping tables relates to a corresponding non-partitionable key and each mapping table represents a non-partitionable key-to-partitionable key mapping for the corresponding non-partitionable key.

### Claim 16 (depends on 15)

The computer system of claim 15, wherein if the partitioning service component cannot identify the partitionable key related to the customer from the received service request, the partitioning service component identifies a non-partitionable key of the customer from the received service request.

### Claim 17 (depends on 16)

The computer system of claim 16, wherein the partitioning service component obtains the partitionable key related to the customer from the global data service component based on the identified non-partitionable key of the customer.

### Claim 18 (depends on 11)

The computer system of claim 11, wherein each partition of the plurality of partitions is managed by a separate data partition service that is configured to manage the partition.

### Claim 19

A computer-implemented method for accessing information about a customer stored in a plurality of data stores, wherein each data store of the plurality of data stores includes a plurality of partitions, the computer-implemented method comprising:
under control of instructions that are executed by one or more computing devices:
receiving, at a first data store of the plurality of data stores, a request to access information about the customer,
wherein the information about the customer is stored in one of the plurality of partitions of one of the plurality of data stores,
wherein each partition of the plurality of partitions has at least one set of a plurality of sets of partitionable keys associated therewith,
wherein each set of partitionable keys from the plurality of sets of partitionable keys includes a plurality of partitionable keys related to a subset of customers whose customer information is stored in a single data store from the plurality of data stores such that a set of partitionable keys represents a portion of the customer information stored in a partition,
wherein each of the plurality of data stores is associated with one or more customer categories, and
wherein each customer category from the one or more customer categories is associated with the single data store from the plurality of data stores;
identifying from the received request a partitionable key from the plurality of partitionable keys related to the subset of customers related to the customer;
identifying from the identified partitionable key the single data store from the plurality of data stores which contains the identified partitionable key, where the identification is based at least in part on a customer category associated with the customer;
if the identified single data store corresponds to the first data store:
using the identified partitionable key to identify the set of partitionable keys within the first data store that includes the identified partitionable key;
determining, based on the identified set of partitionable keys, the partition within the first data store where the information about the customer is stored;
determining whether the information about the customer is accessible for the received request based on whether the portion of the customer information that is represented by the identified set of partitionable keys is accessible for the received request; and
if it is determined that the portion of the customer information is accessible for the received request:
sending to a data partition service that manages the determined partition an access request for the information about the customer; and
obtaining, from the data partition service, a result of the sent access request from the determined partition; and
if the identified single data store does not correspond to the first data store:
forwarding the received request to access information about the customer to the identified single data store.

### Claim 20 (depends on 19)

The computer-implemented method of claim 19, further comprising:
if the partitionable key related to the customer cannot be identified from the received request, identifying a non-partitionable key of the customer from the received request; and
obtaining the partitionable key related to the customer from a lookup table based on the identified non-partitionable key of the customer,
wherein the lookup table represents a non-partitionable key-to-partitionable key mapping.

### Claim 21 (depends on 20)

The computer-implemented method of claim 20, further comprising:
if the non-partitionable key of the customer cannot be identified from the received request, broadcasting the access request to each partition of the plurality of partitions in the plurality of data stores and aggregating a result from each partition.

### Claim 22 (depends on 19)

The computer-implemented method of claim 19, wherein each partition of the plurality of partitions is managed by a separate data partition service that is configured to manage the partition.

### Claim 23

A computer system for accessing information about a customer stored in a plurality of customer data stores, wherein each customer data store from the plurality of customer data stores is associated with one or more customer categories and wherein each customer category from the one or more customer categories is associated with a single customer data store, the computer system comprising:
at least one memory for storing a first customer data store of the plurality of customer data stores,
wherein each customer data store includes a plurality of partitions, and
wherein the first customer data store is associated with at least a first customer category from the one or more customer categories; and
one or more computing devices in communication with the at least one memory, wherein the one or more computing devices are configured to implement a plurality of components, including:
a customer service component associated with the first customer data store, wherein the customer service component comprises computer-executable code that, when executed by the one or more computing devices, carries out a method comprising:
receiving a service request to access information about the customer,
wherein the information about the customer is stored in one of one of the plurality of customer data stores,
wherein each partition of the plurality of partitions has at least one set of a plurality of sets of partitionable keys associated therewith, and
wherein each set of partitionable keys from the plurality of sets of partitionable key includes a plurality of partitionable keys related to a subset of customers whose customer information is stored in a single customer data store from the plurality of customer data stores such that each set of partitionable keys represents a portion of the customer information stored in the partition; and
a partition partitioning service component associated with the first customer data store, wherein the partitioning service component comprises computer-executable code that, when executed by the one or more computing devices, carries out a method comprising:
processing the received service request to identify a partitionable key related to the customer;
using the identified partitionable key to identify a customer data store of the plurality of customer data stores associated with the customer based at least in part on a customer category from the one or more customer categories associated with the customer; and
if the identified customer data store corresponds to the first data store:
identifying a set of partitionable keys of the first customer data store that includes the identified partitionable key;
determining, based on the identified set of partitionable keys, a partition of the first customer data store where the information about the customer is stored; and
determining whether the information about the customer is accessible for the received service request based on whether the portion of the customer information that is represented by the identified set of partitionable keys is accessible for the received service request;
if it is determined that the portion of the customer information is accessible for the received service request, sending, by the partitioning service component, to a data partition service that is configured to manage the determined partition an access request for the information about the customer; and
if the identified customer data store does not correspond to the first customer data store, forwarding the received service request to a partitioning service component associated with the identified customer data store.

### Claim 24 (depends on 23)

The computer system of claim 23, wherein the data partition service accesses the information about the customer data based on the sent access request.

### Claim 25 (depends on 24)

The computer system of claim 24, wherein the partitioning service component returns a result of the sent access request which is obtained from the determined partition.

### Claim 26 (depends on 23)

The computer system of claim 23, wherein each partition of the plurality of partitions is managed by a separate data partition service that is configured to manage the partition.