論文 / 著書情報
Article / Book Information
Title

Comparison of Replica Assisting and Speed Adjustment for ServiceawareHorizontal Data Migration on Autonomous Disks

Author

Dai Kobayashi, Haruo Yokota

Journal/Book name

Proceedings of the Second IEEE International Conference on Digital
Information Management, , , pp. 539-544

Issue date2007, 10

DOI

http://dx.doi.org/10.1109/ICDIM.2007.4444279

URL

http://www.ieee.org/index.html

Copyright(c)2007 IEEE. Personal use of this material is permitted. Permission
from IEEE must be obtained for all other users, including
reprinting/republishing this material for advertising or promotional
purposes, creating new collective works for resale or redistribution toservers or lists, or reuse of any copyrighted components of this work inother works.

Note

このファイルは著者（最終）版です。
This file is author (final) version.

Powered by T2R2 (Science Tokyo Research Repository)

Comparison of Replica Assisting and Speed Adjustment for Service-aware
Horizontal Data Migration on Autonomous Disks
Dai Kobayashi
Tokyo Institute of Technology
Japan Society for the Promotion of Science
daik@de.cs.titech.ac.jp

Abstract
We have previously proposed Autonomous Disks System
as a dependable and high-performance networked parallelstorage system. The system has function of load balancing
by online horizontal data migration. However, the migration causes a reduction of system availability by insensitively utilizing of system resources for massive data transfers. Thus we have also proposed Replica-assisted Migration, which solve the problem by using replica data for data
redundancy. In this paper we show the efﬁciency of thismethod with experimental results on simulation program,comparing to speed adjusting method which is widely used
for service-aware data migration.

1

Introduction

We have previously proposed Autonomous Disks as adependable and high-performance networked parallel storage system. The system comprises many intelligent storage
nodes and high-speed local network. The node contains not
only hard disk drive(s) but also cache memory and CPU.
Data is distributed, replicated, and stored in each storage
node, and is partitioned into short segments such as ﬁles,
extents, pages, or blocks.
The system has function of load balancing by online
horizontal data migration. Horizontal data migration is amethod to balance workloads for removing hot spots inwhich heavy load is concentrate on parallel storage systems
and distributed databases [4, 11]. Transferring data fromhot spots to unused storage nodes, the system keeps performance of accesses on all data even when workload trendchanges.
However, data migration causes temporary performancedegradation since data transfer often consumes system resources such as I/O bandwidth and network bandwidth[3, 9, 14]. The storage nodes with heavy accesses need toHaruo Yokota
Tokyo Institute of Technology
yokota@cs.titech.ac.jp

serve accesses of both services and data migration, although
the storage node decreases its performance extremely withexcessive load. Saturated I/Os such as disks or networksof partial storage nodes make a system difﬁcult to guarantee its performance. On the other hand, data migration forload balancing should be performed quickly because slow
migration which cannot follow changes in access trends, results in access concentrations that the system should haveavoided. Therefore, using the sensitive speed adjustment
which is commonly used for data migration in hierarchical,
or vertical, storage [3, 9, 14] is discouraged.
We have also proposed adaptive Replica-assisted Migration (RM), which reduces and distributes the load causedby data migration by using replica data for data redundancy [6]. The method reduces the amount of transferreddata and provides a source node selection by using replica
data location. The method also has ability to keep performance of each storage node by forwarding moderate ratioof accesses to replicas. A notable point of the method isthat the method needs not to decrease data migration speed.
In this paper we show the efﬁciency of the method withexperimental result on simulation program, comparing tospeed adjust method which is widely used for service-aware
data migration. We ﬁrst evaluate the methods with Zipfbased synthetic workloads. The results show that the proposed method indicates performance gain and the gain isrelated to migration duration. We also use Web-based real
workload for evaluating applicability of the methods. The
results also show the ascendancy of the proposed method.
It is because the migration speed with proposed method isfaster than speed of workload trend evolution, while thatwith speed-adjust or normal migration lose against workload trend.
The remainder of this paper is organized as follows. We
describe the Autonomous Disks System in Section 2. In
Section 3, we summarize the RM migration we have previously proposed. In Section 4, we describe the experimental
environment. Sections 5 and 6 give experimental results
and discuss using the simulation program with a synthetic                         migration source node      

 

pri 2

pri 3

pri 4

bak n

bak 2

bak 3

disk2

disk3

disk4
N-pattern

