Effective buffer management replacement algorithm for parallel shared-nothing database systems

Authors

  • L.B. Sokolinsky

Keywords:

параллельные системы баз данных
управление буферным пулом
алгоритмы замещения страниц
буферизации обменов
анализ эффективности

Abstract

We introduce a new approach to database disk buffering, called the LFU-K method. The LFU-K page replacement algorithm is an improvement of the Least Frequently Used (LFU) algorithm. A probability-theoretical model for a formal description of the LFU-K algorithm is proposed. Using this model, we obtain some estimates for the LFU-K parameters. An implementation of LFU-2 policy (called LFU-2m algorithm) is discussed. As we demonstrate with trace-driven simulation experiments, the LFU-2m algorithm performs better than the conventional buffering algorithm for the shared-nothing database system workloads.

New computational technologies

Downloads

Published

2002-04-03

Issue

Vol. 3 (2002): Issue 1.

Section

Section 2. Programming

Author Biography

L.B. Sokolinsky

Chelyabinsk State University,
Faculty of Mathematics

References

  1. Кнут Д.Э. Искусство программирования. 1. Основные алгоритмы. М.: Издательский дом «Вильямс», 2000.
  2. Кнут Д.Э. Искусство программирования. 3. Сортировка и поиск. М.: Издательский дом «Вильямс», 2000.
  3. Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002.
  4. Соколинский Л.Б. Организация параллельного выполнения запросов в многопроцессорной машине баз данных с иерархической архитектурой // Программирование. 2001. № 6. 13-29.
  5. Титчмарш Е.К. Теория дзета-функции Римана. М.: ИЛ, 1953.
  6. Цымблер М.Л., Соколинский Л.Б. Организация обработки больших объемов данных в многопроцессорных системах с массовым параллелизмом // Высокопроизводительные вычисления и их приложения. М.: Изд-во Моск. ун-та, 2000. 186-190.
  7. Aho A.V., Denning P.J., Ullman J.D. Principles of optimal page replacement // J. of the ACM. 1971. 18, N 1. 80-93.
  8. Belady L.A. A study of replacement algorithms for virtual-storage computer // IBM Systems Journal. 1966. 5, N 2. 78-101.
  9. Chou H.-T., DeWitt D.J. An evaluation of buffer management strategies for relational database systems // Proceedings of the 11th International Conference on Very Large Data Bases. Stockholm: Morgan Kaufmann, 1985. 127-141.
  10. Coffman E.G., Denning P.J. Operating systems theory. Englewood Cliffs: Prentice-Hall, 1973.
  11. Effelsberg W., Harder T. Principles of database buffer management // ACM Trans. on Database Systems. 1984. 9, N 4. 560-595.
  12. Gray J., Graefe G. The five-minute rule ten years later, and other computer storage rules of thumb // SIGMOD Record. 1997. 26, N 4. 63-68.
  13. Heising W.P. Note on random addressing techniques // IBM Systems Journal. 1963. 2, N 2. 112-116.
  14. Johnson T., Shasha D. 2Q: a low overhead high performance buffer management replacement algorithm // Proceedings of the 20th International Conference on Very Large Data Bases. 1994. Santiago de Chile: Morgan Kaufmann, 1994. 439-450.
  15. Lee D., Choi J., Kim J.-H., Noh S.H., Min S.L., Cho Y., Kim C.-S. On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies // International Conference on Measurement and Modeling of Computer Systems. Atlanta, 1999. 134-143.
  16. Mattson R.L., et al. Evaluation techniques for storage hierarchies // IBM Systems Journal. 1970. 9, N 2. 78-117.
  17. O’Neil E.J., O’Neil P.E., Weikum G. The LRU-K page replacement algorithm for database disk buffering // Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. Washington, D.C.: ACM Press. 1993. 297-306.
  18. O’Neil E.J., O’Neil P.E., Weikum G. An optimality proof of the LRU-K page replacement algorithm // J. of the ACM. 1999. 46, N 1. 92-112.
  19. Rahm E., Marek R. Analysis of dynamic load balancing strategies for parallel shared nothing database systems // The 19th International Conference on Very Large Data Bases. Dublin: Morgan Kaufmann, 1993. 182-193.
  20. Robinson J.T., Devarakonda M.V. Data cache management using frequency-based replacement // 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems. University of Colorado. Boulder, 1990. 134-142.
  21. Sacco G. M., Schkolnick M. Buffer management in relational database systems // ACM Transactions on Database Systems. 1986. 11, N 4. 473-498.
  22. Sleator D.D., Tarjan R.E. Amortized efficiency of list update and paging rules // Communications of the ACM. 1985. 28, N 2. 202-208.
  23. Smaragdakis Y., Kaplan S., Wilson P.R. EELRU: simple and effective adaptive page replacement // International Conference on Measurement and Modeling of Computer Systems. Atlanta, 1999. 122-133.
  24. Sokolinsky L.B. Design and evaluation of database multiprocessor architecture with high data availability // The 12th International DEXA Workshop. Munich, 2001. 115-120.
  25. Stonebraker M. Operating system support for database management // Communications of the ACM. 1981. 24, N 7. 412-418.
  26. Wilschut A.N., Flokstra J., Apers P.M. G. Parallel evaluation of multi-join queries // Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. San Jose: ACM Press, 1995. 115-126.
  27. Zipf G.K. Human behavior and the principle of least effort: an introduction to human ecology. Reading: Addison-Wesley, 1949.