Optimizing i/o-intensive transactions in highly interactive applications

ABSTRACT

The performance provided by an interactive online database system is typically measured in terms of meeting certain pre-specified Service Level Agreements (SLAs), with expected transaction latency being the most commonly used type of SLA. This form of SLA acts as a soft deadline for each transaction, and user satisfaction can be measured in terms of minimizing tardiness, that is, the deviation from SLA. This objective is further complicated for I/O-intensive transactions, where the storage system becomes the performance bottleneck. Moreover, common I/O scheduling policies employed by the Operating System with a goal of improving I/O throughput or average latency may run counter to optimizing per-transaction performance since the Operating System is typically oblivious to the application high-level SLA specifications. In this paper, we propose a new SLA-aware policy for scheduling I/O requests of database transactions. Our proposed policy synergistically combines novel deadline-aware scheduling policies for database transactions with features of Operating System scheduling policies designed for improving I/O throughput. This enables our proposed policy to dynamically adapt to workload and consistently provide the best performance.

REFERENCES

• 1: R. K. Abbott and H. Garcia-Molina. Scheduling I/O requests with deadlines: A performance evaluation. In RTSS, 1990.
• 2: Robert K. Abbott , Hector Garcia-Molina, Scheduling real-time transactions: a performance evaluation, ACM Transactions on Database Systems (TODS), v.17 n.3, p.513-560, Sept. 1992 [doi>10.1145/132271.132276]
• 3: Hal Berenson , Phil Bernstein , Jim Gray , Jim Melton , Elizabeth O'Neil , Patrick O'Neil, A critique of ANSI SQL isolation levels, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.1-10, May 22-25, 1995, San Jose, California, United States
• 4: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 5: Kurt P. Brown , Michael J. Carey , Miron Livny, Managing Memory to Meet Multiclass Workload Response Time Goals, Proceedings of the 19th International Conference on Very Large Data Bases, p.328-341, August 24-27, 1993
• 6: G. Buttazzo , M. Spuri , F. Sensini, Value vs. deadline scheduling in overload conditions, Proceedings of the 16th IEEE Real-Time Systems Symposium, p.90, December 05-07, 1995
• 7: M. J. Carey , R. Jauhari , M. Livny, Priority in DBMS resource scheduling, Proceedings of the 15th international conference on Very large data bases, p.397-410, July 1989, Amsterdam, The Netherlands
• 8: S. Chen, J. A. Stankovic, J. F. Kurose, and D. F. Towsley. Performance evaluation of two new disk scheduling algorithms for real-time systems. Real-Time Systems, 3(3):307--336, 1991.
• 9: Alan Fekete , Elizabeth O'Neil , Patrick O'Neil, A read-only transaction anomaly under snapshot isolation, ACM SIGMOD Record, v.33 n.3, September 2004 [doi>10.1145/1031570.1031573]
• 10: Shenoda Guirguis , Mohamed A. Sharaf , Panos K. Chrysanthis , Alexandros Labrinidis , Kirk Pruhs, Adaptive Scheduling of Web Transactions, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.357-368, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.137]
• 11: Christoffer Hall , Philippe Bonnet, Getting priorities straight: improving Linux support for database I/O, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: Sitaram Iyer , Peter Druschel, Anticipatory scheduling: a disk scheduling framework to overcome deceptive idleness in synchronous I/O, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 13: E. G. C. Jr. and M. Hofri. On the expected performance of scanning disks. SIAM J. Comput., 11(1):60--70, 1982.
• 14: B. Kao and H. Garcia-Molina. Subtask deadline assignment for complex distributed soft real-time tasks. In ICDCS, 1994.
• 15: Ben Kao , Hector Garcia-Molina, Deadline Assignment in a Distributed Soft Real-Time System, IEEE Transactions on Parallel and Distributed Systems, v.8 n.12, p.1268-1274, December 1997 [doi>10.1109/71.640019]
• 16: V. C. S. Lee, K. yiu Lam, B. Kao, K.-W. Lam, and S. lun Hung. Priority assignment for sub-transaction in distributed real-time databases. In RTDB, 1996.
• 17: David T. McWherter , Bianca Schroeder , Anastassia Ailamaki , Mor Harchol-Balter, Priority Mechanisms for OLTP and Transactional Web Applications, Proceedings of the 20th International Conference on Data Engineering, p.535, March 30-April 02, 2004
• 18: A. S. Meritt , J. A. Staubi , K. M. Trowell , G. Whistance , H. M. Yudenfriend, z/OS support for the IBM TotalStorage Enterprise Storage Server, IBM Systems Journal, v.42 n.2, p.280-301, April 2003
• 19: P. S. Ow , T. E. Morton, The single machine early/tardy problem, Management Science, v.35 n.2, p.177-191, Feb. 1989 [doi>10.1287/mnsc.35.2.177]
• 20: Adrian Daniel Popescu , Mohamed A. Sharaf , Cristiana Amza, SLA-Aware Adaptive On-demand Data Broadcasting in Wireless Environments, Proceedings of the 2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware, p.142-151, May 18-20, 2009 [doi>10.1109/MDM.2009.25]
• 21: A. L. N. Reddy , Jim Wyllie , K. B. R. Wijayaratne, Disk scheduling in a multimedia I/O system, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.1 n.1, p.37-59, February 2005 [doi>10.1145/1047936.1047941]
• 22: Chris Ruemmler , John Wilkes, An introduction to disk drive modeling, Computer, v.27 n.3, p.17-28, March 1994 [doi>10.1109/2.268881]
• 23: Bianca Schroeder , Mor Harchol-Balter, Web servers under overload: How scheduling can help, ACM Transactions on Internet Technology (TOIT), v.6 n.1, p.20-52, February 2006 [doi>10.1145/1125274.1125276]
• 24: Bianca Schroeder , Mor Harchol-Balter , Arun Iyengar , Erich Nahum, Achieving Class-Based QoS for Transactional Workloads, Proceedings of the 22nd International Conference on Data Engineering, p.153, April 03-07, 2006 [doi>10.1109/ICDE.2006.11]
• 25: Bianca Schroeder , Mor Harchol-Balter , Arun Iyengar , Erich Nahum , Adam Wierman, How to Determine a Good Multi-Programming Level for External Scheduling, Proceedings of the 22nd International Conference on Data Engineering, p.60, April 03-07, 2006 [doi>10.1109/ICDE.2006.78]
• 26: Mohamed A. Sharaf , Shenoda Guirguis , Alexandros Labrinidis , Kirk Pruhs , Panos K. Chrysanthis, Poster session: ASETS: A self-managing transaction scheduler, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering Workshop, p.56-62, April 07-12, 2008 [doi>10.1109/ICDEW.2008.4498285]
• 27: Rajendran M. Sivasankaran , John A. Stankovic , Don Towsley , Bhaskar Purimetla , Krithi Ramamritham, Priority assignment in real-time active databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.019-034, January 1996 [doi>10.1007/s007780050013]
• 28: Ari P. J. Vepsalainen, Priority rules for job shops with weighted tardiness costs, Management Science, v.33 n.8, p.1035-1047, August 1, 1987 [doi>10.1287/mnsc.33.8.1035]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Design, Performance

Keywords:
database systems, i/o scheduling, transaction processing