We have previously proposed Autonomous Disks [12]as
dependable and high-performance networked parallel storage systems. This adopts Primary-backup one-copy replicas[2] and the Chained Declustering replica-placement strategy [5], in which each node has replicas of one neighbor node and locates a replica of its stored data in anotherneighbor to achieve greater reliability. It utilizes Fat-Btree[13], which is a kind of distributed B+ -Tree with no single control point, as the storage virtualization structure. It
also utilizes a range partitioning data distribution strategy,
whereby each storage node contains data with an assigned
ﬁeld range. Items of stored data have unique identiﬁers
and are sorted by the identiﬁer. Each node has a range ofidentiﬁers. data are stored in the node that has range corresponding to the identiﬁer. Figure 1 shows the combinationof Chained Declustering and range partitioning.
The Autonomous Disks system has function for load balancing by data migration that is executed by communicationof intelligent controllers on each storage nodes. All intelligent storage nodes on the system record degree of current
load, and the planning task to decide a migration strategy
is executed on a coordinator node, which aggregates thecurrent workload information for all nodes. Storage nodes
execute the following tasks at regular predeﬁned time intervals. Firstly, a node is picked out to be coordinator andeach node send its current load information to the coordinator. Then the coordinator node calculates the average load
degree and creates a migration quantity list that includes information for each node on how much data or load should
migrate to another node. To complete the strategy, eachstorage node transfers the speciﬁed quantity of data to thespeciﬁed nodes.

pri 3

pri 4

bak n

bak 2

bak 3

disk2

disk3

disk4

load
(read)

load(write)

pri 2

pri 3

pri 4

bak n

bak 2

bak 3

disk2

disk3

disk4

Figure 2. Two data transfer source nodes. The
coordinator node can select the source nodefrom prii on diski or baki on diski+1 when
migrating datai

workload and a real workload, respectively. The ﬁnal section contains our conclusions.

Autonomous Diskspri 2S-pattern 

Figure 1. Chained Declustering and range
partitioning2

load(write)load(read)

3

Replica-assisted migration

We use replica data for data redundancy for realizing
data migration and access quality simultaneously. We ﬁrst
reduce the quantity of transferred data and select the migration source node by using replica location. We also use
replicas for access services, by forwarding partial accessesof primary data to replicas. An advantage of our method
is that the system can migrate a substantial quantity of data
even if the source node has already become a hot spot without decrease migration speed.

3.1

Migration source selection using replicas

Multiple replica locations make selection of the migration source node possible, which enables allocation of migration load to less accessed nodes.
The migration destination node is restricted to either theright neighbor node, which stores data with higher identiﬁers, or the left neighbor node, which has lower identiﬁers.
Therefore, using replicas on the right node, the migration
can select the data transfer source node as either primarydata or replica data. We call the former the S(Self)-pattern
and the latter the N(Neighbor)-pattern. Figure 2 shows theS- and N-patterns of right migration.
When data migration is required, the coordinator canselect the colder migration source node from the S- or Npattern using aggregated workload information.

3.2

Access forwarding to replicas

Partial read accesses for data stored in a hot spot nodethat is also a source node for data migration can be forwarded to nodes that store replicas of the primary data to9 :;:=<> ?2@:;> A2BDC5E:%FGH A :I9KJ :@;> :IH5:ILIL ENM,M6O AP@QR:@9 > B5?

Table 1. Simulation Parameters      

 

 

 

             

 


 

 

        !54 -6 % /3.# 0* && &7#%  &'"8&  / -60!&Simulation Parameter

Value

Rotational speed (RPM)# of surfaces# of sectors per cylinder
Seek time (msec)
Buffer size (KB)7200
64320 – 9000
0.8 – 15.1
8196

Disk node
Cache size (MB)Network bandwidth (Mbps)

4
512
800

    !"!#%$&'"(*)+', -+ .,  /0    !"!#%$&'"(*)+$& 1% !&$2 /3!4 &0, $Figure 3. A concept of access forwarding for
migration load

avoid performance degradation caused by the data migration. Therefore, data replacement can be executed even if
a hot spot has appeared. Figure 3 illustrates the concept of
the partial access forwarding.
The number of read accesses forwarded to replicas isimportant to provide stable data transfer services to bothclients and data migration processes. In other words, themethod calculates the ratio that maximizes the resources
for data migration at the data migrating node while staying
within the maximum storage node performance limits. The
limiting load values for maintaining tolerable availability ofa system are estimated before running the system, from service level agreements, speciﬁcations of disks, networks, andthe brief characteristics of workload trends on nodes, suchas cache hit ratios and request sizes.
The access forwarding ratio ri on node i is calculated at
the coordinator node from aggregated current workload information, which includes the load quantity and the write
request ratio, and is communicated to node i . Our method
executes the following tasks in addition to the regular migration tasks described in Section 2. Firstly, the coordinatorcalculates the access forwarding ratios ri , as well as calculating the quantity of migrating load, using the load degree
aggregated from all nodes. Secondly, the coordinator sends
ri to node i for all i and the nodes each apply their own
ri . Thirdly, nodes migrate stored data to other nodes, as
required. At this point, read accesses to the nodes are partially forwarded to the nodes that store replicas according
to each forwarding ratio ri . When each node has ﬁnishedmigrating the speciﬁed quantity of data, it sets its ri to zero.
Detailed information of algorithm for calculating ri is de-scribed in [6].
Access forwarding to nodes storing replicas decreases
the hit ratios of cache memory on each storage node because
both the primary and replica data of other nodes may be
stored in the same cache and will compete for cache space.
In this paper, we use a method for choosing forwarded accesses that uses the hit ratios of each cache to estimate thepopularity of data at low cost [7]. It helps the replication to
use the limited cache space efﬁciently if accesses for data
in less demand are forwarded. In addition, it also strictly
distinguishes between primary accessed data and replica accessed data to avoid competition for cache space.

4

Experiment Environment

We observed and evaluated the behavior of our methodwith the Autonomous Disks System, using a Zipf-based
synthetic workload and a ﬁle server workload with a simulation program. In this section, we describe the simulation
environment and the workloads. The results of experimentswith the synthetic workload are given in the next section
and those with the real workload are given in Section 6.
We used a queuing network-based storage system simulation program. The behavior of the hard disk drives in thesimulation was calculated with parameters from an HGST
Deskstar T7K500 speciﬁcation [10]. Table 1 gives the simulation parameters.
We implemented the data migration strategy described in
Section 2. The load value was deﬁned as the summation ofrequest sizes in the previous 600 seconds. The sizes were
modiﬁed by using the storage node performance observedin preparatory experiments, giving the smaller size a relatively larger load value per unit of size.
In each experiment, we compared three methods: data
migration without performance-aware control (NORMAL),
RM method, and the speed adjust method. We implemented
Aqueduct [9] as speed adjust method. It adjust migration
speed adaptively by using observed response time on eachnode, respectively.

Table 2. Speciﬁcation of experiments withsynthetic workload
Workload parameter

Value

Time span (hours)
Total ﬁle size (GB)# of ﬁles in total

2
100 × 2 (Primary & Backup)
100,000 (1MB each)“”

Access distributions

Zipf f (k; s, N ) = PN1/k1/ns
n=1

Zipf exponent s

1.5, 1.2

Duration of first migration [sec]8000

Ratio of accesses expiring 0.2 sec

0.5

5000
4000
3000
2000
1000
0

50

100
150
200
250
Request arrival rate [req/sec]

300

Figure 5. Duration of ﬁrst data migration (Zipfparameter s=1.5)

0.3

0.2

0.1

0
0

50

100
150
200
Request arrival rate [req/sec]

250

300

Figure 4. The ratio of accesses expiring within
0.2 sec(Zipf parameter s=1.5)

5

6000

0

speed adjust
normalRM

0.4

speed adjust
normalRM

7000

Synthetic data

First, we observed the behavior of each method with asynthetic workload. The workload speciﬁcation is given in
Table 2. The workload was generated by using a Zipf-based
access distribution and a Poisson arrival distribution. The
Zipf distribution is described in the table, where f is theratio of accesses to a ﬁle ranking k in N ﬁles and s is aparameter indicating the degree of skew. We set the workload trend at 10 minutes after the start of the simulation bychanging the seed of a random value generator for a shufﬂe function that decided the target ﬁle for each access, followed by migration start at 5 minutes after the workloadchange.
Figure 4 shows the number of access requests expiring
within 0.2 seconds, as an agreed service level. The 0.2second value is about ten times the latency under low load.
The horizontal axis indicates scale of workload quantity.
While the requests for NORMAL and speed adjust data migration increased sharply, those for the two RM methods
increased at a slower pace, even for heavier workloads.

