A system includes a storage system configured to store data objects as a plurality of shards according to a redundancy encoding technique at a plurality of availability zones. The system further includes a redundancy reduction manager configured to perform a shard spreading process and a shard pruning process. The shard spreading process involves identifying an underutilized availability zone for a particular data object and moving at least one shard of the particular data object from another availability zone to the underutilized availability zone. The shard pruning process involves identifying a pruning candidate availability zone and deleting a shard of a particular data object at the pruning candidate availability zone in response to determining that deleting the shard would not violate a durability model for the particular data object.