Storage-Retrieval-Repair Cost Tradeoff in Network-Coded Distributed Storage Systems
Huazi Zhang, Cai Qi, Qiuyuan Huang, Dapeng Oliver Wu · 2016
In distributed storage systems, network coding can be used for reducing the amount of storage required to achieve the same level of reliability, compared with the current three-duplication schemes. However, in the case of a node failure, extra repair cost is required to generate a repair node. Meanwhile, to retrieve a certain amount of data, additional data may be downloaded to perform the necessary decoding. This ``retrieval cost", which may involve extra node access or data download, is a major concern in practice but has been generally overlooked in theory. In this paper, we propose the point of view that there exists a three dimensional tradeoff among storage cost, retrieval cost and repair cost. First, we define the three types of cost incurred in a network coded distributed storage system, and define the optimal tradeoffs among them. Second, we use a regeneration code-based framework to verify and illustrate the tradeoff. The results suggest that a cloud storage provider may dramatically save the overall cost by tuning to the optimal operational point.