Разработка поисковой системы

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

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

Определение задачи

Согласно ГОСТ 7.73-96 СИБИД "Поиск и распространение информации. Термины и определения":  полнотекстовый поиск:

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

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

Первые версии программ полнотекстового поиска предполагали сканирование всего содержимого всех документов в поиске заданного слова или фразы. При использовании такой технологии поиск занимал очень много времени (в зависимости от размера базы), а в интернете был бы невыполним. Современные алгоритмы заранее формируют для поиска так называемый полнотекстовый индекс — словарь, в котором перечислены все слова и указано, в каких местах они встречаются. При наличии такого индекса достаточно осуществить поиск нужных слов в нём и тогда сразу же будет получен список документов, в которых они встречаются.

Существующие решения

В настоящее время существует несколько вариантов реализации системы полнотекстового поиска. Рассмотрим наиболее распространенные из них:

Lucene

The Apache Lucene — это свободная библиотека для высокоскоростного полнотекстового поиска, написанная на Java. Может быть использована для поиска в интернете и других областях компьютерной лингвистики (аналитическая философия).

Sphinx

Sphinx (англ. SQL Phrase Index) — система полнотекстового поиска, распространяемая по лицензии GNU GPL. Отличительной особенностью является высокая скорость индексации и поиска, а так же интеграция с существующими СУБД и API для распространённых языков веб-програмирования.

DataparkSearch Engine

DataparkSearch Engine — поисковая машина с открытым исходным текстом, написанная на языке С. Распространяется по лицензии GNU GPL. Предназначена для организации поиска на одном или многих веб-серверах.

PostgreSQL tsearch2

PostgreSQL — свободная объектно-реляционная система управления базами данных (СУБД)[2]. Сильными сторонами PostgreSQL считаются:

^А поддержка БД практически неограниченного размера;

^ мощные и надёжные механизмы транзакций и репликации;

^ расширяемая система встроенных языков программирования;

^ наследование;

^ легкая расширяемость.

tsearch2 — расширение PostgreSQL для реализации полнотекстового поиска. Ранее был выполнен в виде отдельного модуля, начиная с версии 8.3 был интегрирован в ядро СУБД.

Выбор

После обзора существующих технологий был выбран вариант на tsearch2. Этому послужили следующие причины:

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

^ Более гибкая настройка индексирования и поиска;

^А Существующий опыт и инструменты работы с PostgreSQL;

^А Возможность написания расширенных функций на PL/Perl;

^А Возможность использования произвольных словарей;

^А Сайт уже использует PostgreSQL в качестве основной базы данных.

Поиск в PostgreSQL

Как и многие современные СУБД, PostgreSQL имеет встроенный механизм полнотекстового поиска[2]. Отметим, что операторы поиска по текстовым данных существовали очень давно, это операторы LIKE, ILIKE, ~, ~*. Однако, они не годились для эффективного полнотекстового поиска, так как:

^А у них не было лингвистической поддержки;

^А они не предоставляют никакой информации для ранжирования документов, что делает такой поиск практически бесполезным;

^А они очень медленные из-за того, что они каждый раз просматривают весь документ и не имеют индексной поддержки.

Полнотекстовый поиск

Для улучшения ситуации два русских разработчика, Олег Бартунов и Федор Сигаев, предложили и реализовали новый полнотекстовый поиск[3], существовавший как модуль расширения и интегрированный в PostgreSQL, начиная с версии 8.3.

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

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

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

(важности), которая потом может использоваться для вычисления ранжирующей информации.

Для эффективной работы с такими многомерными данными PostgreSQL предлагает два типа индекса: GIST (Generalized Search Tree) и GIN (Generalized Inverted Index).

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

В тоже время, GIST индекс является "прямым" индексом, т.е. для каждого документа ставится в соответствие битовая сигнатура, в которой содержится информация о всех лексемах, которые содержаться в этом документе, поэтому добавление нового документа приводит к добавлению только одной сигнатуры.

GIST был предложен как обобщение нескольких классов индексов (такие как B-Tree, R-Tree, Similarity Tree, RD-Tree) и позволяет создавать индексы на базе произвольной метрики типа данных. Для использования GIST разработчик должен создать метрику и функции-адаптеры, используя API. Как классический индекс, в котором храниться одна и только одна пара ключ-ссылка, индексы GIST имеют хорошею производительность при вставке нового ключа, но производительность при поиске может сильно зависеть от метрики проиндексированного типа данных и собственно типа поискового запроса[5].

По результатам сравнения производительности индексов было выяснено что время поиска в таблице с индексом GIN снизилось почти в 44 раза по сравнению с поиском без использования индексов и в 5,5 раз по сравнению с индексом GIST.

Сравнение индексов

Для определения области применения каждого из индексов необходимо знать их основные различия[4]:

• ^А создание индекса - GIN требует в 3 раза больше времени чем GIST;

• ^А размер индекса - GIN-индекс в 2-3 раза больше GIST-индекса;

• ^Л время поиска - GIN-индекс в 3 раза быстрее, чем GIST-индекс;

• ^Л обновление индекса - GIN-индекс обновляется в 10 раз медленнее.

Индексация страниц

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

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

Реализация паука

В соответсвии с перечисленными требованиями был реализован синхронный http-паук с помощью языка perl. Для загрузки документов используется модуль LWP::RobotUA, полностью поддерживающий обработку файла robots.txt и совместимый со стандартным способом загрузки. Для разбора документов html используется парсер XML::Twig. Для повышения эффективности заполнения базы данных все запросы заключены в одну транзакцию, колонка поискового вектора заполняется после записи всех данных и индекс строится в групповом режиме.

В результате мы имеем колонку поискового вектора, по которой будем производить поиск. По ней построен индекс GIN для ускорения поиска. Эта колонка имеет 4 группы элементов(Название документа, заголоки, ключевые слова, текст) для динамического управления весом элементов. То есть такая конфигурация позволяет производить поиск с заданной важностью элементов страницы(например поиск только в заголовках и ключевых словах).

Web-интерфейс поиска

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

В результате был создан интерфейс к поиску. В соответствии с используемыми на сайте технологиями страница поиска выполнена в виде подгружаемой функции для сервера на perl, соединенного с frontend сервером по протоколу fastcgi. Преимущества этого подхода:

В качестве frontend используется web-сервер nginx(один из самый эффективных в высоконагруженных проектах). Он используется для отдачи статических файлов и связи с backend сервером, используемым для генерации динамического контента. Также он используется для кеширования ответов backend сервера.

В отличии от протокола cgi, fastcgi позволяет использовать постоянно запущенный процесс, а не запускать его при каждом запросе. Это значительно повышает производительность и снижает время ответа.

В качестве backend может быть запущено несколько копий сервера на одном порту, либо можно указать несколько портов. Также backend и frontend могут находиться на разных физических серверах. Это позволяет гибко масштабировать архитектуру системы.

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

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

Тестирование производительности

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

Внутренние механизмы замера времени генерации страницы представлены в табл. 1:

Таблица 1.

Номер запроса	Форма поиска	Выдача результатов	Безрезультатный запроc
Первый запрос	1,411 мс	24,886 мс	6,786 мс
Следующие запросы	0,383 мс	18,443 мс	1,506 мс
Запросы из кеша	Страница не генерируется, а возвращается из кеша, время на порядок меньше

По результатам теста максимальное время отклика не превышает 30 мс. Это время практически не заметно для пользователя и не препятствует комфортному взаимодействию.

Вывод

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