Zpacr: A C Library in Searching for the Optimal Single-Disk Failure Recovery Solution for XOR-based Erasure Codes

Introduction

Zpacr is a library that implements various single-disk failure recovery methods for a number of XOR-based erasure codes, including:

Given the inputs (e.g., the specific coding scheme, stripe size, the failed disk), Zpacr returns a recovery solution, which specifies how to download blocks from other surviving disks for recovering the data of the input failed disk. The library is implemented in C.

The most innovative point of Zpacr is that it implements a replace recovery algorithm. The replace recovery algorithm uses a hill-climbing (greedy) technique to find an efficient recovery solution for a single-disk failure. It returns the optimal recovery solution for RDP, EVENODD and X-Code. It also provides a near-optimal recovery solution for the STAR code and the Cauchy Reed-Solomon code. Note that the computational complexity of the replace recovery algorithm is polynomial. In fact, the algorithm can be easily generalized to other XOR-based erasure codes.

Publication

Download

People

Zpacr is developed by Key Laboratory of High Performance Computing in the Department of Computer Science and Engineering at the University of Science and Technology of China (USTC). This project is also affiliated with the Advanced Network and System Research Laboratory at CUHK

Faculty: Students:

Please contact Yunfeng Zhu if you have any questions.