An Efﬁcient Piggybacking Design Framework with Sub-packetization l (cid:54) r for All-Node Repair

—Piggybacking design has been widely applied in distributed storage systems since it can greatly reduce the repair bandwidth with small sub-packetization. Compared with other existing erasure codes, piggybacking is more convenient to operate and the I/O cost is lower. In this paper, we propose a new efﬁcient design which can further reduce the repair bandwidth with the sub-packetization l (cid:54) r where r = n − k . Generally, we let l (cid:54) 8 . Compared with other analogous designs, our design has lower l and the value of l is more ﬂexible. Moreover, our design can repair all nodes with small repair bandwidth. Therefore our piggybacking design is more feasible.


I. INTRODUCTION
I N the era of big data, countless amounts of data are generated every day. Therefore distributed storage systems are widely deployed in data centers. However the node failures occasionally happen. Erasure codes are widely used to retain the stability of the systems and MDS code is the most popular. A (k + r, k) MDS storage code, composed of (k + r) nodes, can tolerate the failure of any r nodes. If a node fails, it can be recovered by downloading data from some surviving nodes. The total data need to be downloaded to recover the failed node is termed as repair bandwidth. A trivial method is downloading the total data of any k surviving nodes, but it costs a lot. In 2010, Dimakis et al. [1] proposed the lower bound of the repair bandwidth of MDS codes and introduced a notion of regenerating codes that the failed nodes can be recovered by downloading same amount of data from each of the surviving nodes. Particularly, the ones with the optimal repair bandeidth are termed as MSR codes. MSR codes were studied extensively in [2]- [6].
The number of the sub-packets stored in each node that is termed as the sub-packetization is also an important indicator for regenerating codes. It has been proved that exponential sub-packetization is necessary for MSR codes [7]. Hence MSR codes are extremely difficult to apply into distributed storage systems. In 2013, Rashmi et al. [8], [9] proposed the piggybacking framework based on MDS array codes to reduce the repair bandwidth with samll sub-packetization. The failed nodes can be recovered by solving piggybacking functions which are downloaded from surviving nodes. And the piggybacked codes retain the MDS property. Since then, the piggybacking design has been further developed. Yang et al. [10] utilized the piggybacking design to obtian new MSR codes which are almost optimal repair bandwidth of parity nodes while retaining the optimal repair bandwidth of systematic nodes. Yuan et al. [11] and Shangguan et al. [12] proposed a generalized piggybacking codes (REPB&SPB) with the average repair bandwidth ratio 2 √ r+1 and √ 2r−1 r of systematic nodes respectively. And the sub-packetization l = r in [12]. For repairing all nodes, an efficient one-to-one piggybacking design (OOP) [13] was proposed by Li et al while the sub-packetization l = r − 1 + √ r − 1. Sun et al. [14] reduced the repair bandwidth of parity nodes in [12] by making full use of each parity node while retaining the repair bandwidth of systematic nodes. Jiang et al. [15] reduced the average repair bandwidth of all nodes by sacrificing a part of the systematic nodes repair bandwidth.
In this paper, we propose a new effcient piggybacking design (C). Compared with the designs in [12]- [14], our design has lower sub-packetization l r and can further reduces the repair bandwidth of systematic nodes in [13], [14] when l = r. Compared with the codes in [11], [15], the average repair bandwidth of all nodes and systematic nodes can be further reduced under the same parameters in this paper.
The remaining of the paper is organized as follows. Section II describes the framework of the new piggybacking and gives a toy example to illustrate the repair process of the design. The characteristics of the design are discussed in Section III. Section IV compares our design with some existing ones. The conclusion is given in section v.

II. THE NEW PIGGBACKING DESIGN
In this section, we propose a new explicit piggybacking design and show the repair process of our codes through an example. For any two integers i < j, denote by [i, j] = {i, i + 1, . . . , j} and [i] = {1, 2, . . . , i}.

