Information Technology Reference
In-Depth Information
h
) and
h
be the number of data nodes and redundant nodes in the system respec-
tively. Assuming the number of redundant nodes in the system is fixed, then we can apply the
(
N
Let (
N
−
,
h
)-RSE code to compute the
h
redundant data blocks in each group of (
N
−
h
) data blocks
using
f
1
,
1
f
1
,
2
f
1
,
3
...
f
1
,
N
−
h
d
i
,
0
d
i
,
1
.
d
i
,
N
−
h
−
1
f
2
,
1
f
2
,
2
f
2
,
3
...
f
2
,
N
−
h
F
·
D
=
.
.
.
.
f
h
,
1
f
h
,
2
f
h
,
3
...
f
h
,
N
−
h
11 1
...
1
d
i
,
0
d
i
,
1
.
d
i
,
N
−
h
−
1
12 3
...
N
−
h
=
(15.2)
.
.
.
.
12
h
−
1
3
h
−
1
...
(
N
−
h
)
h
−
1
=
c
i
,
0
c
i
,
1
.
c
i
,
h
−
1
=
C
where the
F
,
D
, and
C
are the Vandermonde matrix [4], the media data vector, and the
redundant data vector respectively; and
d
i
,
j
,
c
i
,
k
represent data block
j
(
j
=
0
,
1
,...,
N
−
h
−
1) and redundant block
k
(
k
=
0
,
1
,...,
h
−
1) of parity group
i
. Elements in
F
are
constants computed from
f
i
,
j
=
j
i
−
1
. Note that the matrix multiplication in equation (15.2) is
computed over Galois Fields of 2
w
where
N
<
2
w
. For example, by setting
w
=
16, then the
code can support up to 65,535 nodes.
Reconsider the generation of a redundant data block before and after addition of one data
node in Figure 15.11 and Figure 15.12 respectively. We can observe that in many cases,
the reorganized parity group still comprises some data blocks from the original parity group
before reorganization. For example, in expanding a system from
N
nodes to
N
+
1 nodes,
the first parity group will be reorganized from the composition of
{
v
0
,v
1
,...,v
N
−
h
−
1
}
to
{
v
0
,v
1
,...,v
N
−
h
−
1
,v
N
−
h
}
v
N
−
h
. This means that the
resultant matrix computations in equation (15.2) will differ by only one variable in the data vec-
tor. This raises the question of whether we can reuse the original redundant data in computing
the new redundant data, discussed next.
Consider the original configuration in Figure 15.11. The first two redundant data in redundant
node
r
1
, denoted by
c
0
,
1
and
c
1
,
1
, are computed from
, which differs by only one data block
3
c
0
,
1
=
f
2
,
j
+
1
v
j
(15.3)
j
=
0
and
7
c
1
,
1
=
f
2
,
j
−
4
+
1
v
j
(15.4)
j
=
4
respectively according to equation (15.2).
Search WWH ::
Custom Search