Как устроен поиск
Андрей Аксенов (shodan, Разработчик поискового движка Sphinx)
Поиск устроен вот так:
Индексация — по большому счету, ничего сложного. Понятное дело, что по малому счету, там в каждой из трех «деталей» спрятан не то, что демон, а целое где-то стадо, где-то легион, не совсем понятно. Но концепция всегда простая. Все начинается с маленького простенького патчика к Многосерчу, а потом 15 лет этой херней занимаешься.
Берешь документы, разваливаешь их на ключевые слова. И просто взять и развалить документ на ключевые слова «мама, мыла, раму» — это ты не далеко ушел от grep«а, потому что потом все равно эти ключевые слова перебирать. Надо строить некую спец. структуру — полнотекстовый индекс. Вариантов для его построения человечество придумало в свое время довольно много, но, слава Богу, от всех отказалось и в нормальных продакшн системах, по большому счету, победил на данный момент вариант ровно один. Про него и буду рассказывать. Все остальные имеют скорее историческое значение, что ли, и практического интереса не представляют.
Потом, когда мы эту спец. структуру волшебную под названием «индекс» построили, по ней не только надо сделать поиск, к несчастью. Условно говоря, поиска по тексту вам не достаточно, вообще, никогда уже. Т.е. я не могу придумать такой use case, когда вам достаточно было бы только текстовых данных для того, чтобы сделать поиск. Потому что если вы ищете по каким-нибудь логам, то вам надо ключевик найти или маску, и наверняка либо отсортировать, либо отгруппировать, либо какие-то еще дополнительные операции сделать над данными. Вам недостаточно просто текста. Для того чтобы найти, вам еще нужна какая-нибудь хотя бы сортировка по дате, или количество фейлов на график выдать и сгруппировать результаты поиска по дню и т.д.
Если вы веб-поиск, который иллюзорно прост… Или ладно веб-поиск, какой-нибудь поиск по локальной коллекции юридических документов, которому, казалось бы, достаточно было найти всякое, отранжировать и — ура-ура, вот оно. Ни хрена подобного. Тоже текста недостаточно для этого, потому что в веб-поиске, вообще, ад и холокост. Ранжирование основывается не только на тексте документов, но еще и на десятках и сотнях дополнительных факторов. И даже в толковом десктопном поиске по достаточно интересной коллекции опять же, кроме текста, будет еще масса всего.
Я потратил много драгоценных секунд на то, чтобы объяснить, что есть доп. обработка, и если раньше когда-то были идеи, что она, вообще, не нужна, то сегодня таких идей нет. Везде и всегда у вас обязательно будет какая-то доп. обработка. Я, в принципе, не видел ни одного запроса, который бы делал просто полнотекстовый матчинг и просто по какой-то голимой релевантности его сортировал. Это, конечно, некоторое преувеличение. Понятное дело, что когда ты какой-нибудь поиск по какому-нибудь форуму делаешь, то у тебя, скорее всего, как раз дефолтный режим — это та самая сортировка по той самой релевантности, если ты особо не заморачиваешься. Но надо понимать, что в этом случае у тебя все равно на твои божественные 2000 постов целых три матча найдется на средний запрос и, как ты их не сортируй, все равно получишь три матча.
Данные решают все. Чтобы понимать, как оно устроено, понятное дело, плясать надо от тех данных, с которыми мы работаем, от устройства той самой спец. структуры волшебной под названием «полнотекстовый индекс».
Полнотекстовый индекс, на самом деле, структура в первом приближении совершенно тупая, как палка. Вот он:
Индекс выглядит вот так. На самом деле, он выглядит совершенно не так, на самом деле все существенно сложнее. Но, как только вы выходите за пределы первого драфта, который на коленке написали, то к словарю привязывается всякая метаинформация. Списки не только документов нужны, а еще и списки позиций, внутри этих списков позиций еще какая-то морфологическая информация хранится… И далее еще много всякой радости, и атрибутивка сбоку где-нибудь лежит. Но, повторюсь, в первом приближении, вот она — визуализация этой структуры.
Тут введен некий непонятный оператор стрелочка (=>), который не является 2/3 оператора сравнения двух элементов для сортировки, который во всякие эзотерические языки пихают. Это некая связь, что, дескать, у нас есть отдельно словарь — левая колонка. Если мы правую половинку заслоним, то у нас останется словарь и стрелочка — это тоже часть словаря. Можно считать, что это указатель для каждого слова разный. Он показывает соответственно на список документов. По этому словарю мы можем найти все документы, где встречается «абырвалг» — тут очевидно 123; или все документы, где есть Петя Петров — вот очевидно, это документы номер 8 и 2. А Вася Васечкин почему-то нигде не встречается. Не повезло Васе.
На самом деле, элемент словаря — это не просто слово, там типично лежит еще дополнительный всякий фарш. Вот — пример фарша в конце. Например, собственно слово, во-первых, смещение в список документов, во-вторых, смещение в список позиций, в-третьих… Далее это все можно было бы положить в сами списки, в отдельные файлы, куда мы показываем, и тем самым более компактный словарь делать. Но тогда, по самому словарю не понятно, а какая частота этого самого слова? А частота этого самого слова либо частота позиций нужна для того, чтобы с одной стороны более оптимальный план запросов построить, плюс отдать вам статистику по ключевым словам без дергания основных здоровых данных индекса с другой стороны. И вдобавок может храниться еще какая-нибудь дополнительная нафаршированная информация. Вот как мы в Sphinx храним масочку полей, которую сматчили по этому слову, чтобы немножечко акселерировать поиск по отдельным полям, если это можно сделать.
Опять же, все может оказаться немного не так, это придуманный пример, если что. Т.е. на самом деле, в обеих существующих в мире и доступных простому человеку open source системах все не так. Что в Sphinx, что в Lucene, словарь на самом деле другой, с другими данными, несколько другим форматом и т.д. Но концептуально он отличается не сильно. Т.е. да, он не такой, чуть другие поля, у нас position offset нет, и все.
Еще один интересный момент, который, наверное, стоит упомянуть, это то, что указатели могут храниться не всегда, значит, стоит данные просто заинлайнить и словарь после этого всего надо пожать. Т.е. не просто вот такие структурки лежат, как бы…
Как хипстер реализует поиск? Он берет такую фигню, json-документ, и на диск, потом в jQuery грузим…
Но работает недостаточно хорошо, недостаточно эффективно. Поэтому надо, во-первых, не json документ со всеми этими данными, а, естественно, в бинарном формате, а во-вторых, для того, чтобы оно было более-менее компактно и хорошо работало, этот словарик, еще неплохо бы пожать. Для того чтобы был быстрый поиск, строим сортированный вектор. В идеале и при деле, конечно, надо бы для поиска было строить просто хэш, ну, натурально по всем словам построили хэш и потом мгновенный lookup того или иного слова.
Но с хэшом две проблемы:
- мгновенный lookup-то будет, но тогда в словаре необходимо держать совершенно несжатые элементы, а он от этого распухает раза в четыре.
- вдобавок, если у тебя хэш, то в хэше нет никакого диапазонного поиска и, вообще, по физическим ограничениям… Поэтому до свидания, поиск подстрок. В принципе, мы тебя сразу ненавидели, но пользователи постоянно требуют зачем-то. Я бы конечно хэш делал, но на хрена искать подстроки, не понимаю.
Основное счастье сжатия в словаре… Натурально основное, я не приведу сейчас конкретных цифр, что «ровно 37% всего сжатия из-за этого, а остальные 69% из-за другого», но основная масса сжатия в словаре, после того как ты его сортанул, в человеческом, значит, нормальном словаре, достигается за счет префиксности языка. Т.е. люди довольно тупые и ограниченные твари в отличие от роботов, и поэтому словарь всех человеческих языков одновременно крайне невелик. В самом деле, какой лексикон был у Пушкина? Наше все, между прочим, памятник стоит, чуть не в каждом городе, и улицы есть наверняка. А лексикон, дай Бог, 30 тыс лем. Ну сколько всего из этих 30 тыс лем можно сгенерировать словоформ? Не спать, общаться, максимум тысяч 200.
Возьмем кого-нибудь поакадемичнее Пушкина, например, классический морфологический словарь Зализняка и все, что из него постепенно выросло. Порядок в русском языке — 100–200 тыс. лем более-менее ходовых, и, конечно, русский язык еще довольно мутабельный с точки зрения программиста и флективный с точки зрения человека, еще не забывшего филологию, если сразу знал. И это означает, что из каждой конкретной лемы, из каждого конкретного корня можно сгенерировать много разных приставочек — бег, бегу, бежал, бегущий, бегущая и т.д. Таких склонений в русском языке много, поэтому словоформ много. Каждая словоформа в пределе индексируется как отдельное слово. Но даже их, хоть весь словарь посмотри, их жалкие миллионы. Это на самом деле: 1. очень мало, и 2. они похожи друг на друга как близнецы братья.
После того, как ты такой словарь отсортировал лексикографический, у тебя получается… А еще же опечатки, конечно, есть. Человеки — они, как бы, тупые и ограниченные, и это проявляется не только в том, что словарь довольно ограниченный, а еще и в том, что они постоянно норовят как-то по-быдлятски писать. То какой-нибудь олбанский придумают, то подоночий, то просто тупорылые и опечатываются, как я, например, в каждом втором слове, слава Богу, что автокорректоры фиксят. И получается такое вот: абыр, абыррр, абырвалг и т.д.
Нет никакой человеческой возможности хранить на каждый долбанный абыр лишние 8 байт, потому что в Юникоде это будет именно 8 байт. Существенно интересней сохранить один раз префикс «абыр», а потом для «абырр» сохранить, например, edit код небольшой в несколько битиков, что мы короче, сейчас допишем +1 символ в конец, и символ этот сохранить, а потом еще два символа допишем в конец, а потом два отрежем и «валг» сохраним. За счет этого нехитрого трюка словарь, подчеркиваю, человеческого языка сокращается очень существенно.
К несчастью, это ни хрена не помогает против ботов. Ботов ненавижу лютой ненавистью, потому что именно из-за ботов, которые генерят всякие url чмошные, всякие session_ID, utm_campaign и весь прочий фарш сессий — из-за этого, когда ты индексируешь, например, url, словарь у тебя распухает в какие-то адовые дали, и особо сделать с этим ничего нельзя. У тебя такой session_ID случайный совершенно и разрежен, и префиксов там никаких нет. Эта гадость подсирает словарю.
Для нормального языка со словарем все интересно. Вот пожаловался на жизнь, что для всяких автоматически генеренных данных со словарем все плохо. На самом деле плохо, но не плохо-плохо. Словарь в каком-нибудь уродском случае, когда у вас настоящего текста нет, а есть много-много автоматически и случайно генерированных данных, ну, если вы сгенерируете 100 млн. уникальных ключевых слов рандомом и проиндексируете их, естественно, у вас основная масса индексов будет в словаре. У вас, по большому счету, весь индекс выродится в словарь. Но, к счастью, в тех коллекциях, которые обычно принято индексировать, данные более чем осмысленные, поэтому кроме словаря есть еще, собственно, основные данные, документы, позиции.
Я долго рассказывал про префиксы и забыл рассказать про инлайнинг. Инлайнинг — это крайне тупая вещь. Зачем сохранять восьмибитное смещение на документ, если у тебя всего один документ и одна позиция? Этим нехитрым трюком мы несколько лет назад в Sphinx в один удар и один нехитрый upgrade срезали размер индекса, по-моему, то ли на 30%, то ли на 40%. А потом в Lucene у нас эту идею украли, или придумали независимо, что на самом деле вероятней.
Основная часть индекса, тем не менее, — это документы и позиции. Это просто сортированные списки. Всегда сортированные, иначе никак. Иначе их эффективно не пересечь в тот момент, когда ты делаешь поиск по двум ключевым словам одновременно. Наверное, пытаются их не сортировать, а сортировать по какому-то легковесному рангу и т.д. только две категории лиц. Во-первых, это чуваки, которым диссертацию очень надо защитить, а то военком призовет. И вторая категория лиц — это чуваки, которым диссертацию надо защитить, потому что это означает продвижение по внутренней карьерной лестнице в Яндексе и Google. Других научных работ на эту тему я не видел, т.е. не существует каких-нибудь доказательств, что как-то можно ловко и эффективно документы положить в противоестественном порядке, а не в естественном, сортированном по ID порядке. Нельзя по какому-то легковесному рангу уложить в индекс для того, чтобы вынимать топ1000 по этому легковесному рангу для одного слова, а не все 30 млн. документов и, соответственно, топ1000 для другого слова, — это работает достаточно хорошо, но вот люди уже не первый десяток лет пытаются, ни хрена не выходит.
Позиции. Позиции нужны в тот момент, когда вы ищете, во-первых, более одного ключевого слова для того, чтобы сделать ранжирование, во-вторых, когда у вас менее тривиальный поисковый оператор, чем просто «дай мне все и отвали». Понятно, что если вы ищете фразу, то точное совпадение фразы, не говоря уж о поиске поблизости и т.д., вам нужны сразу позиции. Даже если вы потом эти данные ранжировать не будете, просто для того, чтобы сматчить фразу, придется позиции шманать. И если вам нужно хоть какое-то ранжирование, то более-менее толковое ранжирование тоже хочет смотреть в позиции, причем делать это очень медленно.
Этих данных много, их реально много. Сами прикиньте, на каждое вхождение каждого слова в каждый документ мы где-то должны сохранить какой-то внутренний номер документа. На самом деле, для поисковика неважно, внешний номер или внутренний, но мы его должны сохранить. Таких данных, грубо говоря, как минимум сравнимо по размеру с оригинальным текстом, а то, если неаккуратно хранить и много оверхедов, то и во много раз больше оригинального текста. Нет никакой человеческой возможности работать с индексом, который втрое больше, чем размер оригинального проиндексированного текста. Это медленно, нехорошо и, вообще, память жрет. Существенно лучше ловко все пожать, чтобы оно занимало не 300% от размера исходного текста, а в идеале 5%. Когда у тебя данных в 60 раз меньше, то естественным образом любая операция над этими данными работает быстрее.
Сжатие. Сжатие решает все. Внезапно про детали реализации в конкретных поисковиках.
В Lucene на сегодняшний день, насколько я помню, основные данные, которые хранятся, по полнотекстовому индексу выглядят вот так. Отдельно есть поток с блоками пожатых ID документов. Отдельно к нему вдобавок, грубо говоря, в отдельном файле или по отдельным смещениям лежат блоки частот, т.е. не просто факт, что вот у нас документ 1, 2, 3 и 17, а еще факты, что в документе № 1 у нас была частота три раза слово встретилось, в документе № 2 — 17 раз и т.д. Такой блок частот в конкретном документе. Естественным образом этот блок частот определяет длину количества позиций для третьего мегавектора, в котором хранятся конкретные позиции. Там, соответственно, сколько сумма tf в блоке, столько данных и будет лежать в posting«ах.
Соответственно, чуваки хранят это тремя разными стримами. Эти данные лежат не вперемешку. У нас они лежат в текущей версии несколько вперемешку, т.е. docids, tfs, частоты по документам, плюс еще некая мелкая дополнительная метаинформация, конкретно — смещение в список постингов и, по-моему, там какие-то легкие фокусы про число постингов, масочку, которая не всегда есть, и т.д. У нас такая основная кишка лежит для тех, кто интересуется, в файлике индексном с расширением SPD, и отдельно лежит файлик, в котором лежат все позиции.
И опять-таки инлайнинг хорошо работает. Если у тебя есть одна позиция, надо ее сохранить, не надо хранить на нее указатель. В этом случае, если у тебя ровно одна позиция, ровно одно вхождение, оно у нас тоже инлайнится в общую мегакишку документов.
Как будет устроено в свежей версии, которую давно готовим, и про которую я недавно начал рассказывать, я пока не знаю. Предварительно, в прототипчике довольно клево работает расклад, когда у нас, вообще, все данные перемешаны, т.е. и docids и постинги лежат одной ровной кишкой. Это плохо тем, что, когда тебе нужны только идентификаторы документов, и у тебя, грубо говоря, поиск по одному ключевому слову, тебе совершенно наплевать на позиции и вхождения этого слова в документ. Ты больше не имеешь возможности посмотреть в сравнительно маленький в этом случае список идентификаторов документа, выкинуть и не смотреть в номера позиций совсем. Но с другой стороны, таким образом общий размер индекса конкретно уменьшается, и код упрощается. Соответственно, пока не решился. С одной стороны, как бы и хочется все-таки отселить постинги отдельно, как раз для оптимизации таких вот либо однословных поисков, либо булевых поисков, где позиции, вообще, не нужны. А с другой стороны, это сильно раздувает индекс. Еще нужно думать, бенчмаркать и т.д.
Я считаю, будет особенно смешно и иронично, если где-нибудь в зале сидит какой-нибудь засланный казачок из Google, тихо ухмыляется и про себя думает, что «у нас все не так». Это не единственный метод сделать формат, и тем более не единственный верный. Эксперименты с тем, как бы нам половчее сохранить эти данные (списки документов и списки позиций), их много, их надо хранить как-то эффективно, а потом эффективно читать и работать. Эксперименты, наверное, не прекратятся никогда.
Я смутно помню, что когда-то читал какую-то бумажку от Google. Google, вообще, известная «открытая», «open source» компания — ни патча наружу и ни одного документа, устаревшего менее чем на пять лет, наружу отдавать нельзя. Но я читал, тем не менее, документ, который непонятно насколько устарел, где вкратце и вскользь в два слова упоминалось, что в Google еще более интересный формат хранения этого всего. Вместо того чтобы хранить какие-то отдельные списки документов, tfs и прочего, они хранят один гигантский список позиций. Или это какой-то эксперимент был гугловый или боевой индекс? «Открытая» компания, ничего понять нельзя. Но запомнил следующую идею, в любом случае интересную — хранится гигантский общий список позиций, причем плотный. Типа, вот у нас первый документ, в нем 1000 слов, соответственно, он занимает номера позиций с 1-й по 1000-ую, а вот второй документ, в нем 12 слов, он занимает позиции с 1001-ой по 1012-ую, а вот третий документ и т.д. И, как бы, вскользь читал, что клевый формат, типа стало хорошо, а границы документов при этом определяются внешней метаинформацией, т.е. отдельно лежит маленькая такая кишка, в которой конкретные границы документов прописаны, что у нас первый начался с позиции №1 и кончился в №1000, второй — с №1001 и кончился в №1012 включительно и т.д.
Данные лежат вот так — см. слайд выше. В Lucene так, в Sphinx — так, в Sphinx следующей версии — не понятно как, и у «больших дядек» тоже непонятно, как и регулярно меняется. Зачем я все это, вообще, рассказываю? Всем же плевать. Но это хорошо, когда тебе плевать на внутренности того с чем ты собираешься работать, особенно, когда ты пришел на доклад про то, как это внутри работает, но к несчастью, это дело довольно неплохо влияет на две немаловажные характеристики — на скорость работы всего и еще на объем.
Потому что даже просто механизм кодирования данных, которые ты собрался сложить внутрь индекса, меняет объем этих данных и, как минимум, скорость чтения обработки этих данных в время, которое чуть менее чем бесконечность. И насчет «чуть менее чем бесконечность» — это не шутка. Вот пример условно-частотного слова. На самом деле, слово «что» менее частотное. Самое частотное, по-моему, в русском языке, не то, что вы подумали, а предлог «и», но для примера сойдет. Предположим, у нас есть такой список идентификаторов документов [1,3,4,5,6 и т.д]. Он возрастает, и в нем довольно плотные документы. Зачем нам хранить большие числа, которые постепенно, вообще, до миллиона дорастут, и на них надо много бит? Давайте посчитаем дельты между каждыми соседними циферками. Я посчитал, и у меня вышло [1,2,1,1,1,4… и т.д]. Возможно, я где-то обсчитался, но не суть важно. Важно то, что абсолютный порядок циферок во втором векторе, который подписан «varint», существенно меньше. Значит, нехитрый ход, давайте возьмем эти маленькие циферки и закодируем их переменным количеством байт. Семибитные значения — 8 байт, 14-ти битные значения — 16 байт и т.д. Некоторые уже догадались, как это сделать, и буквально за четыре часа напишут реализацию на php и выкинут.
Внезапно, вместо 32-х бит, или не дай Бог, даже 64-х на каждый ID, мы храним, спаси Господи, 8, в среднем. И, конечно, у нас встречаются изредка какие-то уродские пики, когда тут прыжок в основном списке сразу с 11 млн. до 12 млн. Будет 12 млн. минус 11 млн., тут потребуются 24 бита для этого значения, для этой дельты, и она, все равно, закодируется в четыре байта. В три ее уже не закодировать, потому что у тебя будут оверхеды кодирования. Но, в среднем, у тебя будет один байт, а не четыре.
Внезапно, данные схлопнулись в четыре раза, и это наука 20-летней давности. Значит современная наука (т.е. всего 10-летней давности) — это забавные блочные коды, которые, во-первых, еще единичку вычитают, потому что у тебя обязана быть дельта — у тебя номера начинаются с единички, не с нуля. Вычли единичку — сэкономили битик. Получается такая штука и последовательность этих нулей и единичек (изредка троек), их можно закодировать в зависимости от того, как подойти к снаряду, и иногда в 0 (нуль) бит. В смысле, когда у тебя достаточно длинный блок, в котором исключительно нули, т.е. у тебя матчат последовательно много документов — блок, например, из 128 документов подряд, 1,2,3, очень частотное слово. Либо просто ты сграбил посты одного и того же человека с бложика и, очевидно, его погремуха встречается во всех этих документах подряд. И так бывает. Понятное дело, дельты между соседними ID документами по единичке, и все константы, и этот факт можно пожать, условно говоря, в 0 бит на документ, плюс небольшой фиксированный оверхед. Мы пишем один байтик, что, дескать, следующие 128 дельт у нас единичка. Такое счастье в реальных данных встречается крайне редко на самом деле. Если я правильно помню свои эксперименты с кодеком, то такое кодирование блоков именно нулем бит особых радостей не давало, но кодирование достаточно большого блока документов в один, два или три бита по сравнению с восемью, опять-таки, схлопывают размер индекса еще в несколько раз. Эффект, надеюсь, понятен — одно дело, если нам надо прочитать с диска или из памяти 100 Мб и перелопатить. Если бы мы данные не жали совсем, varint пожали 25 Мб, кодек более приличный, значит жмет совсем хорошо. Я считаю, что все-таки важно хотя бы представлять, что там внутри происходит, и зачем, вообще, все эти кодеки нужны, как настраивать и т.д.
Внезапно вспоминаем противный факт, что кроме текста в индексе есть еще те самые божественные циферки, т.е. определенная какая-то метаинформация, привязанная к документу, атрибутивка в той или иной форме. Т.е. данные, которые мы не индексируем полнотекстовым индексатором, но которые, тем не менее, должны тоже присутствовать и состоять, потому что по ним неизбежны дополнительные операции. Очевидные — фильтрация, группировка, сортировка. Менее очевидные — ранжирование, с одной стороны, и просто сторедж, с другой стороны, в тот момент, когда вы внезапно из поиска сделаете кривую базу данных.
К несчастью, человечество придумало много концепций на настоящий момент, и миллион разных методов хранения, и один конкретный еще не победил. Данные, можно сказать, что они у нас как бы реляционные, с жестко заданной заранее схемой. Можно, наоборот, сказать, что мы хотим полного динамизма и разврата, и поэтому у нас полный schemaless. После этого тоже можно сохранить данные по-разному.
Нереляционные можно криво сохранить, с одной стороны, ну, традиционно schemaless принято хранить особо хорошо, т.е., в лучшем случае, в каком-нибудь бинарном форматике.
Меня в этом плане не перестает удивлять история PostgreSQL, которые сделали поддержку json и в первой итерации хранили этот json, грубо говоря, просто текстовым. Вообще, без никаких дополнительных попыток как-то ускорить работу с этим самым json.
Слава Богу, даже Lucene таким ужасным образом данные не хранит, но он, насколько я знаю (здесь я могу дико ошибаться, потому что смотрю в них не каждый день). У них внутри та самая очень гибкая, но, соответственно, при этом тормозная структура, которую я ласково называю ФлексиТормоз, по меньшей мере, такая структура данных используется для хранения дополнительной атрибутивки умолчательным образом. Т.е. когда вы сохраняете атрибут, там не схема естественно делается аля реляционная база данных с дико быстрым доступом, а хранится, условно говоря, json-документ. Или, скорее, bson-документ в некоем бинарном формате, где доступ быстрее, чем парсинг текста. И чтобы все это не так адово тормозило, все обставлено многоуровневыми кэшами, чтобы после первого раза доступ был быстрый, а первый раз доступ был очень медленный.
В Sphinx решение, не сказать, чтобы принципиально лучше, но местами работает, мне кажется, все-таки бодрее. У нас, наоборот, адски реляционный подход, гигантская таблица с фиксированной схемой в памяти, что, понятное дело, неудобно, когда ты туда хочешь заливать разреженные данные типа json. Но мы от нее отказываться, наверное, не хотим, потому что я верю в то, что у человека должен быть выбор — то ли застрелиться в голову, то ли застрелиться в артерию на ноге и истечь кровью. Соответственно, выбор — реляционная схема хранения атрибутов, если ты заранее знаешь, что у тебя в каждом документе есть колонка «прайс» и она флатовая. Это уже не то, чтобы в артерию, но на два пальца на ноге, в принципе, тянет, — флатами цены хранить. Тем не менее, если ты заранее знаешь, что она у тебя в каждом документе есть, заведи ее сразу в схему, она будет клево, эффективно храниться, занимать четыре байта на документ, и доступ к ней будет мгновенный. Не надо ни json парсить, ни по bson скачать, ни через миллион кэшей через Lucene продираться. Но, естественно, схемы иногда меняются и на лету, и местами всякие исключения возникают, поэтому json никто не отменял, у нас поддержка есть и внутренний формат.
Я пытался сделать из себя хорошего разработчика и украсть чью-нибудь хорошую реализацию, но выяснилось, что я плохой разработчик, и поэтому все чужие реализации еще хуже, чем я могу написать, пришлось написать свою.
Кроме хранения атрибутов, мало их просто хранить, еще желательно их как-то индексировать. Этим, насколько я знаю, более-менее прилично пока не занимается никто. Подчеркиваю, здесь ключевое слово «более-менее прилично».
Вроде бы, местами Lucene делает прикольный какой-то совершенно адский фарш с эмуляцией индексов по колонкам, по большому счету, элементами полнотекстового индекса. Это с одной стороны. А родных индексов нет.
И у Sphinx есть не менее монументальное решение. У нас по отдельно взятым блокам записи стоится махонький блочный индекс, чтобы если вдруг в какой-то момент наступил полный перебор всех записей, уже не каждую запись перебирать, а сначала верхний уровень проскакать и какое-то количество блоков откинуть сразу.
Тем не менее, насколько я знаю, в поисковиках никакого креатива с хранением атрибутивки пока нет. Т.е. когда у тебя есть схема, можно креативить — хранить не просто тупую построчную матрицу, а всякие там поколоночные сжатия, поколоночные и пожатые представления делать хотя бы для отдельных колонок. Если у тебя даже схемы нет, тоже все интересно — можно взять этот schemaless документ, сплющить его в облако key-value тегов и потом по этому облаку линейно искать.
Можно и этого не делать, но, слава Богу, текстом никто не хранит. Можно, простите, сделать не просто облако key-value тегов, а хотя бы положить к нему хэшик для быстрого доступа. А можно его не плющить, можно честную иерархию хранить, можно компрессию ключей делать — миллион разных трюков, но до них пока еще поиски, по меньшей мере, open source, не особо доросли. Мы кое над чем работаем, но пока не доработали, я считаю еще немного рановато хвалиться.
Внезапно про ранжирование.
С ранжированием моя текущая гипотеза такая, что ситуаций бывает, по большому счету, две — либо его, вообще, нет, либо в идеале оно вам нужно тяжелое, но вы отделываетесь легким. Т.е. если у вас, вообще, не стоит задача что-то ранжировать, то все прекрасно, булев матчинг, никакой тяжеловесной обработки документов не нужно.
Если у вас, в принципе, качество поиска хоть что-то да значит, если бы вам хотелось, чтобы ранжирование было более интересное, но вы не знаете, как, не умеете или, в принципе, «на трех результатах и так сойдет», то отделываешься какой-нибудь легкой шнягой типа встроенного канонического BM25 ранжирования, придуманного 40 лет назад и везде хорошо описанного. Это натуральная несложная формула, это она только выглядит страшно, на самом деле, в ней две переменные, по большому счету, интегрируются по всем совпавшим словам. TF (term frequency) — частота слова, попавшего в документ, и IDF (inverse document frequency) — обратная частота по коллекции. Это логарифмическая метрика, которая, грубо говоря, равна 0 (нулю) для документов, которые есть везде. Т.е. документ, который есть везде — в каждом документе всей коллекции, он ничего не значит с точки зрения ранжирования. Факт, что мы его нашли — ни о чем. И наоборот, документ, который есть в одном документе из коллекции, вот у него IDF максимальный — 1 (единица). И функция там нелинейная, там логарифм некий определенный, чтобы жизнь медом не казалась. TF — линейный, поэтому TF сглаживает. Здесь вместо F, Q, I, D надо, на самом деле, написать TF, грубо говоря. Но поскольку уже четвертый год руки до фотошопа не доходят, чтобы формулу стыренную из википедии подкрасить, она выглядит более страшно, чем могла бы.
Еще в этой формуле есть третий фактор, этот фактор уже не текстовый — это средняя длина документа. Вон, avgdl в формуле, и avg_doc_length на слайде. Вот эта легкая математика, которая что-то делает с длиной документа, — это нормирование на длину документа. Чем ближе документ к средней длине, тем для этой формулы лучше. Она хорошо изучена, 100 лет всеми используется и дает довольно неплохие результаты, чисто статистические, никак не учитывая позиции.
Она никак не учитывает позиции, и какой-то рэпак, который миллион раз повторяет все ключевые слова и мощно спамит базу по точному совпадению фразы «I feel you», одноименную песню Depeche Mode загоняет на позицию примерно 112. Меня этот гнусный факт напрягал еще 12–14 лет назад, поэтому у нас дефолтнный ранкер сразу в BM25 подмешивает компоненту, основанную на позициях про близость, степень совпадения фразы запроса и документа. Он тоже довольно легковесная в расчетах штука, но смотрит в позиции хоть как-нибудь.
Если надо тяжелое качественное ранжирование, то на самом деле все весело, потому что факторов для того, чтобы хорошо все сделать, скорее всего, много. Ни разу не два. Дело не ограничивается BM25, точнее, BM25 никуда не девается, но вместо родного BM25, надо пользовать всякие модификации, композитить вместе много этих самых BM25, смотреть на дополнительные интересные факторы, посчитанные по тексту, а что еще интересней, смотреть на массу факторов, которые внетекстовые, которые привязаны к конкретному документу. Собственно, именно в этом основная головная боль и машинное обучение у больших поисковиков. Переменных, которые учитываются в этих расчетах, их натурально сотни и тысячи, т.е. 800 факторов на каждый документ, который учитывают в ранжировании — легко, бывает и так. Так вкратце устроено ранжирование. Понятно дело, что как бы про разные аспекты можно отдельный мастер класс дня на три устроить, сначала про общие всякие, про BM25 поговорить, потом про всякие возможные факторы и в машинное обучение полезть…
Дальше следующий внезапный ход. Мы поговорили про некий базовый формат, что ок, есть слово, есть список документов и т.д., а поиски иногда делают вид, что они реалтаймовые. Как это устроено внут
