Кришнамурти Б., Рексфорд Дж. Web-протоколы. Теория и практика

Подождите немного. Документ загружается.

390 Часть V. Web-приложения

Эти факторы задержки прослеживаются от передачи запроса браузером серверу

до воспроизведения им полученного ответа. Рассмотрим влияние кэширования на

каждый из перечисленных факторов задержки.

Сетевое соединение. Задержка передачи данных между клиентом и провайде-

ром меняется существегню меньше, чем задержка в Internet. Если содержание рас-

положено достаточно близко к провайдеру, то тогда можно достаточно точно пред-

сказать время ожидания ответа. Если скорость соединения провайдера с Internet

высокая, то ответ будет доставляться до провайдера достаточно быстро. Однако

если скорость соединения небольшая, то время передачи ответа в сеть провайдера

может составлять основную часть общего времени ожидания ответа. Кроме того,

если соединение между провайдером и исходным сервером невозможно в момент

запроса, то кэш провайдера может вернуть ответ. Ответ может оказаться устарев-

шим, однако в некоторых случаях это может быть не так важно. В ряде случаев от-

веты исходных серверов персонализированы и поэтому отсутствуют в кэше.

Задержка, связанная с DNS. Увеличение времени жизни (TTL) таблиц соответ-

ствий между доменными именами и IP-адресами в DNS также может сократить об-

щее время ожидания ответа, поскольку соответствие между доменным именем и

IP-адресом меняется не слишком часто. Как это будет обсуждаться в разделе

11.13,

некоторые схемы кэширования могут не только располагать ХУеЬ-содержание ближе

к пользователю, но и уменьшать время поиска соответствия между доме1Н1ым име-

нем и IP-адресом. Расположение Web-содержания ближе к пользователю означает

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

рующий прокси-сервер может хранить список часто используемых доменов и тем са-

мым сокращать задержки, связанные с DNS-операциями.

Сетевая нагрузка и производительность сети. Сокращение числа промежуточ-

ных передач пакетов может увеличить пропускную способность между клиентом и

сервером, на котором размещено Web-содержание. Поскольку TCP является ос-

новным протоколом транспортного уровня для HTTP, то сокращение времени про-

хождения пакетов от клиента к серверу и назад (RTT) повышает производитель-

ность. Производительность TCP обратно пропорциональна RTT. Уменьшение чис-

ла промежуточных передач приводит также к уменьшению вероятности задержек

в промежуточных точках из-за перегрузок. Как было отмечено в главе 5 (раз-

дел 5.2.6), большое число пакетов в сети может вызвать перегрузку сети, приводя-

щую к утере пакетов. Утерянные пакеты должны быть переданы повторно. Если

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

могут быть нереданы быстрее. Отправитель ТСР-пакетов для более полного ис-

пользования сети может увеличить размер скользящего окна.

Нагрузка на исходный сервер. Исходный сервер может также выиграть от кэ-

ширования. Если будут кэшироваться наиболее популярные ответы, то нагрузка

сервера сократится, поскольку существегню уменьшится количество запросов, дос-

тигающих этого сервера. Сервер сможет обработать большее количество запросов

пользователей без постановки в очередь соединений транспортного уровня, без за-

держек в обработке HTTP-запросов. Исходный сервер переносит задачу обработки

запросов на вспомогательные кэширующие прокси-серверы. Исходный сервер мо-

жет также поддерживать долговременные соединения с меньшим числом клиентов,

и эти соединения дольше могут оставаться открытыми. Время на генерацию из-

лишних ответов сокращается, оставляя больше времени на выполнение сервером

других задач.

Глава 11. Кэширование 391

Время генерации ответа. Время генерации ответа на запрос может быть сокра-

щено путем изменения архитектуры Web-сервера. Если обработка входящих за-

просов требует немного ресурсов сервера (т.е. циклов процессора), то на генерацию

ответа их тратится гораздо больше. Если генерация ответа будет занимать значи-

тельную часть времени ожидания ответа пользователем, а кэширование полностью

отсутствует, то такая задержка будет наиболее значимой. Кроме того, если архитек-

тура Web-сервера требует последовательной обработки запросов, то генерация

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

данного соединения.

Воспроизведение ответа браузером. Браузер должен синтаксически проанали-

зировать и отобразить ответ. Время на анализ ресурса браузером не может быть со-

кращено кэшированием, если только не хранить версию воспроизводимой страницы,

непосредствегпю в оперативной памяти браузера. Чтение и воспроизведение требует

времени, даже если ответ записан в кэш браузера. Однако поскольку весь документ

доступен локально, то для отображения ответа могут быть использованы различные

технологии. Например, браузер может изменить процесс отображения содержания

документа, если все встроенные изображения уже имеются в наличии. Большинство

Web-страниц отображаются по мере загрузки ресурсов браузером, тем самым ото-

бражение загружаемых ресурсов может быть медленнее, чем отображение из кэша.

Кэширование связано и с финансовыми аспектами, так как влияет на задержки.

Кэширование сокращает нагрузку на сеть провайдера. Неожиданная популярность у

пользователей одного или двух ресурсов могут привести к перефузке провайдера.

Например, некоторые события, например, ожидание приговора суда, популярные

спортивные мероприятия вызывают резкий всплеск обращений пользователей к оп-

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

наращивать пропускную способность магистральной сети. Часть полосы пропуска-

ния, высвобожде1Н1ая в результате кэширования, позволит провайдеру обслуживать

большее число пользователей в пределах существующей инфраструктуры.

Даже при отсутствии неожиданных всплесков нагрузки провайдер обычно обя-

зан платить своему вышестоящему провайдеру за полосу пропускания сети незави-

симо от того, какую часть этой полосы он фактически использует. Сокращая объем

загружаемых данных, провайдер может существенно сократить свои расходы. Про-

вайдеры заключают соглашения по обмену трафиком друг с другом, если обмени-

ваются примерно равными объемами да1П1ых. Такие соглашения требуют симмет-

ричного трафика, так что имеется сильный финансовый стимул сократить объем

данных, передаваемых наружу из сети провайдера. В свою очередь, крупные про-

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

помочь провайдеру в конкурентной борьбе. Новый сервис может быть добавлен

без боязни значительного ухудшения качества обслуживания клиентов.

11.3.

Что кэшировать?

Кэш может принимать решение о необходимости кэширования на основе двух

факторов: требований протокола HTTP и кэшируемого содержания. Требования,

связанные с протоколом, определяют необходимость выполнения директив, касаю-

щихся кэширования сообщений. Требования, связанные с содержанием, отделены

от факторов, определяемых протоколом. Эти соображения обусловлены коммерче-

скими требования и политикой обновления кэша, проверяющей, содержатся ли

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

ляться свойствами сообщений, например, размером.

392 Часть V. Web-приложения

11.3.1.

требования, определяемые протоколом

Хорошо функционирующий кэш должен подчиняться требованиям HTTP. Про-

ект стандарта НТТР/1.1 определяет простые правила того, какие ответы необходимо

кэшировать; методы запросов, ноля заголовков запросов, коды и заголовки ответов

должны указывать на то, что ответ можно кэшировать. Несоответствие одному или

нескольким из перечисленных требований не позволяет кэшировать ответ. Напри-

мер,

ответы на запросы с методами OPTIONS, PUT и DELETE (рассмотренные

в главах 6 и 7) не кэшируются. Ответы на запросы с методом POST не кэшируется,

если не содержат заголовков Cache-Control и Expires. Если кэш не поддерживает за-

головков Range, то ответ с кодом 206 Partial Content не может кэшироваться.

Некоторые ответы включают зависящую от ресурса информацию от исходного

сервера, которая может препятствовать кэшированию сообщений. Такая информа-

ция бывает двух видов: информация о возможности кэширования и директивы

управления кэшированием. Если ответ включает информацию о возможности кэ-

ширования, то решение о кэшированиидолжпо определяться ею. Например, сервер

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

ловка Expires. Если время, указанное в Expire, близко ко времени прибытия сооб-

щения, то ресурс кэшировать нельзя. Директивы управления кэшированием могут

предотвращать кэширование некоторых ответов. Например, директива Cache-

Control: Private указывает, что прокси-сервер, совместно используемый несколь-

кими клиентами, не может кэшировать данный ответ. Ответное сообщение, вклю-

чающее директиву управления кэшированием

Cache-Control: no-store

не должно сохраняться. Директива управления кэшированием

Cache-Control: no-cache

уменьшает вероятность того, что кэш будет сохранять ответ, поскольку перед тем,

как отправить клиенту кэшированную копию, будет осуществлена проверка ее ак-

туальности. Директивы не обязательно должны быть директивами в ответе, пере-

данном исходным сервером. Они могут быть директивами запроса, определенными

запрашивающим клиентом. Например, Cache-Control: no-store может появляться

как в запросе, так и в ответе. Протокол использует эти директивы для обеспечения

конфиденциальности ответа, а также указывает, что данные ресурсы могут быть

изменены после их отправки. Кэш должен внимательно отслеживать такие дирек-

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

Присутствие в запросе заголовка Authorization или заголовка Vary в ответе

снижает шанс того, что ресурс будет кэширован. Заголовок запроса Authorization

указывает на то, что запрашиваемый ресурс доступен не для всех. Это уменьшает

вероятность, что ответ используется многими пользователями. Аналогично, при-

сутствие заголовка Vary указывает на то, что сохраняемый кэшем ответ будет огра-

ничен версией, указанной в заголовке Vary.

Конфликтующие цели сторон, вовлеченных в кэширование, были известны раз-

работчикам HTTP. Огандарт протокола не может дать оптимальное решение для

всех сторон, связанных с транзакцией. Однако разработчики протокола в основном

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

ление последней всем сторонам, вовлеченным транзакцию.

Глава 11. Кэширование 393

11.3.2.

Соображения, определяемые Web-содержанием

у кэша может быть набор своих собственных правил, не связанных с требова-

ниями протокола, для решения вопроса о необходимости кэширования ответа.

Другими словами, возможность кэширования ответа не означает, что он будет обя-

зательно кэширован. Сообщение может оказаться слишком большим, динамически

генерируемым или включать в себя cookies, что может оказать влияние на кэширо-

вание. Политика кэширования может руководствоваться другими соображениями,

отличными от требований протокола, например, атрибутами сообщений. Напри-

мер,

частота, с которой кэш проверяет актуальность ресурсов на исходном сервере,

может диктоваться политикой продолжительности кэширования ресурсов. С дру-

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

вателям, то он может принять решение игнорировать дату последней модификации

и посылать полный ответ вместо передачи 304 Not Modified. Совместно используе-

мый кэш может не кэшировать ответы на запросы, содержащие внедренную в них

личную информацию (например, cookies). Страницы ASP и запросы на документы,

требующие аутентификации, являются, вероятно, не лучшими кандидатами на кэ-

ширование.

Можно сократить коммерческую стоимость передач, игнорируя некоторые огра-

ничения, связанные с кэшированием. Кэши могут сохранять ресурсы, которые не

предполагалось кэшировать, например, в случае использования Cache-Control:

private. Цели пользователя — сократить время ожидания ответа, а провайдера —

сократить объем пересылаемых данных, могут не совпадать с побудительными мо-

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

ничений протокола.

Кэши могут также учитывать расходы но хранению данных и не кэшировать

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

Если сообщение слишком большое, то, возможно, что многие другие объекты будут

вытеснены из кэша. В терминах времени задержки ответа, стоимость загрузки

большого числа небольших ресурсов с соответствующих исходных серверов может

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

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

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

шем, могут давать значительную экономию трафика. Например, предположим, что

новая версия популярной программы появилась на Web-сайте. Такой ресурс имеет

и большой объем, и достаточно высокую частоту запросов. Его кэширование дает

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

провайдеры должны платить за объем загружаемых ими да1Н1ых, и они предпочи-

