An Improved Search Algorithm for Resource Allocation in Cloud Databases

The Virtual Design Advisor (VDA) has addressed the problem of optimizing the performance of Database Management System (DBMS) instances running on virtual machines that share a common physical machine pool. In this work, the search algorithm in the optimization module of the VDA is improved. An Exhaustive Greedy algorithm (EG) studies the effectiveness of tuning the allocation of the shared resources (the share values); and presents a mathematical analysis of the effect of the share values on reaching an optimal solution. Also, it studies the effect of the share values of resources on the feasibility and speed of reaching an optimal solution. On the other hand, the particle swarm optimization (PSO) heuristic is used as a controller of the greedy heuristic algorithm to reduce trapping into local optima. Our proposed algorithm, called Greedy Particle Swarm Optimization (GPSO), was evaluated using prototype experiments on TPC-H benchmark queries against PostgreSQL instances in Xen virtualization environment. Our results show that the GPSO algorithm required more computation but in many test cases succeeded to escape local optima and reduce the cost as compared to the greedy algorithm alone. Also, the EG search algorithm was faster than the GPSO algorithm when the search space of the share values grow