Partition management in a partitioned, scalable, and available structured storage

• US 9,996,572 B2
• Filed: 10/24/2008
• Issued: 06/12/2018
• Est. Priority Date: 10/24/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Calder, Bradley Gene, Wang, Ju, Skjolsvold, Arild E., Srivastav, Shashwat, Nilakantan, Niranjan, Bhardwaj, Deepali
• Primary Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US12/258,050
• Publication Number:
  US 20100106934A1
• Time in Patent Office: 3,518 Days
• Field of Search: 707687, 707705, 707790, 707702, 707720
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Partition management for a scalable, structured storage system is provided. The storage system provides storage represented by one or more tables, each of which includes rows that represent data entities. A table is partitioned into a number of partitions, each partition including a contiguous range of rows. The partitions are served by table servers and managed by a table master. Load distribution information for the table servers and partitions is tracked, and the table master determines to split and/or merge partitions based on the load distribution information.

Claims

1. A method implemented by one or more computing devices within a structured storage system in which structured storage is represented by one or more tables, each table including a plurality of rows, each row representing a data entity stored by the structured storage system and including one or more keys for identifying the row, the plurality of rows being divided among a plurality of partitions, each partition including a range of rows from the plurality of rows within the table, wherein the plurality of partitions are stored on a plurality of table servers, and wherein a table master controls partition assignment to the plurality of table servers, the method for splitting a partition assigned to a table server of the plurality of table servers into child partitions and comprising:

identifying the partition for the splitting of the partition based on load information for the partition, wherein the load information includes information specifying an amount of load tracked on the partition from actual read and write requests made on each of two or more portions of the partition;

determining, by the table master, a split ratio for the splitting of the partition based on a distribution of the amount of the load tracked on the partition such that the split ratio specifies a load distribution that represents a point in the partition in which a first portion of the partition includes a first portion of the amount of load tracked across the partition and a second portion of the partition includes a second portion of the amount of load tracked across the partition;

providing a request to the table server for key information indicating an actual location within the partition for the splitting that corresponds to the load distribution specified by the split ratio, the request includes the split ratio;

receiving the key information at the table master from the table server, the key information indicating the actual location within the partition;

sending a split request from the table master to the table server, the split request indicating to the table server to perform the splitting of the partition based on the key information;

performing the splitting of the partition at a location corresponding to the actual location to create the child partitions;

notifying the table master that the splitting has completed; and

updating a partition map based on the partition being split into the child partitions, the partition map storing mappings between the plurality of partitions and the plurality of table servers serving the plurality of partitions.

2. The method of claim 1, wherein the method further comprises constructing, at the table master, a stream for at least one of the child partitions.

3. The method of claim 1, wherein the splitting of the partition comprises:

ceasing to serve the partition from the table server;

building the child partitions from the partition; and

loading and serving the child partitions from the table server.

4. The method of claim 3, wherein ceasing to serve the partition comprises making a checkpoint of the partition, thereby reducing the amount of logs to be replayed during partition reload.

5. The method of claim 4, wherein making the checkpoint of the partition comprises efficient truncation of log streams during checkpoint by atomically:

creating a new log stream, hard-linking extents after the checkpoint from an old log stream to the new log stream, deleting the old log stream, and renaming the new log stream to a name of the old log stream.

6. The method of claim 3, wherein building the child partitions from the partition comprises efficient construction of streams of the child partitions by atomically hard-linking extents from streams of the partition without expensive data copy.

7. The method of claim 1, wherein the method further comprises assigning at least one of the child partitions to a second table server.

8. The method of claim 7, wherein the method further comprises updating the partition map to indicate that the at least one of the child partitions is located at the second table server.

9. The method of claim 1, wherein the method further comprises adjusting boundaries of the two or more portions of the partition based on the load information by merging or splitting at least a subset of the two or more portions of the partition for load monitoring purposes.

10. One or more computer-storage media storing computer-usable instructions for performing a method for managing a structured storage system represented by one or more tables, each table including a plurality of rows, each row representing a data entity stored by the structured storage system and including one or more keys for identifying the row, the plurality of rows being divided among a plurality of partitions, each partition including a range of rows from the plurality of rows within the table, wherein the plurality of partitions are stored on a plurality of table servers, and wherein a table master controls partition assignment to the plurality of table servers, the method for merging at least two partitions of the plurality of partitions of the table into a merged partition and comprising:

tracking load information for the plurality of partitions on the plurality of table servers, wherein the load information indicates an amount of load tracked across the partition for each of the plurality of partitions from actual traffic read and write access requests made on the partitions on the table servers;

determining, by the table master, the at least two partitions to merge into the merged partition based on a distribution of the amount of load tracked across the partition for each of the at least two partitions compared to the amount of load for others of the plurality of partitions; and

performing the merging based on the determining of the at least two partitions, the merging comprising;

creating, by the table master, a metadata stream for the merged partition;

offloading the at least two partitions from at least one table server serving the at least two partitions based on the determining by the table master;

assigning, by the table master, the merged partition to a selected table server from the plurality of table servers; and

loading and serving the merged partition at the selected table server.

11. The one or more computer-storage media of claim 10, wherein the at least two partitions are stored on the same table server.

12. The one or more computer-storage media of claim 10, wherein the selected table server comprises a table server on which at least one of the at least two partitions resided before being merged into the merged partition.

13. The one or more computer-storage media of claim 10, wherein the method further comprises updating a partition map based on the at least two partitions being merged into the merged partition, the partition map storing mappings between the plurality of partitions and the plurality of table servers serving the plurality of partitions.

14. The one or more computer-storage media of claim 10, wherein the method further comprises sending a prepare-merge message from the table master to the at least one table server serving the at least two partitions, wherein the prepare-merge message causes the at least one table server to compact the at least two partitions prior to merging in order to reduce load time for the merged partition.

15. One or more computer-storage media storing computer-usable instructions for performing a method for managing a structured storage system represented by one or more tables, each table including a plurality of rows, each row representing a data entity stored by the structured storage system and including one or more keys

for identifying the row, the plurality of rows being divided among a plurality of partitions, each partition including a contiguous range of rows from the plurality of rows within the table, wherein the plurality of partitions are stored on a plurality of table servers, and wherein a table master controls partition assignment to the plurality of table servers, the method for splitting a partition of the plurality of partitions of the table into at least two child partitions and comprising:

tracking load information for the plurality of partitions on the plurality of table servers, wherein the load information comprises an amount of load tracked on each of the plurality of partitions from actual traffic read and write access requests made on the plurality of partitions;

determining by the table master, to perform the splitting of the partition by analyzing the amount of load tracked on the partition from the load information, wherein the load information for the partition identifies different loads on different portions of the partition;

determining, at the table master, a split ratio for the splitting of the partition, wherein the split ratio is determined based on a distribution of the amount of load tracked across the partition such that the split ratio specifies a load distribution that represents a point in the partition in which a first portion of the partition includes a first portion of the amount of load tracked across the partition and a second portion of the partition includes a second portion of the amount of load tracked across the partition;

sending a request from the table master to the table server, the request being for key information identifying an actual location in the partition for the splitting that corresponds to the load distribution specified by the split ratio, the split ratio being included in the request;

determining based on the split ratio specified in the request, by the table server, the actual location in the partition for the splitting by attempting to match the load distribution specified by the split ratio;

communicating the key information from the table server to the table master for the splitting; and

constructing, at the table master, a metadata stream for each of the child partitions;

sending a split request from the table master to the table server, the split request indicating to the table server to perform the splitting of the partition based on the key information;

performing the splitting in response to the table server receiving the split request, the splitting comprising;

building, at the table server, the child partitions from the partition;

ceasing to serve the partition at the table server; and

loading and serving the child partitions at the table server;

sending a split completion notification from the table server to the table master that indicates completion of the splitting; and

updating a partition map based on the partition being split into the child partitions by the splitting, the partition map storing mappings between the plurality of partitions and the plurality of table servers serving the plurality of partitions.

16. The one or more computer-storage media of claim 15, wherein the method further comprises assigning at least one of the child partitions to a second table server.

17. The one or more computer-storage media of claim 16, wherein the method further comprises updating the partition map to indicate that the at least one of the child partitions is located at the second table server.

18. The method of claim 15, wherein ceasing to serve the partition comprises making a checkpoint of the partition, thereby reducing the amount of logs to be replayed during partition reload.

19. The method of claim 18, wherein making the checkpoint of the partition comprises efficient truncation of log streams during checkpoint by atomically:

creating a new log stream, hard-linking extents after the checkpoint from an old log stream to the new log stream, deleting the old log stream, and renaming the new log stream to a name of the old log stream.

20. The method of claim 15, wherein building the child partitions from the partition comprises efficient construction of streams of the child partitions by atomically hard-linking extents from streams of the partition without expensive data copy.