РАЗРАБОТКА МОДУЛЯ УПРАВЛЕНИЯ ОЧЕРЕДЬЮ ИНДЕКСАЦИИ ПОИСКОВОГО РОБОТА

Введение:

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

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

Так как количество страниц достаточно велико (от десятков тысяч до миллионов страниц) [1], весь процесс занимает долгое время. Очевидно, для актуализации содержимого в базе, время от времени необходимо перезапускать кроулер на том же наборе страниц.

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

Основная часть:

1. Описание приложения

Само приложение для индексации реализовано на Node.js (название модуля – simplecrawler [3]) – событийно-ориентированный поисковый робот обхода страниц. Этот модуль использует собственную очередь индексации, реализующую интерфейс управления очередью FetchQueue. Проблема в том, что эта очередь хранится в оперативной памяти в том же процессе, в котором запускается поисковый робот, а, значит, она не может быть доступна нескольким роботам, запущенным параллельно. Но архитектура приложения сформирована так, что используемую очередь легко изменить при инициализации робота. Поэтому и было решено реализовать модуль, который мог бы использоваться кроулером, при этом других изменений в исходный код кроулера вносить не нужно.

В качестве внешнего хранилища очереди объектов было решено использовать MongoDB [2], так как она удовлетворяет необходимым требованиям: работа с JSON, поддержка атомарных операций, агрегирующие функции, наличие официального клиента для Node.js.

2. Интерфейс очереди

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

• Добавить элемент в очередь;
• Проверить элемент на существование в очереди по URL;
• Извлечь элемент по индексу;
• Обновить элемент по индексу;
• Извлечь следующий непроиндексированный элемент;
• Агрегирующие функции для мониторинга статистики (кол-во элементов, кол-во проиндексированных элементов).

Рисунок 1. Программная архитектура модуля

На Рисунке 1 представлена программная архитектура модуля, реализующего интерфейс очереди индексирования FetchQueue [3]. Как уже было сказано выше, модуль должен реализовывать функции добавления и изменения элементов очереди, извлечения следующего непроиндексированного элемента, а также несколько агрегирующих по какому-то параметру функций. Имя параметра должно храниться в поле stateData объекта QueueItem.

3. Обоснование методов и средств решения задачи

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

1. Процесс извлечения следующего элемента очереди обязан выполняться атомарно – иначе существует потенциальная возможность, что два и более экземпляра робота получат один и тот же элемент очереди;
2. Для обеспечения атомарности необходимо иметь представление о том, какой элемент извечен из очереди, а какой – нет - для этого можно использовать поле status объекта QueueItem;
3. В реализации очереди «из коробки» статус объекта очереди не меняется, так как вся очередь хранится в том же потоке, в котором работает кроулер – в этом случае достаточно просто хранить индекс последнего неизвлеченного элемента;
4. Исходя из пунктов 1-4, лучший способ обеспечения корректной работы распределенной очереди – использовать атомарную операцию «найти и обновить», либо транзакцию, в которой происходит сначала поиск элемента, а потом его обновление;

Также стоит отметить, что несмотря на то, что термин «очередь» подразумевает полное извлечение элемента из этой структуры при соответствующей операции, в контексте поискового робота необходимо понимать этот термин по-другому. Дело в том, что чтобы избежать повторного индексирования той же страницы, необходимо хранить историю индексирования всех страниц и при добавлении очередного объекта в очередь необходимо также проверять, что такого элемента (в данном случае – с заданным URL) еще нет в очереди или он не был уже проиндексирован.

4. Проблемы реализации и пути их решения

Основной сложностью реализации стало обеспечение целостности данных и атомарности всех операций, где может возникнуть проблема перезаписи данных. Некоторые из операций удалось обеспечить «атомарностью» довольно просто – например, для извлечения следующего непроиндексированного объекта используется операция findAndUpdate, которая атомарно извлекает объект по заданному фильтру и обновляет заданные поля объекта.

Для добавления элемента в очередь пришлось исхитриться – на самом деле, используется метод update, причем фильтром выступает сам объект. Также, операция сконфигурирована на использование правила «upsert: true», что значит «вставить новый объект, если такой объект не нашелся. Таким образом, даже если 2 параллельных экземпляра кроулера вызовут один метод добавления для одного объекта, в очереди в результате окажется только один объект.

Также стоит отметить, что для корректной работы и большей безопасности был реализован вспомогательный метод очистки очереди от объектов в «подвешенном» состоянии. Объекты очереди могут попасть в такое состояние, если экземпляр кроулера получил его на обработку, но не обработал до конца (например, в результате ошибки и падения приложения). В таком случае объект хранится в очереди со статусом «занят» бесконечно, и ни один другой экземпляр кроулера не может его обработать. Чтобы избежать этого, вспомогательный метод обновляет все объекты очереди с таким статусом, время обращения к которым было более 10 минут назад. То есть, если за 10 минут экземпляр кроулера не обработал объект, объект возвращается в изначальное положение и его могут обрабатывать другие экземпляры.

5. Результаты реализации

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

В качестве тестирования было запущено несколько циклов индексации с разным количеством параллельных экземпляров модуля (от 1 до 8). На исходных данных в 60 000 страниц скорость обработки растет линейно, что говорит о том, что лимит по производительности не достигнут. Таким образом можно сделать вывод, что модуль можно использовать на заданных объемах, но необходимо продолжить тестирование на большем объеме.

Заключение

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

Список литературы:

1. Michael Nielsen. How to crawl a quarter billion webpages in 40 hours [Электронный ресурс]. URL: http://www.michaelnielsen.org/ddi/how-to-crawl-a-quarter-billion-webpages-in-40-hours/ (дата обращения: 22.04.2019)
2. MongoDB Node.js Driver [Электронный ресурс]. URL: https://mongodb.github.io/node-mongodb-native/ (дата обращения: 23.04.2019)
3. Simplecrawler documentation [Электронный ресурс]. URL: https://github.com/simplecrawler/simplecrawler#documentation (дата обращения 23.04.2019)