A. The new piggybacking design
For an (n, k, l) MDS array code over F q , the original data symbols a 1 , . . . , a l are stored in the k systematic nodes, where a i = (a 1,i , . . . , a k,i ) . The corresponding parity symbols are P T 1 a i , . . . , P T r a i T ∈ F r q . In the piggybacking model, each substripe a 1,i , . . . , a k,i , P T 1 a i , . . . , P T r a i T ∈ F n q is an MDS codeword.  Let the sub-packetization l = s + t + u r, and denote k = α 1 u+β. Divide the systematic nodes into u groups where each of the first u−β groups contains α 1 nodes and each of the last β groups contains α 2 nodes, where α 1 = k u , α 2 = k u . As in figure 1, we obtian 1) the piggybacking design of data symbols: • For the ith group, we treat the first l − i symbols of each node as an • Partition the symbols in G i into r − 1 almost equal parts column by column and the number of symbols in each part is Then add each part of G i to P T 2 a l−i+1 , . . . , P T r a l−i+1 by piggybacking function in turn, where l = s + t + u, i ∈ [u].
2) the piggybacking design of parity symbols: • Partition the first s + t symbols of each parity node into two parts, s and t symbols respectively. We treat the first s symbols of the r parity nodes as an r × s matrix H 1 and use permutation g j = (1, 2, . . . , r) j act on the jth and i denotes the position of the ith element of the jth column. Then we have a new matrixH 1 . • Partition the symbols of the mth arrow ofH 1 into t almost equal parts and the number of symbols in each part is required to differ by no more than 1. Then add each part to P T m a s+1 , . . . , P T m a s+t in turn by piggybacking functions, where m ∈ [r]. It is easy to check that the MDS property of the code and the symbols added to each parity symbol will not come from the same node.

III. THE GENERAL REPAIR PROPERTIES
In this section, we will discuss the average repair bandwidth of our piggybacking design and the values of s, t, u to get the optimal repair bandwidth where l = s + t + u r.
Remark 1. Although we consider the total repair bandwidth of systematic nodes in one group, the repair process is one by one, i.e. we still consider the condition of single node failures.

A. The average repair bandwidth of systematic nodes
Define three variables as in section II: 1) The repair bandwidth of systematic nodes in the first u − β groups: Define γ i as the repair bandwidth of the ith group of systematic nodes, where i ∈ [u − β]. Firstly, consider the repair bandwidth of the first α 1 nodes. Let where z 1 is the remainder of α 1 (l − 1) mod r − 1. Therefore, the first r − 1 − z 1 positions of the parity symbols used to piggyback the first group of data symbols each piggyback ζ 1 symbols, and each position piggybacks ζ 1 symbols in the last z 1 positions.
Since only the last one symbol in each node of the first group has not been piggybacked, these α 1 symbols can be recovered only through the MDS property, i.e. download kα 1 symbols totaly. And other symbols are all piggybacked in some parity symbols, they can be recovered by some linear operations. Since kα 1 symbols have been downloaded, the original parity symbols in the last substripe can be recovered. Then in this process, ζ 1 or ζ 1 need to be downloaded for each data symbol recovered. Therefore we need download ((r − 1) − z 1 )·ζ 2 1 +z 1 · ζ 1 2 symbols to recover the remaining α 1 (l − 1) data symbols and γ 1 = kα 1 + ((r − 1) − z 1 ) · ζ 2 1 + z 1 · ζ 1 2 . Define ϕ 1 = · · · = ϕ (r−1)−z1 = ζ 1 , and ϕ (r−1)−z1+1 = · · · = ϕ r−1 = ζ 1 . Then Similarly, we can calculate the total repair bandwidth of the nodes in the ith group, . Then 2) The repair bandwidth of the last β groups: Since the only difference from III-A1 is that the last β groups each contain α 2 nodes, in a similar way, we have 3) The total repair bandwidth of systematic nodes: By (3) and (4), we obtain Theorem 1. The total repair bandwidth of systematic nodes in the new piggybacking design is 4) The lower bound of the average repair bandwidth of systematic nodes: Without loss of generality, we may assume u|k, then α 1 = α 2 = k u α. If u k, only need α 2 = α 1 + 1, and the rest of the process is all the same.
Define the average repair bandwidth and repair ratio of systematic nodes asγ sys = γsys k andγ sys =γ sys kl respectively. Proposition 2.γ sys andγ sys achieve their lower bounds . And Γ is defined as in (8). (6) meets the quality when z i = 0. Therefore the average repair bandwidth and define Then combine (7) with (8),γ sys andγ sys achieve the lower bounds when u = by some simple calculation.

