Fast Acceleration Strategies for XOR-Based Erasure Codes
Wei Wang, Min Lyu, Tianyang Niu, Qiliang Li, Liangliang Xu, Yinlong Xu · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2024
Erasure coding is a common redundancy scheme for tolerating failures in storage systems. Compared with replication, erasure coding saves a large amount of storage space, but incurs heavy computation overhead and, is more time consuming. In this article, we accelerate the coding speed with three techniques. First, we propose an algorithm to search coding bitmatrices with fewer 1’s from Vandermonde and Cauchy matrices, and further optimize the coding bitmatrices by greedily reducing the number of 1’s in the bitmatrices. So we can find near-optimal coding bitmatrices with the number of 1’s only up to 1% more than the lower bound. Next, we redesign the process of building pointers and reuse the pointers to access data for coding, which obtains a better tradeoff between spatial locality and computation efficiency. Finally, we smartly decompose the coding procedure of wide stripes into multiple subprocedures, to improve spatial locality and reduce the number of XORs. Based on the proposed techniques, we implement an erasure coding library, Cerasure. Extensive experiments show that Cerasure significantly improves the coding throughput. Compared with the state-of-the-art erasure coding libraries, Zerasure and SLPEC, Cerasure increases the encoding throughput by up to 200.2%.