A data storage system may be configured to allocate replica-sets in a balanced manner and mark some of these balanced replica-sets as being spares. As one or more drives or machines fail, the data storage system may move all copies of an affected replica-set to a marked spare replica-set and mark the affected replica-set as being inactive or invalid. As the failed drives are replaced, the data storage system may reconfigure those inactive replica-sets and use them as new spares. The data storage system may implement a coordinator module that handles the balancing and allocation of spares within a sub-cluster. The coordinator may also reallocate entire replica-sets across sub-clusters to maintain balance at the cluster level.