Сравнение дельта-алгоритмов

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

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

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

•   Размер разности.

•   Частота изменения ресурса.

Указанные факторы не обязательно приводят к однозначному выбору алгоритма вычисления разности. Например, алгоритм, который способен быстро вычислять разиость, может выдавать разность большого размера, жертвуя объемом дан- иых ради скорости. Такой алгоритм менее полезен для ресурсов, которые часто изменяются. Подобные обстоятельства привели к использованию алгоритмами вычисления текстовой разности, такими как Revision Control System (RCS) [Tic85] и Source Code Control System (SCCS) [Roc75], принципа опережающей разности. Опережающая разность накапливает разности по сравнению с последней версией. Разности хранятся вместе, что позволяет приложению быстро создать любую версию. При рассмотрении второго фактора следует помнить, что объем информации увеличивается медленно от версии к версии, на любом этапе разность между двумя ближайшими версиями Обычно невелика. Главное наблюдение состоит в том, что в зависимости от приложения, величина разности между версиями и суммарная разность могут оказаться различными для различных алгоритмов. Третий фактор учитывает, что не все типы ресурсов изменяются с одинаковой частотой. Например, текстовые ресурсы изменяются чаще изображений [DFKM97].

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

МЕТОДОЛОГИЯ ИССЛЕДОВАНИЯ

Чтобы оценить алгоритмы вычисления разности на предмет их применения в Web, при проведении исследования следует учитывать следующие методологические соображения:

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

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

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

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

•    Частота, с которой изменяются ресурсы.

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

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

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

