Erasure Coding Technology in the Evolution of Vivo Storage Systems

This article reviews core research results on erasure coding (EC) from both academia and industry, then analyzes Vivo's online storage system EC. It optimizes and innovates EC techniques based on typical IDC, server, network resources, and business characteristics of internet enterprises, proposing an integrated EC solution (RS + LRC + intermediate‑result optimization + parallel repair across AZs) to support engineering practice.

1. Background

Erasure coding is a mainstream data redundancy method in cloud storage, offering lower storage overhead than replication while providing high reliability. The article cites the 2020 “Post‑Shannon Era” forum where efficient EC was highlighted as a key challenge.

2. Research Significance

Distributed storage systems use cheap commodity servers whose disks have limited lifespans (2‑7 years). To improve data reliability, replication and erasure coding are the two common redundancy schemes. EC trades computation for storage efficiency, making it the dominant technique in modern cloud storage.

3. Current EC Landscape

EC research splits into two camps: (1) pure theory focusing on coding complexity, repair bandwidth, storage overhead, etc., and (2) engineering‑oriented adaptations of existing codes (e.g., multi‑AZ, heterogeneous servers, large stripes, cross‑rack). Both camps drive the development of EC in distributed storage.

The article then surveys major EC families:

Reed‑Solomon (RS) codes – MDS, widely used but incur high repair bandwidth.

MDS array codes (EVENODD, RDP, STAR, Liberation, ZigZag, Blaum‑Roth) – XOR‑based, lower decoding complexity but with parameter constraints.

Regenerating codes (MSR, MBR) – aim to minimize storage or repair bandwidth; examples include Product‑Matrix MSR, Butterfly, Clay.

Locally Repairable Codes (LRC) – add local parity to reduce the number of nodes involved in a repair.

Piggyback frameworks (e.g., Hitchhiker) – embed extra information into parity to cut repair traffic.

4. Industrial Practices

RS remains the most mature EC in production (Google, AWS, Alibaba, etc.). The article also mentions HashTag (optimal regenerating code), Butterfly (FAST 2016), Clay (FAST 2018), and various LRC implementations (Azure, YottaChain).

5. Vivo’s EC Exploration and Practice

Vivo adopts RS as the base EC (CRS) and optimizes it through:

Bit‑matrix schedule representation to replace finite‑field multiplications with XOR/AND operations.

Parallel repair to reduce cross‑AZ bandwidth.

Integration of LRC and MSR for local fast repairs.

Key implementation details include the use of Cauchy matrices, GF(2^w) to bit‑matrix mapping, and a schedule format (op, sd, sb, dd, db) for efficient encoding/decoding.

The article also provides a C++ code fragment (shown as an image) illustrating the schedule‑based EC engine.

6. Production‑Environment Analysis

The article discusses IDC resource distribution, heterogeneous server capacities, and network bandwidth constraints. It emphasizes that EC repair traffic can amplify bandwidth usage (n‑fold compared to replication), making cross‑IDC bandwidth a critical factor.

7. Reliability Modeling

Vivo employs a Markov‑chain based MTTDL model combined with cluster‑level failure probability analysis. The model accounts for Mean Time To Failure (MTTF), Mean Time To Repair (MTTR), and Mean Time To Data Loss (MTTDL), providing a quantitative basis for EC design decisions.

8. Multi‑Fusion EC Scheme

Building on an 8+4 CRS baseline, Vivo proposes a two‑layer EC architecture:

Cross‑AZ strategy: LRC + RS + parallel repair + MSR. Local failures are repaired within an AZ using MSR; global failures leverage local parity plus intermediate results for bandwidth‑efficient recovery.

Example topology (16,4,4) across four AZs demonstrates how local parity (P) and global parity (Q) interact to minimize cross‑AZ traffic.

9. Conclusion

Erasure coding remains a hot research area. Vivo’s approach combines RS, parallel repair, LRC, and MSR to achieve low cross‑AZ bandwidth while maintaining high reliability. Ongoing work will continue to refine EC algorithms, reliability models, and deployment strategies.