Information Technology Reference
In-Depth Information
next section, we relax the streaming load balance constraint to further reduce the reorganization
overhead.
15.3.3 Multi-Row-Permutated Data Reorganization
While perfect streaming load balance is desirable, the cost of data reorganization, which
itself consumes system resources, can still be substantial. Depending on the particular system
configuration (e.g., disk throughput, network bandwidth, system utilization, etc.), it may be
desirable to trade off some streaming load balance to further reduce the data reorganization
overhead.
By relaxing the streaming load balance constraint, we generalize the row-permutated data
reorganization algorithm into a multi-row-permutated data reorganization (
m
-RPDR) algo-
rithm, which also subsumes the original RPDR as the special case 1-RPDR. In
m
-RPDR we
process the media blocks
m
groups at a time. Moreover, we redefine node overflow to occur
only if more than
m
blocks from the
m
groups are stored in the same node. Similarly, a node
underflows if it stores fewer than
m
blocks from the
m
groups under consideration.
Figure 15.7 illustrates the reorganization of the first two groups using 2-RPDR. In this
example, nodes
n
0
and
n
2
overflow and so we move media data blocks
v
1
,
4
to
n
4
to
restore streaming load balance. Comparing to reorganizing the same two groups using 1-RPDR
(Figure 15.4 and Figure 15.5), the number of block movements is reduced from 3 to 2. The
trade-off is in streaming load balance. As shown in Figure 15.7 node
n
4
stores media data
blocks
v
1
,
3
and
v
0
,
4
. Thus, if the system sends a group
of
N
data blocks in each service round, then in the first service round node
n
1
will need to
send two data blocks while node
n
4
will be idle, and vice versa in the second service round.
v
1
,
3
and
v
1
,
4
, and node
n
1
stores blocks
v
0
,
1
and
n
0
,
n
2
overflow while
n
4
underflows.
Blocks
v
1,3
and
v
1,4
are moved to
n
4
.
v
0,0
v
0,1
v
0,3
v
0,2
v
0,0
v
0,1
v
0,3
v
0,2
v
1,3
2
-RPDR
v
1,2
v
0,4
v
1,0
v
1,1
v
1,2
v
0,4
v
1,0
v
1,1
v
1,4
v
1,3
v
2,0
v
1,4
v
2,1
v
2,0
v
2,1
Re-organize
v
2,3
v
2,2
v
2,4
v
3,0
v
2,3
v
2,
2
v
2,4
v
3,0
v
3,1
v
3,2
v
3,4
v
3,3
v
3,1
v
3,2
v
3,4
v
3,3
.
.
.
.
.
.
.
.
n
0
n
1
n
2
n
3
n
4
n
0
n
1
n
2
n
3
n
4
Group 0-1 before reorganization
Group 0-1 after reorganization
Figure 15.7
Reorganizing group 0 and 1 using the 2-RPDR algorithm
Search WWH ::
Custom Search