info

Опыт внедрения поискового движка в веб-проект

Presentation mode
head
Тихонов Александр
Научный руководитель: Стучилин В.В.

Введение

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

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

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

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

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

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

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

Lucene

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

lucene logo

Sphinx

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

Sphinx logo

DataparkSearch Engine

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

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

PostgreSQL tsearch2

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

  • поддержка БД практически неограниченного размера;
  • мощные и надёжные механизмы транзакций и репликации;
  • расширяемая система встроенных языков программирования: в стандартной поставке поддерживаются PL/pgSQL, PL/Perl, PL/Python и PL/Tcl;
  • наследование;
  • легкая расширяемость.

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

PostgreSQL logo

Выбор

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

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

Поиск в PostgreSQL

Операторы поиска

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

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

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

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

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

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

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

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

GIN индекс

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

GiST индекс

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

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

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

Создадим тестовую таблицу fts_test

сreate table fts_test(
	id serial not null,
	content VARCHAR,
	fts tsvector,
	primary key (id)
)

Затем вставим туда 5 миллионов записей со случайными предложениями на русском языке:

insert into fts_test (content) values (?)

Создадим колонку для вектора текста и запишем его туда для каждой строки:

disarmer=> UPDATE fts_test SET fts=setweight(coalesce(to_tsvector('russian',content),''),'A');
UPDATE 5000000
Time: 142519,580 ms

Произведем поиск в таблице по полю с вектором:

disarmer=> select content,ts_rank('{1,1,1,1}', fts, q) as rank FROM fts_test , plainto_tsquery('russian','тест') as q where fts @@ q order by rank desc limit 50;
Time: 1850,480 ms

Таким образом, мы видим что поиск работает и без использования индексов.

Производительность GIST индекса

Создадим GIST индекс по полю с вектором текста:

disarmer=> CREATE INDEX fts_test_idx ON fts_test USING gist(fts);
CREATE INDEX
Time: 287301,764 ms

Снова произведем поиск в таблице с индексом:

disarmer=> select content,ts_rank('{1,1,1,1}', fts, q) as rank FROM fts_test , plainto_tsquery('russian','тест') as q where fts @@ q order by rank desc limit 50;
Time: 233,980 ms

Здесь видно что время поиска в индексированной таблице снизилось 7.9 раз.

Производительность GIN индекса

Создадим GIN индекс по полю с вектором текста:

disarmer=> CREATE INDEX fts_test_idx ON fts_test USING gin(fts);
CREATE INDEX
Time: 66818,478 ms

Снова произведем поиск в таблице с индексом:

disarmer=> select content,ts_rank('{1,1,1,1}', fts, q) as rank FROM fts_test , plainto_tsquery('russian','тест') as q where fts @@ q order by rank desc limit 50;
Time: 42,255 ms

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

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

  • создание индекса - GIN требует в 3 раза больше времени чем GiST;
  • размер индекса - GiN-индекс в 2-3 раза больше GiST-индекса;
  • время поиска - GiN-индекс в 3 раза быстрее, чем GiST-индекс;
  • обновление индекса - GiN-индекс обновляется в 10 раз медленнее.

Размеры таблиц


    tablename     |    data    |   total
------------------+------------+------------
 fts_test         | 573 MB     | 680 MB
 fts_test_vector  | 1082 MB    | 1190 MB
 fts_test_indexed | 1089 MB    | 1440 MB

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

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

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

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

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

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

Пример индексации

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

idhreftitleheaderskeywordscontentfts
2/ln/disarmer.ru | Сокращатель ссылокСокращатель ссылоксокращатель ссылок,ссылка,скинуть ссылкуСокращатель ссылок Сокращатель ссылок http:// Своя метка:'disarmer.ru':1A,11 'метк':17 'сво':16 'скинут':9C 'сокращател':2A,4B,6C,12,14 'ссылк':8C,10C 'ссылок':3A,5B,7C,13,15

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

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

Реализация интерфейса

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

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

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

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

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

Внутренние механизмы замера времени генерации страницы показывают следующие результаты:

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

Вывод

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