Repair Duality with Locally Repairable and Locally
Regenerating Codes
Danilo Gligoroski∗ , Katina Kralevska∗ , Rune E. Jensen† , and Per Simonsen‡
Email: danilog@ntnu.no, katinak@ntnu.no, runeerle@idi.ntnu.no, per.simonsen@memoscale.com

arXiv:1701.06664v4 [] 30 Aug 2017

∗ Department

of Information Security and Communication Technology, NTNU, Norwegian University of Science and Technology
† Department of Computer Science, NTNU, Norwegian University of Science and Technology
‡ MemoScale AS, Norway

Abstract—We construct an explicit family of locally repairable
and locally regenerating codes whose existence was proven in a
recent work by Kamath et al. about codes with local regeneration
but no explicit construction was given. This explicit family of
codes is based on HashTag codes. HashTag codes are recently
defined vector codes with different vector length α (also called
a sub-packetization level) that achieve the optimal repair bandwidth of MSR codes or near-optimal repair bandwidth depending
on the sub-packetization level. We applied the technique of paritysplitting code construction. We show that the lower bound on the
size of the finite field for the presented explicit code constructions
can be lower than the one given in the work of Kamath et al.
Finally, we discuss the importance of having two ways for node
repair with locally regenerating HashTag codes: repair only with
local parity nodes or repair with both local and global parity
nodes. To the best of the authors’ knowledge, this is the first
work where this duality in repair process is discussed. We give
a practical example and experimental results in Hadoop where
we show the benefits of having this repair duality.

Keywords: Vector codes, Repair bandwidth, Repair locality,
Exact repair, Parity-splitting, Hadoop.
I. I NTRODUCTION
The repair efficiency of erasure coding in distributed storage
systems is measured with two main metrics: the amount of
transferred data during a repair process (repair bandwidth)
and the number of accessed nodes in a repair process (repair
locality). Two types of erasure codes that are optimal with
respect to these two metrics have emerged: Regenerating
Codes (RCs) [1] and Locally Repairable Codes (LRCs) [2]–
[4].
Minimum Storage Regenerating (MSR) codes are an important class of RCs that minimize the amount of data stored
per node and the repair bandwidth. Explicit constructions of
MSR codes can be found in [5], [6]. LRCs relax the maximum
distance separable (MDS) requirement in order to minimize
the number of nodes accessed during a repair. Studies on
implementation and performance evaluation of LRCs can be
found in [7]–[10]. Combining the benefits of RCs and LRCs
in one storage system can bring huge savings in practical
implementations. For instance, repair bandwidth savings by
RCs are important when repairing huge amounts of data, while
a fast recovery and an access to small number of nodes enabled
by LRCs are desirable for repair of frequently accessed data.

Several works present code constructions that combine the
benefits of RCs and LRCs [11]–[13]. Rawat et al. in [11]
and Kamath et al. in [12] have independently investigated
codes with locality in the context of vector codes, and they
call them locally repairable codes with local minimum storage
regeneration (MSR-LRCs) and codes with local regeneration,
respectively. Rawat et al. [11] provided an explicit construction, based on Gabidulin maximum rank-distance codes, of
vector linear codes with all-symbol locality for the case when
the local codes are MSR codes. However, the complexity of
these codes increases exponentially with the number of nodes
due to the two-stage encoding. In [12], Kamath et al. gave an
existential proof without presenting an explicit construction.
Another direction of combining RCs and LRCs is to use repair
locality for selecting the accessed nodes in a RC [13], while
an interpretation of LRCs as exact RCs was presented in [14].
Two different erasure codes, product and LRC codes, are used
to optimize for recovery performance and reduce the storage
overhead in [15].
Our Contribution: We construct an explicit family of
locally repairable and locally regenerating codes whose existence was proven in a recent work by Kamath et al. [12]
about codes with local regeneration. In that work, an existential
proof was given, but no explicit construction was given. Our
explicit family of codes is based on HashTag codes [5], [6].
HashTag codes are MDS vector codes with different vector
length α (also called a sub-packetization level) that achieve
the optimal repair bandwidth of MSR codes or near-optimal
repair bandwidth depending on the sub-packetization level. We
apply the technique of parity-splitting of HashTag codes in
order to construct codes with locality in which the local codes
are regenerating codes and which hence, enjoy both advantages
of locally repairable codes as well as regenerating codes.
We also show (although just with a concrete example) that
the lower bound on the size of the finite field where these
codes are constructed, given in the work by Kamath et al.
[12], can be lower. The presented explicit code construction
has a practical significance in distributed storage systems as
it provides system designers with greater flexibility in terms
of selecting various system and code parameters due to the
flexibility of HashTag code constructions.
Last but not least, we discuss the repair duality and its