B. The average repair bandwidth of parity nodes
Consider the repair bandwidth of parity nodes on the premise that the average repair bandwidth of the systematic nodes has been optimal in our scheme, i.e. we may assume u = 6l 2 −6l−1 3r−1 . As in Remark 1, consider the total repair bandwidth of parity nodes first. Let ω = s t , ω = s t , y = s − tω, clearly t s. Then the t positions used to piggyback parity symbols in each parity node, each of the first t−y positions piggybacks ω parity symbols, the rest of them each piggyback ω symbols.
1) The total repair bandwidth of parity nodes: Since only the first s symbols of each parity nodes have been piggybacked, the last t + u symbols can be recovered only through the MDS property. Then in this process, (t + u)kr symbols need to be downloaded to recover the original (t + u)r parity symbols first. On the other hand, there are rs+k(s+t)+ k u ((u−1)+· · ·+1) = rs+k(s+t)+ k(u − 1) 2 symbols that have been piggybacked to these (t+u)r symbols, for simplicity, we suppose α 1 = α 2 = k u , i.e. u |k . However only the rs + ks symbols of them haven't been downloaded yet, the rest belong to the rk(t + u) symbols that have been already downloaded in the first step. Hence only the rs + ks more symbols need to be downloaded.
Consider the repair of the first s symbols in each parity nodes next. To recover one symbol in this process, ω or ω symbols need to be downloaded. As in the section A, r (t − y) ω 2 + y (ω ) 2 symbols need to be downloaded totally. Therefore we can obtian Theorem 3. The total repair bandwidth γ par of parity nodes is 2) The lower bound of the average repair bandwidth of parity nodes: Define the average repair bandwidth of parity nodes asγ par = and t|s, ω = s t , thenγ par andγ par achieve their lower bounds (t + u)k + s(k+r) r + tω 2 and t+u l + s(k+r) rkl + tω 2 kl respectively when t = (l − u) r k(r−1) .
By s + t + u = l, we have s = l − u − t, since l and u are known, (10) can be viewed as a univariate polynomial with respect to t. Sinceγ par andγ par are are both constant multiples of γ sys , they achieve the lower bounds at the same point t = (l − u) r k(r−1) .

Remark 2.
Although the two extreme points we consider above do not necessarily make the average repair bandwidth of all nodes optimal, we believe that the repair of systematic nodes is the top priority and the gap is also negligible. The most relevant works to ours are [11], [12], [14], [15]. Define the code in this paper as C and the average repair bandwidth ratio of all nodes asγ all . Clearly,γ all =γ sys k k+r + γ par r k+r . Remark 4. In Yuan et al. [11], in order to reduce the repair bandwidth of parity nodes, the original sub-packetization l needs to be enlarged by m times, where m 2. There are two piggybacking designs that we call C 1 and C 2 here in Jiang et al. [15].
To some extent, the method of [12] is utilized to improve our work, but the repair bandwidth of systematic nodes in [12] and [14] is reduced by using more locations to piggyback the data information symbols in this paper. Furthermore, the designs in [12] and [14] are only suitable for the sub-paketization l = r. The average repair bandwidth ratioγ sys of systematic nodes of our design and SPB in [12] are plotted in Fig. 3. Since the repair bandwidth of systematic nodes is identical in [12] and [14], it is not necessary to make further comparison with [14]. On the other hand, it is not feasible for the subpacketization l 10 in industry, hence it is sufficient to consider l ∈ [5,10] in Fig. 3. And the repair bandwidth ratio can be reduced by about 5%. Sinceγ sys is independent with k, for the sake of high code rate, k in taken as 50 in Fig. 3.
In the following, we focus on comparing our repair bandwidth ratio with [11] and [15] under the same parameters. On the other hand, [15] reduced the average repair bandwidth ratio of all nodes in [11] by sacrificing a part of the systematic nodes repair bandwidth, hence the average repair bandwidth ratio of all nodes is compared with [15] in Fig. 4. And Fig.  5 shows the average repair bandwidth ratio of the systematic nodes in [11] and ours. In Fig. 4 and 5, k = 100 and l = 8. The repair bandwidth ratio can be reduced by about 8% and 6% respectively.
Actually, it is inevitable that our results outperform [11] and [15] , since during the repair process at each node, the fewer  [11] with k = 80, 10 r 20 and l 8 symbols are recovered only through the MDS property in this paper.

V. CONCLUSION
In this paper, we propose a new piggybacking design framework with sub-packetization l r for all nodes. The proposed design further reduces the repair bandwidth of all nodes in [11] and [15]. Moreover, it expands the scope of application of the design in [12] and [14] while reducing the repair bandwidth of systematic nodes. Compared to other piggybacking designs, the proposed design has lower sub-packetization and repair bandwidth, therefore it is more feasible in industry.