1. A computer-implemented method, comprising: under the control of one or more computer systems configured with executable instructions, selecting a first set of shards defined by a first redundancy encoding scheme, each shard of the first set of shards having a corresponding storage device of a set of storage devices configured to store the shard, each corresponding storage device having a consumed capacity and an available capacity, the available capacities of the set of storage devices including a plurality of available capacities; selecting a subset of the set of storage devices, the subset including a number of storage devices sufficient to implement a second redundancy encoding scheme, each storage device of the subset of the set of storage devices selected based at least in part on the available capacity of the storage device being greater than a threshold value; determining a minimum available capacity of the subset of the set of storage devices, the minimum available capacity determined such that each storage device of the subset of the set of storage devices has a corresponding available capacity greater than the minimum available capacity; generating a storage partition on each storage device of the set of storage devices, the storage partition having a storage capacity not greater than the minimum available capacity; and generating a second set of shards defined by a second redundancy encoding scheme, each shard of the second set of shards having a corresponding storage device of the subset of the set of storage devices configured to store the shard in the storage partition of the shard.