Efficient Serverless Resource Allocation for MapReduce Job Based on A* Algorithm
Chuanzhi Chen, Hongyan Sang, Jinquan Zhang, Hongqing Liu, Hao Chi · 2024
With the development of cloud computing technology, serverless computing models have gradually emerged. The existing serverless resource allocation framework, Astrea, models the resource allocation problem as the shortest path problem in graph theory and solves it using the Dijkstra algorithm, effectively addressing resource allocation issues. However, its computational complexity can be inefficient for large-scale applications. The A* algorithm generally outperforms Dijkstra's by avoiding unnecessary paths and converging more quickly, enhancing efficiency. This paper proposes an improved A* algorithm based on the serverless job scheduling and resource allocation framework, Astrea. Implement timely budget limit checks to reduce unnecessary path exploration. Priority queues and hash tables are used to enhance data access and path query efficiency. Optimize paths with heuristic function prioritization to focus on cost-effective routes. As a result, the search space is narrowed. The Astrea framework, implemented with the A * algorithm, enhances execution efficiency. Theoretical analysis and simulation experiments confirm this, showing approximately 30% improvement compared to traditional methods. The A* algorithm is applied to serverless resource allocation. It optimizes the algorithm for large-scale MapReduce tasks. The results demonstrate the algorithm's effectiveness in this new application.