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

Accordion: An Efficient Gear-Shifting for a Power-Proportional
Distributed Data-Placement Method

Authors

Hieu Hanh Le, Satoshi Hikida, Haruo Yokota

出典 / Citation

IEICE Transactions on Information and Systems, Vol. E98-D, No. 5,
pp. 1013-1026

発行日 / Pub. date2015, 5URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2015 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Science Tokyo Research Repository)

IEICE TRANS. INF. & SYST., VOL.E98–D, NO.5 MAY 2015

1013

PAPER

Special Section on Data Engineering and Information Management

Accordion: An Eﬃcient Gear-Shifting for a Power-Proportional
Distributed Data-Placement Method∗∗
Hieu Hanh LE†∗a) , Satoshi HIKIDA† , Nonmembers, and Haruo YOKOTA† , Member

SUMMARY
Power-aware distributed file systems for eﬃcient Big Data
processing are increasingly moving towards power-proportional designs.
However, current data placement methods for such systems have not given
careful consideration to the eﬀect of gear-shifting during operations. If
the system wants to shift to a higher gear, it must reallocate the updated
datasets that were modified in a lower gear when a subset of the nodes
was inactive, but without disrupting the servicing of requests from clients.
Ineﬃcient gear-shifting that requires a large amount of data reallocation
greatly degrades the system performance. To address this challenge, thispaper proposes a data placement method known as Accordion, which uses
data replication to arrange the data layout comprehensively and provide efficient gear-shifting. Compared with current methods, Accordion reduces
the amount of data transferred, which significantly shortens the period required to reallocate the updated data during gear-shifting then able to improve the performance of the systems. The eﬀect 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 thesystem therefore our proposed method is expected to work well in practical environments. Extensive empirical experiments using actual machineswith an Accordion prototype based on the Hadoop Distributed File Systemdemonstrated that our proposed method significantly reduced the periodrequired to transfer updated data, i.e., by 66% compared with an existing
method.
key words: energy-aware, power-proportionality, data-placement, HDFS

1.

Introduction

In the era of Big Data, distributed file systems, such as
Google File System [2] and Hadoop Distributed File System (HDFS) [3], have been widely used for eﬃcient processing over a huge amount of unstructured data. In such
systems, not only high performance but also power consumption have gained much attention from both academia
and industry. Among this, power-aware distributed file systems are progressively moving towards power-proportional
design [4]. The power-proportionality in these systems canbe achieved using well designed data placement methods tocontrol the total number of active nodes to store and retrieve
the data [5]–[7]. The common idea in these methods is to
Manuscript received July 27, 2014.
Manuscript revised November 28, 2014.
Manuscript publicized January 21, 2015.
†
The authors are with the Department of Computer Science,
Tokyo Institute of Technology, Tokyo, 152–8552 Japan.
∗
Presently, with Yokohama Research Laboratory, Hitachi Ltd.
∗∗This paper is an extended version based on our paper proposed in BigData 2013 [1].
a) E-mail: hanhlh@de.cs.titech.ac.jp
DOI: 10.1587/transinf.2014DAP0007

carefully place the data’s replicas at organized nodes. 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 diﬀerent number ofgroups, and oﬀers a diﬀerent level of parallelism and aggregate IO [5]. A higher gear has a larger number of groupsof active nodes. For example, if there is a 30-node system
which is managed to operate in three gears. Gear 1 contains
10 active nodes, Gear 2 contains 20 active nodes and Gear
3 contains 30 active nodes. Accordingly, in a higher gear,
the system consumes more power, although it can deliver
higher performance with suitable processing. Leveraging
this mechanism, the system can manage its power consumption and performance so it can deliver power proportionality.
However, the current power-proportional data placement methods do not well consider the eﬀects of gearshifting on the performance of the system. During operations, the system may have to update the datasets modified in a low gear when a subset of the nodes was powered
oﬀ. When the system moves to a higher gear to gain a better power-proportionality by reactivating inactive nodes, itneeds to provide the new power proportionality in serving
the requests from clients. Therefore, in the background,the system has to internally re-transfer the updated data
to the reactivated nodes to share the load equally among
all of the active nodes in order the obtain better performance. Ineﬃcient gear-shifting with the large amount of
re-transferred data is believed to greatly degrade the performance of power-proportional distributed file systems.
To address this problem, in this paper, we propose
an eﬃcient and flexible power-proportional data placement
method known as Accordion, which aims to improve theeﬃciency of gear-shifting by reducing the amount of retransferred data. Accordion shares the node organization ofother methods because it supports a multigear operationalmode where each gear is combined from diﬀerent numbersof diﬀerent groups of nodes. However, the locations of the
primary data in the dataset are diﬀerent 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
replicated so each of its replicas is located on nodes that belong to diﬀerent groups. As the primary data are locatedat all nodes, 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. Hence, only
the remainder of the updated dataset, which can be assumed
to be written to the deactivated nodes, needs to be written

c 2015 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. INF. & SYST., VOL.E98–D, NO.5 MAY 2015

1014

temporally. Consequently, only this temporal part of the
updated dataset needs to be re-transferred when the systemshifts to a 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 ofdata movement.
Furthermore, the eﬃciency of this reduction is increased when gear-shifting is performed in a high gear.
In such situation, with a lower number of inactive nodes,
the amount of data reallocated is reduced, then shortens
the gear-shifting period further. It restricts the degradationof the system performance when Accordion-based systems
shift to a higher gear. Consequently, Accordion is capable of providing smooth gear-shifting for multigear powerproportional distributed file systems. This feature of Accordion is well analyzed by numerical analysis and verified
through our empirical experiments.
Moreover, 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 the active nodes to serve the same amount of datawhen responding to requests. However, another importantfactor that highly aﬀects the performance of the file systemis 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 20
GB of data, generally it would be more eﬃcient if two nodes
served 10 GB simultaneously rather than sequentially. The
diﬀerent locations of the primary data mean that Accordion
can both balance the amount of data requested and the service timing on the active nodes. It is observed through ourempirical experiments based on actual machines.
Additionally, it is easier to apply Accordion in a practical environment as the configuration, such as the number ofactive nodes in each gear, is more flexible. Although Rabbit [6] is the first method to achieve power proportionality
in a HDFS, in addition to the ineﬃcient gear-shifting due
to the large amount of moving data, it also has a strict constraint where the number of nodes in each group is definedby an exponential function. In Accordion, this constraint ismore flexible because there is only a simple constraint thatthe total number of nodes in the system should be an evennumber.
Last but not least, it is recognized that the advantage of
Accordion is vital especially for commodity-oﬀ-the-shelfbased systems in which the power consumption has not been
well optimized. In such systems, the power consumption of
the systems generally has not gained enough support frommodern technologies such as low energy CPU, memory or
disk. For example, the power consumption of the investigated file server in idle time is still large compared with inactive time (more than 75% as in [8]).
Our contributions are summarized as follows.
• We propose a distributed data placement method
known as Accordion, which utilizes data replication

