Distributed Storage Allocations for Optimal Service Rates

Distributed systems operate under storage access and download service uncertainty. We consider two access models. In one, a user can access each storage node with a fixed probability, and in the other, a user can access any fixed-size subset of nodes. We consider two download service models. In the first (small file) model, the time to transmit file data is negligible compared to the overall average download time. In the second (large file) model, the download time scales with the amount of downloaded data. The performance metric is the system's service rate. For a fixed redundancy level, the systems' service rate depends on the allocation of coded chunks over the storage nodes. Since finding the general optimal allocation is prohibitively hard, we consider quasi-uniform allocations, where coded content is equally spread among a subset of nodes. The question we address asks what the size of this subset (spreading) should be. We show that concentrating the coded content to a minimum-size subset is universally optimal for the small file model. However, for the large file model, the optimal spreading depends on the system parameters. These conclusions hold for both access models.