автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Адаптивные алгоритмы кэширования в информационных системах

^ - рукописи

00500*»**'

ЖУКОВ АЛЕКСАНДР ИГОРЕВИЧ

АДАПТИВНЫЕ АЛГОРИТМЫ КЭШИРОВАНИЯ В ИНФОРМАЦИОННЫХ СИСТЕМАХ

Специальность 05.13.01 - Системный анализ, управление и обработка информации

Автореферат диссертации на соискание ученой степени кандидата технических наук

- 8 НОЯ 2012

Ростов-на-Дону - 2012 г.

005054523

Работа выполнена на кафедре «Программное обеспечение вычислительной техники и автоматизированных систем», ФБГОУ ВПО «Донской государственный технический университет» (ДГТУ).

Научный руководитель: кандидат технических наук, профессор

Гранков Михаил Васильевич

Официальные оппоненты: доктор технических наук, профессор

Фатхи Владимир Ахатович Институт энергетики и машиностроения ДГТУ, г. Ростов-на-Дону

кандидат технических наук, доцент, Хашковский Валерий Валерьевич, Таганрогский технологический институт ЮФУ, Таганрог

Ведущая организация: ФГАОУ ВПО «Южный федеральный

университет»

Защита состоится 15 ноября 2012 года в 14-00 часов на заседании диссертационного совета Д212.058.04 ДГТУ:

344000, г. Ростов-на-Дону, пл. Гагарина, 1, ауд. № 252.

С диссертацией можно ознакомиться в библиотеке ДГТУ.

Автореферат разослан 12 октября 2012 г.

Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью, просим направлять ученому секретарю диссертационного совета Д212.058.04.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент

Могилевская Н.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования. Кэширование является универсальной методологией повышения производительности информационных систем массового обслуживания, в основу которой положен принцип комбинирования гетерогенных хранилищ данных, характеризуемых различной скоростью доступа. В связи с ростом популярности сетевых технологий и глобальной сети Интернет в последнее время наблюдается интенсивное увеличение заинтересованности исследователей во всем мире в повышении производительности web-систем, в том числе за счет использования кэширования на различных уровнях их функционирования: web-серверах, прокси-серверах, серверах баз данных, web-обозревателях конечных пользователей. Увеличению эффективности кэш-систем посвящены работы следующих исследователей: Aho A.V., AI-Zgool M.B.Y., Arlitt M.F., Belady LA, Calzarossa M.C., Cao P., Chankhunthod A., Che H., Cherkasova L, Danzig P.B., Dahlin M.7 Denning P.J., Dilley J., Hall R.S., Hassan R., Irani S., Korupolu M.R., Lee D., MegiddoN., O'Neil E.J, O'Neil P.E., Pandurangan G., PatilJ.B., Pawar B.V., Pierre G., Tanenbaum A.S., Smaragdakis Y., Szpankowski W., Tse P.K.C., Ulman J.D., Сахаров И.Е., Соколинский Л.Б., и других.

В основе оценки эффективности системы кэширования, как правило, лежат известные критерии «число кэш-попаданий» (англ. hit-ratio) и «взвешенное число кэш-попаданий» (англ. byte hitratio). Ядром системы кэширования, играющим определяющую роль в эффективности функционирования последней, является стратегия замещения, основная задача которой сводится к сохранению в кэшпамяти объектов, появление которых в трассе запросов в ближайшее время наиболее вероятно. Точность составления данного прогноза, основанного на явном или скрытом вычислении кэш-рейтинга объектов системы, а также требуемая для его определения вычислительная ресурсоемкость аппаратной платформы обусловливают эффективность кэш-системы. На вход системы кэширования поступают данные, попадающие под определение стохастического нестационарного процесса, вследствие чего одним из резервов повышения эффективности систем кэширования является возможность стратегии замещения адаптироваться к изменениям закона распределения объектов в потоке запросов.

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

Целью диссертационного исследования является повышение быстродействия систем обработки и хранения информации за счет применения адаптивных систем кэширования.

Для достижения данной цели необходимо решить следующие задачи:

1) провести анализ существующих адаптивных стратегий замещения, их достоинств, недостатков, выделить характерные особенности их реализации, а также возможности применения в гетерогенных информационных системах;

2) разработать математическую модель абстрактной одноуровневой системы кэширования, позволяющую описывать существующие и разрабатываемые системы кэширования и использующую инвариантный математический аппарат;

3) разработать эффективный метод адаптации существующей модели управляемой гибридизации стратегий замещения, на базе комбинирования разнородных алгоритмов кэширования с использованием методов краткосрочного прогнозирования;

4) на базе разработанных методов реализовать адаптивные алгоритмы кэширования объектов в кэш-памяти;

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

Методы исследования. Для решения поставленных в диссертации задач использовались методы теории информационных систем и шеЬ-сисгем, методы системного анализа, математического моделирования, методы теории вероятностей и математической статистики, а также методы математического программирования.

С целью проведения имитационного моделирования была сформирована экспериментально-исследовательская база представляющая комплекс программных средств под названием «Программный стенд для исследования эффективности стратегий замещения», реализующих концепции объектно-ориентированной парадигмы.

Существенные научные результаты, полученные в диссертации, и степень их научной новизны:

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) спроектированные адаптивные алгоритмы кэширования положены в основу разработанной кэш-системы программно-алгоритмического каркаса Codelgniter, внедренной в информационную систему поддержки образовательного процесса Донского государственного технического университета.

Апробация диссертационной работы. Материалы диссертационной работы апробировались на международной научной конференции (МНК) "Математические методы в технике и технологиях": ММТТ-22 (Иваново, 2009), ММТТ-23 (Иваново, 2010). На международном научно-методическом симпозиуме "Современные проблемы многоуровневого образования" (Дивноморск): 2008, 2010. На международном семинаре студентов, аспирантов и ученых «Системный анализ, управление и обработка информации» (Дивноморск): №1 - 2010, №2 - 2011, №3 - 2012. На международной научно-технической конференции «Инновация, экология и ресурсосберегающие технологии ка предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства» (Ростов н/Д): IX - 2010, X - 20Í2. Промежуточные материалы диссертационных исследований докладывались на ежегодных

научно-технических конференциях профессорско-

преподавательского состава, сотрудников и студентов Донского государственного технического университета в 2010, 2011 и 2012 годах.

Публикации по теме диссертации. Основные результаты диссертации опубликованы в 15 работах, из которых 7 -самостоятельные публикации, в том числе одна монография. В 8 работах, опубликованных в соавторстве, доля материалов, принадлежащих автору диссертации, составляет не менее 50%. При этом 2 статьи, одна из которых самостоятельная публикация, опубликованы в ведущих научных журналах, входящих в список ВАК РФ. Кроме того, одна статья принята для публикации в б-ом номере журнала «Вестник ДГТУ» за 2012 год, входящих в список ВАК РФ.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Работа состоит из зведения, четырех глав, заключения, списка литературы из 115 позиций, а также пять приложений. Объем основной части - 128 страниц, 20 таблиц, 32 рисунка.

В первой главе рассмотрены общие вопросы применения кэширования в качестве универсальной методологии увеличения производительности вычислительных систем.

Определены основные понятия и терминология, связанная с проектированием и реализацией кэш-систем, а также представлены особенности применения кэширования в web-приложениях.

Рассмотрены проблемы реализации кэш-систем, а именно: выбор структуры системы кэширования (одноуровневая, иерархическая, распределенная), обеспечение когерентности кэша, выбор размера кэш-памяти, а также выбор и реализация стратегии замещения.

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

характеристик объектов в трассе, а также на основе поведенческих особенностей различных стратегий замещения.

Отмечено, что разработанные в результате исследований новые алгоритмы кэширования могут быть сравнительно просто внедрены прикладными программистами в шеЬ-приложения и программное обеспечение прокси-серверов, что обусловлено открытостью исходных кодов этих систем.

Во второй главе представлена используемая методология исследования эффективности алгоритмов замещения на базе событийно-регулируемого метода моделирования, а также описаны типы трасс, на которых проводится имитационное исследование и ограничения, накладываемые на модель потока запросов.

Далее представлена математическая модель абстрактной стратегии замещения объектов в кэш-памяти, основанная на расширении и уточнении известной моделей АИо АЛ/. Пусть N представляет множество образов (идентификаторов) объектов системы:

Г представляет множество объектов системы:

Е = {е1,е2...е„}1 (2)

V - множество значений соответствующих размеров объектов системы:

где V/- размер объекта ег

Поток запросов (трасса) представляется упорядоченной последовательностью обращений к объектам системы:

о = (г1,г2..г,..^г), (4)

где г,еЫ- это обращение к объект/ системы (его идентификатор), запрошенному в момент времени £ при условии, что время дискретно, и в каждый момент времени не может быть более одного обращения к объекту системы.

Введем в рассмотрение - множество подмножеств множества

объектов £, которые могут быть размещены в кэш-памяти размера М\

(1)

(3)

где Б - это допустимое состояние кэш-памяти, определяемое как множество сохраненных в кэш-памяти объектов.

Таким образом, в любой момент в кэш-памяти может находиться любое подмножество множества объектов системы при условии, что совокупный размер объектов, находящихся в кэш-памяти, не превосходит М.

Тогда алгоритмом кэширования будем называть:

Л = ?о.я)/ (б)

где - множество состояний управления алгоритмом замещения, каждое из которых может быть представлено упорядоченной последовательностью кэш-рейтингов объектов системы;

е <2 - начальное состояние управления алгоритма

кэширования;

д- отображение перехода, которое, при получении идентификатора объекта, запрошенного у системы, обеспечивает определение по текущему состоянию кэш-памяти и состоянию управления новое допустимое состояние кэш-памяти (5), содержащее запрошенный объект, а также новое состояние управления:

(7)

Пусть представляет допустимое (5, еЗм) состояние кэшпамяти размером М в текущий момент времени

текущее значение состояние управления алгоритма замещения, а х - идентификатор запрошенного объекта (хеИ), тогда в соответствии с (7) д- это отображение вида:

е5.> (8)

где с! - это отображение из текущей конфигурации алгоритма кэширования, представляемой парой (5^) и идентификатора запрошенного объекта - х, во множество подмножеств множества объектов, вытесняемых из кэш-памяти в момент времени £