тают использовать кэши, чтобы не загружать ресурсы многократно.

Многие кэши воздерживаются от сохранения ответов, сформированных сцена-

риями, предполагая малую вероятность того, что те же значения параметров запро-

сов будут повторно использованы. Решение о том, что ответ был сгенерирован как

результат вызова сценария, основано на эвристике. Основное предположение,

влияющее на решение о кэшировании ответа, заключается в том, что в дальнейшем

будет генерироваться один и тот же ответ, а запрос на такой ответ может поступить

в ближайшее время. По сравнению с запросами на статические ресурсы, которые

меняются не слишком часто, каждое выполнение сценария с высокой вероятно-

стью приводит к отличному от предыдущего ответа результату. Однако присутст-

вие в динамическом ответе такой информации о возможности кэширования, как

заголовки Expires и Etag, может указать на целесообразность кэширования ресур-

394 Часть V. Web-приложения

са. Например, рассмотрим CGI-сценарий, который возвращает п-ую цифру числа р.

Ответ не будет изменяться до тех пор, пока передаваемый сценарию параметр ра-

вен п. Многие запросы часто приводят к одному и тому же ответу и некоторые

кэши уже учитывают это. Данное соображение актуально для поисковых серверов,

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

например, "трЗ", "sex" и т.д. Если поисковый сервер обновляет результаты таких

запросов, например, не чаше, чем раз в день, то запрос будет приводить к одному и

тому же ответу. В общем случае не всегда возможно сказать, был или не был воз-

вращенный ответ сгенерирован динамически.

Миф о том, что ответы на CGI-запросы и другие динамически генерируемые

страницы не должны кэшироваться, должен развеяться. Другой категорией отве-

тов,

которые могут выглядеть как некэшируемые, являются ответы, включающие

данные, подготовленные для определегпюго пользователя. Например, ответ, содер-

жащий cookie, рассматривается прокси-сервером как некэшируемый, т.к. ожидает-

ся,

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

с cookies могут все же кэшироваться, если они возвращают один и тот же ответ для

различных значений cookies [WM99]. Заметим, что некоторые типы содержания,

которые обычно рассматриваются как кэшируемые (например, изображения в фор-

матах GIF или JPEG), могут на самом деле включать нестандартную информацию,

или вообще информация о необходимости их обновления может отсутствовать, что

затрудняет принятие решения о кэшировании.

Решение о кэшировании определяется частотой изменения ресурсов. Некоторые

ресурсы изменяются не очень часто. Примерами таких ресурсов является электрон-

ные книги. Некоторые статические ресурсы могут изменяться периодически. Основ-

ная страница пользователя, например, периодически изменяется, но не особенно час-

то.

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

метрикой для принятия решения о кэшировании ресурса. Первоначально решение о

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

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

то маловероятно, что он изменится в ближайшем будущем. Это делает ресурс канди-

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

фикации используется также для решения о том, когда проверить актуальность кэ-

шированного ответа. И наоборот, этот гюдход предполагает, что если ресурс был мо-

дифицирован недавно, то имеется высокая вероятность того, что он вскоре будет

снова изменен. Таким образом, кэшированная копия такого ресурса очень быстро ус-

тареет. В то же время высокая частота изменения ресурса может указывать на высо-

кий интерес и на большую частоту запросов, что является аргументом в пользу его

кэширование. Поскольку выгода от кэширования обусловлена в основном большим

числом обращений к кэшируемому ресурсу, то частота обращений к ресурсу должна

учитываться при принятии решения о кэшировании.

Нагрузка на кэш тоже должна учитываться при принятии решения о кэширова-

нии ресурса. Например, заполненный кэш может обрабатывать запросы к кэшу,

просто посылая отказы в кэшировании, и, соответственно, не кэшируя ответные со-

общения в этих случаях.

11.4.

Где выполняется кэширование?

Кэши имеются в браузерах, они также располагаются на пути между агентом

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

Глава 11, Кэширование 395

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

местах, а не только в одном месте. Кэширование браузером и прокси-сервером име-

