Systems and methods for balancing storage resources in a distributed database

1. A computer-implemented method of balancing data objects stored on a plurality of storage resources, the method comprising:

creating, by a computer processor, a set of pods, wherein each pod in the set of pods includes a plurality of nodes, at least two of which reside on different storage racks, wherein creating each pod in the set of pods comprises:

assigning, to the pod, nodes from a set of nodes residing on a set of storage racks until the pod is assigned a specified amount of nodes,

wherein the pod has assigned to it, a set of shards each shard in the set of shards comprising a set of replicas of a data object, wherein all replicas of a data object are stored on a single pod of the set of pods;

after creating the set of pods, distributing at least a portion of the set of shards assigned to a first subset of pods in the set of pods among a second subset of pods in the set of pods according to an available processing capacity of the first subset and the second subset of pods in the set of pods; and

after distributing at least the portion of the set of shards among the second subset of pods, distributing within a pod the set of replicas of the data object for a shard to ensure that each replica of the set of replicas for the shard is assigned to a node residing on a different storage rack of storage racks associated with the pod.

2. The computer-implemented method of claim 1 , further comprising:

calculating the specified amount of nodes for each pod of the set of pods based on: an incoming network bandwidth, an outgoing network bandwidth, an amount of the set of replicas of each of the set of shards, an annualized failure rate, and a storage capacity of each of the set of nodes.

3. The computer-implemented method of claim 1 , wherein assigning, to the pod, nodes from the set of nodes residing on the set of storage racks comprises:

establishing that the pod is assigned nodes to maximize representation of the set of storage racks.

4. The computer-implemented method of claim 3 , wherein assigning, to the pod, nodes from the set of nodes residing on the set of storage racks comprises:

ensuring that an amount of the set of storage racks is less than or equal to the specified amount of nodes for each pod of the set of pods.

5. The computer-implemented method of claim 3 , wherein assigning, to the pod, nodes from the set of nodes residing on the set of storage racks comprises:

ensuring that an amount of the set of storage racks is greater than an amount of the set of replicas for each of the set of shards.

6. The computer-implemented method of claim 4 , wherein distributing the set of replicas of the data object comprises:

ensuring that the amount of the set of storage racks is larger than an amount of the set of nodes that share a replica of the set of replicas.

7. The computer-implemented method of claim 1 , further comprising:

creating, by the processor, an additional set of pods from the set of nodes residing across on the set of storage racks.

8. The computer-implemented method of claim 1 , further comprising:

sorting the set of storage racks according to an amount of nodes residing on the set of storage racks;

and wherein creating each pod of the set of pods comprises:

assigning, to the pod, nodes from the set of nodes residing on the set of storage racks that were sorted.

9. The computer-implemented method of claim 1 , further comprising:

determining that a first pod of the set of pods needs repair;

identifying a first node of the set of nodes that ensures that a node from each of the set of storage racks is assigned to the first pod; and

assigning the first node to the first pod.

10. The computer-implemented method of claim 9 , wherein determining that the first pod of the set of pods needs repair comprises:

determining that at least two pods need repair, the at least two pods including the first pod; and

selecting to repair the first pod based on the first pod having a least specified amount of nodes assigned thereto.

11. A system for balancing data objects stored on a plurality of storage resources, comprising:

a computer processor;

a set of storage racks;

a set of nodes residing on the set of storage racks;

a pod creation module executed by the computer processor and configured to:

create a set of pods, wherein each pod in the set of pods includes a plurality of nodes, at least two of which reside on different storage racks, wherein to create each pod in the set of pods, the pod creation module is configured to:

assign, to the pod, nodes from the set of nodes residing on the set of storage racks until the pod is assigned a specified amount of nodes,

wherein the pod has assigned to it, a set of shards, each shard in the set of shards comprising a set of replicas of a data object, wherein all replicas of a data object are stored on a single pod of the set of pods; and

a balancer module executed by the computer processor and configured to:

distribute at least a portion of the set of shards assigned to a first subset of pods in the set of pods among a second subset of pods in the set of pods according to an available processing capacity of each of the first subset and the second subset of pods in the set of pods, and

after distributing the at least the portion of the set of shards among the second subset of pods, distribute within a pod the set of replicas of the data object for a shard to ensure that each replica of the set of replicas for the shard is assigned to a node residing on a different storage rack of storage racks associated with the pod.

