Schedule multi-instance microservices to minimize response time under budget constraint in cloud HPC systems
Dong Wang, Hong Shen, Hui Tian, Yuanhao Yang · Journal of Parallel and Distributed Computing · 2025
In the emerging microservice-based architecture of cloud HPC systems, a challenging problem of critical importance for system service capability is how we can schedule microservices to minimize the end-to-end response time for user requests while keeping cost within the specified budget. We address this problem for multi-instance microservices requested by a single application to which no existing result is known to our knowledge. We propose an effective two-stage solution of first allocating budget (resources) to microservices within the budget constraint and then deploying microservice instances on servers to minimize system operational overhead. For budget allocation, we formulate it as the Discrete Time Cost Tradeoff (DTCT) problem which is NP-hard, present a linear program (LP) based algorithm, and provide a rigorous proof of its worst-case performance guarantee of 4 from the optimal solution. For microservice deployment, we show that it is harder than the NP-hard problem of 1-D binpacking through establishing its mathematical model, and propose a heuristic algorithm of Least First Mapping that greedily places microservice instances on fewest possible servers to minimize system operation cost. The experiment results of extensive simulations on DAG-based applications of different sizes demonstrate the superior performance of our algorithm in comparison with the existing approaches. • Formulate the problem of budget allocation to multi-instance microservices as the Discrete Time Cost Tradeoff (DTCT) problem, a well-known NP-hard problem. • Transform this problem to a linear program (LP) and present an approximation algorithm to minimize microservice completion time by determining the desired number of instances for each microservice within the given budget constraint. • Provide a rigorous proof of worst-case performance guarantee of 4 of our algorithm. • Present a heuristic algorithm of Least First Mapping for the problem of microservice deployment to place the microservice instances on fewest possible servers at minimum system operation cost. • Experimentally validate our algorithm and demonstrate its superiority to the existing approaches in terms of maximum completion time of microservices under budget constraint and the number of launched servers.