оригинал:yetanotherdevblog.com/lsm/
дерево слияния с логарифмической структурой (log-structured merge-treeLSM-дерево) обычно представляет собой структуру данных, используемую при обработке большого количества задач записи. Оптимизируйте путь записи с помощью последовательной записи. LSM-деревья — это множество баз данных (включаяBigTable, Cassandra, Scylla,иRocksDB) за основной структурой данных.
Сортировать таблицу строк
Использование LSM-дереваСортировать таблицу строк(Sorted Strings Table SSTable для краткости) формат сохраняется на диск. Как следует из названия, SSTables — это формат для хранения пар ключ-значение, в котором ключи расположены по порядку. SSTable будет состоять из нескольких именованных сегментов (Segments) упорядоченных файлов. Как только эти сегменты данных записываются на диск, они становятся неизменяемыми. Упрощенный пример выглядит следующим образом:
Мы видим, что пары ключ-значение в каждом сегменте отсортированы по ключу. Далее посмотрим, что такое фрагмент и как он генерируется.
записать данные
Напомним, что LSM-деревья выполняют только последовательную запись. Нам может быть интересно, как данные могут быть записаны последовательно в упорядоченном формате, когда значения записываются в произвольном порядке? Эту проблему можно решить, используя древовидную структуру в памяти. Часто упоминается как таблица памяти (memtable), но основная структура данных обычно представляет собой некоторую форму отсортированного дерева, напримеркрасно-черное дерево. Когда данные записываются, они добавляются в это красно-черное дерево.
Наши записи будут храниться в этом красно-черном дереве до тех пор, пока дерево не достигнет предопределенного размера. Как только красно-черное дерево наберет достаточно записей, оно сбрасывается на диск как сегмент на диск в упорядоченном порядке. Это позволяет нам записывать файлы сегментов последовательно, даже если порядок вставки не фиксирован.
читать данные
Итак, как найти соответствующее значение в SSTable? Простой способ — просканировать сегмент данных, чтобы найти нужный ключ. Начните с самого нового сегмента и сканируйте самый старый сегмент, пока не найдете нужный ключ. Это означает, что сначала мы извлекаем самые последние записанные ключи. Простая оптимизация - держать в памятиразреженный индекс разреженный индекс.
Мы можем использовать этот индекс, чтобы быстро найти смещение значения до и после целевого ключа. Теперь просто отсканируйте небольшую часть каждого файла сегмента в соответствии с этими границами. Давайте рассмотрим сценарий, предположим, мы хотим найти ключ в указанном выше сегменте.dollar. Мы можем выполнить бинарный поиск по разреженному индексу и найтиdollarмеждуdogиdowngradeмежду. Теперь просто просканируйте от смещения 17208 до 19504, чтобы найти значение (или определить, отсутствует ли оно).
Это хорошее улучшение, но что, если искать записи, которых не существует? Все еще нужно перебрать все файлы сегментов и не удается найти целевой ключ.Фильтр Блумаможет помочь нам решить эту проблему. Фильтр Блума — это компактная структура данных, которая сообщает нам, существует ли ключ в наших данных. Мы можем добавлять данные в фильтр по мере их записи и проверять их в начале чтения, чтобы эффективно реагировать на запросы данных, которых не существует.
компрессия
Со временем система накапливает все больше и больше файлов сегментов по мере работы. Эти файлы сегментов необходимо очищать и поддерживать, чтобы количество файлов сегментов не вышло из-под контроля. Этот процесс называется сжатием. Сжатие — это фоновый процесс, который объединяет последовательные старые сегменты в новые.
Как вы можете видеть в приведенном выше примере, сегмент 1 и сегмент 2 имеютdogзначение ключа. Новый сегмент содержит самое последнее записанное значение, поэтому значение из сегмента 2 будет перенесено в сегмент 4. Как только процесс сжатия запишет новый сегмент для входного сегмента, старый файл сегмента будет удален.
удалить данные
Мы говорили о чтении данных и записи данных, но как насчет удаления данных? Как удалить данные из SSTable, если файлы сегментов считаются неизменяемыми? Удаление фактически следует тому же пути, что и запись данных. Всякий раз, когда поступает запрос на удаление, файл с именемtombstone(то есть уникальный токен для ключей, помеченных для удаления).
Пример выше показывает, что ключdogВ какой-то момент в прошлом значение было 52, но теперь оно имеет маркер удаления. Это означает, что если мы получим ключ какdogзапрос, то возвращается ответ, указывающий, что ключ не существует. Это означает, что удаление на самом деле все еще занимает место на диске, что может удивить многих разработчиков. В конце концов маркер удаления будет сжат, так что значение больше не будет существовать на диске.
в заключении
Теперь мы понимаем, как работает механизм хранения дерева LSM:
- Данные записи хранятся в дереве памяти (также известном как таблица памяти). Любые поддерживаемые структуры данных (фильтры Блума и разреженные индексы) также обновляются по мере необходимости.
- Когда это дерево становится достаточно большим, оно сбрасывается на диск с ключами по порядку.
- При чтении данных сначала проверьте фильтр Блума. Если фильтр указывает, что значение не существует, верните, что у клиента нет этого ключа. Если фильтр указывает, что значение существует, мы перебираем файлы сегментов в порядке от нового к старому.
- Для каждого файла сегмента мы проверяем разреженный индекс и сканируем смещение целевого ключа, пока ключ не будет найден. Возвращается, как только значение будет найдено в файле сегмента.