Кафедра Информационных Систем и Технологий. Сдана на проверку Допустить к защите 2007 г. 2008 г. Защищена с оценкой 2008 г курсовая

Вид материала

Курсовая

Содержание 7.Как выполняется кэширование? 7.1.Замещение содержимого кэша и запись ответа в кэш Самый старый из используемых (LRU-Least Recently Used). Самый редко используемый (LFU-Least Frequently Used). Размер объекта (SIZE). Hyper-G (LFU/LRU/SIZE). Алгоритмы, основанные на полезности (GreedyDual-Size).

Подобный материал:

• Калининградский Государственный Технический университет Экономический факультет Кафедра, 305.66kb.
• Курсовая работа защищена с оценкой, 18.89kb.
• Конференция «Безопасность информационных систем предприятия», 59.58kb.
• Московская финансово-юридическая академия «Согласовано» «Утверждено на 2007 / 2008, 21.72kb.
• О защите конкуренции, 1152.72kb.
• Институт информационных технологий Кафедра информационных и коммуникационных технологий., 195.33kb.
• Институт информационных технологий Кафедра информационных и коммуникационных технологий, 207.89kb.
• Уголовный кодекс российской федерации, 3723.74kb.
• Титульный лист программы обучения по дисциплине Syllabus, 456.17kb.
• Принят Государственной Думой 8 декабря 1995 года     Глава I. Общие положения   статья, 545.05kb.

^

7.Как выполняется кэширование?

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

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

После того как освобождается место для записи ответа, кэш извлекает информацию о сообщении, включая дату последнего обновления и информацию об устаревании. Обрабатываются следующие заголовки сообщений: Expire и Cache-Control: max-stale, несущие информацию об актуальности ресурса. Эти поля заголовков помогают кэшу выполнять ограничения HTTP по периоду времени, в течение которого может быть возвращен семантически корректный ответ. Кэш, поддерживающий протокол, обязан гарантировать, что любой возвращенный им ответ, рассматривался бы исходным сервером как актуальный. При отсутствии специфической информации об актуальности ресурса кэш использует эвристически полученное время истечения срока актуальности. Значение этого времени может быть получено, основываясь на времени последнего обновления ресурса (значения поля заголовка Last-Modified). Например, сервер может добавить фиксированный промежуток времени, скажем, 10 минут к значению Last-Modified и использовать его как время обновления ресурса. И, наконец, создается ключ ресурса, используемый при последующих поисках этого ресурса. Ключ создается с помощью хэш-функции на основе на URL запроса. Когда кэш получает новый запрос, то он использует URL для поиска ресурса в кэше.
^

7.1.Замещение содержимого кэша и запись ответа в кэш

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

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

• Стоимость извлечения ресурса. Стоимость извлечения ресурса с исходного сервера определяется возможностями кэша в организации взаимодействия с сервером и расстоянием, которое должен пройти ресурс до того, как достиг­нет кэша. Цена замещения ресурса, требующего больших затрат по извлече­нию, должна быть оправдана тем, что ресурс потребуется в будущем.
  
• Стоимость хранения ресурса. Кэш использует фиксированный объем диско­вой памяти, сохранение одного объекта требует уменьшения объема памяти для других. Большой ресурс занимает больше пространства, однако повторное его извлечение с исходного сервера будет также дорогостоящим.
  
• Число обращений к ресурсу. Объект, к которому многократно обращались в прошлом, будет, вероятно, запрошен снова и является достойным кандида­том на кэширование в течение длительного срока.
  
• Вероятность того, что ресурс будет запрошен в ближайшее время. Если та­кая вероятность высокая, то нет смысла удалять ресурс из кэша. Вероятность доступа к ресурсу может быть рассчитана заранее или оценена на основе под­ходящих образцов.
  
• Время последней модификации ресурса. Ресурс, который не менялся в тече­ние длительного времени, скорее всего, не изменится и в ближайшем буду­щем. Ресурс, созданный совсем недавно, может оказаться или динамически создаваемым ресурсом, или он снова изменится в ближайшем будущем. Ре­сурсы, которые чаще изменяются, как правило, оказываются более популяр­ными, поскольку они меняются именно в результате своей популярности и, следовательно, являются хорошими кандидатами на кэширование. Однако кэшируемый ответ должен в этом случае заменяться достаточно часто (с часто­той его изменения на исходном сервере). Время последней модификации, та­ким образом, может использоваться для принятия решения о том, какие ре­сурсы можно замещать.
  
• Эвристическая оценка времени истечения срока годности ресурса. Если вре­мя истечения срока годности ресурса не указано сервером, то кэш должен найти эвристическую оценку этого времени. Если отсутствуют ресурсы с истекшим сроком годности, то наиболее вероятным ресурсом на замещение является тот, у которого осталось наименьшее время до истечения его срока годности.
  

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

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

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

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

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

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

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

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

• Устойчивое снижение цен на устройства хранения данных, привело к появле­нию кэшей, имеющих объем памяти достаточный для храпения большинства запрашиваемых ресурсов.
  
• Общее сокращение доли кэшируемого трафика.
  
• Разработка алгоритмов, которые могут использоваться в большинстве ситуа­ций замещения кэшируемых объектов. Алгоритмы типа GreedyDual-Size и Hyper-G относятся к этой категории.
  
• Изменение ресурсов во времени сокращает время храпения ресурсов в кэшах.