PaperlayerView exact revision on arXiv

Source-linked AI summary

A Piggybacking Design Framework for Read-and Download-efficient Distributed Storage Codes

K. V. Rashmi, Nihar B. Shah, Kannan Ramchandran

arXiv:1302.5872v1cs.ITcs.DCcs.NImath.IT

TL;DR

Repairing a failed storage node requires reading and downloading data from surviving nodes, making both quantities important repair-efficiency measures. The paper introduces piggybacking, which adds designed functions of data across code instances, and constructs codes for several repair settings; parity-repair extensions save 25% to 50% in read and download.

  • Problem

    Repairing a failed storage node requires recovering its data by reading and downloading data from the remaining nodes, and both quantities determine repair efficiency.

    Source: §I · p. 1

  • Method

    Piggybacking combines multiple instances of an existing code by adding designed functions of one instance's data to another to reduce repair read and download.

    Source: §I · p. 2

  • Results

    The constructions provide MDS codes for high-rate, low-substripe and binary settings, MDS codes with smallest possible repair-locality, and parity-repair extensions saving 25% to 50% in read and download.

    Source: §I · pp. 2–3

  • Takeaways & Limitations

    The framework can also add efficient parity repair to existing codes designed for systematic-node repair while retaining their systematic-repair efficiency.

    Source: §I · p. 3, §VIII · p. 17

Abstract

from arXiv · show

We present a new 'piggybacking' framework for designing distributed storage codes that are efficient in data-read and download required during node-repair. We illustrate the power of this framework by constructing classes of explicit codes that entail the smallest data-read and download for repair among all existing solutions for three important settings: (a) codes meeting the constraints of being Maximum-Distance-Separable (MDS), high-rate and having a small number of substripes, arising out of practical considerations for implementation in data centers, (b) binary MDS codes for all parameters where binary MDS codes exist, (c) MDS codes with the smallest repair-locality. In addition, we employ this framework to enable efficient repair of parity nodes in existing codes that were originally constructed to address the repair of only the systematic nodes. The basic idea behind our framework is to take multiple instances of existing codes and add carefully designed functions of the data of one instance to the other. Typical savings in data-read during repair is 25% to 50% depending on the choice of the code parameters.

I. INTRODUCTION

Distributed storage codes need efficient repair because failed nodes must recover their data by reading and downloading from surviving nodes. Piggybacking adds designed functions of one code instance to another, yielding explicit codes for several repair settings while preserving properties such as minimum distance and field of operation.

I. INTRODUCTION

  • Piggybacking adds designed functions of one code instance to another to reduce repair data-read and download while preserving properties such as minimum distance and field of operation.The framework offers a design space for constructing codes in different settings.Source: §I · pp. 2, 4
  • The Class 1 codes are MDS, high-rate, and low-substripe, with the least known repair data-read and download in this class and support for all n and k.The paper identifies small substripe counts as a practical implementation consideration.Source: §I · p. 2
  • Binary MDS codes achieve the lowest known average repair data-read among existing binary MDS codes and optimize parity-node repair as well as systematic-node repair.They support all parameters for which binary MDS codes are known to exist.Source: §I · pp. 2–3
  • The framework constructs MDS codes with efficient repair and the smallest possible repair-locality for an MDS code.Repair-locality is the number of nodes read during repair.Source: §I · p. 3
  • Piggybacking enables efficient parity repair in existing codes designed only for systematic repair, while retaining systematic-node repair efficiency.The resulting parity-repair codes save 25% to 50% in repair data-read and download on average.Source: §I · p. 3
  • In the examples, systematic repair reads 6 symbols, 75% of the message, while second-parity repair reads 13 symbols instead of 16.The Fig. 1 example reports 25% savings in systematic repair; the Fig. 2 modification leaves systematic repair unchanged.Source: Figure 1 · p. 1, §I · p. 3

II. THE PIGGYBACKING FRAMEWORK

Piggybacking combines multiple instances of a base code by adding functions of earlier instances to later ones, with functions chosen to improve repair efficiency. The construction retains the base code’s decoding properties, including the MDS property when the base code is MDS.

II. THE PIGGYBACKING FRAMEWORK

  • Piggybacking adds functions of previously encoded instances to later instances of a base code, choosing those functions to reduce repair data-read and download.The base code may be chosen arbitrarily; piggyback functions depend on messages from earlier instances.Source: §II · p. 4
  • Decoding proceeds instance by instance: decode the first base-code instance, subtract its piggybacks from the next, and repeat for subsequent instances.Each instance’s piggybacks depend only on previously decoded instances.Source: §II · pp. 4–5
  • The choice of piggyback functions does not hamper the base code’s decoding properties, allowing those functions to be designed for efficient repair.Piggybacking preserves minimum distance, and piggybacking an MDS code preserves its MDS property.Source: §II · p. 5
  • Each node may also undergo its own invertible data transformation without changing the code’s decoding capabilities.The paper illustrates this with the transformation of node 6 in Example 1.Source: §II · p. 5
  • The constructed codes use repair-by-transfer, so the amount read during repair equals the amount downloaded.In general, download can be smaller than read when nodes send a non-injective function of their stored data.Source: §II · p. 5