importance. Repair duality is a situation of having two ways
to repair a node: to repair it only with local parity nodes or
repair it with both local and global parity nodes. To the best
of the authors’ knowledge, this is the first work that discusses
the repair duality and how it can be applied based on concrete
system and code parameters.
The paper is organized as follows. Section II presents
mathematical preliminaries. In Section III, we describe a
framework for explicit constructions of locally repairable and
locally regenerating codes. The repair process is analyzed in
Section IV where we explain the repair duality. Experimental
results of measurements in Hadoop are given in Section V.
Conclusions are summarized in Section VI.
II. M ATHEMATICAL P RELIMINARIES AND R ELATED W ORK
Inspired by the work of Gopalan et al. about locally repairable codes [2], Kamath et al. extended and generalized
the concept of locality in [12]. In this paper, we use notation
that is mostly influenced (and adapted) from those two papers.
Definition 1 ( [12]): A Fq -linear vector code of block
n
having a symbol alphabet Fα
length n is a code C ∈ Fα
q
q
for some α ≥ 1, i.e.
C = {c = (c1 , c2 , . . . , cn ), ci ∈ Fα
q for all i ∈ [n]},
and satisfies the additional property that for given c, c0 ∈ C
and a, b ∈ Fq ,
ac + bc0 = (ac1 + bc01 , ac2 + bc02 , . . . , acn + bc0n )
also belongs to C where aci is a scalar multiplication of the
vector ci . 
Throughout the paper, we refer to the vectors ci as vector
symbols or nodes. Working with systematic codes, it holds
that for the systematic nodes ci = di for 1 ≤ i ≤ k and for
the parity nodes
n ck+i = pi for 1 ≤ i ≤ r. For every vector
code C ∈ Fα
there is an associated scalar linear code C (s)
q
over Fq of length N = αn. Accordingly, the dimension of
the associated scalar code C (s) is K = αk. For a convenient
notation, the generator matrix G of size K × N of the scalar
code C (s) is such that each of the α consecutive columns
corresponds to one code symbol ci , i ∈ [n], and they are
considered as n thick columns Wi , i ∈ [n]. For a subset
I ⊂ [n] we say that it is an information set for C if the
restriction G|I of G to the set of thick columns with indexes
lying in I has a full rank, i.e. rank(G|I ) = K.
The minimum cardinality of an information set is referred
as quasi-dimension κ of the vector code C. As the vector code
C is Fq -linear, the minimum distance dmin of C is equal to
the minimum Hamming weight of a non-zero codeword in
C. Finally, a vector code of block length n, scalar dimension
K, minimum distance dmin , vector-length parameter α and
quasi-dimension κ is shortly denoted with [n, K, dmin , α, κ].
While in the general definition of vector codes in [12] the
quasi-dimension κ does not necessarily divide the dimension
K of the associated scalar, for much simpler and convenient
description of the codes in this paper we take that k = κ, i.e.

K = ακ. In that case the erasure and the Singleton bounds
are given by:
dmin ≤ n − κ + 1.
(1)
In [1], Dimakis et al. studied the repair problem in a distributed
storage system where a file of M symbols from a finite field
Fq is stored across n nodes, each node stores M
k symbols.
They introduced the metric repair bandwidth γ, and proved
that the repair bandwidth of a MDS code is lower bounded by
M
d
γ≥
,
(2)
k d−k+1
where d is the number of accessed available nodes (helpers).
Lemma 1 ( [1]): The repair bandwidth of a (n, k) MDS
code is minimized for d = n − 1. MSR codes achieve the
lower bound of the repair bandwidth equal to
M n−1
min
.
(3)
γM
SR =
k n−k
A (n, k) MSR code has the maximum possible distance
dmin = n − k + 1 in addition to minimizing the repair
bandwidth, but it has the worst possible locality.
Corollary 1: The locality of a (n, k) MSR code is equal to
n − 1.
Any [n, K, dmin , α, κ] vector code C is MDS if and only if
its generator matrix can be represented in the form G = [I|P ],
where the K × (N − K) parity matrix


G1,1 G1,2 . . .
G1,κ
 G2,1 G2,2 . . .
G2,κ 


P= .
(4)
.
..  ,
.
..
..
 ..
