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

An Experimental Evaluation of the Adaptive Replica-assisted Migration
forParallel Storage Systems

Author

Dai Kobayashi, Ryo Taguchi, Haruo Yokota

Journal/Book nameProc. of International Special Workshop on Databases For Next
Generation Researchers (SWOD 2007), Vol. , No. , pp.

Issue date2007, 4

DOI

http://dx.doi.org/10.1109/SWOD.2007.353198

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)

An Experimental Evaluation of the Adaptive Replica-assisted Migration for
Parallel Storage Systems
Dai Kobayashi
Tokyo Institute of Technology
Japan Society for the Promotion of Science
daik@de.cs.titech.ac.jp

Ryo Taguchi
Japan Broadcasting Corporation
taguchi.r-cs@nhk.or.jp

Haruo Yokota
Tokyo Institute of Technology
yokota@cs.titech.ac.jp

Abstract
We have proposed a method replica-assisted migrationthat use temporally replica data in other storage nodes during executing data migration to keep both qualities of service accesses and data migration duration. However, wehave not evaluated the method with real workload including update operations. In this paper, we ﬁrst improve themethod and evaluate an efﬁciency of the method under ﬁleserver workloads. Base on the result of it, we also propose Adaptive replica-assisted migration for reduce migration duration.

1. Introduction
Data migration is a method to balance workloads for remove hot spots in which heavy load is concentrate on parallel storage systems and distributed databases [2, 10]. Transferring data from hot spot to unused storage node keep performance of storage systems for changing workloads.
However, data migration causes performance degradation temporarily because data transfer consumes system
resources such as I/O bandwidth and network bandwidth[1, 7, 11]. The storage nodes with heavy accesses needto process accesses for both services and data migration,
though the storage node degredate its performance extremely with excessive load. Saturated I/O such as disks or
networks of partial storage nodes makes a system difﬁcult
to guarantee its performance.
For the problem, we have proposed Replica-assisted migration that reduce and distribute load caused by migration,using replica data for data redundancy. The method reduces
the amount of data transferred and provides a source node
selectability by using replica data location. The method alsoachieves to keep performance of each storage node by forwarding moderate ratio of accesses to replicas.
However, our past studies don’t include enough evaluations. We have indicated the efﬁciency of our method byonly experiments under synthetic workload with only read
operations, while update operations and real workload havean inﬂuence on behavior of the method because of the consistency control and real change of access trend. The evaluation and improvement of the method for real workloadwith update operations is required in order to apply our
method to actual systems.
A purpose of the paper is to show the efﬁciency and applicability of the Replica-assisted Migration on real workloads with update operations. At ﬁrst, In this paper, we
use ﬁle server workload generated by trace logs on actual
shared ﬁle server for evaluate our method. Current ﬁleservers become larger and larger storing enlarged personal
information. So they are one of most signiﬁcant application
for large-scale storage systems The workloads include extremely skew distribution and a half of the loads consists of
update operations.
First, we improve our method for ﬁle server workload.
Then we observe a behavior of our method on simulation
program with workload generated by real ﬁle server tracelogs. Results of the simulation show that providing migration source node selectability can work well, while accessforwarding cannot indicate efﬁciency.
Based on the results, we also propose Adaptive replicaassisted migration that improve the proposed method tocontrol the migration source node adaptively with the loadof the node for reduce migration duration. The experimental results with simulation and real workload indicate that
adaptive method can reduce migration duration in many situations.
The rest of this paper is organized as follows. We de-scribes assumed environment, technology and system organization in 2. In section 3, we summarize Replica-assisted
migration we have proposed. Section 4 describes ﬁle server
I/O and improvement of the proposed method. Section 5
indicate exeprimental results and discussions using simulation program. In section 6, we proposed adaptive replicaassisted migration and show its efﬁciency. In last section
we include our concluding remarks.

appear on systems, the migration cannot make a sense orcannot guarantee the quality of storage systems services.
Although there are many studies on achieve both storage QoS and data migration simultaneously [1, 7, 11], manyof them consider not horizontal migration but vertical one.
Thus, the horizontal migration with speed adjusting makes
no sense because it cannot follow changing speed of workload trend.

2

3

Data migration

Performance of hard disk drives extremely decline when
excessive accesses concentrated on them [8]. Current largescale storage systems consist of a lot of storage nodes withconnecting over high-speed networks. Saturated I/O suchas disks or networks of partial storage nodes make a system
difﬁcult to guarantee its performance. Therefore access load
skew should be balanced over all storage nodes.
Data migration is proposed for the problem. Data relocation by transferring stored data with considering performance of storage node and current workload trend canachieve load balancing on parallel storage systems.

2.1

Migration strategy

We assumed that all intelligent storage nodes record thedegree of current load and planning task is executed on anode, aggregating current workload information. The node
executing planning task, we call coordinator, planed notamount of migrating data but amount of migration load
degree because aggregating workload information of eachdata is much complex.
The nodes execute following tasks at regular time intervals deﬁned in advance. At ﬁrst the nodes pick a node forcoordinator and send the degree of current load on eachnode to coordinator. Then the coordinator node calculates average load degree and make migration amount listthat include information that how much data or load eachnode should migrate to other node. At third, the coordinator node reﬁne the list by multiply speed-factor parameterθ(0 ≤ θ ≤ 1) to prevent overdo. The end of the strategy,
each storage nodes transfer ordered amount of data to ordered nodes.

2.2

A Problem caused by load of data migration

It is signiﬁcant problem that data migration causes performance degradation temporarily. Data migration consumes system resources such as I/O access ability and network transfer bandwidth that services for clients also uses.
The migration causes serious performance degradation on
systems because the migration tends to occur on nodes
when the nodes already become hot spot. So when hot spots

Replica-assisted Migration

We have proposed Replica-assisted migration to achieveboth storage QoS and data migration without slowing migration speed . The rest of the section describes a concept
and summary of the method.

3.1

Concepts

We uses replica data for data redundancy described at
section 2. We ﬁrst reduce the amount of transferred data
and make selectability on migration source node. We also
use replicas for access services, forwarding partial accessesof primary data to replicas. Using replicas not only with
migration but also with regular services is beyond the scopeof this paper, although we discussed the usage in [5] An advantage of our method is that systems can migrate moderateamount of data even if the source node already becomes hot
spot.
Following description of the method and algorithm assume that the systems adopt range-partitioning data placement policy and Chained Declustering replica placement
policy [3] implicitly, although the concept of our method
is applicable to other systems.

3.2

Migration source selectability using replicas

Replicas location make selectability of migration source
node and the selectability make it available to generate migration load on less accessed nodes.
The algorithms implicitly assumed that Chained Declustering replica placement policy and range partitioning data
placement policy. The stored data has unique identiﬁer andsorted the identiﬁer. Each node has range of identiﬁer andequivalent data are stored the node. The range make two
nodes as neighbors.
The migration destination node restricted to which rightneighbor node that store data that has larger identiﬁer or left
neighbor node that store smaller one by range restriction.
Therefore using replicas on right node, the migration canselect data transfer source node from whether primary dataor replica data. We call the former S(Self)-pattern and thelatter N(Neighbor)-pattern. Figure 1 shows the S- and Npattern of right migration.

load(write)load(read)
migration source node

pri 2

pri 3

pri 4

bak n

bak 2

bak 3

disk2

disk3

disk4

pri 2

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

S-patternN-pattern

Figure 1. Two data transfer source node. thecoordinator node can select the source nodefrom prii on diski or baki on diski+1 when
migrating datai
When data migration requires, the coordinator can selectmigration source node from S- or N- pattern with aggregated workload information.

3.3

Access forwarding to replicas

Partial accesses towards data stored in a node which is
hot spot and also be source node of data migration can be
forwarded to nodes that store replicas of the primary data to
avoid causing performance degradation by data migration.
Thus you can execute data replacement even if hot spot has
appeared.
Our method execute following tasks in addition to regular migration tasks described at 2.1 At ﬁrst coordinatorcalculate access forwarding ratio r as well as calculate theamount of migrating load, using load degree aggregatedfrom all nodes. At that point, the coordinator issues orders
to all node to switch replica consistency mode from asynchronous to synchronous one and apply uncommitted update logs, if the system adopt asynchronous replicas. Thenthe coordinator send the r to all nodes and the nodes set eachr to itself. At third, required nodes migrate the stored datato ordered nodes. At that point, accesses to the nodes are
partially forwarded to the nodes that stores replicas based
on r. When the node ﬁnish to migrate ordered amount of
data, the node set own forwarding ratio as zero.
3.3.1

Calcuration of Forwarding Ratio

A coordinator node calculate access forwarding ratio r as
follows. In the discussion, Li (t) is load of primary datastored in node i and LTMP(t) is list of values using temi
porarily in the algorithm.
At ﬁrst, the coordinator picks a node i that total numberof current load of the node LTMP(t) plus migration loadi

LMIG is larger than max processable load per node Lmi .
Then, if forwardable load hi is smaller than the primaryload Li (t), in other word, the node i can forward its load
to other one, LTMP(t) − LMIG is subtracted from LTMP
(t)
i
i
TMP
and added to Li+1 (t) and hi that is forwarding load ofnode i. The calculation involves access forwarding. At thatpoint, if Li+1 (t) that is load of nodes storing replicas of thenodei, we call the node node i + 1, exceeds the max load
Lmi+1 to keep agreed response time, node (i + 1) forwards
the access load to node (i + 2), according similar to theway described as above. The algorithm terminate when anode j that satisfy hj > Lj (t) exists or all node i satisfy
LTMP(t) < Lmi , in other word, no update of hi occur.
i
The output of the algorithm is access forwarding ratio rithat is calculated by hi /Li (t)3.3.2

Estimation of data migration load

This section describes the estimation value of data migration load LMIG that is required at algorithm described section .
We estimate the migration load by performance curve ofstorage nodes that indicate response times of a storage nodeby access frequency. The migration load can be represented
as Qavg /2Rreq [Byte/s], where Qavg [ Byte ] is average
size of data segment such as ﬁle and blocks, Rreq [s] is max
response time that client can tolerate, and 2 on denominator
represent sequential behavior between data read on source
node and write on destination node.
You note that we improve the estimation method at section 5.1 because the estimation method assumed that behavior of storage nodes is linear to IO size, although workloadwith various IO size such as ﬁle server workload caused
non-linear responses.

4

Improvement for ﬁle server workloads

In this paper, we uses ﬁle server workloads as realand update-including workloads. We describes summaryof properties of ﬁle server workloads, improvement ofpremised migration strategy and Replica-assisted migration.

4.1

Properties and trends of ﬁle server workloads

Hsu et al. [4] analyzed trace logs on ﬁfteen PCs and ﬁve
ﬁleservers and report their characteristics. In this section,
we summarize the report as four properties:
Property 1 The workload includes update requests. The
ratio of update requests is 30-60 percent by both requestsize and number.

Property 2 Request size is very small. The average request
size for the original workloads is about 7-9KB, they said.
Property 3 Only a small fraction of the data stored is in active use, they said. the average size of ﬁles accessed c times
at a day f (c) is approximately described as a/cb , where aand b are positive constants. In addition, the daily working set for the various workloads ranges from just over forpercent to about seven percent of the storage used.
Property 4 There are few ﬁles tha t are both read and written. less than 25 percent of the total working set size areused both read and written.

4.2

Improvement of premised migration strategy

Before improving our method, we ﬁrst improve thepremised migration strategy described at section 2.1.
4.2.1

Various request size

Property 2 shows that the workload includes various size ofaccess requests. Thus it is difﬁcult to estimate max performance of storage nodes as units on MB/s or iops because
behaviors of hard disk drives tend to be non-linear on size.
We reﬁne our migration strategy not to use response performance on a request size but to use one on various request
size by measuring with benchmarks.
4.2.2

Extremely skew access distribution

Property 3 shows the extremely skew access distribution.
Our premised migration strategy described at section 2.1
must migrate massive amount of data because the strategy isbased on load equalization on each node with the workload.
The massive amount migration causes longer migration duration than changing speed of workload trend.
We reﬁne the strategy not to base on load equalization
but keeping max load to keep agreed response time of eachnode. The strategy calculates amounts of migrating data bykeeping performance of storage node as hot spot on levels
on service level agreement (SLA).
The reﬁne reduce amount of migrating data on practicalone. Our simulation experiments show that the amount isreduced from about 100GB to about 1GB, while keeping
performances of all storage nodes.
4.2.3

skew distribution of update ratio

Property 4 shows that update ratio of each data segments arefunnel towards zero or one. Thus the coordinator cannot determine the migrating data segments with abstract average
information of update ratio on stored data.

We reﬁne to re-obtain update ratio of each data on eachstored node after the coordinator node issues migration orders for keeping both scalability and accuracy of update
ratio information. The migration destination node also informs the update ratio of migrated data to the node that has
replica of it.

4.3

Improvement of Replica-assisted Migration

