В. А. Пранскевичус, М. В. Привалов

Построение масштабируемого сфокусированного поискового робота с использованием принципа отложенных вычислений

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

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

Задача построения эффективного поискового робота является довольно нетривиальной, по нескольки причинам:

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

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

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

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

На сегодняшний день поисковые роботы общего назначения, например, роботы всемирных поисковых систем (Googlebot [1], Yahoo! Slurp и др.), решают задачу сбора максимального объема полезной информации для последующего построения индекса, используемого при полнотекстовом поиске. Однако, на практике часто возникают задачи анализа таких общих характеристик веб-ресурса, как язык содержимого, категория веб-ресурса(например, блог, корпоративный портал, форум), технологий, использованных при разработке данного ресурса, его навигационной структуры и т. п. Использование конвенциональных архитектур поисковых роботов наподобие описанных в [1], [2] для решения таких задач неэффективно, т. к. для проведения анализа в большинстве случаев необходима только небольшая часть содержимого веб-ресурса. Классические техники, используемые в фокусированных поисковых роботах также неприменимы, т. к. основной задачей, решаемой такими роботами является получение веб-страниц определенной заданной тематики.

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

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

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

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

, (1)

где W — веб-ресурс, P_u — страница, расположенная по адресу(URL) u, U_w — множество URL веб-ресурса.

Ни одна из страниц P_u не будет загружена до тех пор, пока к ней не будет произведено обращение, т. е. страница представляет собой результат отложенной операции загрузки, “обещание” загрузить страницу при необходимости. В немного модифицированной нотации лямбда-исчисления это можно представить как

, (2)

где u — URL страницы, f — функция постановки страницы в очередь загрузок.

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

, (3)

где А — некоторая задача анализа.

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

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

Построенная система представляет собой набор взаимодействующих распределенных компонентов, которые при необходимости могут быть разнесены по разным серверам. Общий вид архитектуры поискового робота представлен на Рис. 1.

Рис. 1. Архитектура поискового робота

Центральным компонентом системы является компонент DataStorage, реализующий хранение веб-страниц и их отложенную загрузку. Этот компонент предоставляет удобные абстракции для работы с отложенно загружаемыми веб-страницами, обработки и анализа их содержимого.

Компонент Fetcher реализует непосредственную загрузку веб-страницы по заданному адресу и сохранение ее через DataStorage. Для получения заявок на загрузку используется специализированная приоритетная очередь Fetch queue; заявки в эту очередь помещает компонент DataStorage при вызове функции загрузки веб-страницы. В системе может быть несколько экземпляров компонента Fetcher, синхронно обрабатывающих очередь Fetch queue. Для удобства эти компоненты сгруппированы в динамический пул. Нотификации об успешной загрузке веб-страниц помещаются в FIFO-очередь Ready queue.

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

Для реализации отложенных вычислений естественным образом подходит высокоуровневый функциональный язык программирования. В данной работе был выбран язык Python 3, т. к. средства этого языка легко позволяют создать необходимую абстракцию веб-страницы, обладающую отложенным поведением, а стандартная библиотека предоставляет множество удобных инструментов для работы с сетевыми протоколами и примитивов построения распределенных систем. Очереди Fetch queue и Ready queue выполнены с использованием средств объектно-реляционной СУБД PostgreSQL 9.0. Для опроса состояния очередей используется механизм асинхронных нотификаций данной СУБД, а такие ее свойства, как постоянное хранение больших объемов данных и транзакционное поведение позволяют реализовать довольно надежные очереди, устойчивые к разного рода непредвиденным ситуациям. СУБД PostgreSQL также была использована для реализации хранилища веб-страниц DataStorage и для хранения данных аналитики. Содержимое веб-ресурсов сохраняется в файловое хранилище со специальной структурой директорий.

Для тестирования поискового робота были описаны несколько типов анализа веб-ресурса:

• анализ существования веб-сайта по заданному доменному имени;

• является ли расположенный по данному адресу веб-сайт заглушкой(т. е. не содержит полезной информации);

• анализ языка содержимого веб-сайта;

• анализ наличия поддоменов;

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

Описанные виды анализа были запущены для 1000 доменных имен из доменной зоны .ru. Анализ выполнялся на обычной рабочей станции с двухядерным ЦП, работающей под управлением ОС GNU/Linux и имеющей выход в интернет по симметричному каналу с пропускной способностью 10 Мбит/с. В тестовой конфигурации поискового робота было задействовано 8 компонентов-роботов и 4 компонента Fetcher.

При проведении данного эксперимента, были получены такие результаты:

Таблица 1

Экспериментальные данные анализа веб-ресурсов

Общее время исполнения	~ 20 мин.
Количество проанализированных доменов	1000
Количество загруженных страниц	4589
Среднее количество загруженных страниц/сайт	~ 4.5
Результирующий объем файлового хранилища данных	118 МБ
Количество сайтов-заглушек	92
Количество сайтов, имеющих поддомены(в т.ч. www)	715
Преобладающий язык	Русский
Количество мультиязычных ресурсов	112

Альтернативами рассмотренному в данной работе поисковому роботу могут служить приложения cURL(http://curl.haxx.se/) или wget(http://www.gnu.org/software/wget/). Wget в принципе является приложением, предназначенным для конечных пользователей и не предоставляет того уровня гибкости программирования, который необходим при использовании его в качестве полноценного поискового робота. cURL, а точнее библиотека его функций libcurl, предоставляющая API для программиста, может с какой-то степенью успешности выполнять роль поискового робота. Однако, ее использование в описанных выше задачах анализа веб-ресурсов связано с целым рядом неудобств и деградаций производительности, краткий перечень которых представлен ниже:

• неудобство программирования — довольно непросто создать удобную и эффективную абстракцию веб-ресурса для работы с веб-страницами, загружаемыми при помощи cURL. Это обстоятельство неизбежно ведет к усложнению логики компонентов-роботов.

• cURL не обладает полным набором функциональности, позволяющим работать с некоторыми несоответствующими стандартам веб-сайтами;

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

В результате исследований было установлено, что использование рассмотренного в данной работе поискового робота способно привести к значительному увеличению производительности(с точки зрения использования хранилища данных и пропускной способности сетевого канала) в задачах анализа веб-ресурсов.

Литература:

1. Sergey Brin, Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine // Computer Science Department, Stanford University, Stanford — 1998.

2. Vladislav Shkapenyuk and Torsten Suel. Design and Implementation of a High-Performance Distributed Web Crawler // Technical Report. - CIS Department, Polytechnic University, Brooklyn, NY - 2001.

3. Soumen Chakrabarti, Martin van den Berg, Byron Dom. Focused crawling: a new approach to topic-specific Web resource discovery // Elseveir Science B. V. - 1999.