Techniques for incrementally increasing media size in data storage systems using grid encoded data storage techniques are described herein. A grid of shards is created where each shard of the grid of shards has a first index, a second index and each shard also has an associated storage device configured with a storage capacity that is large enough to store the largest set of data on a shard. Upon determining to replace the storage devices of the grid with storage devices that have a different storage capacity, the storage devices can be incrementally replaced within the grid by first padding each shard of the grid of shards with a set of data values, replacing a data shard storage device with a device of the different storage capacity, and replacing a set of derived shard storage devices with devices of the different storage capacity.