Replica-assisted Migration should be improved as follows for real workload such as ﬁle servers.
Consistency control between primary and replicas are as
follows. We assume the synchronous update between primary and replicas. Request sequence is received the nodecontaining primary data. The update requests and read requests are serialized by the primary node and sending tonodes containing replicas if forwarding is needed.
Forwarding ratio should be calculated by load of readrequests. We change the strategy described at section ?? tocalculate by load of the node and average update ratio of
node i ui (0 ≤ ui ≤ 1). First reﬁned point is to change
deﬁnition of load of a node from only primary load to totalof read and write to primary and write to replicas. Second
one is forwardable load from total primary load to only readload of primary. Third one is calculation of forwarding ratio
hi to hi /{Li (t)(1 − ui )}5

Experiments

We evaluate and observe the behavior of our method under ﬁle server workload by simulation program we constructed.

5.1

Environments

We use a queuing network based storage system simulation program that we constructed in past study. Behaviorof hard disk drives in the simulation is calculated with parameters on HGST deskstar T7k250 speciﬁcation [9]. The
simulation constructs of 16 storage nodes with 64MB cacheconnected by 800 Mbps network.
Write accesses are processed as below. Cache on eachstorage node is set to write through and replicas are updated synchronously. Then the write request arrived at disk
drives on both primary node and replica node . Disk drives
eliminate requests to same blocks. Command re-ordering
method is not implemented.
As described at section , we need benchmark result of
the storage nodes. We measured the max access frequency
a node can keep practical response time with storing 1GB
ﬁles by request size. Responses of larger size are dominatedby networks, while one of smaller size are constricted by1.4

Table 1. Speciﬁcations of used workloads
workload parameter

a

b

c

d

1.2

e

proposal(avg)

proposal(max)normal(avg)normal(max)1

Head Timestamp (hour)Time span (hour)
Write Ratio on # (%)
Write Ratio on size (%)
Accessed size (GB)# of accessed ﬁles (103 )# of requests
total ﬁle size(GB)# of total ﬁles

15
1.1
46.9
43.4
36
14.0

16
1.0
41.7
42.2
40
13.4

17
0.9
38.5
39.6
40
11.6

18
1.0
42.7
42.0
42
13.4

19
0.9
44.4
44.7
40
11.9










0.8










0.6














0.4







1.2 × 10450 × 2 (Primary & Backup)
1.0 × 106
5

0.2
0
a

where sid is preliminary numbered by trace sequence order.
The transform distribute ﬁles on 220 ranges.

5.2

Results

Figure 2 shows the average and max response time perblocks under ﬁve segments of workload. both of them arenormalized by response time without our method. The ﬁgure indicates that average response time are reduced, while
max response time has no differences.
The experimental results show that the proposed method
make no sense from aspects of QoS. We analyze the result
log on simulation and discuss two differences of behaviors
between synthetic workload and real workload.
One is by property 3 that is high skew distribution. Extremely skew distribution causes isolated hot spot and themigration can transfer data from other idle nodes by using
replicas. Therefore migration load don’t occurs on hot spot.
The other is high update load. In spite of the similarratio between read and write operation, it is observed thatmany heavy workload consist of much of write accesses.

c

d

e

EXP

