Как стать автором
Обновить

Построение индекса для поисковой машины

Поисковые технологии *
Полное содержание и список моих статей по поисковой машине будет обновлятся здесь.

В предыдущих статьях я рассказывал про работу поисковой машины, вот и дошел до сложного технически момента. Напомню что разделяют 2 типа индексов – прямой и обратный. Прямой – сопоставление документу списка слов в нем встреченного. Обратный – слову сопоставляется список документов, в которых оно есть. Логично, что для быстрого поиска лучше всего подходит обратный индекс. Интересный вопрос и про то, в каком порядке в списке хранить документы.

На предыдущем шаге DataFlow от модуля-индексатора мы получили кусочек данных в виде прямого индекса, ссылочной информации и информации о страницах. Обычно у меня он составляет около 200-300mb и содержит примерно 100 тысяч страниц. Со временем я отказался от стратегии хранения цельного прямого индекса, и храню только все эти кусочки + полный обратный индекс в нескольких версиях, чтобы можно было откатиться назад.

Устройство обратного индекса с виду, простое, – храним файл, в нем в начале таблица адресов начала данных по каждому слову, потом собственно данные. Это я утрировано. Так получается самый выгодный для оптимизации скорости поиска формат — не надо прыгать по страницам — как писали Брин и Пейдж, — 1 seek, 1 read. На каждой итерации перестроения, я использую 20-50 кусочков информации описанных выше, очевидно загрузить всю инфу из них в память я не могу, тем более что там полезно хранить еще кучу служебных данных об индексе.

Чтобы решить и эту, и много других проблем связанных с ограничениями ФС, диска, параллельным доступом к нескольким спискам страниц, я разбил весь индекс на 256 частей. В часть I попадают списки страниц для слов WORD_ID%256=I
Таким образом делим индекс на примерно равные части. Кроме того вся обработка на очередной итерации перестроения индекса связана только в рамках одной части. Т.е. из 20-50 кусков БД по 200-300 Mb необходимо загрузить только те данные, которые связаны со словами, попадающими в обрабатываемую часть.

Итого: делаем 256 повторений одной и той же процедуры:

  1. читаем нужные данные из входных кусков БД, предварительно загрузив всю информацию о словах, страницах и Url страниц. В памяти сортируем, делаем списки правильной структуры. Упаковываем инфу о странице и добавляем ее ID, HASH и другие данные.
  2. открываем баррель (я обозвал так куски индекса) обратного индекса «крайней версии» для чтения. Открываем пустой баррель «новой версии» индекса для записи.
  3. Для каждого слова по порядку сливаем 2 списка – один построенный сортированный в памяти, а другой читаемый и уже отсортированный в файле.
  4. Закрываем, дописываем все что надо, радуемся.


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

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

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

Причем очевидно, что при высокочастотных запросах, нам реально нужны дай бог первая 1000-2000 результатов в списке, для верности будем считать 262 тысячи. Т.к. все популярные ответы очевидно попадут в них, а дальше на них можно запускать уже функцию ранжирования которая как следует их отсортирует.
При низкочастотных запросах, когда нам реально нужны 2-3-10 результатов, без полного прохождения индекса не обойтись, однако и общая длина списка страниц редко когда будет больше 100 тысяч.

В целом если мы сможем гарантировать что первые N тысяч страниц в списке будут лучшими из остальных пары миллионов, то задача решена, а гарантировать это довольно просто эвристическими методами. Тогда для корректного перестроения каждого барреля:
  1. запоминаем какие PR сильно изменились при пересчете
  2. грузим первые N тысяч из списка+немного из остатка по критериям PR, метрики страницы и другой эвристике
  3. туда же грузим из входных данных нужную порцию о словах текущего барреля
  4. только для выделенных страниц уже обновляем все данные на корректные, новые – PR, метрики
  5. сортируем сотню тысяч результатов, вместо пары десятков миллионов и уже в памяти
  6. пишем отсортированное, а остальное просто копируем из предыдущего индекса удаляя дубли


Ну и конечно надо иметь функцию «обновить целиком» когда раз в месяц-полгода, к примеру, индекс будет перестраиваться весь самым простым прямым алгоритмом

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

Забавно что итеративный способ перестроения дает в разы большую производительность чем простейшее построение обратного индекса из прямого. Некоторые поисковики конечно умудряются это делать достаточно быстро на довольно мощном железе, однако это все равно не лучший подход хоть и самый корректный. Просто количество длинных вставок в обратный индекс сводит все плюсы на нет, да и в известных мне структурах хранения страдает либо скорость вставки либо скорость последовательного чтения.
Теги:
Хабы:
Всего голосов 33: ↑32 и ↓1 +31
Просмотры 13K
Комментарии Комментарии 9