. 
Gκ,1 Gκ,2 . . . Gκ,n−κ
possesses the property that every square block submatrix of P
is invertible. The Gi,j entries are square sub-matrices of size
α × α, and a block submatrix is composed by different entries
of Gi,j .
In order to analyze codes with local regeneration, Kamath
et al. introduced a new family of vector codes called uniform
rank-accumulation (URA) codes in [12]. They showed that
exact-repair MSR codes belong to the class of URA codes.
Definition 2: [12, Def. 2] Let C be a [n, K, dmin , α, κ]
vector code with a generator matrix G. The code C is said to
have (l, δ) information locality if there exists a set of punctured
codes {Ci }i∈L of C with respective supports {Si }i∈L such that
• |Si | ≤ l + δ − 1,
• dmin (Ci ) ≥ δ, and
• rank(G|S
) = K.
i∈L
If we put δ = 2 in Def.2, then we get the definition of
information locality introduced by Gopalan et al. [2]. They
derived the upper bound for the minimum distance of a
(n, k, d)q code with information locality l for δ = 2 as
 
k
dmin ≤ n − k −
+ 2.
(5)
l
A general upper bound was derived in [12] as
 

k
dmin ≤ n − k + 1 −
− 1 (δ − 1).
l

(6)

Huang et al. showed the existence of Pyramid codes that
achieve the minimum distance given in (5) when the field size
is big enough [7]. Finally, based on the work by Gopalan et
al. [2] and Pyramid codes by Huang et al. [7], Kamath et al.
proposed a construction of codes with local regeneration based
on a parity-splitting strategy in [12].
III. C ODES WITH L OCAL R EGENERATION FROM H ASH TAG
C ODES BY PARITY-S PLITTING
In [5], [6], a new class of vector MDS codes called
HashTag codes is defined. HashTag codes achieve the lower
k
bound of the repair bandwidth given in (3) for α = rd r e ,
while they have near-optimal repair bandwidth for small subpacketization levels. HashTag codes are of a great practical
importance due to their properties: flexible sub-packetization
level, small repair bandwidth, and optimized number of I/O
operations. We briefly give the basic definition of HashTag
codes before we construct codes with local regeneration from
them by using the framework of parity-splitting discussed in
[12].
Definition 3: A (n, k, d)q HashTag linear code is a vector systematic code defined over an alphabet Fα
q for some
α ≥ 1. It encodes a vector x = (x1 , . . . , xk ), where
xi = (x1,i , x2,i , . . . , xα,i )T ∈ Fα
q for i ∈ [k], to a codeword
C(x) = c = (c1 , c2 , . . . , cn ) where the systematic parts ci =
xi for i ∈ [k] and the parity parts ci = (c1,i , c2,i , . . . , cα,i )T
for i ∈ {k + 1, . . . , n} are computed by the linear expressions
that have a general form as follows:
X
cj,i =
fν,j,i xj1 ,j2 ,
(7)
where fν,j,i ∈ Fq and the index pair (j1 , j2 ) is defined in the jth row of the index array Pi−r . The r index arrays P1 , . . . , Pr
are defined as follows:


(1, 1) (1, 2) . . . (1, k)
 (2, 1) (2, 2) . . . (2, k) 


P1 =  .
..
..  ,
..
 ..
.
.
. 
(α, 1)

(α, 2)

...

(α, k)
dk
re



z

}|

{

(?, ?)
(?, ?)

.

(?, ?)

(1, 1)
 (2, 1)

Pi =  .
 ..

(1, 2)
(2, 2)
..
.

...
...
..
.

(1, k)
(2, k)
..
.

(?, ?)
(?, ?)

...
...

(α, 1)

(α, 2)

...

(α, k)

(?, ?)

...

where the values of the indexes (?, ?) are determined by a
scheduling algorithm that guarantees the code is MDS, i.e.
the entire information x can be recovered from any k out of
the n vectors ci . 
One scheduling algorithm for Def. 3 is defined in [5], [6].
Example 1: The linear expressions for the parity parts for a
(9, 6) HashTag code with α = 9 are given here. The way how
we obtain them is explained in Section 4.1 in [6]. We give
one set of coefficients fν,j,i for equation (7) from the finite
field F32 with irreducible polynomial x5 + x3 + 1. This code
achieves the lower bound of repair bandwidth in (3), i.e. the

Fig. 1. There are r parity nodes from a systematic (n, k) MDS code with a
sub-packetization level α. The parity splitting technique generates from every
parity node p1 , . . . , pδ−1 l local parity nodes and renames the parity nodes
pδ , . . . , pr as global parity nodes g1 , . . . , gr−δ+1 .

repair bandwidth is γ =
node.

8
3

= 2.67 for repair of any systematic

c1,7
c2,7
c3,7
c4,7
c5,7
c6,7
c7,7
c8,7
c9,7

= 7x1,1 +10x1,2 +18x1,3 +11x1,4 +17x1,5 + 6x1,6
=26x2,1 +17x2,2 +25x2,3 +27x2,4 +31x2,5 + 4x2,6
=22x3,1 +12x3,2 +27x3,3 +31x3,4 +31x3,5 +23x3,6
=17x4,1 + 9x4,2 +14x4,3 + 4x4,4 +21x4,5 +25x4,6
=20x5,1 + 5x5,2 + 5x5,3 +13x5,4 +11x5,5 +16x5,6
=25x6,1 +16x6,2 +30x6,3 +28x6,4 +10x6,5 +24x6,6
=20x7,1 + 8x7,2 +21x7,3 + 9x7,4 + 3x7,5 +25x7,6
=23x8,1 + 4x8,2 +12x8,3 +16x8,4 + 8x8,5 +17x8,6
= 2x9,1 +21x9,2 + 8x9,3 +16x9,4 + 7x9,5 +25x9,6

c1,8
c2,8
c3,8
c4,8
c5,8
c6,8
c7,8
c8,8
c9,8

= 8x1,1 +24x1,2 +21x1,3 +19x1,4 + 6x1,5 +20x1,6 + 8x4,1 + 6x2,4
= 3x2,1 +12x2,2 + 6x2,3 + 3x2,4 +16x2,5 +10x2,6 +30x5,1 +24x1,5
=23x3,1 +20x3,2 +30x3,3 + 7x3,4 +16x3,5 +10x3,6 +21x6,1 +27x1,6
=14x4,1 + 7x4,2 +10x4,3 +14x4,4 +24x4,5 +20x4,6 +16x1,2 +31x5,4
=25x5,1 +11x5,2 +29x5,3 +12x5,4 +20x5,5 +24x5,6 +15x2,2 + 6x4,5
=17x6,1 +27x6,2 + 4x6,3 +21x6,4 +15x6,5 +11x6,6 +19x3,2 +21x4,6
=19x7,1 +23x7,2 +16x7,3 + 4x7,4 +14x7,5 +16x7,6 + 9x1,3 + 8x8,4
= 5x8,1 +26x8,2 +22x8,3 +30x8,4 +22x8,5 +21x8,6 +24x2,3 +26x7,5
=10x9,1 + 8x9,2 +10x9,3 +27x9,4 +28x9,5 +20x9,6 +16x3,3 + 4x7,6

c1,9
c2,9
c3,9
c4,9
c5,9
c6,9
c7,9
c8,9
c9,9

=20x1,1 +20x1,2 +30x1,3 +17x1,4 +12x1,5 +27x1,6 +28x7,1 + 9x3,4
=18x2,1 +10x2,2 +20x2,3 +21x2,4 +13x2,5 + 7x2,6 + 2x8,1 + 6x3,5
=31x3,1 +25x3,2 +12x3,3 +18x3,4 +15x3,5 +24x3,6 +31x9,1 +28x2,6
= 6x4,1 +16x4,2 +26x4,3 + 4x4,4 +21x4,5 +27x4,6 +26x7,2 + 8x6,4
= 7x5,1 + 6x5,2 +26x5,3 + 6x5,4 +15x5,5 +16x5,6 +28x8,2 + 4x6,5
=20x6,1 +20x6,2 +12x6,3 +20x6,4 +18x6,5 +26x6,6 +19x9,2 +30x5,6
=26x7,1 + 2x7,2 + 6x7,3 +20x7,4 +17x7,5 +23x7,6 + 8x4,3 +31x9,4
=20x8,1 +15x8,2 +13x8,3 +20x8,4 +10x8,5 +24x8,6 +31x5,3 + 9x9,5
= 6x9,1 + 2x9,2 +31x9,3 +12x9,4 +16x9,5 +30x9,6 +20x6,3 +13x8,6

We adapt the parity-splitting code construction for designing
codes with local regeneration described in [12] for the specifics
of HashTag codes. The construction is described in Construction 1. For simplifying the description, we take some of the
parameters to have specific relations, although it is possible
to define a similar construction with general values of the
parameters. Namely, we take that r|k and r|α. We also take
that the parameters for the information locality (l, δ) are such
that l|k and δ ≤ r.
Construction 1: An input to the construction is a (n, k)
HashTag MDS code with a sub-packetization level α. This
input comes with the associated linear parity equations (7),
i.e. with the associated systematic generator matrix G. The
MDS code can be, but it does not necessarily have to be a
MSR code. Another input is the information locality (l, δ)
that the constructed code with local regeneration will have.
The following steps are performed:

Step 1. Split k systematic nodes into l disjunctive subsets
Si , i ∈ [l], where every set has kl nodes. While this
splitting can be arbitrary, take the canonical splitting
where S1 = {1, . . . , kl }, S2 = { kl + 1, . . . , 2k
l }, . . .,
Sl = { (l−1)k
+
1,
.
.
.
,
k}.
l
Step 2. Split each of the α linear equations for the first δ −1
parity expressions (7) into l sub-summands where the
variables in each equation correspond to the elements
from the disjunctive subsets.
Step 3. Associate the obtained α×l×(δ −1) sub-summands
to l × (δ − 1) new local parity nodes.
Step 4. Rename the remaining r − δ + 1 parity nodes that
were not split in Step 1 - Step 3 as new global parity
nodes.
Step 5. Obtain a new systematic generator matrix G0 from
the local and global parity nodes.
Step 6. Return G0 as a generator matrix of a [n, K =
kα, dmin , α, k] vector code with information locality
(l, δ).
A graphical presentation of the parity-splitting procedure is
given in Fig. 1.
Theorem 1: If the used (n, k) MDS HashTag code in Construction 1 is MSR, then the obtained [n, K = kα, dmin , α, k]
code with information locality (l, δ) is a MSR-Local code,
where


k
− 1 (δ − 1).
(8)
dmin = n − k + 1 −
l
Proof: (Sketch) Since in Construction 1 we took that r|k
and r|α, it means that the scalar dimension of the code is K =
mlα for some integer m. Then the proof continues basically as
a technical adaptation of the proof of Theorem 5.5 that Kamath
et al. gave for the pyramid-like MSR-Local codes constructed
with the parity-splitting strategy in [12].
k
Note that if α < r r , then HashTag codes are sub-optimal
in terms of the repair bandwidth. Consequently, the produced
codes with Construction 1 are locally repairable, but they are
not MSR-Local codes.
Example 2: Let us split the MSR code given in Example
1 into a code with local regeneration and with information
locality (l = 2, δ = 2). In Step 1 we split 6 systematic nodes
{c1 , . . . , c6 } into l = 2 disjunctive subsets S1 = {c1 , c2 , c3 }
and S2 = {c4 , c5 , c6 }. According to Step 2 of Construction
1, the first global parity c7 in Example 1 is split into two
local parities l1 = (l1,1 , . . . , l9,1 )T and l2 = (l1,2 , . . . , l9,2 )T
as follows:
l1,1
l2,1
l3,1
l4,1
l5,1
l6,1
l7,1
l8,1
l9,1

= 7x1,1 +10x1,2 +18x1,3
=26x2,1 +17x2,2 +25x2,3
=22x3,1 +12x3,2 +27x3,3
=17x4,1 + 9x4,2 +14x4,3
=20x5,1 + 5x5,2 + 5x5,3
=25x6,1 +16x6,2 +30x6,3
=20x7,1 + 8x7,2 +21x7,3
=23x8,1 + 4x8,2 +12x8,3
= 2x9,1 +21x9,2 + 8x9,3

l1,2
l2,2
l3,2
l4,2
l5,2
l6,2
l7,2
l8,2
l9,2

=11x1,4 +17x1,5 + 6x1,6
=27x2,4 +31x2,5 + 4x2,6
=31x3,4 +31x3,5 +23x3,6
= 4x4,4 +21x4,5 +25x4,6
=13x5,4 +11x5,5 +16x5,6
=28x6,4 +10x6,5 +24x6,6
= 9x7,4 + 3x7,5 +25x7,6
=16x8,4 + 8x8,5 +17x8,6
=16x9,4 + 7x9,5 +25x9,6

The remaining two global parities are kept as they
are given in Example 1, they are only renamed as

g1 = (c1,8 , c2,8 , . . . , c9,8 )T and g2 = (c1,9 , c2,9 , . . . , c9,9 )T .
The overall code is a (10, 6) code or with the terminology
from [8] it is a (6, 2, 2) code. 
Example 3: Let us split the same MSR code now
with parameters (l = 3, δ = 2). In Step 1 we split 6
systematic nodes {c1 , . . . , c6 } into l = 3 disjunctive subsets
S1 = {c1 , c2 }, S2 = {c3 , c4 } and S3 = {c5 , c6 }. In Step 2
of Construction 1, the first global parity c7 is split into three
local parities: l1 = (l1,1 , . . . , l9,1 )T , l2 = (l1,2 , . . . , l9,2 )T and
l3 = (l1,3 , . . . , l9,3 )T as follows:
l1,1
l2,1
l3,1
l4,1
l5,1
l6,1
l7,1
l8,1
l9,1

= 7x1,1 +10x1,2
=26x2,1 +17x2,2
=22x3,1 +12x3,2
=17x4,1 + 9x4,2
=20x5,1 + 5x5,2
=25x6,1 +16x6,2
=20x7,1 + 8x7,2
=23x8,1 + 4x8,2
= 2x9,1 +21x9,2

l1,2
l2,2
l3,2
l4,2
l5,2
l6,2
l7,2
l8,2
l9,2

=18x1,3 +11x1,4
=25x2,3 +27x2,4
=27x3,3 +31x3,4
=14x4,3 + 4x4,4
= 5x5,3 +13x5,4
=30x6,3 +28x6,4
=21x7,3 + 9x7,4
=12x8,3 +16x8,4
= 8x9,3 +16x9,4

l1,3
l2,3
l3,3
l4,3
l5,3
l6,3
l7,3
l8,3
l9,3

=17x1,5 + 6x1,6
=31x2,5 + 4x2,6
=31x3,5 +23x3,6
=21x4,5 +25x4,6
=11x5,5 +16x5,6
=10x6,5 +24x6,6
= 3x7,5 +25x7,6
= 8x8,5 +17x8,6
= 7x9,5 +25x9,6

The remaining two global parities are kept as they
are given in Example 1, but they are just renamed as
g1 = (c1,8 , c2,8 , . . . , c9,8 )T and g2 = (c1,9 , c2,9 , . . . , c9,9 )T .
The overall code is a (11, 6) code or with the terminology
from [8] it is a (6, 3, 2) code. 
There are two interesting aspects of Theorem 1 that should
be emphasized: 1. We give an explicit construction of an MSRLocal code (note that in [12] the construction is existential),
and 2. Examples 2 and 3 show that the size of the finite field
can be slightly lower than the size proposed in [12]. Namely,
the MSR HashTag code used in our example is defined over
F32 , while thelower bound in [12] suggests the field size to be
bigger than 96 = 84. We consider this as a minor contribution
and an indication that a deeper theoretical analysis can further
lower the field size bound given in [12].
IV. R EPAIR D UALITY
Theorem 2: Let C be a (n, k) MSR HashTag code with
M n−1
0
min
γM
SR = k n−k . Further, let C be a [n, K = kα, dmin , α, k]
code with local regeneration and with information locality
min
(l, δ) obtained by Construction 1. If we denote with γLocal
the
minimum repair bandwidth for single systematic node repair
with C 0 , then
M kl + δ − 2 M n − 1
min
γLocal
= min(
,
).
(9)
k δ−1
k n−k
Proof: When repairing one systematic node, we can
always treat local nodes as virtual global nodes from which
they have been constructed by splitting. Then with the use
of other global nodes we have a situation of repairing one
systematic node in the original MSR code for which the repair
n−1
bandwidth is M
k n−k . On the other hand, if we use the MSRLocal code, then we have the following situation. There are kl
systematic nodes in the MSR-Local code, and the total length
of the MSR-Local code is kl + δ − 1. The file size for the
MSR-Local code is decreased by a factor l, i.e. it is Ml . If we

apply the MSR repair bandwidth for these values we get:
M
l
k
l

·

k
l

+ (δ − 1) − 1
M
=
δ−1
k

k
l

+δ−2
.
δ−1

Theorem 2 is one of the main contributions of this work:
It emphasizes the repair duality for repairing one systematic
node: by the local and global parity nodes or only by the local
parity nodes. We want to emphasize the practical importance
of Theorem 2. Namely, in practical implementations regardless
min
, the number of I/O operations
of the theoretical value of γLocal
and the access time for the contacted parts can be either
crucial or insignificant. In those cases an intelligent repair
strategy implemented in the distributed storage system can
decide which repair procedure should be used: the one with
global parity nodes or the one with the local parity nodes. We
illustrate this by the following example.
Example 4: Let us consider the (9, 6) MSR HashTag code
given in Example 1 and its corresponding local variant from
Construction 1 with information locality (l = 2, δ = 2) given
in Example 2. That means that the code with local regeneration
has 6 systematic nodes, 2 local and 2 global parity nodes.
Let us analyze the number of reads when we recover one
unavailable systematic node. If we recover with the local
nodes, then we have to perform 3 sequential reads, reading
the whole data in a contiguous manner from 3 nodes. If we
repair the unavailable data with the help of both local and
global parity nodes, it reduces to the case of recovery with a
MSR code, where the number of sequential reads is between
8 and 24 (average 16 reads) but the amount of transferred data
is equivalent to 2.67 nodes.
More concretely, let us assume that we want to recover the
node x1 = (x1,1 , x2,1 , . . . , x9,1 )T .
1) For a recovery only with the local parity l1 , 3 sequential
reads of l1 , x2 and x3 are performed.
2) For a recovery with the local and global parities:
a) First, read l1,1 , l2,1 and l3,1 from l1 , and x1,2 , x2,2
and x3,2 from x2 and x1,3 , x2,3 and x3,3 from x3
to recover x1,1 , x2,1 and x3,1 .
b) Additionally, read x1,4 , x2,4 and x3,4 from x4 and
x1,5 , x2,5 and x3,5 from x5 and x1,6 , x2,6 and x3,6
from x6 .
c) Then, read c1,8 , c2,8 and c3,8 from the global parity
g1 to recover x4,1 , x5,1 and x6,1 .
d) Finally, read c1,9 , c2,9 and c3,9 from the global
parity g2 to recover x7,1 , x8,1 and x9,1 .
Now, let a small file of 54 KB be stored across 6 systematic,
2 local and 2 global parity nodes. The sub-packetization level
is α = 9, thus every node stores 9 KB, sub-packetized in 9
parts, each of size 1 KB. If the access time for starting a read
operation is approximately the same as transferring 9 KB, then
repairing with local and global parity nodes is more expensive
since we have to perform in average 12 reads, although the
amount of transferred data is equivalent to 2.67 nodes.
On the other hand, let us have a big file of 540 MB
stored across 6 systematic nodes and 2 local and 2 global

parity nodes. The sub-packetization level is again α = 9, thus
every node stores 90 MB, sub-packetized in 9 parts, each of
size 10 MB. The access time for starting a read operation is
again approximately the same as transferring 9 KB, which is
insignificant in comparison with the total amount of transferred
data in the process of repairing of a node. In this case, it is
better to repair a failed node with local and global parity nodes
since it requires a transfer of 240 MB versus the repair just
with local nodes that requires a transfer of 270 MB.
V. E XPERIMENTS IN H ADOOP
The repair duality discussed in Example 4 of previous
section was mainly influenced by one system characteristic:
the access time for starting a read operation. In different
environments of distributed storage systems there are several
similar system characteristics that can affect the repair duality
and its final optimal procedure. We next discuss this matter
for Hadoop.
Hadoop is an open-source software framework used for
distributed storage and processing of big data sets [16]. From
release 3.0.0-alpha2 Hadoop offers several erasure codes such
as (9, 6) and (14, 10) Reed-Solomon (RS) codes. Hadoop
Distributed File System (HDFS) has the concepts of Splits
and Blocks. A Split is a logical representation of the data
while a Block describes the physical alignment of data. Splits
and Blocks in Hadoop are user defined: a logical split can be
composed of multiple blocks and one block can have multiple
splits. All these choices determine in a more complex way the
access time for I/O operations.
To verify the performance of HashTag codes and their
locally repairable and locally regenerating variants we implemented them in C/C++ and used them in HDFS.
For the code (9, 6) we used one NameNode, nine DataNodes, and one client node. All nodes had a size of 50 GB
and were connected with a local network of 10 Gbps. The
nodes were running on Linux machines equipped with Intel
Xeon E5-2676 v3 running on 2.4 GHz. We have experimented
with different block sizes (90 MB and 360 MB), different
split sizes (512 KB, 1 MB and 4 MB) and different subpacketization levels (α = 1, 3, 6, and 9) in order to check how
they affect the repair time of one lost node. The measured
times to recover one node are presented in Fig. 2. Note that
the sub-packetization level α = 1 represents the RS code that
is available in HDFS, while for every other α = 3, 6, 9 the
codes are HashTag codes. In all measurements HashTag codes
outperform RS. The cost of having significant number of I/O
operations for the sub-packetization level α = 9 is the highest
for the smallest block and split size (Block size of 90 MB
and Split size of 512 KB). This is shown by yellow bars. As
the split sizes increase, the disadvantage of bigger number of
I/Os due to the increased sub-packetization diminishes, and
the repair time decreases further (red and blue bars).
In Fig. 3, we compare the repair times for one lost node
of 50 GB with the codes from Examples 2 and 3. The cost
of bigger redundancy with the locally repairable code (10, 6)