Теперь мы представим краткий отчет об исследовании, который впервые был опубликован в [MDFK97a], а более подробный отчет можно найти в [MDFK97bJ. Исследование проводилось несколько лет назад, но единственный основной фактор, который с тех пор мог подвергнуться изменениям, — это состав трафика (меньше текстовых документов, больше динамических ответов и больше изображений в различных форматах). Никаких значительных изменений, связанных с ускорением вычисления разности или с алгоритмами сжатия, не произошло.

Главным отличием этого исследования от проводившихся рапее (например, [HL96J), было использование потока реальных запросов и ответов в Web, вместо выбора коллекции документов и рассмотрения возможности применения к ним методов вычисления разности. Исследование начинается с рассмотрения, какие ресурсы выбраны путем просмотра журналов прокси-серверов и трасс пакетов. В ходе исследования было отобрано два набора ресурсов из двух различных мест, расположенных в США. Один источник данных представлял собой корпоративный прокси-сервер. Прокси-сервер отслеживал все исходящие запросы. В течение всего двух дней было записано достаточно много данных (около 9 гигабайтов, составивших примерно полмиллиона трасс примерно 8000 различных клиентов). Второй источник представлял собой трассы мониторинга пакетов исследовательской орга- пизации. Было записано 19 гигабайтов данных в течение 17 дней, что составило около миллиона трасс примерно 7500 клиентов. Трассировка пакетов перехватывает данные на низком уровне и реконструирует их в запросы и ответы HTTP, как говорилось в главе 14 (раздел 14.1). Множество ресурсов для оценки дельта-мех- низма было выбрано из этих двух наборов.

Для определения полезности дельта-механизма должны анализироваться только запросы на ресурсы, которые изменялись в период проведения тестирования. Идентифицировались ответы для одного и того же ресурса, имеющие код статуса 200 OK для более чем одного экземпляра, а значения в заголовке ответа Last- Modified использовались для определения, были ли ресурсы изменены. После того, как такие пары экземпляров были выявлены, к каждой паре применялись различные мехаиизмы вычисления разности, чтобы определить величину разиости второго экземпляра относительно первого. Если подходящий дельта-мехаиизм имелся, исходный сервер отправлял соответствующий код. Такие пары экземпляров называются делъта-приемлемъши.

В ходе исследования изучались три различных алгоритма кодирования разности с учетом их популярности и доступности. Первый из них заключается в использовании команды UNIX diff с опцией ~e для построения сценария, который может быть применен на другой стороне к первому экземпляру ресурса для воссоздания второго экземпляра. Второй алгоритм состоит в сжатии выходного результата команды diff ~e с помощью программы gzip для уменьшения размера разности. Третий метод использует иовый алгоритм вычисления разиости иод названием vdelta (позднее переименованный в acc^[KV00]), который не только находит разность между экземплярами, но и осуществляет сжатие полученной разности.

Ряд ресурсов был исключен из рассмотрения, поскольку их тины содержания плохо подходили для вычисления разности. Например, изображения GIF и JPEG уже являются предварительно сжатыми, и вычисление разиости для них прииесет мало пользы. Программы, подобные diff предназначены только для текстовых ресурсов и не будут работать с двоичными ресурсами. В то же время алгоритм vcdiff работает со любыми форматами данных, иоэтому он использовался в исследовании для всех ресурсов, включая изображения.

РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ

Здесь мы вкратце подытожим результаты исследования. Показатель дель- та-приемлемости позволяет оценить полезность дельта-механизма в целом. Около 38% ресурсов в исследуемых трассах прокси-сервера оказались дельта-приемлемыми, в то время как только около 10% ресурсов оказались дельта-приемлемыми в трассах пакетов. Главная причина такого различия заключается в том, что при исследовании трасс прокси-сервера исключалось несколько типов содержания — главным образом нетекстовые типы, такие как GIF,JPEG, MPEG и аудиоформаты. При более широком исследовании никакие форматы не исключались, а данные собирались в различных местах, чтобы гарантировать репрезентативность распределения типов содержания, имеющихся в Web.

Были рассчитаны две Группы показателей: количество байтов, которое будет сэкономлено, если передавать только разности между экземплярами, и примерная экономия времени, которая достигается за счет отказа от извлечения полного ответа. При подсчете экономии в исследовании не учитывались затраты на кодирование (и декодирование) разиости. Поскольку разность вычисляется только при появлении изменений, затраты на кодирование и декодирование малы, если раскладываются на все содержание.

Исследование показало, что около 30% объема полных ответов, имеющих тела, не будут отправляться, если в качестве механизма кодирования разности используется vcdiff. Если получатель уже имел кэшированную копию предыдущего экземпляра, 83% объема тел ответов нет необходимости передавать. В ходе исследования также были определены затраты на вычисление разности и применение дельта-механизма к предыдущему экземпляру. Кроме того, исследование показало, что из всех протестированных алгоритмов vcdiff в большинстве случаев дал наилучший результат.

Один из результатов состоял в том, что библиотечная реализация (что является наиболее вероятным способом реализации вычисления разности для реальных Web-серверов) vcdiff работает с производительностью линии Т-1 (193 Кб/с). Таким образом, все пользователи, пропускные способности соединений которых меньше или равны пропускной способности линии Т-1, могут получить преимущество от кодирования разности и сжатия. Исследование подтвердило, что vcdiff является наиболее эффективным (с точки зрения затрат времеии) для кодирования разности и сжатия. Исследование также показало, что кодирование разности и сжатие предпочтительнее сжатия, реализуемого современными модемами, особенно для больших файлов.

В результате исследования был сделан вывод, что широкое применение дель- та-механизма может привести к значительному сокращению объема данных, передаваемых в Web, не увеличивая время ожидания при вычислении разности и воссоздании ответов. Применительно к трассам прокси-сервера исследование показало, что объем передаваемых данных ответа может быть сокращен почти на треть, а время передачи ответов, подвергнутых вычислению разиости, сокращено почти на 40%. Для трасс пакетов с разнообразными типами содержания (нетекстовые типы не игнорировались) может быть достигнут очень большой выигрыш в объеме передаваемых данных (около 85%), если ресурсы дельта-приемлемы. Однако включение всех типов содержания снижает общую эффективность примерно на 9%. В результате исследования делается вывод, что дельта-приемлемые ответы должны подвергаться дельта-кодированию, а для других следует осуществлять лишь сжатие, чтобы по крайней мере уменьшить объем данных, передаваемых по сети.

ДРУГИЕ СООБРАЖЕНИЯ, СВЯЗАННЫЕ С ДЕЛЬТА-МЕХАНИЗМОМ

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

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