Поисковые технологии

Поисковые технологии или в чем загвоздка написать свой поисковик

Когда-то давно взбрела мне в голову идея: написать свой собственный поисковик. Было это очень давно, тогда я еще учился в ВУЗе, мало чего знал про технологии разработки больших проектов, зато отлично владел парой десятков языков программирования и протоколов, да и сайтов своих к тому времени было понаделано много.

Ну есть у меня тяга к монструозным проектам, да…

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

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

Здесь я в первый раз, публично, опишу то, что было сделано лично мной. Думаю, многим будет интересно как же работают Яндекс, Google и почти все мне известные поисковики изнутри.

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

Просто вдумайтесь, Google хранит, по одной из оценок, более 500 миллиардов страниц в индексе. Если бы каждое слово встречалось на 1 странице только 1 раз, и на хранение этого надо было 1 байт – что невозможно, т.к. надо хранить хотя бы id страницы – уже от 4 байт, так вот тогда объем индекса бы был 500гб. В реальности одно слово встречается на странице в среднем до 10 раз, объем информации на вхождение редко когда меньше 30-50 байт, весь индекс увеличивается в тысячи раз… Ну и как прикажите это хранить? А обновлять?

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

На сегодня объем только индекса, по которому происходит поиск — 57Gb, увеличивается каждый день примерно на 1Gb. Объем сжатых текстов – 25Gb, ну и я храню кучу другой полезной инфы, объем которой очень трудно посчитать из-за ее обилия.

С чего начинается поисковик, или несколько мыслей про crawler

Итак есть несколько крупных задач, которые должна решить система поиска, начнем с того что отдельную страницу надо получить и сохранить.

Тут есть несколько способов, в зависимости от того, какие способы обработки Вы выберете в дальнейшем.

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

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

Сколько страниц получать с одного сайта за раз? Лично я предпочитаю не больше 100 тысяч, хотя периодически меняю это ограничение всего на 1000 страниц. Да и сайтов на которых страниц больше – не так много.

Сейчас рассмотрим подробнее:

Если мы получаем 1 страницу за раз, все страницы последовательно, то сколько страниц мы обработаем, скажем, за час?

— время получения страницы складывается из:

времени, которое мы ждем ответа ДНС (оно, как показывает практика совсем не мало). ДНС сопоставляет имени сайта «site.ru» ip адрес сервера, на котором он лежит, и это не самая простая задача учитывая, что сайты имеют обыкновения переезжать, маршруты роутинга пакетов меняться и многое другое. Вкратце, ДНС сервер хранит таблицу адресов, и каждый раз мы стучимся к нему чтобы понять адрес – куда идти за страницей.

времени коннекта и отсылки запроса (быстро если у вас хотя бы средний канал)

времени получения собственно ответа – страницы

Именно поэтому Яндекс, по слухам, в свое время столкнулся с самой первой проблемой – если получать действительно много страниц, то ДНС провайдера не в состоянии справится с этим – по моему опыту задержка составляла до 10 секунд на адрес, тем более что надо еще передать ответ туда сюда по сети, и я у провайдера не один. Замечу, что при запросе последовательно 1000 страниц с одного сайта, Вы будете каждый из 1000 раз дергать провайдер.

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

Если же используете готовые решения типа LWP или HTTP модулей для Perl, то локальный ДНС сервер будет оптимален.

Теперь положим, что ответ идет до Вас 1-10 секунд в среднем – есть быстрые сервера, а есть и очень медленные. Тогда в минуту Вы получили 6-60 страниц, в час 360-3600, в день примерно от 8000 до 60000 (осознано округляю в меньшую сторону на всевозможные задержки: в реальности при запросе 1 страницы за раз без локального ДНС, на канале 100mbit/s, Вы получите 10000 страниц в сутки, конечно, если сайты будут разные, а не один очень быстрый)

И даже учитывая, что здесь не учтено время на обработку, сохранение страниц – результат, откровенно, мизерный.

Ок, сказал я, и сделал 128 запросов за раз параллельно, все летало отлично – пик 120 тысяч страниц в час, пока не стали поступать матерные логии от админов серверов куда я стучался, о ДДОС атаках, ну да 5000 запросов за 5 минут это наверное не любой хостинг позволяет.

Все решилось тем, что одновременно грузить я стал 8-16 разных сайтов, не больше чем по 2-3 страницы параллельно. Получилось что-то около 20-30 тысяч страниц в час, и меня это устроило. Надо сказать ночью показатели намного вырастают.

Общие слова про устройство поиска в Web

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

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

Надо сказать что задача поиска в общем виде не решается – для любого документа имеющего наибольшую релевантность например по слову «работа», можно создать модифицированную копию, которая будет иметь еще лучшую, с точки зрения поисковой машины, релевантность, однако будет полным бредом с точки зрения человека. Вопрос цены и времени, конечно. Из-за обширности Интернета на сегодняшний день таких страниц, мягко говоря, много. Разные системы борются с ними по-разному и с переменным успехом, когда-нибудь искусственный интеллект победит всех нас…

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

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

Скажем у меня 100 миллионов страниц. Среднее слово встречается на 1-1,5% страниц, т.е. 1 миллион страниц на каждое слово (есть слова которые встречаются на каждой второй странице, а есть более редкие). Всего скажем 3 миллиона встречающихся слов – остальные встречаются гораздо реже и это в основном описки и цифры. На хранение 1 записи что конкретное слово встречается на конкретной странице уходит id страницы – 4 байта, id сайта – 4 байта, упакованная информация о том в каком месте и как было выделено – 16-32 байта, 3 коэффициента ссылочного ранжирования – 12 байт, остальные метрики еще около 12-24 байт. Какого объема будет индекс – оставляю вам на прикидку:

3млн*1млн*суммарный объем записи.

Для того чтобы построить этот индекс есть 3 механизма:

индексация страниц – получение страниц из web и их начальная обработка

построение ссылочных метрик типа PageRank на основе первичной информации

обновление существующего индекса – внос туда новой информации и его сортировка по полученным метрикам, в частности PageRank.

Дополнительно надо сохранить тексты страниц – для построения аннотаций в процессе поиска

Процесс поиска

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

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

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

Когда индекс уже построен, по нему можно искать:

разбить запрос на слова, выбрать кусочки индекса соответствующие каждому слову, пересечь или сделать что-то еще, в зависимости от выбранной политики

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

построить метрику релевантности исходя из коэффициентов, отсортировать, выбрать лучшие результаты

построить аннотации — снипеты и вывести результат.

Dataflow работы поисковой машины

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

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

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

На выходе получаем тексты страниц без всего лишнего и сгруппированные по сайтам.

Все готовые страницы одного сайта складываю в каталог, который попадает к индексатору. Индексатор создает маленькую версию «прямого» индекса, состоящего из нескольких (10-1000) сайтов подготовленных на предыдущем этапе – парсит HTML, сопоставляет слова, упаковывает, считает метрики пословные. Прямой индекс – это таблица где по ID документа я могу получить список слов и всю информацию об их вхождениях в документ. Также к нему прикладываются БД слов (построенная из этого маленького количества документов) и ссылок (все еще не добавленные в общий индекс и потому еще не имеющие ID). Ссылки идут к модулю пересчета PR (в информации у ссылок участвуют слова и их веса), остальное на обновление обратного индекса. Объем кусочка, который индексатор подготовил, обычно 100-300Mb за час. И это без текстов страниц.

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

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

Предварительно готовятся БД слов, метрик и всего прочего, так же инкрементально соединяя предыдущую версию с новой информацией. ID слов в мелком прямом индексе на ходу заменяются на те, которые соответствуют полной версии БД, и остальная информация аналогично.

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

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

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

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

Если же нормальной формы не нашлось, то применяем стемминг – исходя из текстов книг скачанных с lib.ru, я построил таблицу частоты встречаемости окончаний, ищем наиболее встречаемое из подходящих (тоже деревом) и заменяем на нормальную форму. Стемминг хорошо работает, если слова не было в языке еще лет 5-10 назад – легко разберет «краулеры» в «краулер».

Про удаление малозначимых частей страниц при индексации сайта

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

Думаю нет особой причины останавливаться на алгоритме разбора HTML в дерево, тем более, что в обобщенном виде такие парсеры учат писать курсе на 3-4 ВУЗа. Обычный стек, немного фишечек по пропуску аргументов (кроме тех что потом понадобятся), и выходное дерево как результат разбора. Текст разбивается на слова прямо в процессе разбора, и слова отправляются в отдельный список, где запомнены кроме общей информации и все позиции слова в документе. Понятное дело слова в списке уже в 1-й нормальной форме, про морфологию уже писал, здесь просто скопирую из предыдущей статьи.

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

Если же нормальной формы не нашлось, то применяем стемминг – исходя из текстов книг скачанных с lib.ru, я построил таблицу частоты встречаемости окончаний, ищем наиболее встречаемое из подходящих (тоже деревом) и заменяем на нормальную форму. Стемминг хорошо работает, если слова не было в языке еще лет 5-10 назад – легко разберет «краулеры» в «краулер»

После долгих экспериментов с разбором HTML обратил внимание на то, что одинаковые блоки в HTML очевидно составляют одинаковые поддеревья – грубо говоря если есть 2 страницы, и 2 дерева и между ними сделать XOR то останется только нужный контент. Ну или если так проще – пересечение большинства таких деревьев по одному сайту даст вероятностную модель – чем в большем количестве деревьев встречен блок, тем меньше его значимость. Все что встречено более чем в 20% -30% — я выкидываю, смысла нет тратить время на дублированный контент.

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

Итак в 2 прогона по всем страницам сайта – сначала собираем статистику, потом индексим – вопрос вычленения паттернов легко решается. Получаем, кроме того, много плюсов – конструкции типа <td></td>, <b></b> и остальные бессмысленные будут выкинуты в первую очередь.

Методы оптимизации производительности приложения при работе с РБД

Действуют они везде – хоть MySQL, хоть Oracle хоть самописная БД. Чем умнее БД – тем больше она старается оптимизировать сама, но лучше ей помочь

1. Разделяй и властвуй, а попросту кластеризация БД – все данные одного типа можно еще разбить на кластеры – отдельные таблицы, в каждую таблицу попадают записи, которые удовлетворяют какому-то простейшему правилу, например в таблицу с индексом I попадают данные у которых ID%N==I, где N – кол-во кластеров. Таким образом очень просто и эффективно делим те данные, которые не надо считывать последовательно – например разбиваем все слова на 100-200-миллион блоков, в каждом блоке только слова у которых ID%N==I. В качестве примера в большой системе, типа социальной сети, можно поделить все данные по признаку принадлежности одному пользователю — например все фото разместить в N таблиц, информация о фото помещается в таблицу K=USER_ID%N

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

3. Не храните на диске то, что нужно часто – загрузите в память. Сейчас легко можно положить в память гигабайт, а то и два. Если все не помещается – разбейте данные на куски и делайте работу в рамках одного куска. Никакой memcached и аналоги не помогут в такой задаче, только Вы знаете, в какой последовательности данные попадут в обработку, поэтому сможете написать решение в десятки раз быстрее стандартных утилит. Для использования данных хорошо подходят многие «старые» структуры.

— хеширование (все данные разбиваются на части в соответствии с некоторым правилом, например CRC%N)

— AVL и B деревья (очень советую для себя любимого взять бумагу, ручку, C/C++ и реализовать их самостоятельно следуя только определениям, не читая алгоритма — разработать самому. Развивает смекалку и поднимает Ваш общий уровень)

— Heap с упорядоченной выборкой

4. Используйте указатели и связанные структуры. Пример из социальных сетей: часто из 100 млн фото сложно найти те, на которых отмечен конкретный человек, зато в информации о самом человеке легко хранить список таких фото. Аналогично: хранить в памяти все ссылки на страницы, которые есть в поиске, невозможно, зато легко помещаются url корня сайта. Вычислив по полной ссылке CRC или ID корня (любым образом) можно быстро найти место в файле где записаны все известные ссылки на этом сайте и проверить существует ли данная.

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

И еще: я придерживаюсь мнения что в любой задаче есть что оптимизировать, и если это критично — занимайтесь оптимизацией, и, заодно, собственным образованием по этой теме.

Немного про проектирование баз данных для поисковой машины

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

Итак как минимум будет нужна БД обслуживающая обычные «плоские» («2D») данные – т.е. некоторому идентификатору ID ставится в соответствие поле данных.

Почему поле данных я рассматриваю одно? Потому что:

выборка производится только по полю ID – поиск по данным не производится. Для этого есть специализированные индексы – иначе с такими количествами информации толку будет мало

любое количество полей можно упаковать в одно, для этого я «на коленке» создал набор небольших прикладных библиотек, в частности при упаковке сохраняется CRC данных, чтобы не использовать не дай бог битые

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

Основными операциями для таких таблиц БД являются:

выборка по ID

прочитать последовательно всю базу (в память или хэш)

обновить запись по ID

вставить новую в конец, получить ID

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

