New version page

How to determine a good multi-programming level for external scheduling

This preview shows page 1-2-3-4 out of 12 pages.

View Full Document
View Full Document

End of preview. Want to read all 12 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

How to determine a good multi-programming level for external schedulingBianca Schroeder§ Mor Harchol-Balter§∗§Carnegie Mellon UniversityDepartment of Computer SciencePittsburgh, PA USA<bianca, harchol, acw>@cs.cmu.eduArun Iyengar† Erich Nahum† Adam Wierman§†IBM T.J. Watson Research CenterYorktown Heights, NY USA<aruni,nahum>@us.ibm.comAbstractScheduling/prioritization of DBMS transactions is im-portant for many applications that rely on database back-ends. A convenient way to achieve scheduling is to limitthe number of transactions within the database, maintain-ing most of the transactions in an external queue, which canbe ordered as desired by the application. While externalscheduling has many advantages in that it doesn’t requirechanges to internal resources, it is also difficult to get rightin that its performance depends critically on the particularmultiprogramming limit used (the MPL), i.e. the number oftransactions allowed into the database. If the MPL is toolow, throughput will suffer, since not all DBMS resourceswill be utilized. On the other hand, if the MPL is too high,there is insufficient control on scheduling. The question ofhow to adjust the MPL to achieve both goals simultaneouslyis an open problem, not just for databases but in system de-sign in general. Herein we study this problem in the contextof transactional workloads, both via extensive experimenta-tion and queueing theoretic analysis.We find that the two most critical factors in adjusting theMPL are the number of resources that the workload utilizesand the variability of the transactions’ service demands. Wedevelop a feedback based controller, augmented by queue-ing theoretic models for automatically adjusting the MPL.Finally, we apply our methods to the specific problem of ex-ternal prioritization of transactions. We find that externalprioritization can be nearly as effective as internal prioriti-zation, without any negative consequences, when the MPLis set appropriately.1. IntroductionMany of todays web applications are largely dependenton a backend database, where the majority of the request∗Supported by NSF grants CCR-0133077, CCR-0311383, 0313148,and a 2005 Pittsburgh Digital Greenhouse Grant.processing time is spent. For such applications it is oftendesirable to control the order in which transactions are exe-cuted at the DBMS. An e-commerce applications for exam-ple might want to give faster service to those transactionscarrying a lot of revenue.Recently, systems researchers have started to investigatethe idea of external scheduling as a method of controllingthe order in which transactions are executed. The basicmechanism in external scheduling is demonstrated in Fig-ure 1, and simply involves limiting the number of transac-tions concurrently executing within the DBMS. This limitis referred to as the MPL (multi-programming limit). If theMPL is already met, all remaining transactions are queuedup in an external queue. The application can then controlthe order in which transactions are executed by schedulingthe external queue.DBMSMPL=4incomingtransactionsexternalqueueFigure 1. Simplified view of the mechanism used inexternal scheduling. A fixed limited number of trans-actions (MPL=4) are allowed into the DBMS simul-taneously. The remaining transactions are held backin an external queue. Response time is the time fromwhen a transaction arrives until it completes, includ-ing time spent queueing externally to the DBMS.Examples of recent work on external scheduling comefrom many areas including storage servers, web servers, anddatabase servers. For example, Jin et al. [9] develop an ex-ternal scheduling front-end to provide proportional sharingamong the requests at a storage service utility. Blanquer etal. [4] study external scheduling for quality of service pro-visioning at an Internet services cluster. In our own recentwork [22] we propose external scheduling for providingclass-based quality of service guarantees for transactional,database driven workloads. Finally, for many commercialDBMS there exist tools that provide mechanisms for exter-nal scheduling, such as the IBM DB2 Query Patroller [2].The advantage of the external approach is that it isportable and easy to implement since it does not requirechanges to complex DBMS internals. Moreover it is ef-fective across different types of workloads, since (unlikethe internal approach which directly schedules the resourcesinside the backend DBMS) external scheduling works inde-pendentlyof the system’s bottleneck resource. It is also veryflexible in that it allows applications to implement their owncustom-tailored scheduling policy, rather than being limitedto the policies supported by the backend DBMS.While the basic idea behind external scheduling is sim-ple, its efficacy in practice hinges on the right choice of theMPL. For scheduling to be most effective a low MPL is de-sirable, since then at any time only a small number of trans-actions will be executing inside the DBMS, while a largenumber are queued under the control of the external sched-uler. On the other hand, too low an MPL can hurt the over-all performance of the DBMS, e.g., by underutilizing theDBMS resources resulting in a drop in system throughput.While many have cited the problem of choosing the MPL inexternal scheduling as critical, previous research in all ar-eas of system design leaves it as an open problem. Existingtools for external scheduling leave the choice of MPL to thesystem administrator.The question of this paper is: How low can we choosethe MPL to facilitate effective scheduling, without hurtingoverallsystem performance? There are three important con-siderations when choosing an MPL: (1) As already men-tioned, by holding back transactions outside the DBMS, theconcurrency inside the DBMS is lowered, which can leadto a drop in throughput. We seek algorithms that determine,for any input scenario, the lowest possible MPL value nec-essary to ensure near-optimal throughput levels (when com-pared to the system without MPL). (2) Holding back trans-actions, and sequencing them (rather than letting them allshare the database resources concurrently), creates the po-tential for head-of-line (HOL) blocking where some long-running transactions prevent other shorter transactions fromentering the DBMS and receiving service. This can result inan actual increase in overall mean response time. We seekalgorithms that determine, for any input scenario, the low-est possible MPL


Loading Unlocking...
Login

Join to view How to determine a good multi-programming level for external scheduling and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view How to determine a good multi-programming level for external scheduling and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?