ЭФФЕКТИВНЫЙ АЛГОРИТМ КЭШИРОВАНИЯ В КЭШИРУЮЩЕМ ПРОКСИ – СЕРВЕРЕ

 

Осадчиев А.А., Полухин Д.П.

 

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

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

 

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

 

От 30 до 60% всех НТТР- и FTP-запросов в Интернет это повторяющиеся запросы пользователей, которым нужна информация, уже проходившая через Интернет-шлюз их компании. Идея кэширования с помощью proxy серверов заключается в том, чтобы сохранять наиболее часто запрашиваемые данные и таким образом свести объем трафика к минимуму.

        

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

 

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

 

Алгоритм кэширования

 

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

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

Впервые полученные документы всегда помещаются в кэш (они заменяют более старые версии, если такие имеются). Так как дисковое пространство ограничено то, когда нет свободного места на дисковом массиве, чтобы вставить новый документ, необходимо очистить кэш. В этом случае, верхняя граница размера кэша определена параметром «верхний уровень воды». Текущий размер кэша обозначен параметром «текущий уровень воды». Во время очистки кэша документы удаляются до тех пор, пока размер кэша не станет ниже параметра «нижний уровень воды». «Верхний и нижний уровень воды» могут быть изменены пользователем.

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

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

Величина индекса, которым помечается документ зависит от сочетания следующих факторов:

 

1. Оценка времени соединения с удалённым сервером (Clat_server(i)).

2. Оценка пропускной способности соединения  с удалённым сервером (Cbw_{server (i)}).

3. Размер документа (s_i).

4. Частота обращений к документу (Fref_i).

 

Первые два фактора - оценки, основанные на времени соединения и пропускной способности соединения, измеренные в течение прошлых соединений с удалённым сервером, сохранённые и обработанные объектом «база данных серверов» регистрирующим данную информацию. Всякий раз, когда происходит получение  нового документ с удалённого сервера, измеряется время соединения и пропускная способность (время передачи / размер) для этого документа (обозначаются sclat и scbw соответственно) и обновляются оценки факторов следующим образом:

Clat_server(i) = (1-Alpha) × Clat_server(i) + Alpha × sclat

Cbw_server(i) = (1- Alpha) × Cbw_server(i) + Alpha × scbw

Где Alpha - коэффициент сглаживания, по умолчанию равен 1/8. Значение Alpha может быть изменено пользователем.

 

Необходимо отметить, что статистика по удалённому серверу формируется исходя из статистики документов этого сервера. Это устраняет проблему более низкой значимости пропускной способности для малых документов, чем пропускной способности для больших документов на том же самом сервере. Удалённый сервер, как ожидается, содержит набор документов различных размеров, так что, на измеряемую пропускную способность для всех серверов, как ожидается,  в равной степени повлияет вышеупомянутое явление.

 

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

 

Результирующая функция формирования значения индекса значимости документа объединяет в себе все четыре фактора и будет выглядеть следующим образом:

( W_Clat × Clat_{server (i)} + W_Cbw / Cb_{Wserver (i)}) × ( Fref_i ^ W_Fref) / (s_i ^ Ws_i)

 

Где W_Clat, W_Cbw, W_Fref и W_si - настраиваемые веса  значимости факторов.

 

Алгоритм очистки предпочитает удалять документы с более низким значением индексов. Следовательно, документ, вряд ли  будет удалён, если значение индекса относительно велико, что возможно, если документ находится на сервере, время соединения с которым велико (то есть большой Clat_server(i)) и пропускная способность соединения мала (то есть мал Cbw_server(i)), и при этом документ часто вызывался (то есть большой Fref_i), и размер документа мал (то есть мал s_i).

Литература

1.     Terry William Ogletree. “Practical Firewalls”, published by QUE , 2000.

2.     Brian Tiemann,Michael C. Urban “FreeBSD”, published by SAMS , 2002.