Karma: Resource Allocation for Dynamic Demands
Karma: Resource Allocation for Dynamic Demands
复制标题
DOI：
10.48550/arxiv.2305.17222
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Midhul Vuppalapati;Giannis Fikioris;R. Agarwal;Asaf Cidon;Anurag Khandelwal;É. Tardos
中科院分区：
文献类型：
--
作者：
Midhul Vuppalapati;Giannis Fikioris;R. Agarwal;Asaf Cidon;Anurag Khandelwal;É. Tardos
我们考虑在用户需求是动态的系统中公平分配资源的问题，也就是说，用户需求随时间变化。我们的主要观察是，用于资源分配的经典最大最小公平算法提供了许多理想的属性（例如，帕累托效率、策略验证性和公平性），但只有在用户需求随时间保持静态的强烈假设下。对于动态用户需求的现实情况，最大最小公平性算法失去了这些属性中的一个或多个。我们提出了一种新的动态用户需求资源分配机制Karma。Karma的关键技术贡献是基于信用的资源分配算法：在每个量子中，用户捐赠其未使用的资源，并在其他用户借用这些资源时分配信用；Karma精心编排用户之间的积分交换（基于他们的即时需求、捐赠的资源和借来的资源），并根据用户的积分执行优先级资源分配。我们从理论上建立了与动态用户需求的帕累托效率、策略验证和公平性相关的因果保证。对生产工作负载的经验评估表明，这些特性可以很好地转化为实践：Karma能够将用户之间的性能差异减少到最小，同时保持帕累托最优的系统范围性能。
We consider the problem of fair resource allocation in a system where user demands are dynamic, that is, where user demands vary over time. Our key observation is that the classical max-min fairness algorithm for resource allocation provides many desirable properties (e.g., Pareto efficiency, strategy-proofness, and fairness), but only under the strong assumption of user demands being static over time. For the realistic case of dynamic user demands, the max-min fairness algorithm loses one or more of these properties. We present Karma, a new resource allocation mechanism for dynamic user demands. The key technical contribution in Karma is a credit-based resource allocation algorithm: in each quantum, users donate their unused resources and are assigned credits when other users borrow these resources; Karma carefully orchestrates the exchange of credits across users (based on their instantaneous demands, donated resources and borrowed resources), and performs prioritized resource allocation based on users' credits. We theoretically establish Karma guarantees related to Pareto efficiency, strategy-proofness, and fairness for dynamic user demands. Empirical evaluations over production workloads show that these properties translate well into practice: Karma is able to reduce disparity in performance across users to a bare minimum while maintaining Pareto-optimal system-wide performance.