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 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 table into split partitions and comprising: identifying, by the table master, the partition for splitting based on load distribution information tracked for the plurality of partitions on the plurality of table servers, wherein the load distribution information includes information specifying load on each of two or more portions of the partition, wherein a request sampling mechanism is used to track load distribution information within each partition; determining, by the table master, a split ratio for splitting the partition based on the loading on each of the two or more portions of the partition, wherein the split ratio represents a point in the partition in which a first portion of the partition includes a first amount of load and a second portion of the partition includes a second amount of load; querying a table server hosting the partition for key information indicating an actual location within the partition corresponding with the split ratio; receiving key information at the table master from the table server, the key information indicating the actual location within the partition corresponding with the split ratio; sending a split request from the table master to the table server, the split request indicating to split the partition based on the key information; splitting (518, 520, 522) the partition at a location corresponding with the key information to create the split partitions; notifying the table master of split completion; and updating a partition map based on the partition being split into the split partitions, the partition map storing mappings between the plurality of partitions and the plurality of table servers serving the plurality of partitions. identifying, by the table master, the partition for splitting based on load distribution information tracked for the plurality of partitions on the plurality of table servers, wherein the load distribution information includes information specifying load on each of two or more portions of the partition, wherein a request sampling mechanism is used to track load distribution information within each partition; determining, by the table master, a split ratio for splitting the partition based on the loading on each of the two or more portions of the partition, wherein the split ratio represents a point in the partition in which a first portion of the partition includes a first amount of load and a second portion of the partition includes a second amount of load; querying a table server hosting the partition for key information indicating an actual location within the partition corresponding with the split ratio; receiving key information at the table master from the table server, the key information indicating the actual location within the partition corresponding with the split ratio; sending a split request from the table master to the table server, the split request indicating to split the partition based on the key information; splitting (518, 520, 522) the partition at a location corresponding with the key information to create the split partitions; notifying the table master of split completion; and updating a partition map based on the partition being split into the split partitions, the partition map storing mappings between the plurality of partitions and the plurality of table servers serving the plurality of partitions.