disk drives. Applying least square method, we can calculateload of a request to l(s) by following equation:{s×3.38×10−9 +5.49×10−3 (s ≤ 800KB)
l(s) =(1)s/(96×106 )(s > 800KB)
where the node performance is normalized as one. We
use the equation on following experiments and discussion.
To evaluate our method, we use trace logs on real ﬁleserver [6]that Hewlette Packard published. The used workloads are generated by clipping ﬁve set of one hour traces
form the trace log and be as sequences of stateless accesses. Table 1 shows the characteristics of clipped workloads. Stored ﬁle set is also generated by trace log and results of ls command.
We use range partitioning as ﬁle placement policy. Identiﬁer of each ﬁles are generated as follows:
id = sid ⊕ ((sid ∧ 0xff) × 212 )(2)bFigure 2. Relative access latency with/without
Replica-assisted Migration~iwithout proposed method ~jIn addition, cache on storage nodes absorb almost all ofread accesses with 90 percent hit ratio. Thus most accesses
requests concentrated on hot spot are write operations thatcannot forward to replicas.
We summaries the result as that while providing migration source selectability well works, access forwarding to
replicas should be reﬁned to work well with real and hard
update operations.

6

Adaptive replica-assisted migration

The experiments and analysis shows that providing migration source selectability well work even under real workload.
In this section, we propose to enhance the method in order to reduce migration duration.

6.1

Adaptive selection of migration source nodes

When concentrated update operations make hot spot
nodes, the node containing their replicas also become hot
spot with synchronous update load. In order to reduce migration duration, the migration load should be distributed tocolder hot spot.
We propose Adaptive selection of migration source
nodes to solve the problem. The method dynamically select migration source node based on short-span evaluatedload information such as I/O queue length.
The method enhances our past proposed method to add
following tasks.
When migration of each ﬁle or moderate amount of ﬁles
ﬁnishes, the migration source node, the replicas of the nodeand destination node communicate the short-span evaluated       

16.0%

  

14.0%

                    

12.0%
10.0%
8.0%
6.0%
4.0%
2.0%

 

            

0.0%


Figure 3. reduction ratio of migration duration
by Adaptive replica-assisted migration.
load information. The information tend to transfer in piggyback payload. Then the primary of migration source node
select which S-pattern or N-pattern, so that migration load
occur at colder hot spot. At a result, the migration load is
distributed to two nodes equally and migration duration is
reduced.

Based on the result of analyze, we also proposed Adaptive replica-assisted migration by enhancing our past proposed method to reduce migration duration. The adaptive
method worked well with almost all time of real ﬁle server
workload.
To solve current issue, we plan to enhance and improve
the premised migration strategy to apply our method to actual systems. We also should reﬁne replica consistency control and cache behavior in order to reduce update load.
Detailed evaluation and analysis are one of important future works.

Acknowledgement
This work is partially supported by Japan Science andTechnology agency via CREST program, JSPS via Grantin-aid for Scientiﬁc Research, Storage Research Consortium, MEXT via Grant-in-Aid for Scientiﬁc Research#18049026 and the MEXT 21st Century COE Program.

References
6.2

Efﬁciency of adaptive selection

We observe behaviors of the adaptive migration source
selection by simulation and real workload. In the experiments we use queue length of disk module as short-spanevaluated load information.
Figure 3 shows reduction ratios on migration duration of
eleven periods of migration with six segments of workload.
The ﬁrst three segments of workload are same as a, b, c intable 1 and the second three are heavier version of ﬁrst three
to reduce 30 percent of intervals between accesses. In theﬁgure, while bar indicate ﬁrst migration on the migration
and black bar indicate after second migration.
The results show that all of the migration duration is reduced by adaptive version of proposed method. About 2.6
percent of migration duration is reduced. Although we havenot analyze details yet, the ﬁgure also show that the method
work more efﬁcient after second migration than ﬁrst migration.

7

Conclusions

In this paper, we improved, observed, analyzed and evaluated Replica-assisted migration we have proposed withﬁle server workload as actual and update-including workload. Reﬁning a few point in order to work as ﬁle server,
one of our method to provide migration source node selectability worked well with the workload, while the otherof our method to forward partial accesses to replicas madeno sense because of high skew access distribution and highupdate load.

[1] K. Dasgupta, S. Ghosal, R. Jain, U. Sharma, and A. Verma.
Qosmig: Adaptive rate-controlled migration of bulk data instorage systems. In the 21st ICDE, pages 816–827, 2005.
[2] 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
DEXA, pages 846–858, Sep 2000.
[3] H.-I. Hsiao and D. J. DeWitt. Chained declustering: A newavailability strategy for multiprocessor database machines.
In Proceedings of the 6th ICDE, pages 456–465, 1990.
[4] W. W. Hsu and A. J. Smith. Characteristics of I/O trafﬁcin personal computer and server workloads. IBM Syst. J.,
42(2):347–372, Feb. 2003.
[5] D. Kobayashi, A. Watanabe, R. Taguchi, T. Uehara, andH. Yokota. An efﬁcient access forwarding method based oncaches on storage nodes. In SWOD 2005, pages 188–191,
2005.
[6] S.-P. Labs. Publicly-available storage traces( ”ﬁle system
traces”). http://tesla.hpl.hp.com/public software/.
[7] C. Lu, G. A. Alvarez, and J. Wilkes. Aqueduct: online data
migration with performance guarantees. In USENIX FAST,
pages 219–230, 2002.
[8] H. Simitci. Storage Network Performance Analysis. Wiley
Technology Publishing, 2003.
[9] H. G. S. Technologies. Deskstar T7K250 Hard Disk Drive
Speciﬁcation. http://www.hitachigst.com, ver. 1.7 edition,
2006.
[10] 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.
[11] 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.