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

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

ПОКАЗАТЕЛИ ЭФФЕКТИВНОСТИ

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

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

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

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

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

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

Коэффициент понадания и точность широко применяются при оцеике информации поисковыми системами, рассмотренными в главе 2 (раздел 2.7.3). В контексте построения томов коэффициент попадания и точность отражают противоречие между желанием предсказать большее число запросов зарапее и необходимостью избежать некорректных предсказаний. Например, чтобы достичь высокого коэффициента попадапия, серверу может потребоваться отправлять большее число рекомендаций. В свою очередь это ведет к снижению точиости, поскольку мпогие из рекомендаций могут оказаться бесполезными.

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

Подобные ограничения по времени могут быть учтепы путем назначения фиксированного интервала времени для каждой рекомендации. Предположим, ripo- кси-сервер получает рекомендацию относительно ресурса s. Если клиент запрашивает ресурс s в течение промежутка времени, не превышающего т секупд, рекомендация не будет полезной. Если клиент запрашивает ресурс 5 по истечении Гсекунд после выдачи рекомендации, где T > т, рекомендация не будет полезной. Другими словами, рекомендация будет полезна только для запросов, поступивших на интервале времени между т и Гсекунд после получения рекомендации прокси-сервером. Алгоритм построения томов формирует том vr для каждого ресурса r, где vr представляет собой набор ресурсов, посылаемых как рекомендации при запросе ресурса r. Применение этих томов к последовательности запросов приводит к различным зпачеииям показателей размера рекомендации, коэффициента попадания, точности и доли обновлений. Достижение баланса между четырьмя показателями предполагает несколько подходов к построению томов. Алгоритм может пытаться добиться максимума или минимизировать один из показателей с учетом ограничений на другие показатели. Например:

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

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

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

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

В первом алгоритме процесс начинается с целевого размера рекомендации и попыток предсказать как можно больше запросов. Для второго алгоритма, наоборот, процесс начинается с заданного коэффициента попадания, причем делаются попытки отправить как можно меньше рекомендаций с учетом установленного ограничения. Аналогично, последние два алгоритма предполагают достижение оптимального соотношения между точностью и коэффициентом попадания. Однако пи одна из этих задач оптимизации не имеет эффективного решения [CKR99], что заставляет искать эффективные эвристические алгоритмы.

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

Первая эвристическая процедура, рассмотренная в разделе 13.2.1, предлагает способ груннировки ресурсов, предполагающий совместное обращение ко всем этим ресурсам. Эвристика предполагает, что том vr должен содержать ресурс s, если вслед за запросом на r обычно следует запрос на s от того же самого клиента; запрос на s должен поступить не раньше т секунд, и не позже T секуид после запроса на r. Для ирииятия решения, включать ли s в vr, алгоритм подсчитывает число запросов на r, вслед за которыми следуют запросы на s. Это число делится на общее число запросов на ресурс r. Если полученное отношение превышает некоторое пороговое значение, то s включается в vr\ в противном случае эгого не происходит. В действительности алгоритм может подсчитать число запросов на каждый из ресурсов и интервалы между парами запросов, последовательно проанализировав журнал запросов сервера. Затем, после обработки журнала, алгоритм вычисляет отношения с целью определить, какие ресурсы включать в каждый из томов. Подобный подход был рассмотрен в исследованиях, посвященных упреждающей выборке в Web [PM96, Bes95, JK98].

Хотя алгоритм эффективен с точки зрения объема вычислений, подобный подход имеет две слабые стороны. Во-первых, оп требует наличия большого числа счетчиков, особеиио для Web-сайтов, имеющих тысячи уникальных ресурсов. Xpa- пепие этих счетчиков требует большого объема памяти. Введенные в базовый алгоритм усовершенствования могут уменьшить нагрузку. В частности, можно сфокусировать внимание на наиболее популярных ресурсах и не использовать счетчики для пар ресурсов, которые редко фигурируют вместе [CKR99]. Во-вторых, алгоритм включает в том некоторые ресурсы, которые не способны послужить основой для новых предсказаний. Если сервер совмещает рекомендации с каждым сообще- нием-ответом, прокси-сервер может получать множество рекомендаций для одного и того же ресурса. Это дополнительные рекомендации не предоставляют никакой повой информации. Удаление ресурса из одного или нескольких томов позволяет избежать создания этих лишних рекомендаций. Это сокращает размер рекомендации и способствует повышению точности. Удаление ресурса из тома повышает точность, поскольку позволяет избежать ситуаций, в которых рекомендация не предсказывает будущий запрос.

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

Исходный однопроходный алгоритм наименее сложен с вычислительной точки зрепия, но генерирует избыточные рекомендации. Двухпроходпый алгоритм удаляет неэффективные рекомендации, но требует дополнительных вычислительных затрат. Мпогопроходпый алгоритм создает очень эффективный набор рекомендаций, но требует еще больших вычислительных затрат. Чтобы найти паиболее выгодный режим, требуется осозиать, насколько более сложный алгоритм повышает эффективность и увеличивает время, необходимое для построения гомов. В некоторых случаях увеличение времени вычислений может не иметь Значения. Решение зависит от частоты формирования гомов, а также различий в эффективности и объеме вычислений для эгих трех алгоритмов. Кроме того, важпо осуществлять сравнение этих трех алгоритмов с более простыми подходами, например, с эвристическими процедурами, описанными в разделе 13.2.1, в которых ресурсы груннируются на основе структуры их URL. Эти важные проблемы не могут быть решены без оценки алгоритмов с учетом реальной работы серверов.

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