ЗЯм={7|Ус5(}. (10)

Отображение d определяет множество объектов Y, которое требуется вытеснить для размещения в кэш-памяти последнего запрошенного объекта г. При этом, в частном случае, когда v, —v2 =... = v„ множество К будет состоять из одного вытесняемого

объекта Y = {у}. Таким образом, в отличие от представленных ранее моделей, математическая модель абстрактной стратегии замещения позволяет описывать последние без учета ограничения на равенство всех объектов в кэш-системе.

Далее во второй главе предложенная математическая модель используется для описания сначала традиционных стратегий замещения (LRU, LFU), затем комбинационной стратегии замещения, использующей информацию о размере объектов при определении жертвы (GDS), а затем известного адаптивного алгоритма кэширования (ACR). Таким образом, удалось построить математические модели систем кэширования для алгоритмов различных классов, реализующих стратегии замещения, основанных на различных характеристиках объектов в трассе. В последствие полученные математические модели использовались при реализации алгоритмов кэширования и их исследования с помощью метода имитационного моделирования на разработанном программном стенде.

Далее во второй главе рассматривается метод управляемой стохастической гибридизации двух стратегий замещения. Метод позволяет реализовать адаптацию системы кэширования к изменению распределения объектов в потоке запросов с помощью управления влиянием каждой из двух базовых стратегий.

Затем в работе предлагается обобщение модели управляемой стохастической бигибридизации с возможностью получения гибридов с числом базовых алгоритмов более двух, а также с учетом предложенных выше уточнений, позволяющих описывать кэш-системы, использующие свойство «размер объекта». Для этого вводится в рассмотрение множество базовых алгоритмов замещения, объединяемых в вектор:

1 = (4,л2..Л£), (И)

где А/ - представляет алгоритм кэширования, определенный в соответствии (6).

Так как, алгоритмы в векторе (11) реализуют различные стратегии замещения, принципы расчета кэш-рейтинга объектов также различны. Введем в рассмотрение вектор д, представляющий упорядоченное множество значений состояний управления для соответствующих базовых алгоритмов кэширования:

где <7/ - состояние управление ¡-го алгоритма кэширования, при этом <7, е , при этом <2 - это множество состояний управления ¡-го

алгоритма кэширования.

Таким образом, ¡-ый алгоритм кэширования представляется как:

4=(а>я>,./), (13)

где множество состояний управления ¡-го алгоритма;

Я 01е Qi ~ начальное состояние управления алгоритма

кэширования;

f- общее для всех гибридизируемых алгоритмов отображение перехода, которое, при получении идентификатора объекта запрошенного у системы, обеспечивает определение по текущему состоянию кэш-памяти и вектору состояний управления новое допустимое состояние кэш-памяти, содержащее запрошенный объект, а также новое состояние управления для каждого алгоритма:

к, (14)

где I- параметр, используемый для выбора выполняемого алгоритма кэширования. Значения параметра /являются случайными и при этом находятся в интервале [0,1];

К - множество допустимых значений вектора управления гибридного алгоритма кэширования (12).

Для управления степенью влияния базовых алгоритмов кэширования в полученном гибриде введем в рассмотрение серию дополнительных безразмерных переменных:

где ^ - представляет ¡-ый параметр управления стохастическим гибридом и при этом удовлетворяет следующим ограничениям:

Кцц е I

: [ОД]/ (16)

л, <...<Л, <...< Vi- (17)

При выполнении процедуры замещения, гибридный стохастический алгоритм отдает предпочтение одной из гибридизируемых стратегий замещения. Тогда общее для всех базовых алгоритмов гибрида отображение перехода в новое допустимое состояние кэш-памяти:

{S, u HgJ(x « + £»,) ¿ М | е,. е S„ (18)

| е,- е 7j л | v.

i !

>M\et <*S„.

где дй - состояние управления к-го алгоритма кэширования в момент времени £

с1к - отображение перехода, определяющая текущую выполняемую стратегию замещения, которая при этом соответствует алгоритму кэширования Ак\

(19)

Правило для определения значения к, представляющего номер алгоритма кэширования из вектора А, в зависимости от значения случайного параметра /следующее: Г 1,7 <Я,;

А = (20).

1 + \,Х1<1<Ям \/1<{Ь-\).

Таким образом, описывается модель управляемой стохастической гибридизации любого числа базовых алгоритмов замещения, а также предлагается методология реализации, адаптации, которая в отличие от рассмотренных ранее моделей позволяет синтезировать гибриды, использующие более двух базовых алгоритмов кэширования. В заключение второй главы приводятся предложения о формальном определении целесообразности выполнения гибридизации по описанной методологии для известных алгоритмов кэширования, основанных на представленной в первой главе классификации стратегий замещения.

В третьей главе проводится обзор классов адаптивных систем управления и выбора схемы адаптации в соответствии с представленной классификацией. Описывается схема реализации самонастраивающейся поисковой системы адаптивного, векторного управления (рис. 1), в соответствие с представленной во второй главе математической моделью. Таким образом, адаптивная система используется для максимизации оценки вероятности заданного критерия эффективности кэш-системы на предыдущем участке трассы, т.е. в поиске наилучшего значения вектора А, при котором значение заданного критерия эффективности наибольшее. При этом, в зависимости от условий эксплуатации информационной системы, в качестве возможных критериев эффективности кэш-систем предлагается использовать следующие критерии:

• hit-ratio (HR) - отношение числа кэш-поданий к общему числу запросов объектов на участке трассы;

• byte hit-ratio (BHR) - отношение совокупного объема трафика представленного из кэш-памяти к общему трафику информационной системы на участке трассы;

• cost hit-ratio (CHR) - отношение совокупной стоимости получения объектов из кэш-памяти к общей стоимости получения объектов информационной системы на участке трассы.

Рисунок 1 - Схема реализации адаптивного управления кэшем

На вход системы кэширования и алгоритма адаптации поступает участок трассы, обозначенный mit). Алгоритм адаптации, запоминает

данный участок и находит значение управляющего вектора Л, обеспечивающее максимальное среднее значения процента кэш-попаданий (критерий HR), используя модель системы кэширования.

В отличие от представленной ранее модели адаптации гибридной стратегии замещения предлагается использование методов краткосрочного прогнозирования при вычислении значения управляющего вектора А и применение последнего для управления алгоритмом на текущем участке трассы. Прогнозирование в данном случае позволяет увеличить скорость реагирования системы адаптации на изменения, происходящие в потоке запросов, так как процесс поиска наилучшего значения вектора управления на предыдущем участке трассы требует на порядки большего временного ресурса.

Для увеличения скорости реагирования адаптивного алгоритма кэширования на изменение закона распределения в потоке запросов применяется метод обнаружения такого изменения, основанный на мере Махалонобиса, Метод, основанный на прямом применении этой меры, не реагирует на изменение законов распределения в случае их цикличности, начиная со второго цикла. Для устранения этого недостатка предложено улучшение данного метода, основанное на использовании механизма устаревания информации о частотах доступов к объектам системы.

В четвертой главе рассмотрена структура и особенности реализации разработанного программного стенда, позволяющего исследовать эффективность известных алгоритмов кэширования и их гибридов, в том числе адаптивных. Применение принципов объектно-ориентированного программирования позволило эффективно реализовать математическую модель абстрактной стратегии замещения с использованием понятия «абстрактный класс», а также реализовать конкретные алгоритмы замещения как экземпляры классов, которые являются наследниками абстрактного класса и соответствуют конкретной стратегии замещения. В программный класс, описывающий гибридную стратегию замещения, введены дополнительные поля, обеспечивающие реализацию отношения агрегирования между экземплярами этого класса и экземплярами 14

классов, представляющих известные стратегии замещения.

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

О 1000 2000 3000 4000 5000 6000 7000 S000 9000 время

Рисунок 2 - Визуальная иллюстрация метода генерации нестационарных трасс, базирующихся на законах Зипфа

Как видно из графика (рис. 3) предложенный адаптивный алгоритм кэширования (AHRC) на нестационарных трассах, полученных на базе законов Зипфа, обеспечивает устойчивый выигрыш по критерию hit-ratio.

Рисунок 3 - Результаты исследования стратегий замещения на нестационарных трассах, базирующихся на законах Зипфа

С помощью предложенного метода проектирования адаптивных систем кэширования представлена технология реализации интеллектуальной адаптивной системы кэширования, предназначенной для прокси-сервера Squid, на базе нечеткой логики, В качестве входных параметров, подаваемых после выполнения процедуры фазификации на блок нечеткого вывода, выступают как известные характеристики объектов в потоке запросов, такие как новизна, размер и стоимость кэшируемых данных, так и характеристика пространственной локальности объектов web-системы. Подобно известному применению данного свойства в кзш-системах микропроцессоров, близкими объектами считаются те объекты, которые расположены на одном web-сервере, остальные -далекими. В основе модификации нечеткой стратегии замещения находится эмпирическое суждение о том, что в случае обращения к объекту, расположенному на некотором web-cepsepe, вероятность доступов к близким с ним объектам в ближайшем будущем повышается. Последнее влияет на вычисление значения кэш-рейтинга объектов, основанное на процедуре нечеткого вывода.

В заключение раздела приведены результаты внедрения разработанных алгоритмов кэширования и сделаны выводы об эффективности их использования.

ЗАКЛЮЧЕНИЕ

1. Выполненный анализ существующих стратегий замещения позволил классифицировать алгоритмы кэширования, показал актуальность и значимость диссертационной работы, что позволило наметить возможные направления получения новых гибридов, а также определить возможности применения различных стратегий замещения в гетерогенных информационных системах.

2. Разработанная математическая модель абстрактной одноуровневой системы кэширования позволила реализовать метод векторного управления стохастической гибридизацией любого числа базовых стратегий замещения, что расширяет возможности разработки новых эффективных гибридных алгоритмов кэширования для информационных систем.

3. Предложенный метод адаптации модели управляемой гибридизации стратегий замещения, на базе комбинирования разнородных алгоритмов кэширования с использованием методов краткосрочного прогнозирования позволяет реализовать эффективную систему кэширования.

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

5. Разработанный программный стенд позволил экспериментально исследовать известные стратегии замещения, а также предложенные в работе гибридные алгоритмы кэширования и методы прогнозирования и на основании статистической обработки результатов экспериментов сделать выводы об их эффективности, подтвержденной выполненными внедрениями в реальные информационные системы. Данный стенд может быть использован в качестве инструментального средства для исследования и синтеза систем кэширования.

Таким образом, поставленная в диссертации цель достигнута.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рецензируемых научных журналах и изданиях

1. Жуков А.И. Методика тестирования результатов вертикальной кластеризации отношений / А.И. Жуков, М.В. Гранков // Вестник Донского гос. тех-ro ун-та, 2011, №8.

2. Жуков А.И. Модель адаптивного векторного управления стохастическим гибридным алгоритмом кэширования / А.И. Жуков // Вестник Донского гос. тех-го ун-та, 2012, №5.

Публикации, принятые к изданию в рецензируемых научных журналах и изданиях

3. Жуков А.И. Адаптивный нечеткий алгоритм кэширования для прокси-серверов / А.И. Жуков // Вестник Донского гос. тех-го ун-та, 2012, №6.

Публикации в других изданиях

4. Жуков А.И. Монография «Адаптивные гибридные стратегии замещения информации в кэш-памяти» / А.И. Жуков // Красноярск, 2012.

5. Жуков А.И. Математическая модель метода бигибридизации алгоритмов кэширования / А.И. Жуков, Мосаб Б.Ю. Аль Згуль // «В мире научных открытий» №4(10). Часть 13, г.Красноярск, 2010.

6. Жуков А.И. Математическая модель гибридного алгоритма кэширования информации / А.И. Жуков // «Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства». Труды IX Международной научно-технической конференции. - Ростов н/Д: ИЦ ДГГУ, 2010.

7. Жуков А.И. Модель адаптивной гибридной системы кэширования / А.И. Жуков // «Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства». Труды X Международной научно-технической конференции. - Ростов н/Д: ИЦ ДГГУ, 2012.

8. Жуков А.И. Программный стенд для исследования эффективности алгоритмов кэширования / А.И. Жуков // Системный анализ, управление и обработка информации: Труды 1-го Международного семинара студентов, аспирантов и ученых. - Ростов

н/Д: ИЦ ДГТУ, 2010.

9. Жуков А.И. Методика экспериментального исследования эффективности систем кэширования информации / А.И. Жуков, М.В. Гранков // Труды 2-го международного семинара под общ. ред. P.A. Недорфа - Ростов н/Д, изд. центр Доснк. гос. техн. ун-та, 2011.

10. Жуков А.И. Методология исследования эффективности систем кэширования / А.И. Жуков Ц Труды 3-го международного семинара под общ. ред. P.A. Недорфа - Ростов н/Д, изд. центр Доснк. гос. техн. ун-та, 2012.

11. Жуков А.И. Система кэширования программно-алгоритмического каркаса Codelgniter / А.И. Жуков, A.B. Штапов // Труды 3-го международного семинара под общ. ред. P.A. Недорфа -Ростов н/Д, изд. центр Доснк. гос. техн. ун-та, 2012.

12. Аль Згуль Мосаб Б.Ю. 'Толстый клиент" - технология оптимизации системы поддержки учебного процесса / Мосаб Б.Ю. Аль Згуль, А.И. Жуков // Математические методы в технике и технологиях: сб. тр. XXII междунар. науч. конференции. - Ростов-на-Дону, 2008.

13. Жуков А.И. Гибридный подход к решению проблемы миграции объектов информационных систем / А.И. Жуков, A.B. Слоновский, М.Е. Кириенко // Математические методы в технике и технологиях -ММТТ23: сб. тр. XIII Междунар. науч. конф. Т.12. Иваново, 2010.

14. Гранков М.В. Принципы интеграции разнородных систем поддержки учебного процесса в вузе / М.В. Гранков, Мосаб Б.Ю. Аль-Згуль, Жуков А.И. // Современные проблемы многоуровневого образования: сб. трудов И междунар. научно-методического симпозиума, ММТГ XX. - Россов н/Д: ИЦ ДГТУ, 2007.

15. Жуков А.И. Теоретическое и экспериментальное исследование методов интеграции гетерогенных подсистем управления ВУЗом / А.И. Жуков, М.В. Гранков, Д.С. Короткое // «Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства». Труды IX Международной научно-технической конференции. - Ростов н/Д: изд. центр ДПУ, 2010.

В работе [1] автором доказана нецелесообразность применения трасс с равномерным распределением объектов в потоке запросов в качестве входных данных при исследовании эффективности системы кэширования. В работе [5] автору принадлежит математическая модель гибридизации двух базовых алгоритмов замещения, В работе [9] автору принадлежит методика проведения исследований

стратегий замещения. В работе [II] автору принадлежит описание технологии разработки и внедрения системы кэширования для программно-алгоритмического каркаса Сос1е1дп№ег. В работе [12] автору принадлежит описание способа реализации кэширования в клиентских приложениях в рамках трехзвенной архитектуры. В работах [13-15] автором предлагается использование преимуществ методологии кэширования при решении задачи интеграции гетерогенных информационных систем.

В набор 08.10.2012 В печать 10.10.2012

Объем 1 усл.п.л,, 1.0 уч.-изд.л. Офсет. Формат 60x84/16. Бумага тип №3. Заказ № 577. Тираж 120.

Издательский центр ДГТУ Адрес университета и полиграфического предприятия 344000, г. Ростов-на-Дону, пл. Гагарина, 1.

ВВЕДЕНИЕ.

1 УНИВЕРСАЛЬНАЯ МЕТОДОЛОГИЯ УВЕЛИЧЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

1.1 Общие вопросы организации систем кэширования.

1.2 Особенности кэширования информации в web-системах.

1.3 Проблемы реализации кэш-систем.

1.3.1 Реализация иерархических кэш-систем.

1.3.2 Обеспечение согласованности данных кэша.

1.3.3 Влияние размера кэш-памяти на эффективность системы кэширования.

1.3.4 Выбор стратегии замещения объектов в кэш-памяти.

1.3.4.1 Идеальные стратегии замещения.

1.3.4.2 Стратегии замещения семейства LRU.

1.3.4.3 Специальные стратегии замещения.

1.3.4.4 Стратегии замещения семейства LFU.

1.3.4.5 Комбинационные стратегии замещения.

1.3.4.6 Нечеткие стратегии замещения.

1.3.4.7 Адаптивные стратегии замещения.

1.3.4.8 Классификация стратегий замещения.

1.4 Выводы по главе.

2 ИССЛЕДОВАНИЕ И МОДЕЛИРОВАНИЕ ОДНОУРОВНЕВЫХ СИСТЕМ КЭШИРОВАНИЯ.

2.1 Методология исследования эффективности алгоритмов замещения.

2.2 Математическая модель потока запросов.

2.3 Параметры количественного исследования и методы обработки полученных результатов.

2.4 Моделирование одноуровневой системы кэширования.

2.4.1 Математическая модель абстрактной одноуровневой системы кэширования.

2.4.2 Математические модели известных стратегий замещения.

2.4.2.1 Математическая модель LRU.

2.4.2.2 Математическая модель LFU.

2.4.2.3 Математическая модель GDS.

2.4.2.4 Математическая модель нечеткого алгоритма кэширования

2.4.2.5 Математическая модель ARC.

2.4.3 Обобщенная математическая модель управляемой стохастической гибридной системы кэширования.

2.5 Формализованная постановка решаемой научной задачи.

2.6 Выводы по главе.

3.1 Адаптивная кэш-система на базе стохастического гибридного алгоритма кэширования.

3.1.1 Реализуемая схема адаптации.

3.1.2 Методы поиска вектора управления стохастическим гибридным алгоритмом кэширования.

3.1.3 Увеличение скорости реагирования на изменения в трассе.

3.2 Адаптивная кэш-система web-pecypcoB на базе нечеткой логики.

3.3 Выводы по главе.

4 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ КЭШ-СИСТЕМ.

4.1 Программный стенд для исследования одноуровневых кэш-систем

4.2 Результаты экспериментальных исследований.

4.2.1 Сравнение алгоритмов кэширования на квазистационарных трассах.

4.2.2 Сравнение алгоритмов кэширования на трассах с петлеобразной моделью доступа.

4.2.3 Сравнение алгоритмов кэширования на нестационарных синтезированных трассах.

4.2.3 Сравнение алгоритмов кэширования на реальных трассах.

4.3 Практические результаты внедрения разработанных решений.

4.4 Выводы по главе.

Актуальность исследования. Кэширование является универсальной методологией повышения производительности информационных систем массового обслуживания, в основу которой положен принцип комбинирования гетерогенных хранилищ данных, характеризуемых различной скоростью доступа. В связи с ростом популярности сетевых технологий и глобальной сети Интернет в последнее время наблюдается интенсивное увеличение заинтересованности исследователей во всем мире в повышении производительности web-систем, в том числе за счет использования кэширования на различных уровнях их функционирования: web-серверах, прокси-серверах, серверах баз данных, web-обозревателях конечных пользователей. Увеличению эффективности кэш-систем посвящены работы следующих исследователей: Aho A.Y., Al-Zgool M.B.Y., ArlittM.F., Belady L.A., Cal-zarossa M.C., Cao P., Chankhunthod A., Che H., Cherkasova L., Danzig Р.В., Dahlin M., Denning P.J., DilleyJ., HallR.S., Hassan R., Irani S., Korupolu M.R., Lee D., MegiddoN., O'Neil E.J, OT4eil P.E., Pandurangan G., PatilJ.B., PawarB.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) разработать программные средства для экспериментального исследования эффективности реализованных стратегий замещения, а также внедрить разработанные методы в реальные информационные системы массового обслуживания.

Новые научные результаты, диссертационной работы:

1) математическая модель абстрактной одноуровневой системы кэширования, которая в отличие от известных моделей:

• содержит модель стратегии замещения как отображение, возвращающее множество объектов кэш-памяти, которое необходимо заместить согласно заданной стратегии;

• позволяет описывать гибридные алгоритмы кэширования, опирающиеся на любое число базовых стратегий замещения;

• позволяет описывать алгоритмы кэширования, использующие размер в байтах объекта информационной системы для определения его кэш-рейтинга;

2) метод адаптивного векторного управления гибридным алгоритмом кэширования, в отличие от существующих реализующий краткосрочное прогнозирование значений управляющих параметров, что позволяет повысить число кэш-попаданий на нестационарных трассах, полученных на базе закона распределения Зипфа 20/80, в среднем на 10% и с вероятностью 0,95 - не менее чем на 6%, что доказано представительным (более 1000 опытов) экспериментом;

3) адаптивный нечеткий online алгоритм кэширования для прокси-серверов, который в отличие от известных стратегий замещения, использует свойство пространственной локальности web-pecypcoB. Предложенный алгоритм обоснован более чем на 1000 опытах и позволяет увеличить частоту кэш-попаданий для нестационарных стохастических трасс в среднем на 8% и с вероятностью 0,95 - не менее чем на 6%;

4) метод обнаружения изменения закона распределения появления объектов в трассе в системах обработки информации с использованием меры Махаланобиса (DCD - Detection of Changes in Distribution), который в отличие от известных позволяет с вероятностью не менее 0,95 обнаруживать изменение законов распределения объектов на циклических трассах и, следовательно, сохраняет эффективность для циклических трасс любой длины.

