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

Efficient Gear-shifting for a Power-proportional Distributed Dataplacement Method

Author

Hieu Hanh LE, Satoshi HIKIDA, Haruo YOKOTA

Journal/Book name

Proceedings of IEEE BigData 2013, , , pp. 76-84

Issue date2013, 10DOI

10.1109/BigData.2013.6691557

URL

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

Copyright(c)2013 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)

Efficient Gear-shifting for a Power-proportional
Distributed Data-placement Method
Hieu Hanh LE∗

Satoshi HIKIDA

Haruo YOKOTA

Department of Computer Science,
Tokyo Institute of Technology
Tokyo, Japan
hanhlh@de.cs.titech.ac.jp

Department of Computer Science,
Tokyo Institute of Technology
Tokyo, Japan
hikida@de.cs.titech.ac.jp

Department of Computer Science,
Tokyo Institute of Technology
Tokyo, Japan
yokota@cs.titech.ac.jp

Abstract—Energy-aware commodity-based distributed file systems for efficient Big Data processing are increasingly moving towards power-proportional designs. However, current data
placement methods for such systems have not given carefulconsideration to the effect of gear-shifting during operations. If
the system wants to shift to a higher gear, it must reallocate theupdated datasets that were modified in a lower gear when a subsetof the nodes was powered off, but without disrupting the servicingof requests from clients. Inefficient gear-shifting that requires alarge amount of data reallocation greatly degrades the system
performance. This paper proposes a data placement method
known as Accordion, which uses data replication to arrange
the data layout comprehensively and provide efficient gearshifting. Compared with current approaches, Accordion reduces
the amount of data transferred, which significantly shortens theperiod required to reallocate the updated data during gearshifting. The effect of this reduction is larger with higher gears
so Accordion is suitable for smooth gear-shifting in multigear
systems. Moreover, the times when the active nodes serve therequests are well distributed so Accordion is capable of higher
scalability than existing methods based on the I/O throughput
performance. Accordion does not require any strict constraint
on the number of nodes in the system therefore our proposed
method is expected to work well in practical environments.
Extensive empirical experiments using actual machines withan Accordion prototype based on the Hadoop Distributed File
System demonstrated that our proposed method significantly
reduced the period required to transfer updated data, i.e., by
66% compared with an existing method.
Keywords—energy-aware;placement; HDFS

I.

power-proportionality;

data-

I NTRODUCTION

Energy-aware distributed file systems for efficient Big
Data processing are increasingly moving towards powerproportional designs [1]. In such systems, the power proportionality can be achieved using data placement methods tocontrol the total number of active nodes used to store datain the system. Based on this concept, several data placement
policies have been proposed that position data on organized
nodes, which aim to provide power proportionality [2]–[4].
These methods share an approach where data are replacedwith replicas on organized nodes. First, the system divides
all of the nodes into a set of small separated groups. These
groups are then configured to operate in multiple gears where
each gear contains a different number of groups. A high gear
∗ Hieu Hanh LE is currently working for Hitachi Ltd.

has a large number of groups of active nodes. Thus, thesystem consumes more power in a high gear, although it candeliver higher performance with suitable processing. Using thismechanism, the system can manage its power consumption andperformance so it can deliver power proportionality.
However, the power-proportional data placement methods
used by current approaches do not consider the effects of gearshifting on the performance of the system. Initially, the system
may have to update the datasets modified in a low gear when asubset of the nodes was powered off. When the system moves
to a higher gear, it needs to guarantee power proportionality
to serve the requests of clients. Therefore, the system has toreplicate the updated data internally on the reactivated nodes
in the background to share the load equally among all of theactive nodes. Inefficient gear-shifting degrades the performanceof power-proportional distributed file systems greatly.
In this paper, we propose a flexible power-proportional
data placement method known as Accordion, which aims to
improve the efficiency of gear-shifting by reducing the amountof re-transferred data. Accordion shares the node organizationof other methods because it supports a multigear operationalmode where each gear is combined from different numbersof different groups of nodes. However, the locations of the
primary data in the dataset are different with Accordion. At
first, the primary data in the dataset are located equally among
all of the nodes in the system. Next, the data are replicatedso each of its replicas is located on nodes that belong todifferent groups. Thus, when the modified dataset is updated(or appended) in low gear, part of the primary data in the
updated dataset is already stored on the active nodes so, only
the remainder of the updated dataset, which can be assumed
to be written to the deactivated nodes, needs to be written
temporally. Therefore, only this temporal part of the updated
dataset needs to be re-transferred when the system shifts toa higher gear. In other existing methods, the overall updated
dataset needs to be reallocated during gear-shifting. As a result,
Accordion is expected to reduce the cost of updating during
gear-shifting because it reduces the period of data movement.
Moreover, the efficiency of this reduction is increased whengear-shifting is performed in a high gear. The amount of data
reallocated is reduced with a lower number of deactivatednodes, which reduces the gear-shifting period further. Thus,
the degradation of the system performance is prevented when
Accordion-based systems shift to a higher gear. Consequently,
Accordion is capable of providing smooth gear-shifting formultigear power-proportional distributed file systems.
Furthermore, Accordion also benefits from a load balancer
that aims to share the workload among all of the active nodes.
One of the main goals of the load balancer is to allow all of theactive nodes to serve the same amount of data when responding
to requests. However, another important factor that affects theperformance of the file system greatly is the timing distribution
when active nodes serve requests. It should be well balanced
in order to provide a higher I/O throughput performance. For
example, if two nodes serve 100 MB of data, generally it would
be more efficient if two nodes served 50 MB simultaneously
rather than sequentially. The different locations of the primarydata mean that Accordion can balance the amount of data
requested and the service timing on the active nodes.
Additionally, the flexibility to determine the configuration
is important in practical applications, such as the number ofactive nodes in each gear in power-proportional file systems.
Rabbit, the first method to achieve power proportionality ina Hadoop Distributed File System (HDFS) [5], has a strict
constraint where the number of nodes in each group is definedby an exponential function, which provides ideal power proportionality based on an equal work policy [4]. In Accordion,
this constraint is more flexible because the total number ofnodes in the system should be an even number. Therefore, itis easier to apply Accordion in a practical environment.
The main contributions of this paper are as follows.
••

We propose a distributed data placement method
known as Accordion, which utilizes data replication
to deliver efficient gear-shifting in power-proportional
distributed file systems. The different approach of
locating the primary data in Accordion reduces theamount of data updated during gear-shifting, hence
shortens the time required to reallocate data.
Accordion is applicable to smooth gear-shifting in
multigear systems because it increases the performance efficiency when gear-shifting is performed in ahigher gear.

•

Accordion increases the I/O throughput performance
because it improve the parallelism effectively distributes both the timing of serving requests and theamount of data requested.

•

Accordion is expected to work well in practical environments because it does not require a strict constraint
on the number of nodes in file systems.

•

We performed extensive empirical experiments usinga maximum of 24 nodes with an Accordion prototype
on HDFS to evaluate the efficiency of gear-shifting
and the performance scalability of power proportionality. The empirical experimental results showed that
Accordion significantly improved the performance by
66% compared with red Rabbit.

The remainder of this paper is organized as follows.
Related studies are discussed in Sect. II and the design of
Accordion is described in Sect. III. Section IV presents a performance evaluation of our proposed method. Our conclusions
and future work are discussed in Sect. V.

II.

R ELATED W ORK

Rabbit [4] was the first method to provide power proportionality to an HDFS by focusing on the read performance.
Rabbit uses an equal work–data-layout policy based on data
replication. The primary replicas are stored evenly among the
primary nodes. The remaining replicas are stored on additional
and increasingly large subsets of nodes. Each node in thesubsets has a fixed order and it stores a number of blocks
that is inversely related to its order, which guarantees thatthe system can distribute the workload equally among all of
the active nodes. However, Rabbit still does not support thewrite workload so it cannot consider the cost of reflecting the
updated data in a low gear.
Sierra [3] was designed as a power-proportional distributed
storage system for general data centers where a replicated object store supports the write-and-read workloads during multigear operations. This method guarantees the write availability
in a low gear by exploiting the concept of write off-loading [6],which was motivated originally by the aim of saving power byspinning down unnecessary disks. This method allows write
requests on spun-down disks to be redirected to other active
disks in the file system. Thus, this technique increases the spindown duration, thereby providing additional power savings.
This method may be considered as a solution for multigear filesystems to deal with updated data in a low gear. Sierra can deal
with write requests in a low gear, but it is still not optimized
to reflect the updated data efficiently when the system moves
to a higher gear.
In previous studies [7], we conducted a simple evaluation of Rabbit and PARAID [2] to identify an appropriate
data placement approach to support efficient gear-shifting in
power-proportional systems. PARAID uses a skewed pattern
to replicate and stripe data blocks to the disks. This facilitates
adaptation to the system load by varying the number of active
disks in the system. PARAID focuses only on the RAID unit
and it is unreliable when adapting to a distributed environment.
We also proposed an architecture known as NDCouplingHDFS [8] to facilitate the efficient reflection of updated
data in a power-proportional HDFS. NDCouplingHDFS focuses on coupled metadata management and data management
on each HDFS node, which localizes the range of data maintained by the metadata in an efficient manner. This reduces
the cost of managing the metadata generated during changes inthe system configuration. However, the data placement method
was not considered in this study.
Other studies, rather than power-proportional designs, haveaimed to reduce the total power consumption based on a tradeoff with performance in general storage system [9]–[12].

III.

P ROPOSED M ETHOD

In this section, we describe the data placement method usedby Accordion in detail. Next, we explain the load balancer,
which aims to distribute the workload among all of the active
nodes and provide power proportionality. Finally, we present
the processes that reflect updated data, which are written to thesystem in a low gear, when the system performs gear-shifting.

Gear 2

Algorithm 1 Algorithm used to assign roles to nodes in thecluster.
Input: All the nodes of the system which are organized in G groups (N odeig , g ∈[1, G], i ∈ [1, Ng ])Output: Role(N odeig )1: for Groupg from Group1 to GroupG do
2:
if Ng is even thenN3:
middle = 2g4:
for i from middle to 1 do
5:order = middle − i + 1
6:Role(N odeig ) = Lef torderg7:
end for8:
for i from middle + 1 to NG do
9:order = i − middle
10:
Role(N odeig ) = Rightorderg11:
end for12:
else if Ng is odd thenN
13:
middle = 2g + 1
14:
for i from middle to 1 do
15:order = middle − i + 1
16:Role(N odeig ) = Lef torderg17:
end for18:
for i from middle to NG do
19:order = i − middle
20:
Role(N odeig ) = Rightorderg21:
end for22:
end if
23: end forGear 1

Role

Node21

Node22

Node23

Node24

Node11

Node12

Node13

Node14

Node25

Node26Node27

Node28

Left24

Left23

Left22

Left21

Left12

Left11

Right11

Right12

Right21

Right22

Right23

Right24

Left2

Like other approaches, Accordion aims to control thepower consumption of the system by dividing the nodes ina cluster into several separate groups. A system that uses
the Accordion data placement layout can then operate in a
multigear mode where each gear contains a different numberof groups. The higher gears have more groups of nodes.
Power proportionality is achieved by Accordion’s data
placement policy, which is based on skewed replication, and acareful consideration of the effects of reflecting the modified
dataset when the system moves from low to high gears. The
data placement policy is described in detail in the following
parts and the symbols used are summarized in Tab. I.
1) Node role assignment: In a system that uses Accordion,changes in the operational modes of nodes are associated withchanges in the shape of the bellows of an Accordion (musicalinstrument) after adjusting for effects on the transitions of anote or between multiple notes. When the system moves up tohigher gears or down to lower gears, the active node ranges
are expanded or reduced centrally.
In our method, the nodes are arranged geometrically in ahorizontal array because the nodes that belong to lower groups
are bounded by the nodes of higher groups. Groupm is higher
than Groupn if m > n. For example, we assume that a systemis operating in a two-gear mode with two groups of nodes, i.e.,
Group1 and Group2 . The nodes from Group1 are activated inGear 1 and the nodes from Group1 and Group2 are turned on

Right1

Right2

Fig. 1. Example of a two-gear system using Accordion where two groups
of nodes have roles, where G = 2, N1 = 4, N2 = 8, and N = 12.

in Gear 2. In this case, Group2 is higher than Group1 . Thus,
the nodes of Group1 are bounded by the nodes of Group2 .
To perform data replication among the nodes in the system,
i.e., to identify the destination nodes for storing the backup
data of a specific node, each node is assigned its correspondingrole in the group. The role of each node is determined by theconfiguration, which is related to the number of groups andthe total number of nodes in each group. The algorithm used
to assign the roles to nodes is shown in Algorithm 1:

A. Accordion design
Accordion was designed to provide power proportionality
and a high data I/O throughput in cluster file systems thatuse commodity computer servers such as HDFS, Google File
System [13]. In Accordion, the files are divided into a large
number of blocks and a number of replicas of each data blockare distributed among the nodes of the cluster. The mapping of
the file names to block identifiers is maintained by a separate
metadata service.

Left1

Role(N odeig ) = P artorder
,
g

(1)

where P art is either Lef t or Right and order ∈ [1, Ng + 1].
Definition 1: For a GroupgA that contains an odd numberof nodes (NgA is an odd number), there is a node that has tworoles, i.e., Lef t1gA and Right1gA .
An image of a multigear system using Accordion withorganized nodes and roles are shown in Fig. 1. Gear 1 requires
the nodes from Group1 (a set of Lef t1 and Right1 ) to be
activated while Gear 2 requires the nodes from both Group1
and Group2 to be activated.
2) Skewed data replication in Accordion: The three goalsof Accordion are to provide power proportionality in the read
performance, reduce the cost of reflecting updated data when
the system changes gear, and guaranteeing the data reliability
in all file system operating modes. Thus, we need to apply thepolicies shown below to satisfy these goals.
a) Location of primary data: First, we distribute theprimary data in the dataset to all of the nodes in the system.
This means that each node stores the same amount of data.
b) Location of backup data: Starting with the highest
GroupG , we replicate the data stored in this group to thenext lower group GroupG−1 . Thus, the node with the role
P artorderG−1 in GroupG−1 is allocated to the backup data forthe data from the nodes in GroupG , which have roles in thefollowing range, if they exist.
(middle−order)rateG +1[P artG(middle−order+1)rateG, P artG],

G
where P art is Lef t or Right, rateG = NNG−1, andmiddle = N

G2⌊ N2G ⌋ + 1

NG is even
NG is odd(2)

For example, in Fig. 1, the data from the range [Lef t32 ,Lef t42 ] are replicated in the node with the role Lef t21 . ThisTABLE I.
SymbolN
GGroupgNg
N odeigRole(N odeig )Lef tgRightgB
V (B)
V (B)gDescription
Number of nodes in the cluster
Number of groups in the cluster
A group of nodes with index g (g ∈ [1, G])
Number of nodes in group Gg
A node with index i in group Gg (i ∈ [1, Ng ])orderi, where P art is Lef t or Right
The role of a node N odeig , is P artgi
Lef tg = ∀N odeg ∈ Groupg , Role(N odeig ) = Lef tg order
Rightg = ∀N odeig ∈ Groupg , Role(N odeig ) = Rightorderg
Total number of blocks in a dataset
Storage requirements to store a dataset with B blocks
Storage requirements to store a dataset with B blocks in Groupg

Group3 are replicated in Group2 and the data in Group2 are
replicated in Group1 . Finally, the chained declustering method
is used to replicate the data in Group1 . Thus, the three groups
contain 1200, 400, and 200 blocks.

Chained declustering
replicate700

replicate

Number of blocks

600
B6

B1

B5

B2

B4

B3

B1

B6

