С увеличением спроса на операции, которые требуют больших объемов записи, традиционные базы данных, использующие B-дерево, становятся узким местом, поскольку обновление записей в b-дереве приводит к многочисленным беспорядочным операциям ввода-вывода (IO) и обновлению нескольких страниц на диске. B-дерево очень хорошо подходит для "тяжелых" операций чтения. Для операций с большими объемами записи у нас есть LSM-дерево.

Давайте попробуем понять, что такое LSM-дерево, как оно работает на самом деле.

LSM-деревья (Log-Structured Merge) — это тип структуры данных, используемый для эффективного хранения и извлечения больших объемов данных в динамичной и изменяющейся среде.

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

Основная идея LSM-деревьев заключается в объединении преимуществ файловых систем с лог-структурой и B-деревьев.

LSM-деревья работают путем организации данных в серию более мелких, легко управляемых файлов, называемых SSTables (Sorted String Tables).

Что такое SSTables?

SSTables (Sorted String Tables) — строительные блоки LSM-деревьев (Log-Structured Merge). Это дисковые структуры данных, которые хранят информацию в отсортированном формате, что позволяет эффективно искать и извлекать ее оттуда.

SSTables — это результат процесса уплотнения в LSM-деревьях, когда мелкие, несортированные файлы данных объединяются вместе, образуя более крупные, лучше организованные SSTables.

Данные в SST-таблице хранятся в отсортированном виде, что позволяет быстро искать конкретную информацию с помощью алгоритмов двоичного поиска.

Пояснение на примере

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

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

+-------------+-----------+-----------+-----------+
| Employee ID | Name       | Age       | Salary    | Department |
+-------------+-----------+-----------+-----------+
| 1001        | John Doe   | 30        | $50,000   | HR         |
+-------------+-----------+-----------+-----------+
| 1002        | Jane Doe   | 25        | $40,000   | IT         |
+-------------+-----------+-----------+-----------+
| 1003        | Bob Smith | 35        | $60,000   | Sales      |
+-------------+-----------+-----------+-----------+

В этом примере SSTable содержит три пары ключ-значение, по одной для каждой записи о сотруднике.

Ключи — это идентификаторы сотрудников (ID), а значения — остальные поля записи. Ключи отсортированы в порядке возрастания, чтобы обеспечить эффективный двоичный поиск и запросы по диапазону.

Когда выполняется операция чтения, к SSTable обращаются для получения значения, связанного с данным ключом (ID сотрудника). Например, если мы хотим получить запись для идентификатора сотрудника 1002, SSTable будет просмотрена с использованием индекса, чтобы найти соответствующий блок. Затем будет возвращено значение, связанное с ключом 1002.

Я надеюсь, что благодаря этому вы поняли, как работает SSTable.

SSTable обычно содержит следующую информацию:

1. Пары ключ-значение: Основные данные, хранящиеся в SSTable. Каждая пара ключ-значение представляет собой одну запись в базе данных.

2. Фильтр Блума: Структура данных, используемая для быстрого определения наличия или отсутствия ключа в SSTable.

3. Индекс: Структура данных, используемая для сопоставления ключей с соответствующим блоком в SSTable. Это позволяет эффективно выполнять поиск по ключу.

4. Сжатие: SSTables обычно подвергаются сжатию с помощью таких алгоритмов, как Snappy или LZ4, чтобы уменьшить использование дискового пространства.

Фильтр Блума

Фильтр Блума — это структура данных, которая используется для определения того, является ли элемент членом множества или нет. В контексте SSTable фильтр Блума используется для определения того, присутствует ли данный ключ в SSTable или нет.

Фильтр Блума обеспечивает быстрый и эффективный способ проверки наличия ключа без необходимости выполнять полное сканирование диска.

Пояснение на примере

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

Если вероятность присутствия ключа невелика (т.е. фильтр Блума возвращает false), то поиск можно прекратить, сэкономив время и дисковый ввод-вывод. Если ключ, скорее всего, присутствует (т.е. фильтр Блума возвращает true), то можно выполнить поиск в SSTable для получения значения, связанного с ключом.

LSM-деревья считаются динамическими системами хранения данных, поскольку они могут обрабатывать большие объемы информации, которые постоянно изменяются с течением времени.

Как работает LSM-дерево?

LSM-деревья работают путем организации данных в серию небольших, более удобных для управления файлов, называемых SSTables (Sorted String Tables), которые могут быть легко объединены вместе для формирования более крупного индекса. Такой подход обеспечивает быстрое и эффективное хранение данных, а также быстрый доступ к ним.

• Сначала данные добавляются в оперативную память (in-memory) Memtable.

• Когда memtable достигает определенного размера, она сбрасывается на диск и становится новой SSTable.

• Затем SSTable добавляется на самый нижний уровень LSM-дерева.

• По мере записи информации в базу данных создается множество SSTables, которые добавляются на самый нижний уровень LSM-дерева.

• Когда самый нижний уровень LSM-дерева становится слишком большим, SSTables внутри него объединяются вместе, образуя более крупные SSTables, и перемещаются на следующий уровень дерева.

Объединение (мерджинг) SSTables называется уплотнением.

Уплотнение

Уплотнение является важным аспектом LSM-деревьев и играет решающую роль в производительности и эффективности системы хранения данных.

Уплотнение — это процесс объединения нескольких небольших SST-таблиц в более крупные, что уменьшает количество SST-таблиц и объем дискового пространства, используемого данными.

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

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

Уплотнение также помогает поддерживать эффективность и производительность LSM-дерева с течением времени. По мере записи новых данных в систему количество SSTables может увеличиваться, что может замедлить операции чтения и привести к повышению дискового ввода-вывода.

Потеря данных при выключении питания?

Если вы заметили, 1st data [данные, которые компании получают от клиентов напрямую через регистрации, пиксели и cookies на сайте, CRM и другие сервисы] записываются в memTable, которая находится в памяти, а как мы знаем, память волатильна, и данные в ней теряются, если отключается питание или что-то идет не так. Значит, в этом случае наши данные будут потеряны?

Ответ — нет!

В LSM-дереве memtable используется как временная структура хранения для новой информации, которая записывается в базу данных. При отключении питания все данные, которые еще не были выгружены на диск и скомпилированы в SSTable, будут потеряны.

Чтобы предотвратить потерю данных в случае отключения питания, в LSM-деревьях часто реализуется механизм логирования с опережением записи, при котором изменения данных сначала записываются в журнал на диске, а затем фиксируются в memtable.

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

Преимущества LSM-деревьев 

Существует несколько ключевых преимуществ использования LSM-деревьев, в том числе:

1. Высокая пропускная способность записи: LSM-деревья разработаны для обработки рабочих нагрузок с высокой интенсивностью записи, что делает их хорошим выбором для сред с большим объемом входящего трафика записи.

2. Быстрый доступ к данным: LSM-деревья оптимизированы для быстрого доступа к данным, что позволяет оперативно извлекать информацию из больших массивов.

3. Эффективное хранение: Разбивая данные на более мелкие SST-таблицы и объединяя их по мере увеличения размера, LSM-деревья способны эффективно хранить большие объемы информации на диске.

4. Динамичная и изменяющаяся среда: LSM-деревья разработаны для работы с динамичными и изменяющимися данными, что делает их хорошим выбором для сред, где информация постоянно добавляется, обновляется и удаляется.

Недостатки LSM-деревьев 

Хотя LSM-деревья имеют много преимуществ, есть и некоторые недостатки, которые следует учитывать, в том числе:

1. Более интенсивное использование диска: Процесс уплотнения, используемый в LSM-деревьях, может привести к повышенному использованию диска, поскольку на нем может храниться несколько копий одних и тех же данных.

2. Сложность: LSM-деревья могут быть сложными в реализации и обслуживании, и для их правильной настройки и управления может потребоваться высокий уровень квалификации.

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

Надеюсь, эта статья помогла вам понять, что такое LSM-дерево, как оно может использоваться и быть полезным.

Сегодня вечером пройдет открытое занятие, посвященное эффективному использованию Clickhouse в высоких нагрузках. Что рассмотрим:

• SQL диалект,

• физическое хранение данных,

• индексация данных и разреженные индексы,

• различные движки: MergeTree, Log.

Записаться на открытое занятие можно на странице курса «Архитектор высоких нагрузок».