FastTT: Accelerating Shift-XOR Erasure Coding for Data Storage

Erasure coding is a widely used redundancy technique for fault tolerance in data storage systems, offering significant space savings. However, it generally incurs substantial computational overhead. While existing research has explored various optimization techniques for classical Reed-Solomon (RS) erasure codes, more recent shift-XOR codes, which feature significantly lower computational complexity, have received comparatively little attention. In this paper, we focus on two-tone, the state-of-the-art shift-XOR code, and present the first comprehensive and high-optimized implementation of two-tone, FastTT. Due to its inherent shifting pattern, two-tone encounters challenges including redundant memory access operations and inefficient data traversal patterns. To address these issues, we propose a suite of optimization techniques: (1) Cache-Friendly Window Partitioning to improve data locality in both encoding and decoding; (2) Neighbor-Merging Access that combines adjacent data operations within registers to reduce memory traffic in encoding; (3) Erasure-Parity Mapping that simplifies the decoding process of all data and parity erased cases; and (4) Traversal Pattern Selection for accelerating the single-erasure recovery by exploiting the vectorization store operations. Validated across multiple configurations, FastTT consistently outperforms the state-of-the-art erasure coding libraries, including ISA-L and Cerasure, achieving an average encoding throughput improvement of 36.2% (up to 84.1%) and an average decoding throughput improvement of 33.5% (up to 182.1%).