ет следующие особенности:

• Кэш браузера помогает избежать повторной загрузки страниц, просматривае-

мых пользователем во время сеанса работы с браузером. Однако кэш браузера

никак не учитывает частые запросы других пользователей на тот же ресурс.

• Кэширующий прокси-сервер может иметь десятки, если не сотни пользовате-

лей. Однако браузер может хранить набор принятых ответов за большее вре-

мя,

чем кэширующий прокси-сервер. Работая с большим числом пользовате-

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

быстрее, чем браузер.

• Региональный кэш может помочь нескольким другим кэшам, географически

расположенным недалеко от него. Национальный кэш может группировать

региональные кэши и помочь им сократить объем трафика через националь-

ные границы. С каждым шагом, удаляющим от клиента, добавляются потери

в производительности даже при наличии кэшированиых ответов.

В главе 3 (раздел 3.8) были кратко описаны обратные и перехватывающие про-

кси-серверы. Обратный прокси-сервер работает как представитель одного или бо-

лее исходных серверов и может включать кэш. Кэширование на нем выполняется

от лица исходных серверов, а не пользователей. Это сокращает нагрузку на исход-

ные серверы, задачи, с которыми сталкиваются обратные прокси-серверы, сходны

с задачами для прокси-серверов, находящихся близко от пользователей. Наиболее

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

щаются в кэш обратного прокси-сервера. Если ресурс не найден на обратном про-

кси-сервере, то последний направляет запрос исходному серверу. При этом про-

кси-сервер действует как ретранслятор.

Перехватывающий прокси-сервер может быть расположен в произвольном мес-

те сети и анализировать трафик на сетевом и транспортном уровнях. Перехваты-

вающий прокси-сервер перехватывает HTTP-запрос и принимает ответ. Обычно

такой прокси-сервер располагается ближе к клиентам. Отметим, что перехваты-

вающий прокси-сервер не обязательно должен находиться на пути прохождения

пакетов. Устройство, которое может проанализировать пакеты на транспортном

уровне, может переадресовывать трафик перехватывающему прокси-серверу. По-

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

щимся под тем же административным управлением, что и перехватывающий про-

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

чувствовать только сокращение времени ожидания ответа и предположить, что

ответ получен из кэша. К сожалению, некоторые перехватывающие прокси-серве-

ры не поддерживают непосредственно протокола HTTP, а принятый ответ может

быть не тот же самый, который был бы получен от обычного прокси- или исход-

ного сервера.

11.5.

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

Обсудим теперь подробно вопрос о том, как выполняется кэширование, т.е. опе-

рации, которые происходят при кэшировании. Во-первых, кэш должен определить,

нужно ли сообщение кэшировать. Затем решить, имеется ли для этого достаточно

свободного места и, если места нет, решить, какие объекты в кэше следует замес-

396

Часть

Web-приложения

тить.

при получении запроса кэш должен определить, может ли он его обработать,

если может, то вернуть кэшированный ответ и обновить некоторую информацию.

Кэш должен иметь согласованную политику по проверке актуальности кэширован-

ных ресурсов.

11.5.1.

Решение о необходимости кэширования

Кэш должен сначала решить, нужно ли сообщение кэшировать. Различные

кэши используют различные стратегии принятия решений о кэшировании. Как

было обсуждено в разделе И.З^, общими критериями, используемыми при приня-

тии решения о кэшировании, являются:

• Имеются ли требования протокола, которые предотвращают кэширование от-

вета?

• Является ли содержание ответа иекэшируемым (т.е. динамические данные

или особый тин содержания)?

• Насколько вероятно, что кэшированный ответ будет использован повторно?

• Приведет ли кэширование данного ресурса к замещению в кэше одного или

более ресурсов?

Кэш использует некоторые или все неречислегнхые критерии для принятия ре-

шения о необходимости кэширования.

11.5.2.

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

После принятия решения о записи сообщения осуществляется проверка, можно

ли записать сообщение без замещения других объектов в кэше. Если это не так, то

