Efficient Optimization of User Costs in Microservice Deployment Through Distributed Column Generation

In microservice architecture, each industrial application is decomposed into multiple microservices and deployed on cloud servers to provide timely services to users. However, existing methods rarely optimize service deployment strategies from the user's perspective to reduce the leasing costs of cloud servers. Furthermore, accurately estimating the required number of instances and resource utilization for microservices remains challenging, and decision-making in large-scale scenarios also faces significant timeliness constraints. To solve this problem, this article proposes a Column Generation deployment strategy, which decomposes the microservice deployment problem into a master problem for scheme selection and subproblems for scheme generation and proves the gap between its convergent solution and the optimal solution. A Distributed Column Generation strategy is further introduced to enable efficient problem-solving. Experimental results based on real-world server pricing demonstrate that the proposed method exhibits a high degree of consistency with the theoretically optimal solution. Compared to the baseline methods, it reduces the average total cost of ownership (TCO) for users by 11.3%, while the decision-making time is only 21.5% of that of the comparative methods. At the same time we used our approach to make deployment decisions for real industrial microservices and deployed them on real cloud servers. Compared to the baseline approach, it reduces TCO by 4%, but decision-making is 97% faster.