to deliver eﬃcient gear-shifting in power-proportional
distributed file systems. The diﬀerent 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 performanceeﬃciency when gear-shifting is performed in a higher
gear.
• Accordion increases the I/O throughput performance
because it improve the parallelism eﬀectively 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.
• In order to evaluate the eﬃciency of Accordion, we
performed extensive empirical experiments using amaximum of 24 nodes with an Accordion prototype on
HDFS, which is widely used as the distributed file systems to support MapReduce [9] for eﬃcient Big Data
processing. The empirical experimental results showedthat Accordion significantly improved the performanceby 66% compared with Rabbit and Sierra [7], two of
the most standard power-proportional data placement
methods.
This paper is an extended version of [1] as it included
the important parts of reporting the empirically experimental results which show the applicability of Accordion to provide the smooth gear-shifting in high-gear distributed filesystems. Furthermore, the high eﬃciency of Accordion relating to the time to reallocate data is furthered comparedwith Sierra, which was newly implemented to HDFS.
The remainder of this paper is organized as follows.
Related studies are discussed in Sect. 2 and the design of
Accordion is described in Sect. 3. Section 4 presents a performance evaluation of our proposed method. Our conclusions and future work are discussed in Sect. 5.
2.

Related WorkIn this section, at first we reviewed some of the existing data
placement methods in the field. Then, we described in moredetail Rabbit and Sierra because they are used as comparative methods in the experiments.
Rabbit [6] 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 basedon 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. Eachnode in the subsets has a fixed order and it stores a numberof blocks that is inversely related to its order, which guarantees that the system can distribute the workload equally
among all of the active nodes. However, Rabbit still does
not support the write workload so it cannot consider the costLE et al.: ACCORDION: AN EFFICIENT GEAR-SHIFTING FOR A POWER-PROPORTIONAL DISTRIBUTED DATA-PLACEMENT METHOD

1015

of reflecting the updated data in a low gear.
Sierra [7] was designed as a power-proportional distributed storage system for general data centers where areplicated 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 oﬀ-loading [10], which was motivated originally by the aim of saving power by spinning 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 spin-down duration,
thereby providing additional power savings. This method
may be considered as a solution for multigear file systems
to deal with updated data in a low gear. Sierra can deal withwrite requests in a low gear, but it is still not optimized toreflect the updated data eﬃciently when the system moves
to a higher gear.
In previous studies [11], we conducted a simple evaluation of Rabbit and PARAID [5] to identify an appropriate
data placement approach to support eﬃcient 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 numberof 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 [12], [13] to facilitate the eﬃcient reflectionof updated data in a power-proportional HDFS. NDCouplingHDFS focuses on coupled metadata management anddata management on each HDFS node, which localizes therange of data maintained by the metadata in an eﬃcientmanner. This reduces the cost of managing the metadata
generated during changes in the system configuration. However, the data placement method was not considered in thisstudy.
Other studies, rather than power-proportional designs,
have aimed to reduce the total power consumption based ona trade-oﬀ with performance in general storage system [14]–[17].
GRAID [14] is similar to PARAID because it is also agreen storage architecture that aims to improve the energy
eﬃciency and reliability of a RAID unit. In this study, thedata-mirroring redundancy of RAID10 has been extended
by incorporating a dedicated log disk, which stores all of
the updates since the last mirror disk update. Using thislog disk information, the system only needs to update themirroring disks periodically so it can spin down all of themirroring disks in a low-power mode for most of the time,
which saves energy.
Kim et al. [17] proposed a fractional replication method
to balance the power consumption and system performance.
In this method, the data placement layout was inspired by
PARAID where fractional replication and downshifting of
the operational modes to a lower gear saved power using aprobabilistic prediction model based on historical observations.

One of the first attempts to improve the energy eﬃciency of HDFS was performed by Leverich et al. [15] who
showed that it was possible to recast the data layout and task
distribution of HDFS to allow significant portions of a cluster to be powered down while still fully operational. They
also confirmed that the energy could be conserved at the expense of performance so there was a trade-oﬀ between thetwo.
Later, Kaushik et al. [16] proposed an energyconserving multiple zone approach for HDFS, which utilized life cycle information as data. They divided the storage clusters of the HDFS into hot and cold zones. The frequently accessed data were placed in the hot zone where
all of the data nodes were active so they consumed power.
The less frequently accessed data were placed in the coldzone, which allowed data nodes to be inactive. Thus, thepower consumption was lower in the cold zone than in the
hot zone. Some power savings were achieved in HDFS using this method. These techniques are able to be combinedwith our method.
2.1 Rabbit
Rabbit is a data placement for a power-proportional distributed file system that uses a data replication to control
the power and performance of the system by achieving thethe equal–work-policy in which the workload is evenly distributed among all active nodes.
In Rabbit, the nodes in the system are divided into a
number of separated groups and the replicas of the dataset
are stored in a group unit. Assume that r replicas of B blocksof dataset D are to be stored in n nodes using G groups.
Here, each node is numbering from 1 to n. Initially, a replicaof all B blocks is evenly stored in the first primary p nodes
in Group1 (also called the primary group). Consequently,
each node in Group1 will contain Bp blocks. The remaining(r − 1) replicas are distributed to the (N − p) nodes such thata node n(g,i) , where g > 2 and p < i ≤ N, stores Bi blocks.
Here, using the constraint of keeping the number of replicas
r small for a fixed number of nodes, Rabbit can guaranteethat the number of blocks stored by the i-th node must not
be less than Bn for all i ≤ n when n nodes are active. Obeying
this constraint makes it possible for the load to be sharedequally among the active nodes. The performance of thesystem is therefore expected to be linear with the numberof powered nodes, thereby fulfill the idea of equal–workpolicy. However, this constraint also leads to the constraintof the number of nodes in groups from Group2 to GroupG ,as the number of nodes in each group is determined throughan exponential function of r and p. The detail calculation
can be found from [6].
Figure 1 depicts a heuristic illustration of a multigear
system with Rabbit data placement. Here, the system has 3groups of nodes and 3 gears. In Gear 1, only the nodes inGroup1 are active. The nodes in Group1 and Group2 areactive in Gear 2. And all the nodes in Group1 , Group2 andGroup3 are power on in Gear 3. The primary replicas of theIEICE TRANS. INF. & SYST., VOL.E98–D, NO.5 MAY 2015

1016

3.

Eﬃcient Gear-Shifting Method

In this section, at first, we describe the replication-based
data placement method used by Accordion in detail. Next,
we explain the load balancer for reads, 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 the system in a low gear, when the system performs gear-shifting.
3.1 Accordion Design
Fig. 1ment.

An example of a three-gear system based on Rabbit data place-Fig. 2ment.

An example of a three-gear system based on Sierra data place-dataset are stored on nodes on Group1 , the second replicas
are maintained by nodes in Group2 and the tertiary replicas
are dedicated to nodes in Group3 . It should noted that thenodes in Group1 stored the same amount of data while theother nodes contain a diﬀerent amount of data.
2.2

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. In Accordion, the files are divided into a large
number of blocks and a number of replicas of each data
block are distributed among the nodes of the cluster. The
mapping of the file names to block identifiers and of theblock to the block’s locations are maintained by a separate
metadata service.
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 diﬀerent 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, anda careful consideration of the eﬀects of reflecting the modified dataset when the system moves from low to high gears.
We describe the data placement policy in detail in the following parts and summarize the symbols used in Table 1.
3.1.1

Node Role Assignment

SierraLike Rabbit, Sierra is also a data placement for a powerproportional distributed file system by leveraging the data
replication. Sierra also organizes the replicas of the dataset
such that, each replica of the dataset is stored in a group of
nodes. The primary replicas are stored on a specific subset of nodes, called primary nodes (Group1 ). Then, thesecondary replicas are stored on a diﬀerent group of nodes(Group2 ) and so on. Sierra diﬀers from Rabbit that each
replica of the dataset is evenly distributed to all the nodes ineach group. As a result, there is no constraint of the numberof nodes in each group like in Rabbit.
Figure 2 shows an illustration of a multigear distributed
file system based on the data placement in Sierra with 3groups of nodes and 3 gears. It is recognized that all nodes
in the same group store the same amount of data, which differs from Rabbit.

In a system that uses Accordion, changes in the operationalmodes of nodes are associated with changes in the shapeof the bellows of an Accordion (musical instrument) after
adjusting for eﬀects on the transitions of a note or between
multiple notes. When the system moves up to higher gears
or down to lower gears, the active node ranges are expanded
or reduced centrally.
In our method, the nodes are arranged geometrically ina horizontal array because the nodes that belong to lower
groups are bounded by the nodes of higher groups. Groupa
is higher than Groupb if a > b. For example, we assume that a system is operating in a two-gear mode with
two groups of nodes, i.e., Group1 and Group2 . The nodes
from Group1 are activated in Gear 1 and the nodes fromGroup1 and Group2 are turned on in Gear 2. In this case,Group2 is higher than Group1 . Thus, the nodes of Group1
are bounded by the nodes of Group2 .
Each node in the system is assigned its corresponding role in the group to perform data replication among thenodes in the system, i.e., to identify the destination nodes forLE et al.: ACCORDION: AN EFFICIENT GEAR-SHIFTING FOR A POWER-PROPORTIONAL DISTRIBUTED DATA-PLACEMENT METHOD

1017
Table 1
SymbolN
GGroupg
Ng
NodeigRole(Nodeig )Le f tg
Rightg
B
V(B)
V(B)g

Notations.

Description
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 ])order
The role of a node Nodeig , is Partg i , where Part is Le f t or Right
Le f tg = ∀Nodeig ∈ Groupg , Role(Nodeig ) = Le f tg orderi
order
Rightg = ∀Nodeig ∈ Groupg , Role(Nodeig ) = Rightg i
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

Algorithm 1 Algorithm used to assign roles to nodes in thecluster.
Require: All the nodes of the system which are organized in G groups (Nodeig , g ∈[1, G], i ∈ [1, Ng ])Ensure: Role(Nodeig )1: for all Groupg from Group1 to GroupG do
2: if Ng is even thenN3:
middle = 2g4:
for all i from middle to 1 do
5:order = middle − i + 1
6:Role(Nodeig ) = Le f tgorder7:
end for8:
for all i from middle + 1 to NG do
9:order = i − middle
10:
Role(Nodeig ) = Rightgorder11:
end for
12: else if Ng is odd thenN
13:
middle = 2g + 1
14:
for all i from middle to 1 do
15:order = middle − i + 1
16:Role(Nodeig ) = Le f tgorder17:
end for18:
for all i from middle to NG do
19:order = i − middle
20:
Role(Nodeig ) = Rightgorder21:
end for
22: end if
23: end forFig. 3 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.

tionality in the read performance, reduce the cost of reflecting updated data when the system changes gear, and guarantee the data reliability in all file system operating modes.
Thus, the below policies are applied to satisfy these goals.
(1)First, the primary data in the dataset are distributed to all of
the nodes in the system. This means that each node storesthe same amount of data.
(2)storing the backup data of a specific node. The role of eachnode is determined by the configuration in terms of the number of groups and the total number of nodes in each group.
Algorithm 1 describes the function used to assign the roles
to nodes:Role(Nodeig ) = Partgorder ,(1)

where Part is either Le f 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
11
and RightgA.
two roles, i.e., Le f tgA
An image of a multigear system using Accordion withorganized nodes and roles are shown in Fig. 3. Gear 1 requires the nodes from Group1 (a set of Le f t1 and Right1 )to be activated while Gear 2 requires the nodes from bothGroup1 and Group2 to be activated.
3.1.2

Location of primary data

Skewed Data Replication in Accordion

The three goals of Accordion are to provide power propor-

Location of backup data

Starting with the highest GroupG , the data stored in thisgroup are replicated to the next lower group GroupG−1 .
orderin GroupG−1 is alThus, the node with the role PartG−1
located to the backup data for the data from the nodes inGroupG , which have roles in the following range, if they
exist.
[PartG(middle−order)scaleG +1 , PartG(middle−order+1)scaleG ],G, andwhere Part is Le f t or Right, scaleG = NNG−1
 NG
NG is even2
middle =(2)NG 2  + 1 NG is odd
For example, in Fig. 3, the data from the range [Le f t23 ,4
Le f t2 ] are replicated in the node with the role Le f t12 . Thismeans that the data in Node12 and Node22 are replicated in
Node11 .

The process is finished when the backup data for thenodes in Group2 are replicated to the nodes in Group1 , thelowest group.
(3)

Chained declustering at the smallest group

Chained declustering has been proved to provide superior

IEICE TRANS. INF. & SYST., VOL.E98–D, NO.5 MAY 2015

1018