Методы исследования. Для решения поставленных в диссертации задач использовались методы теории информационных систем и web-систем, методы системного анализа, математического моделирования, методы теории вероятностей и математической статистики, а также методы математического программирования.

С целью проведения имитационного моделирования была сформирована экспериментально-исследовательская база, представляющая комплекс программных средств под названием «Программный стенд для исследования эффективности стратегий замещения», реализующих концепции объектно-ориентированной парадигмы.

Теоретическая значимость диссертационной работы определяется несколькими составляющими:

1) разработанная модель является теоретической платформой для формального описания как существующих, так и новых стратегий замещения и, следовательно, может быть использована для синтеза новых алгоритмов кэширования и их гибридов;

2) применение пространственной локальности в качестве характеристики web-pecypcoB может быть использовано для получения новых стратегий замещения и их дальнейшего использования в web-среде.

Практическая полезность диссертационной работы заключается в следующем:

1) разработанная математическая модель позволила спроектировать и реализовать в рамках объектно-ориентированной парадигмы программный стенд, обеспечивающий исследование известных стратегий и синтезированных на их основе гибридов;

2) разработанное программное средство реализует метод синтеза потоков запросов, основанный на профилировании пространственно-временной локальности объектов в эталонных трассах;

3) работа используется в учебном процессе, а предложенные решения позволяют изучить и применять на практике идеи теории информационных систем, системного анализа, теории вероятностей, что необходимо при изучении дисциплин «Системы управления базами данных», «Методы и средства искусственного интеллекта» и «Internet»;

4) спроектированные адаптивные алгоритмы кэширования положены в основу разработанной кэш-системы программно-алгоритмического каркаса Codelg-niter, внедренной в информационную систему поддержки образовательного процесса Донского государственного технического университета.

Апробация диссертационной работы. Основные результаты диссертационной работы получили апробацию на следующих международных конференциях:

• на XXII Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-22), Иваново, 2009;

• на XXIII Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-23), Иваново, 2010;

• на III международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования», Дивноморск, 2008;

• на IV международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования», Дивноморск, 2010;

• на I международном семинаре студентов, аспирантов и ученых «Системный анализ, управление и обработка информации», Дивноморск, 2010;

• на II международном семинаре студентов, аспирантов и ученых «Системный анализ, управление и обработка информации», Дивноморск, 2011;

• на III международном семинаре студентов, аспирантов и ученых «Системный анализ, управление и обработка информации», Дивноморск, 2012;

• на IX международной научно-технической конференции «Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства», Ростов-на-Дону, 2010;

• на X международной научно-технической конференции «Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства», Ростов-на-Дону, 2012.

Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях профессорско-преподавательского состава, сотрудников и студентов Донского государственного технического университета в 2010, 2011 и 2012 годах.

Публикации. По теме диссертационного исследования опубликовано 15 печатных работ (три в издании, включенном в перечень ВАК), в которых отражены его основные результаты.

Структура и объём работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 115 позиций, а также пяти приложений. Объем основной части - 128 страниц, 20 таблиц, 32 рисунка.

4.4 Выводы по главе

Разработанный программный стенд позволил реализовать имитационное моделирование известных стратегий замещения, с использованием математических моделей разработанных во второй главе. С помощью моделирования удалось осуществить оценку эффективности различных алгоритмов кэширования по критериям рейтинг кэш-попаданий и взвешенный рейтинг кэш-попаданий на квазистационарных, циклических, нестационарных и реальных трассах.

На стенде экспериментально подтверждены сделанные теоретические выводы, эффективность предложенных моделей и разработанных адаптивных алгоритмов. Было показано, что разработанный гибрид AHRC, базирующийся на трех стратегиях кэширования LRU-min, GDSF и LFU, позволяет увеличить частоту кэш-попаданий для нестационарных трасс, полученных на базе чередования стационарных участков, соответствующих закону распределения Зипфа "20-80", в среднем на 10% и с вероятностью 0,95 не менее чем на 7% .

Применение в алгоритме AHRC модуля прогнозирования, а также модифицированного метода обнаружения изменения закона распределения вероятностей появления объектов в запросах к системе обработки информации с использованием метрики Махаланобиса, позволило сохранить эффективность применения данной метрики для трасс с циклическим изменением закона распределения.

Обработка результатов экспериментов на реальных трассах, полученных с использованием журналов работы кэширующего прокси-сервера Squid, показала эффективность применения адаптивного нечеткого online алгоритма кэширования, который в отличие от известных стратегий замещения использует свойство пространственной локальности для определения кэш-рейтинга web-pecypcoB, в среднем на 8% большую, чем для известных стратегий замещения.

