LSM tree и SSTable

Мотивация

B-tree прекрасно работает на чтение, но каждая вставка потенциально вызывает split и случайную запись на диск. На HDD это катастрофа; на SSD -- истирание ячеек (write wear). Time-series и аналитические нагрузки пишут в тысячи раз больше, чем читают.

LSM tree (Log-Structured Merge tree, O'Neil et al., 1996) меняет правила:

• Все записи сначала идут в память (MemTable) и append-only в WAL.
• Когда MemTable заполняется, она дампится на диск как SSTable (Sorted String Table) -- отсортированный immutable файл.
• Старые SSTables периодически сливаются (compaction) в более крупные.

Результат: запись становится последовательной. Sequential writes на SSD быстрее random на 2-3 порядка, на HDD -- на 4+.

Схема работы

Clients writes
      │
      ▼
  ┌─────────┐         ┌─────────────┐
  │ MemTable│ ──flush→│ Level 0 SST │  immutable
  │  (RAM,  │         └──────┬──────┘
  │  sorted)│                │ compact
  │         │                ▼
  └────┬────┘         ┌─────────────┐
       │              │ Level 1 SST │
       │              └──────┬──────┘
       ▼                     │ compact
  ┌─────────┐                ▼
  │   WAL   │         ┌─────────────┐
  │ (append)│         │ Level 2 SST │
  └─────────┘         └─────────────┘
                            ...
                      ┌─────────────┐
                      │ Level N SST │  largest, oldest
                      └─────────────┘

MemTable

In-memory структура для буфера записей. Чаще всего -- skip list (LevelDB, RocksDB) или red-black tree. Поддерживает concurrent inserts и sorted iteration.

Write path:

1. Запись в WAL (append, fsync при durability-требовании).
2. Запись в active MemTable.
3. Если MemTable достигла порога (~64 MB) -- становится immutable, создаётся новая.
4. Фоновый flush пишет immutable MemTable на диск как SSTable.

SSTable (Sorted String Table)

Immutable файл из отсортированных пар (key, value). Структура:

SSTable layout (simplified):

+--------------------------+
| Data blocks (sorted KVs) |  ← main content, ~4 KB each
+--------------------------+
| Filter block (Bloom)     |  ← skip SSTable if key absent
+--------------------------+
| Index block              |  ← key → offset of data block
+--------------------------+
| Footer (metadata offsets)|
+--------------------------+

• Data blocks: последовательные KV, сжатые (snappy, lz4, zstd).
• Index: sparse -- хранит первый ключ каждого блока, чтобы найти блок за O(log).
• Bloom filter: для каждого SSTable -- позволяет за O(1) сказать "ключа точно здесь нет".
• Footer: оффсеты index и filter блоков.

Потому что SSTable immutable, к ней можно безопасно делать concurrent reads без блокировок.

Compaction

Compaction -- процесс слияния SSTables. Решает три проблемы:

1. Дубликаты ключей: запись K=1, затем K=2 в разных SSTable -- при compaction побеждает более новая.
2. Tombstones: удаление -- это запись специального маркера "K удалён". При compaction реальная запись исчезает.
3. Read amplification: чем меньше SSTable, тем быстрее lookup.

Без compaction read amplification растёт линейно со временем.

Стратегии compaction

Leveled compaction подробнее

L0: [SST][SST][SST][SST]    ← overlapping, from recent flushes
        │ compact to L1
        ▼
L1: [A-D][E-H][I-L][M-P]    ← non-overlapping, sorted by range, ~10× L0 size
        │ merge selected SST with overlapping from L2
        ▼
L2: [A-B][C-D][E-F]...       ← ~10× L1 size
...

При compaction выбирается один SSTable с уровня Lᵢ и все overlapping с Lᵢ₊₁, сливаются. Это гарантирует, что lookup на любом уровне ≥ 1 = 1 файл.

Tombstones и GC

Удаление в LSM = запись tombstone. Реальные данные исчезнут только при compaction, которая пройдёт через обе записи (живую и tombstone). До этого lookup увидит tombstone и вернёт "не найдено".

Проблема TTL: если данные имеют TTL, tombstones накапливаются и могут занимать значительную часть диска. Cassandra даёт параметр gc_grace_seconds (default 10 дней) -- после него tombstone может быть физически удалён.

Проблема распределённых удалений: tombstone должна дожить, пока не реплицируется на все узлы. Иначе -- "voodoo resurrection" удалённых записей.

Bloom filter в LSM

При point lookup GET key:

1. Проверить MemTable.
2. Проверить immutable MemTable(ы).
3. Для каждого SSTable (от нового к старому):
   • Проверить Bloom filter → если "точно нет", skip.
   • Иначе: binary search в index block, прочитать data block.

Bloom filter с FP rate = 1% сокращает ложные чтения SSTable в 100 раз. Для millions of SSTables это критично -- без Bloom LSM была бы непрактична для point lookups.

Амплификации

Это три главные метрики LSM, и они в конфликте.

• Write amplification (W) -- байт записано на диск / байт от пользователя.
  • STCS: ~O(log n), обычно 10-30×.
  • LCS: ~O(N × L) при L уровнях, обычно 20-50×.
• Read amplification (R) -- блоков прочитано / блоков запрошено.
  • STCS: ~O(log n × files_per_level).
  • LCS: ~O(L).
• Space amplification (S) -- диск занят / логический размер данных.
  • STCS: до 2× из-за дубликатов до compaction.
  • LCS: близко к 1× (максимум 1.11× при ratio 10).

Вывод: нельзя минимизировать все три одновременно. LCS жертвует write amp ради read/space. STCS -- обратное.

Read path в деталях

Чтение ключа K:

1. Check MemTable → если есть, вернуть.
2. Check immutable MemTables.
3. Для каждого SSTable (от L0 -- новейшие -- к Lⁿ):
   • Bloom filter? Если "нет" → skip.
   • Index block: найти data block содержащий K.
   • Прочитать + distress data block, найти K.
   • Если нашли tombstone → "не найдено".
   • Если нашли значение → вернуть (первое найденное -- самое свежее).

Для оптимизации RocksDB использует block cache (LRU блоков в RAM).

LSM vs B-tree

Кто использует LSM

Минимальная структура SSTable в коде

<?php

declare(strict_types=1);

/**
 * Simplified MemTable + SSTable flush for teaching.
 * Real SSTable includes bloom filter, sparse index, block-level compression.
 */
final class MemTable
{
    /** @var array<string, array{value: ?string, tombstone: bool}> */
    private array $data = [];

    public function put(string $key, string $value): void
    {
        $this->data[$key] = ['value' => $value, 'tombstone' => false];
    }

    public function delete(string $key): void
    {
        $this->data[$key] = ['value' => null, 'tombstone' => true];
    }

    public function flush(string $path): void
    {
        ksort($this->data);

        $fp = fopen($path, 'wb');
        if ($fp === false) {
            throw new \RuntimeException("Cannot open $path");
        }

        foreach ($this->data as $key => $entry) {
            $value = $entry['value'] ?? '';
            $header = pack('VVC', strlen($key), strlen($value), $entry['tombstone'] ? 1 : 0);
            fwrite($fp, $header);
            fwrite($fp, $key);
            fwrite($fp, $value);
        }

        fclose($fp);
    }
}

package lsm

import (
	"bytes"
	"encoding/binary"
	"os"
	"sort"
)

// Entry represents a single KV pair in an SSTable.
type Entry struct {
	Key       []byte
	Value     []byte
	Tombstone bool
}

// MemTable is a sorted in-memory buffer (simplified: map + sort on flush).
type MemTable struct {
	data map[string]Entry
}

func NewMemTable() *MemTable { return &MemTable{data: map[string]Entry{}} }

func (m *MemTable) Put(k, v []byte) {
	m.data[string(k)] = Entry{Key: k, Value: v}
}

func (m *MemTable) Delete(k []byte) {
	m.data[string(k)] = Entry{Key: k, Tombstone: true}
}

// Flush writes sorted entries to an SSTable file.
// Real SSTable would include: data blocks, bloom, sparse index, footer.
func (m *MemTable) Flush(path string) error {
	keys := make([]string, 0, len(m.data))
	for k := range m.data {
		keys = append(keys, k)
	}
	sort.Strings(keys)

	f, err := os.Create(path)
	if err != nil {
		return err
	}
	defer f.Close()

	buf := new(bytes.Buffer)
	for _, k := range keys {
		e := m.data[k]
		// [klen][vlen][tomb][key][value]
		_ = binary.Write(buf, binary.LittleEndian, uint32(len(e.Key)))
		_ = binary.Write(buf, binary.LittleEndian, uint32(len(e.Value)))
		tomb := byte(0)
		if e.Tombstone {
			tomb = 1
		}
		buf.WriteByte(tomb)
		buf.Write(e.Key)
		buf.Write(e.Value)
	}
	_, err = f.Write(buf.Bytes())
	return err
}

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

// Simplified MemTable + SSTable flush for teaching.
// A real SSTable also includes a bloom filter, a sparse index and block compression.
public readonly record struct Entry(byte[] Value, bool Tombstone);

public sealed class MemTable
{
    private readonly Dictionary<string, Entry> _data = [];

    public void Put(string key, byte[] value) => _data[key] = new Entry(value, Tombstone: false);

    public void Delete(string key) => _data[key] = new Entry([], Tombstone: true);

    // Flush writes entries sorted by key: [klen][vlen][tomb][key][value].
    public void Flush(string path)
    {
        using var stream = File.Create(path);
        // BinaryWriter is little-endian, matching the Go/PHP layout above.
        using var writer = new BinaryWriter(stream, Encoding.UTF8);

        foreach (var (key, entry) in _data.OrderBy(kv => kv.Key, StringComparer.Ordinal))
        {
            var keyBytes = Encoding.UTF8.GetBytes(key);
            writer.Write((uint)keyBytes.Length);
            writer.Write((uint)entry.Value.Length);
            writer.Write(entry.Tombstone ? (byte)1 : (byte)0);
            writer.Write(keyBytes);
            writer.Write(entry.Value);
        }
    }
}

from __future__ import annotations

import struct
from dataclasses import dataclass

# [klen: uint32 LE][vlen: uint32 LE][tombstone: uint8]
HEADER = struct.Struct("<IIB")

@dataclass(slots=True)
class Entry:
    value: bytes
    tombstone: bool = False

class MemTable:
    """Simplified MemTable + SSTable flush for teaching.

    A real SSTable also includes a bloom filter, a sparse index and
    block-level compression.
    """

    def __init__(self) -> None:
        self._data: dict[bytes, Entry] = {}

    def put(self, key: bytes, value: bytes) -> None:
        self._data[key] = Entry(value)

    def delete(self, key: bytes) -> None:
        self._data[key] = Entry(b"", tombstone=True)

    def flush(self, path: str) -> None:
        """Write entries sorted by key into an immutable SSTable file."""
        with open(path, "wb") as f:
            for key in sorted(self._data):
                entry = self._data[key]
                f.write(HEADER.pack(len(key), len(entry.value), int(entry.tombstone)))
                f.write(key)
                f.write(entry.value)

• Read-heavy без write: B-tree проще и быстрее.
• Очень маленькие датасеты: оверхед compaction не оправдан.
• Строгие p99 latency требования: compaction может вызывать spike'и (решается pacing, но полностью не устраняется).

Выводы

• LSM tree превращает random writes в sequential через буферизацию в MemTable + flush в immutable SSTable.
• Compaction сливает SSTables, убирает дубликаты и tombstones; стратегии -- size-tiered, leveled, time-window.
• Bloom filter на каждой SSTable -- обязателен для нормального read latency.
• Три амплификации (write, read, space) в трёх-стороннем конфликте -- выбор стратегии = выбор трейд-оффа.
• LSM -- стандарт для write-heavy и time-series нагрузок: Cassandra, RocksDB, InfluxDB, HBase.
• Для balanced workload'а B+ tree часто проще и быстрее на чтение.