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

Эффективность и объем вычислений зависят от количества ресурсов на сервере, а также от поведения клиеигов. Эксперименты, описанные в [CKR98, CKR99J, оценивают алгоритмы на основе данных из журналов серверов нескольких Web-сай- тов, а также на основе данных из журналов прокси-серверов крунных корпораций. Интервал времени наблюдений варьировался от одной до семи недель, а количество запросов — от 180000 до 13000000 при обращении до 218000 клиентов к 94-30000 уникальным ресурсам. В журналах прокси-серверов ответ 304 Not Modified давался на 16-19% запросов. В журналах серверов около 85% запросов пришлось примерно на 10% уникальных ресурсов. Эти статистические данные показывают, что правильное предсказание запросов на эти популярные ресурсы может повысить эффективность работы прокси-сервера. Например, рекомендации, содержащие время последней модификации Last-Modified ресурсов сервера, позволят прокси-серверу обновить время истечения актуальности кэшированных ответов, которые не были модифицированы, либо удалить ответы, которые были изменены.

В ходе экспериментальных исследований предпринималась попытка установить, может ли сервер эффективно доставлять полезные рекомендации прокси-серверам. В ходе экспериментов сравнивались различные алгоритмы построения томов с учетом четырех показателей: объема рекомендации, коэффициента попадания, точности и доли обновлений. В исследованиях использовался единственный фильтр прокси-сервера, ограничивающий число рекомендаций, совмещенных с каждым ответом. С сообщениями-ответами для ресурса r сервер совмещал рекомендации для ресурсов, которые наиболее вероятно могли быть запрошепы после ре- cypca г. Число рекомендаций на одно сообщение-ответ в ходе экспериментов варьировалось. При построении томов алгоритмы учитывали все ресурсы, доступ к которым осуществлялся не менее десяти раз. Это значительно снизило сложность алгоритмов построения томов за счет удаления большого числа менее популярных ресурсов. Построение томов для таких ресурсов не привело бы к выдаче достаточно большого числа полезных рекомендаций.

В результате исследований было сделапо заключение, что каждый из алгоритмов построения томов дает хорошие коэффициенты попадания и доли обновлений. Однако для томов, посгроенных на основе структур каталогов, высокие коэффициенты попадания достигаются цепой излишне большого размера рекомендаций и низкой точности. Сервер носылает много избыточных рекомендаций. Алгоритмы, основанпые на анализе доступа клиентов к ресурсам, даюг гораздо большую точность и меньший объем рекомендаций. В общем случае отправка большего числа рекомендаций ведег к снижению точности при весьма незначительном увеличении коэффициента попадания. За счет удалепия неэффективных рекомендаций, двух- нроходпые и многопроходные алгоритмы предлагают дальнейшее уменьшение объема рекомендаций и увеличение точности. Двухпроходпый алгоритм дает почти столь же хороший эффект, что и многопроходный алгоритм, требуя при этом гораздо меньших затрат. Для множества журналов в результате применения двухпро- ходного алгоритма был нолучеп коэффициент попадания от 60% до 80%, точность от 80% до 88% и число рекомендаций от 2 до 10 рекомендаций на сообщение. Эти результаты действительны для предсказаний, соответствующих значениям T в пределах от 60 секунд до 5 минут и т = 0.

Применение алгоритмов к большим серверным журналам с миллионами записей требует больших затрат времени. Затраты Можно уменьшить, вынолпив алгоритм но формированию томов над усеченной версией журнала. Создание усеченной версии журнала предусматривает случайную выборку клиентов и Анализ запросов, поступивших от этих клиентов. Усеченные журналы содержат от 3% до 50% запросов исходного журнала. Эксперименты показали, что построение томов на основе этих усеченных журналов не приводят к снижению эффективности. В другой группе экспериментов тома создавались на основе запросов одного периода, а применялись эти тома к другому периоду из того же журнала. Использование одних и тех же томов за час или день к последующему часу или дшо не искажало результатов. Однако важно периодически пересчитывать тома, чтобы адаптироваться к измепепиям в поведении пользователей, например, учесть особенности трафика в рабочие и выходные дни, либо чтобы учесть изменения в содержании Web-сайта. Наблюдения показали, что периодическое построение томов на основе выборок из журналов может быть вполне приемлемым для большинства серверов.

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

Источник: 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