В заключение главы приведены результаты внедрении разработанных алгоритмов и методов в информационную систему поддержки образовательного процесса Донского государственного технического университета, что позволило сократить время отклика системы на запросы конечных пользователей в среднем более чем в 3 раза.

ЗАКЛЮЧЕНИЕ

1. Выполненный анализ известных стратегий замещения впервые позволил разработать два варианта их классификации по используемым характеристикам объектов в потоке запросов и по структуре и принципам их функционирования, что позволило обосновать возможные направления в получении новых гибридов, а также необходимость применения методов адаптации кэш-систем с целью повышения их быстродействия.

2. Разработанная математическая модель абстрактной одноуровневой системы кэширования позволила реализовать метод векторного управления стохастической гибридизацией любого числа базовых стратегий замещения, а также формализовать алгоритмы, использующие для определения кэш-рейтинга объектов их размер (в байтах), что создало теоретическую возможность синтеза новых эффективных гибридов, позволяющих увеличить быстродействие информационных систем.

3. Предложенный метод адаптации модели управляемой гибридизации стратегий замещения, на базе комбинирования разнородных алгоритмов кэширования с использованием методов краткосрочного прогнозирования позволяет повысить скорость адаптации к изменению потока запросов и, следовательно, сократить время отклика кэш-системы.

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

5. С помощью разработанного программного стенда экспериментально подтверждена эффективность предложенных моделей кэш-систем. Проведенные исследования позволили синтезировать новые алгоритмы кэширования, использующие адаптивную систему управления. Эффективность разработанных алгоритмов подтверждается как проведенными статистическими испытаниями на стенде, так и реальным внедрением. Данный программный стенд может быть использован в качестве инструментального средства для исследования и синтеза систем кэширования.

Таким образом, поставленная в диссертации цель достигнута.

1. Abrams, M. Caching Proxies: Limitations and Potentials / M. Abrams et al // WWW-4, Boston Conference. 1995

2. Aguilar, J. A Web Proxy Cache Coherency and Replacement Approach / Jose Aguilar and Ernst Leiss // N. Zhong et al. (Eds.). 2001. - с. 75-84.

3. Aho, A.V. Principles of optimal page replacement / Aho A.V., Denning P.J., and Ulman J.D. // Journal of the ACM. 1971, vol. - 18. - no. 1.

4. Allspaw, J. Web Operations: Keeping the Data on Time / John Allspaw, Jesse Robbins // O'Reilly Media, Inc. 2010.

5. Almasi, G. Calculating Stack Distances Efficiently / George Almasi et al // Memory System Perfomance. ACM New York. - 2002.

6. Alternative PHP Cache // Электронный ресурс.: http://www.php.net/apc

7. Arlitt, M.F. Performance Evaluation of Web Proxy Cache Replacement Policies / Martin Arlitt, Rich Friedrich, Tai Jin // Internet Systems and Applications Laboratory. October, 1999.

8. Arlitt, M.F. Evaluating Content Management Techniques for Web Proxy Caches / M. F. Arlitt et al. // ACM S1GMETRICS Performance Evaluation Review. -2000. Vol. 27. - Num. 4.

9. Austin, T. SimpleScalar Tutorial v4 / T. Austin et al // University of Michigan. 2000.

10. Belady, L.A. An Anomaly in space-Time Characteristics of Certain Programs Running in a Paging Machine / Belady, L.A., Nelson, R.A., and Shedler, G.S. // Commun Of the ACM. 1969.-vol.12.

11. Borodin, A. Online Computation and Competitive Analysis / A. Borodin, R. El-Yaniv // Cambridge University Press. 1998.

12. Brehob, M. An Analytical Model of Locality and Caching / M. Brehob and R. Enbody // Michigan State University. 1999.

13. Calzarossa, M.C. A Fuzzy Algorithm for Web Caching / Maria Carla Cal-zarossa, Giacomo Valli // Электронный ресурс.: http://peg.unipv.it/publications/ PDF/Proxy.pdf.

14. Cao, P. Cost-Aware WWW Proxy Caching Algorithms / P. Cao, S. Irani // In Proceedings of the USENIX Symposium on Internet Technology and Systems. 1997.

15. Castro, M. НАС: Hybrid Adaptive Caching for Distributed Storage Systems / Miguel Castro, Atul Adya, Barbara Liskov, and Andrew C. Myers // Proceedings of the 16th ACM Symposium on Operating Systems Principles. Saint-Malo, France. - 1997

16. Chankhunthod, A. A Hierarchical Internet Object Cache / A. Chankhunthod at et // Электронный ресурс.: http://netweb.usc.edu/danzig/cache/cache.html

17. Che, H. Hierarchical Web Caching Systems: Modeling, Design and Experimental Results / Hao Che, et al. // IEEE Journal on selected areas in communications. September 2002. - vol. 20. - no. 7.

18. Cherkasova, L. Improving WWW Proxies Performance with Greedy-Dual-Size-Frequency Caching Policy // In HP Technical Report HPL-98-69(R.l). 1998.

19. Cho S. Coherence and Replacement Protocol of DICE-A Bus Based COMA Multiprocessor / Cho S., King J., Lee G // Journal of Parallel and Distributed Computing. 1999. - Vol. 57. - c. 14-32.

20. Chou H.-T. An Evaluation of Buffer Management Strategies for Relational Database Systems / Hong-Tai Chou and David J. Dewitt // Proceedings of VLDB 85, Stockholm. 1985

21. Danzig, P.B. A Case for Caching File Objects Inside Internetworks / Peter B. Danzig, Richard S. Hall, Michael F. Schwartz // ACM SIGCOMM Computer Communication Review. Volume 23. - Issue 4. - 1993.

22. De Maesschalck, R. The Mahalanobis distance / De Maesschalck, R.; D. Jouan-Rimbaud, D.L. Massart // Chemometrics and Intelligent Laboratory Systems. -2000.

23. Denning, P.J. Working sets past and present // IEEE Trans. Software Engineering. 1980. - vol. SE-6.

24. Denning, P.J. Properties of the Working-Set Model / P. Denning and S. Schwartz // Communications of the ACM. 1972.

25. Denning, P.J. The locality principle // Communication of the ACM 48. 7. -2005

26. Emer, J. Asim: A performance model framework / J. Emer et al // IEEE Computer. 2002.

27. Feldman, J. Computer Architecture, A Designer's Text Based on a Generic RISC Architecture, 1st ed. // New York: McGraw-Hill. 1994.

28. Fernandez, E.B. Effect of Replacement Algorithms on a Page Buffer Database System / E.B. Fernandez, T. Lang, C. Wood // IBM Journal of Research and Development. 1978.

29. Handy, J. The Cache Memory Book, The 2nd Edition / Jim Handy // Morgan Kaufmann. 1998.

30. Harizopoulos S. Hierarchical Caching and Prefetching for Improving the Performance of Continuous Media Servers / Stavros Harizopoulos // Department of Electronic and Computer Engineering. 1998.

31. Hassan, R. A Hybrid Markov Model for Accurate Memory Reference Generation / Hassan R. et. al. // IAENG Int. Conf. on Computer Science (ICCS'07). Hong Kong, 2007.

32. Holowaychuk, T.J. Drupal 6 Performance Tips / T.J. Holowaychuk, Trevor James // Packt Publishing. 2010.

