An MDS Code Construction for Optimal Update and Efficient Repair With Linear Subpacketization Level and Small Field Size

<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Maximum Distance Separable</i> (MDS) codes can provide the optimal storage efficiency with the same fault tolerance. From the practical considerations, the systematic and optimal update properties of codes are crucial, where the former affects the workflow of read/write operations while the latter impacts the write amplification costs in update intensive scenarios. Moreover, the repair bandwidth, subpacketization level, and finite field size are three important performance metrics to evaluate the effectiveness of codes, which impact the network traffic, I/O performance and computational complexity, respectively. However, various code constructions with the optimal update property were devised to minimize repair bandwidth with high subpacketization levels or huge finite field sizes. While other constructions that reach a good trade-off among these three performance metrics always lack the optimal update property. In this paper, to address the above challenges of constructing practical MDS codes, we present <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Permutation Transformation(PT) codes</i> that excel in the following respects: The systematic and optimal update properties can be both guaranteed; the code reaches nearly optimal repair bandwidth when repairing any single systematic node; the subpacketization level achieves a linear scale of the fault-tolerance capacity; the required size of the finite field to ensure the MDS property is small.