Treator: a Fast Centralized Cluster Scheduling at Scale Based on B+ Tree and BSP
Yuzhao Wang, Junqing Yu, Zhibin Yu · 2021
Centralized cluster scheduling at scale achieves better task scheduling quality but incurs longer scheduling delay than decentralized scheduling, and vice versa. Moreover, scheduling policies may be application-specific, making it hard to employ only one scheduling policy to achieve short scheduling delay as well as high scheduling quality at the same time. This paper proposes a centralized cluster scheduling scheme which achieves short delay as well as high quality, named Treator. The key innovation is the use of two B+ trees and a BSP model in cluster scheduling. One B+ tree is used to maintain the states of cluster resources and the other one stores the resource indexes. The BSP model is leveraged to perform parallel scheduling based on the B+ trees, aiming to make the scheduling delay as short as possible. We implement Treator on Mesos and compare it against the scheduling policies used in Mesos and TPShare. The results show that Treator can significantly reduce the scheduling delays and improve application performance over Mesos and TPShare. In addition, Treator can also reduce the CPU consumption of a Mesos managed cluster by 21%.