Шпаргалка · Данные и хранение
Движки хранения: B-tree и LSM
Проблема
Парк датчиков шлёт 50 000 показаний в секунду, и B-tree таблица не справляется. Проходим путь записи через LSM-движок: WAL, memtable, SSTable и compaction — и смотрим, чем за это платят чтения.
Чему вы научитесь
- Почему B-tree переписывает страницы целиком и превращает мелкие записи в случайный IO
- Как LSM-дерево превращает запись в дозапись: WAL, memtable, flush в SSTable
- Усиление чтения, Bloom-фильтры и почему compaction может остановить запись
- Когда выигрывает B-tree, а когда LSM-дерево
Диаграмма как код
Итоговая схема урока в виде текста: вставьте её в Jira, GitLab, GitHub, Notion или документацию, там Mermaid рисуется сам. Есть варианты для D2 и PlantUML (Confluence, IntelliJ).
Mermaid: схема
flowchart LR
n_sensors(["Датчики"])
n_ingest["Сервис приёма"]
n_wal[["WAL"]]
n_memtable{{"Memtable"}}
n_l0[("SSTable L0")]
n_dash["API дашборда"]
n_compact("Compaction")
n_l1[("SSTable L1")]
n_sensors --> n_ingest
n_ingest --> n_wal
n_ingest --> n_memtable
n_memtable --> n_l0
n_dash --> n_memtable
n_dash --> n_l0
n_l0 --> n_compact
n_compact --> n_l1
n_dash --> n_l1Mermaid: последовательность запросов
sequenceDiagram
participant n_ingest as Сервис приёма
participant n_table as B-tree таблица
participant n_wal as WAL
participant n_memtable as Memtable
participant n_l0 as SSTable L0
participant n_dash as API дашборда
participant n_compact as Compaction
participant n_l1 as SSTable L1
Note over n_ingest,n_table: Запись попадает в страницу B-дерева
n_ingest->>n_table: INSERT INTO readings (sensor_id, ts, value)
n_table-->>n_ingest: INSERT 0 1
Note over n_ingest,n_table: На 50 000 записей в секунду диск сдаётся
n_ingest->>n_table: LOG: checkpoint complete
Note over n_ingest,n_wal: LSM-дерево: дописать в журнал, сортировать в памяти
n_ingest->>n_wal: APPEND 000412.log offset=88123904 len=64
n_wal-->>n_ingest: fsync: 0.4 ms
Note over n_memtable,n_l0: Полная memtable становится SSTable
n_memtable->>n_l0: flush memtable #35;57
Note over n_dash,n_l0: Одно чтение проверяет 31 место
n_dash->>n_l0: GET s_1093/latest
n_l0-->>n_dash: memtable: miss
Note over n_dash,n_l0: Bloom-фильтр пропускает лишние файлы
n_dash->>n_l0: GET s_1093/latest
n_l0-->>n_dash: memtable: miss
Note over n_compact,n_l1: Compaction сливает файлы в уровень 1
n_compact->>n_l1: compact L0 -#62; L1
Note over n_ingest,n_memtable: Compaction отстаёт, запись встаёт
n_ingest->>n_memtable: WARN write stall
Note over n_l0,n_compact: Дать compaction место и ограничить вход
n_l0->>n_compact: compaction threads: 6 (was 2)
Note over n_dash,n_l1: Чтение диапазона: здесь выигрывает B-tree
n_dash->>n_l1: SCAN s_1093 from 09:00 to 10:00
n_l1-->>n_dash: merge iterators: memtable, 3 x L0, L1D2
direction: right
n_sensors: "Датчики" {
shape: rectangle
}
n_ingest: "Сервис приёма" {
shape: rectangle
}
n_wal: "WAL" {
shape: queue
}
n_memtable: "Memtable" {
shape: hexagon
}
n_l0: "SSTable L0" {
shape: stored_data
}
n_dash: "API дашборда" {
shape: rectangle
}
n_compact: "Compaction" {
shape: rectangle
style.multiple: true
}
n_l1: "SSTable L1" {
shape: stored_data
}
n_sensors -> n_ingest
n_ingest -> n_wal
n_ingest -> n_memtable
n_memtable -> n_l0
n_dash -> n_memtable
n_dash -> n_l0
n_l0 -> n_compact
n_compact -> n_l1
n_dash -> n_l1PlantUML: последовательность запросов
@startuml
participant "Сервис приёма" as n_ingest
database "B-tree таблица" as n_table
queue "WAL" as n_wal
collections "Memtable" as n_memtable
database "SSTable L0" as n_l0
participant "API дашборда" as n_dash
participant "Compaction" as n_compact
database "SSTable L1" as n_l1
note over n_ingest, n_table : Запись попадает в страницу B-дерева
n_ingest -> n_table : INSERT INTO readings (sensor_id, ts, value)
n_table --> n_ingest : INSERT 0 1
note over n_ingest, n_table : На 50 000 записей в секунду диск сдаётся
n_ingest -> n_table : LOG: checkpoint complete
note over n_ingest, n_wal : LSM-дерево: дописать в журнал, сортировать в памяти
n_ingest -> n_wal : APPEND 000412.log offset=88123904 len=64
n_wal --> n_ingest : fsync: 0.4 ms
note over n_memtable, n_l0 : Полная memtable становится SSTable
n_memtable -> n_l0 : flush memtable #57
note over n_dash, n_l0 : Одно чтение проверяет 31 место
n_dash -> n_l0 : GET s_1093/latest
n_l0 --> n_dash : memtable: miss
note over n_dash, n_l0 : Bloom-фильтр пропускает лишние файлы
n_dash -> n_l0 : GET s_1093/latest
n_l0 --> n_dash : memtable: miss
note over n_compact, n_l1 : Compaction сливает файлы в уровень 1
n_compact -> n_l1 : compact L0 -> L1
note over n_ingest, n_memtable : Compaction отстаёт, запись встаёт
n_ingest -> n_memtable : WARN write stall
note over n_l0, n_compact : Дать compaction место и ограничить вход
n_l0 -> n_compact : compaction threads: 6 (was 2)
note over n_dash, n_l1 : Чтение диапазона: здесь выигрывает B-tree
n_dash -> n_l1 : SCAN s_1093 from 09:00 to 10:00
n_l1 --> n_dash : merge iterators: memtable, 3 x L0, L1
@endumlPlantUML: компоненты
@startuml
left to right direction
agent "Датчики" as n_sensors
component "Сервис приёма" as n_ingest
queue "WAL" as n_wal
stack "Memtable" as n_memtable
storage "SSTable L0" as n_l0
component "API дашборда" as n_dash
collections "Compaction" as n_compact
storage "SSTable L1" as n_l1
n_sensors --> n_ingest
n_ingest --> n_wal
n_ingest --> n_memtable
n_memtable --> n_l0
n_dash --> n_memtable
n_dash --> n_l0
n_l0 --> n_compact
n_compact --> n_l1
n_dash --> n_l1
@endumlИтог
B-tree обновляет данные на месте: быстрые и предсказуемые чтения и диапазоны, но каждая мелкая запись переписывает страницу в случайном месте. LSM-дерево дописывает и сортирует потом: очень быстрая запись ценой усиления чтения и compaction.
B-tree — для данных с преобладанием чтения, транзакций и диапазонных запросов. LSM — для потоков с преобладанием записи: события, метрики, логи. В LSM следите за тремя числами: файлы в L0, ожидающий compaction и write stall.
Показатели: в начале и в конце
| Показатель | В начале | В конце |
|---|---|---|
| Принято записей | 8 000/с | 50 000/с |
| Усиление записи | 10 x | 12 x |
| Мест на одно чтение | 1 | 5 |
| Чтение p99 | 3 мс | 45 мс |
Шаги
- Кейс Запись попадает в страницу B-дерева
Каждый датчик раз в несколько секунд присылает показание.
- Проблема На 50 000 записей в секунду диск сдаётся
Парк вырастает до 50 000 записей в секунду.
- Решение LSM-дерево: дописать в журнал, сортировать в памяти
Переходим на LSM-движок.
- Кейс Полная memtable становится SSTable
Когда memtable дорастает до 64 МБ, её замораживают, записи принимает новая пустая, а замороженная пишется на диск как SSTable — отсортированный файл, который больше никогда не меняется.
- Проблема Одно чтение проверяет 31 место
Дашборд просит последнее показание датчика
s_1093. - Решение Bloom-фильтр пропускает лишние файлы
У каждой SSTable появляется Bloom-фильтр: несколько бит на ключ, хранится в памяти.
- Решение Compaction сливает файлы в уровень 1
L0 продолжает расти: новый файл каждые несколько секунд.
- Проблема Compaction отстаёт, запись встаёт
Приходит шторм, все датчики шлют разом, запись подскакивает до 80 000 в секунду.
- Решение Дать compaction место и ограничить вход
Compaction получает шесть потоков вместо двух.
- Кейс Чтение диапазона: здесь выигрывает B-tree
Дашборд просит последний час одного датчика.
- Итоги Итоги
B-tree обновляет данные на месте: быстрые и предсказуемые чтения и диапазоны, но каждая мелкая запись переписывает страницу в случайном месте.
Термины
- B-дерево (B-tree)
- Структура, которая хранит данные в отсортированных страницах и обновляет их на месте. Чтения и диапазоны быстрые, но каждая мелкая запись переписывает целую страницу в случайном месте.
- LSM-дерево
- Хранилище, которое дописывает запись в WAL, сортирует её в memtable в памяти и потом сбрасывает на диск файлом SSTable. Запись очень быстрая, плата — усиление чтения и compaction.
- WAL (журнал предзаписи)
- Каждое изменение сначала дописывается в конец журнала и только потом попадает в основную структуру. Если сервер упал, данные восстанавливаются из этого журнала.