33. Hypertext Transfer Protocol ~ HTTP/1.1 // Электронный ресурс.: http://www.w3.org/Protocols/rfc2616/rfc2616-sec 14.html#sec 14.9.

34. Introduction to XCache // Электронный ресурс.: http://xcache.lighttpd.net/ wiki/Introduc tion/

35. Jayarekha, P. An Adaptive Dynamic Replacement Approach for a Multicast based Popularity Aware Prefix Cache Memory System / P. Jayarekha, T.R.Gopalakrishnan Nair // InterJRI Computer Science and Networking. December, 2009.-Vol. 1.- Issue 1.

36. Jelenkovic, P. R. Optimizing the LRU algorithm for Web caching / Jelenkovic P. R., Radovanovic A // 18th. International Teletraffic Congress. Berlin, Germany. -2003.

37. Latha Shanmuga Vadivu, S. Optimization of Web Caching and Response Time in Semantic based Multiple Web Search Engine / S. Latha Shanmuga Vadivu, M. Ra-jaram. // European Journal of Scientific Research. 2011. - Vol.56. - No.2. - c. 244255.

38. Lee, D. On the Existence of a Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies / Lee D. et al // Performance Evaluation Review. 1999. - Vol. 27

39. Lee, D. Implementation and Performance Evaluation of the LRFU Replacement Policy / Donghee Lee et. al. // Dep. Of Computer Engineering, Seoul National University. 1996.

40. Lorenzetti, P. Replacement Policies for a Proxy Cache / P. Lorenzetti, L. Rizzo and L. Vicisano // Электронный ресурс.: http://www.iet.unipi.it/luigi/ research.html.

41. Karedla, R. Cache Strategies to Improve Disk System Performance / R. Karedla et al // IEEE Computer Magazine. March, 1994. - c. 38-46.

42. Kelly, T. Optimal Web cache sizing: scalable methods for exact solutions / Kelly Т., Reeves D. // Elsevier Science B.V. Computer Communications 24. 2001.

43. Kharbutli, M. Counter-based cache replacement algorithms / M. Kharbutli, Y. Solihin // IEEE International Conference on Computer Design. 2005

44. Korupolu, M.R. Coordinated placement and replacement for large-scale distributed caches / M. R. Korupolu and M. Dahlin // Proc. IEEE Workshop on Internet Applications. June, 1999. - c. 62-71.

45. Mattson, R.L. Evaluation techniques for storage hierarchies / R. L. Mattson et al // IBM Journal of Research and Development. 1970. - vol. 9. - no.2.

46. Megiddo, N. ARC: A Self-Tuning, Low Overhead Replacement Cache / Nim-rod Megiddo and Dharmendra S. Modha // 2nd USENIX Conference on File and Storage Technologies. San Francisco, 2003.

47. Megiddo, N. Outperforming LRU with an Adaptive Replacement Cache Algorithm / Nimrod Megiddo, Dharmendra S. Modha // IEEE Computer Society. 2004. Vol. 37. - Issue 4.

48. O'Neil, E.J. An optimality proof of the LRU-K page replacement algorithm / O'Neil E.J., O'Neil P.E., Weikum G. //Journal of the ACM. 1999. - Vol. 46. -No.l.

49. O'Neil, E.J. The LRU-K Page Replacement Algorithm For Database Disk Buffering / O'Neil E.J., O'Neil P.E., Weikum G. // Proceedings of the 1993 ACM SIG-MOD International Conference on Management of Data. Washington, D.C., 1993.

50. Oslake, M. Capacity model for Internet transactions / Technical Report MSR-TR-99-18. Microsoft Research. - 1999.

51. Pandurangan, G. A Universal Online Caching Algorithm Based on Pattern Matching / Gopal Pandurangan, Wojciech Szpankowski // Algorithmica. 2010 - Vol. 57. - Number 1.

52. Patil, J.B. Improving Performance on WWW using Intelligent Predictive Caching for Web Proxy Servers / J. B. Patil and B. V. Pawar // International Journal of Computer Science Issues. 2011. - Vol. 8. - Issue 1.

53. Patil, J.B. Integrating Intelligent Predictive Caching and Static Prefetching in Web Proxy Servers / J.B. Patil, B.V. Pawar. // International Journal on Computer Science and Engineering. 2011. - Vol. 3. - No. 2.

54. Paul, S. Distributed caching with centralized control / S. Paul, Z. Fei // Computer Communications 24. 2001. - no.2.

55. PhpExpress Manual // Электронный ресурс.: http://www.nusphere.com/kb/ phpexpressmanual/

56. Pierre, G. Dynamically Selecting Optimal Distribution Strategies for Web Documents / G. Pierre, M. van Steen, and A.S. Tanenbaum // IEEE Transactions on Computers 51. no. 6. - 2002.

57. Pirtle, M. Extreme Joomla! Performance // Addison-Wesley Educational Publishers Inc. 2010.

58. RealView ARMulator ISS // ARM Ltd. 2004.

59. Sabeghi, M. Using Fuzzy Logic to Improve Cache Replacement Decisions / Mojtaba Sabeghi, and Mohammad Hossein Yaghmaee // IJCSNS International Journal of Computer Science and Network Security. 2006. - Volume 6. - No.3.

60. Smaragdakis, Y. EELRU: Simple and Effective Adaptive Page Replacement / Yannis Smaragdakis et al // ACM SIGMETRICS Performance Evaluation Review. -1999. Volume 27. - Issue 1.

61. Sokolinsky, L.B. LFU-K: An Effective Buffer Management Replacement Algorithm // Proceedings. Lecture Notes in Computer Science. Vol. 2973. - New York: Springer. - 2004. - c. 670-681.

62. Spirn, J. Program Behavior: Models and Measurements // Elsevier. 1977.

63. Stierhoff, G.C. A History of the IBM Systems Journal / G. C. Stierhoff, A. G. Davis // IEEE Annals of the History of Computing. 1998. - T. 20. - № 1

64. Thiebaut, D. Synthetic Traces for Trace-Driven Simulation of Cache Memories / D. Thiebaut, J. L. Wolf, and H. S. Stone // IEEE Transactions on Computers. 1992.

65. Tse, P.K.C. Multimedia information storage and retrieval: techniques and technologies / Philip K.C. Tse. // New York: IGI Publishing. 2008.

66. Wang K. Anomalous Payload-based Network Intrusion Detection / Ke Wang, Salvatore J. Stolfo // Computer Science Department. New York, 2004.

67. Williams, S. Removal Policies in Network Caches for World-Wide Web Documents / Williams S. et al. // In Proceedings of the ACM Sigcomm96. Stanford University, 1996.

68. Wood, C. Minimization of Demand Paging for LRU Stack Model of Program Behavior / C. Wood, E.B. Fernandez, T. Lang // Information Processing Letters. 1983.

69. Wooster, R.P. Proxy Caching that Estimates Page Load Delays / R. P. Wooster and M. Abrams // Электронный ресурс.: http://vtopus.cs.vt.edu/~chitra/docs/ 96trNEW/

70. Yang, Q. Web-Log Mining for Predictive Web Caching. / Q. Yang, and H.H. Zhang // IEEE Transactions on Knowledge and Data Engineering. 2003. - Volume 15. - Number 4.

71. Zipf, G.K. Human Behavior and the Principle of Least Effort: an Introduction to Human Ecology // Cambridge, Mass.: Addison-Wesley, 1949. 573 p.

