Замещение объектов в кэше

После того как кэш заполняется, необходимо выполнить удаление некоторых объектов для кэширования новых ответов. В течение последних лет было исследовано несколько подходов к замещению объектов в кэше. Некоторые из них заимствованы из традиционных подходов к кэшированию в файловых системах, а некоторые специально предложены для Web-кэширования. Одним из хорошо известных подходов является алгоритм LRU (Least Recent Use) — замена объектов, запрошенных наиболее давно. Статьи на полках, которые давно не использовались, больше покрыты иылыо, чем те, которыми пользовались недавно. Чем больше времени прошло с момента последнего обращения, гем больше пыли. Задачи кэширования, такие, как уменьшение объема данных, пересылаемых но сети, и сокращение времени ожидания ответа, приводят к необходимости комплексного решения задачи замещения объектов в кэше. Комплексный подход состоит в использовании комбинации метрик, включая размер кэшировапного ответа, гип его содержания и информация о расстоянии до исходного сервера.

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

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

•          Стоимость хранения ресурса. Кэш использует фиксированный объем дисковой памяти, сохранение одного объекта требует уменьшения объема памяти для других. Большой ресурс запимает больше пространства, однако повторное его извлечение с исходного сервера будет также дорогостоящим.

•          Число обращений к ресурсу. Объект, к которому многократно обращались в прошлом, будет, вероятно, запрошен снова и является достойным кандидатом на кэширование в течение длительного срока.

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

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

•          Эвристическая оценка времени истечения срока годности ресурса. Если время истечения срока годности ресурса не указано сервером, то кэш должен найти эвристическую оценку этого времени. Если отсутствуют ресурсы с истекшим сроком годности, то наиболее вероятным ресурсом на замещение является тог, у которого осталось наименьшее время до истечения его срока годности.

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

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

Самый старый из используемых (LRU—Least Recently Used). Является одним из наиболее протестированных алгоритмов. Этот алгоритм просто удаляет из кэша самый старый объект (с точки зрения времени его последнего использования). Идея подхода весьма прямолинейна — объект, который запрашивался недавно, скорее всего, будет запрошен снова в ближайшее время, и необходимо заместить более старые объекты до удалепия любого из более новых ресурсов. Ряд исследований [AW97, ASA+95, WAS+96, CI97] ноказали, что этот алгоритм не является лучшим для максимизации доли наиболее часто используемых объектов. Среди причин можно указать отсутствие временной локализации в ссылках на документы и то, что многие объекты запрашиваются только однократно.

Самый редко используемый (LFU — Least Frequently Used). Эгот алгоритм ранжирует документы по частоте доступа к пим и удаляет документы, которые имеют самую маленькую частоту. Стратегии, основанные на частотах использования кэшированных ресурсов, были рассмотрены в работах [WAS+96, SSV97J.

Размер объекта (SIZE). Другим критерием для выбора объекта, подлежащего замещению, является его размер. Удаляя из кэша объект самого большого размера, можно освободить место для нескольких объектов меньшего размера.

Hyper-G (LFU/LRU/SIZE). Алгоритм Hyper-G объединяет три предыдущие стратегии. Первыми кандидатами на замещение в этом алгоритме являются наименее часто используемые объекты (LFU). Если имеется несколько ресурсов, удовлетворяющих этому критерию, то удаляется самый старый из них (LRU). Если предыдущие операции все еще не определяют единственного ресурса, то удаляется тот из них, который имеет самый большой размер (SIZE).

Алгоритмы, основанные на полезности (GreedyDual-Size). Этот алгоритм был предложен в контексте замещения страниц в памяти компьютера [You94]. Все рассматриваемые страницы должпы быть одного размера, а стоимость извлечения страницы из вторичного источника храпения должна быть составной частью ключа. Позднее алгоритм был модифицирован для анализа Web-pecypcoB различных размеров [CI97]. Модифицированный алгоритм определяет зпачепие параметра, называемого полезностью, и замещает ресурс, имеющий наименьшее зпачепие полезности. Отталкиваясь от стоимости загрузки ресурса в кэш и его размера, полезность принимает во внимание также временной фактор, значение которого обновляется каждый раз, когда ресурс удаляется из кэша.

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

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

•          Общее сокращение доли кэшируемого трафика.

•          Разработка алгоритмов, которые могут использоваться в большинстве ситуаций замещения кэшируемых объектов. Алгоритмы типа Greedy Dual-Size и Hyper-G относятся к этой категории.

•          Изменение ресурсов во времени сокращает время храпения ресурсов в кэшах.

Источник: Web-протоколы. Теория и практика. — M.: ЗАО «Издательство БИНОМ», 2002 г. – 592 c.: ил.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100