запускается специальный алгоритм замещения. Замещение содержимого кэша яв-

ляется достаточно трудоемким процессом, особенно если замещается большое ко-

личество небольших объектов (замещение содержимого кэша будет рассмотрено

более детально в разделе 11.6). Дополнительная нагрузка возникает, когда выпол-

няются новые запросы на замещенные объекты, так как должны быть установлены

гювые соединения для их загрузки. Часто, когда становится известно, что ресурс

устарел, то он может быть удален из кэша, даже если кэш не заполнен до конца.

Это понижает затраты на выполнение алгоритма замещения содержимого кэша

в момент обработки запроса, в свою очередь это уменьшает время ожидания ответа.

После того как освобождается место для записи ответа, кэш извлекает инфор-

мацию о сообщении, включая дату последнего обновления и информацию об уста-

ревании. Обрабатываются следующие заголовки сообщений: Expire и Cache-

Control; max-stale, несущие информацию об актуальности ресурса. Эти поля заго-

ловков помогают кэшу выполнять ограничения HTTP по периоду времени, в тече-

ние которого может быть возвращен семантически корректный ответ. Кэш, поддер-

живающий протокол, обязан гарантировать, что любой возвращенный им ответ,

рассматривался бы исходным сервером как актуальный. В главе 7 (раздел 7.7.3) об-

суждались различные заголовки, семантически связанные с кэшированием. При

отсутствии специфической информации об актуальности ресурса кэш использует

эвристически полученное время истечения срока актуальности. Значение этого

времени может быть получено, основываясь на времени последнего обновления ре-

сурса (значения поля заголовка Last-Modified). Например, сервер может добавить

фиксированный промежуток времени, скажем, 10 минут к значению Last-Modified

Глава 11. Кэширование 397

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

сурса, используемый при последующих поисках этого ресурса. Ключ создается

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

прос,

то он использует URL для поиска ресурса в кэше.

11.5.3.

Возврат кэшированного ответа

Когда в кэше находится ответ, соответствующий ключу, то встает вопрос о том,

что возвращать пользователю. В зависимости от политики кэширования и ограни-

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

жет быть выполнена проверка актуальности для того, чтобы убедиться, что ответ

еще не устарел (проверка актуальности и общая согласованность кэшированных

результатов будут обсуждены ниже в разделе 11.7). Если проверка подтверждает,

что ответ не устарел, то запрос удовлетворяется из кэша. В противном случае кэш

получает новую копию ресурса и использует политику кэширования для решения

о том, нужно ли его снова кэшировать, одновременно направляя ресурс клиенту.

Если запрос не найден в кэше, то запрос перенаправляется исходному серверу.

11.5.4.

Обслуживание кэша

Периодически кэш может проверяться на наличие устаревших объектов, чтобы

удалить их. Кэш может также контролировать частоту запросов кэшированного

объекта, чтобы определить наиболее популярные ресурсы и выполнить специаль-

ные действия. Например, кэш может проверить актуальность популярного ресурса.

Такая проверка может быть сделана с помощью запроса HEAD, который приводит

к получению только метаданных ресурса. Кэш может также обратиться к исходно-

му серверу, определить наличие изменений ресурса и обновить его содержимое

в кэше. Такой подход направлен на уменьшения времени ожидания ответа пользо-

вателями. Однако он увеличивает трафик между исходным сервером и кэшем.

11.6.

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

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

объектов для кэширования новых ответов. В течение последних лет было исследо-

вано несколько подходов к замещению объектов в кэше. Некоторые из них заимст-

вованы из традиционных подходов к кэшированию в файловых системах, а некото-

рые специально предложены для Web-кэширования. Одним из хорошо известных

подходов является алгоритм LRU (Least Recent Use) ~ замена объектов, запро-

шенных наиболее давно. Книги на полках, которые давно не использовались, боль-

ше покрыты пылью, чем те, которыми пользовались недавно. Чем больше времени

прошло с момента последнего обращения, тем больше пыли. Задачи кэширования,

такие, как уменьшение объема данных, пересылаемых по сети, и сокращение вре-

мени ожидания ответа, приводят к необходимости комплексного решения задачи

замещения объектов в кэше. Комплексный подход состоит в использовании комби-

нации метрик, включая размер кэшированного ответа, тип его содержания и ин-

формация о расстоянии до исходного сервера.

398 Часть V. Web-приложения

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

включая:

• Стоимость извлечения ресурса. Стоимость извлечения ресурса с исходного

сервера определяется возможностями кэша в организации взаимодействия

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

нет кэша. Цена замещения ресурса, требующего больших затрат по извлече-

нию,

должна быть оправдана тем, что ресурс потребуется в будущем.

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

вой памяти, сохранение одного объекта требует уменьшения объема памяти

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

его извлечение с исходного сервера будет также дорогостоящим.

• Число обращений к ресурсу. Объект, к которому многократно обращались

в прошлом, будет, вероятно, запрошен снова и является достойным кандида-

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

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

кая вероятность высокая, то нет смысла удалять ресурс из кэша. Вероятность

доступа к ресурсу может быть рассчитана заранее или оценена па основе под-

ходящих образцов.

• Время последней модификации ресурса. Ресурс, который не менялся в тече-

ние длительного времени, скорее всего, не изменится и в ближайшем буду-

щем. Ресурс, созданный совсем недавно, может оказаться или динамически

создаваемым ресурсом, или он снова изменится в ближайшем будущем. Ре-

сурсы, которые чаще изменяются, как правило, оказываются более популяр-

ными, поскольку они меняются именно в результате своей популярности и,

следовательно, являются хорошими кандидатами на кэширование. Однако кэ-

шируемый ответ должен в этом случае заменяться достаточно часто (с часто-

той его изменения на исходном сервере). Время последней модификации, та-

ким образом, может использоваться для принятия решения о том, какие ре-

сурсы можно замещать.

• Эвристическая оценка времени истечения срока годности ресурса. Если вре-

мя истечения срока годности ресурса не указано сервером, то кэш должен найти

эвристическую оценку этого времени. Если отсутствуют ресурсы с истекшим

сроком годности, то наиболее вероятным ресурсом на замещение является тот,

у которого осталось наименьшее время до истечения его срока годности.

Каждый из этих факторов принимается во внимание при решении о том, какой

механизм замещения будет наиболее подходящим для текущего состава объектов

в кэше.

Различные факторы, принимаемые во внимание при замещении объектов

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

ритм использует одну метрику, в то время как двухуровневый алгоритм использует

комбинацию алгоритмов с первичной и вторичной метриками. Комбинированные

алгоритмы используют взвешенные значения оценок. Если сложность замещающе-

го алгоритма увеличивается, то возможно снижение его эффективности. Это про-

исходит по причине больших накладных расходов в процессе добавления ресурса,

который, скорее всего, скоро будет замещен. Накладные расходы на выполнение

алгоритма рассматриваются как стоимость и являются фактором в оценке общей

полезности алгоритма. Ниже приведен краткий обзор предложенных и используе-

мых алгоритмов замещения объектов кэша.

Глава

11.

Кэширование

399

Самый старый из используемых (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-ресурсов различных

размеров [CI97]. Модифицированный алгоритм определяет значение параметра,

называемого

полезностью,

и замещает ресурс, имеющий наименьшее значение по-

лезности. Отталкиваясь от стоимости загрузки ресурса в кэш и его размера, полез-

ность принимает во внимание также временной фактор, значение которого обнов-

ляется каждый раз, когда ресурс удаляется из кэша.

Замещение объектов в кэше было давней проблемой кэширования. Устойчивое

снижением цен на устройства хранение данных привело к тому, что объем кэшей

существенно увеличился. Проблема замещения объектов кэша сошла со сцены по

следующим четырем основным причинам:

• Устойчивое снижение цеп на устройства хранения данных, привело к появле-

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

запрашиваемых ресурсов.

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

• Разработка алгоритмов, которые могут использоваться в большинстве ситуа-

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

Hyper-G относятся к этой категории.

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