LSM-дерево: memtable, SSTable и компакция на db_bench RocksDB, уровни Cassandra

LSM-дерево не правит страницы на месте: запись попадает в журнал и в память, а на диск уходит целым отсортированным файлом, который потом многократно перезаписывается слияниями. В опыте на RocksDB 2 млн случайных ключей дали 244 МБ сброшенных файлов и ещё 755 МБ записи компакциями, то есть каждый сброшенный байт переписан 3,1 раза. Устройство B-tree PostgreSQL и журнал WAL разобраны отдельно; здесь считаем, куда уходят байты у LSM, чем за них платит чтение и что показывает та же нагрузка в PostgreSQL 18.

DBA / 01koddo

LSM: память, журнал, уровни и фильтр Блума

Опыт 1: куда уходят байты при записи

RocksDB в Debian упакован вместе с db_bench. Версию выводит сам бенчмарк; параметры уменьшены (memtable 4 МиБ, L1 до 16 МиБ), чтобы 2 млн ключей по 16 байт ключа и 100 байт значения (около 230 МБ) успели пройти три уровня:

docker run -d --name dba-lsm-rocks debian:bookworm sleep 3600
docker exec dba-lsm-rocks bash -c 'apt-get update -qq && apt-get install -y -qq rocksdb-tools'
docker exec dba-lsm-rocks bash -c 'cd /tmp && db_bench --benchmarks=fillrandom,waitforcompaction,levelstats \
  --db=/tmp/db --num=2000000 --key_size=16 --value_size=100 --write_buffer_size=4194304 \
  --max_bytes_for_level_base=16777216 --target_file_size_base=4194304 --max_background_jobs=2 \
  --compression_type=none --bloom_bits=10 --statistics'

вывод (сокращён до нужных строк)
db_bench version 7.8.3
fillrandom   :       3.597 micros/op 278015 ops/sec 7.194 seconds 2000000 operations;   30.8 MB/s
Level Files Size(MB)
  0        0        0
  1        3       13
  2       44      142
rocksdb.bytes.written COUNT : 262000000
rocksdb.wal.bytes COUNT : 262000000
rocksdb.flush.write.bytes COUNT : 243731946
rocksdb.compact.read.bytes COUNT : 835333384
rocksdb.compact.write.bytes COUNT : 755477157

Бенчмарк предупреждает, что пакет собран с включёнными assertions («Assertions are enabled; benchmarks unnecessarily slow»), поэтому абсолютные операции в секунду занижены; сравнивать стоит байты и счётчики. Из вывода:

• 262 МБ пользовательских записей ушли в WAL: rocksdb.wal.bytes равен rocksdb.bytes.written.
• memtable по 4 МиБ сбрасывались в файлы L0: 243,7 МБ (flush.write.bytes).
• компакции прочитали 835 МБ и записали 755 МБ: 755 477 157 / 243 731 946 даёт 3,1. Это и есть усиление записи самих уровней.
• к концу данные лежат в L1 (13 МБ при лимите 16) и L2 (142 МБ), в L0 пусто.

Запись в memtable RocksDB кодирует как последовательность «длина ключа, ключ, длина значения, значение, контрольная сумма» (MemTable::Add):

  // Format of an entry is concatenation of:
  //  key_size     : varint32 of internal_key.size()
  //  key bytes    : char[internal_key.size()]
  //  value_size   : varint32 of value.size()
  //  value bytes  : char[value.size()]
  //  checksum     : char[moptions_.protection_bytes_per_key]

Что компактить, решает оценка («score») каждого уровня. Фрагмент LevelCompactionBuilder::SetupInitialFiles из compaction_picker_level.cc перебирает уровни и берёт первый, у которого оценка не меньше 1; для L0 это число файлов к порогу, для остальных размер к лимиту:

void LevelCompactionBuilder::SetupInitialFiles() {
  // Find the compactions by size on all levels.
  bool skipped_l0_to_base = false;
  for (int i = 0; i < compaction_picker_->NumberLevels() - 1; i++) {
    start_level_score_ = vstorage_->CompactionScore(i);
    start_level_ = vstorage_->CompactionScoreLevel(i);
    assert(i == 0 || start_level_score_ <= vstorage_->CompactionScore(i - 1));
    if (start_level_score_ >= 1) {
      if (skipped_l0_to_base && start_level_ == vstorage_->base_level()) {
        // If L0->base_level compaction is pending, don't schedule further
        // compaction from base level. Otherwise L0->base_level compaction
        // may starve.
        continue;
      }

Опыт 2: фильтр Блума и отсутствующие ключи

Для точечного чтения у LSM нет единого дерева: ключ может лежать в memtable, в любом файле L0 (они перекрываются) и в одном файле каждого нижнего уровня. Тот же db_bench читает 200 000 ключей, которых в базе нет (readmissing), на базе с фильтром (10 бит на ключ) и на такой же без фильтра (--bloom_bits=0, база заполнена отдельно):

docker exec dba-lsm-rocks bash -c 'cd /tmp && db_bench --benchmarks=readmissing --db=/tmp/db \
  --use_existing_db=1 --num=2000000 --reads=200000 --threads=1 --key_size=16 --value_size=100 \
  --write_buffer_size=4194304 --max_bytes_for_level_base=16777216 --target_file_size_base=4194304 \
  --compression_type=none --bloom_bits=10 --statistics'

вывод (сокращён): с фильтром, затем база без фильтра
readmissing  :       0.752 micros/op 1329433 ops/sec ... (0 of 200000 found)
rocksdb.bloom.filter.useful COUNT : 476537
rocksdb.bloom.filter.full.positive COUNT : 4569
rocksdb.sst.read.micros ... COUNT : 3068
readmissing  :       6.650 micros/op 150370 ops/sec ... (0 of 200000 found)
rocksdb.bloom.filter.useful COUNT : 0
rocksdb.sst.read.micros ... COUNT : 308671

Без фильтра запросу приходится заглядывать в файлы: 308 671 чтение SST на 200 000 запросов, около 1,5 на запрос. Фильтр Блума ответил «нет» 476 537 раз (useful) и дал 4 569 ложных «возможно» (full.positive), чтения упали до 3 068, а время запроса — с 6,65 до 0,75 мкс. Проверку делает MayMatch в filter_policy.cc: хеш ключа и несколько проб в битовом массиве. «Нет» фильтр говорит точно, «да» — вероятностно, поэтому ложные срабатывания есть, а пропуска существующего ключа нет.

Для существующего ключа файл всё равно придётся читать, поэтому фильтр помогает там, где часто спрашивают отсутствующее.

Опыт 3: та же нагрузка в PostgreSQL 18

2 млн строк с ключом text (16 символов, случайный порядок) и значением в 100 байт, первичный ключ, один оператор INSERT … SELECT, затем CHECKPOINT, чтобы страницы ушли на диск:

docker run -d --name dba-lsm-pg -e POSTGRES_PASSWORD=pg postgres:18
docker exec -i dba-lsm-pg psql -U postgres <<'EOF'
CREATE TABLE kv (k text PRIMARY KEY, v text);
CREATE TEMP TABLE b AS SELECT wal_bytes AS w FROM pg_stat_wal;
\timing on
INSERT INTO kv SELECT left(md5(g::text),16), left(repeat(md5((g+1)::text),4),100)
  FROM generate_series(1,2000000) g;
CHECKPOINT;
SELECT round((wal_bytes - w)/1e6) AS wal_mb FROM pg_stat_wal, b;
SELECT round(pg_relation_size('kv')/1e6) AS table_mb, round(pg_relation_size('kv_pkey')/1e6) AS index_mb;
SELECT backend_type, round(writes*8192/1e6) AS mb FROM pg_stat_io
  WHERE object='relation' AND context='normal' AND writes>0;
EOF

вывод (сокращён)
INSERT 0 2000000
Time: 13222.195 ms (00:13.222)
CHECKPOINT
Time: 996.307 ms
 wal_mb | 625
 table_mb | 298     index_mb | 107
 client backend    | 241
 background writer |  37
 checkpointer      | 140

Страницы файлов данных PostgreSQL записал примерно 418 МБ (241 + 37 + 140) при размере таблицы с индексом 405 МБ. WAL вышел 625 МБ, больше, чем данных на диске (405 МБ). Сумма 1 043 МБ против 1 261 МБ у RocksDB (262 WAL + 244 сброс + 755 компакции). Выигрыша «LSM пишет меньше» на этой нагрузке нет; отличие в характере записи: RocksDB пишет только крупными последовательными файлами, PostgreSQL перезаписывает страницы индекса там, где они лежат.

Ту же проверку отсутствующих ключей PostgreSQL прошёл так:

SELECT count(*) FROM generate_series(1,200000) g
 WHERE EXISTS (SELECT 1 FROM kv WHERE k = 'm' || lpad(g::text,15,'0'));

Первый запуск занял 1 406 мс (кэш холодный), повторный 363 мс, около 1,8 мкс на ключ при индексе 107 МБ целиком в shared_buffers 128 МБ. Это запрос SQL, а у db_bench вызов библиотеки, поэтому сравнивать можно только порядок: единицы микросекунд у обоих. У LSM такой результат держится на фильтре, без него на 6,65 мкс.

Уровни в Cassandra: размер задаёт формула

Cassandra с LeveledCompactionStrategy устроена так же: memtable, SSTable, уровни. Допустимый размер уровня в LeveledManifest.maxBytesForLevel — степень множителя от размера SSTable:

    public static long maxBytesForLevel(int level, int levelFanoutSize, long maxSSTableSizeInBytes)
    {
        if (level == 0)
            return 4L * maxSSTableSizeInBytes;
        double bytes = Math.pow(levelFanoutSize, level) * maxSSTableSizeInBytes;
        if (bytes > Long.MAX_VALUE)
            throw new RuntimeException("At most " + Long.MAX_VALUE + " bytes may be in a compaction level; your maxSSTableSize must be absurdly high to compute " + bytes);
        return (long) bytes;
    }

В LeveledCompactionStrategy по умолчанию множитель DEFAULT_LEVEL_FANOUT_SIZE = 10, размер SSTable configuredMaxSSTableSize = 160 МиБ. Значит, L0 вмещает 640 МиБ, L1 — 1 600 МиБ, L2 — 16 000 МиБ. Каждый следующий уровень в десять раз больше, поэтому при росте данных число уровней, а с ним и число файлов, которые приходится перекладывать, растёт логарифмически.

Что из этого следует

• Усиление записи — цена LSM, и её надо измерять. В опыте компакции записали в 3,1 раза больше, чем сброс, и в сумме с WAL RocksDB записал 1 261 МБ против 1 043 МБ у PostgreSQL. Смотри rocksdb.compact.write.bytes относительно flush.write.bytes и bytes.written.
• Фильтры Блума нужны, если спрашивают отсутствующее. Они сократили чтения SST со 308 671 до 3 068 на 200 000 запросов. Для нагрузки, где ключ почти всегда есть, выигрыш меньше.
• Выбор между B-tree и LSM не сводится к «кто быстрее». На этой нагрузке по объёму записи они сопоставимы; LSM пишет только целыми файлами, а точечное чтение держит на фильтрах.

Чек-лист для работы с LSM

1. Посчитай усиление записи: compact.write.bytes делить на flush.write.bytes, плюс WAL и данные клиента.
2. Включи фильтры Блума для таблиц с запросами по отсутствующим ключам и проверь bloom.filter.useful против sst.read.micros.
3. Оцени размеры уровней по формуле (в Cassandra — fanout^уровень × sstable_size), чтобы не удивиться объёму при росте.
4. Убери контейнеры вместе с томами: docker rm -f -v dba-lsm-rocks dba-lsm-pg.