mufassall

Шпаргалка · Данные и хранение

Движки хранения: B-tree и LSM

15 мин · Продвинутый · mufassall.dtwin.uz/ru/l/storage-engines/

← Открыть урок

Проблема

Парк датчиков шлёт 50 000 показаний в секунду, и B-tree таблица не справляется. Проходим путь записи через LSM-движок: WAL, memtable, SSTable и compaction — и смотрим, чем за это платят чтения.

Чему вы научитесь

  • Почему B-tree переписывает страницы целиком и превращает мелкие записи в случайный IO
  • Как LSM-дерево превращает запись в дозапись: WAL, memtable, flush в SSTable
  • Усиление чтения, Bloom-фильтры и почему compaction может остановить запись
  • Когда выигрывает B-tree, а когда LSM-дерево
Итоговая сцена
30%60%25%40%45%20%75%

Диаграмма как код

Итоговая схема урока в виде текста: вставьте её в 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_l1

Mermaid: последовательность запросов

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, L1

D2

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_l1

PlantUML: последовательность запросов

@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
@enduml

PlantUML: компоненты

@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 x12 x
Мест на одно чтение15
Чтение p993 мс45 мс

Шаги

  1. Кейс Запись попадает в страницу B-дерева

    Каждый датчик раз в несколько секунд присылает показание.

  2. Проблема На 50 000 записей в секунду диск сдаётся

    Парк вырастает до 50 000 записей в секунду.

  3. Решение LSM-дерево: дописать в журнал, сортировать в памяти

    Переходим на LSM-движок.

  4. Кейс Полная memtable становится SSTable

    Когда memtable дорастает до 64 МБ, её замораживают, записи принимает новая пустая, а замороженная пишется на диск как SSTable — отсортированный файл, который больше никогда не меняется.

  5. Проблема Одно чтение проверяет 31 место

    Дашборд просит последнее показание датчика s_1093.

  6. Решение Bloom-фильтр пропускает лишние файлы

    У каждой SSTable появляется Bloom-фильтр: несколько бит на ключ, хранится в памяти.

  7. Решение Compaction сливает файлы в уровень 1

    L0 продолжает расти: новый файл каждые несколько секунд.

  8. Проблема Compaction отстаёт, запись встаёт

    Приходит шторм, все датчики шлют разом, запись подскакивает до 80 000 в секунду.

  9. Решение Дать compaction место и ограничить вход

    Compaction получает шесть потоков вместо двух.

  10. Кейс Чтение диапазона: здесь выигрывает B-tree

    Дашборд просит последний час одного датчика.

  11. Итоги Итоги

    B-tree обновляет данные на месте: быстрые и предсказуемые чтения и диапазоны, но каждая мелкая запись переписывает страницу в случайном месте.

Термины

B-дерево (B-tree)
Структура, которая хранит данные в отсортированных страницах и обновляет их на месте. Чтения и диапазоны быстрые, но каждая мелкая запись переписывает целую страницу в случайном месте.
LSM-дерево
Хранилище, которое дописывает запись в WAL, сортирует её в memtable в памяти и потом сбрасывает на диск файлом SSTable. Запись очень быстрая, плата — усиление чтения и compaction.
WAL (журнал предзаписи)
Каждое изменение сначала дописывается в конец журнала и только потом попадает в основную структуру. Если сервер упал, данные восстанавливаются из этого журнала.