Leveled Product Codes for Optimal Block Repairs in Geo-distributed Storage Systems

To provide fault tolerance with low storage overhead, modern geo-distributed storage systems use erasure coding to stripe data redundancy across geographical regions. The prevalence of node, rack, and region failures motivates the needs for both single-block and multi-block repairs, yet block repairs trigger substantial cross-rack and cross-region data transfers. We propose a new family of erasure codes, Leveled Product Codes (LPCs), by adapting the classical Product Codes designed for disk arrays into geo-distributed storage systems. LPCs localize single-block repairs within racks and optimize multi-block repairs with the minimum sum of cross-rack and cross-region data transfers, while providing fault tolerance against node, rack, and region failures. We theoretically prove the optimality of LPCs, and further implement LPCs in a distributed storage prototype. Our numerical analysis and testbed evaluation show that LPCs significantly reduce the single-block and multi-block repair times of state-of-the-art hierarchy-aware erasure codes.