Convertible Codes: Enabling Efficient Conversion of Coded Data in Distributed Storage
Francisco Maturana, K. V. Rashmi · IEEE Transactions on Information Theory · 2022
Erasure codes are essential for providing efficient resilience against node failures in distributed storage. Typically, an$[n, k]$erasure code encodes$k$symbols into$n$symbols which are then stored in different nodes. Recent work by Kadekodi et al. shows that the failure rates of storage nodes vary significantly over time, and that changing the rate of the code (via a change in$n$and$k$) in response to such variations provides substantial storage space savings. However, the resource overhead of re-encoding the already encoded data is prohibitively high. We present a new theoretical framework formalizingcode conversion—the process of converting data encoded with an$[n^{ I}, k^{ I}]$code into data encoded with an$[{n^{ F}}, {k^{ F}}]$code while maintaining desired decodability properties. We then introduceconvertible codes, a new class of codes that allow for code conversions in a resource-efficient manner. This paper begins the study on convertible codes by focusing on linear MDS codes and the access cost of conversion. We derive a lower bound on the access cost of conversion and present an explicit optimal construction matching this bound for an important subclass of conversions. Additionally, we propose constructions with low field-size requirement for a broad subset of parameters. Our results show that it is possible to achieve code conversions with significantly less resources than the default approach of re-encoding for a wide range of parameters.