Information Technology Reference
In-Depth Information
. . .
RSE
c
i
,
0
c
i
,
1
c
i
,
h
-
1
Data
Central archive server computes all redundant
data and distributes them to redundant nodes.
. . .
d
N
−
h
−
1
. . .
d
0
d
1
r
0
r
1
r
h
-
1
Figure 15.16
Update of multiple redundant nodes directly by a central archive server
15.5.2 Sequential Redundant Data Update
When updating multiple redundant nodes in SRDU, we observe that the data blocks required
are in fact the same for all the redundant nodes. For example, consider the computation of the
redundant block
c
0
,
j
in the redundant node
r
j
. The equation for computing
c
0
,
j
is
c
0
,
j
=
c
0
,
j
+
f
j
+
1
,
5
v
4
+
f
j
+
1
,
6
v
5
(15.15)
where
v
5
are the required data blocks and are the same for all
j
's.
Therefore, if the data blocks
v
4
and
v
5
have already been sent to redundant node
r
k
, then it
can compute partial results for the other redundant nodes:
v
4
and
p
j
=
f
j
+
1
,
5
v
4
+
f
j
+
1
,
6
v
5
,
∀
j
=
k
(15.16)
and then send them to the other redundant nodes
{
r
j
|∀
j
=
k
}
to complete the redundant data
update computation:
c
0
,
j
=
c
0
,
j
+
p
j
,
∀
j
=
k
(15.17)
as shown in Figure 15.17. In this case, the overhead is reduced from sending two data blocks
v
4
and
v
5
to sending just the partial result
p
j
. In general, we always need to send only the
partial results no matter how many data blocks are required. Therefore, the total redundant
data update overhead is equal to the SRDU overhead in updating one redundant node plus the
overhead in transmitting the partial results: (
h
h
)).
Table 15.1 summarizes the total redundant data update overhead of the algorithms discussed
earlier. An important observation is that the overhead is dominated by the overhead in updating
the first redundant node due to the large number of data blocks required to generate the new
redundant data blocks. Once these are cached in the redundant node, new redundant blocks of
other redundant nodes can be computed with much lower overhead.
Consider an example of adding one data node to a system with 199 data nodes. Figure 15.18
plots the total redundant data update overhead versus number of redundant nodes in the system.
−
1)(
B
/
(
N
−
Search WWH ::
Custom Search