Home > Papers

 
 
A Graph-Based Conflict-Aware Load-Balancing Algorithm for Database Replication
Zheng Angen 1 #,Liao Jianxin 2 *,Wang Jing 2,Zhu Xiaomin 2
1.State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876; EBUPT Information Technology Co., Ltd., Beijing 100876
2.1. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China, 2. EBUPT Information Technology Co., Ltd. Beijing 100876, China
*Correspondence author
#Submitted by
Subject:
Funding: the Fundamental Research Funds for the Central Universities （No.BUPT2009RC0505）, National Natural Science Foundation of China （No.No. 61072057, 60902051, 61101119）, National 973 Program （No.No. 2012CB315802）, National Key Science & Technology Specific Project of China（No.No. 2011ZX03002-001-01, Research about Architecture of Mobile Internet）
Opened online:31 December 2011
Accepted by: none
Citation: Zheng Angen,Liao Jianxin,Wang Jing.A Graph-Based Conflict-Aware Load-Balancing Algorithm for Database Replication[OL]. [31 December 2011] http://en.paper.edu.cn/en_releasepaper/content/4455344
 
 
In this paper, we present a novel graph-based conflict-aware load-balancing algorithm: GBCA (Graph-Based Conflict-Aware) for certification-based database replication protocols to increase the concurrency and reduce the aborts due to the lack of synchronization during transaction executions. GBCA represents all concurrent transactions in the system and their conflict relationship using a graph, where transactions are represented by nodes and transaction conflicts are represented by edges connecting the inter-conflicting transactions. Node weights account for the complexity of transactions, while edge weights account for the odds of conflicting between different transaction types. We then apply a graph partitioning algorithm to splits this graph into k(the number of replicas) disjoin subsets such that the sum of the edge-weights spanning subsets, called edge-cut, is minimized, while subjecting to the constraint that the sum of the vertex-weights in each subset is balanced and that the virtual nodes (Each database server is represented as a virtual node) are splits into k distinct subsets. Thus, each subset has a unique virtual node which indicates the replica that the transactions of this subset should be assigned to. This graph operation approximates minimizing the number of inter-conflicting transaction executing on different replicas while balancing the load evenly across replicas. At each replica, we adopt a conflict-aware load control technique to avoid data contention thrashing casued by the concentration of inter-conflicting transactions to a single node.
Keywords:load balancing; database replication; abort rate
 
 
 

For this paper
  • ● PDF (0B)
  • ● Revision 0 　　
  • ● Print this paper
  • ● Recommend this paper to a friend
  • ● Add to my favorite list

    Saved Papers

    Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags
Add yours

Related Papers

Statistics
PDF Downloaded 243
Bookmarked 0
Recommend 5
Comments Array
Submit your papers