More info

• Group members
• Publications
• Coauthors
• Talks
• Thesis
• CV
• Related Conferences

Research news

• April 2008
  I was named a Microsoft New Faculty Fellowship Finalist. Congratulations to the other finalists and the 5 new Fellows.
• April 2008
  John Musacchio from UC Santa Cruz will be visiting the week of the 9th.
• March 2008
  My thesis was given an Honorable Mention among the finalists for the dissertation award for operations research in telecommunications given by INFORMS.
• February 2008
  Heavy-tails expert Bert Zwart will be visiting the week of the 25th.
• February 2008
  My paper with Misja was accepted to Sigmetrics!
• January 2008
  My thesis is a finalist for the dissertation award for operations research in telecommunications given by INFORMS.
• December 2007
  My thesis is a co-recipient of the 2007 CMU SCS Distinguished Dissertation Award.

Seminars

• CS
• Lunch Bunches
• EE
• ACM
• CMI
• SISL
• HSS
• IQI

QoS for Databases

People

Bianca Schroeder
Mor Harchol-Balter
Arun Iyengar
Erich Nahum
Adam Wierman

Motivation

There is a strong economic motivation for online retailers (e.g. Amazon) to provide lower response times to their more important, ``big-spending'' clients, so as not to lose these clients. It is likewise financially desirable to offer certain clients Service Level Agreements (SLAs) to guarantee them certain QoS goals, such as high throughput or low mean response time. Because the dominant time associated with serving a dynamic web request is the time spent at the backend database/storage system, it is important that the QoS be applied to the backend database/storage system to control the time spent there. Unfortunately, most commercial database management systems (DBMS), which lie at the heart of e-commerce applications, do not provide effective transaction prioritization for transactional, web-driven workloads.  In this project we investigate the possibility of achieving service differentiation for database transactions using external scheduling.

Results and Impact

The goal of this project is to design a new approach for service differentiation in backend servers which is portable across different DBMS, storage devices, caches, and other backend servers. We develop an External QoS Management System (EQMS), that sits between the web server (or the application server) and the backend server. The key idea of the EQMS is to maintain an upper limit on the number of transactions executing simultaneously within the DBMS (called the Multi-Programming Limit, or ``MPL''). If a transaction arrives and finds MPL number of transactions already in the DBMS, the arriving transaction is held back in an external queue (no transactions are dropped). QoS targets are then achieved by scheduling the external queue. Response time for a transaction includes both waiting time in the external queue (queuing time) and time spent within the DBMS (execution time).

This approach of encapsulating QoS functionality in the EQMS outside the database has many advantages: it doesn't require any changes to the DBMS and hence is portable across DBMS and is marketable as an independent black-box device. The approach is also effective across different workloads and changing workloads, since the scheduling isn't tied to a particular bottleneck resource inside the DBMS. 

Building the EQMS involves two key challenges.

1) Choosing the MPL: The performance of the EQMS depends critically on the particular multiprogramming limit used (the MPL), i.e. the number of transactions allowed into the database. If the MPL is too low, throughput will suffer, since not all DBMS resources will be utilized. On the other hand, if the MPL is too high, there is insufficient control on scheduling. The question of how to adjust the MPL to achieve both goals simultaneously is an open problem, not just for databases but in system design in general.

In our work, we first investigate the question of whether there exists an MPL that is low enough to provide good service differentiation, while not harming throughput or overall mean response time. We find, using benchmark driven workloads, that such an MPL does in fact exist. Then we develop a feedback based controller, augmented by queueing theoretic models for automatically adjusting the MPL.

2) Scheduling to achieve QoS targets: A second key component of the EQMS is the scheduler which decides on the order in which transactions are dispatched to the DBMS such that the associated QoS targets are met. The scheduler allows for an arbitrary number of different QoS classes, where the classes can differ in their arrival rates, transaction types, etc. Each class is associated with one or more QoS targets for (per-class) mean response time, percentiles of response time, variability in response time, best effort, or any combination thereof.

The core idea behind the scheduler is that, by maintaining a low MPL, we obtain a better estimate of a transaction's execution time within the DBMS, and hence we are able to maintain accurate estimates of the per-class mean execution times. This in turn gives us an upper bound on the queueing time for a transaction, which can be used by the scheduler in order to ensure that QoS targets are met.

Publications  

• Open versus closed: A cautionary tale
  Bianca Schroeder, Adam Wierman and Mor Harchol-Balter
  Proceedings of NSDI, 2006.
  Workload generators may be classified as based on a closed system model, where new job arrivals are only triggered by job completions (followed by think time), or an open system model, where new jobs arrive independently of job completions. In general, system designers pay little attention to whether a workload generator is closed or open. Using a combination of implementation and simulation experiments involving static and dynamic workloads, this paper illustrates that there is a vast difference in behavior between these open and closed models in real-world settings. In addition, this work synthesizes many of the differences in behavior between the models into eight simple principles.
• How to determine a good multi-programming level for external scheduling
  Bianca Schroeder, Mor Harchol-Balter, Arun Iyengar, Erich Nahum and Adam Wierman
  Proceedings of IEEE ICDE, 2006.
  Scheduling/prioritization of DBMS transactions is important for many applications that rely on database backends. A convenient way to achieve scheduling is to limit the number of transactions within the database, maintaining most of the transactions in an external queue, which can be ordered as desired by the application. While external scheduling has many advantages in that it doesn't require changes to internal resources, it is also difficult to get right, in that its performance depends critically on the particular multiprogramming limit used (the MPL), i.e. the number of transactions allowed into the database. If the MPL is too low, throughput will suffer, since not all DBMS resources will be utilized. On the other hand, if the MPL is too high, there is insufficient control on scheduling. The question of how to adjust the MPL to achieve both goals simultaneously is an open problem, not just for databases but in system design in general. Herein we study this problem in the context of transactional workloads, both via extensive experimentation and queueing theoretic analysis. We find that the two most critical factors in adjusting the MPL are the number of resources that the workload utilizes and the variability of the transactions' service demands. We develop a feedback based controller, augmented by queueing theoretic models for automatically adjusting the MPL. Finally, we apply our methods to the specific problem of external prioritization of transactions. We find that external prioritization can be nearly as effective as internal prioritization, without any negative consequences, when the MPL is set appropriately.