A new fragment re-allocation strategy for NoSQL database systems  

作　　者：Zhikun CHEN Shuqiang YANG Shuang TAN Li HE Hong YIN Ge ZHANG 

机构地区：[1]Department of Computer Science, National University of Defense Technology, Chang sha 410073, China [2]Unit 91655, People's Liberation Army, Beijing 100036, China [3]Beijing Aeronautics Engineering Technology Research Center, Beijing 100076, China

出　　处：《Frontiers of Computer Science》2015年第1期111-127,共17页中国计算机科学前沿（英文版）

基　　金：Thanks to the anonymous reviewers for their insightful comments. This work was supported by National High Technology Research and Development Plan of China （＂863＂ plan）（2012AA012600, 2012AA01A402, 2012AA01A401, 2011AA010702 and 2010AA012505）; the National Natural Science Foundation of China （Grant Nos. 60933005 and 91124002）; the National Key Technology Research and Development Program of China （2012BAH38B04 and 2012BAH38B06）; National 242 Information Security Program of China （2011A010）.

摘　　要：Abstract NoSQL databases are famed for the characteristics of high scalability, high availability, and high faulttolerance. So NoSQL databases are used in a lot of applications. The data partitioning strategy and fragment allocation strategy directly affect NoSQL database systems＇ performance. The data partition strategy of large, global databases is performed by horizontally, vertically partitioning or combination of both. In the general way the system scatters the related fragments as possible to improve operations＇ parallel degree. But the operations are usually not very complicated in some applications, and an operation may access to more than one fragment. At the same time, those fragments which have to be accessed by an operation may interact with each other. The general allocation strategies will increase system＇s communication cost during operations execution over sites. In order to improve those applications＇ performance and enable NoSQL database systems to work efficiently, these applications＇ fragments have to be allocated in a reasonable way that can reduce the communication cost i.e., to minimize the total volume of data transmitted during operations execution over sites. A strategy of clustering fragments based onhypergraph is proposed, which can cluster fragments which were accessed together in most operations to the same cluster. The method uses a weighted hypergraph to represent the fragments＇ access pattem of operations. A hypergraph partitioning algorithm is used to cluster fragments in our strategy. This method can reduce the amount of sites that an operation has to span. So it can reduce the communication cost over sites. Experimental results confirm that the proposed technique will effectively contribute in solving fragments re-allocation problem in a specific application environment of NoSQL database system.Abstract NoSQL databases are famed for the characteristics of high scalability, high availability, and high faulttolerance. So NoSQL databases are used in a lot of applications. The data partitioning strategy and fragment allocation strategy directly affect NoSQL database systems＇ performance. The data partition strategy of large, global databases is performed by horizontally, vertically partitioning or combination of both. In the general way the system scatters the related fragments as possible to improve operations＇ parallel degree. But the operations are usually not very complicated in some applications, and an operation may access to more than one fragment. At the same time, those fragments which have to be accessed by an operation may interact with each other. The general allocation strategies will increase system＇s communication cost during operations execution over sites. In order to improve those applications＇ performance and enable NoSQL database systems to work efficiently, these applications＇ fragments have to be allocated in a reasonable way that can reduce the communication cost i.e., to minimize the total volume of data transmitted during operations execution over sites. A strategy of clustering fragments based onhypergraph is proposed, which can cluster fragments which were accessed together in most operations to the same cluster. The method uses a weighted hypergraph to represent the fragments＇ access pattem of operations. A hypergraph partitioning algorithm is used to cluster fragments in our strategy. This method can reduce the amount of sites that an operation has to span. So it can reduce the communication cost over sites. Experimental results confirm that the proposed technique will effectively contribute in solving fragments re-allocation problem in a specific application environment of NoSQL database system.

关 键 词：fragment allocation NoSQL database hypergraph partition clustering fragments fragment correlation 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TN929.533[自动化与计算机技术—计算机科学与技术]