Hadoop Map Reduce For Mobile Clouds PDF
Hadoop Map Reduce For Mobile Clouds PDF
Hadoop Map Reduce For Mobile Clouds PDF
fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TCC.2016.2603474,
IEEE Transactions on Cloud Computing
Abstract—The new generations of mobile devices have high processing power and storage, but they lag behind in terms of
software systems for big data storage and processing. Hadoop is a scalable platform that provides distributed storage and
computational capabilities on clusters of commodity hardware. Building Hadoop on a mobile network enables the devices to
run data intensive computing applications without direct knowledge of underlying distributed systems complexities. However,
these applications have severe energy and reliability constraints (e.g., caused by unexpected device failures or topology changes
in a dynamic network). As mobile devices are more susceptible to unauthorized access, when compared to traditional servers,
security is also a concern for sensitive data. Hence, it is paramount to consider reliability, energy efficiency and security for such
applications. The MDFS (Mobile Distributed File System) [1] addresses these issues for big data processing in mobile clouds. We
have developed the Hadoop MapReduce framework over MDFS and have studied its performance by varying input workloads in
a real heterogeneous mobile cluster. Our evaluation shows that the implementation addresses all constraints in processing large
amounts of data in mobile clouds. Thus, our system is a viable solution to meet the growing demands of data processing in a
mobile environment.
Index Terms—Mobile Computing, Hadoop MapReduce, Cloud Computing, Mobile Cloud, Energy-Efficient Computing, Fault-
Tolerant Computing
also a major concern as the stored data often contains 2 Related Work & Background
sensitive user information [6] [7]. Traditional security There have been several research studies that at-
mechanisms tailored for static networks are inadequate tempted to bring MapReduce framework to the het-
for dynamic networks. Devices can be captured by erogeneous cluster of devices, due to its simplicity and
unauthorized users and data can be compromised easily powerful abstractions [11].
if necessary security measures are not provided. To ad- Marinelli [12] introduced the Hadoop based platform
dress the aforementioned issues of energy efficiency, reli- Hyrax for cloud computing on smartphones. Hadoop
ability and security of dynamic network topologies, the TaskTracker and DataNode processes were ported on
k-out-of-n computing framework was introduced [8] [9]. Android mobile phones, while a single instance of
An overview of the previous MDFS will be described NameNode and JobTracker were run in a traditional
in section 2.2. What remains as an open challenge is server. Porting Hadoop processes directly onto mobile
to bring the cloud computing framework to a k-out-of-n devices doesn’t mitigate the problems faced in the mo-
environment such that it solves the bottlenecks involved bile environment. As presented earlier, HDFS is not well
in processing and storage of big data in a mobile cloud. suited for dynamic network scenarios. There is a need
for a more lightweight file system which can adequately
The Hadoop MapReduce cloud computing framework address dynamic network topology concerns. Another
meets our processing requirements for several reasons: MapReduce framework based on Python, Misco [13]
1) in the MapReduce framework, as the tasks are run was implemented on Nokia mobile phones. It has a
in parallel, no single mobile device becomes a bottle- similar server-client model where the server keeps track
neck for overall system performance; 2) the MapReduce of various user jobs and assigns them to workers on
framework handles resource management, task schedul- demand. Yet another server-client model based MapRe-
ing and task execution in an efficient fault tolerant duce system was proposed over a cluster of mobile
manner. It also considers the available disk space and devices [14] where the mobile client implements MapRe-
memory of each node before tasks are assigned to duce logic to retrieve work and produce results from
any node; 3) Hadoop MapReduce has been extensively the master node. The above solutions, however, do not
tested and used by large number of organizations for solve the issues involved in data storage and processing
big data processing over many years. However, the of large datasets in the dynamic network.
default file system of Hadoop, HDFS (Hadoop Dis- P2P-MapReduce [15] describes a prototype imple-
tributed File System) [10] is tuned for static networks mentation of a MapReduce framework which uses a
and is unsuitable for mobile environments. HDFS is peer-to-peer model for parallel data processing in dy-
not suitable for dynamic network topologies because: namic cloud topologies. It describes mechanisms for
1) it ignores energy efficiency. Mobile devices have managing node and job failures in a decentralized man-
limited battery power and can easily fail due to energy ner.
depletion; 2) HDFS needs better reliability schemes for The previous research focused only on the parallel
data in the mobile environment. In HDFS, each file processing of tasks on mobile devices using the MapRe-
block is replicated to multiple devices considering heavy duce framework without addressing the real challenges
I/O bound jobs with strong requirements on backend that occur when these devices are deployed in the
network connections. Instead, we need lightweight pro- mobile environment. Huchton et al. [1] proposed a k-
cesses which react well to slow and varying network Resilient Mobile Distributed File System (MDFS) for
connections. Consequently, we considered k-out-of-n mobile devices targeted primarily for military opera-
based MDFS [8], instead of HDFS, as our underlying tions. Chen et al. [16] proposed a new resource al-
file system for the MapReduce framework. location scheme based on k-out-of-n framework and
implemented a more reliable and energy efficient Mobile
In this paper, we implement Hadoop MapReduce Distributed File System for Mobile Ad Hoc Networks
framework over MDFS and evaluate its performance (MANETs) with significant improvements in energy
on a general heterogeneous cluster of devices. We im- consumption over the traditional MDFS architecture.
plement the generic file system interface of Hadoop In the remaining part of this section we present
for MDFS which makes our system interoperable with background material on Hadoop and MDFS.
other Hadoop frameworks like HBase. There are no
changes required for existing HDFS applications to be
deployed over MDFS. To the best of our knowledge, 2.1 Hadoop Overview
this is the first work to bring Hadoop MapReduce The two primary components of Apache Hadoop are
framework for mobile cloud that truly addresses the the MapReduce framework and HDFS, as shown in
challenges of the dynamic network environment. Our Figure 1. MapReduce is a scalable parallel processing
system provides a distributed computing model for pro- framework that runs on HDFS. It refers to two distinct
cessing of large datasets in mobile environment while tasks that Hadoop jobs perform- the Map Task and
ensuring strong guarantees for energy efficiency, data the Reduce Task. The Map Task takes the input data
reliability and security. set and produces a set of intermediate <key,value>
2168-7161 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more
information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TCC.2016.2603474,
IEEE Transactions on Cloud Computing
MapReduce
Program M Map Task
Client Node
R Reduce Task
Job Client
A B File Blocks
Submit Job
Encrypted AES
Name Node
Block A
File.txt
Block B Data Node Data Node
Block Datanodes A B A B
A 1,2
Block Datanodes Fig. 2. Existing MDFS architecture
B 1,2
Metadata Data Read/ Data Read/ at regular intervals through heartbeat messages which
Operations Write Write
Network contain the information regarding their stored blocks.
NameNode builds its metadata from these block reports
Fig. 1. Hadoop architecture and always stays in sync with the DataNodes in the
pairs which are sorted and partitioned per reducer. The cluster.
map output is then passed to Reducers to produce the When the HDFS client initiates the file read opera-
final output. The user applications implement mapper tion, it fetches the list of blocks and their corresponding
and reducer interfaces to provide the map and reduce DataNode locations from NameNode. The locations are
functions. In the MapReduce framework, computation ordered by their distance from the reader. It then tries
is always moved closer to nodes where data is located, to read the content of the block directly from the first
instead of moving data to the compute node. In the location. If this read operation fails, it chooses the
ideal case, the compute node is also the storage node next location in the sequence. As the client retrieves
minimizing the network congestion and thereby maxi- data directly from the DataNodes, the network traffic
mizing the overall throughput. is distributed across all the DataNodes in the HDFS
Two important modules in MapReduce are the cluster.
JobTracker and the TaskTracker. JobTracker is the When the HDFS client is writing data to a file, it
MapReduce master daemon that accepts the user jobs initiates a pipelined write to a list of DataNodes which
and splits them into multiple tasks. It then assigns are retrieved from the NameNode. The NameNode
these tasks to MapReduce slave nodes in the cluster chooses the list of DataNodes based on the pluggable
called the TaskTrackers. TaskTrackers are the process- block placement strategy. Each DataNode receives data
ing nodes in the cluster that run the tasks- Map and from its predecessor in the pipeline and forwards it to
Reduce. The JobTracker is responsible for scheduling its successor. The DataNodes report to the NameNode
tasks on the TaskTrackers and re-executing the failed once the block is received.
tasks. TaskTrackers report to JobTracker at regular
intervals through heartbeat messages which carry the
information regarding the status of running tasks and 2.2 MDFS Overview
the number of available slots. The traditional MDFS was primarily targeted for mil-
HDFS is a reliable, fault tolerant distributed file itary operations where front line troops are provided
system designed to store very large datasets. Its key with mobile devices. A collection of mobile devices
features include load balancing for maximum efficiency, form a mobile ad-hoc network where each node can
configurable block replication strategies for data protec- enter or move out of the network freely. MDFS is
tion, recovery mechanisms for fault tolerance and auto built on a k-out-of-n framework which provides strong
scalability. In HDFS, each file is split into blocks and guarantees for data security and reliability. k-out-of-n
each block is replicated to several devices across the enabled MDFS finds n storage nodes such that total
cluster. expected transmission cost to k closest storage nodes
The two modules in HDFS layer are NameNode and is minimal. Instead of relying on conventional schemes
DataNode. NameNode is the file system master daemon which encrypt the stored data per device, MDFS uses
that holds the metadata information about the stored a group secret sharing scheme.
files. It stores the inode records of files and directories As shown in Figure 2, every file is encrypted using
which contain various attributes like name, size, per- a secret key and partitioned into n1 file fragments
missions and last modified time. DataNodes are the file using erasure encoding (Reed Solomon algorithm). Un-
system slave nodes which are the storage nodes in the like conventional schemes, the secret key is not stored
cluster. They store the file blocks and serve read/write locally. The key is split into n2 fragments using Shamir’s
requests from the client. The NameNode maps a file to secret key sharing algorithm. File creation is complete
the list of its blocks and the blocks to the list of DataN- when all the key and file fragments are distributed
odes that store them. DataNodes report to NameNode across the cluster. For file retrieval, a node has to
2168-7161 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more
information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TCC.2016.2603474,
IEEE Transactions on Cloud Computing
retrieve at least k1 (<n1 ) file fragments and k2 (<n2 ) an empty slot on any node that contains the block. If
key fragments to reconstruct the original file. no slots are available, it looks for an empty slot on a
MDFS architecture provides high security by en- different node but in the same rack. In MDFS, as no
suring that data cannot be decrypted unless an au- node in the network has a complete block for processing,
thorized user obtains k2 distinct key fragments. It the challenge is to determine the best locations for each
also ensures resiliency by allowing the authorized users task execution. Section 4.5 proposes an energy-aware
to reconstruct the data even after losing n1 -k1 frag- scheduling algorithm that overrides the default one.
ments of data. Reliability of the file increases when 5. The MapReduce and HDFS components are rack
the ratio k1 /n1 decreases, but it also incurs higher aware. They use network topology for obtaining the
data redundancy. The data fragments are placed on a rack awareness knowledge. As discussed, if the node
set of selected storage nodes considering each node’s that contains the block is not available for task exe-
failure probability and its distance to the potential cution, the default task scheduling algorithm selects a
clients. A node’s failure probability is estimated based different node in the same rack using the rack awareness
on the remaining energy, network connectivity, and knowledge. This scheme leverages the single hop and
application-dependent factors. Data fragments are then high bandwidth of in-rack switching. The challenge is
allocated to the network such that the expected data to define rack awareness in context of mobile ad-hoc
transferring energy for all clients to retrieve/recover the network as the topology is likely to change at any
file is minimized. time during the job execution. This challenge is also
MDFS has a fully distributed directory service in addressed by the new scheduling algorithm described
which each device maintains information regarding the in Section 4.5.
list of available files and their corresponding key and
file fragments. Each node in the network periodically 4 System Design
synchronizes the directory with other nodes ensuring In this section, we present the details of our proposed
that the directories of all devices are always updated. architectures, system components and the interactions
among the components that occur during file system
3 Challenges operations.
This section describes the challenges involved in the
implementation of MapReduce framework over MDFS. 4.1 Requirements
1. Traditional MDFS architecture only supports a For the design of our system, the following requirements
flat hierarchy. All files are stored at the same level in had to be met:
the file system without the use of folders or directories. • Since the Hadoop JobTracker is a single entity
But the MapReduce framework relies on fully qualified common to all nodes across the cluster, there
path names for all operations. The fully qualified path should be at least one node in the cluster which
is added to MDFS, as described in Section 4.4.6. always operates within the network range and
2. The capabilities of traditional MDFS are very remains alive throughout the job execution phase.
limited. It supports only a few functionalities such The system must tolerate node failures.
as read(), write() and list(). A user calls the write() • Data stored across the cluster may be sensitive.
function to store a file across the nodes in the network Unauthorized access to sensitive information must
and the read() function to read the contents of a file be prohibited.
from the network. The list() function provides the full • The system is tuned and designed for handling
listing of the available files in the network. large amounts of data in the order of hundreds of
However, MapReduce framework needs a fairly megabytes, but it must also support small files.
generic file system that implements wide range of func- • Though we primarily focus on mobile devices,
tions. It has to be compatible with available HDFS the system must support heterogeneous cluster
applications without any code modification or extra of devices which can be a combination of tradi-
configuration. The implementation detail is described tional personal computers, servers, laptops, mobile
in Section 4.4. phones and tablets depending on the working en-
3. MapReduce framework needs streaming access vironment of the user.
to their data, but MDFS reads and writes are not • Like HDFS, the system must support sequential
streaming operations. How the data is streamed during writes. Bytes written by a client may not be visible
read/write operations are described in Section 4.4. immediately to other clients in the network unless
4. During the job initialization phase of Hadoop, the file is closed or flush operation is called. Append
JobTracker queries the NameNode to retrieve the in- mode must be supported to append the data to
formation of all the blocks of the input file (blocks and an already existing file. Flush operation guarantees
list of DataNodes that store them) for selecting the that bytes up to that given point in the stream are
best nodes for task execution. JobTracker prioritizes persisted and changes are visible to all other clients
data locality for TaskTracker selection. It first looks for in the system.
2168-7161 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more
information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TCC.2016.2603474,
IEEE Transactions on Cloud Computing
• Like HDFS, the system must support streaming The client connects to the RPC server and talks to
reads. It must also support random reads where a it using the MDFS Name Protocol. The MDFS client
user reads bytes starting from an arbitrary offset and MDFS Name Server are completely unaware of the
in the file. fragment distribution which is handled by the Data
Server. We kept the namespace management and data
4.2 System Components management totally independent for better scalability
and design simplicity.
In the traditional MDFS architecture, a file to be stored 4.2.2.2 Data Server: The MDFS Data Server is
is encrypted and split into n fragments such that any k a lightweight MDFS daemon instantiated on each node
(<n) fragments are sufficient to reconstruct the original in the cluster. It coordinates with other MDFS Data
file. In this architecture, parallel file processing is not Server daemons to handle MDFS communication tasks
possible as even a single byte of the file cannot be like neighbor discovery, file creation, file retrieval and
read without retrieving the required number of frag- file deletion. On startup, it starts a local RPC server
ments. Moreover, MapReduce framework assumes that listening on the port defined by mdfs.dataservice.rpc-
the input file is split into blocks which are distributed port in the configuration file. When the user invokes
across the cluster. Hence, we propose the notion of any file system operation, the MDFS client connects to
blocks, which was missing in the traditional MDFS the local Data Server at the specified port and talks
architecture. In our approach, the files are split into to it using the MDFS Data Protocol. Unlike Hadoop
blocks based on the block size. These blocks are then DataNode, the Data Server has to be instantiated on
split into fragments that are stored across the cluster. all nodes in the network where data flow operations
Each block is a normal Unix file with configurable block (reads and writes) are invoked. This is because the Data
size. Block size has a direct impact on performance as Server prepares the data for these operations and they
it affects the read and write sizes. are always executed in the local file system of the client.
The file system functionality of each cluster node is The architecture is explained in detail in the subsequent
split across three layers- MDFS Client, Data processing sections.
layer and Network communication layer.
4.2.3 Network communication layer
4.2.1 MDFS Client This layer handles the communication between the
User applications invoke file system operations using nodes in the network. It exchanges control and data
the MDFS client, a built-in library that implements the packets for various file operations. This layer abstracts
MDFS file system interface. The MDFS client provides the network interactions and hides the complexities
file system abstraction to upper layers. The user does involved in routing packets to various nodes in case of
not need to be aware of file metadata or the storage dynamic topologies like in MANETs.
locations of file fragments. Instead, the user references 4.2.3.1 Fragment Mapper: The Fragment Map-
each file by paths in the namespace using the MDFS per stores information of file and key fragments which
client. Files and directories can be created, deleted, include the fragment identifiers and the location of
moved and renamed like in traditional file systems. fragments. It stores the mapping of a block to its list
All file system commands take path arguments in URI of key and file fragments.
format (scheme://authority/path). The scheme decides 4.2.3.2 Communication Server: The Communi-
the file system to be instantiated. For MDFS, the cation Server interacts with every other node and is
scheme is mdfs and the authority is the Name Server responsible for energy-efficient packets routing. It must
address. support broadcast and unicast, the two basic com-
munication modes required by MDFS. To allow more
4.2.2 Data processing layer flexible routing mechanisms in different environments,
Data Processing layer manages the data and control it is implemented as a pluggable component which can
flow of file system operations. The functionality of this be extended to support multiple routing protocols.
layer is split across two daemons- Name Server and 4.2.3.3 Topology Discovery & Maintenance
Data Server. Framework: This component stores the network
4.2.2.1 Name Server: MDFS Name Server is a topology information and the failure probabilities
lightweight MDFS daemon that stores the hierarchical of participating nodes. When the network topology
file organization or the namespace of the file system. changes, this framework detects the change through a
All file system metadata including the mapping of a file distributed topology monitoring algorithm and updates
to its list of blocks is also stored in the MDFS Name the Fragment Mapper. All the nodes in the network
Server. The Name Server has the same functionality are thus promptly updated about network topology
as Hadoop NameNode. The Name Server is always up- changes.
dated with any change in the file system namespace. On There are two types of system metadata. The file
startup, it starts a global RPC server at a port defined system namespace which includes the mapping of file
by mdfs.nameservice.rpc-port in the configuration file. to blocks is stored in the Name Server while mapping of
2168-7161 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more
information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TCC.2016.2603474,
IEEE Transactions on Cloud Computing
8 9
Step 2: Similar to HDFS block allocation scheme,
18
15 10 Commu. Commu. for each block to be written, the MDFS client requests
K-out-of-n Server Server
Commu.
Server Topology
framework the Name Server to allocate a new block Id which is
Discovery/
Maintenance Fragment a unique identifier for each block. As all the identifiers
Unit Mapper
13
are generated by a single Name Server in a centralized
12
architecture, there will not be any identifier. However,
17
in the distributed architecture, an appropriate hashing
16
function is required to generate the unique global iden-
Fig. 6. Data Flow of a write operation tifier. In our implementation, the absolute path of each
file is used as the hash key.
operation is completed, the block is deleted for security
reasons to restore the original state of the cluster. Step 3: The Name Server returns a new block id
If many clients are accessing the same file, the mo- based on the allocation algorithm and adds the block
bile nodes that store the fragments may become the identifier in its local cache. The mapping of file to list
hot spots. This problem can be fixed by enabling file of blocks is stored in the Name Server.
caching. Caching is disabled by default and each node Steps 4-5: The MDFS client issues a creation request
deletes the file fragments after the file retrieval. If to the Data Server which contains a specific opcode
caching is enabled, the reader node caches the file in the request message. The Data Server identifies the
fragments in its local file system so that it does not fetch opcode and instantiates the File Creator module to
the fragments from the network during the subsequent handle the block creation.
read operations.
Step 6: The block stored in the local file system is
If the file fragments are available locally, the reader
encrypted using the secret key. The encrypted block is
client verifies the length of cached file with the actual
partitioned into n fragments using erasure encoding.
length stored in Name Server. This avoids the problem
of reading the outdated version of the file. If some Step 7: The key is also split into fragments using
data has been appended to the file after caching, file Shamir’s secret key sharing algorithm.
fragments are re-fetched from the network overwriting Steps 8-9: The Data Server requests the k-out-of-n
the existing ones. Fragment availability increases due framework to provide n storage nodes such that total
to caching which leads to fair distribution of load in expected transmission cost from any node to k closest
the cluster without consuming extra energy. However, storage nodes is minimal.
caching affects system security due to higher availability
Step 10: The Data Server requests the Fragment
of file fragments in the network.
Mapper to add the fragment information of each file
which includes the fragment identifier with the new
4.4.2 File Write Operation
locations returned by the k-out-of-n framework. If the
HDFS write design is not applicable for MDFS as data network topology changes after the initial computation,
cannot be written unless the block is decrypted and k-out-of-n framework recomputes the storage nodes
decoded. Hence in the MDFS architecture, when write for every file stored in the network and updates the
operation is called, bytes are appended to the current Fragment Mapper. This ensures that Fragment Mapper
block till the block boundary is reached or the file is is always in sync with the current network topology.
closed. The block is then encrypted, split into fragments
and redistributed across the cluster. Steps 11-18: The file fragments are distributed
Our MDFS architecture does not support random in parallel across the cluster. The key fragments are
writes. Random writes make the design more compli- also stored in the same manner. These details are not
cated when writes span across multiple blocks. This included in the diagram for brevity.
feature is not considered in the present design as it is Steps 19-20: Once the file and key fragments are
not required for the MapReduce framework. Figure 6 distributed across the cluster, the Data Server informs
illustrates the control flow of a write operation through the client that the file has been successfully written
these numbered steps to the nodes. For security purposes, the original block
Step 1: The user issues a write request for a file of stored in the local file system of the writer is deleted
length L. The file is split into blocks of size [L/B] where after the write operation as it is no longer needed.
2168-7161 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more
information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TCC.2016.2603474,
IEEE Transactions on Cloud Computing
probability) to estimate the task retrieval energy and is being executed. Once the write has completed, the
assign tasks. Only nodes that are currently functional new data is visible across the cluster immediately. In
and available may be selected. Ci⋆ (b) is defined as the all circumstances, MDFS provides strong consistency
minimal cost of fetching block b at node i. Let Fb be a guarantee for reads such that all concurrent reader
1 × N binary vector where each element Fb (j) indicates clients will read the same data irrespective of their
whether node j contains a fragment of block b (note that
P locations.
N
j=1 Fb (j) = n ∀b); Sb is the size of block b; di,j is
the distance (hop-count) between node i and node j; 4.7 Failure Tolerance
the pair-wise node distance can be estimated efficiently
This section describes how MDFS uses k-out-of-n en-
using all pair shorted distance algorithm X is a 1 × N
coding technique and snapshot operation to improve the
binary decision variable where Xj = 1 indicates that
data reliability and prevent node failures.
node j sends a data fragment to node i.
X
N X
N 4.7.1 k-out-of-n reliability
Ci⋆ (b) = min (Sb /k)Fb (j)di,j Xj , s.t. Xj = k In HDFS, each block is replicated a specific number of
j=1 j=1 times for fault tolerance, which is determined by the
Ci⋆ (b) can be solved by Algorithm 1, which minimizes replication factor configured by the user. In MDFS, the
the communication cost for node i to retrieve k data k-out-of-n framework ensures data reliability where k
fragments of block b. Once Ci⋆ (b) for each node is solved, and n parameters determine the level of fault tolerance.
the processing task for block b is then assigned to node These parameters are per file configurable which are
p where p = arg mini Ci⋆ (b). The time complexity of specified at the file creation time. Only k nodes are
Algorithm 1 is N logN due to the sorting procedure, and required to retrieve the complete file, ensuring data
because it is performed once for each of the N node, the reliability.
time complexity for assigning a block to a taskTracker
is N 2 logN . Considering the size of our network (≤ 100) 4.7.2 Snapshot operation
and the processing power of the modern mobile devices, A snapshot operation creates a backup image of current
the computational overhead of the scheduling algorithm state which includes in-memory data structures. During
is minimal. safe shutdown of the Name Server and Fragment Map-
per, a snapshot operation is automatically invoked to
4.6 Consistency Model save the state on the disk. On restart, the saved image
is used to rebuild the system state. Snapshot operations
Like HDFS, MDFS also follows single writer and multi-
are particularly useful when a user is experimenting
ple reader model. An application can add data to MDFS
with changes that need to be rolled back easily in
by creating a new file and writing data to it (Create
the future. When client requests a snapshot operation,
Mode). The data once written cannot be modified or
the Name Server enters a special maintenance state
removed except when the file is reopened for append
called safe mode. No client operations are allowed when
(Append Mode). In both write modes, data is always
the Name Server is in safe mode. The Name Server
added to the end of the file. MDFS provides the support
leaves safe mode automatically once backup is created.
for overwriting the entire file but not from any arbitrary
The data server is not backup as it mainly handles
offset in the file.
MDFS communication tasks like neighbor discovery, file
If an MDFS client opens a file in Create or Append
creation, file retrieval. These information varies with
mode, the Name Server acquires a write lock on the
time, so it is unnecessary to include in the snapshot.
corresponding file path so that no other client can open
the same file for write. The writer client periodically
notifies the Name Server through heartbeat messages 4.8 Diagnostic Tools
to renew the lock. To prevent the starvation of other MDFS Shell is a handy and powerful debugging tool to
writer clients, the Name Server releases the lock after execute all available file system commands. It is invoked
a user configured time limit if the client fails to renew by hadoop mdfs <command><command args>. Each
the lock. The lock is also released when the file is closed command has file path URI and other command specific
by the client. arguments. MDFS shell can simulate complex cluster
A file can have concurrent reader clients even if it is operations like concurrent reads and writes, device fail-
locked for a write. When a file is opened for a read, the ures, device reboots etc. All MDFS specific parameters
Name Server acquires a read lock on the corresponding can be changed at run time using MDFS shell. MDFS
file path to protect it from deletion from other clients. shell is particularly useful in testing new features and
As the writes are always executed in the local file analyzing its impact on overall performance of the
system, the data is not written to the network unless the system. All file system operations are logged in a user
file is closed or the block boundary is reached. So, the specific folder for debugging purposes and performance
changes made to the last block of the file may not be analysis. If any issue is encountered, the operation logs
visible to the reader clients while the write operation can be used to reproduce the issue and diagnose it.
2168-7161 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more
information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TCC.2016.2603474,
IEEE Transactions on Cloud Computing
400
can be transferred in a single block read/write request.
# of Broadcast Packets
Distributed Architecture 400
# of Broadcast Packets
350 Distributed Architecture
Centralized Architecture 350 Centralized Architecture
However, when input dataset size is increased further, 300
250
300
250
one additional request is required for extra data and 200
200
reads and 2.12 MB/s for writes for file sizes that are 0
0 10 20 30 40 50
0
4 5 6 7 8 9 10
multiples of block size. Size of Input Dataset (MB) Cluster Size
less than linear time with input dataset size. For larger 1000
datasets, there is a sufficient number of tasks that can
800
be executed in parallel across the cluster resulting in
better node utilization and improved performance. 600
400
6.6 Centralized versus Distributed Architecture
200
The major difference between the distributed solution
0
and the centralized solution is that nodes in distributed 0 20 40 60 80 100
solution need to continuously synchronize their Name Size of Input Dataset (MB)
Server and Fragment Mapper. Due to the synchro-
nization, the distributed solution needs to broadcast Fig. 12. New task scheduling algorithm vs. Random
directory information after a file is created or updated. significant. Hence, a centralized approach is preferred
The broadcast messages directly impact the perfor- in large clusters. However, data reliability is guaranteed
mance difference between the centralized architecture by k-out-of-n framework in both architectures.
and the distributed architecture. When a MapReduce
job has more read operations, distributed architecture 6.7 Energy-aware task scheduling v.s. Random task
might perform better as all metadata information can scheduling
be queried locally rather than contacting the centralized As mentioned in Section 4.5, our energy-aware task
server; when a MapReduce task has more write opera- scheduling assigns tasks to taskTrackers considering the
tions, centralized architecture might perform better due locations of data fragments. The default task scheduling
to lesser broadcast messages. algorithm in Map-Reduce component is ineffective in
Figure 11(a) compares the number of broadcast mes- mobile ad-hoc network as the network topology in a
sages sent during file creation for different input dataset traditional data center is completely different from a
sizes. The block size is set to 4 MB. As input dataset size mobile network. Figure 12 compares the job completion
increases, the number of file blocks also increases. In a time between our energy-ware scheduling algorithm and
distributed architecture, each block allocation in Name a random task scheduling. The default Map-Reduce
Server and subsequent fragment information update in task scheduling in a mobile ad-hoc network is essen-
Fragment Mapper needs to be broadcast to all other tially a random task allocation. In both TeraGen and
nodes in the cluster so that their individual caches re- TeraSort experiments, our scheduling algorithm effec-
main in sync with each other. Large usage of bandwidth tively reduces the job completion time by more than
makes broadcasting a costly operation in wireless net- 100%. Lower job completion time indicates lower data
works. This effect is much worse when the cluster size retrieval time and lower data retrieval energy of each
grows. Figure 11(b) compares the number of broadcast taskTracker.
messages sent during file creation for varying cluster
sizes. The updates are not broadcast in a centralized 7 Roadmap for Mobile Hadoop 2.0
approach as the Name Server and Fragment Mappers Porting both the jobTracker and the taskTracker dae-
are singleton instances. mons to the Android environment is our ongoing work.
The results prove that the distributed architecture In future, we plan to integrate the energy-efficient
is ideal for medium sized clusters with independent and fault-tolerant k-out-of-n processing framework pro-
devices and no central server. The overhead due to posed in [9] into the Mobile Hadoop to provide better
broadcasting is minimal if the cluster is not large. For energy-efficiency and fault-tolerance in a dynamic net-
large clusters, the communication cost required to keep work. We will also look into the heterogeneous prop-
the metadata synchronized across all nodes becomes erties of the hardware and prioritize between various
2168-7161 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more
information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TCC.2016.2603474,
IEEE Transactions on Cloud Computing
devices based on the device specifications. For example, [12] E. E. Marinelli, “Hyrax: Cloud computing on mobile devices
if static devices are available in the network, they can using mapreduce,” Master’s thesis, School of Computer Sci-
ence Carnegie Mellon University, 2009.
be prioritized over other mobile nodes in the cluster [13] T. Kakantousis, I. Boutsis, V. Kalogeraki, D. Gunopulos,
for data storage as they are less likely to fail; if a G. Gasparis, and A. Dou, “Misco: A system for data analysis
more powerful node like a laptop is present, it can be applications on networks of smartphones using mapreduce,”
in Proc. Mobile Data Management, 2012.
assigned more tasks than a smartphone. How to balance [14] P. Elespuru, S. Shakya, and S. Mishra, “Mapreduce system
the processing load as well as the communication load over heterogeneous mobile devices,” in Software Technologies
of each node is a practical question that needs to be for Embedded and Ubiquitous Systems, 2009.
[15] F. Marozzo, D. Talia, and P. Trunfio, “P2p-mapreduce:
addressed. To mitigate the single point of failure issue in Parallel data processing in dynamic cloud environments,” J.
the centralized architecture, we plan to develop a hybrid Comput. Syst. Sci., 2012.
model where the Name Server and Fragment Mapper [16] C. A. Chen, M. Won, R. Stoleru, and G. G. Xie, “Energy-
efficient fault-tolerant data storage and processing in dy-
run concurrently on multiple master nodes. The hybrid namic networks,” in Proc. of MobiHoc, 2013.
model can reduce the load of each master node, tolerate [17] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The google file
failures, and improve the RPC execution time. system,” SIGOPS Oper. Syst. Rev., 2003.
[18] P. H. Carns, W. B. Ligon, III, R. B. Ross, and R. Thakur,
“Pvfs: A parallel file system for linux clusters,” in Proc. of
8 Conclusions Annual Linux Showcase & Conference, 2000.
[19] S. A. Weil, S. A. Brandt, E. L. Miller, D. D. E. Long,
The Hadoop MapReduce framework over MDFS and C. Maltzahn, “Ceph: A scalable, high-performance dis-
demonstrates the capabilities of mobile devices to cap- tributed file system,” in Proc. of OSDI, 2006.
[20] “Lustre file system,” http://www.lustre.org.
italize on the steady growth of big data in the mobile [21] “Hadoop 1.2.1 release,” http://hadoop.apache.org/docs/r1.
environment. Our system addresses all the constraints 2.1/releasenotes.html.
of data processing in mobile cloud - energy efficiency,
data reliability and security. The evaluation results Johnu George received his B.Tech degree
show that our system is capable for big data analytics in Computer Science from National Institute
of Technology Calicut, India in 2009. He
of unstructured data like media files, text and sensor was a research engineer at Tejas Networks,
data. Our performance results look very promising for Bangalore during 2009-2012. He completed
the deployment of our system in real world clusters for his M.S. degree in Computer Science from
Texas A&M University in 2014. His research
big data analytic of unstructured data like media files, interests include distributed processing and
text and sensor data. big data technologies for mobile cloud.
Acknowledgment
Chien-An Chen received the BS and MS
This work was supported by Naval Postgraduate School degree in Electrical Engineering from Univer-
under Grant No. N00244-12-1-0035 and NSF under sity of California, Los Angeles in 2009 and
Grants #1127449, #1145858 and #0923203. 2010 respectively. He is currently working
toward the PhD degree in Computer Science
and Engineering at Texas A&M University.
References His research interests are mobile computing,
energy-efficient wireless network, and cloud
[1] S. Huchton, G. Xie, and R. Beverly, “Building and evaluating computing on mobile devices.
a k-resilient mobile distributed file system resistant to device
compromise,” in Proc. MILCOM, 2011.
[2] G. Huerta-Canepa and D. Lee, “A virtual cloud computing
provider for mobile devices,” in Proc. of MobiSys, 2010. Radu Stoleru is currently an associate pro-
[3] K. Kumar and Y.-H. Lu, “Cloud computing for mobile users: fessor in the Department of Computer Sci-
Can offloading computation save energy?” Computer, 2010. ence and Engineering at Texas A&M Uni-
[4] “Apache hadoop,” http://hadoop.apache.org/. versity. Dr. Stoleru’s research interests are
[5] S. George, Z. Wei, H. Chenji, W. Myounggyu, Y. O. Lee, in deeply embedded wireless sensor systems,
A. Pazarloglou, R. Stoleru, and P. Barooah, “Distressnet: a distributed systems, embedded computing,
wireless ad hoc and sensor network architecture for situation and computer networking. He is the recipient
management in disaster response,” Comm. Mag., IEEE, of the NSF CAREER Award in 2013. He has
2010. authored or co-authored over 80 conference
[6] J.-P. Hubaux, L. Buttyán, and S. Capkun, “The quest for and journal papers with over 3,000 citations.
security in mobile ad hoc networks,” in Proc. of MobiHoc,
2001.
[7] H. Yang, H. Luo, F. Ye, S. Lu, and L. Zhang, “Security in Geoffery G. Xie received the BS degree
mobile ad hoc networks: challenges and solutions,” Wireless in computer science from Fudan University,
Communications, IEEE, 2004. China, and the PhD degree in computer
[8] C. A. Chen, M. Won, R. Stoleru, and G. Xie, “Resource sciences from the University of Texas, Austin.
allocation for energy efficient k-out-of-n system in mobile ad He is a professor in the Computer Science
hoc networks,” in Proc. ICCCN, 2013. Department at the US Naval Postgraduate
[9] C. Chen, M. Won, R. Stoleru, and G. Xie, “Energy-efficient School. He has published more than 60 ar-
fault-tolerant data storage and processing in dynamic net- ticles in various areas of networking. His
work,” in MobiHoc, 2013. current research interests include network
[10] K. Shvachko, H. Kuang, S. Radia, and R. Chansler, “The analysis, routing design and theories, un-
hadoop distributed file system,” in Proc. of MSST, 2010. derwater acoustic networks, and abstraction
[11] J. Dean and S. Ghemawat, “Mapreduce: Simplified data driven design and analysis of enterprise networks.
processing on large clusters,” Commun. ACM, 2008.
2168-7161 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more
information.