A hitchhiker’s guide to fast and efficient data reconstruction in erasure-coded data centers

Erasure codes such as Reed-Solomon (RS) codes are being extensively deployed in data centers since they offer signif-icantly higher reliability than data replication methods at much lower storage overheads. These codes however man-date much higher resources with respect to network band-width and disk IO during reconstruction of data that is miss-ing or otherwise unavailable. Existing solutions to this prob-lem either demand additional storage space or severely limit the choice of the system parameters. In this paper, we present Hitchhiker, a new erasure-coded storage system that reduces both network traffic and disk IO by around 25 % to 45 % during reconstruction of missing or otherwise unavailable data, with no additional storage, the same fault tolerance, and arbitrary flexibility in the choice of parameters, as compared to RS-based systems. Hitchhiker “rides ” on top of RS codes, and is based on novel encoding and decoding techniques that will be presented in this paper. We have implemented Hitchhiker in the Hadoop Distributed File System (HDFS). When evaluating various metrics on the data-warehouse cluster in production at Facebook with real-time traffic and workloads, during reconstruction, we observe a 36 % reduction in the computation time and a 32% reduction in the data read time, in addition to the 35 % re-duction in network traffic and disk IO. Hitchhiker can thus reduce the latency of degraded reads and perform faster re-covery from failed or decommissioned machines. 1