The performance degradation is well related to a data migration duration. Figure 5 shows duration from when theﬁrst data migration occurred to when the migration ﬁnish totransfer required quantities of data in same experiments as
Figure 4. The ﬁgure 5 shows that the duration with bothspeed adjust method and normal migration increases extremely when request arrival rate increases. It is a result ofthat data migration and accesses for storage services compete for resources on hot spots. On the other hand, thatof the RM method increases slower than the others. It iseffect of access forwarding and migration source node selection that move trafﬁc of migration to replica nodes thathas enough resources.
When degree of access distribution is less sharp, the effect of RM becomes smaller because usable resources on
replica nodes relatively small. It is observed in ﬁgure 6 thatis the number of expiring accesses when Zipf parameter s
set to 1.2 that is less sharp than s = 1.5. Although theﬁgure shows a same characteristic as ﬁgure 4, performancegain by RM method is 33% that is less than 38 % on theexperiment with s = 1.5.

6

Web server data

In this section, we evaluate the efﬁciency of methods byusing access trace logs of large scale web server as more
real workload. Actual workloads is much complex thanthat of previous because it has quick and large evolution,or concept drift, and also has various size of requests. The
properties lead to an increase of error in estimated valueof load quantities. We use a workload generated by partial
terms of access logs of FIFA WorldCup98 Ofﬁcial Web [8].

speed adjust
normal
RM

0.6
0.5
0.4
0.3
0.2
0.1
0
0

50

100
150
200
250
Request arrival rate [req/sec]

300

350

Ratio of accesses expiring the response tim e

Ratio of accesses expiring 0.2 sec

0.7

workload parametervalue

time span# of requests
read:write
total ﬁle size

2 hours
5,000,000
10:0
430MB ×h× 2(Primary & Backup)
21000
277MB ×h
6300

# of total ﬁlesaccessed ﬁle size
# of accessed ﬁles

The workload speciﬁcation is given in Table 3. More information of the workload is on [1]. The period on workload
used in the experiment has two major evolution of accesstrend. Thus the experiment consists two large load balancing; from initial state to stationary state, and from stationary state to state after trend evolution. Results of NORMAL and RM include two migrations. However, that ofspeed-adjust method includes only latter migration because
speed-adjust stop migration tasks if speed-adjust is activefrom initial state, or extremely skewed state. Request sizesof the workload in each experiment multiplied by h which
is deﬁned as a load parameter for expressing various quantities of workload.
Figure 7 shows the ratio of the number of access requests
expiring within 4 seconds and 64 seconds, as an agreed service level, for the experiments with various load parameterh. In the ﬁgure, the horizontal axis indicates the load parameter h.
The result shows the efﬁciency of the RM method with

RM-expire64[s]RM-expire4[s]normal-expire64[s]normal-expire4[s]speed-adjust-expire64[s]speed-adjust-expire4[s]

0.5
0.4
0.3
0.2
0.1
0
0

Figure 6. The ratio of accesses expiring within
0.2 sec(Zipf parameter s=1.2)

Table 3. Speciﬁcation of experiments with real
server workload

0.6

10

20
30
40
50
60
h: Enlargement raio of filesize

70

Figure 7. The ratio of accesses that expiring
within four second and 64 second with Webbased workload

real workload clearly. Contract to the result of synthetic
one, all method indicates same performance on the resultwith h lower than 60. It is because there are few accessconcentration that decrease node performance on the experiments. Thus, speed-adjust method hardly decrease migration speed on it. However, speed-adjust and normal
method indicates signiﬁcant performance degradation whenh equals 65. Analytic result of simulation log shows that thedegradation was caused by data location change slower thanaccess trend change. The situation that data migration andaccesses for storage services compete for resources on hot
spots results in the decrease of the migration speed. On theother hand, RM method can execute data migration quickly
because the method uses resources on replica node.
The results indicate that the important things for horizontal migration and performance keeping is quick data migration. The proposed method have ability to realize it andthe speed adjust method does not.

7

Conclusions

In this paper, we analyzed and evaluated Replica-assisted
migration we have proposed, focusing on migration duration. The method reduces the amount of data transferredand provides a source node selection by using replica data
location. The method also achieves to keep performance ofeach storage node by forwarding moderate ratio of accesses
to replicas.
We ﬁrst experimented with a Zipf-based synthetic workload using several parameter values, and showed that themethod can maintain availability and migrate required data

