Как Elasticsearch добивается быстрого поиска — секрет инвертированного индекса

«Все проблемы в информатике могут быть решены на другом уровне косвенности».

- Дэвид Дж. Уилер

«Компьютерный мир — это искусство компромисса»

Введение

Несколько недавних проектов использовали Elasticsearch (далее ES) для хранения данных, поиска и анализа данных, поэтому я немного изучил ES. Эта статья организует мой собственный технический обмен.

Эта статья не будет посвящена использованию распределенных технологий и связанных с ними API-интерфейсов в ES, а будет посвящена совместному использованию"Как быстро восстановить ЭП"выше этой темы. Это также та часть, которая меня больше всего интересует в ES перед изучением.

---

Эта статья примерно включает следующее:

• • Различия между традиционными реляционными базами данных и ES

  • Принципы поисковой системы

• Изучите инвертированный индекс

  • Как выглядит перевернутый индекс (список постов -> индекс терминов -> индекс терминов)

  • Несколько советов по списку постов (FOR, Roaring Bitmaps)

  • Как быстро сделать совместный запрос?

2. О поиске

Сначала представьте сценарий поиска, предположим, мы хотим найти древнее стихотворение со словом «до» в содержании стиха,

В чем разница между традиционной реляционной базой данных и реализацией ES?

Если мы используем РСУБД, такую ​​как MySQL, для хранения древних стихов, мы должны использовать такой SQL для запроса

select name from poems where content like "%前%";

Это мы называем методом последовательного сканирования, который должен пройти все записи, чтобы найти совпадение.

Это не только неэффективно, но и не соответствует нашим поисковым ожиданиям. Например, когда мы ищем такие ключевые слова, как «ABCD», мы обычно ожидаем увидеть результаты поиска «A», «AB», «CD». и "Азбука".

Так что есть профессиональные поисковики, такие как наш сегодняшний главный герой — ES.

Принципы поисковой системы

Принцип поиска поисковой системы можно кратко свести к следующим этапам:

• Сканирование контента, фильтрация стоп-слов

  Например, некоторые бесполезные модальные частицы/связки, такие как «的», «了».

• Сегментация контента, извлечение ключевых слов

• Строить на основе ключевых словПеревернутый индекс

• Пользователь вводит ключевые слова для поиска

Здесь мы вводим понятие, которое также находится в центре нашего сегодняшнего анализа -Перевернутый индекс. Это также основная точка знаний ES.

Если вы знакомы с ES, вы должны знать, что ES можно назвать инкапсуляцией Lucene, а реализация инвертированного индекса реализована через API, предоставляемый пакетом jar lucene, поэтому содержимое упомянутого ниже инвертированного индекса на самом деле Содержание люцена.

3. Перевернутый индекс

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

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

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

1. Несколько концепций

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

term

Ключевое слово - это моя собственная манера говорить.В ES ключевое слово называетсяterm.

postings list

Все еще используя приведенный выше пример,{静夜思, 望庐山瀑布}список, соответствующий термину «до». В ES они описываются как совокупность всех идентификаторов документов, содержащих определенный термин. В связи с тем, что целые числа могут быть эффективно сжаты, целые числа лучше всего размещать в списке проводок в качестве уникальных идентификаторов документов, ES будет обрабатывать эти сохраненные документы и преобразовывать их в уникальный целочисленный идентификатор.

Давайте поговорим о диапазоне этого идентификатора.При хранении данных в каждом сегменте ES будет хранить данные в другом сегменте, который является меньшим блоком сегментирования, чем сегмент, и эти сегменты будут регулярно объединяться. В каждом сегменте хранится максимум 2^31 документ, и каждому документу присваивается уникальный идентификатор, начиная с0прибыть(2^31)-1.

Все родственные существительные — это описания, данные в официальных документах ЕС, а источник можно найти в следующих справочных материалах.

2. Внутренняя структура индекса

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

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

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

term dictionary

Так что естьterm dictionary, ES, чтобы быстро найти термин, упорядочивает все термины по порядку и выполняет бинарный поиск. Кажется, это немного знакомо?Не правда ли, это способ индексации MySQL, который напрямую использует дерево B+ для создания индексного словаря, указывающего на проиндексированные данные.

term index

Но вот возникает вопрос, где, по вашему мнению, следует разместить словарь терминов? Должно быть в памяти, верно? Диск ио очень медленный. Так же, как индексы MySQL хранятся в памяти.

Но каковы последствия, если весь словарь терминов хранится в памяти?

взрыв памяти...

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

Так что естьterm index.

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

Это дерево не содержит всех терминов, оно содержит некоторые префиксы терминов (это также сценарий использования словарных деревьев, общих префиксов). С помощью индекса терминов вы можете быстро найти определенное смещение словаря терминов, а затем выполнить поиск с этой позиции по порядку. Так же, как на картинке справа. (Как насчет, например, когда мы просматриваем словарь английского языка, мы находим первое слово, начинающееся с S, или находим первое слово, начинающееся с Sh, а затем ищем последовательно)

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

FST имеет два преимущества:

• Маленький след. Сжатое пространство для хранения за счет повторного использования префиксов и суффиксов слов в словаре.
• Скорость запроса высокая. O(len(str)) сложность времени запроса.

Теория FST более сложная, и в этой статье мы не будем вдаваться в подробности.

Дополнительная литература: https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

Хорошо, теперь мы можем примерно представить, как выглядит инвертированный индекс Lucene.

4. Несколько советов по списку постов

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

• Если список сообщений не сжат, он займет много места на диске.
• Как быстро найти пересечения и объединения по совместному запросу

Что касается того, как сжимать, некоторые люди могут посчитать, что в этом нет необходимости: «Разве список сообщений уже хранит только идентификаторы документов? Вам все еще нужно сжимать?», но если в списке сообщений миллионы идентификаторов документов, компрессия нужна.. (Например, запросить древние поэмы по династиям?) Что касается того, зачем нужно получать пересечение и объединение, то для поиска специально используется ES, и должно быть много совместных запросов (И, ИЛИ).

Согласно приведенным выше идеям, мы сначала рассмотрим, как сжимать.

1. Сжатие

Frame of Reference

В lucene списки сообщений должны быть отсортированными целочисленными массивами. Это дает хорошее преимущество сжатия с помощью дельта-кодирования.

Например, теперь есть список id[73, 300, 302, 332, 343, 372], который преобразуется в инкрементное значение каждого идентификатора относительно предыдущего идентификатора (предыдущий идентификатор первого идентификатора по умолчанию равен 0, а приращение само по себе). Список[73, 227, 2, 30, 11, 29].В этом новом списке все идентификаторы меньше 255, поэтому каждому идентификатору требуется только один байт памяти..

На самом деле ES сделает это более тонко,

Он делит все документы на блоки, каждый блок содержит ровно 256 документов, а затем последовательно кодирует каждый документ отдельно, чтобы вычислить максимальное количество битов, необходимых для хранения всех документов в этом блоке для сохранения каждого идентификатора, и поместить это количество битов в качестве информации заголовка (заголовок) перед каждым блоком. Эта технология называетсяFrame of Reference.

Изображение выше также является примером из официального блога ES (при условии, что в блоке всего 3 файла вместо 256).

Шаги FOR можно резюмировать следующим образом:

После окончательного битового сжатия типы целочисленных массивов расширяются с 4 типов фиксированного размера (8, 16, 32, 64 бит) до 64 типов с [1-64] битами.

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

Roaring Bitmaps (for filter cache)

В ES вы можете использовать фильтры для оптимизации запроса.Запрос фильтра имеет дело только с тем, соответствует ли документ или нет, и не включает операцию оценки документа.Результат запроса может быть кэширован.

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

Алгоритм сжатия Frame Of Reference, о котором мы упоминали выше, хорошо работает для списков сообщений, но не для кэшей фильтров и т. д., которые необходимо хранить в памяти.

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

Для этого типа списка сообщений ES использует другой метод сжатия. Итак, давайте шаг за шагом.

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

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

Он часто используется в качестве индекса в базах данных, системах запросов и поисковых системах, а битовые операции (такие как и для пересечения или для объединения) могут быть распараллелены, что более эффективно.

Однако у растрового изображения есть очевидный недостаток: сколько бы элементов ни использовалось в бизнесе, объем памяти, который он занимает, остается постоянным. Это не подходит для разреженного хранения. В отрасли также существует множество зрелых схем сжатия для разреженных растровых изображений.roaring bitmaps.

Здесь я опишу простым способом, как происходит процесс сжатия,

Разделите идентификатор документа на старшие 16 бит и младшие 16 бит. Агрегируйте старшие биты (используйте старшие биты в качестве ключа и используйте старшие биты как все младшие массивы с одинаковыми старшими битами) и используйте разные контейнеры (структуры данных) для их хранения. по количеству данных в младших битах (длины младших массивов, агрегированных разными старшими битами, различны).

