HFR code: a flexible replication scheme for cloud storage systems

Bing Zhu, Hui Li, Kenneth W. Shum, Shuo-Yen Robert LiIet Commun 2015 · DOI

TL;DR

This paper introduces Heterogeneous Fractional Repetition (HFR) codes, a novel approach to data redundancy in cloud storage. HFR codes offer flexible replication by allowing different data chunks to have varying numbers of copies, improving storage efficiency and repair capabilities compared to existing methods. This flexibility is achieved through constructions based on combinatorial designs, leading to codes that achieve optimal storage capacity and offer multiple repair options for node failures.

What Problem Does This Paper Address?

Cloud storage systems, like those used by Amazon S3 and Google Cloud, store massive amounts of data across numerous nodes. These systems face constant node failures, making data reliability and efficient recovery crucial. Traditional replication (storing multiple identical copies) is simple but inefficient in terms of storage. Erasure codes, such as Reed-Solomon codes, offer better storage efficiency but can be complex and bandwidth-intensive during node repair.

Regenerating codes aim to minimize repair overhead by allowing a new node to be "regenerated" by contacting a subset of surviving nodes and downloading only a fraction of their data. Fractional Repetition (FR) codes are a specific type of regenerating code that achieves "uncoded repair," meaning surviving nodes simply transfer data without complex computations, significantly reducing repair complexity and bandwidth. However, standard FR codes require all coded packets to have the same repetition degree (number of copies). This paper addresses the limitation of uniform repetition degrees in FR codes, recognizing that in real-world systems, different data chunks might have varying importance or access patterns, thus benefiting from different replication levels.

Methods

The paper proposes Heterogeneous Fractional Repetition (HFR) codes, which generalize FR codes by allowing different coded packets to have different repetition degrees. This is achieved by:

  1. Outer MDS Code: An initial Maximum-Distance-Separable (MDS) code is used to encode the source data into a set of coded packets.
  2. Inner Heterogeneous Repetition Code: These coded packets are then replicated a specific number of times, but crucially, this number (the repetition degree) can vary across different packets. The paper defines a $\lambda$-HFR code as one with $\lambda$ distinct repetition degrees.
  3. Combinatorial Design Constructions: The core of the HFR code construction relies on Group Divisible Designs (GDDs). GDDs are mathematical structures that define sets of "points" and "blocks" with specific intersection properties. In this context, points represent coded packets, and blocks represent storage nodes. By carefully selecting GDDs, the authors can construct HFR codes where the distribution of packets across nodes naturally leads to the desired heterogeneous repetition degrees.
  4. Incidence Matrix Viewpoint: The paper also uses an incidence matrix representation to formally characterize the properties of HFR codes and prove their necessary and sufficient conditions for construction.
  5. Novel Design Framework: A new framework is proposed where storage nodes are partitioned into clusters. This is particularly useful when the outer MDS code is systematic (meaning some original data packets are stored directly). By organizing nodes into clusters, each containing a full set of systematic packets, data reconstruction can be significantly faster, as a data collector might only need to contact nodes within a single cluster.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and does not evaluate its proposed codes on any specific datasets.

Key Insights and Ideas

  • Flexibility is Key: The most significant insight is that enforcing uniform repetition degrees in FR codes is suboptimal. Real-world data access patterns (popularity) and data importance (functionality of systematic packets) warrant heterogeneous replication.
  • Combinatorial Designs as Building Blocks: The paper demonstrates the power of combinatorial designs, specifically Group Divisible Designs, in constructing complex and efficient coding schemes for distributed storage. This highlights a strong link between theoretical mathematics and practical system design.
  • Uncoded Repair Remains Optimal: HFR codes retain the desirable "uncoded repair" property of FR codes, meaning repair is computationally simple and bandwidth-efficient, even with heterogeneous replication.
  • Clustering for Faster Reconstruction: The proposed clustering framework, especially when combined with systematic MDS codes, offers a practical way to dramatically reduce data reconstruction time by localizing access to a subset of nodes. This is a crucial step towards making these advanced coding schemes more practical.
  • Trade-off between Repair and Reconstruction: The paper implicitly highlights a trade-off. While HFR codes optimize repair, the clustering framework optimizes reconstruction. Combining them offers a holistic improvement for cloud storage systems.

Key Results

  • Explicit Constructions: The paper provides explicit constructions for $\lambda$-HFR codes using Group Divisible Designs.
  • Achieving Storage Capacity: The constructed HFR codes are shown to achieve the system storage capacity ($C_{MBR}$) under the random access repair model.
  • Multiple Repair Alternatives: HFR codes offer multiple repair alternatives for node failures, increasing system robustness. The repair alternativity is shown to be $\prod_{i=1}^{\lambda} (p_i - 1)$, where $p_i$ are the repetition degrees.
  • Reduced Reconstruction Time: The proposed clustering framework, when applied to systematic MDS codes, can significantly reduce data reconstruction time. Simulations show that with random access, obtaining all systematic packets might occur with less than 4% probability, whereas with the proposed clustering, a data collector can reconstruct the source file without decoding if they connect to any one of the four clusters.

Limitations and Future Work

  • Existence of GDDs: The constructions rely on the existence of specific types of Group Divisible Designs. While the paper references existing results on GDD existence, finding suitable GDDs for all desired parameters might be challenging.
  • Complexity of Construction: While repair is simple, the initial construction of HFR codes might involve complex combinatorial design searches.
  • Future Work: The authors suggest exploring constructions of HFR codes from other combinatorial structures. Additionally, further investigation into the practical deployment implications of the clustering framework and its interaction with system metadata management would be valuable. The paper also hints at exploring the trade-offs between different types of repair (exact vs. functional) within the HFR framework.

Summary updated

BibTeX
@article{zhu2015hfr,
  author = {Bing Zhu and Hui Li and Kenneth W. Shum and Shuo-Yen Robert Li},
  title = {{HFR code: a flexible replication scheme for cloud storage systems}},
  journal = {Iet Commun},
  year = {2015},
  doi = {10.1049/iet-com.2014.1225},
}
Figure