Яндекс для всех

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

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

После того как все части информации обработаны, начинается объединение (слияние) результатов. Основная база участвует в анализе как одна из частей нового индекса. Так, если объединяются 70 новых частей, то в анализе участвует 71 фрагмент (70 новых + основная база предыдущей редакции). Специальная программа ('сливатор') составляет таблицы перенумерации документов базы. Содержимое всех частей объединяется. Среди страниц с одинаковыми адресами выбирается наиболее свежая версия; если при скачивании URL последней информацией была ошибка 404 (запрашиваемая страница не существует), она временно удаляется из индексной базы. Параллельно осуществляется склейка дублей — страницы, которые имеют одинаковое содержимое, но различные URL, объединяются в один документ.

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

Источник: 'Принципы работы поисковой машины Рамблер' (http://www.rambler.ru/doc/architecture.shtml).

А вот что рассказывали о решении аналогичных задач на Яндексе.

Если применить к поиску на Яндексе традиционные термины Distributed Information Retrieval, то можно выделить следующие приемы распараллеливания.

1. Разделение коллекции документов — начиная с весны 2000 года, в Яндексе используется 'параллельный поиск' в нескольких поисковых источниках. Параллельный поиск — это одновременный поиск в специализированных базах (коллекциях), предлагаемых поисковой системой. Обычно, источник — это отдельная база небольшого размера, отличная от 'большой' базы документов. Подразумевается, что документы, индексируемые в такой базе, имеют некоторую регулярную структуру. Если при поиске по обычной базе находятся и документы из базы параллельного поиска, точно соответствующие запросу, то одновременно (параллельно) с обычным результатами поиска выдается список из нескольких найденных документов. База параллельных источников имеет существенно меньший размер, чем база веб-поиска. Обход и индексация документов в ней осуществляется отдельным роботом, поэтому обновление базы может происходить очень быстро (вплоть до ежеминутного).

В 'Яндексе' есть четыре базы параллельного поиска:

• по новостям (обновление каждые 10 минут, ежедневно около 3000 новостей);

• по товарным предложениям интернет-магазинов (ежедневное обновление, примерно 300 000 товаров);

• по заголовкам статей энциклопедий (обновление раз в месяц, около 200 000 статей);

• по каталогу ('ручному' описанию веб-ресурсов).

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

Среди особенностей текущей реализации разделения веб-коллекции в Яндексе можно отметить следующее:

• есть центр контроля и распределения URL;

• отсутствует репликация коллекции по машинам;

• распределение документов по коллекциям случайно.

2. Первая фаза обработки запроса: выбор коллекции, трансформации запроса — пользователь может явно указать, в какой коллекции следует искать. Если этого не сделано, то на основе лингвистического (точнее, эвристического) анализа запроса Яндекс может сделать допущение о приоритете специализированной коллекции или подходящей к характеру запроса рубрики каталога.

3. Вторая фаза обработки запроса: раздача запроса по коллекциям — обычно используются все коллекции. Собирающий сервер раздает в коллекции модифицированные запросы, в которых для каждого термина сообщается глобальное значение его обратной частоты (IDf в терминах традиционного IR). Для этого на всех 'собирающих' серверах хранится глобальная статистика терминов. Она изменяется медленно, поэтому обновляется относительно редко. Статистика подсчитывается по считающейся наиболее универсальной — вебовской — коллекции. Таким образом, каждая поисковая машина ищет ответ на запрос с назначенными 'сверху' глобальными частотами, и значения релевантности, вычисляемые в разных коллекциях, можно считать последовательными и вычисляемыми 'в одной системе координат'. Модификации запросов этим не ограничиваются, и для специализированных коллекций (например, 'энциклопедии') могут быть и другими, в том числе и очень специфическими.

4. Третья фаза обработки запроса: исполнение и ранжирование запроса в коллекциях — запрос выполняется паралельно для всех коллекций.

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

1.2.1. 'Пауки'

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

Вот они, те роботы, которые выполняют основную работу по поиску и индексированию информации:

? Yandex/1.01.001 (compatible; Win16; I) — основной индексирующий робот;

? Yandex/1.01.001 (compatible; Win16; P) — индексатор картинок;

? Yandex/1.01.001 (compatible; Win16; H) — робот, определяющий зеркала сайтов;

? Yandex/1.02.000 (compatible; Win16; F) — робот, индексирующий пиктограммы сайтов (favicons);

? Yandex/1.03.003 (compatible; Win16; D) — робот, обращающийся к странице при добавлении ее