Возникает вопрос как обновлять записи в середине таблицы когда их размер меняется – ведь если вся таблица больше 10-20-200 Гб, то скопировать половину таблицы во временный файл, а потом обратно будет занимать часы? Я переложил этот вопрос на файловую систему разбив все страницы на блоки. Один блок – один файл на диске, количество файлов одной таблицы не ограничено. В каждом файле хранятся последовательно ограниченное фиксированное количество страниц. Тогда если надо обновить запись в середине таблицы, то мне надо изменить только 1 файл гораздо меньшего и, зачастую, ограниченного объема. Ответственность за то чтобы не просить файловую систему делать глупости типа сначала пишем в начало, потом в конец, потом опять в начало — я взял на себя. Просто чтобы не напрягать сервер пишу всегда пакетно, соответствующий функционал максимально оптимизирован, все происходит в памяти. Ну и понятное дело, вся система модулей поисковой машины построена исходя из того что записать 1000 записей в конец быстрее чем 1 в начало — поэтому при записи в начало иногда проще сделать копию таблицы.

Хорошо, с обычными таблицами решили. Сейчас описанная БД очень неплохо, в частности, обрабатывает в процессе поиска 35 Гб кусков текстов, с произвольной выборкой.

Но есть и ограничения – в такой таблице хранить соответствие: для каждого слова список документов в которых слово встретилось (вместе с дополнительной информацией) — практически невозможно – по каждому слову будет ну очень много документов, а соответственно и объем будет огромный.

Итак какие операции надо делать с такой БД:

последовательную выборку с начала списка по нужному произвольному слову и пока не надоест

по хорошему надо бы изменять список документов для слова, но тут можно сделать финт – обойтись только вставкой в конец БД

Как обновлять такой индекс? Очевидно что если индекс пустой и мы начнем в него вставлять списки документов начиная с первого слова и заканчивая последним – писать мы будем только в конец файла. Более того, писать или не писать физически отдельные блоки для каждого слова – отдельно на диск, дело разработчика – и в том и другом случае можно просто запомнить: где закончился очередной блок и его длину, сохранить это в простейший список. Тогда процедура последовательного чтения будет такая: перемещаемся в файле на начало списка для нужного слова, и читаем последовательно пока не начнется список для следующего слова: 1 seek, и минимально необходимое кол-во read — победа (здесь я специально не считаю операции самой файловой системы — можно отдельно заняться их оптимизацией)

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

AVL деревья и широта их применения

Решил немного описать на мой взгляд самую полезную древовидную структуру. AVL дерево это бинарное дерево (у каждой вершины не более 2 сыновей), в котором каждой вершине присвоен идентификатор (как раз его и хранит дерево), идентификаторы подчиняются следующему правилу: ID левого сына<ID родителя<ID правого сына.

Т.е. если обходить дерево рекурсивно слева направо получим отсортированный по возрастанию список ID, справа налево – по убыванию.

Причем дерево максимально сбалансировано: высота левого поддерева отличается от высоты правого максимум на 1.

Интересно в нем то, что тогда на проверку существования элемента в дереве уходит log(N) N – количество ID. Ведь надо пройти от корня вниз, а поскольку дерево максимально симметрично то его высота — log(N)+1

Хорошая новость – нам никто не запрещает прикрепить к вершине еще какие-то полезные данные и тогда выборка произвольных данных по ID будет занимать log(N) времени

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

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

Интересно вот что: очевидно такое дерево из списка идентификаторов можно построить, но так же, оказывается, в него можно быстро добавлять и быстро удалять элементы за очень короткое время <= log(N) (добавление)

Таким образом для сортировки массива из N элементов можно его просто добавить в дерево – N*log(N) а потом обойти слева направо – N т.е. суммарное время N*log(N) – и мы сделали очередной очень быстрый метод сортировки массива

Кстати еще несколько операций для удобства – раз мы быстро ищем вершину с нужным ID, то сделаем операции Set и Get для изменения поля DATA в вершине. Таким образом обновление данных соответствующих заданному ID в памяти мы делаем тоже за <=log(N)

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

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

Теперь немного про то, как же добавлять в дерево, полных описаний очень много в свободном доступе, поэтому кратенько:

Введем в каждую вершину число balance которое показывает, какое из поддеревьев выше – левое или правое.

При добавлении вершины в дерево оно иногда становится не сбалансированным. Процедура добавления проста – спускаемся по дереву до самого низа, используя правило

ID левого сына<ID родителя<ID правого сына, т.е. если новый ID < ID вершины идем влево, иначе вправо. Добавив сына к нижней вершине мы должны обновить показатель balance по нашему пути которым мы шли – можем это делать по ходу спуска, можем пройтись вверх обратно – если пришли из левого поддерева то balance--, иначе balance++

Если на каком-то уровне мы получили balance=0 – то поддерево сбалансировано и можно закончить добавление (все дерево вверху не надо пересчитывать т.к. высота поддерева не изменилась – было balance=-1 стало 0 – левое поддерево перевешивало, добавили в правое и выровняли, или balance=1 стало 0 — правое поддерево перевешивало, добавили в левое и выровняли)

