26-12-2012, 02:04 PM
An Experimental Study of Data Migration Algorithms
1An Experimental Study.pdf (Size: 210.85 KB / Downloads: 29)
Abstract.
The data migration problem is the problem ofc omputing a
plan for moving data objects stored on devices in a network from one configuration
to another. Load balancing or changing usage patterns might
necessitate such a rearrangement ofda ta. In this paper, we consider the
case where the objects are fixed-size and the network is complete. We
introduce two new data migration algorithms, one ofwh ich has provably
good bounds. We empirically compare the performance of these
new algorithms against similar algorithms from Hall et al. [7] which have
better theoretical guarantees and find that in almost all cases, the new
algorithms perform better. We also find that both the new algorithms
and the ones from Hall et al. perform much better in practice than the
theoretical bounds suggest.
Introduction
The performance of modern day large-scale storage systems (such as disk farms)
can be improved by balancingt he load across devices. Unfortunately, the optimal
data layout is likely to change over time because of workload changes, device
additions, or device failures. Thus, it may be desirable to periodically compute
a new assignment of data to devices [3,5,6,11], either at regular intervals or on
demand as system changes occur. Once the new assignment is computed, the
data must be migrated from the old configuration to the new configuration.
This migration must be done as efficiently as possible to minimize the impact
of the migration on the system. The large size of the data objects (gigabytes
are common) and the the large amount of total data (can be petabytes) makes
migration a process which can easily take several days.
Indirect Migration without Space Constraints
We begin with a new algorithm, Max-Degree-Matching which uses at most 2n/3
bypass nodes and always attains an optimal Δ step migration plan without space
constraints. Max-Degree-Matching works by sending, in each stage, one object
from each vertex in the demand graph that has maximum degree. To do this,
we first find a matchingwhic h matches all maximum-degree vertices with no
out-edges. Next, we match each unmatched maximum-degree vertex up with a
bypass node. Finally we use the general matching algorithm [8] to expand this
matchingto a maximal matching and then send every edge in this new expanded
matching. The full algorithm is given in Appendix A.1; a proof of the following
theorem is given in [1].
Results on the Load-Balancing Graphs
Graph Characteristics
Detailed plots on the characteristics of the load-balancing graphs are given in [1]
and are summarized here briefly. We refer to the sets of graphs generated by
Hippodrome on the first and second device type as the first and second set
respectively and the sets of graphs generated with the TPC-D method for the
first and second device types as the third and fourth sets.
The number of nodes in each graph is less than 50 for the graphs in all sets
except the third in which most graphs have around 300 nodes. The edge density
for each graph varies from about 5 for most graphs in the third set to around 65
for most graphs in the fourth set. The Δ value for each graph varies from about
15 to about 140, with almost all graphs in the fourth set having density around
140.
Performance
Figure 1 shows the performance of the algorithms on the load-balancing graphs
in terms of the number of bypass nodes used and the time steps taken. The x-axis
in each plot gives the index of the graph which is consistent across both plots.
The indices of the graphs are clustered according to the sets the graphs are from
with the first, second, third and fourth sets appearingleft to right, separated by
solid lines.
Time Steps Needed
For General and Regular Graphs, the migration plans Greedy-Matching found
never took more than Δ + 1 time steps. Since the other algorithms we tested
are guaranteed to have plans taking less than Δ + 3, we present no plots of
the number of time steps required for these algorithms on General and Regular
Graphs.
As shown in Figure 3, the number of stages used by Greedy-Matching for
Zipf Graphs is significantly worse than for the other types of random graphs. We
note however that it always performs better than 4-factoring direct. The first
plot shows that the number of extra stages used by Greedy-Matching for Zipf
Graphs with minimum degree 1 varies from 2 to 4 as the number of nodes varies
from 100 to 800. The second plot shows that the number of extra stages used
by Greedy-Matching for Zipf Graphs with 146 nodes varies from 1 to 11 as the
minimum degree of the graphs varies from 1 to 10. High density Zipf graphs are
the one weakness we found forGreedy-Matching.
Theory versus Practice
In our experiments, we have found that not only are the number of bypass nodes
required for the types of graphs we tested much less than the theoretical bounds
suggest but that in addition, the rate of growth in the number of bypass nodes
versus the number of demand graph nodes is much less than the theoretical
bounds. The worst case bounds are that n/3 bypass nodes are required for 2-
factoring and 4-factoring indirect and 2n/3 for Max-Degree-Matching but in most
graphs, for all the algorithms, we never required more than about n/30 bypass
nodes.
Conclusion
We have introduced two new data migration algorithms and have empirically
evaluated their performance compared with two algorithms from [7]. The metrics
we used to evaluate the algorithms are: (1) the number of time steps required to
perform the migration, and (2) the number of bypass nodes used as intermediate
storage devices. We have found on several types of random and load-balancing
graphs that the new algorithms outperform the algorithms from [7] on these two
metrics despite the fact that the theoretical bounds for the new algorithms are
not as good. Not surprisingly, we have also found that for all the algorithms
tested, the theoretical bounds are overly pessimistic. We conclude that many of
the algorithms described in this paper are both practical and effective for data
migration.
There are several directions for future work. Real world devices have different
I/O speeds. For example, one device might be able handle sending or receiving
twice as many objects per stage as another device. We want good approximation
algorithms for migration with different device speeds. Also in some important
cases, a complete graph is a poor approximation to the network topology. For
example, a wide area network typically has a very sparse topology which is more
closely related to a tree than to a complete graph. We want good approximation
algorithms for commonly occuring topologies (such as trees) and in general for
arbitrary topologies. Saia [10] gives some preliminary approximation algorithms
for migration with variable device speeds and different network topologies.