disks. The complexity of writing and replicating the datameans that the orderless arrival timing of writing requests
on each node 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, it is 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(Accordion-DP) that uses a partitioning technique on eachnode, which logically locates the primary data and backup
data in two separate parts of the disks. For example, inFig. 4, in Le f t1 , P3, B1–B2 and B4–B6 are stored in separated partitions of the disks. Accordion-DP is expected to
improve the I/O throughput performance of file systems because it reduces the seek time on the disks.
Fig. 4 An example of a three-gear system based on Accordion data
placement.

performance in the event of failure while maintaining a very
high degree of data availability [18]. As a result, to guarantee the data reliability in the lowest gear, the chained declustering policy is applied to the smallest group (Group1 ).
Each node replicates its data to its neighbor node, whichguarantees that all of the data in the dataset are replicatedin the two neighbor nodes. In Fig. 3, the data (the primarydata and the backup data) in Node11 are replicated in Node21 ,then from Node21 to Node31 , and so on. In other powerproportional approaches, the data reliability in the lowest
gear is often omitted because the data are not replicated.
Figure 4 shows an example of a three-gear system
based on Accordion data placement described above whereB = 600, G = 3, and N = 60 (N1 = N2 = N3 = 20). Groupicontains the nodes of Le f ti and Righti . Gear 1 contains only
the nodes in Group1 . To serve a request, Gear 2 requires thenodes in Group1 and Group2 to be activated, while Gear 3
requires all of the nodes in Group1 , Group2 , and Group3
to be activated. The primary data in 600 blocks are storedequally among all of the nodes so each group locates 100
blocks initially. Next, the data in Group3 are replicated inGroup2 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.
3.1.3

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 datafrom other nodes) so the physical locations of these two
types of data in the disks should be well designed. Normally,
the data are stored physically in a number of sectors of the

3.1.4

Storage Requirements

This section describes the total storage requirements forstoring a dataset based on the skewed data replication policy
used by Accordion. The total of blocks in a dataset is B andthere are G groups, where each group contains Ng nodes.
The total amount of data blocks V(B) stored is calculatedas:
V(B) =G

V(B)g ,

(3)g=1

where V(B)g is the number of data blocks located on thenodes of Groupg , g ∈ [1, G]. Initially, all of the blocks
are stored equally among all ofthe nodes in the cluster so
V(B)G = B × NNG , where N = Gg=1 Ng is the total numberof nodes in the system. In addition to the original data, thenodes in GroupG−1 are also used to locate the replication
data from the nodes in GroupG . Thus,NG
NG−1 NG
NG−1
+B
= B(
+
).
(4)
N
N
N
N
The amount of data in the remaining groups fromGroup(G−2) to Group1 are similarly calculated. Finally,
chained declustering is applied to Group1 so the storage required by Group1 is as follows:
V(B)G−1 = B

B 
V(B)1 = 2 (Ng ) = 2B.
N g=1
G

(5)