Ну и самое интересное это балансировка поддерева если на каком-то шаге по обратному пути мы получили balance=-2 или 2, это значит что одна половина дерева перевесила сильно, и надо сделать некий поворот – поднять на 1 звено, к примеру, правое, а левое удлинить. Весь поворот сводится к проверке условий и переставлению ссылок, лично я его понимал для себя на бумажке – возможны всего 3 варианта, чего и вам советую для лучшего осознавания – специально не буду здесь расписывать словами то, что можно нарисовать, а если совсем лень, то найти в инете готовые решения.

Работа с URL и их хранение

Ну вот одна из самых вкусных частей БД – она хранит миллиарды разных ссылок, и производит доступ к ним в произвольном порядке.

Сначала очевидно можно заметить что все URL сгруппированы в рамках сайта, т.е. все ссылки внутри 1 сайта можно хранить вместе для скорости. Я выделил URL сайта, и стал хранить список сайтов отдельно – сейчас их 600 тыс и отдельная таблица БД описанной раньше легко с ними справляется. В памяти постоянно находится AVL дерево с CRC всех известных сайтов, и проверяя первым делом существование URL я получаю ID сайта ему соответствующего, если он уже есть в базе.

Остальную часть ссылки – кроме названия сайта я отрезаю, и считаю CRC для нее, назовем ее Hash. Таким образом любая ссылка относительно однозначно имеет индекс (ID сайта, Hash). Все ссылки можно отсортировать по Hash в рамках отдельного сайта, и тогда можно легко искать существующую или нет – пробегать по списку все ссылок данного сайта пока не встретим с нужным Hash или не встретим больший Hash – значит ссылки нет. Ускорение не очень большое, но в 2 раза, все таки, в среднем.

Надо сказать, что каждой ссылке у меня присвоен ID для того чтобы меньше места занимал в индексе – 4 байта вместо 2*4. Отдельная таблица содержит данные ID – (ID сайта, Hash) для быстрой выборки.

Теперь немного про то как же хранить списки по миллиону ссылок да еще и отсортировано для 600 тысяч сайтов. Для этого реализован еще один тип таблицы – с двумерным индексом, т.е. сначала по ID1 мы получаем доступ к списку данных отсортированных по ID2 причем специально ID2 не обязан быть от 1 до N, как делается в большинстве случаев. Такая таблица применялась у меня и для хранения обратного индекса, но сейчас там работает более эффективное решение. Сама таблица реализована так, чтобы добавление в список ID2 сохраняло отсортированность списка.

Все данные об URL'ах разбиты на 64 части по ID1, в таблице K содержаться записи о сайтах ID сайта%64=K, каждая таблица разбита на сегменты, выделенные под каждый конкретный ID1. Когда нужен доступ к конкретному списку записей – по ID1, все они уже лежат подряд на диске, и сразу известна позиция, куда сделать seek и откуда начать буферизовано читать. Читаем ровно до момента, когда встретим нужный Hash

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

URL с www и без учитываются как одинаковые – в зависимости от того на какой из них была первая ссылка тот и считается основным – он будет добавлен в базу, а все остальные ссылки приклеятся к нему. Это позволяет избежать бездумного отрезания или не отрезания www – ведь сайт может не работать без www, однако не полностью решает все проблемы связанные с тем что по адресам с www и без могут быть разные сайты

Самая кропотливая работа была в разрешении относительных ссылок – пример:

на странице “site.ru/index” есть ссылка “./” тогда она должна разрешится в “site.ru/” однако если к первой ссылке приписать слеш: “site.ru/index/” и хотя это может быть все та же страница на сайте, разрешенная ссылка будет «site.ru/index/» поэтому нельзя отрезать слеш на конце, нельзя отрезать аргументы ссылки, и названия файла исполняемого.

В целом я делю ссылку на части: протокол, сайт, путь, имя файла, аргументы, именованная ссылка (все что после #)

Из двух ссылок, так порезанных я собираю новую проходя по списку и подставляя пропущенные элементы (если надо) в результат.

Потом надо не забыть что бывают конструкции вида “./././././” и их надо убрать, а также “../../../”, ну и потом удаляются либо подставляются “#”,”?”

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

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

В предыдущих статьях я рассказывал про работу поисковой машины, вот и дошел до сложного технически момента. Напомню что разделяют 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 и другие параметры – их ведь тоже нельзя кэшировать все в памяти.

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