Elastic Erasure Coding for Adaptive Redundancy
Wan Hee Cho, Anwitaman Datta · 2016
Redundancy is an essential mechanism for fault-tolerance, and yet, it inherently leads to overheads. This prompts an obvious question: how much resource ought to be provisioned in order to account for such overheads? As obvious as the question itself is, a good response is illusive. Provisioning in excess would cause wastage or under-utilization of capacity, while under-provisioning will lead to service disruptions to outright catastrophes. In the context of data storage, such adverse situations would be temporary unavailability to permanent loss of data. Thus, it is imperative to adapt the redundancy (elastic redundancy) in the system as per the environment and end user needs. In the context of data storage, if the redundancy is realized using full replication of data, then elasticity can be achieved by just creating (or garbage collecting) further copies of the said data. However, if erasure code is used instead (which is preferable, given the significantly lower storage overhead of erasure codes with respect to fully replicated systems), then, while shrinking redundancy can still be achieved similarly, expanding redundancy becomes non-trivial. A naive approach will require re-coding, which is both network and computation heavy. In this paper, we explore the possibility to use the resources at the edge storage nodes, applying network coding techniques, to both distribute computational load, as well as reduce network usage, and in the process, speed-up the process of creating additional redundancy. Specifically, in addition to defining the problem and analyzing the theoretical limits by leveraging on and extending the existing literature on regenerating codes, we propose a framework to realize erasure code instances that are amenable to network coding based elastic expansion of redundancy. We then carry out some preliminary evaluation of one specific code instance, which happens to be optimal with respect to the aforementioned established theoretical limit.