Dynamic resource brokering for multi-user query execution

ABSTRACT

We propose a new framework for resource allocation based on concepts from microeconomics. Specifically, we address the difficult problem of managing resources in a multiple-query environment composed of queries with widely varying resource requirements. The central element of the framework is a resource broker that realizes a profit by "selling" resources to competing operators using a performance-based "currency." The guiding principle for brokering resources is profit maximization. In other words, since the currency is derived from the performance objective, the broker can achieve the best performance by making the scheduling and resource allocation decisions that maximize profit. Moreover, the broker employs dynamic techniques and adapts by changing previous allocation decisions while queries are executing. In a first validation study of the framework, we developed a prototype broker that manages memory and disk bandwidth for a multi-user query workload. The performance objective for the prototype broker is to minimize slowdown with the constraint of fairness. Slowdown measures how much higher the response time is in a multi-user environment than a single-user environment, and fairness measures how even is the degradation in response time among all queries as the system load increases, Our simulation results show the viability of the broker framework and the effectiveness of our query admission and resource allocation policies for multi-user workloads.

REFERENCES

• BiG88: Dina Bitton , Jim Gray, Disk Shadowing, Proceedings of the 14th International Conference on Very Large Data Bases, p.331-338, August 29-September 01, 1988
• BMC94: Kurt P. Brown , Manish Mehta , Michael J. Carey , Miron Livny, Towards Automated Performance Tuning for Complex Workloads, Proceedings of the 20th International Conference on Very Large Data Bases, p.72-84, September 12-15, 1994
• CLL85: M.J. Carey, M. Livny, and H. Lu, Dynamic Task Allocation in a Distributed Database System, in Proc. 5th Int'l. Conf. in Distr Computing Sys., IEEE Computer Society, 1985, 282.
• CoG94: Richard L. Cole , Goetz Graefe, Optimization of dynamic query evaluation plans, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.150-160, May 24-27, 1994, Minneapolis, Minnesota, United States
• DaG94: Diane L. Davison , Goetz Graefe, Memory-Contention Responsive Hash Joins, Proceedings of the 20th International Conference on Very Large Data Bases, p.379-390, September 12-15, 1994
• Dav95: Diane Leslie Davison , Goetz Graefe, Dynamic resource allocation for multi-user query execution, 1995
• DGS90: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• FNS91: Christos Faloutsos , Raymond T. Ng , Timos K. Sellis, Predictive Load Control for Flexible Buffer Allocation, Proceedings of the 17th International Conference on Very Large Data Bases, p.265-274, September 03-06, 1991
• FYN88: D. Ferguson, Y. Yemini, and C. Nikolaou, Microeconomic Algorithms for Load Balancing in Distributed Computer Systems, Proc. 8th IEEE Int'l. Conf. on Distr. Computing Sys., San Jose, CA, June 1988.
• GlL89: E R. Glahe and D. R. Lee, Microeconomics Theory and Applications, Harcourt Brace Jovanovich, 1989.
• GrD93: G. Graefe , D. L. Davison, Encapsulation of Parallelism and Architecture-Independence in Extensible Database Query Execution, IEEE Transactions on Software Engineering, v.19 n.8, p.749-764, August 1993 [doi>10.1109/32.238579]
• Gru91: D. Grunwald, A Users Guide to AWESIME: An Object Oriented Parallel Programming and Simulation System, Univ. of Colorado Tech. Rep. Univ. of Colorado at Boulder-Comp. Sci.-552-91, Boulder, CO, November 1991.
• MeD93a: Manish Mehta , David J. DeWitt, Dynamic Memory Allocation for Multiple-Query Workloads, Proceedings of the 19th International Conference on Very Large Data Bases, p.354-367, August 24-27, 1993
• MeD93b: M. Mehta and D. DeWitt, Dynamic Memory Allocation for Multiple-Query Workloads, Univ. of Wisconsin - Madison Comp. Sci. Tech. Rep. 1151, 1993.
• NF91: Raymond Ng , Christos Faloutsos , Timos Sellis, Flexible buffer allocation based on marginal gains, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.387-396, May 29-31, 1991, Denver, Colorado, United States
• PCL93a: HweeHwa Pang , Michael J. Carey , Miron Livny, Memory-Adaptive External Sorting, Proceedings of the 19th International Conference on Very Large Data Bases, p.618-629, August 24-27, 1993
• PCL93b: Hwee Hwa Pang , Michael J. Carey , Miron Livny, Partially preemptible hash joins, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.59-68, May 25-28, 1993, Washington, D.C., United States
• PCL94: Hwee Hwa Pang , Michael J. Carey , Miron Livny, Managing memory for real-time queries, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.221-232, May 24-27, 1994, Minneapolis, Minnesota, United States
• SDK94: Michael Stonebraker , Robert Devine , Marcel Kornacker , Witold Litwin , Avi Pfeffer , Adam Sah , Carl Staelin, An economic paradigm for query processing and data migration in mariposa, Proceedings of the third international conference on on Parallel and distributed information systems, p.58-68, October 1994, Autin, Texas, United States
• WHH92: Carl A. Waldspurger , Tad Hogg , Bernardo A. Huberman , Jeffrey O. Kephart , W. Scott Stornetta, Spawn: A Distributed Computational Economy, IEEE Transactions on Software Engineering, v.18 n.2, p.103-117, February 1992 [doi>10.1109/32.121753]
• Yu93: Philip S. Yu , Douglas W. Cornell, Buffer management based on return on consumption in a multi-query environment, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.1-38, January 1993 [doi>10.1007/BF01231797]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Verification