The Storage vs Repair-Bandwidth Trade-off for Clustered Storage Systems

Abstract

We study a generalization of the setting of regenerating codes, motivated by applications to storage systems consisting of clusters of storage nodes. There are $n$ clusters in total, with $m$ nodes per cluster. A data file is coded and stored across the $mn$ nodes, with each node storing $\alpha$ symbols. For availability of data, we require that the file be retrievable by downloading the entire content from any subset of $k$ clusters. Nodes represent entities that can fail. We distinguish between intra-cluster and inter-cluster bandwidth (BW) costs during node repair. Node-repair in a cluster is accomplished by downloading $\beta$ symbols each from any set of $d$ other clusters, dubbed remote helper clusters, and also up to $\alpha$ symbols each from any set of $\ell$ surviving nodes, dubbed local helper nodes, in the host cluster. We first identify the optimal trade-off between storage-overhead and inter-cluster repair-bandwidth under functional repair, and also present optimal exact-repair code constructions for a class of parameters. The new trade-off is strictly better than what is achievable via space-sharing existing coding solutions, whenever $\ell >0$. We then obtain sharp lower bounds on the necessary intra-cluster repair BW to achieve optimal trade-off. Our bounds reveal the interesting fact that, while it is beneficial to increase the number of local helper nodes $\ell$ in order to improve the storage-vs-inter-cluster-repair-BW trade-off, increasing $\ell$ not only increases intra-cluster BW in the host-cluster, but also increases the intra-cluster BW in the remote helper clusters. We also analyze resilience of the clustered storage system against passive eavesdropping by providing file-size bounds and optimal code constructions.

arXiv commentAccepted for publication in IEEE Transactions on Information Theory

References in corpus (4)

• Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction
• Distributed Storage Codes with Repair-by-Transfer and Non-achievability of Interior Points on the Storage-Bandwidth Tradeoff
• Capacity and Security of Heterogeneous Distributed Storage Systems
• Enabling Node Repair in Any Erasure Code for Distributed Storage

Cited by in corpus (5)

• Rack-Aware Regenerating Codes with Multiple Erasure Tolerance
• Efficient Recovery of a Shared Secret via Cooperation: Applications to SDMM and PIR
• Generalized regenerating codes and node repair on graphs
• Rack-Aware Regenerating Codes for Data Centers
• Explicit Constructions of MBR and MSR Codes for Clustered Distributed Storage