Storage and repair bandwidth tradeoff for distributed storage systems with clusters and separate nodes

Jingzhao Wang, Tinghan Wang, Yuan Luo

TL;DR

This paper characterizes the fundamental tradeoff between storage cost and repair bandwidth for distributed storage systems (DSS) that use a hybrid architecture of clusters (racks) and separate, isolated nodes. By introducing novel algorithms to analyze information flow graphs, the authors provide a generalized model that helps engineers minimize expensive cross-cluster network traffic while maintaining data reliability.

What Problem Does This Paper Address?

In massive data centers, storage node failures are a "when," not an "if." To maintain reliability, systems use erasure coding, which requires a new node to download data from "helper" nodes to recover lost information. This process consumes repair bandwidth.

Standard models often treat all nodes as equal (homogeneous). However, real-world systems are hierarchical: nodes within the same rack (cluster) communicate over fast, cheap local networks, while cross-rack communication is slow and expensive. Previous research into "cluster DSS" often assumed that all surviving nodes must participate in a repair. This paper tackles a more realistic and flexible scenario:

  1. General Parameters: Repair can be performed using a subset of helper nodes ($d$).
  2. Hybrid Topology: The system includes both structured clusters and "separate nodes" that don't belong to any cluster.
  3. Bandwidth Differentiation: It distinguishes between intra-cluster, cross-cluster, and separate-node repair costs.

Methods

The authors employ Information Flow Graphs (IFGs)—a directed graph representation where edges represent data storage and transmission—to calculate the "min-cut," which defines the maximum data capacity the system can reliably support.

To find the optimal tradeoff, they introduce two key algorithms:

  • Vertical Order Algorithm: This determines the specific sequence of node repairs that results in the minimum possible capacity. In a heterogeneous system, the "history" of which nodes failed and where they were located matters.
  • Horizontal Selection Algorithm: This identifies the worst-case distribution of nodes across clusters. By finding this "bottleneck" configuration, the authors can define the lower bound of the system's capacity.

For the practical side, they use Interference Alignment, a signal processing technique, to propose a specific Minimum Storage Regenerating (MSR) code construction that achieves the theoretical optimal points on the tradeoff curve.

Datasets

As a theoretical paper in information theory and communications, it does not use empirical datasets. Instead, it validates the proposed models through:

  • Numerical Simulations: Using specific system parameters (e.g., $n=12$ nodes, $k=8$ for reconstruction, file size $M=32$) to plot tradeoff curves.
  • Mathematical Proofs: Rigorous derivations for Theorems 1, 2, and 3 to prove the optimality of their algorithms.

Key Insights and Ideas

  • Location Matters: In homogeneous systems, any $k$ nodes are as good as any other. Here, the "min-cut" depends heavily on how many nodes are selected from each cluster and the order in which they were repaired.
  • The "Separate Node" Influence: Adding isolated nodes complicates the tradeoff. The paper shows that for a system to be optimized, the repair strategy must prioritize "cheap" intra-cluster data even when separate nodes are involved in the network.
  • Generalizing the Tradeoff: By allowing the number of helper nodes ($d$) to be a variable rather than "all nodes," the authors bridge the gap between theoretical MDS codes and practical data center constraints.
  • Interference Cancellation: The MSR code construction demonstrates that by downloading specific linear combinations of data, a system can "cancel out" unwanted information (interference) from other nodes, allowing for successful repair with minimal cross-cluster traffic.

Key Results

  • Optimal Tradeoff Curves: The paper provides explicit curves showing how storage per node ($\alpha$) can be traded against cross-cluster bandwidth ($\beta_C$). For example, in a system with $n=12, k=8$, increasing the number of cross-cluster helper nodes significantly shifts the curve to the left, reducing the bandwidth required for a fixed storage amount.
  • MSR Code Achievement: The authors successfully demonstrated a (6,4) MDS code construction. In their numerical example ($M=8$), they showed that a node can be repaired by downloading only 1 symbol from each cross-cluster node and 2 symbols from intra-cluster nodes, matching the theoretical minimum.

Limitations and Future Work

  • Separate Node Complexity: While the paper introduces separate nodes, the full proof for multiple separate nodes is only sketched. Theorem 3 specifically focuses on the case with only one separate node.
  • Code Construction Scalability: The provided MSR code is a specific numerical example. Developing a generalized, explicit code construction that works for any arbitrary number of clusters, nodes, and separate nodes remains an open challenge.
  • Dynamic Environments: The model assumes static parameters for bandwidth and storage. Future work could explore how these tradeoffs change in "bursty" network conditions where cross-cluster costs fluctuate.

Summary updated

Abstract

The optimal tradeoff between node storage and repair bandwidth is an important issue for distributed storage systems (DSSs). For realistic DSSs with clusters, while repairing a failed node, downloading more data from intra-cluster nodes than from cross-cluster nodes is effective. Therefore, differentiating the repair bandwidth from intra-cluster and cross-cluster is useful. For cluster DSSs, the tradeoff is considered with special repair assumptions where all alive nodes are used for repairing a failed node. In this paper, we investigate the optimal tradeoff for the cluster DSSs under more general storage/repair parameters. Furthermore, we propose a regenerating code construction strategy that achieves the points in the optimal tradeoff curve for the cluster DSSs with specific parameters as a numerical example. Moreover, we consider the influence of separate nodes for the tradeoff for the DSSs with clusters and separated nodes.
BibTeX
@article{wang2018storage,
  author = {Jingzhao Wang and Tinghan Wang and Yuan Luo},
  title = {{Storage and repair bandwidth tradeoff for distributed storage systems with clusters and separate nodes}},
  journal = {Science China Information Sciences},
  year = {2018},
  url = {https://openreview.net/forum?id=kX59pZwa9Jr},
}

Loading related content...

Figure