A computer-implemented method for load balancing a scalable storage, the method comprising: receiving, by an assignment generator, partitions for assignment to servers of the scalable storage, wherein the partitions have partition values that quantify resource utilization of the scalable storage of a respective partition; generating, by the assignment generator, a plurality of assignment plans for the assignment of the partitions to the servers, wherein the servers have server values that quantify resource utilization of the scalable storage of a respective server, wherein an assignment plan describes which partition is to be assigned to which server of the scalable storage, wherein each assignment plan is determined by a different assignment heuristic, wherein each assignment heuristic corresponds to a different assignment strategy for the partitions, and wherein generating the plurality of assignment plans comprises, for each assignment heuristic: wherein a search order is determined by the respective assignment heuristic, wherein the search order is based on one of sorting the partitions by their corresponding partition values and sorting the servers by their corresponding server values, selecting each of the partitions according to the search order, and for each selected partition: iteratively searching, using the search order, for a candidate server for the assignment of the selected partition, wherein the candidate server at each iteration is determined according to server capacity to host the selected partition based on the respective assignment heuristic; selecting the determined candidate server in an iteration of the searching for the candidate server; and adding the candidate server to the assignment plan; receiving, by a plan analyzer, from the assignment generator, the plurality of assignment plans; selecting, by the plan analyzer, one of the generated assignment plans from the plurality of assignment plans for execution on the scalable storage based on assignment criteria; and executing the selected one of the assignment plans on the scalable storage. receiving, by an assignment generator, partitions for assignment to servers of the scalable storage, wherein the partitions have partition values that quantify resource utilization of the scalable storage of a respective partition; generating, by the assignment generator, a plurality of assignment plans for the assignment of the partitions to the servers, wherein the servers have server values that quantify resource utilization of the scalable storage of a respective server, wherein an assignment plan describes which partition is to be assigned to which server of the scalable storage, wherein each assignment plan is determined by a different assignment heuristic, wherein each assignment heuristic corresponds to a different assignment strategy for the partitions, and wherein generating the plurality of assignment plans comprises, for each assignment heuristic: wherein a search order is determined by the respective assignment heuristic, wherein the search order is based on one of sorting the partitions by their corresponding partition values and sorting the servers by their corresponding server values, selecting each of the partitions according to the search order, and for each selected partition: iteratively searching, using the search order, for a candidate server for the assignment of the selected partition, wherein the candidate server at each iteration is determined according to server capacity to host the selected partition based on the respective assignment heuristic; selecting the determined candidate server in an iteration of the searching for the candidate server; and adding the candidate server to the assignment plan; wherein a search order is determined by the respective assignment heuristic, wherein the search order is based on one of sorting the partitions by their corresponding partition values and sorting the servers by their corresponding server values, selecting each of the partitions according to the search order, and for each selected partition: iteratively searching, using the search order, for a candidate server for the assignment of the selected partition, wherein the candidate server at each iteration is determined according to server capacity to host the selected partition based on the respective assignment heuristic; selecting the determined candidate server in an iteration of the searching for the candidate server; and adding the candidate server to the assignment plan; iteratively searching, using the search order, for a candidate server for the assignment of the selected partition, wherein the candidate server at each iteration is determined according to server capacity to host the selected partition based on the respective assignment heuristic; selecting the determined candidate server in an iteration of the searching for the candidate server; and adding the candidate server to the assignment plan; receiving, by a plan analyzer, from the assignment generator, the plurality of assignment plans; selecting, by the plan analyzer, one of the generated assignment plans from the plurality of assignment plans for execution on the scalable storage based on assignment criteria; and executing the selected one of the assignment plans on the scalable storage.