Storing and moving data in a distributed storage system

1. A computer-implemented method for moving data between storage groups in a distributed storage system having a plurality of zones at distinct geographic locations, performed on a server having at least one processor and a non-transitory computer readable storage medium storing one or more programs configured for execution by the one or more processors to perform the method, comprising:

storing data for a plurality of directories in the distributed storage system, wherein data for each directory is subdivided into one or more splits, each split is assigned to a respective storage group, and replicas of each storage group are physically stored as tablets in a plurality of zones according to a respective replication policy;

maintaining a data structure including information relating to storage groups in the distributed storage system, each respective entry in the data structure for a respective storage group including placement metrics for the respective storage group, including a placement metric that measures a current amount of storage space being used by the respective storage group;

computing a current total group usage as a sum of the placement metrics for each of the storage groups;

computing a global storage group limit as a function of a total number of storage groups in the distributed storage system, a group storage limit, and a predetermined factor;

creating one or more new storage groups when the current total group usage exceeds the global storage group limit;

receiving, from a computer system, a request to move a first split from a first storage group to a new storage group in the distributed storage system;

using the data structure to identify a second storage group whose placement metrics satisfy a selection criterion;

creating a second storage group container in the second storage group to receive the first split from the first storage group;

copying data for the first split from tablets corresponding to a first storage group container in the first storage group to tablets corresponding to the second storage group container in the second storage group; and

executing a transaction to perform the following operations:

dereferencing the first storage group container in the first storage group;

in an index in the distributed storage system, dissociating a first identifier for the first storage group container from the first split; and

in the index in the distributed storage system associating a second identifier for the second storage group container with the first split.

2. The computer-implemented method of claim 1 , wherein using the data structure to identify a second storage group whose placement metrics satisfy the selection criterion includes:

calculating group placement scores for the storage groups in the distributed storage system based on the placement metrics for the storage groups; and

determining a storage group in the distributed storage system whose group placement score satisfies the selection criterion;

wherein calculating a respective group placement score for a respective storage group includes:

when the current amount of storage space being used by the respective storage group to store data is greater than the group storage limit, calculating the respective group placement score as a predetermined low score; and

when the current amount of storage space being used by the respective storage group to store data is less than or equal to the group storage limit, calculating the respective group placement score as a function of the current amount of storage space being used by the respective storage group to store data, wherein the function biases selection of storage groups that have more available storage space.

3. The computer-implemented method of claim 1 , wherein a number of new storage groups that are created is a function of the current amount of storage space being used by all storage groups in the distributed storage system to store data, a target group size, and a total number of storage groups in the distributed storage system.

4. A system to move data between storage groups in a distributed storage system having a plurality of zones at distinct geographic locations, comprising:

one or more processors;

a non-transitory computer readable storage medium; and

one or more programs stored in the non-transitory computer readable storage medium and executable by the one or more processors;

circuitry for storing data for a plurality of directories in the distributed storage system, wherein data for each directory is subdivided into one or more splits, each split is assigned to a respective storage group, and replicas of each storage group are physically stored as tablets in a plurality of zones according to a respective replication policy;

a data structure stored in the non-transitory computer readable storage medium, wherein the data structure includes information relating to storage groups in the distributed storage system and each respective entry in the data structure for a respective storage group includes placement metrics for the respective storage group, including a placement metric that measures a current amount of storage space being used by the respective storage group;

circuitry for computing a current total group usage as a sum of the placement metrics for each of the storage groups;

circuitry for computing a global storage group limit as a function of a total number of storage groups in the distributed storage system, a group storage limit, and a predetermined factor;

circuitry for creating one or more new storage groups when the current total group usage exceeds the global storage group limit;

circuitry for receiving, from a computer system, a request to move a first split from a first storage group to a new storage group in the distributed storage system;

circuitry for using the data structure to identify a second storage group whose placement metrics satisfy a selection criterion;

