Введение к работе
Актуальность исследования. Кэширование – является универсальной методологией повышения производительности информационных систем массового обслуживания, в основу которой положен принцип комбинирования гетерогенных хранилищ данных, характеризуемых различной скоростью доступа. В связи с ростом популярности сетевых технологий и глобальной сети Интернет в последнее время наблюдается интенсивное увеличение заинтересованности исследователей во всем мире в повышении производительности web-систем, в том числе за счет использования кэширования на различных уровнях их функционирования: web-серверах, прокси-серверах, серверах баз данных, web-обозревателях конечных пользователей. Увеличению эффективности кэш-систем посвящены работы следующих исследователей: Aho A.V., Al-Zgool M.B.Y., Arlitt M.F., Belady L.A., Calzarossa M.C., Cao P., Chankhunthod A., Che H., Cherkasova L., Danzig P.B., Dahlin M., Denning P.J., Dilley J., Hall R.S., Hassan R., Irani S., Korupolu M.R., Lee D., Megiddo N., O'Neil E.J, O'Neil P.E., Pandurangan G., Patil J.B., Pawar B.V., Pierre G., Tanenbaum A.S., Smaragdakis Y., Szpankowski W., Tse P.K.C., Ulman J.D., Сахаров И.Е., Соколинский Л.Б., и других.
В основе оценки эффективности системы кэширования, как правило, лежат известные критерии «число кэш-попаданий» (англ. hit-ratio) и «взвешенное число кэш-попаданий» (англ. byte hit-ratio). Ядром системы кэширования, играющим определяющую роль в эффективности функционирования последней, является стратегия замещения, основная задача которой сводится к сохранению в кэш-памяти объектов, появление которых в трассе запросов в ближайшее время наиболее вероятно. Точность составления данного прогноза, основанного на явном или скрытом вычислении кэш-рейтинга объектов системы, а также требуемая для его определения вычислительная ресурсоемкость аппаратной платформы обусловливают эффективность кэш-системы. На вход системы кэширования поступают данные, попадающие под определение стохастического нестационарного процесса, вследствие чего одним из резервов повышения эффективности систем кэширования является возможность стратегии замещения адаптироваться к изменениям закона распределения объектов в потоке запросов.
Эти обстоятельства делают актуальным теоретическое и практическое исследование применения различных адаптивных стратегий замещения для повышения эффективности кэш-систем в системах обработки и хранения информации.
Целью диссертационного исследования является повышение быстродействия систем обработки и хранения информации за счет применения адаптивных систем кэширования.
Для достижения данной цели необходимо решить следующие задачи:
1) провести анализ существующих адаптивных стратегий замещения, их достоинств, недостатков, выделить характерные особенности их реализации, а также возможности применения в гетерогенных информационных системах;
2) разработать математическую модель абстрактной одноуровневой системы кэширования, позволяющую описывать существующие и разрабатываемые системы кэширования и использующую инвариантный математический аппарат;
3) разработать эффективный метод адаптации существующей модели управляемой гибридизации стратегий замещения, на базе комбинирования разнородных алгоритмов кэширования с использованием методов краткосрочного прогнозирования;
4) на базе разработанных методов реализовать адаптивные алгоритмы кэширования объектов в кэш-памяти;
5) разработать программные средства для экспериментального исследования эффективности реализованных стратегий замещения, а также внедрить разработанные методы в реальные информационные системы массового обслуживания.
Методы исследования. Для решения поставленных в диссертации задач использовались методы теории информационных систем и web-систем, методы системного анализа, математического моделирования, методы теории вероятностей и математической статистики, а также методы математического программирования.
С целью проведения имитационного моделирования была сформирована экспериментально-исследовательская база представляющая комплекс программных средств под названием «Программный стенд для исследования эффективности стратегий замещения», реализующих концепции объектно-ориентированной парадигмы.
Существенные научные результаты, полученные в диссертации, и степень их научной новизны:
1) математическая модель абстрактной одноуровневой системы кэширования, которая в отличие от известных моделей:
содержит модель стратегии замещения как отображение, возвращающее множество объектов кэш-памяти, которое необходимо заместить согласно заданной стратегии;
позволяет описывать гибридные алгоритмы кэширования, опирающиеся на любое число базовых стратегий замещения;
позволяет описывать алгоритмы кэширования, использующие размер в байтах объекта информационной системы для определения его кэш-рейтинга;
2) метод адаптивного векторного управления гибридным алгоритмом кэширования, в отличие от существующих реализующий краткосрочное прогнозирование значений управляющих параметров, что позволяет повысить число кэш-попаданий на нестационарных трассах, полученных на базе закона распределения Зипфа 20/80, в среднем на 10% и с вероятностью 0,95 не менее чем на 7%, что доказано представительным (более 1000 опытов) экспериментом;
3) адаптивный нечеткий on-line алгоритм кэширования для прокси-серверов, который в отличие от известных стратегий замещения, использует свойство пространственной локальности web-ресурсов. Предложенный алгоритм обоснован более чем на 1000 опытах и позволяет увеличить частоту кэш-попаданий для нестационарных стохастических трасс в среднем на 8% и с вероятностью 0,95 – не менее чем на 6%;
4) метод обнаружения изменения закона распределения появления объектов в трассе в системах обработки информации с использованием меры Махалонобиса (DCD - Detection of Changes in Distribution), который в отличие от известных позволяет с вероятностью не менее 0,95 обнаруживать изменение законов распределения объектов на циклических трассах и, следовательно, сохраняет эффективность для циклических трасс любой длины.
Теоретическая значимость диссертационной работы
1) разработанная модель является теоретической платформой для формального описания как существующих, так и новых стратегий замещения и, следовательно, может быть использована для синтеза новых алгоритмов кэширования и их гибридов;
2) применение пространственной локальности в качестве характеристики web-ресурсов может быть использовано для получения новых стратегий замещения и их дальнейшего использования в web-среде;
3) работа является приложением к учебному процессу, так как предложенные решения позволяют изучить и применять на практике идеи теории информационных систем, системного анализа, теории вероятностей, что необходимо при изучении дисциплин «Системы управления базами данных», «Методы и средства искусственного интеллекта» и «Internet».
Практическая полезность диссертационной работы заключается в следующем:
1) разработанная математическая модель позволила спроектировать и реализовать в рамках объектно-ориентированной парадигмы программный стенд, обеспечивающий исследование известных стратегий и синтезированных на их основе гибридов;
2) программное средство, реализующее метод синтеза потоков запросов, основанное на профилировании пространственно-временной локальности объектов в эталонных трассах;
3) спроектированные адаптивные алгоритмы кэширования положены в основу разработанной кэш-системы программно-алгоритмического каркаса CodeIgniter, внедренной в информационную систему поддержки образовательного процесса Донского государственного технического университета.
Апробация диссертационной работы. Материалы диссертационной работы апробировались на международной научной конференции (МНК) "Математические методы в технике и технологиях": ММТТ-22 (Иваново, 2009), ММТТ-23 (Иваново, 2010). На международном научно-методическом симпозиуме "Современные проблемы многоуровневого образования" (Дивноморск): 2008, 2010. На международном семинаре студентов, аспирантов и ученых «Системный анализ, управление и обработка информации» (Дивноморск): №1 – 2010, №2 – 2011, №3 – 2012. На международной научно-технической конференции «Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства» (Ростов н/Д): IX – 2010, X – 2012. Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях профессорско-преподавательского состава, сотрудников и студентов Донского государственного технического университета в 2010, 2011 и 2012 годах.
Публикации по теме диссертации. Основные результаты диссертации опубликованы в 15 работах, из которых 7 – самостоятельные публикации, в том числе одна монография. В 8 работах, опубликованных в соавторстве, доля материалов, принадлежащих автору диссертации, составляет не менее 50%. При этом 2 статьи, одна из которых самостоятельная публикация, опубликованы в ведущих научных журналах, входящих в список ВАК РФ. Кроме того, одна статья принята для публикации в 6-ом номере журнала «Вестник ДГТУ» за 2012 год, входящих в список ВАК РФ.