Substituting the values of V(B)g into (3) yields the following:
V(B) = B(2 +
= B

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

G

(g + 1)Ng
g=1

N

.

(6)

LE et al.: ACCORDION: AN EFFICIENT GEAR-SHIFTING FOR A POWER-PROPORTIONAL DISTRIBUTED DATA-PLACEMENT METHOD

1019

higher gear. The degradation of the system performance was
reduced so Accordion may be applicable to smooth gearshifting in multigear power-proportional file systems where
the number of gears is high.
3.1.6

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

3.1.5

The Amount of Data Transferred During GearShifting

In this section, we calculate and compare the amount of datathat 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 during each gear-shifting. In Accordion, however, shifting between each gear in the system only leads tovariation in the subpart of the dataset located on the nodes
that are reactivated during transitions.
From the calculations in Sect. 3.1.4, the amount of data
moved when the system changes from Gear g to Gear (g+ 1)
is,Vg (D) = D

G

Ni
i=g+1

N

,

(7)

where G is the number of groups, Ni is the number ofactive nodes in Groupi , N is the total number of nodes, andD is the number of blocks updated in the dataset in Gear
g. A constraint on Accordion is that the preferred numberof nodes in Groupg is a multiple of the number of nodes
in Groupg−1 . For a clearer understanding, we consider aNsimple case where ∀g ∈ [1, G], Ng+1
= scale (scale ≥ 1).
g
Substituting into (7), we obtain the following:Gi
i=g+1 scale
Vg (D) = D G−1.
(8)i
i=0 scaleFigure 5 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 to operate using five gears. The amount moved wasalways smaller in Accordion than Rabbit or Sierra and it became smaller when the system performed gear-shifting in a

Skewed Dataset Distribution in Accordion

The skewed data replication in Accordion leads to an imbalance in the amount of data stored on each node. Like in
Rabbit and Sierra, some nodes (in the smaller groups) store
considerably more data than others (in the higher groups).
However, this imbalance does not lead to considerable problem to the overall I/O performance as current hard disk
drives normally make use only part of the capacity otherthan full of the capacity to provide the I/O requests. Given
that the amount of unused storage is increasing [19] andthat the energy problem is a greater focus, the provisionof smooth gear-shifting is more important when delivering
power-proportional systems.
3.1.7

Fault Tolerance

A specific algorithm to deal with node failures in a system
is beyond the scope of this study. When a node fails, however, all of the nodes in the system are reactivated and thedata from a failure node can be reconstructed based on the
backup data. In a future study, we plan to provide a specificsolution to this problem in more detail.
3.2 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 inthe system. To provide power proportionality when serving
a dataset with multiple blocks, it is preferable to balance theload among all of 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 Bblock dataset, the goal of the load balancer is to make eachnode serve Bn blocks. Similar to Rabbit, we define an idealBvalue for each node where Nodeig equals n×containi . Whengthe dataset is being read, the current hit of the node Nodeig
servedigi
is 1×containi , where containg is the number of blocks storedglocally on Nodeig , and servedgi is the number of blocks already served by Nodeig . 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 theideal 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 isstored only in the lowest group’s nodes. Consequently, theIEICE TRANS. INF. & SYST., VOL.E98–D, NO.5 MAY 20151020

lowest group’s nodes can serve the request from the beginning and hence it leads to less skew in distributing the load
among nodes in Accordion than in Rabbit. It is explainedin more detail and clearer in Sect. 4.4.2 through utilizing anempirical experiment.

normal service in a high gear, the cost of allowing the system to operate in multiple modes to save power will depend
greatly on the quantity of data that needs to be transferred.

3.3

We conducted an empirical experiment using actual machines to verify the methods proposed in this study. We
chose Rabbit and Sierra, two of the de facto powerproportional data placement methods for distributed file systems as the comparative methods. First, we evaluated theeﬃciency of Accordion for smooth gear-shifting in multigear systems. Next, we compared Accordion with Rabbit
and Sierra with respect to power proportionality during theperformance of reads. Finally, we evaluated the power proportionality of Accordion using several configurations.

Writing Data Using Write Oﬀ-Loading

When a subset of a group of nodes is deactivated in a low
gear, the system can accept write requests from clients using the write oﬀ-loading technique. Next, when the systemmoves to a higher gear by reactivating nodes, it transfers the
updated data internally in the background without stopping
the processing of read serves from clients.
3.3.1

Writing New Data Using the Write Oﬀ-Loading
Technique4.

Experiments

4.1 Implementation
When the system is in a low gear and it has to deal with requests 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 deactivated nodes. Hence, the system selects another node randomly from the active nodes to serve this request. Information about the data, the temporary node, and the intended
node are saved in a log file. An example of the write oﬀloading process is shown in Fig. 6. In this example, Node22
should serve the write request for data E according to theoriginal data placement policy. However, it is powered oﬀ
in a low gear so the system decides to use an alternative
node, i.e., Node11 is selected in this case.

In this study, we implemented a prototype of the powerproportional distributed file system Accordion based ona modified HDFS. For comparison evaluation, we implemented the data placements in Rabbit and Sierra from thescratch based on their published papers. We changed thecurrent class used to select block locations via an interface
where diﬀerent data-layout policies can be performed. We
also added the load balancing mechanism in to HDFS. The
write oﬀ-loading policy was implemented in the low-powermode, which selects the temporal nodes for writing the newdata for the currently turned oﬀ nodes. To guarantee the datareliability, block replicas were written to distinct nodes in allof the operation modes.

3.3.2

4.2 Framework Used for the Experiments

Reflecting Updated Data

When the system changes to a high gear to serve a request
for high-performance processing with the newly updated
dataset, it needs to perform two functions. The first function
is to transfer the data written in temporary nodes to theiractual intended nodes. This can be achieved by reading theinformation in the log files. In Fig. 6, Node11 is set to transfer
data E to Node22 . 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 data layout, compared with a

Our test-bed for the experiments comprised dozens of commodity 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 Table 2. In the experiments, The power consumption of thecluster of data storage nodes was measured using an AC/DCPower HiTESTER 3334 [20]. The interconnect was a 1000
Mbps switching hub and all of the inactive nodes were hibernating.
4.3 The Smoothness of Accordion in Multigear Systems
In this part, we verified the eﬃciency of Accordion relating
Table 2

Fig. 6

Updated data reflection using write oﬀ-loading.

CPU
MemoryNIC
OS
JavaSpecification of a node.
TM8600 1.0 GHz
DRAM 4 GB
1000 Mb/s
Linux 3.0 64-bit
JDK-1.7.0

LE et al.: ACCORDION: AN EFFICIENT GEAR-SHIFTING FOR A POWER-PROPORTIONAL DISTRIBUTED DATA-PLACEMENT METHOD

1021
Table 3

Experimental environment.

#gears#active nodes from Gear 1 to Gear 6#filesFile size [MB]HDFS version
Block size [MB]64, 8, 12, 16, 20 and 24
420
64
0.20.2
16, 32 and 64

to reflecting the updated data in multigear systems in which
the number of gears is high. As discussed by the numericalanalysis in Sect. 3.1.5, Accordion is believed to be applicable to perform smoother gear-shiftings than other existing
methods as the amount of reflected data is thoroughly considered. This result is verified by the empirical experiments
performed in this section.
4.3.1

Execution time for reflecting updated data.

Experimental Environments and Method

We compared Accordion with Sierra in terms of their execution times needed to reflect updated data when the system
moved from a low gear to a higher gear. The reason wechoose Sierra as a comparative method is that Sierra andAccordion shares a common feature of flexible configuration of the multigear systems, especially when the numberof gear is high. In contrast, Rabbit requires very large numbers of nodes in higher gears because the number of nodes
in each gear is determined through an exponential function.
The systems used in this experiment were operated using a six-gear configuration based on six groups of nodes.
The numbers of active nodes from Gear 1 to Gear 6 were set
to 4, 8, 12, 16, 20 and 24 consequently. The data set contained 420 files in which the file’s size was fixed to 64MB.
The block size used in HDFS was varied to 16 MB, 32 MB
and 64 MB. Here, it is noted that, when the system achieves
gear-shifting, the whole dataset is updated. As the numberof files are 420, the size for the whole dataset is 26880 MB.
We also perform another experiment reported in Sect. 4.5
to evaluate Accordion with varying the size of the updated
data. Table 3 summarizes the above experiment settings.
Using write oﬀ-loading described in Sect. 3.3, thedataset is written when the systems operated in Gear 2.
Specifically, the replicas of files that should be written to
deactivated nodes would be temporally sent to other activating nodes. Here, from the fault tolerance point of view, we
guaranteed the constraint that the replicas of the same file
are not written to the same node. Next, we consequently
shifted the systems to higher gears, step by step from Gear
3 to Gear 6. During each shift, the temporal data were retransferred from temporal nodes to original nodes that werereactivated according to each data placement method, Sierra
or Accordion. The average execution times for reflecting the
temporal data at each shift were measured and reported.
4.3.2

Fig. 7

Experimental Results

Figure 7 describes the average execution time needed tomove the updated data at several configurations of bothFig. 8Size of transferred data.

Sierra and Accordion. From this figure, at each block size
setting, it is seen that the measured execution times in Sierra
were almost unchanged in all configurations. However, it
could be also derived that Accordion outperformed Sierra inall configurations. Furthermore, the eﬀect of Accordion became larger in the configurations in which the gear-shifting
was performed at higher gears as the execution time becomes shorter. Accordion gained highest result in configuration Gear 5 to Gear 6 where it improved the execution
time by 91% compared to Sierra when the block size was 16
MB.
The reason of the above results is shown in Fig. 8 which
presents the amount of reflected data at each configuration.
In Sierra, the amount of reflected data are the same and equal
the size of the dataset. When the system in Sierra shift to ahigher gear through reactivating a group of nodes, it has toreflect all the updated data of that group. Due to the fact thateach group contain one replica of the dataset, the amountof the updated data equals to the dataset’s size. In contrast,
the experimental results reported in this figure verified thenumerical analysis that in Accordion, the size of reflect data
always smaller than Sierra and becomes smaller when thegear-shifting is perform at higher gears. As a result, Accor-

IEICE TRANS. INF. & SYST., VOL.E98–D, NO.5 MAY 2015

1022
Table 4

Experimental environment.

#gears#active nodes (Accordion, Accordion-DP, Sierra)#active nodes (Rabbit)#filesFile size [MB]Block size [MB]32, 8, 20
2, 7, 214206432dion is believed to be applicable to smooth gear-shifting in
multiple power-proportional file systems where the numberof gears is high.
By changing the value of the block size, we could evaluate the eﬀect of the number of blocks to the performanceof Accordion during gear-shifting. Figure 7 also describesthat in both Sierra and Accordion, the execution times wereshorter with larger block size. The reason is mainly owing
to the metadata management cost in HDFS. Larger block
size, which leads to smaller the number of blocks in HDFS,
decreased the cost of the metadata management in our experiments.
4.4

Fig. 9 Throughput per watt using Accordion, Accordion-DP, Rabbit andSierra with various power settings.

Power Proportionality of Accordion, Rabbit and Sierra

We evaluated the eﬀectiveness of Accordion by determining the ratio of the throughput when reading a dataset andthe power consumption of the cluster of data-storing nodes.
We decided to elect two of the most state-of-the-art powerproportional data placement methods, Rabbit and Sierra, as
two comparative methods.
4.4.1

Experimental Environments

We compared Accordion and Accordion-DP with Rabbit
and Sierra in terms of their power proportionality when performing reads. These systems were operated using a threegear configuration based on three groups of 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 Sierra,
Accordion and Accordion-DP had 2, 8, and 20 nodes. In thisexperiment, as in Rabbit, the read performance of scanning
all the dataset is focused, then all 420 files of the dataset areread and each file is read once. The workload is distributed
uniformly to all of the 21 clients as each client sequentiallysends the requests of reading 20 separated files to the filesystems. Here, the size of each file is 64 [MB]. The otherinformation can be referred from Table 4.
4.4.2

Experimental Results

Figure 9 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 five runs and the Linux buﬀer
cache was cleared between runs.
There were not much diﬀerences in the results in Gear
1 and Gear 2 of the three configurations Rabbit, Sierra andFig. 10 Read performance using Accordion, Accordion-DP, Rabbit, andSierra with various power settings.

Accordion. However, in Gear 3, it is seen that Accordion
delivered approximately 10% better results than Rabbit because it gained better throughput as can be seen in Fig. 10
which shows the average throughputs for the configurations.
The reason was that the better load balancer in Accordionbased increased the throughput while consuming less power(20 nodes vs 21 nodes in Rabbit).
The load balancer was the same in all configurations so
the diﬀerences is explained by the timing distribution wheneach node served the requested blocks. Figure 11 shows
the timing distribution of serving blocks at active nodes inthe system for Rabbit and Accordion in Gear 2 and Gear
3. The blank part of the graphs at a node shows that thenode does not serve any block. The results of Sierra weresimilar to the results of Rabbit. In each graph, the vertical axis is the NodeID while the horizontal axis shows theBlockID of the dataset. In Rabbit, the nodes in ranges [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]. In Gear 2 of Rabbit, as there are
only 7 active nodes from NodeID 1 to NodeID 7, there wereno result of NodeID 8. The other blank parts of the graphs

LE et al.: ACCORDION: AN EFFICIENT GEAR-SHIFTING FOR A POWER-PROPORTIONAL DISTRIBUTED DATA-PLACEMENT METHOD

1023

experiment (with higher BlockIDs) to join the work. Whilst
in Accordion, because there are blocks whose replicas only
stored at nodes of lower groups, such nodes are forced toserve those blocks whenever they are called.
In this experiment, the benefit of the partitioning technique for separating the primary and backup data areas on
nodes was confirmed as Accordion-DP yielded approximately 10% better results than Accordion (Gear 3). Fromthe latter experiments, Accordion-DP was used to evaluate
the eﬀectiveness of Accordion.
4.5 Eﬀect of Reflecting the Updated Data on the PerformanceFig. 11 Distribution of timing on the nodes when serving the blocks inGear 2 and Gear 3 using Rabbit and Accordion.

of Rabbit at some nodes show that those nodes do not serve
any block. The reason of this result lays in the data placement in Rabbit because both Rabbit and Accordion used thesame load balancer.
In Rabbit and Accordion, the load balancer as described in Sect. 3.2, to guarantee that all the active nodes
serve the same blocks from the dataset, determines the ideal
value for each node. This ideal value for each nodes depends
on the total number of blocks of the serving dataset and thenumber of the blocks stored at this node. Because the total number of blocks of the dataset is fixed, the decision ofchoosing which node will serve the block from the nodes
that storing the replicas of the requested block, is depended
on the number of blocks storing at those nodes. As a result,the common load balancer utilized in Rabbit and Accordion
generally chooses the nodes of higher gear groups, which
store less blocks than the nodes of smaller gear groups.
For example, in Rabbit the replicas of BlockID 100 are
stored at NodeID 1 of Group1 , NodeID 3 of Group2 andNodeID 10 of Group3 . Here, Group3 is the highest geargroup and Group2 is higher gear group than Group1 . As
a result, when the system operates in Gear 3, NodeID 10
is chosen; in Gear 2, NodeID 3 is chosen and in Gear 1,
NodeID 1 is chosen to serve the BlockID 100.
Although Rabbit and Accordion utilize the common
load balancer described above, it is the data placement thatgenerated a diﬀerent result in Fig. 10. In Rabbit, because
replicas of the dataset are stored in group unit, it is ensured
that a replica of every block is stored in a node of every
group, as in the above example. However, it is diﬀerent
in Accordion as there exists a number of blocks that theirs
replicas are not stored at every group of the system. In theexample described in Fig. 4, the replicas of blocks in P3 andP4 are only stored in nodes of Group1 and the replicas ofblocks in P2 and P5 are not stored in nodes of Group3 .
As a result, in Rabbit, the nodes in higher groups
more aggressively serve the requests than the nodes in lower
group at the start of the experiment (with smaller BlockIDs),and the nodes in lower group have to wait until the late of the

The goal of the experiment in this section is to evaluate theeﬀect of the proposal in the event that when the system shifts
from a low gear to a high gear, it serves the workload of readrequest of reading all the dataset while performing reflectionof updated data in the background. Here, the workload ofread request was the same as the workload used in Sect. 4.4
because we wanted to verify how the read performance isaﬀected by the updated data reflection. It is achieved bycomparing with the results of Rabbit, Sierra, Accordion-DP
at Gear 3 reported in Fig. 10 in Sect. 4.4 in which no data
reflection is occurred.
4.5.1

Experimental Method

The workloads are generated that they are closed to theactual operation of the multiple-gear distributed file systems, like HDFS. It is assumed that initially the file system
was operated in a High gear and stored an initial dataset.
Then, the system shifts to a Low gear for a specified powerproportional service agreements. During this period, thisdataset was updated as new files are appended from theclients. The systems have to apply the write-oﬄoading technique to serve this update. Next, the systems are shiftedto the High gear in order to satisfy the higher throughput
performance on reading the whole dataset from the clients.
Here, the systems have to serve the reading request from theclient while performing updated data reflection in the background. In this assumption, as we focused on the applications on the distributed file systems like HDFS, we choose
the method to update the dataset as appending new files tothe dataset and to read the dataset as scanning all the files inthe dataset, which are considered very closed to the actual
deployments of HDFS.
In order to realize the above descriptions, three kinds ofworkloads are used in this experiment. The first workload isfor the data storing process, in which an initial dataset was
written to the file systems when it operates in Gear 3. The
second workload is for the data update process, in which an
updated dataset was written to the file system when it operates in Gear 2. The third workload is for the data reading
process, in which a reading dataset, which contains the initial dataset and the updated dataset, are read from the clients
when the file system operates in Gear 3.

IEICE TRANS. INF. & SYST., VOL.E98–D, NO.5 MAY 2015

1024
Table 5

Number of files in each dataset used in configurations.
Configuration
Updated dataset
Initial dataset

Small
70
350

Medium
140
280

Large
210
210

Fig. 13 The amount of data that had to be re-transferred when the system
moved from Gear 2 to Gear 3.

Fig. 12

Average throughput for scanning the dataset.

Because the performance degradation of reading
throughput over the whole dataset is evaluated, the size ofthe reading dataset in the third workload is fixed to thesame as in the workload used in the previous experiment(Section 4.4). As a result, the reading dataset contain 420
files, each file is 64 [MB]. Furthermore, as the eﬀect of
the updated data reflection, which is performed in the background when the systems serve the read request from theclients is evaluated, the sizes of the initial dataset and the
updated dataset in three configurations are varied. In Small,
Medium, Large configuration, the numbers of files of theinitial dataset and the updated dataset are consequently set
as (350, 70), (280, 140) and (210, 210) (Table 5).
The third workload for the data reading process is generated similarly as in the previous experiment (Section 4.4),
i.e. uniformly distributed to clients. Here, the number ofclients is 21, which equals the maximum number of active
nodes in Rabbit for a fair evaluation. Each client queried
separated and unique 20 files and the order of the files is
randomly created.
4.5.2

Experimental Results

Figure 12 shows the experimental results as the averagethroughput while scanning the dataset in three cases: small,medium, and large amounts of transferred data. The results
were compared with the results when the system performed
the read requests in Gear 3 (without updated data), whichwere the same as the previous experiment. It is seen that
configurations based on all of Accordion-DP, Rabbit andSierra were aﬀected significantly by the updated data reflection. The throughputs were degraded significantly bymore than 20% (approximately 20% for Accordion-DP and
30% for Rabbit and Sierra). It became worse with higher
amounts of re-transferred data. This confirmed the need toFig. 14 The execution time for the data-re-transfer process when the system moved from Gear 2 to Gear 3.

design the data placement method carefully to ensure eﬃcient gear-shifting in power-proportional file systems.
The results also indicated that Accordion-DP improved
the performance by 30% compared with Rabbit. The reason is with Accordion-DP, the amount of data re-transfer
required was less than that with Rabbit and Sierra. With
Accordion-DP, only part of the dataset written when the system operated in Gear 2 had to be re-transferred when thesystem 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 13 and 14 show the amounts of re-transferreddata and the execution times required to finish the re-transfer
process. Figure 13 shows that with Rabbit and Sierra, theamounts of data in the small, medium, and large cases were4480 MB, 8960 MB, and 13440 MB; while with AccordionDP were 2688 MB, 5376 MB, and 8064 MB, respectively.
As shown in Fig. 14, Accordion-DP significantly reduced
the time required to finish the updated data-re-transfer process by up to 66% (Small case) compared with Rabbit andSierra.

LE et al.: ACCORDION: AN EFFICIENT GEAR-SHIFTING FOR A POWER-PROPORTIONAL DISTRIBUTED DATA-PLACEMENT METHOD

1025
Table 6

Experimental environment.

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

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

among all the active nodes so the I/O throughput performance scales well with the system’s size. Furthermore,
Accordion-DP was highly eﬀective at reducing the cost ofgear-shifting because it improved the performance by 66%
when transferring the updated data.
Benefit from the smaller amount of the updated data,
Accordion is believed to perform well for the write-intensive
applications, in which the larger amount of re-transferreddata will occur because of write-oﬄoading. Moreover, although large amount of transferred data will occur, regarding to the primary data is focused, the write throughput for
the applications when the system operates in a lower gearis improved compare with Rabbit and Sierra. As the primary data are also managed by higher gear groups insteadof only the lowest gear group as in Rabbit and Sierra, thewrite throughput becomes larger as there are more nodes toserve writing the primary data.
5.

Fig. 15
rations.

4.6

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

Eﬀects of Diﬀerent Configurations of Accordion-DP

We also performed an experiment to evaluate the eﬀects ofdiﬀerent configurations of Accordion-DP on the power proportionality of the system. We used three configurations
with diﬀerent numbers of active nodes. The system was assumed to operate in a three-gear mode: Gear 1, Gear 2, andGear 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 thesame as those used in the previous experiment in Table 6.
Figure 15 shows the performance (throughput per watt)for the three configurations we evaluated. It is seen thatlarger configuration gained better throughput per Watt results at all power settings. The considerable reason is thatthe load at each node in larger configuration is lighter as thenumber of serving data becomes smaller. As a result, it canbe suggested that Accordion is able to perform well with thehigh number of active nodes. In a future work, we want toverify this assumption by further experiments using a morenumber of nodes.
4.7

Discussion

The data placement strategy used by Accordion-DP ensureshigh power-proportionality performance of systems, especially when systems operate in a high gear mode with alarger amount of active nodes. It was well modeled throughnumerical analysis and verified through the empirical experiments. In Accordion-DP, the amount of data requested andthe access timing of the active nodes are well distributed

Conclusion and Future Work

Recently, energy-eﬃcient 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 filesystems and we proposed the Accordion data placement
method to address this problem. Furthermore, the Accordion configuration is highly flexible because the numberof nodes in each group can be determined by a weak constrain. In Accordion, the data reliability in the lowest configuration which is omitted in other methods, is ensured
through utilizing chained declustering. Extensive experiments using actual machines with the Accordion prototype
verified the eﬀectiveness of Accordion. Accordion also reduced the execution time required for updated data movement by 66% and improved the power-proportional performance by 30% compared with Rabbit and Sierra, two of
the most standard power-proportional data placement aiming for Big Data. Furthermore, Accordion is applicable forsmooth gear-shifting in multigear systems, especially when
the number of gear is high. In such situation, when the gearshifting is occurred at a high gear, Accordion was shown tobe able to eﬀectively shorten the execution time by at most
91% compared to Sierra. From the experiment results, Accordion is believed to be capable for deploying in real system, especially for commodity-oﬀ-the-shelf based systems,
in which the power consumption is still not gained enoughsupport from modern hardware technologies.
In the future, we would like to confirm the eﬀectiveness of Accordion in diﬀerent experimental environments,
by using actual benchmarks and with more number of nodes.
Moreover, we want to integrate Accordion with architectures other than HDFS. We will also consider developinga specific algorithm to deal with system failures.
Acknowledgments
This work was supported partly by Grants-in-Aid for Sci-

IEICE TRANS. INF. & SYST., VOL.E98–D, NO.5 MAY 2015

1026

entific Research from the Japan Science and Technology
Agency (A) (#22240005).
References[1] H.H. Le, S. Hikida, and H. Yokota, “Eﬃcient gear-shifting for a
power-proportional distributed data-placement method,” Proc. 2013
IEEE International Conference on Big Data, pp.76–84, 2013.
[2] S. Ghemawat, H. Gobioﬀ, and S.T. Leung, “The google file system,” Proc. 19th ACM Symposium on Operating Systems Principles,
pp.29–43, 2003.
[3] Apache Hadoop, “HDFS Hadoop Wiki.” http://wiki.apache.org/
hadoop/HDFS.
[4] L.A. Barroso and U. Hölzle, “The case for energy-proportional computing,” Computer, vol.40, pp.33–37, 2007.
[5] W. Charles, O. Mathew, Q. Jin, W.A.I. Andy, R. Peter, and K. Geoﬀ,“PARAID: A gear-shifting power-aware RAID,” ACM Trans. Storage, vol.3, pp.13:1–13:33, 2007.
[6] A. Hrishikesh, C. James, G. Varun, G.R. Ganger, K. Michael A., and
S. Karsten, “Robust and flexible power-proportional storage,” Proc.
1st Symposium on Cloud Computing, pp.217–228, 2010.
[7] E. Thereska, A. Donnelly, and D. Narayanan, “Sierra: Practicalpower-proportionality for data center storage,” Proc. 6th European
Conference on Computer Systems, pp.169–182, 2011.
[8] S. Priya, T. Vasily, and Z. Erez, “Evaluating performance and energy
in file system server workloads,” Proc. 8th USENIX Conference on
File and Storage Technology, pp.253–266, 2010.
[9] J. Dean and S. Ghemawat, “MapReduce: Simplified data processing on large clusters,” Proc. 6th Symposium on Operating System
Design and Implementation, pp.137–150, 2004.
[10] D. Narayanan, A. Donnelly, and A. Rowstron, “Write oﬀ-loading:
Practical power management for enterprise storage,” ACM Transaction on Storage, vol.4, no.3, pp.10:1–10:23, 2008.
[11] H.H. Le, S. Hikida, and H. Yokota, “An evaluation of powerproportional data placement for Hadoop distributed file systems,”
Proc. Cloud and Green Computing, pp.752–759, 2011.
[12] H.H. Le, S. Hikida, and H. Yokota, “NameNode and DataNode coupling for power-proportional Hadoop distributed file system,” Proc.
18th International Conference on Database System for Advanced
Applications, Part II, pp.99–107, 2013.
[13] H.H. Le, S. Hikida, and H. Yokota, “NDCouplingHDFS: A coupling architecture for a power-proportional Hadoop distributed filesystem,” IEICE Trans. Inf. & Syst., vol.E97-D, no.2, pp.213–222,
Feb. 2014.
[14] B. Mao, D. Feng, H. Jiang, S. Wu, J. Chen, and L. Zeng, “GRAID:
A green RAID storage architecture with improved energy eﬃciency
and reliability,” Proc. 16th International Symposium on Modeling,
Analysis and Simulation of Computers and Telecommunication Systems, pp.1–8, 2008.
[15] J. Leverich and C. Kozyrakis, “On the energy (in)eﬃciency ofHadoop clusters,” SIGOPS Operating System Review, vol.44,
pp.61–65, 2010.
[16] R.T. Kaushik and B. Milind, “GreenHDFS: Towards an energyconserving, storage-eﬃcient, hybrid Hadoop compute cluster,” Proc.
2010 International Conference on Power Aware Computing and Systems, pp.1–9, 2010.
[17] J. Kim and D. Rotem, “Energy proportionality for disk storage using replication,” Proc. 14th International Conference on Extending
Database Technology, pp.81–92, 2011.
[18] H.I. Hsiao and D. DeWitt, “Chained declustering: A new availability strategy for multiprocessor database machines,” Proc. 6th International Conference on Data Engineering, pp.456–465, 1990.
[19] J. Gray, “Greetings from a filesystem user,” Proc. 4th USENIX Conference on Files and Storage Techniques, 2005.
[20] “AC/DC Power HiTester 3334.” http://www.hioki.com/products/
power current sensor/power meters/402.

Hieu Hanh Le
received his B.E., and M.E.
degree from Tokyo Institute of Technology in2008, and 2010, respectively. He is currently a
researcher at Yokohama Research Laboratory of
Hitachi. He is interested in research on data engineering, information storage systems, and network engineering. He is a member of IPSJ.

Satoshi Hikida
received his M.E. degreefrom Tokyo Institute of Technology in 2011. He
is currently a Ph.D student at Tokyo Institute ofTechnology. He is engaged in research on dataengineering, and information storage systems.
He is a student member of IPSJ.

Haruo Yokota
received his B.E., M.E. and
Dr.Eng. degrees from Tokyo Institute of Technology in 1980, 1982, and 1991, respectively.
He joined Fujitsu Ltd. in 1982, and was a researcher at ICOT for the Japanese 5th Generation Computer Project from 1982 to 1986, andat Fujitsu Laboratories Ltd. from 1986 to 1992.
From 1992 to 1998, he was an Associate Professor at Japan Advanced Institute of Science andTechnology (JAIST). He is currently a Professor at the Department of Computer Science inTokyo Institute of Technology. His research interests include the general
research areas of data engineering, information storage systems, and thedependable computing. He was a chair of ACM SIGMOD Japan Chapter, a trustee board member of IPSJ and the DBSJ, and the Editor-in-Chiefof Journal of Information Processing. He is a Vice Chair of DBSJ, an associate editor of the VLDB Journal, a fellow of IEICE and IPSJ, senior
member of IEEE, and a member of JSAI, ACM, and ACM-SIGMOD.