Source-linked AI summary
A Solution to the Network Challenges of Data Recovery in Erasure-coded Distributed Storage Systems: A Study on the Facebook Warehouse Cluster
K. V. Rashmi, Nihar B. Shah, Dikang Gu, Hairong Kuang, Dhruba Borthakur, Kannan Ramchandran
TL;DR
Erasure-coded storage improves efficiency but makes recovery network-intensive, motivating a closer study of its data-center impact. The paper measures recovery traffic in Facebook’s warehouse cluster and proposes Piggybacked-RS codes, which theoretically reduce recovery bandwidth and are estimated to save more than 50TB of cross-rack traffic daily.
Problem
RS codes improve storage efficiency but require substantial disk and network bandwidth during recovery because missing units cannot be copied from replicas.
Method
The paper measures RS-recovery traffic in Facebook’s production warehouse cluster and designs Piggybacked-RS codes using the Piggybacking framework.
Results
The proposed Piggybacked-RS code reduces recovery disk and network bandwidth by 30% for single-block failures and is estimated to cut cross-rack traffic by more than 50TB per day.
Takeaways & Limitations
Reducing recovery traffic could allow a greater fraction of data to use erasure coding, saving storage capacity.
Abstract
from arXiv · showhide
Erasure codes, such as Reed-Solomon (RS) codes, are being increasingly employed in data centers to combat the cost of reliably storing large amounts of data. Although these codes provide optimal storage efficiency, they require significantly high network and disk usage during recovery of missing data. In this paper, we first present a study on the impact of recovery operations of erasure-coded data on the data-center network, based on measurements from Facebook's warehouse cluster in production. To the best of our knowledge, this is the first study of its kind available in the literature. Our study reveals that recovery of RS-coded data results in a significant increase in network traffic, more than a hundred terabytes per day, in a cluster storing multiple petabytes of RS-coded data. To address this issue, we present a new storage code using our recently proposed "Piggybacking" framework, that reduces the network and disk usage during recovery by 30% in theory, while also being storage optimal and supporting arbitrary design parameters. The implementation of the proposed code in the Hadoop Distributed File System (HDFS) is underway. We use the measurements from the warehouse cluster to show that the proposed code would lead to a reduction of close to fifty terabytes of cross-rack traffic per day.
1 Introduction
Erasure codes improve storage efficiency and reliability, but their recovery procedures can impose substantial network and disk costs. The paper measures this impact in Facebook’s warehouse cluster and introduces Piggybacked-RS codes to reduce recovery bandwidth while preserving key RS-code properties.
- Motivation: Erasure codes offer higher storage efficiency than replication, with RS codes providing storage optimality and flexible parameters.Facebook’s warehouse cluster uses a (10, 4) RS code, requiring 1.4× storage versus 3× for conventional replication at a similar reliability level.
- Recovery challenge: RS recovery requires downloading multiple surviving units because no replica of the missing unit exists.Under a (k, r) RS code, the logical stripe data must be read and downloaded to reconstruct the missing unit.
- Study and contribution: The paper’s production study measures how RS-coded data recovery affects network infrastructure in Facebook’s warehouse cluster.The study examines hundreds of petabytes across a few thousand machines and identifies increased cross-rack traffic as a major network burden.
- Proposed solution: The paper introduces Piggybacked-RS codes, which target recovery costs while retaining RS codes’ storage optimality and parameter flexibility.The design is based on the Piggybacking framework and adds functions of one byte-level stripe onto parities of other stripes.
2 Measurements from Facebook’s warehouse cluster
Facebook’s warehouse cluster stores cold data with (10,4) RS coding to reduce storage overhead, but recovery operations impose substantial cross-rack traffic. Measurements show frequent single-block failures and high daily recovery volumes, motivating codes with smaller downloads.
- Cluster scale and storage: The two HDFS clusters store more than ten petabytes of RS-coded data, with capacity growing by a few petabytes weekly.
- Cluster scale and storage: Each 256MB block set is encoded into a stripe of 10 data blocks and 4 parity blocks placed across 14 machines and racks.
- Recovery impact: Recovery-induced network load is the primary deterrent to erasure-coding additional data whose access patterns would permit it.
- Failure and recovery patterns: A median of more than 50 machine-unavailability events occurs daily, although only a subset ultimately triggers recovery.
- Failure and recovery patterns: 98.08% of stripes with missing blocks have exactly one missing block, while 1.87% have two and 0.05% have three or more.The measurements cover six months.
- Recovery impact: A median of 95,500 RS-coded blocks requires recovery daily, transferring more than 180TB across racks through TOR switches.These transfers consume bandwidth otherwise available to foreground map-reduce jobs.
3 Piggybacked-RS codes & system design
Piggybacked-RS codes modify existing RS codes to reduce recovery reads and downloads while preserving storage optimality and failure tolerance. The proposed (10,4) code is expected to reduce bandwidth and cross-rack traffic, but implementation and production evaluation remain underway.
- Code design: Piggybacked-RS codes add functions of one byte-level stripe to parities of other stripes, reducing read and download during individual-unit recovery.The construction retains storage optimality.
- Code design: 3 bytes instead of 4 are downloaded to recover node 1 in the toy (2,2) example.The example combines two byte-level stripes and adds a data unit from one stripe to another stripe’s parity.
- Code design: 30% average savings in read and download are expected for single-block failures under the proposed (10,4) Piggybacked-RS code.The code remains storage optimal and tolerates any 4 failures in a stripe.
- Current implementation: The proposed code is being implemented in HDFS, with download, recovery-time, and reliability performance to be evaluated.The implementation is not yet complete.
- Estimated performance: More than 50TB of cross-rack traffic per day could be eliminated by replacing RS with Piggybacked-RS.The estimate uses the measured recovery workload, where 98% of operations are single-block recoveries and bandwidth requirements fall by 30%.
- Estimated performance: Piggybacked-RS is expected to lower recovery times because it reads and downloads less total data, despite contacting more nodes.Preliminary cluster experiments indicate that contacting more nodes does not affect recovery time; network and disk bandwidth dominate at multi-megabyte scale.
- Estimated performance: The code uses no additional storage and tolerates any r failures in a stripe, while higher MTTDL than RS is only expected.The MTTDL claim is presented as the authors’ belief based on anticipated faster recovery.
4 Current state of the project
The project is implementing Piggybacked-RS codes in HDFS and plans production-scale evaluation after completion. Additional measurements beyond those reported are also being collected.
- Implementation and evaluation: Piggybacked-RS codes are currently being implemented in HDFS and will be evaluated on a production-scale cluster after completion.The planned evaluation concerns the code’s performance.
- Implementation and evaluation: The project is continuing to collect measurements, including metrics beyond those presented in the paper.
5 Related work
Related work covers failure statistics, theoretical comparisons of replication and erasure codes, recovery-bandwidth code design, and LRC evaluations. The paper distinguishes its production network-usage analysis from these prior studies.
- Prior storage studies: Prior studies examined storage-system failure statistics and theoretical replication-versus-erasure-code comparisons for peer-to-peer storage.The cited theoretical comparison does not account for the k-fold read and download requirement of single-block RS recovery.
- Paper’s distinction: This paper focuses on measured network impact from erasure-code recovery in data centers, which it identifies as a previously unstudied area.
- Recovery-bandwidth codes: Regenerating codes introduced connecting to more nodes while downloading less from each, but existing constructions require high redundancy or support at most 3 parities.
- Local reconstruction codes: LRC studies report recovery-bandwidth or latency reductions, including Windows Azure measurements and Amazon EC2 simulations, but bandwidth measurements are absent from the Azure study.