12. The system of claim 11 , further comprising:

a configuration module executed by the computer processor and configured to:

calculate the specified amount of nodes for each pod of the set of pods based on: an incoming network bandwidth, an outgoing network bandwidth, an amount of the set of replicas of each of the set of shards, an annualized failure rate, and a storage capacity of each of the set of nodes.

13. The system of claim 11 , wherein to assign, to the pod, nodes from the set of nodes residing on the set of storage racks, the balancer module is configured to:

establish that the pod is assigned nodes to maximize representation of the set of storage racks.

14. The system of claim 13 , wherein to assign, to the pod, nodes from the set of nodes residing on the set of storage racks, the balancer module is further configured to:

ensure that an amount of the set of storage racks is less than or equal to the specified amount of nodes for each pod of the set of pods.

15. The system of claim 13 , wherein to assign, to the pod, nodes from the set of nodes residing on the set of storage racks, the balancer module is further configured to:

ensure that an amount of the set of storage racks is greater than an amount of the set of replicas for each of the set of shards.

16. The system of claim 14 , wherein to distribute the set of replicas of the data object, the balancer module is configured to:

ensure that the amount of the set of storage racks is larger than an amount of the set of nodes that share a replica of the set of replicas.

17. The system of claim 11 , wherein the pod creation module is further configured to:

create an additional set of pods from the set of nodes residing on the set of storage racks.

18. The system of claim 11 , wherein the pod creation module is further configured to:

sort the set of storage racks according to an amount of nodes residing on the set of storage racks,

and wherein to create each pod of the set of pods, the pod creation module is configured to:

assign, to the pod, the nodes from the set of nodes residing on the set of storage racks that were sorted.

19. The system of claim 11 , further comprising:

a pod repair module executed by the computer processor and configured to:

determine that a first pod of the set of pods needs repair,

identify a first node of the set of nodes that ensures that a node from each of the set of storage racks is assigned to the first pod, and

assign the first node to the first pod.

20. The system of claim 19 , wherein to determine that the first pod of the set of pods needs repair, the pod repair module is configured to:

determine that at least two pods need repair, the at least two pods including the first pod, and

select to repair the first pod based on the first pod having a least specified amount of nodes assigned thereto.

21. A computer-implemented method of balancing, within a pod, replicas of a set of shards, the pod having assigned a set of nodes residing on a set of storage racks, the set of shards assigned to the set of nodes, the method comprising:

determining, by a computer processor, that the replicas of the set of shards are not balanced among the set of nodes;

responsive to the determining, identifying a candidate replica of a given shard of the set of shards;

identifying a subset of the set of storage racks that do not contain a replica of the given shard;

determining, from the subset of the set of storage racks, at least one node having the greatest amount of free space;

selecting, from the at least one node having the greatest amount of free space, a subset of nodes that would result in a lowest value for a maximum node shard overlap factor (SOF) between any pair of nodes within the pod;

selecting, from the subset of nodes, an additional subset of nodes that would result in a lowest value for a maximum rack SOF between any pair of storage racks associated with the pod;

designating, in a deterministic order from the additional subset of nodes, a destination node; and

reassigning the candidate replica to the destination node.

22. A computer-implemented method of balancing a set of shards assigned across a set of pods, wherein each shard of the set of shards comprises a set of replicas of a set of data objects, the method comprising:

for each pod of the set of pods, determining (i) a total weight of the corresponding set of shards assigned to the pod, and (ii) a capacity of the pod;

calculating, by a computer processor, a global average load across the set of pods based on a sum of the total weights of the corresponding sets of shards and a sum of the capacities of the set of pods;

determining, based on the global average load, the respective total weight of the corresponding set of shards, and the respective capacity of the pod, (i) a set of overloaded pods of the set of pods and (ii) a set of underloaded pods of the set of pods;

creating a shard pool including, for each pod in the set of overloaded pods:

removing a portion of the set of shards from the pod until removing an additional shard of the set of shards would result in the pod being underloaded, and

adding the portion of the set of shards to the shard pool;

generating an ordered list of shards from the shard pool according to a respective weight of each shard of the shard pool; and

until the shard pool is empty:

identifying the most underloaded pod from the set of underloaded pods, and

assigning, to the most underloaded pod, a shard from the shard pool having the highest weight according to the ordered list of shards.