Андрей Аксенов ( 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 поговорить, потом про всякие возможные факторы и в машинное обучение полезть…
Дальше следующий внезапный ход. Мы поговорили про некий базовый формат, что ок, есть слово, есть список документов и т.д., а поиски иногда делают вид, что они реалтаймовые. Как это устроено внутри? Здесь должна была быть (но ее нет) картинка, которую все знают, как этот чувак «нет никакой ложки», и он такой: «ни хрена философ». Никакого реалтайма в полноценном понимании термина реалтайм, на самом деле, тоже нет. Т.е. полноценное понимание – это было бы как, если бы натурально индексная структура честно обновлялась в реалтайме.
Полноценного реалтайма в природе нет, потому что список документов, который ассоциирован с каждым словом, потенциально большой и он сжатый, его обновить – это геморрой нечеловеческий. К нему можно, в лучшем случае, что-то дописать в конец – это да, это можно и легко, а всунуть туда в середину какой-нибудь документ практически невозможно. Поэтому для того, чтобы полнотекстовый индекс делал вид, что он реалтаймовый, человечество преследовало много всяких странных концепций. В итоге победила одна – весь реалтайм эмулируется нехитрым образом: когда прилетают новые документы либо новые версии старых документов, то мы создаем новый маленький наноиндекс с этими самыми новыми документами либо новыми версиями. В случае, если это реплейсы, именно новые версии, то в старых существующих индексах (нано они или мега – не важно), мы взводим некие флажки, что дескать, если этот документ найдешь, то ты его не находи, его на самом деле больше нет. И строим каскады таких индексов и постоянно. Чтобы их не становилось три миллиона, мержим и, соответственно, ровно в момент мержа наноиндексов физически вытираем ранее подавленные флажками записи из этого индекса. Вот каноническая технология.
Слово, которое придумали в Lucene, и весь мир теперь знает, оно называется «сегментом». Вот мы и не стали изобретать свою собственную терминологию, у нас те же самые сегменты, концептуально одно и то же. Т.е. нет никакой реалтаймовости, на самом деле. Когда вы льете новые данные в типа реалтайм систему, она создает по ним быстро дополнительный махонький индекс, т.н. сегмент, старые версии, возможно, подавляет kill-листом, масочками или еще как, не суть важно, и когда-нибудь потом, когда два сегмента сольются в экстазе, она эти данные физически удалит. Вся реалтаймовость всегда устроена так. На данный момент нового клевого метода не придумано. Например, сжатые данные, ты иди, внутри zip-архива положи другой zip-архив…
Еще про разную физику, про разные физические отличия, потому что регулярно задают вопрос: «Почему не Lucene?». Особенно меня радует, когда на хабре пишешь статью типа «вот мы делаем кучу улучшений», и первый коммент в стиле «никому они не нужны, убейте себя об стену». Не, мы убьем, конечно, рано или поздно, люди все смертны, но комментарии, что, дескать, никому на хрен не надо ускорение индексации в три раза и какие-то еще приятные плюшки – это весело. Иногда, не то чтобы каждый день, но вопрос задают. Ответ на него такой амбивалентный, двоякий. Концептуально все внутри одинаково. Эта структура со словарем, со списками, сегментами для обеспечения реалтаймовости и прочие радости жизни – она концептуально везде одна. Попробовали всякие разные подходы, лучше всего работает такой. Он везде реализован.
Есть, однако, тонкий момент под названием «детали реализации, разные форматы и т.д.». К несчастью, эти самые «детали реализации, разные форматы и т.д.» местами меняют все, местами на порядки. Навскидку я придумал и написал на слайд три отличия. У нас общий словарь всех слов на все поля всех документов, которые есть, у Lucene, соответственно, на каждое отдельное слово отдельный словарь.
Я все еще хочу когда-нибудь устроить интересный бенчмарк под названием «давайте кинем туда миллион json-документов», и чтобы в каждом поле с уникальным названием. Это не сложно сделать, мне любопытно, как оно себя поведет после этого при поиске по всей коллекции разом. Или я не правильно читаю java-код, что, в принципе, вероятно, но не потому что java – сложный язык, а потому что java провоцирует вас создать 20 разных фабрик, декораторов и прочей ерунды для того, чтобы обернуть четыре строчки кода, которые занимаются актуальной работой. Это мешает. Соответственно, если я через какой-то декоратор неправильно пробился, то возможно не так все плохо, но вроде бы вот так – если сделать сильно много полей, то бедняжка загнется навсегда.
У нас, соответственно, наоборот – не загнется навсегда, но если ты ищешь по низкочастотному и высокоселективному полю, т.е. у тебя есть гигантская коллекция документов, по метру каждый, и к ним махонький тайтл, и ты ищешь по этому тайтлу, там два слова из миллиона. Эффективно иметь отдельный индекс на эти два слова из миллиона, на это отдельное поле, а у нас его не реализовано. У нас лучшее, что реализовано, – это масочка в док листе, но это недостаточно хорошо. Соответственно, мы в этом случае прошманаем весь индекс, а не отдельное конкретное поле, это, в свою очередь, неэффективно.
Разные юзкейсы, разное ломается в разных местах.
У нас таблица атрибутов памяти, про всякие тонкости реализации которой можно долго рассказывать, и возможность в эту таблицу атрибутов пихать просто json-документы в виде отдельных атрибутов. У Lucene реляционки подобной нет, у них документы на диске. Когда мы в последний раз бенчмаркали, у них был удивительно медленный холодный доступ к отдельному полю отдельного документа, но это никогда не видно, потому что у них политика «а ты вхерачь на сервер 64 Гб памяти и из них 62 отдай под кэш».
Физический уровень разный, самые яркие отличия, про которые я знаю, они вот такие. Наверняка есть какие-то еще.
Кроме физики, еще чтобы открыть и по-быстрому закрыть тему под названием «чем Sphinx не Lucene, и как нам обустроить Россию», у меня такое общее впечатление из кода складывается, что концептуально разные подходы к снаряду. Там, где мы предпочитаем что-то не делать, чем делать плохо, а если делаем, то концепция «давайте все уметь быстро-быстро считать, а пользователь сам на своем уровне, на каком надо, закэширует», то у Lucene все наоборот – «давайте потратим кучу памяти, посчитаем хоть как-нибудь, а потом внутри сервера или библиотеки на обоих уровнях (и внутри самой библиотеки и внутри всех серверов) миллион кэшей на разных уровнях, местами даже отключить невозможно».
На самом деле плохи оба подхода. В Sphinx хрен включишь какой-нибудь кэш, который хотелось бы включить на уровне сервера, а в Lucene плохо сделать внятный бенчмарк. Ты его сделал, он на десяти запросах повторил их тысячу раз, ну, замечательно – ты только что померил скорость отдачи из кэша. Причем, потому что кэши хрен отключишь, ты как бы даже если из десяти запросов сделаешь целых 20, то ты все равно погоду на Марсе измеришь.
И тут внезапно история про Xapian. Возводит концепцию в Абсолют. Странная эзотерическая система, которая давно сдохла, ей пользуется наверное только один человек в мире в продакшне, который ее написал, под названием Xapian. Я ее один раз попробовал забенчмаркать. Я запустил какой-то тестовый поиск, она мне отдала результат за 0,000. «Ни хрена» – подумали русские мужики. Я жахнул еще несколько запросов, она отдала еще несколько каких-то там ответов и тоже на 0,000. Я совсем удивился и уже было начал полировать стену, чтобы в этом месте самоубиться, а потом там выгравировали портрет, но все-таки догадался провести второй тест и что-то включить, то ли сортировку по атрибуту, то ли поиск по фразе сделать и т.д. Внезапно тайное стало явным – тупая овца при поиске по отдельным ключевым словам вынимала 10 документов, заранее по какой-то своей никому не нужной магической формуле отсортированных по каждому слову, мерджила вместе эти списки, считало аппроксимацию BM25 и очень быстро отдавала совершенно ненужный резалт в сет. В нем даже точного количества матчей не было, потому что полные списки документов не перебирались, полный матченный резалт сет не считался, а считалась аппроксимация. Типа: «Вот у нас есть миллион документов, это слово встречается в 1%, и это слово в 3%. Саппроксимируем, и так сойдет. Чего, они дебилы, хахаха». Как только включаешь что-то поинтересней этого поиска по ключевику, а он редко когда нужен, и редко, когда дает хороший результаты, производительность сразу падает где-то в 30 раз ниже Sphinx. И на этом я бенчмарк и закончил и свое знакомство с системой тоже.
Не надо недооценивать силу просто тупо багов. Т.е. различия в подходе есть, есть и еще беды в бенчмарках, но я бы хотел еще обратить внимание на то, что всегда неизбежны в отдельно взятых случаях просто втупую жопы в реализациях, в конкретной системе. Вот, неизбежны, и ничего тут.
Мне вспомнилась история про префиксы, потому что она прикольная и показательная. Бенчмаркал как-то раз Lucene на префиксном поиске, не важно на каком, то ли прям префиксном, то ли поиск подстроки, и удивлялся: «А почему так медленно?». Там тогда декораторов принято было писать по 15 всего, а не по 25, поэтому докопаться до проблемы удалось особенно быстро. Выяснилось, что в префиксном поиске реализация на оценку «отлично» в Lucene. Она просто втупую весь словарь перебирала линейно, вообще, весь. Спасибо, что не движком регекспов. Ну, линейный поиск по словарю в 10 млн. ключевых слов – это тоже была очень хорошая идея. Я, как бы, порадовался, и после этого случился эпизод, когда реальность продемонстрировала, что не надо радоваться, когда Sphinx отжёг тоже, с тем же самым кейсом, с поиском подстрок, но несколько в другой ситуации. Некий индекс по словарю, чтобы при поиске подстрок не перебирать 10-ти млн. словарь, вообще, весь линейно, у нас-то сразу был, но ситуацию под названием «а если какая-нибудь сволочь жахнет запрос типа “а*”», не то что бы не предусмотрели, но на наших тестах, она более-менее как-то себя адекватно вела. И тут внезапно у клиентов в продакшне падает сервер, причем не просто падает, а его кнопкой приходится. Причем не той кнопкой, которая ctrl, alt, del, а та кнопка, которая «дернуть из розетки». Вскрытие показало, что клиент немножко ошибся в настройках, мы немножко ошиблись в дефолтах и т.д. и запрос «Журавлев» со звездочкой (*) в конце букву «ё» заменил на пробел, потому что charset_table. После этого остался запрос «в» со звездочкой в конце. И все бы было хорошо, если бы лимит экспансий стоял вменяемый, а не 175 тыс. слов. Уж не помню, было ли это в конфиге, это ошибка конфигурации или ошибка наших дефолтов, не суть важно, но в любом случае, если бы для этих 175 тыс. слов (из которых 174500 слов встречались по одному разу в одном документе) не создавались бы буфера чтения размером в 4 Мб на каждое слово, то серверу бы тоже было немножечко легче. Но ничего, выяснили, от чего он падает, почесали репу, исправили, теперь, значит, у всех все хорошо. И Lucene исправился, и до них дошло, что полный перебор – это не клево, и до нас дошло, что слово, по которому надо прочитать три байта данных, не обязательно читать через буфер размером 4 Мб. Мы теперь всего 8 Кб на него тратим. На самом деле, мы его, вообще, не читаем через буфер, но это уже отдельная сложная история.
Внезапно про бенчмарки. Все знают, что можно правильно бенчмаркать, неправильно бенчмаркать, и вообще. Все знают, что надо сравнивать примерно одинаковое, смотреть время, и потом начинаются мысли о том, что иногда бывают кэши, они чего-то сбивают и т.д. И в идеале надо смотреть среднее время, еще в идеале смотрят гистограмму, считать квантильки, медианы… К несчастью, конкретно в случае с поисковыми системами, а не с бенчмарком селектов базы данных, это подход:
Одинаковый запрос, Карл, одинаковый! Именно в поиске, к несчастью, за счет отсутствия определенной стандартизации, что ли, или еще чего-то, это самое понятие одинакового запроса, этот одинаковый запрос ни хрена не одинаковый. Очень по-разному может внутри считаться.
Вот живой пример, как считается полнотекстовая часть.
Shpinx. Дефолт – мы хотим находить все слова, а это сравнительно быстро обсчитывается, потому что ты берешь самое редкое слово, потом дополнительно уменьшаешь все найденные по самому редкому слову, обфильтровываешь это дело о более частое, о более частое и т.д. Понятное дело, что взять слово, которое встречается в трех документах и потом пофильтровать, оно тебе даст два документа на выходе и огонь. Мержить три документа + 1 млн. документов + 1 млн. документов по второму слову + еще 2 млн. по третьему – это сравнительно медленно. Но зато при этом у нас сравнительно тяжеловесное ранжирование. По дефолту же ранжирование, которое смотрит не только в частоты ключевиков, которые там нашлись, а смотрят еще и в позиции хоть сколько-то, считает не очень тяжелый фактор под названием проксимити, близость запроса и документа, но все-таки считает, и шмонает для этого, подчеркиваю, позиции, а это грубо говоря, минимум вдвое больше работы сразу.
Lucene использует условно медленную реализацию, которая слова вроде как OR’ит, т.е. базовый булев матчинг теоретически медленнее, но зато ранжирование сильно более легковесное. И внезапно эта история про Xapian – улыбаемся и машем. Мы дали заранее прокэшированный, грубо говоря, резалт сет по каждому ключевому слову, который не значит в бою вообще ни хрена.
Вот вам три «одинаковых» запроса. А с точки зрения пользователя, да, они совершенно одинаковые. Мы просто взяли систему и, не приходя в сознание, шарахнули в каждый запрос текстовый «мама, мыла, раму».
И это еще в некотором роде цветочки, потому что момент с внутренними кэшами, так как на слайде написано. Кэши везде, просто ад. Мы в свое время плюнули бенчмаркать определенные штуки, просто потому что не смогли отключить все кэши. Т.е. можно внешний интерфейс некий определенный бенчмаркать в Lucene и просто заваливать его запросами в надежде на то, что эти кэши кончатся. Виртуалочку вставить с 1 Гб памяти и 10 Гб-ный индекс, и удалбливать его запросами. Никаким другим образом не удается обмерить производительность реального кода, который интересно было мерить, а не производительность кэша.
И мой любимый пример, насчет Marketing driven default 3 – это сниппеты, такой отдельно совершенно боком стоящий момент, не всегда и не для всех важный, но очень показательный. Неоднократно, не каждый день, даже, наверное, не каждую неделю, но тем не менее неоднократно, задавали вопрос: «А чего у вас сниппеты такие тормозные прям? В Solr’е, вообще, няшка, работает как ошпаренный кролик на амфетаминах, а у вас тормозище?». Вскрытие показало, что есть три основных момента:
- Во-первых, у нас есть подсветка синтаксиса, а в Solr’е подсветки синтаксиса по дефолту нет, и если ты ее включаешь, он начинает с божьей помощью работать в 10 раз медленнее. Т.е. у нас каждый запрос честно парсится в синтаксическое дерево и быстро работает, в том числе тупорылые запросы, в которых никакого синтаксического дерева нет, а просто навалены ключевые слова пачкой и все. И надо все подсветить.
- Второй момент – то, что у них индекс заранее создан, некая помогающая структура, хотя как ни странно, конкретно для подсветки сниппетов, нам помощь не в 10 раз.
- И мне бальзам на сердце – это называется «оптимизация про 64 Кб». Вы чего думаете, это опять про буфер, который там у нас был 4 Мб и слова читал? Нет, все значительно проще, у Solr’а очень хорошо работает подсветка больших документов, потому что он подсвечивает из них первые 64 Кб и «давай, до свидания». А Sphinx честно подсвечивает все тело и пытается во всем теле документа искать, опять-таки по дефолту. Мы все-таки сделали, по-моему, мычку, для того, чтобы тоже читить и начало подсвечивать.
Это все были ламентации на тему под названием «как правильно бенчмаркать и что такое одинаковый запрос». Одинакового запроса нет. Как правильно бенчмаркать непонятно даже разработчику полнотекстовой системы. И беда. Поэтому для того, чтобы внятно бенчмаркать, к несчастью, надо хотя бы примерно представлять, как все устроено внутри, иначе ваш бенчмарк в лучшем случае окажется несколько некорректным с одной стороны, в худшем случае покажет в продакшне внезапно характеристики ровно в 100 раз хуже, чем были на тестах с другой стороны. Типа кэшики кончатся, хит рейт из 99% станет 1%, и станет все не так.
Итоги.
Вот поиск устроен вот так. Я попытался рассказать, как он, в принципе, устроен на физическом уровне – словарики, документ листы, внезапно сжатие, оно внезапно важно.
Есть ровно две open source системы и мириады всяких коммерческих систем. На самом деле, что те, что другие концептуально устроены совершенно одинаково, никакого прорыва в коммерческих тоже нет. Там внутри такие же словарики, списки, списки, словарики и т.д. Все совершенно одинаково, тем не менее, меняются детали реализации. Ряд деталей реализации тоже попытался подсветить, мол, здесь Lucene делает так, мы делаем немножечко иначе и местами собираемся переделывать и т.д. И из этих деталей реализации и общих подходов к снаряду, под названием «мы хотим честно считать, а они хотят доблестно кэшить», возникают такие странные проблемы, которые специфичны сегодня для поиска под названием «хрен ты меня забенчмаркаешь, у меня внутри такой кэш, такой кэш, что ты всегда будешь бенчмаркать только этот кэш». Невероятно обидно, но факт, данный нам в ощущениях, такой.
Контакты
» shodan@sphinxsearch.com
» shodan
Этот доклад — расшифровка одного из лучших выступлений на конференции разработчиков высоконагруженных систем HighLoad++. Сейчас мы активно готовим конференцию 2016 года — в этом году HighLoad++ пройдёт в Сколково, 7 и 8 ноября.
Также некоторые из этих материалов используются нами в обучающем онлайн-курсе по разработке высоконагруженных систем HighLoad.Guide — это цепочка специально подобранных писем, статей, материалов, видео. Уже сейчас в нашем учебнике более 30 уникальных материалов. Подключайтесь!
Автор:
