Эта статья организована из:вау 6655.GitHub.IO/elastic это ухо…
Недавно я участвовал в разработке плана предоставления статистического запроса в реальном времени с большим объемом данных (уровень 100 миллионов) на основе Elasticsearch в качестве базовой структуры данных.Я потратил некоторое время на изучение основных теоретических знаний Elasticsearch, отсортировал их вышел и надеялся заинтересоваться Elasticsearch.Знание одноклассников полезно. В то же время, я также надеюсь, что если есть какой-то неправильный контент или сомнения, пожалуйста, укажите на это, обсудите, изучите и добейтесь прогресса вместе.
вводить
Elasticsearch — это распределенная и масштабируемая система поиска и анализа в реальном времени.
Elasticsearch — это поисковая система, основанная на системе полнотекстового поиска Apache Lucene™. Конечно, Elasticsearch не так прост, как Lucene, он не только включает в себя функцию полнотекстового поиска, но и умеет выполнять следующую работу:
- Распределенное хранилище файлов в реальном времени и индексация каждого поля, что делает его доступным для поиска.
- Распределенная поисковая система для аналитики в реальном времени.
- Он может масштабироваться до сотен серверов и обрабатывать петабайты структурированных или неструктурированных данных.
Базовые концепты
Давайте сначала поговорим о файловом хранилище Elasticsearch. Elasticsearch — это база данных, ориентированная на документы. Часть данных здесь является документом. В качестве формата сериализации документов используется JSON, например, следующие пользовательские данные:
{
"name" : "John",
"sex" : "Male",
"age" : 25,
"birthDate": "1990/05/01",
"about" : "I love to go rock climbing",
"interests": [ "sports", "music" ]
}
С хранилищем базы данных, таким как Mysql, легко создать таблицу User с полями balabala и т. д. В Elasticsearch этоДокументация, конечно, этот документ будет принадлежать Пользователютип, различные типы существуют впоказательсреди. Вот простое сравнение терминов Elasticsearch и реляционных данных:
Реляционная база данных ⇒ База данных ⇒ Таблица ⇒ Строка ⇒ Столбцы
Elasticsearch ⇒ Индекс ⇒ Тип ⇒ Документ ⇒ Поля
Кластер Elasticsearch может содержать несколько индексов (баз данных), что означает множество типов (таблиц). Эти типы содержат много документов (строк), а затем каждый документ содержит много полей (столбцов).
Для взаимодействия с Elasticsearch можно использовать Java API, а можно напрямую использовать метод HTTP Restful API, например, если мы планируем вставить запись, мы можем просто отправить HTTP-запрос:
PUT /megacorp/employee/1
{
"name" : "John",
"sex" : "Male",
"age" : 25,
"about" : "I love to go rock climbing",
"interests": [ "sports", "music" ]
}
Обновление, запрос также аналогичен этой операции, конкретное руководство по эксплуатации может ссылаться наПолное руководство по Elasticsearch
показатель
Самое главное в Elasticsearch — предоставить мощные возможности индексации.На самом деле, эта статья из InfoQСекреты баз данных временных рядов (2) — индексированиеЭто очень хорошо написано. Я здесь, чтобы еще больше разобраться в этой статье, основываясь на своем собственном понимании, и я надеюсь, что это поможет вам лучше понять эту статью.
Суть индексации Elasticsearch:
Все предназначено для повышения эффективности поиска
Другое значение: Для повышения производительности поиска неизбежно приходится жертвовать некоторыми другими аспектами, такими как вставка/обновление, иначе другие базы данных не нужно смешивать :)
Как было показано ранее, вставка записи в Elasticsearch на самом деле представляет собой прямую операцию PUT объекта json, который имеет несколько полей, таких как в приведенном выше примере.name, sex, age, about, interests, затем при вставке этих данных в Elasticsearch Elasticsearch автоматически [^1] создает индекс для этих полей — инвертированный индекс, поскольку основной функцией Elasticsearch является поиск.
Как Elasticsearch обеспечивает быструю индексацию
В статье InfoQ говорится, что инвертированный индекс, используемый Elasticsearch, быстрее, чем индекс B-Tree реляционной базы данных.Почему?
Что такое индекс B-Tree?
Когда я учился в колледже, мой учитель учил нас, что эффективность поиска бинарного дерева равна logN, и нет необходимости одновременно перемещать все узлы, чтобы вставить новый узел, поэтому использование древовидной структуры для хранения индекса может одновременно учитывать производительность вставки и запроса.
Следовательно, исходя из этого, в сочетании с характеристиками чтения диска (последовательное чтение/случайное чтение), традиционная реляционная база данных использует такую структуру данных, как B-Tree/B+Tree:
Чтобы повысить эффективность запроса и уменьшить количество обращений к диску, несколько значений хранятся в виде массива через непрерывный интервал, и несколько данных считываются за один поиск, что также уменьшает высоту дерева.
Что такое инвертированный индекс?
Продолжая приведенный выше пример, предположим, что есть несколько частей данных (для простоты удалите два поля «о себе» и «интересы»):
| ID | Name | Age | Sex |
|---|---|---|---|
| 1 | Kate | 24 | Female |
| 2 | John | 24 | Male |
| 3 | Bill | 29 | Male |
Идентификатор — это идентификатор документа, созданный Elasticsearch, тогда индекс, созданный Elasticsearch, выглядит следующим образом:
Name:
| Term | Posting List |
|---|---|
| Kate | 1 |
| John | 2 |
| Bill | 3 |
Age:
| Term | Posting List |
|---|---|
| 24 | [1,2] |
| 29 | 3 |
Sex:
| Term | Posting List |
|---|---|
| Female | 1 |
| Male | [2,3] |
Posting List
Elasticsearch установил инвертированный индекс для каждого поля, Kate, John, 24, Female называются терминами, а [1,2] —Posting List. Размещение в списке - это массив INT, который хранит все идентификаторы документов, которые соответствуют сроку.
Смотрите здесь, я не думаю, что это закончилось, увлекательная часть только началась...
Кажется, что для быстрого поиска можно использовать метод индексирования списка постов, например, если вы ищете одноклассника возрастом = 24, Сяомин, который любит отвечать на вопросы, сразу же поднял руку и ответил: я знаю, одноклассник с id 1 и 2. Но что, если здесь десятки миллионов записей? Что делать, если вы хотите искать по имени?
Term Dictionary
Чтобы быстро найти термин, Elasticsearch сортирует все термины, ищет термины бинарным методом, а эффективность поиска logN такая же, как поиск по словарю.Term Dictionary. Глядя на это сейчас, кажется, что это похоже на то, как традиционные базы данных проходят через B-Tree.Почему это быстрее, чем запрос B-Tree?
Term Index
B-Tree повышает производительность запросов, уменьшая количество обращений к диску. Elasticsearch также использует ту же идею. Он ищет термины непосредственно в памяти и не читает диск. Однако, если терминов слишком много, словарь терминов будет очень большой, и в память его нереально поместить, так что придетсяTerm Index, так же, как страница индекса в словаре, какие термины стоят в начале А, и какие страницы соответственно, можно понять, что индекс термина - это дерево:
Это дерево не будет содержать все термины, оно будет содержать некоторые префиксы терминов. С помощью указателя терминов можно быстро найти смещение словаря терминов, а затем выполнить последовательный поиск с этой позиции.
Таким образом, индексу терминов не нужно сохранять все термины, а просто отображать отношения между некоторыми их префиксами. Словарь терминов блока в сочетании с технологией сжатия FST (Finite State Transducers), индекс терминов может быть кэширован в памяти. . После того, как найден соответствующий блок из индекса словаря терминов местоположения, перейдите на диск, чтобы найти термин, что значительно сокращает количество случайных чтений с диска.
В это время Сяо Мин, который любит задавать вопросы, снова поднял руку: «Этот FST — бог Ма Дундун?»
С первого взгляда я знаю, что Сяо Мин — ребенок, который не слушал лекции так серьезно, как я, когда он учился в колледже.Должно быть, учитель структуры данных говорил о том, что такое FST. Но никак, я тоже забыл, вот еще один урок:
FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.
Предположим, теперь мы хотим сопоставить mop, moth, pop, star, stop и top (префикс термина в индексе термина) с порядковыми номерами: 0, 1, 2, 3, 4, 5 (позиция блока в словаре терминов). Самый простой способ сделать это — определить Map
⭕️ представляет государство
--> Обозначает процесс изменения состояния, буквы/цифры выше обозначают изменение состояния и вес
Разделите слово на отдельные буквы с помощью ⭕️ и -->, и вес 0 не будет отображаться. Если после ⭕️ есть ответвление, отметьте вес, и, наконец, веса на всем пути складываются в порядковый номер, соответствующий слову.
FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.
FST хранит все термины в байтах.Этот метод сжатия может эффективно сократить пространство для хранения, сделав индекс термина достаточным для размещения в памяти, но этот метод также требует больше ресурсов ЦП при поиске.
Последняя часть более захватывающая.Студенты, которые устали от просмотра, могут выпить чашечку кофе...
Советы по сжатию
В дополнение к использованию FST для сжатия индекса терминов, упомянутого выше, Elasticsearch также имеет методы сжатия для списка публикаций. Сяо Мин снова поднял руку после того, как выпил кофе: «Разве в списке сообщений уже хранятся только идентификаторы документов? Вам все еще нужно его сжать?»
Ах, мы обращаемся к началу примеру, если Elasticsearch студенты нуждаются в гендерном индексе (на этот раз традиционная реляционная база данных уже слабый крик в туалете ......), Что произойдет? Если есть десятки миллионов студентов, и только в мире мужской / женский пол, так что два, каждый список пост, будет иметь хотя бы один миллион документов ID. Elasticsearch Насколько эффективны эти документы ID сжимают его?
Frame Of Reference
Инкрементное кодирование и сжатие, преобразование больших чисел в десятичные и сохранение их в байтах
Во-первых, Elasticsearch требует, чтобы список постинга был в порядке (чтобы повысить производительность поиска, какими бы капризными не были требования), одно из преимуществ этого — его удобно сжимать, см. легенда:
Если математику не преподает учитель физкультуры, легче увидеть этот прием компрессии.
Принцип состоит в том, чтобы изменить исходное большое число на десятичное путем увеличения, сохранить только возрастающее значение, а затем выполнить тщательный расчет и упорядочить очередь в соответствии с битом и, наконец, сохранить его в байтах, вместо того, чтобы быть небрежным, даже если это 2, используйте int (4 байта) для хранения.
Roaring bitmaps
Когда дело доходит до растровых изображений Roaring, мы должны начать с растрового изображения. Bitmap — это структура данных, при условии, что есть список публикаций:
[1,3,4,7,10]
Соответствующее растровое изображение:
[1,0,1,1,0,0,1,0,0,1]
Очень интуитивно понятное, используйте 0/1, чтобы указать, существует ли определенное значение. Например, значение 10 соответствует 10-м биту, а соответствующее значение бита составляет 1, так что один байт может представлять 8 идентификаторов документов, старую версию ( До 5,0). Луче сжимается таким образом, но этот метод сжатия все еще недостаточно эффективна. Если есть 100 миллионов документов, это требует 12,5 МБ пространства для хранения, которое соответствует только одному индексу (у нас часто есть много индексов) Отказ Поэтому кто-то придумал более эффективную структуру данных, такую как ревеющие растровые изображения.
Недостатком растрового изображения является то, что пространство для хранения растет линейно с количеством документов, Ревущие растровые изображения должны использовать некоторые экспоненциальные функции, чтобы разрушить это проклятие:
Разделите список публикаций на блоки 65535. Например, первый блок содержит идентификаторы документов в диапазоне от 0 до 65535, второй блок содержит идентификаторы в диапазоне от 65536 до 131071 и так далее. Затем используйте комбинацию для представления каждой группы идентификаторов, чтобы диапазон идентификаторов в каждой группе находился в пределах от 0 до 65535, а с остальными было легко справиться.Поскольку каждая группа идентификаторов не станет бесконечной, тогда мы можем сохранить идентификатор здесь наиболее эффективным способом.
В это время осторожный Сяо Мин снова поднял руку: «Почему 65535 — это предел?»
В мире программистов, в дополнение к 1024, 65535 также является классическим значением, потому что оно = 2^16-1, что является самым большим числом, которое может быть представлено 2 байтами, короткой единицей хранения, обратите внимание на последнее в выше. Строка «Если блок имеет более 4096 значений, закодировать как набор битов, а иначе как простой массив, используя 2 байта на значение», если это большой блок, сохраните его в наборе бит, сохраните его в bitset, и сохранить небольшой блок, 2 мне плевать на байты, удобно использовать шорт[].
Так зачем использовать 4096, чтобы различать порог между массивом и растровым изображением?
Это считается из размера памяти.Когда элементы в блочном блоке превышают 4096, используйте растровое изображение, чтобы оставить больше места: Пространство, необходимое для использования растрового изображения, является постоянным: 65536/8 = 8192 байта. И если используется short[], необходимое пространство: 2*N (N — количество элементов массива) Щепотка пальца Сяо Мина N = 4096 — это всего лишь граница:
совместный указатель
Как упоминалось выше, это индекс одного поля в течение длительного времени.Если используется совместный запрос нескольких индексов полей, как инвертированный индекс может соответствовать требованиям быстрого запроса?
- Используйте структуру данных Skip list, чтобы выполнить быструю операцию AND, или
- Побитовое И с использованием набора битов, упомянутого выше
Сначала посмотрите на структуру данных таблицы переходов:
Возьмите упорядоченный связанный список уровня 0 и выберите несколько элементов уровня 1 и уровня 2. Чем выше каждый уровень, тем меньше элементов-указателей выбрано. При поиске ищите от высокого уровня к низкому уровню, например 55, сначала найдите уровень 2 31, затем найдите 47 уровня 1 и, наконец, найдите 55, всего 3 поиска, эффективность поиска эквивалентна эффективности 2-арного дерева, но это также обменивается на определенную избыточность пространства.
Предположим, что есть следующие три списка рассылки, которым нужен совместный индекс:
Если вы используете набор битов, это очень интуитивно понятно, и результатом является финальное пересечение.
Подведите итоги и подумайте
Идея индекса Elasticsearch:
Максимально переместите содержимое диска в память, уменьшите количество случайных чтений с диска (а также используйте функцию последовательного чтения диска), комбинируйте различные хитроумные алгоритмы сжатия и используйте память с жестким отношением .
Поэтому вам нужно обратить внимание при использовании Elasticsearch для индексации:
- Поля, которые не нужно индексировать, должны быть четко определены, поскольку по умолчанию индекс создается автоматически.
- Таким же образом, для полей типовой строки, те, которые не нуждаются в анализе, также необходимо четко определено, поскольку по умолчанию также анализируется по умолчанию.
- Очень важно выбрать обычный идентификатор, а слишком случайные идентификаторы (например, java UUID) не подходят для запросов.
Что касается последнего пункта, я лично думаю, что есть несколько факторов:
Один (возможно, не самый важный) фактор: рассмотренные выше алгоритмы сжатия сжимают большое количество ID в Posting list.Если ID идут последовательно, или имеют общий префикс и другие ID с определенной регулярностью, коэффициент сжатия будет выше;
Еще один фактор: Это может больше всего повлиять на производительность запроса.Последним шагом должен быть поиск информации о документе на диске по идентификатору в Posting list, потому что Elasticsearch хранится в сегментах, а сегмент расположен в соответствии с большим -scale Термин идентификатора. Эффективность напрямую влияет на производительность конечного запроса. Если идентификатор является обычным, сегменты, не содержащие идентификатор, можно быстро пропустить, тем самым уменьшив количество ненужных операций чтения с диска. Подробнее см. в этой статье.Как выбрать эффективную схему глобальной идентификации(Комментарии тоже велики)
Последующие, в сочетании с фактическим разработкой и настройкой работы, чтобы поделиться дополнительным контентом, поэтому оставаться настроенными!
Личный публичный аккаунт WeChat:
Персональный гитхаб:
личный блог: