Алгоритм LRU наконец-то превзойден

Сергей Кузнецов

Обзор апрельского, 2004 г. номера журнала Computer (IEEE Computer Society, V. 37, No 4, April 2004)

Авторская редакция.
Также обзор опубликован в журнале "Открытые системы", #05/2004

На обложке журнала тема апрельского номера обозначена как "Putting the Web to Work" (что-то вроде "Приведения Web в действие"). В действительности с Web связаны только три из шести больших статей, и тематика этих трех статей очень неоднородна. Тем не менее, начнем обзор именно с них.

Первая статья называется "Инфраструктура программного обеспечения для аутентифицируемого снятия показаний в Web" ("A Software Infrastructure for Authenticated Web Metering"). Авторы статьи - Карло Блундо и Стельвио Кимато (Carlo Blundo, Stelvio Cimato, carblu|cimato@dia.unisa.it, University of Salerno). Объем рекламы, размещаемой на Web-сайтах, постоянно растет. По данным Бюро интерактивной рекламы (Interactive Advertising Bureau) в последние 6 месяцев 2002 г. на Internet-рекламу в США было истрачено почти 3 миллиарда долларов. Развитие рекламной деятельности в Internet ограничивается тем, что в этом случае рекламодатели не могут полагаться на схемы оценки рейтингов, которые традиционно используются, например, в телевизионной рекламе. Требуются надежные и эффективные методы, обеспечивающих данные о числе посещений разными пользователями Web-страниц, на которых размещена реклама. При этом нужно, чтобы на стороне Web-сервера была исключена возможность завышения размеров этих показателей и обеспечивалось средства доказательства их истинности. Авторы анализируют методы, используемые в настоящее время, и показывают их ограниченность. Предлагаемая схема выглядит следующим образом. В ней участвуют три стороны: клиент (C), желающий иметь доступ к некоторым Web-страницам; Web-сервер (S), обеспечивающий доступ к этим страницам и специальная Web-служба, аудиторское агентство (AA). C, S и AA используют общую хэш-функцию H. Для получения доступа (k раз) к желаемым страницам Web-сайта (регистрации) C обращается к AA. AA генерирует идентификатор К (idc), выбирает случайное значение w0 и применяет к w0 хэш-функцию H k раз, получая значение wk. После этого AA посылает C кортеж (idc, k, w0), а S - кортеж (idc, wk). S запоминает эти данные и ассоциирует с ними счетчик числа обращений Lc, инициируемый нулем. Далее C k раз обращается к соответствующим страницам Web-сайта. При i-том обращении на стороне C формируется метка вида (idc, wk-i), где wj = H(wj-1) (j = 1, :, k). При i-том обращении S проверяет законность idc, проверяет, что wk-i+1 действительно равняется H(wk-i) и увеличивает Lc на единицу. После обработки k-того обращения S посылает AA кортеж (idc, k, w0) в качества доказательства того, что данный клиент действительно обратился к соответствующим страницам k раз. Авторы показывают, что их метод лишен недостатков используемых методов и описывают реализацию прототипа в среде Linux с использованием Netscape Navigator 4.76 и Apache Web Server 1.3.19.

У следующей статьи пять авторов (все из университетов штата Луизиана). Первый в списке - Сантош Рангараджан (Santosh K. Rangarajan, , santosh_kumarr@hotmail.com, Louisiana Tech. University). Название статьи - "Кластеризация пользователей Web с использованием адаптивных нейронных сетей" ("Adaptive Neural Network Clustering of Web Users"). От уровня персонализации сервисов, предоставляемых пользователям Web-сайта, во многом зависит популярность сайта. В поддерживаемых Web-серверами журналах имеются содержательные данные, характеризующие паттерны доступа пользователей. Однако реструктуризация сайта с учетом индивидуальных интересов пользователей вызывает слишком большие расходы. Одно из возможных компромиссных решений состоит в выявлении групп пользователей с близкими интересами и организация структуры сайта в соответствии с потребностями разных групп. Это часть сравнительно новой области исследований, называемой Web Usage Mining. Авторы разработали алгоритм кластеризации, группирующий пользователей в соответствии с их паттернами доступа к Web-сайту. Алгоритм основан на варианте ART1 теории адаптивного резонанса (adaptive resonance theory, см. www.cs.brandeis.edu/~cs113/docs/other/heins_tauritz.pdf). ART1 обеспечивает подход, адаптирующийся к изменениям в изменении паттернов доступа пользователей без потери ранее накопленной информации. Алгоритм применяется к двоичным векторам, строящимся на основе URL, к которым наиболее часто обращаются члены группы пользователей. Авторы утверждают, что эффективность их алгоритма превышает эффективность традиционных алгоритмов кластеризации. Кроме того, разработана схема, предсказывающая будущие запросы пользователей. Точность предсказания составила 97,78%.

Последняя статья, которую редакция журнала Computer отнесла к тематической подборке, называется "Основанная на XML спецификация безопасности документов Web-сервисов" ("XML-Based Specification for Web Services Security"). Статью написали Рэфей Бхатти, Элиза Бертино, Ариф Гхафур (Rafae Bhatti, rafae@purdue.edu, Elisa Bertino, bertino@cs.purdue.edu, Arif Ghafoor, ghafoor@ecn.purdue.edu) и Джеймс Йоши (James B.D. Joshi, jjoshi@mail.sis.pitt.edu, University of Pittsburgh). Название статьи не вполне точно отражает ее содержание. На самом деле, речь идет о механизме контроля доступа к документам, доступ к которым осуществляется через Web-сервисы. Авторы развивают подход, основанный на модели RBAC (Role-Based Access Control - контроль доступа на основе ролей). Подход авторов состоит в дополнении существующих механизмов обеспечения безопасности средствами спецификации политики контроля доступа. При сохранении общей семантики RBAC вводятся расширения, включающие понятия иерархии ролей и разделения ограничений режима. Спецификация доступа к контенту допускается на концептуальном уровне, а также уровнях схемы, экземпляра и элемента документа (имеется в виду, что все документы представлены на языке XML). В модели авторов при проверке правомочности доступа также учитывается контект, к котором осуществляется попытка доступа. В общих чертах описывается основанный на XML язык спецификации политики доступа в терминах мандатов пользователей, ролей и разрешений. В заключение статьи обсуждается общая архитектура программного обеспечения, основанного на предложенной модели. Отмечается наличие опытной реализации.

Перейдем к другим статьям апрельского номера журнала. Бо Санден (Bo Sanden, bsanden@acm.org, Colorado Technical University) представил статью "Сражение с нитями Java" ("Coping with Java Threads"). Эта статья является хорошим кратким введением в механизм нитей языка Java. В основном автор концентрируется на механизмах синхронизации нитей. Описывается действие механизма взаимного исключения нитей (synchronized) и механизма синхронизации по условию (wait). Рассматриваются соответствующие синтаксические конструкции. Наконец, обсуждаются типичные ситуации, в которых наиболее часто возникают ошибки синхронизации. Наверное, эта статья может быть действительно полезна для программистов, которые впервые столкнулись с параллельным именно в среде Java.

У следующей статьи - "Извлечение знаний из данных о преступлениях: общий каркас и некоторые примеры" (Crime Data Mining: A General Framework and Some Examples" - опять много авторов (пять). Поэтому мы снова укажем только первого в списке - это Хсинчун Чен (Hsinchun Chen, hchen@eller.arizona.edu, University of Arizona). В статье представлена общая схема системы извлечения знаний из данных о преступлениях, которая разрабатывалась исследователями Аризонского университета в проекте Coplink с 1997 г. (http://ai.bpa.arizona.edu/coplink). В проекте использовались методы идентификации объектов на основе паттернов (entity extraction), выявления ассоциативных правил, предсказания, визуализации паттернов и т.д. Работа опиралась на классификационную базу данных о преступлениях полицейского управления г. Таксон. Описываются три примера реального использования системы.

Последнюю статью этого номера написали Нимрод Мегиддо и Дхармендра Модха (Nimrod Megiddo, Dharmendra S. Modha, megiddo|dmodha@almaden.ibm.com, IBM Almaden Research Center). Статья называется "Адаптивный алгоритм замещения кэша с результатами, лучшими, чем у LRU" "Outperforming LRU with an Adaptive Replacement Cache Algorithm"). Предыдущие попытки внедрения алгоритмов, обеспечивающих результаты, лучшие, чем у алгоритма LRU (Least Recently Used), не удавались по причинам больших накладных расходов и потребности в предварительной настройке. Разработанный авторами адаптивный алгоритм замещения кэша (Adaptive Replacement Cache - ARC) превосходит LRU и лишен этих недостатков. Алгоритм предполагает поддержку двух списков страниц - L1 и L2. Максимальная длина обоих списков составляет 2c, где c - размер кэша в страницах. Оба списка формируются в стиле LRU. При перемещении в кэш страницы, номер которой отсутствует в обоих списках, этот номер заносится в начало списка L1. При обращении к странице, номер которой фигурирует в одном из списков, этот номер переносится в начало списка L2. Важной особенностью алгоритма является то, что только в начале каждого из списков (подсписках T1 и T2)находятся номера страниц, находящихся в кэше, т.е. поддерживается история страниц, недавно вытесненных из кэша. Страница для замещения выбирается из конца списка T1 или T2 в зависимости от значения параметра p, определяющего текущую допустимую длину списка T1 (а тем самым, и длину T2). Адаптивность алгоритма состоит в том, что значение p изменяется в зависимости от вида рабочей нагрузки. Приводимые результаты экспериментов убедительно показывают преимущества алгоритма ARC перед рядом других известных алгоритмов.

Тем, кто еще не вступил в IEEE Computer Society в 2004 г., напоминаю, что сейчас самое время оформить подписку на второе полугодие. Рекомендую сделать это, Сергей Кузнецов, kuzloc@ispras.ru