Путь запроса

Теперь, когда мы знаем компоненты (MemTable, WAL, SSTable), давай проследим, что происходит, когда твой код делает запись и чтение.

Секрет феноменальной скорости LSM кроется в отсутствии случайных дисковых операций во время записи.

1. Когда приходит запрос на запись, база делает ровно два действия: дописывает лог в WAL (O(1) для диска) и обновляет дерево в MemTable (O(log N) в памяти).
2. Всё! Клиент мгновенно получает ответ «ОК». База не ждет, пока перестроятся индексы на диске, как это делает B+ Tree.
3. Дальнейший перенос данных из переполненной MemTable в SSTable (Flush) происходит асинхронно, в фоновом потоке, вообще не блокируя новые входящие записи.

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

1. RAM-кэши: Сначала ищем в активной MemTable. Если нет — в замороженной MemTable. Если нет — в Block Cache (это кэш горячих блоков диска в оперативной памяти). Если попали сюда — нам повезло (Cache Hit).
2. Поиск по диску: Если в памяти ключа нет, базе придется проверять файлы SSTable на диске, начиная с самых свежих (Level 0) и спускаясь к самым старым (Level N).

Именно поэтому в LSM-деревьях используется гениальная структура данных — Bloom Filter (Фильтр Блума).

Bloom Filter — это очень компактная структура в оперативной памяти (хэш-таблица битов), которая привязана к каждому файлу SSTable. У нее есть только одна задача: экономить обращения к диску.

Когда база хочет проверить SSTable на наличие ключа, она сначала спрашивает Bloom Filter. Он может дать только два ответа:

• «Точно НЕТ»: Фильтр гарантирует, что ключа в файле нет. База пропускает этот файл и не трогает медленный диск.
• «Возможно ДА»: Фильтр говорит, что ключ скорее всего есть (бывают ложноположительные срабатывания). Только тогда база лезет на диск, читает индекс блока и достает сами данные.