Содержание
- Краткое резюме
- Введение в СУБД и их назначение
- Архитектура реляционной СУБД
- Организация стореджа: страницы и запись
- Обработка удалений: Vacuum
- Способы хранения данных: Row-oriented vs Column-oriented
- Метаданные и системный каталог
- Буферный пул и политика кеширования
- Индексы: кластеризованные, некластеризованные и виды структур
- LSM Storage: Log-Structured Merge-trees
- Skip list: вероятностная структура данных
- Оптимизация чтения и слияние SST-файлов
- Оптимизация и выполнение SQL-запросов
- Заключение
Краткое резюме
- Системы управления базами данных (СУБД) необходимы для абстрагирования хранения, управления конкурентным доступом, восстановления после сбоев и контроля безопасности.
- Классическая архитектура реляционных СУБД включает построение оптимальных планов выполнения SQL-запросов, буферный пул для кеширования страниц и менеджмент дискового пространства.
- Сторедж строится из фиксированных страниц (pages), разбитых на записи с поддержкой переменных и фиксированных размеров, что требует сложных структур данных и механизма вакуума.
- Различают row-oriented (хранение построчно) и column-oriented (по столбцам) модели, подходящие для OLTP и OLAP задач соответственно.
- Для индексации используются разные типы: хэш-индексы (для точечного поиска), B+-деревья (для диапазонного поиска), bitmap и инвертированные индексы (для категориальных и полнотекстовых данных), а также геоиндексы (R-tree).
- Альтернативный сторедж — LSM-деревья (Log-Structured Merge-trees), реализованные в RocksDB: быстрые записи, медленные чтения, с помощью слияния слоёв и bloom-фильтров для ускорения запросов.
- Skip list — вероятностная структура для быстрой сортировки и поиска, используемая в LSM-движках.
- Оптимизатор SQL-запросов преобразует запрос в реляционную алгебру и перестраивает план выполнения на основе статистики и законов эквивалентности для максимальной эффективности.
Введение в СУБД и их назначение
Системы управления базами данных (DBMS) нужны для удобного, безопасного и эффективного хранения больших объемов данных. Хранение в простых файлах, например, CSV или Excel, не обеспечивает:
- Независимость данных (data independence): абстракция доступа к данным независимо от их физического формата.
- Контроль конкурентного доступа (concurrency control): правильное управление одновременными запросами, предотвращение конфликтов обновления.
- Восстановление после сбоев (crash recovery): сохранение целостности данных, откат незавершённых операций.
- Управление доступом (security access control): разграничение прав пользователей к разным частям базы.
«СУБД забирает от нас часть самых больных проблем с файлами и при этом даёт мощные абстракции и гарантии.»
Архитектура реляционной СУБД
Классическая реляционная СУБД состоит из нескольких ключевых компонентов:
- Query Evaluation Engine: преобразование SQL-запроса сначала в реляционные выражения, затем в планы выполнения, выбор оптимального плана на основе статистики о данных.
- Concurrency Control и Transaction Manager: управление транзакциями, блокировками, версиями данных.
- Log Manager и Recovery Manager: ведение журналов изменений (write-ahead log) и механизмов восстановления после сбоев.
- Buffer Manager (буферный пул): кеширует страницы с данными из диска в память, управляет политиками вытеснения (например, LRU).
- Disk Space Manager: отвечает за физическое размещение страниц на диске.
- Файлы данных, индексы и системный каталог: хранят сами данные, вспомогательные структуры и метаданные о таблицах и индексах.
«Мы не строим все с нуля, а ориентируемся на реальные решения, понимая, как движущиеся части складываются в пазл.»
Организация стореджа: страницы и запись
Для хранения данных используется концепция страниц (pages) фиксированного размера (4KB, 8KB и др.), которые разбивают файлы таблиц:
- Каждая таблица — отдельный файл со страницами.
- Страница содержит заголовок, описывающий состояние и свободное место.
- Записи в странице могут быть фиксированной длины — просто друг за другом.
- Для переменных длины записей структура записей усложняется: у каждой записи есть заголовок с указателями на поля переменной длины.
- Имеется также механизм overflow pages (переполнения), куда выносятся слишком большие поля (например, большие JSON или BLOB).
Для более эффективного доступа к записям в странице вводится дополнительный уровень индирекции — таблица указателей на записи, расположенная в начале страницы (head), данные в конце. Это позволяет быстро найти, например, четвертую запись.
Обработка удалений: Vacuum
Удалённые или обновлённые записи не удаляются физически, чтобы избежать сложностей с параллельным доступом. Вместо этого:
- СУБД помечают записи как удалённые.
- Периодически запускается Vacuum — процесс «сборки мусора», который освобождает место, сдвигает записи, обновляет указатели.
Это комплексный процесс, требующий внимательного учёта потенциальных конкурирующих операций.
Способы хранения данных: Row-oriented vs Column-oriented
- Row-oriented (запись построчно) — классический подход, полезен для транзакционных систем (OLTP).
- Column-oriented (хранение по столбцам) — оптимален для аналитических систем (OLAP): при вычислении агрегатов на одном столбце читается меньше данных, возможна лучшая компрессия и векторные операции.
«Хранение по столбцам позволяет выгребать только нужные атрибуты и вычислять агрегаты очень эффективно.»
Метаданные и системный каталог
Системный каталог — «директория» по таблицам, индексам и правам доступа:
- Где лежит таблица, какие индексы затронуты?
- Какая схема у таблицы?
- Кто может её читать или изменять?
Каталог расположен как данные, но управляет организацией и безопасностью.
Буферный пул и политика кеширования
Доступ к данным с диска медленный (микросекунды), а из памяти — очень быстрый (наносекунды). Для ускорения:
- Используется буферный пул — кеш страниц из диска.
- Задача — эффективно загружать нужные страницы и решать, какую вытеснить.
- Простая политика — FIFO, подходит плохо.
- Часто используется LRU (Least Recently Used) — вытесняет страницу, которую давно не трогали.
- Проблема LRU — последовательное чтение (sequential flooding): один тяжелый запрос «прогревает» кеш и вытесняет часто используемые данные.
Индексы: кластеризованные, некластеризованные и виды структур
- Кластеризованный индекс диктует физический порядок записей по ключу.
- Некластеризованный — отдельная структура, указывающая на записи.
Типы индексов:
-
Хэш-индексы: отличный для точечных запросов (например, «найти по exact match»), но не поддерживают диапазонные запросы.
-
B+-деревья (B+Tree): универсальные структуры для быстрого диапазонного поиска и точных значений.
Классический B-дерево хранит ключи и данные везде, при вставках требует частых ребалансировок.
-
B+Tree хранит все данные только в листовых узлах, что улучшает скорость обхода диапазонов.
«B+-дерево позволяет эффективно находить диапазоны значений и делает сканирование линейным.»
- Bitmap индексы — используют битовые маски для атрибутов с ограниченным числом значений (пол, уровень, категория).
- Инвертированные индексы — для полнотекстового поиска, поисковых систем (напр. Elasticsearch).
- Векторные базы (embedding indices) — для семантического поиска с помощью векторных представлений (например, для понимания смысла текста, поиска похожих песен).
- Геоиндексы (R-tree и его вариации) — для пространственного поиска по двум и более измерениям.
LSM Storage: Log-Structured Merge-trees
LSM-деревья оптимизированы для интенсивных записей:
- Данные сначала попадают в memtable — структура в памяти (красно-чёрное дерево, skip list).
- При переполнении memtable сбрасывается в SST-файл — отсортированный файл на диске.
- SST-файлы компактифицируются и сливаются для уменьшения фрагментации и оптимизации чтений.
- Все файлы иммутабельны — не модифицируются на месте, что упрощает параллелизм и версионирование.
- Для ускорения поиска используются bloom-фильтры — позволяют быстро проверить, есть ли ключ в файле, с небольшой ошибкой типа «ложное присутствие» (false positive).
«LSM-сторедж — это стройная цепочка memtable → SST-файлы → компактификация, обеспечивающая высокую скорость записи.»
Skip list: вероятностная структура данных
- Skip list — вероятностная структура, ускоряющая поиск по отсортированному списку.
- Работает как несколько уровней связных списков, где верхний уровень «перескакивает» через данные.
- Средняя сложность поиска, вставки и удаления — O(log n).
- Используется в RocksDB и других LSM-движках для реализации memtable.
Оптимизация чтения и слияние SST-файлов
- При чтении нужно искать в нескольких SST-файлах разных уровней.
- Используются разные стратегии слияния (leveling, tiering) для управления количеством файлов и увеличения производительности.
- Важна сортировка данных для упрощения операций слияния.
Оптимизация и выполнение SQL-запросов
- Запрос сначала парсится в валидный SQL.
- Преобразуется в выражение реляционной алгебры — дерево операторов (проекции, фильтры, джойны и т.д.).
- Оптимизатор преобразует дерево, используя законы эквивалентности (коммутативность, ассоциативность, переноса условий) для постановки запроса в более эффективный вид.
- Выбирается оптимальный план с помощью статистики (количество строк, уровень прогрева данных, наличие индексов).
- План выполняется, даёт результат.
«Оптимизатор строит такое выражение, которое эквивалентно исходному запросу, но выполняется быстрее и эффективнее.»
Заключение
Этот урок подробно раскрывает внутренности стореджа СУБД и связанные компоненты — от хранения байт в страницах до сложных индексов и оптимизаций SQL-запросов. Был охвачен широкий спектр тем:
- Основания и мотивация создания СУБД.
- Архитектура реляционной базы.
- Механизмы хранения, управления страницами и вакуум.
- Различия row vs column форматов.
- Классические индексы: хэш, B+, bitmap, инвертированные, гео.
- Современные подходы с LSM-деревьями.
- Использование probabilistic структур (skiplist, bloom filter).
- Введение в оптимизацию планов SQL-запросов.
Эти знания помогут разбираться в технических особенностях баз данных, понимать новости рынка, технологии и принимать обоснованные решения по выбору СУБД и проектированию систем хранения.
📚 Разработка и внедрение распределённых баз данных — не простая задача, но понимание основ одной ноды стореджа — фундамент для будущих масштабируемых решений.