Fairness and Isolation in Multi-Tenant Storage as Optimization Decomposition

Shared storage services enjoy wide adoption in commercial clouds. But most systems today provide weak performance isolation and fairness between tenants, if at all. Most ap-proaches to multi-tenant resource allocation are based either on per-VM allocations or hard rate limits that assume uni-form workloads to achieve high utilization. Instead, Pisces, our system for shared key-value storage, achieves datacenter-wide per-tenant performance isolation and fairness. Pisces achieves per-tenant weighted fair sharing of sys-tem resources across the entire shared service, even when partitions belonging to different tenants are co-located and when demand for different partitions is skewed or time-varying. The focus of this paper is to highlight the opti-mization model that motivates the decomposition of Pisces’s fair sharing problem into four complementary mechanisms— partition placement, weight allocation, replica selection, and weighted fair queuing—that operate on different time-scales to provide system-wide max-min fairness. An evaluation of our Pisces storage prototype achieves nearly ideal (0.98 Min-Max Ratio) fair sharing, strong performance isolation, and robustness to skew and shifts in tenant demand. 1