quickly. The second experiment used a workload generated
by real large-scale Web server trace logs, and showed thatthe method can work better with practical workload trends
that with speed-adjust method. The two experimental results shows that it is signiﬁcant for keeping service performance with horizontal data migration to transfer required
quantity of data as quick as possible.
Our current issues are treatment of write requests. Our
previous work [6] shows that one of our method to provide migration source node selection worked well with theworkload, while the other of our method to forward partial
accesses to replicas made no sense because of high skew
access distribution and high update load. We consider using the concept of neighbor WAL method for eliminating
quantities of load on replicas caused by write operations.
Another future work will include detailed analysis andevaluation of the method under various workloads with different characteristics, such as OLAP, video servers, and scientiﬁc applications. Analysis will be required not only ofthe method itself but also of underlying techniques such as
the migration strategy and the workload estimation method.

8

Acknowledgments

This work was partially supported by Japan Science andTechnology agency via CREST program, Japan Society for
the Promotion of Science via Grant-in-aid for JSPS Fellows,
Storage Research Consortium, MEXT of Japanese Government via Grant-in-Aid for Scientiﬁc Research on Priority
Areas, #18049026 and the MEXT 21st Century COE Program.

References[1] M. Arlitt and T. Jin. Workload characterization of the 1998
world cup web site. Technical Report HPL-1999-35R1,
Hewlett-Packart Laboratories, Oct. 1999.
[2] P. A. Bernstein and N. Goodman. An algorithm for
concurrency control and recovery in replicated distributed
databases. ACM Trans. Database Syst., 9(4):596–615, Dec.
1984.
[3] K. Dasgupta, S. Ghosal, R. Jain, U. Sharma, and A. Verma.
Qosmig: Adaptive rate-controlled migration of bulk data instorage systems. In the 21st International Conference on
Data Engineering (ICDE2005), pages 816–827, 2005.
[4] H. Feeliﬂ, M. Kitsuregawa, and B. Ooi. A fast convergence technique for online heat-balancing of btree indexed
database over shared-nothing parallel systems. In 11th Int’l
Conf. on Database and Expert Systems Applications, pages
846–858, Sep 2000.
[5] H.-I. Hsiao and D. J. DeWitt. Chained declustering: A newavailability strategy for multiprocessor database machines.
In Proceedings of the Sixth International Conference on
Data Engineering, pages 456–465, Los Angeles, CA, Feb.
1990. IEEE Computer Society.

[6] D. Kobayashi, R. Taguchi, and H. Yokota. An experimental evaluation of the adaptive replica-assisted migration forparallel storage systems. In The Third IEEE International
Workshop on Databases for Next-Generation Researchers(SWOD 2007), 2007.
[7] D. Kobayashi, A. Watanabe, R. Taguchi, T. Uehara, andH. Yokota. An efﬁcient access forwarding method based oncaches on storage nodes. In International Special Workshop
on Databases For Next Generation Researchers (SWOD2005) In Memoriam of Prof. Kambayashi, pages 188–191,
2005.
[8] L. B. N. Laboratory. The internet trafﬁc archive. http://ita.ee.lbl.gov/.
[9] C. Lu, G. A. Alvarez, and J. Wilkes. Aqueduct: online data
migration with performance guarantees. In Conference on
File and Storage Technologies (FAST’02), pages 219–230,
Monterey, CA, Jan. 2002.
[10] H. G. S. Technologies. Deskstar T7K500 Hard Disk Drive
Speciﬁcation. http://www.hitachigst.com, ver. 1.2 edition,
2006.
[11] G. Weikum, A. Mönkeberg, C. Hasse, and P. Zabback. Selftuning database technology and information services: fromwishful thinking to viable engineering. In VLDB, pages 20–
31, 2002.
[12] H. Yokota. Autonomous Disks for Advanced Database Applications. In Proc. of International Symposium on Database
Applications in Non-Traditional Environments (DANTE’99),
pages 441–448, Nov. 1999.
[13] H. Yokota, Y. Kanemasa, and J. Miyazaki. Fat-Btree: An
Update-Conscious Parallel Directory Structure. In Proc. of
the 15th Int’l Conf. on Data Engineering, pages 448–457,
1999.
[14] J. Zhang, P. Sarkar, and A. Sivasubramaniam. Achieving
completion time guarantees in an opportunistic data migration scheme. SIGMETRICS Perform. Eval. Rev., 33(4):11–
16, 2006.