Techniques for exploiting variable media sizes to create new redundancy encoded data storage systems are described herein. A set of storage devices is selected based at least in part on each storage device having an available capacity and, using the set of storage devices, a set of shards for a redundancy encoded data storage system is generated such that each shard of the set of shards has a storage capacity corresponding to the minimum available capacity of the set of storage devices.