circuitry for creating a second storage group container in the second storage group to receive the data from the first storage group;

circuitry for copying data for the first split from tablets corresponding to a first storage group container in the first storage group to tablets corresponding to the second storage group container in the second storage group; and

circuitry for executing a transaction including the following instructions:

dereference the first storage group container in the first storage group;

in an index in the distributed storage system, dissociate a first identifier for the first storage group container from the first split; and

in the index in the distributed storage system, associate a second identifier for the second storage group container with the first split.

5. The system of claim 4 , wherein using the data structure to identify a second storage group whose placement metrics satisfy the selection criterion includes:

calculating group placement scores for the storage groups in the distributed storage system based on the placement metrics for the storage groups; and

determining a storage group in the distributed storage system whose group placement score satisfies the selection criterion;

wherein calculating a respective group placement score for a respective storage group includes:

when the current amount of storage space being used by the respective storage group to store data is greater than the group storage limit, calculating the respective group placement score as a predetermined low score; and

when the current amount of storage space being used by the respective storage group to store data is less than or equal to the group storage limit, calculating the respective group placement score as a function of the current amount of storage space being used by the respective storage group to store data, wherein the function biases selection of storage groups that have more available storage space.

6. The system of claim 4 , wherein a number of new storage groups that are created is a function of the current amount of storage space being used by all storage groups in the distributed storage system to store data, a target group size, and a total number of storage groups in the distributed storage system.

7. A non-transitory computer readable storage medium storing-one or more programs configured for execution by one or more processors of a computer system, the one or more programs comprising instructions for:

storing data for a plurality of directories in a distributed storage system having a plurality of zones at distinct geographic locations, wherein data for each directory is subdivided into one or more splits, each split is assigned to a respective storage group, and replicas of each storage group are physically stored as tablets in a plurality of zones according to a respective replication policy;

maintaining a data structure including information relating to storage groups in the distributed storage system, each respective entry in the data structure for a respective storage group including placement metrics for the respective storage group, including a placement metric that measures a current amount of storage space being used by the respective storage group;

computing a current total group usage as a sum of the placement metrics for each of the storage groups;

computing a global storage group limit as a function of a total number of storage groups in the distributed storage system, a group storage limit, and a predetermined factor;

creating one or more new storage groups when the current total group usage exceeds the global storage group limit;

receiving, from a computer system, a request to move a first split from a first storage group to a new storage group in the distributed storage system;

using the data structure to identify a second storage group whose placement metrics satisfy a selection criterion;

creating a second storage group container in the second storage group to receive the first split from the first storage group;

copying data for the first split from tablets corresponding to a first storage group container in the first storage group to tablets corresponding to the second storage group container in the second storage group; and

executing a transaction to perform the following operations:

dereferencing the first storage group container in the first storage group;

in an index in the distributed storage system, dissociating a first identifier for the first storage group container from the first split; and

in the index in the distributed storage system associating a second identifier for the second storage group container with the first split.

8. The computer readable storage medium of claim 7 , wherein using the data structure to identify a second storage group whose placement metrics satisfy the selection criterion includes:

calculating group placement scores for the storage groups in the distributed storage system based on the placement metrics for the storage groups; and

determining a storage group in the distributed storage system whose group placement score satisfies the selection criterion;

wherein calculating a respective group placement score for a respective storage group includes:

when the current amount of storage space being used by the respective storage group to store data is greater than the group storage limit, calculating the respective group placement score as a predetermined low score; and

when the current amount of storage space being used by the respective storage group to store data is less than or equal to the group storage limit, calculating the respective group placement score as a function of the current amount of storage space being used by the respective storage group to store data, wherein the function biases selection of storage groups that have more available storage space.

9. The computer readable storage medium of claim 7 , wherein a number of new storage groups that are created is a function of the current amount of storage space being used by all storage groups in the distributed storage system to store data, a target group size, and a total number of storage groups in the distributed storage system.