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

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

470 Часть VI. Перспективы исследований

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

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

полезными для прокси-сервера.

• Доля обновлений. Доля обновлений оценивает вероятность того, что клиент-

ский запрос был предсказан заранее и обращен к ресурсу, который был затре-

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

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

сурса до запроса клиента.

Коэффициент попадания и точность широко применяются при оценке инфор-

мации поисковыми системами, рассмотренными в главе 2 (раздел 2.7.3). В контек-

сте построения томов коэффициент попадания и точность отражают противоречие

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

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

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

комендаций. В свою очередь это ведет к снижению точности, поскольку многие из

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

Коэффициент попадания, точность и доля обновлений призваны оценить эф-

фективность серверных рекомендаций. На практике полезность рекомендации мо-

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

получения предсказанного запроса. Предсказание запроса за малое время до его

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

среагировать на предсказание. Например, прокси-сервер может не иметь достаточ-

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

чения запроса на ресурс от клиента. Точно так же, рекомендация, доставленная за-

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

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

принести большой выгоды. Заранее выбранный ресурс будет занимать место

в кэше прокси-сервера. Кроме того, ресурс может быть модифицирован исходным

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

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

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

Подобные ограничения по времени могут быть учтены путем назначения фик-

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

кси-сервер получает рекомендацию относительно ресурса 5. Если клиент запраши-

вает ресурс S в течение промежутка времени, не превышающего т секунд, рекомен-

дация не будет полезной. Если клиент запрашивает ресурс 5 по истечении Т секунд

после выдачи рекомендации, где Г > т, рекомендация не будет полезной. Другими

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

вале времени между т и Г секунд после получения рекомендации прокси-сервером.

Алгоритм построения томов формирует том

для каждого ресурса г, где

пред-

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

са г. Применение этих томов к последовательности запросов приводит к различ-

ным значениям показателей размера рекомендации, коэффициента попадания, точ-

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

предполагает несколько подходов к построению томов. Алгоритм может пытаться

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

ний на другие показатели. Например:

• Увеличивать коэффициент попадания до достижения верхнего предела сред-

него объема рекомендации.

Глава 13. Перспективы исследований, связанных с кэшированием 471

• Уменьшать объем рекомендации до достижения нижней границы коэффици-

ента попадания.

• Увеличивать коэффициент попадания до достижения нижней границы точгюсти.

• Увеличивать точность до достижения нижней границы коэффициента попада-

ния.

В первом а/нюритме процесс начинается с целевого размера рекомендации и по-

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

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

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

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

мального соотношения между точностью и коэффициентом попадания. Однако ни

одна из этих задач оптимизации не имеет эффективного решения [CKR99J, что за-

ставляет искать эффективные эвристические алгоритмы.

АЛГОРИТМЫ, ОСНОВАННЫЕ НА ВРЕМЕННОЙ ЛОКАЛИЗАЦИИ

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

13.2.1,

предлагает

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

этим ресурсам. Эвристика предполагает, что том

должен содержать ресурс s, если

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

прос на S должен поступить не раньше т секунд, и не позже Т секунд после запроса

на г. Для принятия решения, включать ли 5 в

Vr,

алгоритм подсчитывает число за-

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

число запросов па ресурс г. Если полученное отношение превышает некоторое по-

роговое значение, то 5 включается в

Vr]

в противном случае этого не происходит.

В действительности алгоритм может подсчитать число запросов на каждый из ре-

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

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

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

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

в Web [РМ96, Bes95,JK98].

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

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

счетчиков, особенно для Web-сайтов, имеющих тысячи уникальных ресурсов. Хра-

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

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

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

для пар ресурсов, которые редко фигурируют вместе [CKR99]. Во-вторых, алго-

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

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

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

и того же ресурса. Это дополнительные рекомендации не предоставляют никакой

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

избежать создания этих лишних рекомендаций. Это сокращает размер рекоменда-

ции и способствует повышению точности. Удаление ресурса из тома повышает точ-

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

сказывает будущий запрос.

Расширение исходного алгоритма дает возможгюсть удалять неэффективные ре-

комендации за счет сокращения томов. Начав с томов, созданных исходным алго-

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