Fig. 4. Comparison of repair times for one lost node of 50 GB for a (9, 6)
HashTag code with α = 6, and its locally repairable variants with (l = 2, δ =
2) and (l = 3, δ = 2).
Fig. 2. Experiments in HDFS. Time to repair one lost node of 50 GB with
a (9, 6) code for different sub-packetization levels α. Note that the RS code
for α = 1 is available in the latest release 3.0.0-alpha2 of Apache Hadoop.

(which is also a locally regenerative code since the subpacketization level is α = 9) with (l = 2, δ = 2) (the red bar)
is still not enough to outperform the ordinary (9, 6) HashTag
MSR code (the blue bar). However, paying even higher cost
by increasing the redundancy for the other locally regenerative
code (11, 6) with (l = 3, δ = 2) (the yellow bar) finally
manages to outperform the repairing time for the ordinary
(9, 6) HashTag MSR code.

Fig. 3. Comparison of repair times for one lost node of 50 GB for an ordinary
(9, 6) HashTag MSR code (α = 9), and its locally regenerative variants with
(l = 2, δ = 2) and (l = 3, δ = 2).

The situation of comparing the slightly less optimal (9, 6)
HashTag code with α = 6 with its locally repairable variants
with (l = 2, δ = 2) and (l = 3, δ = 2) is different, and
this is presented in Fig. 4. In this case, all variants of locally
repairable codes outperform the original HashTag code, i.e.
they repair a failed node in shorter time than the original
HashTag code from which they were constructed.
VI. C ONCLUSIONS
We constructed an explicit family of locally repairable
and locally regenerating codes. We applied the technique of
parity-splitting on HashTag codes and constructed codes with
locality. For these codes we showed that there are two ways
to repair a node (repair duality), and in practice which way
is applied depends on optimization metrics such as the repair
bandwidth, the number of I/O operations, the access time for

