Power-Saving in Large-Scale Storage Systems with Data Migration
Koji Hasebe, Tatsuya Niwa, Akiyoshi Sugiki, and Kazuhiko Kato
Graduate School of Systems and Information Engineering
University of Tsukuba,
1-1-1 Tennodai, Tsukuba 305-8573, Japan
hasebe@iit.tsukuba.ac.jp, niwa@osss.cs.tsukuba.ac.jp, {sugiki,kato}@cs.tsukuba.ac.jp

Abstract—We present a power-saving method for largescale distributed storage systems. The key idea is to use
virtual nodes and migrate them dynamically so as to skew
the workload towards a small number of disks while notoverloading them. Our proposed method consists of two kindsof algorithms, one for gathering or spreading virtual nodes
according to the daily variation of workloads so that the active
disks are reduced to a minimum, the other for coping withthe changes in the popularity of data over a longer period.
For this dynamic migration, data stored in virtual nodes aremanaged by a distributed hash table. Furthermore, to improve
the reliability as well as to reduce the migration cost, we
also propose an extension of our method by introducing a
replication mechanism. The performance of our method ismeasured both by simulation and a prototype implementation.
From the experiments, we observed that our method skews theworkload so that the average load for the active physical nodes
as a function of the overall capacity is 67%. At the same time,
we maintain a preferred response time by setting a suitablemaximum workload for each physical node.

I. I NTRODUCTION
Power-saving has become a central issue in today’s computing systems. In particular, as a high percentage of thetotal computing system’s energy is used by the data storage
systems, a number of suggestions for reducing power instorage systems have been proposed, e.g. [2], [6], [7]. Manyof these studies have restricted their scope to storage systems
with a specific kind of central controller to manage the data
access or storage systems consisting of a relatively small
number of disks (typically, up to several dozen). However,when considering increasingly large-scale computing systems as typified by cloud computing [1], scalability is ofmajor importance.
In this paper, we propose a power-saving method forlarge-scale distributed storage systems. To reduce power
consumption of storage systems, a commonly-observed technique in the literature is to skew the workload towards asmall number of disks, thereby enabling the others to be
in a low-power mode. To apply this technique to largescale distributed storage systems, a possible approach is to
use replication; a recent example of which is [4] where
they investigated the efficient allocation of replicated data
to minimize the number of active disks, while all the data
are accessible. An alternative approach, not yet thoroughly

studied, is to migrate the stored data dynamically in such a
way that all data are gathered into as small a number of disks
as possible while not overloading them. The main objectiveof our research is to explore the power-saving method using
the latter approach.
For dynamic migration, in our method, data stored in
virtual nodes are managed by a distributed hash table (DHT),
which has been adopted in the context of load-balancing
for DHTs (e.g., [3]). On the other hand, the migrationis controlled by two types of algorithms. One, called theshort-term optimization algorithm, is used for gathering or
spreading virtual nodes according to the daily variation of
the workload so that the number of active physical nodes
is reduced to a minimum. The other algorithm, called thelong-term optimization algorithm, is used for coping withchanges in the popularity of data over a longer period (forexample, a week). This leads to more effective short-term
optimization. Furthermore, we propose an extension of our
method by introducing a replication mechanism to reducethe migration cost and improve reliability (i.e., fast recovery
from disk failure).
The performance of our method is measured both bysimulation and with a prototype implementation in termsof the average load, the average response time, and themigration cost. From the experiments with our prototype
implementation, we observed that our method skews theworkload so that the average load of the active physicalnodes as a function of the overall capacity is 67%. This
result indicates that our method effectively skews the workload while keeping to a preferred response time (whose
overall average is 80msec) by setting a suitable maximum
workload (i.e., threshold of migration) for each physicalnode. Additionally, our simulation shows that the longterm optimization algorithm consistently and continually
improves power consumption.
This paper is organized as follows. Section 2 presents
related work. Section 3 describes the underlying storage
system and the method of data migration. Section 4 introduces our power-saving algorithms. Section 5 proposes a
replication mechanism in our method. Section 6 presents
the simulation results. Section 7 presents the evaluation bymeans of a prototype implementation. Finally, Section 8

!

!+!

!

!
&
!!
!&
"!
"
'
!"
!'
""
#
(
!#
!(
"#
$
)
!$
!)
"$
%
!*
!%
"*
"%
"!!+! ""!+! "#!+! "$!+! "%!+!

,-./0

!+"

!!"#

