B-деревья и LSM-деревья простыми словами: как база данных хранит данные

← назад к разделу

Свою СУБД вы, скорее всего, писать не будете. Но выбирать между PostgreSQL и Cassandra, настраивать ClickHouse, объяснять коллеге, почему лишний индекс замедлил запись, — придётся. А для этого нужно представлять, что база делает на диске.

Хорошая новость: внутри почти любой базы данных лежит один из двух движков хранения — B-дерево или LSM-дерево. Понять эти два — и поведение большинства баз перестаёт быть магией. Разберём оба с начала: с самой примитивной «базы», какую можно представить.

Самая простая база данных в мире

Вот «база данных» из двух строчек на Bash:

db_set () { echo "$1,$2" >> database; }
db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1; }

db_set дописывает пару «ключ,значение» в конец файла. db_get находит последнее вхождение ключа. Примитивно — но кое-чему эта игрушка нас учит.

Запись здесь на удивление хорошая. Дописать строку в конец файла — самая дешёвая операция для диска. На жёстком диске головке не надо прыгать по пластине, всё пишется подряд. На SSD головки нет, но выигрыш остаётся: последовательная запись заполняет блоки целиком, и контроллеру реже приходится перекладывать соседние данные, чтобы освободить место. Настоящие базы используют ровно этот приём и называют его журналом (log) — последовательность записей, в которую можно только дописывать.

А вот чтение ужасное. Чтобы найти ключ, db_get просматривает весь файл от начала до конца. Чем больше данных, тем медленнее: это O(n) — время растёт линейно с размером базы.

Чтобы читать быстро, нужен индекс — вспомогательная структура рядом с данными, вроде оглавления книги. И тут же вылезает главный размен этого мира: индекс ускоряет чтение, но замедляет запись — при каждой вставке его тоже надо обновить. Поэтому базы не индексируют всё подряд: набор индексов выбирает разработчик под свои запросы.

Шаг первый: хеш-индекс

Самый простой индекс к нашему журналу — держать в памяти таблицу «ключ → в каком месте файла лежит его последнее значение». Тогда запись остаётся дешёвым дописыванием, а чтение — один прыжок сразу в нужное место файла.

Чтобы файл не рос до бесконечности, журнал режут на куски (сегменты) и время от времени в фоне делают уплотнение (compaction): выбрасывают устаревшие версии ключей и сливают сегменты в один поменьше.

Ровно так устроен реальный движок Bitcask. Но у подхода два потолка: все ключи обязаны помещаться в оперативную память, а запросы по диапазону («все ключи от А до Б») работать не будут — хеш-таблица ничего не знает о порядке ключей.

LSM-дерево: отсортированные кускиспросят на собеседовании

Оба потолка убирает одна идея — хранить каждый сегмент отсортированным по ключу. Такой отсортированный файл называют SSTable (sorted string table). Сортировка снимает сразу оба потолка: по диапазону теперь можно идти подряд, а в памяти достаточно держать не все ключи, а один на каждые несколько килобайт — нашли ближайший, дочитали небольшой кусок файла и попали в цель. Такой индекс называют разреженным, и стоит он в сотни раз меньше памяти. Вот как на этой идее работает движок:

1. Новая запись сначала попадает в MemTable — небольшое отсортированное дерево прямо в оперативной памяти (плюс дописывается в короткий журнал на диске — на случай, если вырубят питание).
2. Когда MemTable подрастает до нескольких мегабайт, её целиком сбрасывают на диск новым файлом-SSTable. Это снова дешёвая последовательная запись.
3. Чтение ищет ключ сначала в MemTable, потом в самой свежей SSTable, потом в предыдущей — и так вглубь.
4. Фоновый compaction сливает SSTable между собой: два отсортированных файла слить легко, а дубликаты одного ключа схлопываются до последней версии.

Механика четвёртого шага целиком помещается в один цикл:

public class Compaction {
    public static void main(String[] args) {
        String[] older = {"b=1", "c=1", "f=1"};
        String[] newer = {"a=2", "c=2", "e=2"};
        StringBuilder merged = new StringBuilder();
        int i = 0, j = 0;
        while (i < older.length || j < newer.length) {
            char left = i < older.length ? older[i].charAt(0) : '\uffff';
            char right = j < newer.length ? newer[j].charAt(0) : '\uffff';
            if (left < right) merged.append(older[i++]).append(' ');
            else if (right < left) merged.append(newer[j++]).append(' ');
            else { merged.append(newer[j++]).append(' '); i++; }
        }
        System.out.println("старый:  " + String.join(" ", older));
        System.out.println("свежий:  " + String.join(" ", newer));
        System.out.println("слияние: " + merged.toString().trim());
    }
}

package main

import (
	"fmt"
	"strings"
)

func main() {
	older := []string{"b=1", "c=1", "f=1"}
	newer := []string{"a=2", "c=2", "e=2"}
	var merged []string
	i, j := 0, 0
	for i < len(older) || j < len(newer) {
		left, right := byte(0xff), byte(0xff)
		if i < len(older) {
			left = older[i][0]
		}
		if j < len(newer) {
			right = newer[j][0]
		}
		switch {
		case left < right:
			merged = append(merged, older[i])
			i++
		case right < left:
			merged = append(merged, newer[j])
			j++
		default:
			merged = append(merged, newer[j])
			i++
			j++
		}
	}
	fmt.Println("старый:  " + strings.Join(older, " "))
	fmt.Println("свежий:  " + strings.Join(newer, " "))
	fmt.Println("слияние: " + strings.Join(merged, " "))
}

const older = ['b=1', 'c=1', 'f=1'];
const newer = ['a=2', 'c=2', 'e=2'];
const merged = [];
let i = 0, j = 0;
while (i < older.length || j < newer.length) {
  const left = i < older.length ? older[i][0] : '￿';
  const right = j < newer.length ? newer[j][0] : '￿';
  if (left < right) merged.push(older[i++]);
  else if (right < left) merged.push(newer[j++]);
  else { merged.push(newer[j++]); i++; }
}
console.log('старый:  ' + older.join(' '));
console.log('свежий:  ' + newer.join(' '));
console.log('слияние: ' + merged.join(' '));

older = ["b=1", "c=1", "f=1"]
newer = ["a=2", "c=2", "e=2"]
merged = []
i = j = 0
while i < len(older) or j < len(newer):
    left = older[i][0] if i < len(older) else "￿"
    right = newer[j][0] if j < len(newer) else "￿"
    if left < right:
        merged.append(older[i]); i += 1
    elif right < left:
        merged.append(newer[j]); j += 1
    else:
        merged.append(newer[j]); i += 1; j += 1
print("старый:  " + " ".join(older))
print("свежий:  " + " ".join(newer))
print("слияние: " + " ".join(merged))

Один проход, память не нужна — потому слияние и живёт в фоне.

Это и есть LSM-дерево (log-structured merge-tree). На нём стоят RocksDB и LevelDB, Cassandra и HBase; тот же принцип «отсортированные куски + фоновое слияние» лежит в основе поискового индекса Lucene (а значит, и Elasticsearch) и движка MergeTree в ClickHouse.

Одно тонкое место: искать отсутствующий ключ дорого — придётся проверить MemTable и все SSTable до самой старой. Спасает фильтр Блума — компактная структура, которая по ключу быстро отвечает «точно нет» или «может быть, есть», и в первом случае экономит лишние чтения с диска.

Когда LSM не подходит

У LSM есть сценарий, в котором он проигрывает прямо: прочитать, изменить, записать одну строку. Каждое такое изменение — новая запись в журнал и новая версия, старая остаётся до слияния; чтение перед записью обходит все куски, где ключ может лежать. То есть обычное CRUD-приложение, которое правит одну строку по идентификатору, получает от LSM усиление и записи, и места.

Второй неудобный случай — частые удаления. Удаление в LSM это тоже запись (метка удаления), и до слияния она не освобождает ни байта, а чтение обязано её учитывать. Таблица, из которой регулярно удаляют, накапливает такие метки и замедляется — об этом статья про устройство Cassandra.

Отсюда правило: LSM берут под поток записи и данные, которые дописывают, а не правят. Под изменяемые данные с точечным чтением честнее B-дерево.

B-дерево: страницы фиксированного размера и WALспросят на собеседовании

B-дерево придумали ещё в 1970-х, и оно до сих пор стандарт по умолчанию: на нём построены индексы PostgreSQL, MySQL, Oracle и почти всех реляционных баз. Подход тут противоположный. База делится не на куски переменного размера, а на страницы одинакового размера (обычно от 4 до 16 КБ: у PostgreSQL это 8 КБ, у MySQL — 16), и эти страницы перезаписываются на том же месте, а не дописываются в конец.

Страницы выстроены в дерево. В корне — ключи-границы и ссылки на «детей»; каждый ребёнок отвечает за свой диапазон ключей; в самом низу, в листьях, — либо сами значения, либо ссылки на них: в индексах PostgreSQL лист хранит ключ и адрес строки в файле таблицы, а сама строка лежит отдельно, в основном же индексе MySQL (InnoDB) строка лежит прямо в листе. У каждой страницы сотни ссылок на детей, поэтому дерево получается очень «плоское», а поиск ключа — это три-четыре прыжка по диску. Посчитаем вместимость, если на страницу помещается триста ссылок:

public class TreeHeight {
    public static void main(String[] args) {
        long keys = 1;
        for (int level = 1; level <= 4; level++) {
            keys *= 300;
            System.out.println("уровней: " + level + " → " + keys + " записей");
        }
    }
}

package main

import "fmt"

func main() {
	keys := int64(1)
	for level := 1; level <= 4; level++ {
		keys *= 300
		fmt.Printf("уровней: %d → %d записей\n", level, keys)
	}
}

let keys = 1;
for (let level = 1; level <= 4; level++) {
  keys *= 300;
  console.log(`уровней: ${level} → ${keys} записей`);
}

keys = 1
for level in range(1, 5):
    keys *= 300
    print(f"уровней: {level} → {keys} записей")

Четырёх уровней хватает на миллиарды записей. Если вставка не влезает в страницу, страницу разбивают на две и правят ссылку у родителя.

Перезапись на месте — штука опасная: если питание вырубится ровно в момент разбиения страницы, индекс может остаться в «разорванном» виде. Поэтому каждое изменение сначала дописывают в журнал упреждающей записи (write-ahead log, WAL) и только потом применяют к самим страницам. После сбоя база проигрывает журнал заново и восстанавливает согласованность. Ирония: движок с перезаписью на месте всё равно таскает с собой журнал — тот, с которого мы начали.

Индекс отдельно, строки отдельно

Важное уточнение, которое объясняет половину различий между базами: B-дерево — это структура индекса, а не обязательно способ хранения строк.

В PostgreSQL строки лежат в куче (heap) — неупорядоченном наборе страниц, а индекс хранит ключ и ссылку на место строки. Отсюда следствия: индексов может быть много и они равноправны, первичный ключ ничем не выделен, а чтобы прочитать строку по индексу, нужен ещё один переход — в кучу. Именно из этого перехода растёт смысл покрывающего индекса: если все нужные колонки есть в самом индексе, в кучу идти не надо.

В MySQL с движком InnoDB (и в ряде других баз) строки лежат внутри индекса первичного ключа, отсортированные по нему — это кластерный индекс. Чтение по первичному ключу получается за один проход, зато вторичный индекс хранит не ссылку на место, а значение первичного ключа, и поиск по нему превращается в два прохода по дереву. Плюс порядок вставки начинает иметь значение: случайный первичный ключ раскидывает вставки по всему дереву, последовательный — дописывает в конец.

Практический вывод для читателя: одинаковые на вид схемы в разных базах ведут себя по-разному, и «первичный ключ — это UUID» стоит в MySQL дороже, чем в PostgreSQL.

Сравнение: за что платимспросят на собеседовании

Выбор движка это выбор, за что платить, и цена видна на трёх операциях.

Первая плата — за запись. LSM обычно быстрее, потому что всё пишется последовательно. У B-дерева каждая запись — это и запись в WAL, и перезапись целой страницы (даже если поменялись три байта). На диск страница при этом уезжает не на каждую правку: её меняют в буферном кеше, и десять правок подряд превратятся в одну запись на диск при ближайшей контрольной точке — но записана страница будет целиком. Сколько лишних байт при этом реально уезжает на диск на каждый байт полезных данных, называют усилением записи (write amplification). Правда, у LSM усиление тоже есть — compaction переписывает данные по многу раз и при большом потоке записи начинает бороться с ней за диск.

Вторая — за чтение. B-дерево предсказуемее: ключ лежит ровно в одном месте, путь к нему — те же три-четыре прыжка. В LSM ключ может оказаться в нескольких кусках на разных стадиях уплотнения, поэтому «хвостовые» задержки (см. перцентили) у него капризнее — фоновый compaction иногда отбирает диск у обычных запросов.

Третья — за транзакции. В B-дереве удобно вешать блокировку прямо на диапазон ключей в дереве — одна из причин, почему реляционные базы с их изоляцией транзакций построены именно на B-деревьях.

Практическое правило: «много пишем, читаем в основном свежее» (события, метрики, лента) — территория LSM; «много читаем по ключам и диапазонам, нужны транзакции» — территория B-дерева. Точно решает только замер на своей нагрузке.

Где это применяется

Понимание движка превращает «волшебные» свойства баз в понятные следствия. Почему Cassandra тянет огромный поток записи? Последовательные SSTable. Почему в PostgreSQL лишние индексы замедляют вставку? Каждый индекс — ещё одно B-дерево, которое надо обновить.

Почему в ClickHouse данные обязательно сортируются по ключу таблицы? MergeTree — родня LSM, и сортировка для него и есть индекс. Почему после сбоя PostgreSQL стартует не мгновенно? Проигрывает WAL.

Где спотыкаются начинающие:

• Сравнивают базы по маркетингу, а не по движку. «NoSQL быстрее» — фраза ни о чём: вопрос в том, быстрее на записи или на чтении и почему.
• Забывают, что индекс не бесплатный. Пять индексов на таблице — пять деревьев, которые обновляются на каждой вставке.
• Не следят за compaction. LSM-база без присмотра копит куски, пока не кончится диск или не просядут чтения.
• Пугаются слова WAL. Это не экзотика: благодаря журналу база переживает выключение питания, на нём же держатся репликация и резервные копии.

Глубже: стратегии уплотнения и три усилениярасширенное

Куски надо периодически сливать, и как именно их сливать — главное эксплуатационное решение в LSM. Две основные стратегии.

Размерная (size-tiered). Куски примерно одного размера сливаются в один больший. Запись дешёвая (каждая строка переписывается немного раз), зато один ключ может лежать в нескольких крупных кусках сразу, и чтение обходит их все. Плюс нужен запас места: слияние двух кусков по 100 ГБ требует ещё 100 ГБ свободных.

Уровневая (leveled). Данные разложены по уровням, каждый следующий в десять раз больше, и внутри уровня куски не пересекаются по диапазонам ключей. Чтение трогает по одному куску на уровень — то есть предсказуемо мало; место расходуется экономно. Платит запись: одна строка за свою жизнь переписывается на каждом уровне, и общий объём записи выходит в разы больше.

Отсюда три величины, которыми измеряют любой движок хранения:

Усиление записи — сколько байт реально записано на диск на каждый байт данных. У уровневой стратегии оно высокое, у размерной ниже, у B-дерева своё (страница переписывается целиком плюс журнал).

Усиление чтения — сколько обращений к диску нужно, чтобы найти один ключ. У LSM оно тем больше, чем больше кусков может содержать ключ; у B-дерева равно высоте дерева.

Усиление места — сколько места занято сверх полезных данных. У размерной стратегии оно самое заметное: старые версии живут до слияния.

Выбирают по нагрузке: поток записи и чтение диапазонов — размерная; много точечных чтений и ограниченное место — уровневая. Для данных с временем жизни есть третья, по временным окнам, которая просто удаляет целые старые куски.

Глубже: фильтр Блума: цена вопросарасширенное

Фильтр отвечает на вопрос «может ли этот ключ быть в этом куске» и имеет одностороннюю ошибку: «нет» — точно нет, «да» — может быть, а может и не быть. Ложноположительные ответы и есть его цена: часть обращений к диску всё равно окажется напрасной.

Второе — память. На один ключ уходит порядка десяти бит при вероятности ложного срабатывания около одного процента; хотите ошибаться реже — платите больше бит на ключ. Для миллиарда ключей это больше гигабайта памяти, и именно поэтому фильтр не ставят «на всё подряд»: его держат для кусков, которые действительно проверяют на точечных запросах, и настраивают вероятность ошибки по тому, сколько памяти не жалко.

Глубже: почему прыжков по диску на самом деле нетрасширенное

Высота дерева в три-четыре уровня означает три-четыре чтения страниц, но на практике их обычно ноль: страницы лежат в буферном пуле — области памяти, где база держит недавно использованные страницы. Верхние уровни дерева используются в каждом запросе и потому живут в памяти всегда; с диска читаются только листья, и то не все.

Отсюда правило, которое важнее высоты дерева: решает объём памяти. Пока рабочее множество (часто читаемые страницы плюс индексы) помещается в память, база работает со скоростью памяти. Как только перестаёт — каждое обращение превращается в чтение с диска, и производительность падает скачком, а не плавно. Поэтому первый вопрос при настройке любой базы — сколько памяти отдано под кэш страниц, и сравним ли он с размером горячих данных.

Коротко

• Дописывание в конец файла — самая дешёвая запись для диска; с журнала начинаются оба движка.
• LSM: MemTable в памяти, сброс целиком новым SSTable, фоновое слияние сегментов, общий ключ схлопывается до свежей версии.
• Отсутствующий ключ LSM ищет по всем сегментам; спасает фильтр Блума.
• B-дерево: страницы по 8 КБ (PostgreSQL) или 16 КБ (MySQL) перезаписываются на том же месте, сотни ссылок со страницы — четыре уровня на миллиарды записей.
• Перезапись на месте держится на WAL: сначала журнал, потом страницы.
• Платим всегда: у LSM — хвостовые задержки и борьба compaction за диск, у B-дерева — усиление записи.
• Стратегия уплотнения — главное решение в LSM: размерная дешевле по записи и требует места, уровневая даёт предсказуемое чтение ценой усиления записи.
• Три величины для сравнения движков: усиление записи, чтения и места; LSM плох там, где строку читают, меняют и пишут обратно, — это обычный CRUD.
• B-дерево — структура индекса: в PostgreSQL строки лежат в куче (отсюда смысл покрывающих индексов), в InnoDB — внутри индекса первичного ключа.
• Прыжков по диску обычно нет: верхние уровни дерева живут в буферном пуле, и решает не высота дерева, а объём памяти под горячие страницы. Фильтр Блума стоит около десяти бит на ключ и ошибается в сторону лишнего чтения.

Что почитать дальше

• OLTP и OLAP — характер запросов решает, какой движок нужен.
• Типы индексов PostgreSQL — B-дерево со стороны пользователя.
• WAL в PostgreSQL — от чего растёт объём журнала.
• Моделирование в ClickHouse — MergeTree на практике.