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

Авторы

  • Л.Б. Соколинский

Ключевые слова:

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

Аннотация

В работе предлагается новый алгоритм замещения страниц LFU-K для буферизации обменов с дисками, ориентированный на использование в параллельных системах баз данных без совместного использования ресурсов. Данный алгоритм является обобщением хорошо известного алгоритма LFU. Для предложенного алгоритма LFU-K вводится формальная теоретико-вероятностная модель, на базе которой получены аналитические оценки параметров данного алгоритма. На базе алгоритма LFU-2 строится некоторый его модернизированный вариант LFU-2m, пригодный для использования в реальных системах баз данных. Приводятся результаты вычислительных экспериментов над искусственными и реальными трассами обращений к диску, подтверждающие высокую эффективность алгоритма LFU-2m применительно к параллельным системам баз данных без совместного использования ресурсов.

Новые вычислительные технологии

Загрузки

Опубликован

2002-04-03

Выпуск

Том 3 (2002): Выпуск 1.

Раздел

Раздел 2. Программирование

Автор

Л.Б. Соколинский

Челябинский государственный университет,
математический факультет
ул. Братьев Кашириных, 129, 454001, Челябинск

Библиографические ссылки

  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.