• len

• len>=4096 BitmapContainer использует хранилище растровых изображений

Источник разделительной линии: максимальная сумма стоимости2^16=65536, Предполагая, что хранилище должно быть в растровом формате65536bit=8kb, и способ непосредственного хранения значения, значение 2 байта, всего нужно 4 КБ2byte*4K=8kb. Следовательно, когда общее значение значения меньше 4 КБ, более экономно использовать метод прямого сохранения значения.

Сжатие пространства в основном проявляется в:

• Агрегация высокого порядка (при условии, что в данных имеется 100w одинаковых значений высокого порядка, изначально требовалось 100w2 байта, теперь только 12byte)

• низкобитовое сжатие

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

Это компромисс. Искусство баланса.

2. Совместный запрос

После разговора о сжатии давайте поговорим о запросах на объединение.

Скажем просто: если в запросе есть кеш фильтров, то кеш фильтров напрямую используется для вычисления, то есть битмап используется для вычисления по И или ИЛИ.

Если фильтр запроса не кэшируется, используйте метод пропуска списка для обхода списка сообщений на диске.

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

Использование списка пропуска также принесет еще одно преимущество.Помните, что я сказал ранее, список сообщений хранится на диске с использованием кодировки FOR

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

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

V. Резюме

Давайте сделаем техническое резюме ниже (это немного похоже на мистера Ван Гана 😂)

• Чтобы быстро найти целевой документ, ES использует технологию инвертированного индекса для оптимизации скорости поиска.Хотя потребление места относительно велико, производительность поиска значительно повышается.
• Чтобы быстро найти термин в огромном количестве терминов, сохраняя при этом использование памяти и уменьшая чтение дискового ввода-вывода, lucene использует инвертированную структуру индекса «указатель терминов -> словарь терминов -> список публикаций», черезFSTСжато в память для дальнейшего повышения эффективности поиска.
• Чтобы уменьшить потребление диска списком сообщений, lucene используетFOR(Frame of Reference) технология сжатия, эффект сжатия очень очевиден.
• Оператор фильтра ES используетRoaring BitmapТехнология кэширования результатов поиска, обеспечивающая высокую скорость фильтрации запросов и снижающая потребление дискового пространства.
• В совместном запросе, если есть кеш фильтра, он будет напрямую использовать собственные характеристики растрового изображения, чтобы быстро получить результат совместного запроса, в противном случае используйтеskip listПересечение объединения нескольких списков сообщений, пропуск затрат на обход и экономия некоторых затрат ЦП на декомпрессию данных

Индексирование идей Elasticsearch

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

Итак, вам нужно обратить внимание при использовании Elasticsearch для индексации:

• Поля, которые не нужно индексировать, должны быть четко определены, поскольку по умолчанию индекс создается автоматически.
• Точно так же для полей типа String те, которые не нуждаются в анализе, тоже нужно четко определить, потому что анализ тоже выполняется по умолчанию.
• Очень важно выбрать обычный идентификатор, слишком случайный идентификатор (например, Java UUID) не способствует запросу

Наконец, выбор технологии всегда сопровождается рассмотрением бизнес-сценариев.У каждой базы данных есть свои проблемы (или области знаний), которые нужно решить, соответствующие ее собственной структуре данных, и разные сценарии использования и структуры данных требуют разных индексов для максимизации и ускорения запроса.

Хотя эта статья о том, как Lucene реализует инвертированный индекс, как тщательно рассчитать каждую часть памяти, дисковое пространство и как использовать хитрые битовые операции для ускорения обработки, но подумайте об этом с высокого уровня и сравните с MySQL. , вы обнаружите, что хотя оба являются индексами, но они совершенно разные по реализации. В общих чертах, индекс B-дерева — это структура индекса, оптимизированная для операций записи. Когда нам не нужно поддерживать быстрые обновления, мы можем обменять их на меньший объем памяти, более высокую скорость поиска и другие преимущества за счет предварительной сортировки за счет медленных обновлений, как в ES.

Я надеюсь, что эта статья может принести вам пользу~

Справочная документация

• https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps
• https://www.elastic.co/cn/blog/found-elasticsearch-from-the-bottom-up
• http://blog.mikemccandless.com/2014/05/choosing-fast-unique-identifier-uuid.html
• https://www.infoq.cn/article/database-timestamp-02
• https://zhuanlan.zhihu.com/p/137574234

- END -