Stateful DRF: Considering the Past in a Multi-Resource Allocation

The multi-resource allocation problem arises in different scenarios. Different mechanisms have been proposed to fairly divide multiple resources, most notably, Dominant Resource Fairness (DRF). Even though DRF satisfies several desirable properties, it considers fairness only in the static setting. We propose Stateful DRF (SDRF), an extension of DRF that looks at past allocations and enforces fairness in the long run while keeping the fundamental properties of DRF. We prove that SDRF is strategyproof, since users cannot manipulate the system by misreporting their demands; incentivizes sharing, because no user is better off if resources are equally partitioned; and is efficient, as no allocation can be improved without decreasing another. In SDRF, users' priorities change over time. To avoid recalculating priorities at every task scheduling decision, we also propose Live Tree, a data structure that keeps elements with predictable time-varying priorities ordered. We implement SDRF on Mesos and run it in a real cluster. Moreover, we conduct large-scale simulations based on Google cluster traces of 30 million tasks over one month. Results show that SDRF reduces users' waiting time on average. This improves fairness, by increasing the number of completed tasks for users with lower demands, with negligible impact on high-demand users.