III. PIGGYBACKING DESIGN 1

The first piggybacking design reduces data-read and download during repair while keeping the number of substripes small. With two substripes, it can save 25–35% during systematic-node repair.

III. PIGGYBACKING DESIGN 1

  • The design targets reduced data-read and download during repair with a small number of substripes.It presents piggyback functions and associated repair algorithms for systematic nodes and then parity nodes.Source: §III · p. 6
  • With two substripes, the design achieves 25–35% savings during systematic-node repair.Source: §III · p. 6
  • The section presents systematic-node repair first, then turns to parity-node repair.Source: §III · p. 6

A. Efficient repair of systematic nodes

This design partitions the systematic nodes into groups and uses piggybacks to recover failed systematic-node data. Group sizes are optimized because repair costs differ for the final group.

A. Efficient repair of systematic nodes

  • For a node outside the last group, the algorithm decodes b from the other b symbols and a parity symbol, then uses a piggyback and same-group symbols to recover the failed aℓ.This case requires k+k/r reads when groups are equal-sized.Source: A. Efficient repair of systematic nodes · p. 7
  • For a node in the last group, the algorithm decodes b, subtracts known parity contributions from a downloaded parity symbol, then uses the resulting piggyback and other symbols in that group to recover aℓ.The design partitions the k systematic nodes into r groups; the described repair methods recover both symbols aℓ and bℓ.Source: A. Efficient repair of systematic nodes · pp. 6–7
  • Repairing a systematic node in one of the first r−1 groups reads k+t symbols, while repair in the last group reads k+tr+r−2 symbols.The groups’ sizes are adjusted to minimize average read and download because repair in the final group costs more.Source: A. Efficient repair of systematic nodes · p. 7

B. Reducing data-read during repair of parity nodes

The design adds piggybacks to a parity symbol unused in systematic-node repair, enabling parity-node repair while preserving the code’s MDS property and systematic-repair procedure.

B. Reducing data-read during repair of parity nodes

  • This design uses m instances of the piggybacked code of Section III-A, yielding 2m substripes; m can be chosen arbitrarily, and higher values of m result in greater repair-efficiency.Source: B. Reducing data-read during repair of… · p. 7
  • The design adds piggybacks to a parity symbol that systematic-node repair does not read, preserving that repair procedure while retaining the MDS property.It employs m instances of the earlier design, yielding 2m substripes; higher m gives greater repair efficiency.Source: B. Reducing data-read during repair of… · pp. 7–8
  • To repair a parity node other than the first, the algorithm downloads selected systematic symbols and modified symbols, subtracts known components, and uses the remaining piggybacks and parity symbols to recover the failed node’s data.The first parity node is repaired by downloading all 2mk message symbols.Source: B. Reducing data-read during repair of… · p. 8

IV. PIGGYBACKING DESIGN 2

Piggybacking Design 2 partitions systematic nodes into groups and combines data across multiple base-code instances to reduce repair reads and downloads. Its higher repair efficiency requires more substripes, and parity repair can also be improved using multiple instances.

IV. PIGGYBACKING DESIGN 2

  • This design improves repair efficiency over the previous design, but requires (2r −3) substripes rather than 2 or 4.The stated minimums are 2 substripes for Section III-A and 4 for Section III-B.Source: §IV · p. 8
  • 20 of 30 message symbols are read and downloaded to repair a systematic node in the (n=13, k=10) example.The construction uses three instances of the base code.Source: §IV · pp. 8–9
  • The design uses (2r −3) base-code instances and partitions systematic nodes into (r −1) equal or nearly equal sets for its piggyback vectors.The piggyback vectors are designed so repair can recover the failed node's symbols from independent linear combinations.Source: §IV · pp. 9–10
  • Parity repair can be made more efficient by piggybacking odd instances onto succeeding even instances, with larger m reducing data-read and download.This extension follows a procedure analogous to the earlier design.Source: §IV · p. 11

V. PIGGYBACKING DESIGN 3

Design 3 uses structured piggybacks across substripes to reduce repair reads and downloads, while supporting minimum-locality repair for MDS codes. Its examples show the read reductions and the trade-offs associated with locality and substripe count.

V. PIGGYBACKING DESIGN 3

  • For any MDS code, the design repairs systematic nodes with the minimum possible locality, k+1; when n−k>2, its read and download are smallest among known MDS codes with this locality.Locality k is also possible, but necessarily requires downloading the entire data and is not considered.Source: §V · p. 11
  • In the n=11, k=8 example, even- and odd-substripe piggybacks use data from separate systematic-node groups, S1={1,2,3,4} and S2={5,6,7,8}.The example uses four instances of the base code.Source: §V · p. 11
  • 23 symbols, or 71% of the 32-symbol message, are read and downloaded on average to repair systematic nodes in the first-level example.The last substripe cannot be piggybacked, and its contribution to overall read decreases as the number of substripes increases.Source: §V · p. 12
  • The second-level example uses eight instances with n=13 and k=10, adding piggybacks for nodes 9 and 10 onto the first parity node.The first eight nodes are piggybacked onto parity nodes 12 and 13, while the first four substripes are divided from the last four for the additional piggybacks.Source: §V · pp. 12–13, Figure 4 · p. 12
  • In the n=13, k=10, α=8 example, repairing node 1 reads 48 symbols, or 60% of the message, from k+1=11 other nodes.Repairing node 9 also reads 48 symbols from 11 other nodes.Source: §V · p. 13

VI. COMPARISON OF DIFFERENT CODES

The comparison evaluates explicit repair-efficient codes against practical requirements and compares their average repair read and download. Piggyback codes require less average data-read and download than the listed alternatives under the plotted configurations.

VI. COMPARISON OF DIFFERENT CODES

  • The comparison considers whether explicit codes are MDS, which parameters they support, and their number of substripes against data-center requirements.The base code for each piggyback construction is Reed-Solomon, and its parameter m can be any value m ≥1.Source: §VI · pp. 13–14
  • Piggyback codes require less average data-read and download than Rotated-RS, repair-optimized EVENODD, and RDP in the plotted comparison.The plotted configurations use 8 substripes for Piggyback 1 and Rotated-RS, 4(2r −3) for Piggyback 2, and 16 for Piggyback 3.Source: §VI · p. 14

VII. REPAIRING PARITIES IN EXISTING CODES THAT ADDRESS ONLY SYSTEMATIC REPAIR

Piggybacking adapts codes designed for systematic-node repair to reduce parity-node repair reads and downloads while retaining systematic repair efficiency. The examples demonstrate this adaptation and give a parity-repair saving of around 33% in one construction.

VII. REPAIRING PARITIES IN EXISTING CODES THAT ADDRESS ONLY SYSTEMATIC REPAIR

  • In the two-instance example, piggybacking reduces second-parity repair from reading all 8 message symbols to reading and downloading 6.The MDS property carries over from the original code, and systematic-node repair remains optimal.Source: §VII · pp. 14, 16
  • The general design adds a parity symbol from one instance to a parity symbol of another, without changing systematic-node repair read or download requirements.The construction applies when the stated matrix condition holds for the selected parity nodes.Source: §VII · p. 16
  • For codes whose systematic repair has every parity node pass the same linear combination, the piggybacking condition holds for every pair of parity nodes.The cited constructions retain the MDS property and efficient systematic repair after piggybacking.Source: §VII · p. 16
  • In the r=3 example, the average read and download for parity repair is reported as a saving of around 33%.The first parity node is repaired by downloading all 2kµ symbols, whereas the other parity repairs use the piggybacked symbol and data from the systematic and parity nodes.Source: §VII · pp. 16–17

VIII. CONCLUSIONS AND OPEN PROBLEMS

The paper presents piggybacking as a way to improve repair efficiency in three settings and to extend efficient repair to parity nodes in codes focused on systematic-node repair. The optimal repair-efficiency under these settings remains open.

VIII. CONCLUSIONS AND OPEN PROBLEMS

  • The framework combines multiple code instances and adds functions of one instance’s data to another while preserving properties such as minimum distance and finite field of operation.The paper uses it to improve repair efficiency.Source: §VIII · p. 17
  • The framework is applied to three important settings and to enable efficient parity-node repair in existing codes focused on systematic-node repair.Source: §VIII · p. 17
  • Other piggybacking functions and base codes could potentially yield efficient codes for additional settings, but further exploration is left as future work.Source: §VIII · p. 18
  • The paper presents achievable schemes, while determining optimal repair-efficiency under these settings remains open.Source: §VIII · p. 18

APPENDIX

The proof represents data over a selected node set as a base-code vector, then expresses the piggybacked data as that vector plus a function of earlier instances. It invokes independence across instance messages to justify its last two equations.

APPENDIX

  • For a selected node set S, the proof represents base-code data in instance j as the |S|-length vector f(U_j).Source: APPENDIX · p. 19
  • The piggybacked data in instance j is written as f(U_j) + g_j(U_1, ..., U_{j−1}), where g_j is an arbitrary vector-valued function.Source: APPENDIX · p. 19
  • The proof attributes its last two equations to independence of the messages U_l across instances.Source: APPENDIX · p. 19
Loading 1302.5872v1…