System and method for performing live partitioning in a data store

Patent metadata

Field	Value
Publication number	US-10712950-B2
Application number	US-201514733851-A
Country	US
Kind code	B2
Filing date	Jun 8, 2015
Priority date	Jun 30, 2011
Publication date	Jul 14, 2020
Grant date	Jul 14, 2020

Abstract

A system that implements a scalable data storage service may maintain tables in a data store on behalf of storage service clients. The service may maintain table data in multiple replicas of partitions that are stored on respective computing nodes in the system. In response to detecting an anomaly in the system, detecting a change in data volume on a partition or service request traffic directed to a partition, or receiving a service request from a client to split a partition, the data storage service may create additional copies of a partition replica using a physical copy mechanism. The data storage service may issue a split command defined in an API for the data store to divide the original and additional replicas into multiple replica groups, and to configure each replica group to maintain a respective portion of the table data that was stored in the partition before the split.

First claim

What is claimed is:

1. A system, comprising:
a plurality of computing nodes, each comprising at least one processor and memory, wherein the plurality of computing nodes is configured to implement a data storage service;
wherein the data storage service provides a service interface through which service requests are received;
wherein the data storage service maintains a plurality of tables in a data store on behalf of one or more storage service clients, and wherein maintaining the plurality of tables comprises maintaining a plurality of partitions of table data, wherein each replica of two or more replicas of each partition of the table data is stored on a different respective computing node in the data store;
wherein in response to receiving a request to split a particular partition of the plurality of partitions, the data storage service is configured to:
create two or more new replicas of the particular partition in addition to the two or more replicas of the particular partition that already exist on different respective computing nodes, wherein each new replica and each existing replica is a replica of the table data that was stored in the particular partition, wherein each of the two or more new replicas and the two or more replicas of the particular partition is stored on a different respective computing node in the data store;
establish two or more replica groups, wherein a first replica group of the two or more replica groups includes at least two replicas of the particular partition selected from the two or more replicas of the particular partition and the two or more new replicas of the particular partition, and wherein a second replica group of the two or more replica groups includes at least two replicas of the particular partition selected from the two or more replicas of the particular partition and the two or more new replicas, and wherein each replica of the first replica group is distinct from each replica of the second replica group; and
configure each of the two or more replica groups as responsible for maintaining different respective portions of the table data of the particular partition as different, respective, new partitions split from the particular partition;

wherein subsequent to said configuration of the two or more replica groups as new partitions split from the particular partition, the data storage service is configured to:
direct service requests targeting items in the different respective portions of the table data that was stored in the particular partition, to respective ones of the two or more replica groups responsible for the new partitions of the table data split from the particular partition; and
reclaim storage in one of the different respective computing nodes storing an individual one of the two or more new replicas of the particular partition, wherein the individual one of the two or more new replicas is now part of an individual one of the two or more replica groups for an individual one of the new partitions, and wherein the storage that is reclaimed stores table data from the particular partition for which the individual one of the new partitions is not responsible and for which another one of the new partitions is responsible, wherein the reclaimed storage is available for storage of other data.

2. The system of claim 1 , wherein during said creating the two or more new replicas of the particular partition, the two or more replicas of the particular partition are configured to continue to service requests directed to the table data stored in the particular partition.

3. The system of claim 1 , wherein said creating comprises:
copying table data from physical storage locations in which contents of the particular partition are stored; and
writing the copied table data to corresponding locations in physical storage allocated to the two or more new replicas of the particular partition.

4. The system of claim 1 , wherein to establish the two or more replica groups the data storage service is configured to call an operation defined in an application programming interface of the data storage service.

5. The system of claim 1 , wherein the data storage service is further configured to elect a master for each of the two or more replica groups.

6. A method, comprising:
performing by a computer in response to receiving a request to split a particular partition maintained in a data store, wherein the data store maintains a plurality of tables, and wherein maintaining the plurality of tables comprises maintaining one or more replicas of table data stored in each of one or more partitions, including the particular partition, on respective computing nodes in the data store:
creating one or more new replicas of the particular partition in addition to the one or more replicas of the particular partition that already exist on different respective computing nodes, wherein each new replica and each existing replica is a replica of the table data stored in the particular partition, wherein each of the one or more new replicas and the one or more replicas of the particular partition is stored on a different respective computing node in the data store;
establishing two or more replica groups, wherein a first replica group of the two or more replica groups includes at least one replica of the particular partition selected from the one or more replicas of the particular partition and the one or more new replicas of the particular partition, and wherein a second replica group of the two or more replica groups includes at least one replica of the particular partition selected from the one or more replicas and the one or more new replicas, and wherein each replica of the first replica group is distinct from each replica of the second replica group;
configuring the each of the two or more replica groups to be responsible for maintaining different respective portions of the table data of the particular partition as different, respective new partitions split from the particular partition;
directing, subsequent to said configuring the two or more replica groups as new partitions split from the particular partition, requests targeting items in the different respective portions of the table data that was stored in the particular partition, to respective ones of the two or more replica groups responsible for the new partitions of the table data split from the particular partition; and
reclaiming storage in one of the different respective computing nodes storing an individual one of the one or more new replicas of the particular partition, wherein the individual one of the one or more new replicas is now part of an individual one of the two or more replica groups for an individual one of the new partitions, and wherein the storage that is reclaimed stores table data from the particular partition for which the individual one of the new partitions is not responsible and for which another one of the new partitions is responsible, wherein the reclaimed storage is available for storage of other data.

7. The method of claim 6 , wherein said creating comprises:
copying table data from physical storage locations in which contents of the particular partition are stored; and
writing the copied table data to corresponding locations in physical storage allocated to the one or more new replicas of the particular partition replica.

8. The method of claim 7 , wherein said creating further comprises:
logging requests to modify table data stored in the particular partition that are received during said copying; and
during said copying, applying one or more logged requests to the one or more replicas of the particular partition at pre-determined checkpoint intervals.

9. The method of claim 7 , wherein said creating further c

Assignees

• Amazon Tech Inc

Inventors

• Stefani Stefano
• Rath Timothy Andrew
• Buragahain Chiranjeeb
• Leshinsky Yan Valerie
• Lutz David Alan
• Kulesza Jakub
• Xiao Wei
• Vasanth Jai

Classifications

• G06F16/278 Primary

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• G06F3/065

  Replication mechanisms · CPC title

• G06F3/0644

  Management of space entities, e.g. partitions, extents, pools · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title