Полное содержание и список моих статей по поисковой машине будет обновлятся здесь.
В предыдущих статьях я рассказывал про работу поисковой машины, вот и дошел до сложного технически момента. Напомню что разделяют 2 типа индексов – прямой и обратный. Прямой – сопоставление документу списка слов в нем встреченного. Обратный – слову сопоставляется список документов, в которых оно есть. Логично, что для быстрого поиска лучше всего подходит обратный индекс. Интересный вопрос и про то, в каком порядке в списке хранить документы.
На предыдущем шаге DataFlow от модуля-индексатора мы получили кусочек данных в виде прямого индекса, ссылочной информации и информации о страницах. Обычно у меня он составляет около 200-300mb и содержит примерно 100 тысяч страниц. Со временем я отказался от стратегии хранения цельного прямого индекса, и храню только все эти кусочки + полный обратный индекс в нескольких версиях, чтобы можно было откатиться назад.
Устройство обратного индекса с виду, простое, – храним файл, в нем в начале таблица адресов начала данных по каждому слову, потом собственно данные. Это я утрировано. Так получается самый выгодный для оптимизации скорости поиска формат — не надо прыгать по страницам — как писали Брин и Пейдж, — 1 seek, 1 read. На каждой итерации перестроения, я использую 20-50 кусочков информации описанных выше, очевидно загрузить всю инфу из них в память я не могу, тем более что там полезно хранить еще кучу служебных данных об индексе.
Чтобы решить и эту, и много других проблем связанных с ограничениями ФС, диска, параллельным доступом к нескольким спискам страниц, я разбил весь индекс на 256 частей. В часть I попадают списки страниц для слов WORD_ID%256=I
Таким образом делим индекс на примерно равные части. Кроме того вся обработка на очередной итерации перестроения индекса связана только в рамках одной части. Т.е. из 20-50 кусков БД по 200-300 Mb необходимо загрузить только те данные, которые связаны со словами, попадающими в обрабатываемую часть.
Итого: делаем 256 повторений одной и той же процедуры:
На практике естественно оказалось, что тот список, который уже хранится в «предыдущей версии» индекса оказывается отсортированным при новой итерации только тогда, когда никакая внешняя информация о страницах не менялась, а это очевидно не так.
Ведь пока мы копили инфу для индекса, могли пересчитаться данные о PR, метрики страниц, тематичность сайтов, и тд. И как следствие, изменится коэффициенты для сортировки. Вопрос нужно ли вообще сортировать списки по подобным параметрам, до сих пор открыт. По слухам гугл сортирует страницы в списках по PR, но очевидно тогда надо уметь быстро отбрасывать шелуху при поиске – которую специально накачали PR, но тематичности недостаточно.
Я использую совмещенный коэффициент, построенный из общей информации о слове на странице (кол-во встреч; место встречи – title, meta, ссылки, текст; выделение, форматирование), из метрик тематичности (пока что они развиты у меня весьма слабо), из PR, из пословного PR (PR по каждому слову у меня тоже есть) и некоторых других.
Причем очевидно, что при высокочастотных запросах, нам реально нужны дай бог первая 1000-2000 результатов в списке, для верности будем считать 262 тысячи. Т.к. все популярные ответы очевидно попадут в них, а дальше на них можно запускать уже функцию ранжирования которая как следует их отсортирует.
При низкочастотных запросах, когда нам реально нужны 2-3-10 результатов, без полного прохождения индекса не обойтись, однако и общая длина списка страниц редко когда будет больше 100 тысяч.
В целом если мы сможем гарантировать что первые N тысяч страниц в списке будут лучшими из остальных пары миллионов, то задача решена, а гарантировать это довольно просто эвристическими методами. Тогда для корректного перестроения каждого барреля:
Ну и конечно надо иметь функцию «обновить целиком» когда раз в месяц-полгода, к примеру, индекс будет перестраиваться весь самым простым прямым алгоритмом
Понятно, что даже такой объем работы в применении к 3 миллионам средне употребляемых слов и цифр дается нелегко, но зато по сравнению с полным перестроением выигрыш существенен: ведь не надо сортировать на диске, не надо грузить внешние метрики, PR и другие параметры – их ведь тоже нельзя кэшировать все в памяти.
Забавно что итеративный способ перестроения дает в разы большую производительность чем простейшее построение обратного индекса из прямого. Некоторые поисковики конечно умудряются это делать достаточно быстро на довольно мощном железе, однако это все равно не лучший подход хоть и самый корректный. Просто количество длинных вставок в обратный индекс сводит все плюсы на нет, да и в известных мне структурах хранения страдает либо скорость вставки либо скорость последовательного чтения.
В предыдущих статьях я рассказывал про работу поисковой машины, вот и дошел до сложного технически момента. Напомню что разделяют 2 типа индексов – прямой и обратный. Прямой – сопоставление документу списка слов в нем встреченного. Обратный – слову сопоставляется список документов, в которых оно есть. Логично, что для быстрого поиска лучше всего подходит обратный индекс. Интересный вопрос и про то, в каком порядке в списке хранить документы.
На предыдущем шаге DataFlow от модуля-индексатора мы получили кусочек данных в виде прямого индекса, ссылочной информации и информации о страницах. Обычно у меня он составляет около 200-300mb и содержит примерно 100 тысяч страниц. Со временем я отказался от стратегии хранения цельного прямого индекса, и храню только все эти кусочки + полный обратный индекс в нескольких версиях, чтобы можно было откатиться назад.
Устройство обратного индекса с виду, простое, – храним файл, в нем в начале таблица адресов начала данных по каждому слову, потом собственно данные. Это я утрировано. Так получается самый выгодный для оптимизации скорости поиска формат — не надо прыгать по страницам — как писали Брин и Пейдж, — 1 seek, 1 read. На каждой итерации перестроения, я использую 20-50 кусочков информации описанных выше, очевидно загрузить всю инфу из них в память я не могу, тем более что там полезно хранить еще кучу служебных данных об индексе.
Чтобы решить и эту, и много других проблем связанных с ограничениями ФС, диска, параллельным доступом к нескольким спискам страниц, я разбил весь индекс на 256 частей. В часть I попадают списки страниц для слов WORD_ID%256=I
Таким образом делим индекс на примерно равные части. Кроме того вся обработка на очередной итерации перестроения индекса связана только в рамках одной части. Т.е. из 20-50 кусков БД по 200-300 Mb необходимо загрузить только те данные, которые связаны со словами, попадающими в обрабатываемую часть.
Итого: делаем 256 повторений одной и той же процедуры:
- читаем нужные данные из входных кусков БД, предварительно загрузив всю информацию о словах, страницах и Url страниц. В памяти сортируем, делаем списки правильной структуры. Упаковываем инфу о странице и добавляем ее ID, HASH и другие данные.
- открываем баррель (я обозвал так куски индекса) обратного индекса «крайней версии» для чтения. Открываем пустой баррель «новой версии» индекса для записи.
- Для каждого слова по порядку сливаем 2 списка – один построенный сортированный в памяти, а другой читаемый и уже отсортированный в файле.
- Закрываем, дописываем все что надо, радуемся.
На практике естественно оказалось, что тот список, который уже хранится в «предыдущей версии» индекса оказывается отсортированным при новой итерации только тогда, когда никакая внешняя информация о страницах не менялась, а это очевидно не так.
Ведь пока мы копили инфу для индекса, могли пересчитаться данные о PR, метрики страниц, тематичность сайтов, и тд. И как следствие, изменится коэффициенты для сортировки. Вопрос нужно ли вообще сортировать списки по подобным параметрам, до сих пор открыт. По слухам гугл сортирует страницы в списках по PR, но очевидно тогда надо уметь быстро отбрасывать шелуху при поиске – которую специально накачали PR, но тематичности недостаточно.
Я использую совмещенный коэффициент, построенный из общей информации о слове на странице (кол-во встреч; место встречи – title, meta, ссылки, текст; выделение, форматирование), из метрик тематичности (пока что они развиты у меня весьма слабо), из PR, из пословного PR (PR по каждому слову у меня тоже есть) и некоторых других.
Причем очевидно, что при высокочастотных запросах, нам реально нужны дай бог первая 1000-2000 результатов в списке, для верности будем считать 262 тысячи. Т.к. все популярные ответы очевидно попадут в них, а дальше на них можно запускать уже функцию ранжирования которая как следует их отсортирует.
При низкочастотных запросах, когда нам реально нужны 2-3-10 результатов, без полного прохождения индекса не обойтись, однако и общая длина списка страниц редко когда будет больше 100 тысяч.
В целом если мы сможем гарантировать что первые N тысяч страниц в списке будут лучшими из остальных пары миллионов, то задача решена, а гарантировать это довольно просто эвристическими методами. Тогда для корректного перестроения каждого барреля:
- запоминаем какие PR сильно изменились при пересчете
- грузим первые N тысяч из списка+немного из остатка по критериям PR, метрики страницы и другой эвристике
- туда же грузим из входных данных нужную порцию о словах текущего барреля
- только для выделенных страниц уже обновляем все данные на корректные, новые – PR, метрики
- сортируем сотню тысяч результатов, вместо пары десятков миллионов и уже в памяти
- пишем отсортированное, а остальное просто копируем из предыдущего индекса удаляя дубли
Ну и конечно надо иметь функцию «обновить целиком» когда раз в месяц-полгода, к примеру, индекс будет перестраиваться весь самым простым прямым алгоритмом
Понятно, что даже такой объем работы в применении к 3 миллионам средне употребляемых слов и цифр дается нелегко, но зато по сравнению с полным перестроением выигрыш существенен: ведь не надо сортировать на диске, не надо грузить внешние метрики, PR и другие параметры – их ведь тоже нельзя кэшировать все в памяти.
Забавно что итеративный способ перестроения дает в разы большую производительность чем простейшее построение обратного индекса из прямого. Некоторые поисковики конечно умудряются это делать достаточно быстро на довольно мощном железе, однако это все равно не лучший подход хоть и самый корректный. Просто количество длинных вставок в обратный индекс сводит все плюсы на нет, да и в известных мне структурах хранения страдает либо скорость вставки либо скорость последовательного чтения.