72. Аль-Згуль Мосаб, Б.Ю. Гибридные алгоритмы в системах кэширования объектов / Б.Ю. Аль-Згуль Мосаб // Вестник Донского гос. тех-го ун-та. 2008. -№4.-С. 403—411.

73. Аль-Згуль Мосаб, Б.Ю. Гибридные алгоритмы кэширования для систем обработки и хранения информации: дис. . канд. техн. наук / Б.Ю. Аль-Згуль Мосаб. Ростов н/Д, 2009. - 150 с.

74. Аль-Згуль Мосаб, Б.Ю. Применение алгоритма адаптивного кэширования в объектно-ориентированных базах данных / Б.Ю. Аль-Згуль Мосаб // 1-й межвузовский сборник научных статей ДГТУ-ТТИ ЮФУ. 2009.

75. Бендат, Дж. Измерение и анализ случайных процессов / Дж. Бендат, А. Пирсол // М.: Издательство «Мир». 1974.

76. Болотов П. Принципы работы кэш-памяти / Павел Болотов // Электронный ресурс.: http://alasir.com/articles/cacheprinciples/cachehierarchy rus.html.

77. Вентцель, Е.С. Теория вероятностей, 4-е изд. М.:Наука. - 1969.

78. Воронов, A.A. Современное состояние и перспективы развития адаптивных систем / Воронов A.A., Рутковский В.Ю. // Вопросы кибернетики. Проблемы теории и практики адаптивного управления. М.: Научный совет по кибернетике АН СССР, 1985.-С.5-48

79. Гмурман, В.Е. Теория вероятностей и математическая статистика: Учеб. пособие для вузов М.: Высш. шк., 2002. - 479 с.

80. Грановский, В. А. Методы обработка экспериментальных данных при измерениях / Грановский В. А., Сирая Т. Н. // Л.: Энергоатомиздат. 1990.

81. Жуков, А.И. Гибридный подход к решению проблемы миграции объектов информационных систем / Жуков А.И., Слоновский A.B., Кириенко М.Е. // Математические методы в технике и технологиях ММТТ-23. том 12. - Смоленск, 2010.

82. Жуков, А.И. Методика тестирования результатов вертикальной кластеризации отношений / А.И. Жуков, М.В. Гранков // Вестник Донского гос. тех-го унта. 2011,- №8. -С. 1344-1347.

83. Жуков А.И. Модель адаптивного векторного управления стохастическим гибридным алгоритмом кэширования / А.И. Жуков // Вестник Донского гос. тех-го ун-та. 2012. - №5.

84. Жуков А.И. Адаптивный нечеткий алгоритм кэширования для прокси-серверов / А.И. Жуков // Вестник Донского гос. тех-го ун-та. 2012. - №8.

85. Жуков, А.И. Математическая модель метода бигибридизации алгоритмов кэширования / А.И. Жуков, Б.Ю. Аль Згуль Мосаб // В мире научных открытий. -2010.-Часть 13.-№4(10). С. 130-132.

86. Жуков, А.И. Использование информационных систем и технологий в целях удовлетворения информационных потребностей / А.И. Жуков, А.Г. Сорокин. Красноярск: Научно-инновационный центр, 2012. - С. 5-39.

87. Жуков, А.И. Применение меры Махаланобиса в гибридных алгоритмах кэширования / Жуков А.И., Гранков М.В. // Математические методы в технике и технологиях ММТТ22. - Т. 11. - Иваново, 2009.

88. Жуков, А.И. Программный стенд для исследования эффективности алгоритмов кэширования // Системный анализ, управление и обработка информации: Труды 1-го Международного семинара студентов, аспирантов и ученых Ростов н/Д: ИЦ ДГТУ, 2010.

89. Жуков А.И. Методика экспериментального исследования эффективности систем кэширования информации / А.И. Жуков, М.В. Гранков // Труды 2-го международного семинара под общ. ред. P.A. Недорфа Ростов н/Д, изд. центр Доснк. гос. техн. ун-та. - 2011.

90. Жуков, А.И. Система кэширования программно-алгоритмического каркаса Codelgniter / А.И. Жуков, A.B. Штапов // Труды 3-го международного семинара под общ. ред. P.A. Недорфа Ростов н/Д, изд. центр Доснк. гос. техн. ун-та. -2012.

91. Зервас, К. Web 2.0. Создание приложений на PHP / Квентин Зервас // М.:Вильямс. -2009.

92. Кендалл, С. UML Основные концепции: Пер. с англ. М.: Издательский дом "Вильяме". - 2002. - 144 с.

93. Колмогоров, А.Н. Элементы теории функций и функционального анализа / Колмогоров А.Н., Фомин C.B. // М.: Главная редакция физико-математической литературы изд-ва «Наука». 1976. С. 544.

94. Красовский, Г.И. Планирование эксперимента / Красовский Г.И., Филаретов Г.Ф. // Минск: изд-во БГУ. 1982. - 302 с.

95. Лукашин, Ю.П. Адаптивные методы поиска краткосрочного прогнозирования временных рядов: Учеб. пособие. М.Финансы и статистика. - 2003. -416 с.

96. Лю, Б. Теория и практика неопределенного программирования. // М:БИНОМ, Лаборатория знаний. 2005.

97. Методы робастного, нейро-нечеткого и адаптивного управления: Учебник / Под ред. Н.Д. Егупова; издание 2-ое, стереотипное. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 744 с.

98. Нго, Т.Х. Метод вертикальной кластеризации для реляционных систем хранения и обработки информации: дис. . канд. техн. наук / Нго Тхань Хунг. -Ростов н/Д, 2008.

99. Певзнер, Л.Д. Математические основы теории систем / Певзнер Л.Д., Чу-раков Е.П. // М.: Высш. шк. 2009. - 503 с.

100. Розанов, Ю.А. Случайные процессы (краткий курс). Главная редакция физико-математической литературы изд-ва «Наука», 1971.

101. Рутковский, Л. Методы и технологии искусственного интеллекта. / Лешек Рутковский // Пер. с польского И.Д. Рудинского. М.: Горячая линия - Телеком, 2010.-520 с.

102. Сахаров, И.Е. Упреждающее кэширование в подсистеме внешней памяти высокопроизводительных распределенных вычислительных систем: автореферат дис. . канд. техн. наук // Иваново, 2009.

103. Соколинский, Л.Б. Стратегия замещения или как освободить место в буфере // проект 00-07-90077 поддержки Российского фонда фундаментальных исследований. 2002.

104. Соколинский, Л.Б. Методы организации параллельных систем баз данных на вычислительных системах с массовым параллелизмом: дис. . д-р. техн. наук / Соколинский Лев Борисович. Челябинск, 2003.

105. Солтер, H.A. С++ для профессионалов / Николас А. Солтер, Скотт Дж. Клеппер // Пер. с англ. М.:000 «И.Д. Вильяме». - 2006. - 912с.

106. Таненбаум, Э. Современные Операционные Системы, 2-е изд. / Эндрю Таненбаум. СПб: Питер. - 2002.

107. Шлее, М. Qt4. Профессиональное программирование на С++. СПб.: БХВ-Петербург. - 2007. - 880с.

108. Штовба, С.Д. Введение в теорию нечетких множеств и нечеткую логику. Винница: Континент-Прим. - 2003. - 198 с.