Система управления кэшированием объектов
Самостоятельное кэширование данных – неотъемлемая черта любой СУБД. Кэш состоит из двух частей: очереди кэшируемых объектов и памяти для кэшируемых объектов. Память для кэшируемых объектов – это оперативная память, в которую объект загружается. В этой памяти могут располагаться только те объекты, идентификаторы которых находятся в очереди кэшируемых объектов. Удаляемый из очереди объект выгружается в дисковую память. В данной дипломной работе все создаваемые объекты являются стабильными (Persistent), т.е. они обязательно сохраняются на диске и могут быть использованы после открытия базы данных для использования.
Задача управления кэшированием объектов подобна задаче управления памятью в операционной системе. В операционной системе для организации процесса обмена между оперативной и внешней памятью информация представлена набором сегментов (блоки переменной длины) или страниц (блоки фиксированной длины). Способ управления памятью называется алгоритмом замещения, который определяет состав сегментов или страниц в более быстродействующей основной памяти. Таким образом, частота обращений к внешней памяти, а, следовательно, и быстродействие двухуровневой памяти (уровень внешней памяти и уровень оперативной памяти) в целом, существенно зависят от выбранного алгоритма замещения. Наибольшее распространение получила страничная структура памяти.
В дипломной работе роль страницы играет объект. Минимальную частоту обращений к ВП (внешней памяти) давал бы алгоритм, замещающий те объекты в ОП (оперативной памяти), обращение к которым в будущем произойдет через максимально долгое время. Однако реализовать такой алгоритм невозможно, поскольку заранее неизвестна информация о будущих обращениях к объектам программой.
Наиболее популярны следующие пять алгоритмов замещения:
1. Случайное замещение (СЗ): с равной вероятностью может быть замещен любой объект,
2. Раньше пришел – раньше ушел (РПРУ, или FIFO): замещается объект дольше всех находившийся в оперативной памяти,
3. Замещение наиболее давно использовавшегося объекта (НДИ),
4. Алгоритм рабочего комплекта (РК): хранятся в памяти только те объекты, к которым было обращение в течении времени t, назад от текущего момента,
5. Лестничный алгоритм (ЛЕСТН): в списке объектов при обращении к объекту он меняется местами с объектом, находящемся ближе к голове списка. При обращении к отсутствующему в ОП объекту объект, находящийся в последней позиции вытесняется.
Для алгоритма замещения желательно, чтобы он обладал двумя отчасти противоречивыми свойствами: с одной стороны, он должен сохранять в ОП объекты к которым обращения происходят наиболее часто, с другой – быстро обновлять содержимое ОП при смене множества рабочих объектов.
Например, алгоритм РПРУ эффективен только в отношении быстрого обновления ОП, он не выделяет в списке объектов объекты, обращения к которым происходят чаще, чем к остальным. Алгоритм НДИ также позволяет быстро обновлять содержимое ОП. Однако последовательность одиночных обращений достаточной длины к объектам, находящимся во ВП, вытеснит из ОП все объекты, к которым, в среднем, обращения происходят чаще всего.
В [1] описывается класс многоуровневых алгоритмов замещения c, которые позволяют решить эту проблему. Они зависят от конечного числа параметров и при адаптивном подборе этих параметров соединяют свойство быстрого обновления части ОП со свойством сохранения в ОП тех объектов, которые наиболее часто запрашиваются.
В дипломной работе решено использовать алгоритм замещения из класса c, при следующих параметрах: лимит времени нахождения объекта в ОП отсутствует, размеры подсписков на всех уровнях одинаковы, параметр l=1 (это соответствует алгоритму замещения НДИ для объектов всех подсписков; если i – положение объекта в подсписке, и i £ l, то при обращении к нему применяется алгоритм РПРУ, иначе НДИ).
Неэффективным является подход простого освобождения от объектов, которые стоят в конце списка кэша, поскольку они могут быть малы по размеру, а требуется загрузить объект, который занимает значительное количество памяти.
В этом случае, пришлось бы ради одного объекта выгружать значительное количество других. Что привело бы к значительным потерям времени при их повторной загрузке.
Для определения подмножества объектов кэша, подлежащих вытеснению, можно применить алгоритм решения задачи о рюкзаке. Если бы все объекты имели одинаковую длину, без этого можно было бы обойтись. Хотя алгоритм решения задачи о рюкзаке NP-сложен, решение можно компактно записать в виде рекурсивного алгоритма, находящего решение за счет применения принципа динамического программирования Беллмана. Такой способ наиболее эффективен, когда размер кэша составляет 32 объекта, поскольку множество выбранных объектов можно представить битовыми полями в длинном слове. При большем размере кэша возрастают потери памяти и быстродействия, и возникает вопрос о месте расположения данных промежуточных вызовов. Рекурсивный вызов в среде ДССП требует малых затрат ресурсов, а время расчета окупается за счет времени обмена с внешней памятью, работа с которой много медленнее, чем с оперативной.
