М. Абрамзон - Яндекс для всех

Хранилище у всех машин едино.

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

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

После того как все части информации обработаны, начинается объединение (слияние) результатов. Основная база участвует в анализе как одна из частей нового индекса. Так, если объединяются 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.