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

Patent metadata

Field	Value
Publication number	US-9996572-B2
Application number	US-25805008-A
Country	US
Kind code	B2
Filing date	Oct 24, 2008
Priority date	Oct 24, 2008
Publication date	Jun 12, 2018
Grant date	Jun 12, 2018

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.

First claim

What is claimed is:

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

Assignees

• Calder Bradley Gene
• Wang Ju
• Skjolsvold Arild E
• Srivastav Shashwat
• Nilakantan Niranjan
• Bhardwaj Deepali
• Microsoft Technology Licensing Llc

Inventors

• Calder Bradley Gene
• Wang Ju
• Skjolsvold Arild E
• Srivastav Shashwat
• Nilakantan Niranjan
• Bhardwaj Deepali

Classifications

• G06F3/067

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

• G06F3/0605 Primary

  by facilitating the interaction with a user or administrator · CPC title

• G06F15/161

  Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning (casings, cabinets, racks or drawers for data centers H05K5/00) · CPC title

• G06F3/0644

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

• G06F15/16

  Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs {(coordinating program control therefor G06F9/52; in regulating and control system G05B)} · CPC title