1. A computer-implemented method, comprising: under the control of one or more computer systems configured with executable instructions, receiving a first request for a first set of partition placements for placing a master partition of a volume, the master partition being a member of a partition replica pair comprising the master partition and a slave partition; generating the first set of partition placements based at least in part on a first server suitability score, the first server suitability score comprising how suitable a server is for placement of a specified partition, the first server suitability score based at least in part on a set of previous partition placements that were previously provided for other partitions of the volume; providing the first set of partition placements; receiving a second request for a second set of partition placements for placing the slave partition of the volume; generating the second set of partition placements based at least in part on a second server suitability score, the second server suitability score based at least in part on a rack diversity constraint, the set of previous partition placements, and the first set of partition placements; and providing the second set of partition placements.