!
"
#
$
%
&
'
(
)
!*
!!
!"
!#
!$
!%
!&
!'
!(
!)
"*
"!
""
"#
"$
"%
"!!+" ""!+" "#!+" "$!+" "%!+"

"#$

!!#$%
"

'"&"%'($%
!!%$%
"%

!#+$

,-./0

!!+$

!
"
#
$
%
&
'
(
)
!*
!!
!"
!#
!$
!%
!&
!'
!(
!)
"*
"!
""
"#
"$
"%
"!#+$ ""#+$ "##+$ "$#+$ "%#+$

Figure 1.

,-./0

!
&
!!
!&
"!
"
'
!"
!'
""
#
(
!#
!(
"#
$
)
!$
!)
"$
%
!*
!%
"*
"%
"!!+$ ""!+$ "#!+$ "$!+$ "%!+$!!&#

Figure 2.

1/1

Split of virtual node vi

1/2

into vi

2/2

and viExample of configuration of virtual nodes (For c = 5, d = 4)

concludes the paper and presents future work.
II. R ELATED W ORK
There have been a number of studies to reduce storage
power consumption. A commonly-observed feature in manyof these techniques is that they skew the workload, and can
be classified into the following categories according to thevariations in this approach.
The first category, including MAID [2] and PDC [6],focuses on the popularity (i.e., access rate distribution) andconcentrates popular data on specific disks. The second, as
typified by Pergamum [9], uses NVRAM to extend the lowpower mode period by caching data to a write store. The
final category considers redundancy (i.e., data replication).
In DIV [7], original and redundant data are separated into
different disks thereby allowing read/write requests to beconcentrated on the disks with the original data. In EERAID[5], RIMAC [12], and eRAID [10], a data access on a disk in
low-power mode is transformed into accesses on active disks
or caches, and the required data are reconstructed from theparities obtained during these accesses. In Hibernator [13]and PARAID [11], data are collected or spread to adapt tochanges in operational loads. Our study mainly focuses on
the dynamic migration of storing data.
Although these studies in the literature restrict their scope
to storage with a specific kind of central controller to manage
the data access, recent work such as Harnik et al., [4]addresses power-saving in large-scale distributed storage.
They investigated the efficient allocation of replicated dataso as to minimize the number of disks while all the data areaccessible. Our main motivation is to explore an efficienttechnique to skew the workload by means of migration,
instead of taking the replication approach.
III. U NDERLYING S YSTEM AND DATA M IGRATIONThe underlying storage system of our method consists of aset of physical nodes, each of which contains a set of virtual
nodes. In our method, the number of virtual nodes in every
physical node is fixed at some specific number (denotedby c). The physical nodes are segmented into blocks byc, thus each block contains c2 virtual nodes. To simplify
our discussion, let us consider a usage environment where
the daily workload may vary, and five physical nodes are
required at off-peak time to maintain a certain expected
response time, but may increase up to four-fold. (Throughout
this paper, the increasing rate of system workload is denotedby d. Thus, in this case d = 4.) In this case, the system
configuration is as follows. (See also Fig 1 for a graphicalpresentation.) First, the required 20 (= c · d with c = 5,
d = 4) physical nodes are segmented into four blocks
named B 1/1 , B 1/2 , B 1/4 , and B 3/4 , where the physicali/ji/j
nodes in B i/j are called p1 , . . . , p5 for each block. Next,
1/1
1/1
25 (= c2 ) virtual nodes named v1 , . . . , v25 are mapped
1/1
on B
as in Fig 1 where the numbers in block B 1/1
indicate the allocation of virtual nodes. For example, the
1/1
1/1
1/1
second virtual node, v2 , is allocated on p1 , and p1
1/1
1/1
contains v1 , . . . , v5 . On the other hand, operations tostore/retrieve data are realized using the lookup mechanismof a DHT. That is, 25 virtual nodes are allocated at equal
distances in the key space of the DHT.
When the system workload increases, each physical nodein B 1/1 independently checks its own workload, and if it
exceeds its capacity, i.e. the maximum workload to maintaina certain expected response time, one of the virtual nodes
is moved to another low-loaded active physical node in thenext block, B 1/2 . We call such a block a child. If there is nosuch physical node, the leftmost node in a low-power modeis activated. For finer-grained adjustment of the workload,when moving a virtual node it is split as follows. (Seealso Fig 2 for the graphical presentation. Here, we consider
Chord [8] as the underlying DHT.) For example, for the
1/1case of i = 2 in Fig 2, when the workload of p1 exceeds
1/1
capacity and virtual node v2 is moved, a new virtual
1/2
node (called v2 ) is created and put at the midpoint of
1/1
1/2
the key space covered by v2 (i.e., the ID of v2 is set as(k + k 0 )/2), then the data corresponding to the key space
1/2[k, (k + k 0 )/2] are copied to v2 . Thus, through the built-in
mechanism for maintenance of routing tables, the key space[k, k 0 ] is shared equally by these nodes. At this moment,
2/2
1/2
the original virtual node is renamed as v2 . Then v2 ismoved to the point (which is indicated by the correspondingnumber in the figure) in the next block (i.e., B 1/2 ), while
2/2
v2 stays at the same point as the original physical node.
In contrast, when the system workload is decreasing, split
virtual nodes are gradually moved back to the original point.
1/1
For example, when the workload of p1 becomes low and
1/2
able to absorb v2 , the data stored in this virtual node are
2/2
merged into v2 and then removed from the key space. At
1/1
this moment, the merged node is renamed as v2 and put
2/2
into the same position as v2 . Finally, if a physical node
has no active virtual node, it enters a low-power mode.
This migration process occurs for each block according
to the daily variation of the system workload. For example, after all the virtual nodes in B 1/1 are migrated to
1/2
2/2
B 1/2 , again, virtual nodes vi and vi are split into the
3/4 4/4
1/4 2/4
pairs hvi , vi i and hvi , vi i, and then the first-halfnodes are moved to B 3/4 and B 1/4 in a similar way. This
process is realized by using the algorithms, called shortterm optimization algorithms. In addition, we also provide
an auxiliary algorithm, called the long-term optimization
algorithm, to maintain the effectiveness in an environment
where the popularity of data varies. The details of thesealgorithms are explained in the next section.
Here we would like to note that the mapping of the virtual
nodes of any two blocks of a parent-child relationship isorthogonal. That is, as indicated in Fig 1, the virtual nodes
in a block are allocated in vertical lines if and only if thevirtual nodes in its parent as well as its child blocks areallocated in horizontal lines. Because any physical node ina parent block has all the physical nodes in its child blockas destinations of migration, the physical nodes in the childblock can be efficiently activated from the left. This fact isdemonstrated in later sections.
Finally, we comment on the migration cost. To reduce themigration cost, instead of moving the whole data stored in a
1/2
virtual node, there is an alternative way. That is, when v2
1/2
is removed, the stored data remain in p2 and are reusedat the time of the next splitting operation. This enables the
migration by copying the difference from the previous day.
Indeed, the advantage of this technique is the trade-off withthe disk space, however if the system has enough space on
the disks and can afford to create some redundancy, thistechnique can be useful for effective migration. In Section
6, we present the introduction of a replication mechanism
using this technique.
IV. P OWER -S AVING A LGORITHMS
Our power-saving method relies primarily on two typesof algorithm. In this section, we introduce the type named
short-term optimization algorithm, which copes with thedaily variation of the system load. This algorithm consistsof two parts; one is used when the workload is increasing
and the other when the workload is decreasing, and they
are run at regular intervals. We next explain why we require

Algorithm 1 Short-term optimization (extension)if cap(p) ≤ load(p) thenfor all p0 ∈ (On(Bcld ), Oﬀ (Bcld )) do
if state(p0 ) = 0 thenactivate p0
end ifif cap(p0 ) − (load(p0 ) + Σv00 ∈queue(p0 ) load(v 00 ))≥ load(child(v 0 )) thenqueue(p0 ) ← append(queue(p0 ), v 0 )end ifend forend if

!!+!

!
"
#
$

%
&
'
(

)
!*
!!
!"

!#
!$
!%
!&

"!!+! ""!+! "#!+! "$!+!

Figure 3.

!!+"

!
%
)
!#

"
&
!*
!$

#
'
!!
!%

$
(
!"
!&

"!!+" ""!+" "#!+" "$!+"

Example of migration (when system workload is increasing)

the auxiliary algorithm, named long-term optimization algorithm, which is used for load-balancing in each block, andthen introduce the algorithm.
A. Short-term optimization algorithm for extension
When the system workload is increasing during the nominal period of a day, each active physical node behaves in thefollowing way at regular intervals (e.g., every 30 minutes
or one hour), which is called the short-term optimization
algorithm for extension, consisting of the following two
steps.
j/k1) Each active physical node pi checks its own workload, and if the workload exceeds its capacity, then thisnode asks for the current capacity of every physical
2j−1/2k
node in its child block (i.e., pi∈ B 2j−1/2k fori = 1, . . . , c).
2) If there are physical nodes in active mode that do notj/kexceed their capacity, then pi chooses one of them as
the destination of migration of its virtual node. (Notethat, due to the manner of allocation, such a virtual
node is uniquely determined when the destination isj/kdecided.) Otherwise, pi activates the leftmost among
the physical nodes in a low-power mode in the childblock, and then migrates the corresponding virtualnode.
More formally, this procedure is presented in Algorithm 1.
In this algorithm, Bcld is the child block of p, and “queue”
represents the request queue for holding the requests for
migration.

!!+!

!
"
#
$

%
&
'
(

)
!*
!!
!"

!#
!$
!%
!&

"!!+! ""!+! "#!+! "$!+!
,!,!,!,"-

Figure 4.

!!+"

!
%
)
!#

"
&
!*
!$

#
'
!!
!%

$
(
!"
!&

"!!+" ""!+" "#!+" "$!+"

Example of migration (when system workload is decreasing)

To help the reader understand this process, we present a
simple example (see also Fig 3 for the graphical presentation, where the nodes in low-power mode are denotedby gray shading). Initially, the workload of every virtual
node in block B 1/1 is 10 and is equally shared by thechild nodes when splitting. The capacity of every physicalnode is equal to 40. All the physical nodes in B 1/2 are in
low-power mode. In this setting, when the workloads of allnodes in B 1/1 increase, each node migrates one of its virtual
nodes according to the algorithm. Here, if at the beginning
1/1
the workload of p1 exceeds its capacity, then this node
1/2
1/2
activates p1 and v1 is moved to this physical node, and
1/1
1/1
subsequently the remaining nodes from p2 to p4 may
1/2
choose the same physical node, p1 instead of activating
1/1
1/1
1/2
other nodes in B . Furthermore, if p1 and p3 become
overloaded again, then these nodes can migrate their virtual
1/2
1/2
1/2
nodes to p2 , so that p3 as well as p4 are still in a
low-power mode. Such effective migration is realized by themanner of allocation.
B. Short-term optimization algorithm for reduction
After the peak-time of day and when the system workload
is decreasing, reducing power consumption requires gathering the split virtual nodes into their parent blocks again.
However, for effectiveness in power-saving, this cannot berealized solely by the reverse process of extension. We
explain this by using a simple example. (See Fig 4 for agraphical presentation.) Let us consider the situation where
the workload of B 1/1 becomes low and has room to absorb
some of the virtual nodes in B 1/2 . Now assume that the
1/1
remaining capacity of p4 is 2, while the other in B 1/1 is
1 (these are presented as parenthetical numbers below thephysical nodes), and the virtual nodes at the points of theencircled numbers are migrated to B 1/2 , thus, these can be
migrated to B 1/1 . In addition, the workload of every virtual
node in Bcld is equal to 1. In this situation, the best solution
1/2
for minimizing the active nodes in B 1/2 is to migrate v7 ,
1/2
1/2
1/2
1/2
1/2
v10 , v14 , and v15 , that enables both p2 and p3 toenter the low-power mode. Otherwise fewer nodes can be ina low-power mode or at least one physical node in B 1/1 isoverloaded. This problem can be formally stated as follows.
Problem: For a given pair of blocks, Bprt and Bcld , witha parent-child relationship, find a maximal set S of the

Algorithm 2 Short-term optimization (reduction)function findSolution(M1 , M2 , . . . , Mc )N ← {M1 }, T ← φ
for all Mi ∈ {M2 , . . . , Mc } dofor all M ∈ Mi dofor all M 0 ∈ N do
M 00 ← M ∩ M 0
if not is include(T , M 00 ) thenT ← append(T , M 00 )end ifend forN ←T, T ←φ
end forend forreturn one of the maximum elements from N
function is include(T , M )for all S ∈ T do
if M ⊆ S thenreturn trueend ifend forreturn false
end function

physical node in Bcld such that all the virtual nodes in S
can be merged with their corresponding virtual nodes in Bprt
without overloading any physical nodes in Bprt .
The solution of this problem cannot be achieved when
every node behaves independently. That is, our algorithm,
called the short-term optimization algorithm for reduction,gathers the information of the workload at regular intervals
and then calculates the best solution among all possiblecombinations of migration. This algorithm consists of thefollowing four steps.
1) Each p0i ∈ Bcld sends the information of load(v 0 ) for
all v 0 ∈ p0i to all the physical nodes in Bprt .
2) Each pi ∈ Bprt lists all possible combinations ofa subset of physical nodes in Bcld such that pi
can absorb their virtual nodes without exceeding its
capacity.
3) All the results obtained in the previous step aregathered into a specific single node in Bprt , and thesolution is found using Algorithm 2 below. Here Mi
represents the result calculated by pi .
4) The solution is announced to all the physical nodesin Bcld , and then the virtual nodes are gathered into
Bprt according to this solution.
More formally, this procedure is presented in Algorithm
2. Intuitively, each element in Mi indicates one of thelargest sets of physical nodes which can be in a lowpower mode under the best situation possible for pi . Thus,

!!+!

!
"
#
$

%
&
'
(

)
!*
!!
!"

!#
!$
!%
!&

!!+"

"!!+! ""!+! "#!+! "$!+!

!!+!

%
&
#
$

!
"
'
(

)
!*
!!
!"

!#
!$
!%
!&

"!!+! ""!+! "#!+! "$!+!

Figure 5.

!
%
)
!#

"
&
!*
!$

#
'
!!
!%

$
(
!"
!&

"!!+" ""!+" "#!+" "$!+"

!!+"

%
!
)
!#

&
"
!*
!$

#
'
!!
!%

$
(
!"
!&

"!!+" ""!+" "#!+" "$!+"

Example of inefficient migration and reconfiguration

every intersection of elements chosen singly from each Mi
indicates a possible solution if all the physical nodes absorb
as many of their virtual nodes as possible. Therefore, anyof the largest intersections among all possible combinations
is a solution of the problem.
We comment here on the computational complexity of thisalgorithm. Generally, for a given c of the number of physicalnodes in a child block, the computational complexity to findthe best solution is (c−1)·(c Cb 21 cc )3 , although the number of2
all possible combinations becomes 2c . Indeed, as far as our
experiments are concerned, we were able to find a solution ina feasible time for the condition c ≤ 15. Note that, according2
to the value of 2c for the input c, we were able to find asolution in a feasible time for the condition around c ≤ 5,
if we checked the results of all possible combinations one
by one without any strategy.
In consideration of this result of computational complexity, for larger systems, we propose to separate a child block
into several sub-blocks which consist of about 10 physicalnodes, and apply the algorithm to every distinct sub-block.
As we shall show in Section 6, we considered the condition
that c = 100 by taking this approach in our simulation,and observed that it still effectively skews workload without
search-space explosion.
C. Long-term optimization algorithm
So far we have explained how our method reduces powerby moving virtual nodes according to the daily variation of
the workload. However, to maintain effective power-saving,
it requires load-balancing in each block. We explain thisby using a simple example. (See Fig 5 for a graphicalpresentation.) In the upper two blocks, B 1/1 is the parent
block of B 1/2 , each of which consists of four physical nodes.
The capacity of each node equals 10. We assume that due
to changes in popularity of stored data, the workload of
1/1
1/1
vi ∈ p1 (for i = 1, . . . , 4) becomes 5 while the workloadof the others is 2, so the physical node in B 1/1 is muchbusier than in the others. In such a case, this physical node
should migrate its virtual nodes earlier than the others, andconsequently all the physical nodes in B 1/2 should become
active while their workload is low.
To avoid this problem, our method provides an auxiliary algorithm named the long-term optimization algorithm,
which is intended for load-balancing in each block at regular relatively longer periods (such as, once a week). For
example, in the case of Fig 5, p1/1 detects the imbalance,
1/1
1/1
and exchanges some of its virtual nodes (say, v1 and v2 )1/1
with the low-loaded nodes on the same row (say, v5 and
1/1
v6 ) in the same block. (The result is shown as the lower
two blocks in the figure.) At that point, the allocation of
all the other blocks is also changed in the same way. (Notethat this migration requires the exchange of all data storedin each pair of virtual nodes between the different physicalnodes. However, if the pair is on the same row, in half theblocks the corresponding pair is in the same physical node,
hence we reduce the migration cost.) In this case, by this
1/2
reconfiguration, the activation of p4 is delayed, so we can
1/2
reduce the active nodes in B .
However, in a more realistic situation, it is possible thatthe requirement for reconfiguration in one block conflicts
with the requirement of another. In this paper, this problem
is not thoroughly investigated and one of the future work.
V. M ANAGEMENT OF R EPLICASIn this section we explain how to introduce a mechanism
for data replication into our proposed system for improving
the migration cost and reliability. This can be realized by
the following two additional operations when splitting or
merging a virtual node. (See also Fig 6 for the graphicalpresentation. In this figure, the boxed items indicate the data
kept in the original node, while the encircled items indicate
replicas which are updated after the migration.) Here ρ < cis the number of replicas.
Split: When the virtual node v j/k on p ∈ Bprt is split
into hv 2j−1/2k , v 2j/2k i and v 2j−1/2k is moved into
the child block Bcld , the data stored in the key
space of v 2j−1/2k are kept in p. Also, after the
split, the updated difference of stored data by
v 2j/2k is saved in ρ physical nodes in Bcld .
Merge:When the virtual node v 2j−1/2k on physical nodep0 ∈ Bcld is merged with v 2j/2k in the parent block
Bprt , the data stored by v 2j−1/2k are kept in p0 .
Also, after the merge, the updated difference ofstored data by v j/k is saved in ρ physical nodes in
Bprt .
If the system has enough space in its storage disks, thisredundancy of data enables a reduction in data migration.
That is, when splitting virtual node v j/k , the data in v 2j−1/2ksaved at the previous merge operation can be reused, and it'()*+,(-.

&'"("$")&'"%(*&$"%)&'"%("$"%)&'"%(*&$"%)&'"!"!"!"#!$%"#'()*(&%(*&$"%)!+"!"!"#!$%"#'()*+,(-.

Average load of active physical nodes (%)!"#$%&

90
80
70
60
50
40

without long-term,x2.0
with long-term,x2.0
without long-term,x1.5
with long-term,x1.5
without long-term,x1.2
with long-term,x1.2

30
20
0

("$")

18

24

Average load of active physical nodes (with replication)&'"%(*&$"%)!+"!"!"#!$%"#

Data replication (with ρ = 1)

is necessary to migrate only the updated difference from theprevious merge operation. Similarly, when merging virtual
node v 2j−1/2k with v 2j/2k , the data in the key space ofv 2j−1/2k saved at the previous split operation can also bereused.
Our proposed replication mechanism is also useful fordata recovery from disk failure. That is, for a given numberof replicas, ρ, any data in the system is accessible at any
time against ρ disk failures.
VI. S IMULATION R ESULTS
To understand the effectiveness of our method for storage
systems consisting of hundreds of physical nodes, we evaluated the average load (i.e., the ratio of workload to capacity)of the active physical nodes and the impact of the long-term
optimization algorithm using simulations.
Parameters and settings. In the evaluation of this section,
we considered the following system. Each block consistedof 100 physical nodes and the number of virtual nodes
in each physical node is 100, thus each block included
10,000 virtual nodes. In the intended usage environment, we
assumed that the system workload varies in a day. During thecourse of a day (that is modeled by discrete time intervals
t = 0, . . . , 23), the workload of all virtual nodes was initiallyat its lowest, and increased until the middle of the day thendecreased until the end, where the gap was sixfold. We
modeled workloads by natural numbers and assumed thatthe capacity of every physical node was equal to 100. In
addition, due to the popularity of stored data, we considered
two groups of virtual nodes with different workloads: group
1/1
1/1
G1 of 2000 nodes (initially allocated in p1 , . . . , p20 ) were
1/1
1/1
the busier ones, while group G2 of 8000 (in p21 , . . . , p100 )were the normal nodes. In each group, the workloads ofall virtual nodes were the same. The ratio of workloads
of a node in G1 to a node in G2 was denoted by α, andThe number of active physical nodes

Figure 6.

12Time (hour)

Figure 7.
&'"!"!"!"#!$%"#

6&'"%("$"%)&'"%(*&$"%)
("$")
&'"

without long-term,x2.0
with long-term,x2.0
without long-term,x1.5
with long-term,x1.5
without long-term,x1.2
with long-term,x1.2

1000
800
600
400
200
0

6

12

18

24

Time (hour)

Figure 8.

Number of active physical nodes (with replication)

we considered the cases that α = 1.2, 1.5, and 2. In eachcase, we set the initial workload of the system to be 60%
of its capacity, i.e. for α = 1.2, 1.5, and 2, the initial
workloads of a node in G1 were respectively 0.69, 0.82, and1, while in G2 were respectively 0.58, 0.55, and 0.5. In thefollowing simulations, we evaluated cases with the long-term
optimization (which totally improves the bias of workloadin each block) and without one. Due to space limitations,
we only present the results for the case of single replication(i.e., ρ = 1).
Average load of active physical nodes. Fig 7 indicatesthe change in the average load of active physical nodes
during a day. This figure shows that in the case of long-term
optimization, for the cases of α = 1.2, 1.5, and 2, the daily
average load is 74%, 71%, and 67%. On the other hand, inthe case of no long-term optimization, the daily average load
is 69%, 64%, and 57%. The results of this simulation showthat in our method the physical nodes run effectively, copingwith the daily variation of workload. Moreover, comparedwith the case of no long-term optimization, this optimization
algorithm improves the average load as expected.
Impact of long-term optimization. Fig 8 indicates thechange in the number of active physical nodes during aday. This figure shows that long-term optimization saves
on average 7%, 10%, and 14%, and up to 17%, 23%, andParameters and settings. Servers (i.e., physical nodes)
were logically grouped into four blocks, and each server
had initially 10 virtual nodes. Besides these 40 servers,
we used a single client of data access. Every virtual nodestored 600 files whose size was equal to 1MB. In our
experiments we did not consider data replication. As inthe simulations, we considered two gruops of virtual nodes
with different workloads: group G1 of 20 nodes were thebusier ones whose initial workloads were equal to 100
data access requests per minute, while group G2 of 80
nodes were the normal ones whose initial workloads wereequal to 50 requests per minute. The experiment duration
was 24 hours and the workload of all virtual nodes was
initially at its lowest, and increased until the middle thendecreased until the end at regular 1-hour intervals, where
the gap was sixfold. By some preliminary experiments, weobserved that the capacity of each physical node is 1000
requests per minute to keep an expected response time, andin consideration of the migration cost, we set 90% and 60%of this capacity as the thresholds of migration for extension
and reduction, respectively. In our experiments, we assumed
that the amount of daily difference of data from the previous
day is 10%, i.e. migration of virtual nodes was done bymoving only this updating part, and compared it to the casethat the whole data were migrated.

Load of active physical nodes (%)

VII. E XPERIMENTS WITH IMPLEMENTATION
We conducted experiments with the current prototype
implementation of our proposed system to evaluate theapplicability of our method to real systems. In this paper, wemeasured the average load of the active physical nodes, theresponse time, the number of active nodes, and the numberof migrations of virtual nodes in an environment where thesystem workload varies.
Our prototype consisted of 40 PC servers housed infive enclosures, each of which was equipped with Dual
Xeon 3.60GHZ CPUs, 1.2–1.8GB memory, and a single
36GB SCSI disk. Migrations of virtual nodes were managed
by the short-term optimization algorithms with the current
workload (i.e., the number of requests for data access perunit time) monitored by each server. Here, the migration
speed was saved so as to avoid the increase of response
time. In our prototype, DHT for data management was not
implemented, thus data were accessed randomly so that thedata access frequency to each virtual node was the intended
value. In addition, due to the limitation of our experimental
environment, i.e. the bandwidth of different enclosures, weevaluated response time of data access by measuring timefrom sending a request until the data were loaded intomemory in the server.

averagemaximum

120
100
80
60
40
20
0

6

0

12

18

24

Time (min)Figure 9.

Response time per request (msec)

39% in the cases that α = 1.2, 1.5, and 2, comparedwith the case without long-term optimization. Moreover, thisoptimization improves the power consumption consistently
and continually.

Average load of active physical nodes

1000

averagemaximum

800
600
400
200
0

0

6

12

18

24

Time (min)Figure 10.

Average and maximum response time

Average load and response time. Figs 9 and 10 indicate
the change in the average load of active physical nodes andthe response time. Fig 9 shows that the overall averageload is 67% of the capacity, although workloads of somenodes exceed the capacity in the first half part of thisexperiment. From another experiment, we observed that theoverall average load was 68% when the whole data were
migrated. Fig 10 shows that the overall average responsetime is 80msec, which is mostly as intended, although some
responses are delayed. (Throughout this experiment, themaximun response time is 534msec.) In the case that thewhole data were migrated, the overall average and maximum
response time was respectively 158msec and 1436msec.
The results of this experiment show that our optimization
algorithms effectively skew the workload while keeping theintended response time in the real system.
Numbers of active physical nodes and migrations. Fig
11 indicates the change in the number of active physicalnodes and the number of migrations. This figure shows thatthe migration is done on average 0.14 virtual nodes and up
to 20.0 virtual nodes. In the case that the whole data were
migrated, these values were 2.3 and 19.0, respectively. The
result of this experiment shows that our system adjusts thenumber of physical nodes to the variation of workloads andreduces power effectively.

50

physical nodes
migrating nodes

40

40

30

30

20

20

10

10

0

0

6

12

18

24

The number of migrations

The number of active physical nodes

50[2] D. Colarelli and D. Grunwald. Massive arrays of idle disks forstorage archives. In Proc. ACM/IEEE Conf. on Supercomputing, pp.1-11, 2002.
[3] P. B. Godfrey, K. Lakshminarayanan, S. Surana, R. Karp, and
I. Stoica. Load balancing in dynamic structured p2p systems.
In Proc. IEEE INFOCOM, 2004.

0Time (min)Figure 11.

computing. Technical Report UCB/EECS-2009-28, EECS Department, University of California, Berkeley, 2009.

Number of active physical nodes

In closing this section, we would like to stress that the average response time can be reduced further by changing thethreshold of migration for extension to smaller in exchange
for the increase of power consumption.
VIII. C ONCLUSIONS AND FUTURE WORKIn this paper, we presented a power-saving method forlarge-scale distributed storage systems. To reduce power
consumption, we introduced two kinds of optimization algorithms, thereby effectively skewing the workload towards
a small number of physical nodes. We also introduced
a method of data replication for both reducing migration
costs and improving the reliability. Finally, the performanceof our system was evaluated both by simulations and a
prototype implementation. The simulation results showedthat our method kept the workload of active physical nodes
in terms of total capacity, on average, 67–74% for the casewith single replication. The results of experiments with our
implementation showed that the overall average load was
67%. At the same time, we maintained a preferred responsetime (whose overall average was 80msec) by setting asuitable capacity for each physical node.
In future work, we will further investigate to refine ourprototype implementation. Especially, we will implement
our proposed replication mechanism to improve response
time, load balance, and reliability.
ACKNOWLEDGMENTS
We would like to thank Munetoshi Ishikawa for his
valuable comments. This study is partially supported throughthe SCOPE program by the Ministry of Internal Affairs
and Communications of Japan. This study is also supported
in part by the Grant-in-Aid for the Global COE Program
on “Cybernics: fusion of human, machine, and information
systems” at the University of Tsukuba.
R EFERENCES[1] M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. H. Katz,
A. Konwinski, G. Lee, D. A. Patterson, A. Rabkin, I. Stoica,
and M. Zaharia. Above the clouds: A berkeley view of cloud[4] D. Harnik, D. Naor, and I. Segall. Low power mode incloud storage systems. Parallel and Distributed Processing
Symposium, International, pp.1-8, 2009.
[5] D. Li and J. Wang. EERAID: energy efficient redundantand inexpensivedisk array. In Proc. ACM SIGOPS European
Workshop, 6 pages, 2004.
[6] E. Pinheiro and R. Bianchini. Energy conservation techniques
for disk array-based servers. In Proc. Int’l Conf. on Supercomputing, pp.68-78, 2004.
[7] E. Pinheiro, R. Bianchini, and C. Dubnicki. Exploiting redundancy to conserve energy in storage systems. In Proc.
ACM SIGMETRICS Conf. on Measurement and modeling ofcomputer systems, pp.15-26, 2006.
[8] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H.
Balakrishnan. Chord: A scalable peer-to-peer lookup service
for internet applications. In Proc. ACM SIGCOMM, pp.149160, 2001.
[9] M. Storer, K. Greenan, E. Miller, and K. Voruganti. Pergamum: Replacing tape with energy efficient reliable, disk-basedarchival storage. In Proc. USENIX Conf. on File and Storage
Technologies, pp.1-16, 2008.
[10] J. Wang, H. Zhu, and D. Li. eRAID: Conserving energy inconventional disk-based raid system. IEEE Trans. on Computers, vol.57(3), pp.359-374, 2008.
[11] C. Weddle, M. Oldham, J. Qian, A. Wang, P. Reiher, and G.
Kuenning. PARAID: A gear-shifting power-aware RAID. In
Proc. USENIX Conf. on File and Storage Technologies, pp.245260, 2007.
[12] X. Yao and J. Wang. RIMAC: a novel redundancy-basedhierarchical cache architecture for energy efficient, high performance storage systems. In Proc. ACM SIGOPS/EuroSys
European Conf. on Computer Systems, pp.249-262, 2006.
[13] Q. Zhu, Z. Chen, L. Tan, Y. Zhou, K. Keeton, and J. Wilkes.
Hibernator: helping disk arrays sleep through the winter.
In Proc. ACM symposium on Operating systems principles,
pp.177-190, 2005.