B2

B5

3) Storage requirements: This section describes the total
storage requirements for storing a dataset based on the skewed
data replication policy used by Accordion. The total of blocks
in a dataset is B and there are G groups, where each groupcontains Ng nodes. The total amount of data blocks V (B)stored is calculated as:

500
400
replicate300

replicate

200
B1

N OTATIONS

P6

V (B) =

100
P1

P2

P3

P4

P5

P6

Gear 2

-

○

○

○

○

-

Gear 3

○

○

○

○

○

○

Fig. 2.
An example of a three-gear system based on Accordion data
placement.

The process is finished when the backup data for the nodes
in Group2 are replicated to the nodes in Group1 .
c) Chained declustering at the smallest group: To
guarantee the data reliability in the lowest gear, we apply thechained declustering policy to the smallest group (Group1 ).
Each node replicates its data to its neighbor node, whichguarantees that all of the data in the dataset are replicated in
the two neighbor nodes. In Fig. 1, the data (the primary data
and the backup data) in N ode11 are replicated in N ode21 , thenfrom N ode21 to N ode31 , and so on. In other power-proportional
approaches, the data reliability in the lowest gear is often
omitted because the data are not replicated.
Figure 2 shows an example of a three-gear system basedon Accordion data placement where B = 600, G = 3, andN = 60 (N1 = N2 = N3 = 20). Groupi contains the nodes ofLef ti and Righti . Gear 1 contains only the nodes in Group1 .
To serve a request, Gear 2 requires the nodes in Group1 andGroup2 to be activated, while Gear 3 requires all of the nodes
in Group1 , Group2 , and Group3 to be activated. The primarydata in 600 blocks are stored equally among all of the nodes
so each group locates 100 blocks initially. Next, the data in(3)

where V (B)g is the number of data blocks located on thenodes of Groupg . Initially, all of the blocks are stored equally
among all of the nodes in the cluster so V (B)G = B × NNG ,PG
where N =g=1 Ng is the total number of nodes inthe system. In addition to the original data, the nodes inGroupG−1 are also used to locate the replication data fromthe nodes in GroupG . Thus,
V (B)G−1 = B

means that the data in N ode12 and N ode22 are replicated in
N ode11 .

V (B)g ,g=1

0

Left2 22Left
Right
1 Left
4 73 10 131619
25 28
34 37140Right
43464955 58
1 31Right
2 52
3
○
○
Gear 1

G
X

NG−1
NG
NG−1
NG
+B
= B(
+
).
N
N
N
N

(4)

The amount of data in the remaining groups from Group(G-2) to Group 1 are similarly calculated. Finally, chained
declustering is applied to Group1 so the storage required byGroup1 is as follows:G

V (B)1 = 2

B X
Ng ) = 2B.
(
N g=1

(5)

Substituting the values of V (B)g , (g ∈ [1, G]) into (3)yields the following:
V (B)

=

B(2 +

=

B

G−i+1
X Ni
NG
NG−1
NG
+(
+
) + ... +
)
N
N
N
N
i=2

G
X
(g + 1)Ng
g=1

N

.

(6)

4) The amount of data transferred during gear-shifting:In this section, we calculate and compare the amount ofdata that is transferred internally when the system changes
its configuration using Accordion and other methods such as
Rabbit and Sierra. In such methods, as each group contains one
replica of the dataset, the entire updated dataset is transferred

Normalized amount of transfering data

1.4
1.2

I/O performance as current hard disk drives normally makeuse only part of the capacity other than full of the capacity
to provide the I/O requests. Given that the amount of unused
storage is increasing [14] and that the energy problem is agreater focus, the provision of smooth gear-shifting is more
important when delivering power-proportional systems.

Rabbit or Sierra (G=5)
Accordion (G=5, scale=3)
Accordion (G=5, scale=2)
Accordion (G=5, scale=1)

1
0.8
0.6
0.4
0.2

0
Gear 1 to Gear 2 Gear 2 to Gear 3 Gear 3 to Gear 4 Gear 4 to Gear 5

Fig. 3. The normalized amount of data transferred when gear-shifting is
performed in each gear

during each gear-shifting. In Accordion, however, shifting
between each gear in the system only leads to variation in the
subpart of the dataset located on the nodes that are reactivatedduring transitions.
From the calculations in Section III-A3, the amount of data
moved when the system changes from Gearg to Gearg+1 is,GXNiVg (D) = D
,
N
i=g+1

(7)

where G is the number of groups, Ni is the number of active
nodes in Groupi , N is the total number of nodes, and D
is the number of blocks updated in the dataset in Gearg . A
constraint on Accordion is that the preferred number of nodes
in Groupg is a multiple of the number of nodes in Groupg−1 .
To evaluate this further, we consider a simple case where ∀g ∈N
[1, G], Ng+1
= scale (scale ≥ 1). Substituting into (7), wegobtain the following:PG

i=g+1 scale

Vg (D) = D PG−1
i=0

scaleii.

(8)

Figure 3 shows the amount of data moved, which was
normalized against the amount of the dataset that was updated
during each gear shift with Accordion and other methods(Rabbit and Sierra), where the systems were configured tooperate using five gears. The amount moved was always
smaller in Accordion than Rabbit or Sierra and it became
smaller when the system performed gear-shifting in a higher
gear. The degradation of the system performance was reduced
so Accordion may be applicable to smooth gear-shifting in
multigear power-proportional file systems where the numberof gears is high.
5) Skewed dataset distribution in Accordion: The skewed
data replication in Accordion leads to an imbalance in theamount of data stored on each node. Like in Rabbit andSierra, some nodes (in the smaller groups) store considerably
more data than others (in the higher groups). However, thisimbalance does not lead to considerable problem to the overall

6) Physical data placement on a node using Accordion:
In Accordion, each node stores the primary data (the original
data allocated) and the backup data (replicas of the data fromother nodes) so the physical locations of these two types ofdata in the disks should be well designed. Normally, the data
are stored physically in a number of sectors of the disks.
The complexity of writing and replicating the data meansthat the orderless arrival timing of writing requests on eachnode promotes the discreteness of the physical locations of
the sectors for the primary and backup data on the disks.
However, on current disks, the seek time required to allocate
the responsible sectors still degrades the I/O performance
greatly, especially for discretely located sectors. Therefore, itis preferable to allocate the responsible sectors to sequential
locations on the physical disks.
In this paper, we also propose an optimized version of Accordion known as Accordion-with-Disk-Partition (AccordionDP) that uses a partitioning technique on each node, whichguarantees that the primary data and backup data will belocated in two separate parts of the disks. Thus, the physicallocations of the sectors from the primary and backup data ineach part are allocated sequentially. For example, in Fig. 2, in
Lef t1 , P3, B1–B2 and B4–B6 are stored in separated partitionsof the disks. Accordion-DP is expected to improve the I/O
throughput performance of file systems because it reduces theseek time on the disks.
B. Load balancer
When a request for a block is received from a client, thefile system has to select the node that will serve the request
because the block is replicated in multiple nodes in the system.
To provide power proportionality when serving a dataset withmultiple blocks, it is preferable to balance the load among allof the available nodes. The load balancing mechanism used in
Accordion is basically the same as that employed by Rabbit.
If n nodes are active when serving a B-block dataset, the goalof the load balancer is to make each node serve B
n blocks.
Similar to Rabbit, we define an ideal value for each nodeB
where N odeig equals n×containi . When the dataset is beinggservedigread, the current hit of the node N odeig is 1×containi , wheregicontaing is the number of blocks stored locally on N odeig , andservedig is the number of blocks already served by N odeig .
From the possible nodes that may store a requested block,the load balancer greedily selects the node where the distance
between the current hit and the ideal value is the largest.

Although this mechanism is similar to Rabbit, the different
policy of locating the primary data makes Accordion preferable
to Rabbit. In Rabbit, each of the replica set of the whole dataset
is stored separately in each group’s node while in Accordion,
there is always part of the dataset that is stored only in thelowest group’s nodes. Consequently, the lowest group’s nodes
can serve the request from the beginning and hence it leads to

Log
2.

Name
Node

1.
E

Node21

A D
B C

E
B
A

C
D

D

Node11 Node12 Node22

Transfer data E

D
C

B C
A D

E
C

Node21

A
B

TM8600 1.0 GHz
DRAM 4 GB
1000 Mb/s
Linux 3.0 64-bit
JDK-1.7.0

E
D

Node11 Node12 Node22

Low GearHigh Gear

1. Write data with Write off-loading
2. Save Write off-loading information log fileFig. 4.

4.

S PECIFICATION OF A NODECPU
Memory
NIC
OS
Java

3.
Name
Node

C

TABLE II.

Log

3. Check Write off-loading log file
4. Transfer temporal data to original nodes

TABLE III.

E XPERIMENTAL ENVIRONMENT

Number of gears
Number of active nodes (Accordion, Accordion-DP)
Number of active nodes (Rabbit)
Number of files
File size
HDFS version
Block size

32, 8, 20
2, 7, 21420
64 MB
0.20.232 MB

Updated data reflection using write off-loading.

less skew in distributing the load among nodes in Accordion
than in Rabbit. It is explained in more detail and clearer in
Sect. IV-C2 through utilizing an empirical experiment.
C. Writing data using write off-loading
When a subset of a group of nodes is deactivated in a
low gear, the system can accept write requests from clientsusing the write off-loading technique. Next, when the systemmoves to a higher gear by reactivating nodes, it transfers the
updated data internally in the background without stopping theprocessing of read serves from clients.
1) Writing new data using the write off-loading technique:
When the system is in a low gear and it has to deal withrequests to write new data to a previously stored dataset, theplacement of data is performed according to its original policy.
Because the system operates in low gear, certain parts of the
new data cannot be written to their corresponding deactivatednodes. Hence, the system selects another node randomly fromthe active nodes to serve this request. Information about thedata, the temporary node, and the intended node are saved
in a log file. An example of the write off-loading process isshown in Fig. 4. In this example, N ode22 should serve the write
request for data E according to the original data placement
policy. However, it is powered off in a low gear so the system
decides to use an alternative node, i.e., N ode11 is selected inthis case.
2) Reflecting updated data: When the system changes to ahigh gear to serve a request for high-performance processing
with the newly updated dataset, it needs to perform twofunctions. The first function is to transfer the data written
in temporary nodes to their actual intended nodes. This canbe achieved by reading the information in the log files. In
Fig. 4, N ode11 is set to transfer data E to N ode22 . The second
function is to serve a request by scanning the new dataset in
the storage system. When there is no need to correct the datalayout, compared with a normal service in a high gear, the costof allowing the system to operate in multiple modes to savepower will depend greatly on the quantity of data that needs
to be transferred.
IV.

E XPERIMENTS

We conducted an empirical experiment using actual machines to verify the methods proposed in this study. We

chose Rabbit which also shares the idea of achieving powerproportionality as the comparative method. First, we compared
Accordion with Rabbit with respect to power proportionality
during the performance of reads. Next, we tested the effectiveness of Accordion for reducing the cost of reflecting updated
data when the system shifted to a higher gear. Finally, weevaluated the power proportionality of Accordion using several
configurations.
A. Implementation
In this study, we implemented a prototype of the powerproportional distributed file system Accordion based on amodified HDFS. We changed the current class used to selectblock locations via an interface where different data-layout
policies can be performed. We also added the load balancing
mechanism in to HDFS. The write off-loading policy was implemented in the low-power mode, which selects the temporal
nodes for writing the new data for the currently turned off
nodes. To guarantee the data reliability, block replicas were
written to distinct nodes in all of the operation modes.
B. Framework used for the experiments
Our test-bed for the experiments comprised dozens ofcommodity nodes, which was based on the HDFS architecturewith one NameNode, and a cluster of nodes for storing data.
We were focused on the energy-aware commodity system
so we used low power consumption ASUS Eeebox EB1007
machines, the specifications for which are provided in Tab. II.
In the experiments, The power consumption of the clusterof data storage nodes was measured using an AC/DC PowerHiTESTER 3334 [15]. The interconnect was a 1000 Mbps
switching hub and all of the inactive nodes were hibernating.
C. Power proportionality of Accordion and Rabbit
We evaluated the effectiveness of Accordion by determining the ratio of the throughput when reading a dataset andthe power consumption of the cluster of data-storing nodes.
In addition to Accordion and Rabbit, we also configured
Accordion-DP to test whether it improved the throughput
performance.
1) Experimental environments: We compared Accordion
and Accordion-DP with Rabbit in terms of their power proportionality when performing reads. These systems were operatedusing a three-gear configuration based on three groups ofNode ID

1.4

RabbitAccordion
Accordion-DP

Throughput per Watt [MB/W]

1.2
1
0.8

20

15

15

10

10

5

5
0
0

0.6

200

400

0
Gear 1

Gear 2
Power setting0

Gear 3

Accordion-DP
Accordion
Rabbit

200

150

100

50

0
0

5

10
15
Number of active nodes

20

800

200

400

600

800

1000

0

9
8
7
6
5
4
3
2
1
0
1000 0

200

400

600

800

1000

Accordion Gear 2

200

400

600

800

1000

Block ID

Fig. 5. Throughput per watt using Accordion-DP, Accordion, and Rabbit
with various power settings.

250

600

Rabbit Gear 2

9
8
7
6
5
4
3
2
1
0

0.4

Accordion Gear 3

25

20

0

0.2

Throughput [MB/s]

Rabbit Gear 3

25

25

Fig. 6. Read performance using Accordion-DP, Accordion, and Rabbit withvarious power settings.

nodes. The constraint on the number of nodes in the gear
configuration meant that the three gears in Rabbit contained
2, 7, and 21 nodes. To ensure a fair evaluation, the three
gears in Accordion and Accordion-DP had 2, 8, and 20 nodes.
The scanning workload was distributed uniformly from all of
the active nodes. The other information can be referred from
Tab. III.
2) Experimental results: Figure 5 shows the throughput
per watt to compare the read performance using the aforementioned dataset with three power-setting modes: Gear 1,
Gear 2, and Gear 3. The results were the averages of fiveruns and the Linux buffer cache was cleared between runs.
Of the three configurations, Accordion-DP yielded the best
results whereas Rabbit had the worst results in Gear 2 andGear 3. In Gear 3, Accordion-DP delivered 20% better results
than Rabbit because it gained better throughput as can be seenin Fig. 6 which shows the average throughputs for the three
configurations. The reason was that the better load balancer in
Accordion-based increased the throughput while consuming
less power (20 nodes vs 21 nodes in Rabbit).

Fig. 7. Distribution of timing on the nodes when serving the blocks in Gear
2 and Gear 3 using Rabbit and Accordion.

The load balancer was the same in all configurations so
the differences may be explained by the timing distribution
when each node served the requested blocks. Figure 7 shows
the results for Rabbit and Accordion in Gear 2 and Gear 3. Ineach graph, the vertical axis is the NodeID while the horizontal
axis shows the BlockID of the dataset. In Rabbit, the nodes inranges [1, 2], [3, 7] and [8, 21] consequently belong to Group1 ,Group2 and Group3 . In Accordion, the corresponding ranges
are [1, 2], [3, 8] and [9, 20]. It is easy to recognize that the
distribution of the access to blocks was far more balancedwith Accordion than Rabbit. In Rabbit and Accordion, theload balancer tended to transfer the workload to the nodes
in the outbound group, which could be turned off when thesystem operated in a lower gear. Rabbit stored the replicasof the dataset in group units, i.e., Group1 stored the primarydata, Group2 stored the secondary replicas, etc., so certain
groups of nodes were selected centrally by the load balancer
when scanning the dataset. By contrast, the skew of the timing
distribution was lower when selecting nodes to serve therequests using Accordion. This is because Accordion allocatedthe primary data among all of the nodes in the system initiallyso some data were only stored in the low group. Thus, theactive nodes in these groups could be selected to serve therequested files from the start of the scanning process.
In this experiment, the benefit of the partitioning technique
for separating the primary and backup data areas on nodes
was confirmed as Accordion-DP gained better results thanAccordion. From the latter experiments, Accordion-DP wasused to evaluate the effectiveness of Accordion.
D. Effect of reflecting the updated data on the performanceThis experiment evaluated the effect of reflecting the
updated data when the system served read requests while
performing updated data reflection in the background.
1) Experimental method: First, part of a similar dataset tothat used in the above experiment was written to the system
while the system operated in Gear 3. The operation mode of
the system was then shifted down to Gear 2 by hibernating
the nodes of Group3 . Next, the remaining parts of the dataset
were written to the file system using the data-layout policy

250

16000

RabbitAccordion-DP

14000

RabbitAccordion-DP

200

Datasize [MB]Throughput [MB/s]

12000
150

100

10000
8000
6000
4000

50
2000
0

0

Fig. 8.

Small
MediumConfiguration

Large

Average throughput for scanning the dataset.

with the write off-loading technique. Finally, after finishing
the write requests, the system moved to Gear 3 by reactivating
the nodes of Group3 at the same time as it served the scanningworkload, which was generated in a similar way to that usedin the experiment above. The execution time for serving theread requests was measured to verify the effect of updated data
reflection on the file system. Here, the total number of files
used in the dataset was 420 and each file contained two blocks,
which was the same as the experiment above. We also changed
the sizes of the parts of the dataset written when the system
operated in Gear 2 to 140, 280, and 420 files (small, medium,and large update configurations, respectively). In each case, thenumber of files written previously when the system operated
in Gear 3 was 700, 560, and 420, respectively, so there wasno need to re-transfer these files.
2) Experimental results: Figure 8 shows the experimental
results as the average throughput while scanning the dataset inthree cases: small, medium, and large amounts of transferred
data. The results were compared with the results when thesystem performed the read requests in Gear 3 (without updateddata), which were the same as the previous experiment. It isseen that configurations based on Accordion-DP and Rabbit
were affected significantly by the updated data reflection. The
throughputs were degraded significantly by more than 60%(66% and 61% for Rabbit and Accordion-DP). It became worsewith higher amounts of re-transferred data. This confirmed theneed to design the data placement method carefully to ensure
efficient gear-shifting in power-proportional file systems.
The results also indicated that Accordion-DP improved theperformance by 30% compared with Rabbit. The reason iswith Accordion-DP, the amount of data re-transfer required
was less than that with Rabbit. With Accordion-DP, only partof the dataset written when the system operated in Gear 2
had to be re-transferred when the system moved to Gear 3.
By contrast, the whole dataset had to be re-transferred with
Rabbit as the placement policy located replicas of the dataset
in each group.
Figures 9 and 10 show the amounts of re-transferred data
and the execution times required to finish the re-transfer
process. Figure 9 shows that with Rabbit, the amounts of datain the small, medium, and large cases were 4480 MB, 8960

Small

MediumConfiguration

Large

Fig. 9. The amount of data that had to be re-transferred when the system
moved from Gear 2 to Gear 3.
450
400
Updated data reflection time [s]Without
Updated Data

RabbitAccordion-DP

350
300
250
200
150
100
50
0
Small

MediumLarge

Configuration

Fig. 10. The execution time for the data-re-transfer process when the system
moved from Gear 2 to Gear 3.

MB, and 13440 MB; while with Accordion-DP were 2688 MB,
5376 MB, and 8064 MB, respectively. As shown in Figure 10,
Accordion-DP significantly reduced the time required to finish
the updated data-re-transfer process by up to 66% (Small case)compared with Rabbit.
E. Effects of different configurations of Accordion
We also performed an experiment to evaluate the effects
of different configurations of Accordion on the power proportionality of the system. We used three configurations withdifferent numbers of active nodes. The system was assumed tooperate in a three-gear mode: Gear 1, Gear 2, and Gear 3. In
the configuration Accordion-DP (x, y, z), x, y, and z indicate
the number of active nodes in Gear 1, Gear 2, and Gear 3,
respectively. The other environments were the same as thoseused in the previous experiment in Tab. IV.
Figure 11 shows the performance (throughput per watt) for
the three configurations we evaluated. With a larger scale configuration, the power-proportional factor appeared to converge
on a high result. In all configurations, the factor increased from
Gear 1 to Gear 3 because the number of active nodes increased.

TABLE IV.

E XPERIMENTAL ENVIRONMENT

Number of Gears
Number of active nodes Accordion-DP (4, 8, 12)
Number of active nodes Accordion-DP (4, 12, 20)
Number of active nodes Accordion-DP (8, 16, 24)
Number of files
File size

Accordion prototype verified the effectiveness of Accordion.
Accordion reduced the execution time required for updated
data movement by 66% and improved the power-proportional
performance by 20% compared with Rabbit. Furthermore, thenumerical analysis and the experimental results also indicatedthat Accordion is applicable for smooth gear-shifting in multigear systems.
In the future, we would like to confirm the effectiveness of
Accordion in different experimental environments. Moreover,
we want to integrate Accordion with architectures other than
HDFS. We will also consider developing a specific algorithm
to deal with system failures.

Accordion-DP (4, 8, 12)
Accordion-DP (4, 12, 20)
Accordion-DP (8, 16, 24)

1.4
Throughput per Watt [MB/W]

34, 8, 124, 12, 20
8, 16, 24
420
64 MB

1.2
1
0.8

ACKNOWLEDGMENTS

0.6

This work was supported partly by Grants-in-Aid for
Scientific Research from the Japan Science and Technology
Agency (A) (#22240005).

0.4
0.2

R EFERENCES
0
Gear 1

Fig. 11.
tions.

Gear 2
Power setting

Gear 3

The throughput per watt with Accordion-DP in several configura-

Furthermore, from the results at three gears, Accordion-DP(4, 12, 20) experienced the worst standard deviation (0.114
compared with 0.04 and 0.08 in Accordion-DP (8, 16, 24) and
Accordion-DP (4, 8, 12), it could be suggested that Accordion
is more suitable with the configuration that the number ofactive nodes in each group is equal.
F. Discussion
The data placement strategy used by Accordion ensureshigh power-proportionality performance of systems, especiallywhen systems operate in a high gear mode with a larger amountof active nodes. In Accordion, the amount of data requested
and the access timing of the active nodes are well distributed
among all the active nodes so the I/O throughput performancescales well with the system’s size. Furthermore, Accordion was
highly effective at reducing the cost of gear-shifting because
it improved the performance by 66% when transferring the
updated data. The numerical analysis in Sect. III-A4 showedthat the efficiency was even greater when gear-shifting was
performed in a higher gear.
V.

C ONCLUSION AND F UTURE W ORK

Recently, energy-efficient infrastructures for Big Data processing are gaining much attention from both industrial andacademia. In this paper, we identified the issue of ineffective
gear-shifting in power-proportional distributed file systems andwe proposed the Accordion data placement method to address
this problem. Furthermore, the Accordion configuration ishighly flexible because the number of nodes in each groupcan be determined by a weak constrain. In Accordion, thedata reliability in the lowest configuration which is omitted
in other methods, is ensured through utilizing chained declustering. Extensive experiments using actual machines with the[1] L. A. Barroso and U. Hölzle, “The Case for Energy-proportional
Computing,” Computer, vol. 40, pp. 33–37, 2007.
[2] W. Charles, O. Mathew, Q. Jin, W. A.-I. Andy, R. Peter, and K. Geoff,“PARAID: A Gear-shifting Power-aware RAID,” ACM Transaction on
Storage, vol. 3, 2007.
[3] E. Thereska, A. Donnelly, and D. Narayanan, “Sierra: Practical Powerproportionality for Data Center Storage,” in Proc. the 6th European
Conference on Computer Systems. ACM, 2011, pp. 169–182.
[4] A. Hrishikesh, C. James, G. Varun, G. Gregory R., K. Michael A.,
and S. Karsten, “Robust and Flexible Power-proportional Storage,” inProc. the 1st ACM Symposium on Cloud Computing. ACM, 2010, pp.
217–228.
[5] Apache Hadoop, “HDFS Hadoop Wiki,” http://wiki.apache.org/hadoop/
HDFS.
[6] D. Narayanan, A. Donnelly, and A. Rowstron, “Write Off-loading:
Practical Power Management for Enterprise Storage,” ACM Transaction
on Storage, vol. 4, no. 3, pp. 10:1–10:23, 2008.
[7] H. H. Le, S. Hikida, and H. Yokota, “An Evaluation of Powerproportional Data Placement for Hadoop Distributed File Systems,” inProc. Cloud and Green Computing. IEEE Computer Society, 2011,
pp. 752–759.
[8] H. H. Le, S. Hikida, and H. Yokota, “NameNode and DataNode
Coupling for Power-proportional Hadoop Distributed File System,”in Proc. the 18th International Conference on Database System for
Advanced Applications, Part II. Springer Verlag, 2013, pp. 99–107.
[9] B. Mao, D. Feng, H. Jiang, S. Wu, J. Chen, and L. Zeng, “GRAID:
A Green RAID Storage Architecture with Improved Energy Efficiency
and Reliability,” in Proc. IEEE International Symposium on Modeling,
Analysis and Simulation of Computers and Telecommunication Systems,
2008, pp. 1–8.
[10] J. Leverich and C. Kozyrakis, “On the Energy (In)efficiency of Hadoop
Clusters,” SIGOPS Operating System Review, vol. 44, pp. 61–65, 2010.
[11] R. T. Kaushik and B. Milind, “GreenHDFS: Towards an Energyconserving, Storage-efficient, Hybrid Hadoop Compute Cluster,” inProc. the 2010 International Conference on Power Aware Computing
and Systems. USENIX, 2010, pp. 1–9.
[12] J. Kim and D. Rotem, “Energy Proportionality for Disk Storage using
Replication,” in Proc. the 14th International Conference on Extending
Database Technology. ACM, 2011, pp. 81–92.
[13] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The Google File System,”in Proc. the 19th ACM Symposium on Operating Systems Principles.
ACM, 2003, pp. 29–43.
[14] J. Gray, “Greetings from a Filesystem User,” in Proc. the fourth USENIX
Conference on Files and Storage Techniques. USENIX, 2005.
[15] “AC/DC Power HiTester 3334,” http://www.hioki.com/product/3334/
index.html.