предисловие
С повсеместным продвижением движка mysql Innodb дерево B+ становится все более и более привычным для всех.Не так давно, когда я изучал алгоритм Raft, я наткнулся на структуру данных, похожую на дерево B+ - дерево LSM ( Дерево слияния с логарифмической структурой (Log-Structured-Merge tree) — Дерево слияния с логарифмической структурой), документ, опубликованный GoogleBig TableОчень интересная структура данных файловой организации, упомянутая в , теперь используется во многих промышленных продуктах: HBase, Cassandra, LevelDB, RocksDB и так далее. Сегодня давайте изучим принцип LSM-дерева.
Определение LSM-дерева
Дерево LSM (Log-Structured-Merge-Tree) похоже на дерево B+, оба из которых предназначены для лучшего хранения данных на дисках большой емкости. По сравнению с деревом B+ дерево LSM имеет лучшую производительность случайной записи. Это можно увидеть в одном из отчетов ACM ниже:
Производительность последовательной записи на диск несколько противоречит нашему здравому смыслу.В приведенном выше примере пропускная способность последовательной записи на диск может даже превышать пропускную способность случайной записи в память. LSM-дерево использует это в своих интересах и на несколько порядков повышает пропускную способность случайной записи, преобразовывая случайную запись на диск в последовательную запись. Так как же конвертировать? Давайте сначала рассмотрим его основную идею.
Основная идея LSM-дерева
Дерево LSM будет хранить в памяти все операции вставки, модификации, удаления и др. Когда такие операции достигнут определенного объема данных, они будут записываться на диск пачками. При записи на диск они будут объединены с предыдущими данными. В процессе слияния исходные данные не будут изменены, как дерево B+, а новые данные будут вставлены напрямую, что позволит избежать случайной записи.
Структура LSM-дерева
Структура дерева LSM охватывает память и диск и включает несколько частей, таких как memtable, неизменяемая memtable и SSTable.
memtable
Как следует из названия, memtable — это структура данных в памяти, используемая для хранения последних операций обновления.При записи данных в memtable они будут резервироваться на диск с помощью WAL, чтобы предотвратить потерю данных из-за сбоя питания памяти.
Ведение журнала с опережающей записью (сокращенно WAL) — это семейство методов, используемых в системах реляционных баз данных для обеспечения атомарности и надежности (два свойства ACID). В системах, использующих WAL, все изменения записываются в файл журнала перед фиксацией.
Memtable может использовать структуры данных, такие как таблицы переходов или деревья поиска, для организации данных и поддержания их в порядке. Когда memtable достигает определенного объема данных, memtable будет преобразована в неизменяемую memtable, и для обработки новых данных будет создана новая memtable.
immutable memtable
Как следует из названия, immutable memtable — это неизменяемая структура данных в памяти, которая является промежуточным состоянием, преобразующим memtable в SSTable. Цель состоит в том, чтобы не блокировать записи во время процесса создания дампа. Записи могут обрабатываться новой таблицей памяти без ожидания, поскольку таблица памяти заблокирована.
SSTable
SSTable (Sorted String Table) — это упорядоченный набор пар ключ-значение, который является структурой данных группы дерева LSM на диске. Если SSTable относительно большой, вы также можете построить индекс на основе значения ключа, чтобы ускорить запрос SSTable. На следующем рисунке показана простая структура SSTable:
Данные в memtable в конечном итоге будут преобразованы в SSTable и сохранены на диске, и в будущем будет соответствующая операция слияния журналов SSTable, которая также находится в центре внимания древовидной структуры LSM.
Структуру конечного LSM-дерева можно просто представить следующим рисунком:
Добавление, удаление, изменение и поиск дерева LSM
Основная идея и структура LSM представлены выше.Давайте посмотрим, как они работают вместе, чтобы завершить наиболее распространенный процесс CRUD в системе данных.
операция записи
Операция записи сначала должна записать данные в журнал диска через WAL, чтобы предотвратить потерю данных, а затем данные будут записаны в memtable в памяти Таким образом, операция записи была завершена, и только один диск IO требуется плюс 1 операция с памятью. По сравнению с множественным произвольным дисковым вводом-выводом дерева B+ эффективность значительно повышается. Затем данные в memtable будут объединены в SSTable на диске партиями, изменяя случайную запись на последовательную запись.
удалить операцию
Когда есть операция удаления, нет необходимости удалять соответствующие данные после нахождения соответствующих данных на диске, таких как дерево B+, просто вставьте часть данных в memtable в качестве флага, напримерdelKey:1933, когда операция чтения прочитает этот флаг в memtable, она будет знать, что ключ был удален. Затем при слиянии журналов удаленные данные будут удалены вместе во время процесса слияния.
операция обновления
Операция обновления аналогична операции удаления 000. Она только обрабатывает memtable, записывает флаг, а затем реальная операция обновления задерживается и завершается в момент слияния.
операция запроса
Операция запроса будет очень медленной по сравнению с деревом B+, а операция чтения должна последовательно читать memtable, immutable memtable, SSTable0, SSTable1... Необходимо пройти все коллекции в обратном порядке, и из-за порядка записи и порядка слияния данные в коллекции с меньшим порядковым номером должны быть новее, чем данные в коллекции с большим порядковым номером. Поэтому, как только данные для чтения сопоставляются в процессе обхода в обратном порядке, это должны быть самые последние данные, пока данные возвращаются. Но если данных действительно нет во всех наборах данных, то они будут пройдены напрасно.
Операция чтения выглядит коряво, но, к счастью, операцию чтения можно ускорить с помощью фильтра Блума. Когда фильтр Блума показывает, что в соответствующем SSTable нет данных для чтения, SSTable пропускается.
Фильтр Блума на самом деле представляет собой длинный двоичный вектор и серию функций случайного отображения. Фильтры Блума можно использовать для определения того, находится ли элемент в коллекции. Его преимущество заключается в том, что эффективность использования пространства и время запроса намного больше, чем у общего алгоритма, а недостаток заключается в том, что существует определенная частота неправильного распознавания и сложность удаления.
Существуют также индексные файлы, упомянутые выше, которые также могут ускорить операции чтения.
операция слияния
Из предыдущих операций CRUD операция слияния является наиболее важной операцией дерева LSM.
Операция слияния имеет два основных эффекта:
- Слияние данных в памяти на диск.
- Поскольку слияние данных памяти на диск будет генерировать большое количество небольших наборов, а операции обновления и удаления будут генерировать большое количество избыточных данных, операция слияния может уменьшить количество избыточных данных в наборе и сократить время линейного сканирования во время операции чтения.
В настоящее время широко используются две стратегии слияния: многоуровневая стратегия и уровневая стратегия.
многоуровневая стратегия
Стратегия с многоуровневым размером — это стратегия слияния, принятая HBase.Конкретное содержание заключается в том, что когда определенный размер коллекций достигает определенного числа, эти коллекции объединяются в большую коллекцию. Например, если есть 5 наборов по 50 данных, объедините их в набор из 250 данных. Недостатком этой стратегии является то, что когда коллекция достигает определенного объема данных, операция слияния становится очень трудоемкой.
уровневая стратегия
Уровневая стратегия — это стратегия слияния, принятая LevelDB и RocksDB. Многоуровневая стратегия вызовет всплеск потребления ресурсов ввода-вывода и ЦП, поскольку будет генерировать большой объем данных. Таким образом, уровневая стратегия использует многоуровневую структуру данных для замены оригинальный сбор больших данных.
Уровневая стратегия ограничивает размер коллекции небольшим диапазоном, например 5 МБ, и делит коллекцию на разные уровни. Общий размер набора на каждом уровне фиксирован и увеличивается. Например, первый слой 50 МБ, второй слой 500 МБ.... Когда размер набора данных определенного слоя достигает верхнего предела, файл будет выбран из этого слоя и объединен со следующим слоем или напрямую перемещен на следующий слой. Если во время слияния обнаруживается конфликт данных, данные на следующем уровне отбрасываются, поскольку данные на нижнем уровне всегда обновляются.
При этом уровневая стратегия будет ограничена, кроме первого слоя. Значение ключа каждого другого слоя не будет повторяться. Это достигается за счет устранения избыточных данных при слиянии, тем самым ускоряя скорость линейного сканирования данных в пределах одного слоя.
в заключении
LSM-дерево жертвует небольшой частью производительности чтения и значительно улучшает производительность записи, поэтому оно очень подходит для сценария больше писать и меньше читать, В этом сценарии оно более компетентно, чем дерево B+. Благодаря глубокому пониманию можно обнаружить, что стратегия слияния дерева LSM сильно повлияет на производительность дерева LSM, поэтому соответствующую стратегию следует гибко выбирать в соответствии с конкретными сценариями.
пригласительный билет на танцыКодовая записка Ван Лаомо