472 Часть VL Перспективы исследований

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

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

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

удаляет неэффективные элементы из каждого тома. Идея удаления неэффектив-

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

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

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

ным в предвидении запросов на ресурс. Затем, па следующей итерации, алгоритм

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

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

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

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

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

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

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

но требует еще больших вычислительных затрат. Чтобы найти наиболее выгодный

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

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

случаях увеличение времени вычислений может не иметь значения. Решение зави-

сит от частоты формирования томов, а также различий в эффективности и объеме

вычислений для этих трех алгоритмов. Кроме того, важно осуществлять сравнение

этих трех алгоритмов с более простыми подходами, например, с эвристическими

процедурами, описанными в разделе

13.2.1,

в которых ресурсы группируются на

основе структуры их URL. Эти важные проблемы не могут быть решены без оцен-

ки алгоритмов с учетом реальной работы серверов.

13.2.5.

Оценка алгоритмов построения томов

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

а также от поведения клиентов. Эксперименты, описапные в [CKR98, CKR99J, оце-

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

тов,

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

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

во запросов — от 180000 до 13000000 при обращении до 218000 клиентов

к 94-30000 уникальным ресурсам. В журналах прокси-серверов ответ 304 Not

Modified давался па 16-19% запросов. В журналах серверов около 85% запросов

пришлось примерно на 10% уникальных ресурсов. Эти статистические данные пока-

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

повысить эффективность работы прокси-сервера. Например, рекомендации, содер-

жащие время последней модификации Last-Modified ресурсов сервера, позволят

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

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

В ходе экспериментальных исследований предпринималась попытка устано-

вить,

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

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

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

ния, точности и доли обновлений. В исследованиях использовался единственный

фильтр прокси-сервера, ограничивающий число рекомендаций, совмещенных с ка-

ждым ответом. С сообщениями-ответами для ресурса г сервер совмещал рекомен-

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

Глава 13. Перспективы исследований, связанных с кэшированием 473

сурса г. Число рекомендаций на одно сообщение-ответ в ходе экспериментов варь-

ировалось. При построении томов алгоритмы учитывали все ресурсы, доступ

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

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

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

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

В результате исследований было сделано заключение, что каждый из алгорит-

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

Однако для томов, ностроегн1ых на основе структур каталогов, высокие коэффици-

енты попадания достигаются ценой излишне большого размера рекомендаций и

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

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

ность и меньший объем рекомендаций. В общем случае отправка большего числа

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

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

проходные и многопроходные алгоритмы предлагают дальнейшее уменьшение объ-

ема рекомендаций и увеличение точности. Двухпроходный алгоритм дает почти

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

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

ходного алгоритма был получен коэффициент попадания от 60% до 80%, точность

от 80% до 88% и число рекомендаций от 2 до 10 рекомендаций на сообщение. Эти

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

делах от 60 секунд до 5 минут и т = 0.

Применение алгоритмов к большим серверным журналам с миллионами запи-

сей требует больших затрат времени. Затраты можно уменьшить, выполнив алго-

ритм по формированию томов над усеченной версией журнала. Создание усечен-

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

просов, поступивших от этих клиентов. Усеченные журналы содержат от 3% до

50%

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

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

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

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

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

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

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

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

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

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

Эксперименты не предлагают идеального решения для достижения оптимально-

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

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

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

па основе рекомендаций сервера будет вносить существенную дополнительную на-

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

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

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

дации для проверки актуальности (или аннулирования) кэшированных ресурсов.

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

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

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

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

474 Часть VI. Перспективы исследований

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

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

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

13.2.6.

Комплексный информационный обмен. Резюме

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

ности прокси-серверов па основе рекомендаций от исходных серверов. Сервер

руннирует взаимосвязанные ресурсы в тома и применяет фильтры для формиро-

вания рекомендаций обратившимся с запросами прокси-серверам. Эксперименты

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

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

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

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

мендации, которые генерируют дублирующие предсказания. Объединение фильтров

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

ции НТТР/1.1. Фильтр прокси-сервера может быть отправлен в новом заголовке за-

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

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

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

требуется длительного процесса стандартизации. Выразительные средства НТТР/1.1

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

В ходе изучения проблемы были введены понятия серверных томов и фильтров

прокси-серверов, описаны и сопоставлены различные алгоритмы построения то-

мов.

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

разнообразных фильтров с различными параметрами. Поиск эффективного спосо-

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

алгоритмическую задачу. Было предложено на начальном этапе хранить элементы

тома в отдельных списках типа «первым пришел

—

первым обработан» в зависимо-

сти от атрибутов ресурсов. Однако это может оказаться пе самым эффективным

способом обработки большого числа параметров фильтрации. Кроме того, про-

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

точности и доли обновлепрш. Определение влияния этих показателей па эффек-

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

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

бора параметров фильтров прокси-серверов.

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

объединяющие ресурсы, доступ к которым осуществляется совместно. Серверу не-

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

тываются прокси-сервером без обращения к исходному серверу. Это ограничивает

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

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

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

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

тельно ресурса

В этом случае запрос на s может содержать информацию о преды-

дущем запросе на г. Это даст возможность серверу ассоциировать запросы на ре-

сурс S с ресурсом г. Аналогично, сервер не обрабатывает все запросы, которые от-

носятся к встроенным изображениям и гиперссылкам HTML-файлов. Некоторые

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

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

рам, могут содержать информацию о ресурсах, расположенных па других серверах.

Глава

13^

Перспективы исследований, связанных с кэшированием 475

13.3.

Упреждающая выборка

Обработка Web-занроса состоит из нескольких ключевых действий, включая

преобразование доменного имени, установление ТСР-соединения и обмен запроса-

ми-ответами HTTP. Web-клиенты, включая агенты пользователей и прокси-серве-

ры,

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

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

ся дополнительная нагрузка на сеть и на сервер. В течение послед1Н4х нескольких

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

дающей выборки. До недавнего момента внедрение этих идей сдерживалось по

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

ность работы пользователей в конечном итоге может перевесить эти огра1П4чепия.

13.3.1.

Упреждающее преобразование доменных имен

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

вать доменное имя запрашиваемого URL в IP-адрес. Клиент инициирует систем-

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

DNS-серверу, который, в свою очередь, связывается с другими DNS-серверами, как

описывалось ранее в главе 5 (раздел 5.3). Ожидание ответа от локального DNS-

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

жать этой задержки, Web-клиент может инициировать преобразование имени в ад-

рес до пользовательского запроса. Например, пользователь посещает Web-страпи-

цу, содержащую несколько гипертекстовых ссылок на другие Web-серверы. Клиент

может определить IP-адреса этих серверов, пока пользователь читает страницу.

Если пользователь щелкает на одной из этих гипертекстовых ссылок, клиент мо-

жет немедленно установить ТСР-соединепие с Web-сервером. Это уменьшает вре-

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

Сокращение времени ожидания зависит от времени, которое требуется для об-

работки DNS-запроса. DNS-запрос не вносит большой задержки, если локальный

DNS-сервер уже имеет кэшироваппую копию IP-адреса Web-сервера. Однако за-

держка может быть значительной, если локальный DNS-сервер должен связаться

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

кунд — вполне обычное явление [СКОО, HWOO]. Отсутствие IP-адреса в кэше

DNS-сервера

—

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

или соответствий доменное имя-1Р-адрес с небольшими временами жиз1П4 (TTL).

Небольшие значения TTL достаточно часто имеют место, когда ответы па DNS-за-

просы используются для распределения нагрузки между репликами Web-сайта.

Однако небольшие значения TTL также ограничивают выигрыш от упреждающей

выборки информации DNS задолго до получения пользовательского запроса. Хотя

упреждающая выборка обеспечивает Web-клиепту и локальному DNS-серверу ко-

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

как пользователь запросит содержание с этого Web-сервера. Рост популярности се-

тей распределения содержания, которые используют небольшие значения TTL

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

ют проблему упреждающего преобразования доменных имен DNS.

Упреждающая выборка IP-адреса Web-сервера уменьшает время ожидания на

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

Web-клиепт выполняет упреждающее преобразование доменного имени в IP-адрес

в надежде, что пользователь со временем посетит Web-сайт. Однако поведение ноль-

476

Часть VL Перспективы исследований

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

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

DNS-сервер и, возможно, другие DNS-серверы. Обработка этого запроса может за-

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

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

рые редко используются. Если большая часть Web-клиентов выполняет упреждаю-

щее преобразование доменных имен, это может значительно увеличить число

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

нию трафика. Преимущества от упреждающего преобразования домегншхх имен

должны быть сопоставлены с возникающими при этом издержками.

13.3.2.

Упреждающее установление соединений

Составной частью обработки HTTP-запроса является установление ТСР-соеди-

иения с Web-сервером или с промежуточным компонентом, таким как прокси-сер-

вер.

Открытие ТСР-соединения требует трехэтапного обмена между клиентом и

сервером, о чем рассказывалось в главе 5 (раздел 5.2). Время задержки на этом эта-

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

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

словленной утерей пакетов. Чтобы скрыть эти задержки от пользователя, Web-

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

тельского запроса [CKOOJ. Затем, когда пользователь щелкает мышью на гипер-

ссылке, клиент может немедленно отправить НТТР-занрос через открытое ТСР-

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

временем закрывает ТСР-соединение.

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

на временем установления ТСР-соединения. Для небольших сообщений-ответов

дополнительное время прохождения пакетов в прямом и обратном направлении

составляет ощутимую долю общей задержки при открытии ТСР-соединения. Од-

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

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

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

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

править НТТР-занрос. Во-вторых, пользовательский запрос должен поступить до

того,

как клиент или сервер решат закрыть соединение. Web-серверы обычно уста-

навливают ограничение на время нахождения ТСР-соединения в бездействующем

состоянии. Пользовательский запрос, инициированный после того, как сервер за-

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

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

го ТСР-соединения может вызвать увеличение ожидания в очереди на создание

новых соединений. Что еще хуже, увеличение числа открытых соединений может

уменьшить значение таймаута для выполняющихся сеансов.

Открытие ТСР-соединения с сервером снижает время ожидания на стороне

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

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

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

тия соединения. Даже если клиент закрывает ТСР-соединение, не отправляя

ТСР-запрос, сервер потребляет ресурсы на открытие и поддержание соединения.

Web-сервер должен сохранять состояние соединения и может назначить процесс

лля обработки ожидаемого HTTP-запроса (запросов). В действительности Web-

Глава

13.

Перспективы

исследований,

связанных

кэшированием

477

сервер обычно сохраняет состояние в течение определенного периода времени по-

сле закрытия соединения. Сохранение данного ТСР-соединения может помешать

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

тие ТСР-соединения без отправки HTTP-запроса может рассматриваться как атака

отказа от обслуживания (DoS) на Web-сервер. Следует сопоставлять увеличение

нагрузки на сеть и на сервер с потенциальным повышением производительности

на стороне пользователя.

13.3.3.

Упреждающая выборка в HTTP

После установления ТСР-соединения Web-клиент выдает HTTP-запрос Web-

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

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

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

множества факторов, в том числе от времени создания ответа на сервере, размера

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

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

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

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

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

сервера, открытия соединения с сервером и отправки HTTP-запроса. Пользователь

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

сделать использование ТСР-соединений более эффективным, нежели при традици-

01Н1ЫХ Web-передачах, управляемых действиями пользователя. Клиент с упреж-

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

в ходе одного постоянного соединения, а совместная передача сообщений-ответов

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

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

Упреждающей выборке HTTP-ответов посвящены мгюгочисленные исследования

[Bes95,

РМ96, JK98, СВ98, Duc99]. Несмотря на потенциальное уменьшение времени

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

вызвать значительное увеличение нагрузки на Web-сервер и сеть. Упреждающая вы-

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

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

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

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

ствляет доступ в Web через модем с низкой пропускной способностью [HL96, LB97J.

С 0Д1ЮЙ стороны, упреждающая выборка в моменты бездействия гюзволит более эф-

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

упреждающая выборка в момент загрузки пользователем другой Web-страницы уве-

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

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

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

Вместо упреждающей выборки ресурса сервер может осуществить выборку ме-

таданных ресурса. Например, клиент может отправить запрос HEAD серверу, как

говорилось ранее в разделе 13.1.2. HTTP-ответ будет иметь те же заголовки, что и

ответ на запрос GET. Эта информация особенно полезна, если клиент уже имеет

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

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

вить информацию об актуальности ресурса. Заголовки в сообщении-ответе могут

478

Часть VL Перспективы исследований

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

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

нию,

такие как Last-Modified, Cache-Control или Content-Type, чтобы определить,

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

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

няется. Кроме того, клиент может просмотреть заголовок Content-Length с целью

определения размера ресурса. Клиент может решить осуществить упреждающую

выборку ресурса, если заголовок Content-Length указывает, что размер ресурса

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

борки ресурсов, отвлекающих на себя значительную часть сетевого трафика.

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

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

дением, путем передачи запроса GET с заголовком Range (в предположении, что

Web-сервер допускает запросы на диапазоны). Например, клиент может запросить

первые 1000 байтов ресурса. Это позволит клиенту загружать небольшой ресурс

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

чаях может оказаться полезной упреждающая выборка префикса ресурса [Ног98,

SRT99].

Например, первые несколько байтов GIF-файла содержат размер изобра-

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

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

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

достаточное количество кадров, чтобы начать воспроизведение потока [SRT99,

GRBOO].

Как только пользователь запросит ресурс, браузер может отправить вто-

рой запрос Range, чтобы осуществить выборку оставшегося содержимого. С точки

зрения пользователя содержимое начинает воспроизводиться пемедле1Н10, несмот-

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

13.3.4.

Компромиссы при упреждающей выборке

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

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

ты Web. При достижении компромисса между этими двумя факторами следует

учитывать следующее:

• Какие задачи следует выполнять с упреждением. Упреждающая выборка мо-

жет включать выполнение DNS-запроса, открытие ТСР-соединения, извлече-

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

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

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

компоненты Web.

• Какие ресурсы учитывать. Выборка с упреждением наиболее эффективна,

если информация вероятнее всего будет использоваться и сохранит свою ак-

туальность. Это подразумевает выявление наиболее популярных ресурсов и

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

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

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

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

стикой о поведении пользователей.

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

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

Глава

13.

Перспективы

исследований,

связанных

кэшированием

479

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

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

единение с Internet. Если агент пользователя осуществляет взаимодействие

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

В качестве альтернативы прокси-^сервер может сам выполнять упреждающую

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

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

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

Одной из первых систем выборки с упреждением в HTTP, осуществляющих

синтаксический анализ HTML-файлов и упреждающую выборку ресурсов на осно-

ве гиперссылок, была система Letizia [Lie95], о которой говорилось в главе 2 (раз-

дел 2.8.2). В Letizia для отображения загруженного с упреждением содержания от-

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

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

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

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

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

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

наиболее популярными. Возьмем Web-страницу, содержащую список URL, возвра-

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

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

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

на с их расположением на странице.

Агент пользователя может оценить популярность URL на основе предыдущих

запросов. Например, Letizia отслеживает предпочтения пользователя и действия

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

ем.

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

пулярности ресурсов, анализируя запросы групп клиентов. На основе анализа по-

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

ссылки наиболее популярны. При получении запроса на HTML-файл прокси-сер-

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

тупных на Web-странице. Однако прокси-сервер не будет иметь достаточно дан-

ных о поведении пользователей, если только несколько клиентов не обратились

в прошлом к HTML-файлу [JK98]. Сервер обладает более полной информацией о

поведении пользователей. Таким образом сервер может предоставить прокси-сер-

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

шены в будущем, о чем говорилось ранее в разделе 13.2.

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

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

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

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

изменения HTML-страницы и периодического обновления статистики для страницы.

Подобные подходы наиболее эффективны для специфических приложений, таких как

поисковые машины, но не для всех HTML-страниц. В некоторых случаях человек,

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

мер,

предположим, что в HTML-файле http://www.foo.com/index.html имеется ги-

пертекстовая ссылка на HTML-файл http://www.foo.com/neat.html, содержащий

встроенное изображение http://www.foo.com/pic.jpg. Наличие гиперссылки на

pic.jpg на странице index.html приводит к тому, что клиент заранее выберет изобра-

жение при загрузке начальной Web-страницы. В результате изображение уже будет