the contacted parts and the size of the stored file. Additionally,
we showed that the size of the finite field can be slightly lower
than the theoretically obtained lower bound on the size in
the literature. We hope that this work will inspire a further
theoretical analysis for obtaining new lower bound.
R EFERENCES
[1] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE Trans.
Inf. Theory, vol. 56, no. 9, Sept. 2010, pp. 4539–4551.
[2] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of
codeword symbols,” IEEE Trans. on Inf. Theory, vol. 58, no. 11, 2012,
pp. 6925–6934.
[3] F. E. Oggier and A. Datta, “Self-repairing homomorphic codes for
distributed storage systems,” in INFOCOM, 2011, pp. 1215–1223.
[4] D. Papailiopoulos, J. Luo, A. Dimakis, C. Huang, and J. Li, “Simple
regenerating codes: Network coding for cloud storage,” in IEEE INFOCOM, 2012, pp. 2801–2805.
[5] K. Kralevska, D. Gligoroski, and H. Øverby, “General sub-packetized
access-optimal regenerating codes,” IEEE Communications Letters,
vol. 20, no. 7, July 2016, pp. 1281–1284.
[6] K. Kralevska, D. Gligoroski, R. E. Jensen, and H. Øverby, “Hashtag erasure codes: From theory to practice,” arXiv preprint, vol.
abs/1609.02450, 2016.
[7] C. Huang, M. Chen, and J. Li, “Pyramid codes: Flexible schemes to
trade space for access efficiency in reliable data storage systems,” Trans.
Storage, vol. 9, no. 1, Mar. 2013, pp. 3:1–3:28.
[8] C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and
S. Yekhanin, “Erasure coding in windows azure storage,” in USENIX
Annual Technical Conference, 2012, pp. 15–26.
[9] M. Sathiamoorthy, M. Asteris, D. S. Papailiopoulos, A. G. Dimakis,
R. Vadali, S. Chen, and D. Borthakur, “XORing elephants: Novel erasure
codes for big data,” Proc. VLDB Endow., vol. 6, no. 5, 2013, pp. 325–
336.
[10] K. Kralevska, D. Gligoroski, and H. Øverby, “Balanced locally repairable codes,” in Int. Sym. on Turbo Codes and Iterative Inf. Processing (ISTC), Sept 2016, pp. 280–284.
[11] A. S. Rawat, O. O. Koyluoglu, N. Silberstein, and S. Vishwanath,
“Optimal locally repairable and secure codes for distributed storage
systems,” IEEE Trans. on Inf. Theory, vol. 60, no. 1, 2014, pp. 212–236.
[12] G. M. Kamath, N. Prakash, V. Lalitha, and P. V. Kumar, “Codes with
local regeneration and erasure correction,” IEEE Trans. on Inf. Theory,
vol. 60, no. 8, Aug 2014, pp. 4637–4660.
[13] I. Ahmad and C. C. Wang, “When locally repairable codes meet
regenerating codes - what if some helpers are unavailable,” in IEEE
Int. Symp. on Inf. Theory (ISIT), June 2015, pp. 849–853.
[14] T. Ernvall, T. Westerbck, R. Freij-Hollanti, and C. Hollanti, “A connection between locally repairable codes and exact regenerating codes,” in
IEEE Int. Symp. on Inf. Theory (ISIT), July 2016, pp. 650–654.
[15] M. Xia, M. Saxena, M. Blaum, and D. A. Pease, “A tale of two erasure
codes in HDFS,” in 13th USENIX Conference on File and Storage
Technologies (FAST), 2015, pp. 213–226.
[16] T. White, Hadoop: The definitive guide. O’Reilly Media, Inc., 2012.

