Wednesday, August 24, 2016

2DFQ: Two-Dimensional Fair Queueing for Multi-Tenant Cloud Services
Presenter: Jonathan Mace
Co-authors: Peter Bodik, Madanlal Musuvathi, Rodrigo Fonseca, Krishnan Varadarajan

The key problem that the paper is trying to solve is to provide resource fairness to multiple tenants running in the cloud based systems. The paper makes the key observation that in cloud based systems multiple tenants tend to compete with each other for resources within the same shared process. The paper further points out that resource allocation done by operating systems or hypervisor is not suitable for these scenarios, and various fair schedulers like WFQ also achieve sub-optimal fairness.

With the above motivation in mind, the paper proposes a new fair scheduler 2DFQ. There are two main goals that 2DFQ is trying to achieve - (1) Ensure that the scheduler is work conservative, and (2) The schedule produced by the scheduler is not bursty. The key insight that 2DFQ uses is to modify WF2Q algorithm such that a request is eligible to be scheduled at different times for different worker threads, thus partitioning requests across. The paper further extends 2DFQ to scenarios where the request costs are not known in advance, via a pessimistic cost estimation.

For the purpose of evaluation, authors compared 2DFQ to WFQ and WF2Q. Some of the key results include one to two order of magnitude reduction in service lag variation by using 2DFQ and improvement in the 99th percentile latency of tenant requests by upto 198x.

Q: Results depend on the predictability of workloads, so how to incorporate for workloads whose predictabilty change over time?
A: The estimates used by the algorithm decay relatively quickly over time.

Q: This algorithm is work conserving and so there is some pattern that will drive it to worst case scenario. How do you account for it?
A: You can sacrifice work conserving property so that this doesn’t happen, but it can adversely affect the performance in other more common scenarios.

Q: Do you have any complexity result in the paper?
A: We thought about this but only in practical sense - whatever complexity is, it works fine in practice.

Q: Do you account for dependency between different threads?
A: Assumption is that there is no dependency or communication between threads.

Q: How difficult it is to incorporate dependency between the threads?
A: Do not have a concrete solution right now on how to do it.