Разбираем одну ноду базы данных, чтобы понять распределённые системы
Когда читаешь про покупку 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) и версионирование. Без понимания внутренностей одной ноды такое не построишь.
