×

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
First Claim
Patent Images

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.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×