Fragment Re-Allocation Strategy Based on Hypergraph for NoSQL Database Systems

Fragment Re-Allocation Strategy Based on Hypergraph for NoSQL Database Systems

Zhikun Chen (Unit 91655, People's Liberation Army, Beijing, China), Shuqiang Yang (Department of Computer Science, National University of Defense Technology, Changsha, China), Yunfei Shang (Unit 91655, People's Liberation Army, Beijing, China), Yong Liu (Unit 91655, People's Liberation Army, Beijing, China), Feng Wang (Unit 91655, People's Liberation Army, Beijing, China), Lu Wang (Unit 91655, People's Liberation Army, Beijing, China) and Jingjing Fu (Unit 95025, People's Liberation Army, Beijing, China)
Copyright: © 2016 |Pages: 23
DOI: 10.4018/IJGHPC.2016070101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

NoSQL database is famed for the characteristics of high scalability, high availability, and high fault-tolerance. It is used to manage data for a lot of applications. The computing model has been transferred to “computing close to data”. Therefore, the location of fragment directly affects system's performance. Every site's load dynamical changes because of the increasing data and the ever-changing operation pattern. So system has to re-allocate fragment to improve system's performance. The general fragment re-allocation strategies of NoSQL database scatter the related fragments as possible to improve the operations' parallel degree. But those fragments may interact with each other in some application's operations. So the high parallel degree of operation may increase system's communication cost such as data are transferred by network. In this paper, the authors propose a fragment re-allocation strategy based on hypergraph. This strategy uses a weighted hypergraph to represent the fragments' access pattern of operations. A hypergraph partitioning algorithm is used to cluster fragments in the strategy. This strategy can improve system's performance according to reducing the communication cost while guaranteeing the parallel degree of operations. Experimental results confirm that the strategy will effectively contribute in solving fragment re-allocation problem in specific application environment of NoSQL database system, and it can improve system's performance.
Article Preview

1. Introduction

With the development of Internet and Cloud Computing (S.K., 2007) technologies, the world has been in the information explosion era. For example, the number of internet's users and connected devices both rapidly grew in the decade years. So every application system has to face the challenge of big data (Big data, 2013) which is a hot field of academia and industrial community recently. The big data has been discussed in literatures (Nature, 2008; Bryant et al., 2008; sciencemag.com, 2011; Manyika et al., 2011; W. E. Forum, 20120; Economist, 2010, 2011; Lohr, 2012; Noguchi, 2011; Whitehouse, 2012) which involve a lot of fields such as government strategy, medicine, and economic strategy and so on. Under the big data environment, the data of the application system have the following characteristics (B.H., 2011): Volume (the scale of data and users are both very large), Variety (the data source and data type are both variety), Velocity (the increment speed of data is fast), and Value (the data has a lot of potential value). Under the big data era, how to store and manage the big data is a big problem for those application systems. The traditional database technologies can not satisfy the requirement of high concurrent users and operations. The emergence of NoSQL Database (B.H., 2013) provides a good solution for those applications' data storage and management.

NoSQL database is a new data management system, which is generated under the background of cloud computing. The computing model of big data environment transfers from “data close to computing” to “computing close to data as possible as it can”. The location of fragment will directly affect system's performance. Under the big data era, the load of sites dynamical changes because of the system's ever-changing operation pattern. So we have to dynamically regulate fragment's location to guarantee system's performance. The general fragment re-allocation strategies of NoSQL database scatter the related fragments as possible, which can improve the parallel degree of operation. But those fragments may interact with each other in some applications' operations. The high parallel degree of operations may increase the communication cost such as data are transferred by network. Kumar et al. (2013) had used some experiments to prove this issue in the distributed database. In this paper, the objective of our fragment re-allocation strategy is to reduce the total resource consumption according to reducing the number of machine involved in the execution of an operation (called operation span). In order to reduce the operation span, we should allocate the fragments with high relative to the same site as possible while guaranteeing the parallel degree of operation. We use a hypergraph model to represent the relative of fragment. A hypergraph partition algorithm will be used to cluster fragments, which has to cluster the relative fragments together while guaranteeing parallel degree of operation. Finally, a fragments cluster allocation algorithm will be proposed.

The contributions of this paper are as follows:

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing