Разбираем одну ноду базы данных, чтобы понять распределённые системы

Когда читаешь про покупку Neon за $1 млрд, возникает вопрос: за что платят, если PostgreSQL и MySQL бесплатны? Чтобы это понять, нужно залезть под капот - и начать не с распределённых монстров, а с одной ноды.

Вначале был файл

Хранить данные в файлах кажется простым решением. Открыли Excel, добавили строки, сохранили. Проблемы начинаются, когда требования меняются: добавить поле - переписывай парсеры, конвертируй старые данные, разбирайся с версиями. Если файл одновременно редактируют двое - конфликт.

СУБД решает это через data independence. Мы работаем с таблицами и SQL, не думая, как байты лежат на диске. Три ключевых механизма:

Concurrency Control - чтобы два менеджера не переписали бюджет друг друга
Crash Recovery - чтобы после внезапного отключения питания данные не пропали
Security - чтобы Петя не увидел зарплату Васи

Вместе они образуют ACID.

Как устроен классический движок

SQL-запрос проходит конвейер: парсер проверяет синтаксис, оптимизатор строит план выполнения - решает, идти по индексу или читать таблицу целиком. Он оперирует реляционной алгеброй: переставляет фильтры местами, чтобы меньше данных гонять.

В основании всего - Buffer Pool Manager (кеширует страницы в памяти) и Disk Space Manager (решает, куда писать байты).

Страницы и слоты: дизайн внутри страницы

Данные хранятся страницами фиксированного размера - обычно 4–16 КБ. InnoDB хранит каждую таблицу как файл, разбитый на такие страницы.

Внутри страницы записи разной длины. Организовано через метод слотов: в начале страницы - массив указателей на концы записей, сами записи пишутся с конца. Удалённая запись просто помечается как свободная, место переиспользуется. Если строка огромная и не влезает - создаётся overflow page (в PostgreSQL это TOAST).

Со временем внутри страницы появляются «дыры» от удалённых записей. В PostgreSQL за зачистку отвечает VACUUM:

testdb=# CREATE TABLE test (id serial, data text);
testdb=# INSERT INTO test (data) SELECT 'row' FROM generate_series(1,10000);
testdb=# SELECT pg_size_pretty(pg_total_relation_size('test'));
 384 kB

testdb=# UPDATE test SET data = data || ' updated';
testdb=# SELECT pg_size_pretty(pg_total_relation_size('test'));
 768 kB  - выросло в 2 раза!

testdb=# VACUUM FULL test;
testdb=# SELECT pg_size_pretty(pg_total_relation_size('test'));
 384 kB  - вернулось обратно

Обычный UPDATE раздул таблицу вдвое - PostgreSQL при обновлении пишет новую версию строки, старая остаётся как мёртвая. Без VACUUM диски забиваются мёртвыми данными.

Буфер-пул: почему без кеша мы бы умерли

Даже SSD в сотни раз медленнее оперативной памяти, поэтому часто используемые страницы живут в Buffer Pool. Изменённая страница становится «грязной» - фоновый поток сбросит её на диск позже.

Память конечна, нужно решать, кого выкидывать:

FIFO - выкидываем самую старую. Просто, но можно выкинуть популярную страницу
LRU - выкидываем ту, к которой дольше всего не обращались. Работает нормально, пока не начинается sequential scan

При full scan таблица читается целиком и заполняет буфер страницами, которые больше не понадобятся. Это вымывает полезные данные -называется sequential flooding:

testdb=# CREATE TABLE small (id int);
testdb=# CREATE TABLE big (id int);

testdb=# - Загружаем small в кеш
testdb=# SELECT COUNT(*) FROM small;

testdb=# - Проверяем, что она там
testdb=# SELECT COUNT(*) FROM pg_buffercache WHERE relfilenode = 'small'::regclass::oid;
 5

testdb=# - Делаем полное сканирование большой таблицы
testdb=# SELECT COUNT(*) FROM big;

testdb=# - Смотрим на small снова
testdb=# SELECT COUNT(*) FROM pg_buffercache WHERE relfilenode = 'small'::regclass::oid;
 0  - всё, вынесли

Маленькая таблица была в кеше, пришёл full scan большой - и вымел её. Следующий запрос к small пойдёт на диск.

Индексы: как не перебирать всё ручками

Без индекса база сканирует всю таблицу строчка за строчкой. Что происходит с одним запросом до и после создания индекса:

testdb=# CREATE TABLE users (age int, name text);
testdb=# INSERT INTO users SELECT random()*100, 'user' FROM generate_series(1,100000);

testdb=# EXPLAIN ANALYZE SELECT * FROM users WHERE age = 42;
 Seq Scan on users  (cost=0.00..1837.00 rows=1 width=8)
   Filter: (age = 42)
 Execution Time: 25.342 ms - 25 миллисекунд

testdb=# CREATE INDEX idx_age ON users(age);

testdb=# EXPLAIN ANALYZE SELECT * FROM users WHERE age = 42;
 Index Scan using idx_age on users  (cost=0.29..8.30 rows=1 width=8)
   Index Cond: (age = 42)
 Execution Time: 0.123 ms - 0.1 миллисекунды!

25 мс против 0.1 мс - разница в 250 раз.

Кластеризованные и вторичные

Clustered index - определяет физический порядок данных. Например, primary key в MySQL InnoDB. Данные уже лежат отсортированными, можно использовать sparse index - указатель на страницу, а не на каждую запись.
Secondary index - по любому другому полю. Он часто хранит не прямой адрес строки, а значение первичного ключа. Чтобы найти запись, нужно сначала сходить во вторичный индекс, потом в первичный. Лишний шаг, зато упрощает обновления.

Хэш-индекс

БКлюч хэшируется, получаем номер корзины. Поиск за O(1), идеально для точечных запросов: WHERE id = 42. Для диапазонных (WHERE age > 18) бесполезен - хэш не сохраняет порядок.

B-tree

Корень → внутренние узлы → листья. Внутренние узлы хранят только ключи для навигации, данные (ссылки на строки) лежат только в листьях. Для миллиарда записей высота дерева обычно 3–4 уровня. Листья связаны в связный список - специально для диапазонных запросов. WHERE id BETWEEN 40 AND 50: находим первый лист с ключом 40 и идём по списку вперёд, не возвращаясь в корень.

Bitmap-индексы

Идеальны для полей, где мало уникальных значений: пол, статус заказа, категория товара. Допустим, у нас 5 записей:

id	пол	курит?
1	м	да
2	ж	нет
3	м	нет
4	ж	да
5	м	да

Для значения «М» строится битовая маска: 1 0 1 0 1 (где 1 - запись подходит, 0 - нет).
Для значения «Ж»: 0 1 0 1 0.
Для значения «да» (курит): 1 0 0 1 1.

Хотите найти всех мужчин, которые курят? Берёте маску «М» (1 0 1 0 1) и маску «да» (1 0 0 1 1), делаете побитовое AND:

1 0 1 0 1
1 0 0 1 1
--------- AND
1 0 0 0 1

Получили маску 1 0 0 0 1 - значит, подходят записи 1 и 5. Всё за одну операцию, без сканирования таблицы.

Инвертированный индекс (full-text)

Индекс, на котором держится любой поиск по тексту, от поисковиков до поля поиска в интернет-магазине: заводится словарь, где каждому слову соответствует список документов (или строк), в которых это слово встречается.

R-tree - для геоданных

Обычное дерево не умеет работать с координатами (X, Y). R-tree группирует объекты в ограничивающие прямоугольники. Хотите найти все кафе в радиусе 1 км? База сначала смотрит, какие прямоугольники пересекаются с кругом, и только потом лезет внутрь. Используется не только в базах, но и в играх, графике - везде, где есть пространство.

Строки против колонок: вечная битва

Row-oriented (строчное хранение) - данные лежат строками: id:1, name:Вася, age:20 | id:2, name:Петя, age:30. Отлично для OLTP, когда мы часто вставляем и обновляем отдельные записи. Плохо для аналитики: если нужно посчитать средний возраст, база прочитает ещё и имена с id, хотя они не нужны.

Column-oriented (колоночное) - данные лежат колонками: 1,2 | Вася,Петя | 20,30. Идеально для аналитических запросов: читаем только нужную колонку, получаем отличное сжатие (данные одного типа рядом). Но собрать строку целиком - боль, и вставлять новые строки медленно.

Выбор типа хранения диктуется нагрузкой: OLAP или OLTP.

LSM-дерево: когда запись важнее чтения

B-tree при высокой нагрузке на запись тормозит из-за сплитов. Альтернатива - LSM (Log-Structured Merge-Tree), на котором построены Cassandra, RocksDB, LevelDB.

Как это работает:

Запись попадает сразу в память - Memtable (часто реализована как Skip-list, чтобы быстро искать).
Когда память заканчивается, Memtable сбрасывается на диск в виде SSTable (отсортированная таблица, иммутабельная).
На диске со временем накапливается куча таких SSTable. Фоновый процесс compaction сливает их, удаляя дубликаты.

Запись - это всегда добавление, никаких сплитов. Отсюда и преимущество LSM по скорости записи. Чтение сложнее: нужно проверить Memtable, потом SSTable по уровням.

Спасают Bloom-фильтры - компактная структура, которая точно скажет «этого ключа здесь нет». Если говорит «может быть» - идём проверять. Это отсекает большую часть дисковых операций:

(проще обыграть метафорой)

Без Bloom-фильтра:
  Читаем файл 1... нет ключа
  Читаем файл 2... нет ключа
  Читаем файл 3... нет ключа
  ... и так 10 раз

С Bloom-фильтром:
  Спрашиваем фильтр: "Ключ есть в файлах 4-10?"
  Фильтр: "Точно нет, можеже не проверять"
  Проверили только файлы 1,2,3 и нашли

Оптимизация запросов: как планировщик делает магию

Оптимизатор перебирает варианты выполнения и выбирает самый дешёвый. Реляционная алгебра позволяет переставлять операции без изменения результата: сначала отфильтровать, потом джойнить - меньше данных, быстрее.

В PostgreSQL для анализа плана есть команда EXPLAIN ANALYZE. Там можно увидеть, где база сканирует всю таблицу (Seq Scan), а где пишет "Index Scan".

Пример:

testdb=# EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM orders WHERE user_id = 42 AND status = 'active';

 Seq Scan on orders  (cost=0.00..1837.00 rows=1 width=8)
   Filter: ((user_id = 42) AND (status = 'active'::text))
   Rows Removed by Filter: 99999
   Buffers: shared hit=840
 Execution Time: 32.567 ms

- А если создать правильный индекс:

 Index Scan on orders_active_idx  (cost=0.29..8.30 rows=1 width=8)
   Index Cond: (user_id = 42)
   Filter: (status = 'active'::text)
   Buffers: shared hit=4
 Execution Time: 0.089 ms

В первом случае база перебрала 100 тысяч строк, чтобы найти одну, а во втором сразу пришла по индексу к нужным.

Итоги

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

Возвращаясь к Neon: они отделили storage от compute, оставив PostgreSQL только как процессор запросов, а данные убрали в распределённое хранилище поверх S3. Это даёт мгновенные бранчи (copy-on-write) и версионирование. Без понимания внутренностей одной ноды такое не построишь.

Прежде чем шардировать: разбираем внутренности одной ноды СУБД