Пранскевичус Владислав Александрович

Реферат по теме выпускной работы

Разработка распределенного поискового робота

Содержание

1. Введение. Обоснование актуальности темы
2. Цели и задачи работы
3. Предполагаемая научная новизна и практическая ценность
4. Обзор существующих исследований и разработок по теме
5. Исследования
6. Выводы
7. Литература

1. Введение. Обоснование актуальности темы

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

2. Цели и задачи работы

Объектом исследования данной работы является распределенный поисковый робот. Основными задачами разработки поискового робота являются:

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

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

Для формализации архитектуры предлагается использовать π-исчисление [4], а для оценки – метрики, предложенные для веб-краулеров в [3]. Эти концепции описаны более подробно в следующих разделах.

3. Предполагаемая научная новизна и практическая ценность

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

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

4. Обзор существующих исследований и разработок по теме

4.1 Локальный обзор

• Шади Абу Рок: "Исследование свойств поисковых систем". В данной работе исследованы общие проблемы, решаемые современными поисковыми системами. Приведена математическая модель, которая может быть использована в т.ч. для поисковой оптимизации.

4.2 Национальный обзор

В национальном масштабе не было обнаружено активных исследований по теме поисковых роботов.

4.3 Глобальный обзор

Исследования в области поисковых роботов ведутся с самого момента зарождения Всемирной паутины. Можно выделить несколько основных направлений исследований:

• Архитектуры поисковых роботов [2, 3, 7];
• P2P поисковые роботы [3, 12];
• Фокусированные поисковые роботы [5];
• Политики выбора и обновления страниц в поисковых роботах [9];
• Политики вежливости.

В контексте данной работы, наиболее интересными являются исследования в области архитектур поисковых роботов и алгоритмов работы P2P систем.

Одной из наиболее цитируемых и фундаментальных работ в области поисковых роботов является статья Сергея Брина и Ларри Пейджа «The Anatomy of a Large-Scale Hypertextual Web Search Engine» [2], описывающая архитектуру Googlebot по состоянию на 1998 год. Несомненно, с тех пор Googlebot претерпел массу изменений, однако в связи с коммерческой природой Google открытых данных об этом нет.

В работе Junghoo Cho and Hector Garcia-Molina. «Parallel crawlers» [1] представлена классификация архитектур параллельных поисковых роботов и метрики, используемые для их оценки. Данная магистерская работа во многом базируется на этих исследованиях.

5. Исследования

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

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

Благодаря огромным объемам и гетерогенности Всемирной паутины, архитектура поискового робота и в частности политики параллелизма, заложенные в ней, являются интересным объектом исследований. На сегодняшний день ключевым моментом, определяющим производительность поискового робота является горизонтальная масштабируемость его архитектуры, т.е. свойство системы увеличивать производительность при добавлении новых узлов (компьютеров). Достаточно интересное исследование и попытка классификации различных архитектур параллельных поисковых роботов представлены в [1].

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

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

• Централизованные архитектуры — лежат в основе большинства используемых на сегодняшний день поисковых роботов. Эти архитектуры состоят из нескольких потенциально распределенных конкурентных компонентов, имеющих центральный пункт синхронизации(например, очередь задач или специальный компонент-координатор). Ярким примером поискового робота, имеющего централизованную архитектуру является Googlebot [2]. Обычно при использовании централизованной архитектуры применяется внутридоменная (intra-site) модель распределения (согласно классификации данной в [1]), при которой компоненты распределяются внутри одного локального окружения. Структурная схема поискового робота с централизованной архитектурой представлена на рис. 1.
  
  Рисунок 1: Централизованная архитектура поискового робота
• Децентрализованные или мультиагентные архитектуры — отличаются полной (или приближенной к полной) децентрализацией компонентов. Построение подобных систем требует несколько иных алгоритмов и методов, нежели тех, которые используются в централизованных архитектурах [8], поэтому их можно вынести в отдельный класс. Пример использования децентрализованной архитектуры приведен в [3].

На более низком уровне, архитектуры поисковых роботов могут отличаться методами распределения задач между компонентами, способами обмена URL и алгоритмом их распределения. Конфигурация конкретного поискового робота может варьироваться в зависимости от нужд использующего его приложения. Например, для минимизации объема загружаемых данных и оптимизации производительности веб-краулера могут использоваться отложенные вычисления в форме абстракций futures [5].

Для оценки поисковых роботов, можно использовать следующие метрики, предложенные в [1].

• Дублирование (overlap) — оценивает объем избыточно загруженных страниц и определяется по формуле:

  

  где N — общее количество загруженных страниц, I — количество уникальных страниц.
• Покрытие (coverage) — определяет объем страниц, которые должны были быть загружены, но благодаря специфике функций распределения адресов между агентами не были. Покрытие можно определить следующим соотношением:

  

  где I — количество уникальных страниц, U — общее количество страниц.
• Качество (quality) — для определения качества, предположим существование гипотетического предсказывающего робота (oracle crawler), которому заранее известно значение важности страницы по какой-либо метрике. Обозначим множество “интересных” страниц мощности N, загруженных предсказывающим роботом как PN , а аналогичное множество страниц, загруженных реальным роботом как AN. Исходя из этого, можно определить качество как:

  

Перечисленные выше метрики находятся в прямой зависимости от политик параллелизации, заложенных в архитектуре поискового робота, и имеют тенденцию ухудшаться при распределении конкурентных компонентов или увеличении их числа [1]. Этот факт явно показывает необходимость дальнейших исследований политик параллелизации.

Параллельный поисковый робот, по своей сути представляет собой образец системы с конкурентными вычислениями, и следовательно к нему могут быть применены математические методы и модели конкурентных вычислений. Одной из наиболее выразительных моделей конкурентных вычислений является π-исчисление [4]. Π-исчисление является Тьюринг-полной моделью вычислений и является мощным инструментов для формализации и исследования конкурентных процессов с комплексными взаимодействиями.

Базовое π-исчисление предлагает следующие примитивы для описания процессов:

• конкурентность, обозначается как P | Q, где P, Q — процессы;
• входной префикс, c(x).P определяет процесс P, ожидающий сообщения x, которое должно быть доставлено по каналу с;
• выходной префикс с(y).P, определяющий процесс P, осуществляющий отправку имени y по каналу с;
• создание нового имени, (υx)P создает локальное имя x в контексте процесса P.

В качестве примера определения процесса в терминах π-исчисления можно рассмотреть процесс Fetch, выполняющий непосредственную загрузку страницы по данному URL:

Данный процесс представляет собой абстракцию π-исчисления (т.е. параметризуется); URL в виде (s, p), где s — сервер, p — страница, принимается по каналу f, затем происходит запрос страницы с сервера с последующим ее получением по каналу с параметром data. Затем data передается по каналу store в хранилище.

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

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

Основными требованиями, выдвигаемыми к языку реализации являются:

• наличие высокоуровневых конструкций и средств для функциональной декомпозиции системы и создания необходимых абстракций;
• выразительность, близкая к формальному математическому описанию системы;
• наличие встроенных средств для описания конкурентных вычислений, позволяющих легко реализовать процессы системы и их взаимодействия;
• наличие качественных, поддерживаемых сообществом разработчиков библиотек, например для сетевых взаимодействий, протоколов обмена сообщениями, разбора HTML страниц, работы с СУБД и т. п.;
• открытость и общедоступность реализации языка и инструментов разработки.

С учетом выдвинутых требований, в качестве языка реализации был выбран язык программирования Haskell (http://www.haskell.org). Haskell относится к семейству языков ML и представляет собой чистый функциональный язык с отложенными вычислениями. Haskell обладает строгой статической типизацией с автоматическим выводом типов по модели Хиндли-Милнера, поддержкой алгебраических и рекурсивных типов данных, вызовом функции по образцу.

Определяющим фактором в выборе именно этого языка программирования стала его продвинутая реализация примитивов конкурентных вычислений (Concurrent Haskell), близкая по семантике к π-исчислению [6]. Примитивы Concurrent Haskell реализуют все основные операции π-исчисления, кроме недетерминированного выбора, который тем не менее может быть реализован в случае необходимости при помощи других примитивов.

6. Выводы

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

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

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

Литература

1. Cho J., Garcia-Molina H. Parallel crawlers // In Proc. of the 11th International World–Wide Web Conference – 2002. - 13 C.
2. Brin S., Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine // Computer Science Department, Stanford University, Stanford — 1998. - C. 107-117.
3. Boldi P., Codenotti B., Santini M., Vigna S. UbiCrawler: a scalable fully distributed Web crawler // Software: Practice and Experience – 2004. - C. 711-726.
4. Milner R. Communicating and Mobile Systems: the Pi-Calculus // Cambridge, UK: Cambridge University Press – 1999. - 162 C.
5. Пранскевичус В. А., Привалов М. В. Построение масштабируемого сфокусированного поискового робота с использованием принципа отложенных вычислений // Вестник ЛНТУ им. Шевченко – 2010. - С. 189-194.
6. Jones S. P. , Gordon A. , Finne S. Concurrent Haskell // Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages – 1996. - C. 295-308.
7. Shkapenyuk V., Suel T. Design and Implementation of a High-Performance Distributed Web Crawler // In Proc. of the Int. Conf. on Data Engineering – 2002. - C. 357-368.
8. Karger D., Leighton T., Lewin D., Sherman A. Web caching with consistent hashing // In Proc. of 8th International World–Wide Web Conference, Toronto, Canada – 1999. - C. 1203-1213.
9. Page L., Brin S., Motwani R., Winograd T. The PageRank Citation Ranking: Bringing Order to the Web // Stanford InfoLab – 1998. - 17 C.
10. Making AJAX Applications Crawlable – Full Specification [Электронный ресурс]. Режим доступа: URL: http://code.google.com/web/ajaxcrawling/docs/specification.html
11. Web Crawler – Wikipedia [Электронный ресурс]. Режим доступа: URL: http://en.wikipedia.org/wiki/Web_crawler
12. GRUB Web Crawler [Электронный ресурс]. Режим доступа: URL: http://grub.org/