ROBUS: Fair Cache Allocation for Data-parallel Workloads
ROBUS: Fair Cache Allocation for Data-parallel Workloads
复制标题
ROBUS：数据并行工作负载的公平缓存分配
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Babu
中科院分区：
文献类型：
--
作者：
Mayuresh Kunjir;Brandon Fain;Kamesh Munagala;S. Babu
处理大数据的系统-例如，Hadoop、Spark和大规模并行数据库需要同时代表多个租户运行工作负载。这些系统中丰富的基于磁盘的存储通常由更小但更快的缓存补充。缓存是一种宝贵的资源：使用该高速缓存的租户可以看到两个数量级的性能提升。缓存也是一种有限的共享资源：与CPU核心等一次只能由一个租户使用的资源不同，缓存的数据项可以同时被多个租户访问。因此，缓存必须由多租户感知策略跨租户共享，每个租户都有一组唯一的优先级和工作负载特征。在本文中，我们开发的缓存分配策略，加快整体工作负载，同时公平地对待每个租户。我们建立了一个新的公平性模型，针对共享资源设置，不仅采用了更标准的帕累托效率和共享激励的概念，但我们也定义了嫉妒自由度的概念，从合作博弈论的核心。我们的缓存管理平台，ROBUS，使用随机化在小的时间批次，我们开发了一个按比例公平分配机制，满足预期的核心属性。我们证明了该算法和相关的公平算法可以在多项式时间内近似到任意精度。我们评估这些算法的ROBUS原型上实现的火花RDD存储作为缓存。我们对行业标准工作负载的评估表明，我们的算法在各种实际多租户设置中的性能和公平性指标上得分很高。
Systems for processing big data---e.g., Hadoop, Spark, and massively parallel databases---need to run workloads on behalf of multiple tenants simultaneously. The abundant disk-based storage in these systems is usually complemented by a smaller, but much faster, cache. Cache is a precious resource: Tenants who get to use the cache can see two orders of magnitude performance improvement. Cache is also a limited and hence shared resource: Unlike a resource like a CPU core which can be used by only one tenant at a time, a cached data item can be accessed by multiple tenants at the same time. Cache, therefore, has to be shared by a multi-tenancy-aware policy across tenants, each having a unique set of priorities and workload characteristics. In this paper, we develop cache allocation strategies that speed up the overall workload while being fair to each tenant. We build a novel fairness model targeted at the shared resource setting that incorporates not only the more standard concepts of Pareto-efficiency and sharing incentive, but we also define envy freeness via the notion of core from cooperative game theory. Our cache management platform, ROBUS, uses randomization over small time batches, and we develop a proportionally fair allocation mechanism that satisfies the core property in expectation. We show that this algorithm and related fair algorithms can be approximated to arbitrary precision in polynomial time. We evaluate these algorithms on a ROBUS prototype implemented on Spark with RDD store used as cache. Our evaluation on an industry-standard workload shows that our algorithms score high on both performance and fairness metrics across a wide variety of practical multi-tenant setups.