itmo_conspects

Проектирование баз данных

На этом курсе мы будем проектировать реляционные базы данных с помощью СУБД PostgreSQL

Также будут разбираться другие СУБД, реализующие другие модели данных, а также работа с контейнерами.

Лекция 1. Терминология

Модель данных - это концептуальное описание структуры данных, их взаимосвязей, а также правил и ограничений, регулирующих работу с данными. Система управления БД реализует определенную модель данных

Можно выделить такие модели данных:

Модели данных помогают нам преобразовать объекты доменной области в понятные компьютеру образы.

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

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

На курсе “Базы данных” мы изучали виды ключей записей в реляционной БД:

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

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

Первичный ключ - один из потенциальных ключей, выбранный для уникальной идентификации записей в таблице

Внешний ключ - атрибут или множество атрибутов, которые соответствуют потенциальному ключу некоторого (может быть того же самого) отношения

Также ключ может быть естественным и суррогатным

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

Пример: адрес электронной почты в базе клиентов

Плюсы: экономия памяти

Минусы: может измениться, может быть неопределенной длины

Суррогатный ключ - искусственно созданный уникальный идентификатор

Плюсы: не может потребоваться его менять, занимает мало места

Минусы: избыточные данные

Роль суррогатного ключа может принять автоинкремент (увеличенное на 1 значение ключа предыдущей созданной записи) или UUID

Также в PostgreSQL существуют такие типы данных:

Лекция 2. Модели данных

Как уже говорилось, модели данных со своими преимуществами и недостатками имеют свои области применения, в которых они будут наиболее эффективны

Реляционная

По статистике реляционные базы данных имеют наибольшую популярность в разработке

Реляционная модель организует данные в виде двухмерных таблиц со строгой структурой. Данные вносятся как строки, колонки которых соответствуют определенным типам данных. Между таблицами, отношениями, можно настроить семантические связи. Реляционные базы данных используют структурированный язык запросов SQL и соответствуют ACID свойствам

Преимущества реляционных баз данных:

Недостатки:

Применения реляционных БД:

Распространенные реализации: PostgreSQL, MySQL, SQLite, MariaDB, Microsoft SQL Server, Oracle DB, YandexDB

Колоночная

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

Преимущества:

Недостатки:

Применение:

Реализации: Cassandra, ScyllaDB, Google BigQuery, ClickHouse (колоночная реляционная СУБД)

Документоориентированная

Данные хранятся в виде документов (обычно представляющиеся в формате BSON), а не в виде строк таблицы. Документы объединяются в коллекции (по аналогии с таблицами, но без обязательного соответствия единой схеме). Причисляется к NoSQL

Преимущества:

Недостатки:

Применение:

Реализации: MongoDB, Firebase Realtime Database, Elasticsearch, Amazon DynamoDB, CouchDB

Графовая

Вместо таблиц и кортежей в графовой БД объектами являются узлы, ребра и их свойства. Графовые БД считаются NoSQL

Преимущества:

Недостатки:

Применение:

Реализации: Neo4j, Dgraph

Ключ-значение

Данные в “ключ-значение” БД хранятся в виде ключ-значение

Преимущества:

Недостатки:

Применение:

Реализации: Redis, Memcached, Etcd, Kafka

Временные ряды

Данные упорядочены по времени (в данном случае ключ - это метка времени)

Преимущества:

Недостатки:

Применение:

Реализации: InfluxDB, TimescaleDB, Prometheus

Векторная

Данные хранятся в виде векторов вещественных чисел

Преимущества:

Недостатки:

Применение: кластеры, техническое зрение, машинное обучение

Реализации: Pinecone, Milvus

Хранилище данных

Данных хранятся в виде файлах (текст, аудио, видео и др.) в файловой системе. Помимо этого каждый файл хранит метаданные. Доступ к файлам осуществляется по их именам и путям в файловой системы

Преимущества:

Недостатки:

Применение: хранение и распространение файлов

Реализации: Amazon S3, MinIO

Лекция 3. Функциональные требования и паттерны

Функциональные требования

При проектировании баз данных надо правильно уметь читать и составлять функциональные требования. Функциональные требования - это такой документ, который формально описывает сущности бизнес-логики, их свойства/связи и действия, которые они совершают или над которыми они совершают

Разберем функциональные требования для аналога Twitter:

Нейминг

В PostgreSQL используется snake_case, отношения называются в множественном числе, а атрибуты в единственном.

В первичных и внешних ключах указывается название отношения, чтобы избежать коллизии при объединении отношений, например, user_id и chat_id

Паттерны

Многое-ко-многим

Тривиальной реализацией связи многое-ко-многим будет являться атрибут первого отношения, в котором будут указаны первичные ключи второго отношения (в формате JSON, через запятую или по-другому), однако это будет не оптимально

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

Вертикальное разделение

Вместо того, чтобы добавлять новые атрибуты в исходное отношение, мы можем создать новое отношение с этим атрибутами. Например:

user_id username email
     
user_id big_string big_binary biography
       

Если во втором отношении поместить малоиспользуемые атрибуты, то мы получим выигрыш в оптимизации

Фиксированный набор значений

Фиксированный набор значений можно реализовать несколькими способами:

EAV (Entity-Attribute-Value)

EAV - отношение с тремя атрибутами:

EAV позволяет хранить данные с динамически изменяемой структурой, когда новые атрибуты могут добавлять без необходимости изменения структуры

Полиморфные связи

Допустим, что комментарии можем ставить и на посты, и на картинки. Тогда отношение с комментариями можем представить так:

comment_id content commantable_id commantable_type
       

Здесь commentable_type определяет, из какого отношения commentable_id будет являться ключом. Однако такой паттерн делает невозможным использование внешнего ключа

Список смежных вершин

Каждый кортеж будет хранить в себе указатель на родителя, тем самым моделируя дерево.

Пример:

name id parent
food 1 null
vegetable 2 1
potato 3 2
tomato 4 2
fruit 5 1
apple 6 5
banana 7 5

Вложенное множество

Вложенное множество (Nested set) - еще один способ моделирования дерева. Дерево можно представить как вложенное множество:

picture

Вместо хранения указателя на родителя, мы будем хранить указатели на левый и правый концы отрезков:

name left_end right_end
Одежда 1 22
Мужская 2 9
Женская 10 21
Костюмы 3 8
Брюки 4 5
Куртки 6 7
Платья 11 16
Юбки 17 18
Блузки 19 20
Вечерние платья 12 13
Сарафаны 14 15

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

Материализованный путь

Материализованный путь (Materialized path) - еще один способ моделирования дерева, в которым для каждого узла мы храним его путь из корня. Например:

name path
food 1
vegetable 1.1
potato 1.1.1
tomato 1.1.2
fruit 1.2
apple 1.2.1
banana 1.2.2

При помощи инструкции LIKE в SQL мы можем найти всех потомков какого-либо узла. Как и вложенные множества, такой паттерн рекомендуется применять для почти неизменяемых деревьев

Лекция 4. Архитектура PostgreSQL

Postmaster

При запуске PostgreSQL сервере первым делом создается процесс Postmaster. Postmaster - главный процесс, который принимает входящие подключения от клиентов, управляет созданием и завершением дочерних процессов

Для каждого нового подключения Postmaster порождает отдельный процесс, который обрабатывает SQL-запросы, выполняет планирование и возвращает результаты клиенту. Такой подход изолирует сессии и повышает стабильность системы

Фоновые процессы (Background Workers)

PostgreSQL использует дополнительные фоновые процессы для выполнения служебных задач:

Работа с памятью и хранением данных

PostgreSQL выделяет область общей памяти, используемую для:

Данные хранятся в виде файлов на диске. Для взаимодействия с хранилищем данных используются специализированные модули доступа и загрузчик данных

Обработка SQL-запросов

PostgreSQL обрабатывает запросы так:

  1. Прием запроса. Запрос поступает через клиент к дочернему процессу, созданному Postmaster

  2. Парсинг. SQL-текст разбивается на токены и строится синтаксическое дерево. Здесь производится проверка на ошибки

  3. Рерайтинг. Запрос преобразуется с учетом представлений, правил и триггеров

  4. Планирование и оптимизация. Планировщик запросов анализирует различные стратегии выполнения, используя собранную статистику, и выбирает наиболее оптимальный план

  5. Исполнение. Выполнение плана запроса: данные извлекаются, обрабатываются через узлы (фильтрация, сортировка, соединения и т.д.) и формируется результат

  6. Возврат результатов. После выполнения запроса результаты возвращаются клиенту. Для операций, изменяющий данные, делается коммит изменений

MVCC

PostgreSQL реализует механизм MVCC (multiversion concurrency control, многоверсионный контроль согласованности), позволяющий обеспечить согласованность данных при одновременном доступе множества пользователей

Внутри себя PostgreSQL хранит счетчик транзакций, который можно получить функцией txid_current(). При выполнении транзакции этот счетчик увеличивается. Каждая запись в отношении имеет системные атрибуты xmin и xmax

Таким образом, эти атрибуты задают жизненный цикл каждого снимка каждой записи, чтобы соблюдать целостность данных.
Помимо них есть еще cmin и cmax. Они обозначают жизненный цикл самой записи и не затрагиваются при обновлении записи

Vacuum и Autovacuum

Так как MVCC требует очень много памяти на диске, нужны инструменты, очищающие неактуальные данные. В PostgreSQL есть:

Лекция 5. Встреча с Олегом Сергеевичем Бартуновым

Вместо этой лекции была встреча с Олегом Сергеевичем Бартуновым, сооснователем компании Postgres Professional, развивающей форк PostgreSQL для enterprise-решений. Здесь же представлено краткое содержание того, что на ней было - крайне рекомендуется послушать все самим

Часть 1

Часть 2

Часть 3

Часть 4

Часть 5

Часть 6

Первые данные появились, когда человек захотел с кем-то пообщаться или что-то сохранить. Например, астрономия. Астрономические наблюдения требуют больших объемов хранения данных

Сначала примитивными базам данных были шумерские таблички для учета казны и налогом, потом появились каталоги по авторам в библиотеках. Файлы стали первой попыткой организовать данные

Первой настоящей базой данных стала IMS (Information Management System, другое название DB1). IBM создала ее по тендеру для ракеты Saturn V. Она была иерархической и хранила в себе состояние компонентов ракеты

После этого Кодд выпускает свою статью о реляционной модели данных и реляционной алгебре. После этого, Дональд Чемберлин и Рэймонд Бойс создают язык SEQUEL, который изменит свое название на SQL

В период с 75-ого по 82-ой создаются прототипы реляционной СУБД System R (или же DB2)

До этого, узнав о статье Кодда, ученые из университета Беркли Майкл Стоунбрейкер и Юджин Вонг создают свою СУБД под названием Ingres (Interactive Graphics Retrieval System)

Намного позднее Стоунбрейкер с 1986 по 1994 создает реляционную СУБД Postgres (производное от Post Ingres). Postgres изначально распространялся с открытым исходным кодом. Изначальный язык запрос POSTQUEL был заменен на SQL - с тех пор она стала называться PostgreSQL

Олег Бартунов начал вносить вклад в код PostgreSQL в 1995 году. С тех пор благодаря ему и другим разработчикам из России PostgreSQL обзавелся интернационализацией, поддержкой локалей, полнотекстовым поиском, jsonb. В частности благодаря Вадиму Михееву в PostgreSQL появился WAL, MVCC, vacuum и другие фичи

Сейчас же компания Postgres Professional является вторым вкладчиком в мире в кодовую базу PostgreSQL

Лекция 6. Контейнеризация

Контейнеризация - абстракция вокруг группы процессов, позволяющая их изолировать и предоставляющая виртуализацию на уровне операционной системы. В отличии от полной виртуализации операционной системы, контейнеризация не загружают все ядро ОС целиком, а лишь использует механизмы ядра Linux - в частности для этого используются две фичи Linux: контрольные группы (cgroups) и пространства имен (namespaces)

Пространства имен - набор инструментов (функции ядра) для контроля того, что видит отдельный процесс и какие действия может выполнять как процесс, так и пользователь внутри пространства имен

Раньше процесс можно было ограничивать только по процессорному времени. С появлением контрольных групп стало возможным ограничивать использование ресурсов сетевых, памяти и так далее. Контрольные группы включают в себя контроллеры для учета и управления ресурсами

Самая популярная утилита для управления контейнерами - Docker.
Docker, помимо реализации пространства имен и контрольных групп, включает в себя управление образами, CLI для работы с контейнером и прочее

Образ (Image) - это по сути архив с предустановленными заранее программами и библиотеками для работы приложения. Образ может определяться специальным файлом с названием Dockerfile, например:

# Делаем форк на основе готового образа с установленным Python
FROM python:3.12
WORKDIR /usr/local/app

# Устанавливаем зависимости приложения
COPY requirements.txt ./
RUN pip install --no-cache-dir -r requirements.txt

# Копируем исходники
COPY src ./src
EXPOSE 5000

# Создает нового пользователя, чтобы не запускать приложение от лица root
RUN useradd app
USER app

CMD ["uvicorn", "app.main:app", "--host", "0.0.0.0", "--port", "8080"]

Каждая строчка в файле Dockerfile называется слоем (layer). Чтобы собрать из Dockerfile полноценный образ, воспользуемся командой

docker build -t my-python-app .

В Docker Desktop можно посмотреть на слои образа:

alt text

Также можно посмотреть публичные образы в Docker Hub.

Собранный образ теперь можно запустить в контейнере.
В файле docker-compose.yml можно указать конфигурацию контейнера

# Версия параметров Compose
version: "2"

services:
  postgres:
    # Имя образа (в данном случае с готовым PostgreSQL 14)
    image: postgres:14

    # Имя контейнера
    container_name: postgres_db

    # Переназначение портов между контейнером и хостом
    ports:
      - "5432:5432"

    # Привязка файловой системы контейнера с файловой системой хоста
    volumes:
      - ./scripts:/docker-entrypoint-initdb.d
      - ./pgdata:/var/lib/postgresql/data

    # Переменные среды: имя, пароль и название БД в PostgreSQL
    environment:
      POSTGRES_USER: myuser
      POSTGRES_PASSWORD: mypass
      POSTGRES_DB: mydb

Чтобы запустить контейнер, воспользуемся командой

docker compose up

в каталоге с docker-compose.yml. Флаг -d запустит контейнер в фоновом режиме. Команда

docker compose down

прервет выполнение в контейнере, а команда

docker compose stop

остановит контейнер с возможностью возобновления. При помощи

docker ps

можно посмотреть все запущенные контейнеры.

В примере выше мы связали локальную папку ./scripts с /docker-entrypoint-initdb.d. При запуске PostgreSQL выполнит все .sql и .sh-скрипты, находящиеся в ней, таким образом, можно задать начальную схему базы данных

Лекция 7. Миграция базы данных

Миграция описывает последовательность изменений, которые необходимо применить к базе данных. Эти изменения могут включать создание новых таблиц, изменение существующих, добавление или удаление столбцов, создание индексов, изменение ограничений и так далее

Миграция должна удовлетворять свойству идемпотентности - свойство объекта или операции при повторном применении операции к объекту давать тот же результат, что и при первом. Для осуществления этого в PostgreSQL есть фраза IF NOT EXISTS

Скрипты с миграциями лучше всего версионировать, например, называть:

Помимо скрипта применения миграции рекомендуется иметь скрипт для отката. Тогда прямые изменения называют up-миграцией, а обратные - down-миграцией

Миграции можно генерировать при помощи:

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

Во время совершения миграций могут возникнуть сложности, такие как нарушение обратной совместимости или повышенная нагрузка на БД

Например, операция

ALTER TABLE table_name ADD COLUMN SET DEFAULT;

является небезопасной, приводящая к даунтауму, так как она блокирует всю таблицу, пока ставит дефолтные значения каждой записи. Правильным решением будет:

ALTER TABLE table_name ADD COLUMN column_name data_type;
ALTER TABLE table_name ALTER COLUMN column_name SET DEFAULT default_value;

Чтобы изменить схему таблицы и переместить даные в ходе миграции, можно поступить так:

Такие ETL-инструменты (от Extract-Transform-Load) как Apache NiFi, Pentaho Data Integration, Apache Airflow могут автоматически производить миграции данных

Лекция 8. Транзакции

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

Транзакция должна соблюдать свойства ACID:

Чтобы соблюдать согласованность и целостность данных, в PostgreSQL можно установить ограничения на атрибуты:

Чтобы соблюдать изоляцию транзакций, в PostgreSQL существуют 4 уровня изоляции:

Уровень изоляции Грязное чтение Неповторяемое чтение Фантомное чтение Аномалия сериализации
Незавершенное чтение Разрешено, но не в PostgreSQL Возможно Возможно Возможно
Завершенное чтение Невозможно Возможно Возможно Возможно
Воспроизводимое чтение Невозможно Невозможно Разрешено, но не в PostgreSQL Возможно
Сериализуемость Невозможно Невозможно Невозможно Невозможно

Для управления транзакция в PostgreSQL есть такие инструкции:

Опишем проблемы, которые решают данные уровни изоляции:

Грязная запись - аномалия, при которой обе транзакции записывают данные в один и тот же кортеж до коммита. Если какая-либо из них откатиться, то потеряется запись другой:

Транзакция 1 Транзакция 2  
BEGIN; BEGIN;  
UPDATE accounts SET balance=200 WHERE id=1;    
  UPDATE accounts SET balance=300 WHERE id=1;  
COMMIT;   Транзакция 1 коммитит 300
  ROLLBACK; Откат до 100, хотя транзакция 1 выполнилась успешно

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

Транзакция 1 Транзакция 2  
BEGIN; BEGIN; Обе читают исходное значение
SELECT balance FROM accounts WHERE id=1;   Транзакция 1 читает 100
  SELECT balance FROM accounts WHERE id=1; Транзакция 2 читает 100
UPDATE accounts SET balance=100+50 WHERE id=1;   Транзакция 1 записывает 150
  UPDATE accounts SET balance=100+20 WHERE id=1; Транзакция 2 записывает 120
COMMIT;    
  COMMIT; Обновление транзации 1 потеряно

Грязное чтение - такая аномалия возникает, когда транзакция читает еще не зафиксированные изменения, сделанные другой транзакцией:

Транзакция 1 Транзакция 2  
BEGIN; BEGIN;  
UPDATE accounts SET balance=200 WHERE id=1;    
  SELECT balance FROM accounts WHERE id = 1; Транзакция 2 читает 200
ROLLBACK;   Откат от 200 к 100
  SELECT balance FROM accounts WHERE id = 1; Транзакция 2 читает 100

Неповторяющееся чтение возникает, когда транзакция читает одну и ту же строку два раза, а в промежутке между чтениями вторая транзакция изменяет ее, таким образом результат чтения разный:

Транзакция 1 Транзакция 2  
BEGIN; BEGIN;  
SELECT balance FROM accounts WHERE id=1;   Транзакция 1 читает 100
  UPDATE accounts SET balance=200 WHERE id=1;  
  COMMIT; Коммит значения 200
SELECT balance FROM accounts WHERE id=1;   Транзакция 1 читает 200 в той же транзакции

Фантомное чтение возникает, когда между чтениям кортежей в одной транзакции другая транзакция добавляет новый кортеж:

Транзакция 1 Транзакция 2  
BEGIN; BEGIN;  
SELECT * FROM accounts WHERE balance > 100;   Транзакция 1 видит 2 строки
  INSERT INTO accounts(id, balance) VALUES (3, 300);  
  COMMIT;  
SELECT * FROM accounts WHERE balance > 100;   Tранзакция 1 теперь видит 3 строки

Например, здесь

IF (SELECT amount FROM accounts WHERE id = 1) >= 1000 THEN
  UPDATE accounts SET amount = amount - 1000 WHERE id = 1;
END IF;

может возникнуть фантомное чтение или грязное чтение. Чтобы исправить, можно:

Лекция 9. Индекс

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

Индекс устанавливает соответствие между ключом (например, значением проиндексированного столбца) и строками таблицы, в которых этот ключ встречается. Строки идентифицируются с помощью TID (Tuple ID), который состоит из номера блока файла и позиции строки внутри блока

Несмотря на то, что индекс ускоряет поиск записи внутри таблицы (а также выборку, сортировку, агрегирование), изменение записей (а также создание новой, удаление и другие) в таблице требует перестройку индекса

Индекс может быть реализован как:

Хеш-индекс

Хеш-функция - функция, преобразующая массив входных данных произвольного размера в выходную битовую строку определённого (установленного) размера в соответствии с определённым алгоритмом

Так как хеш-функция может дать все, что угодно, то единственная операция, которую поддерживает хеш-индекс, - поиск по условию равенства

Хеш-индекс устроен так:

Элементы корзин упорядочены по хеш-кодам ключей, а подходящие идентификаторы эффективно находятся двоичным поиском

До версии PostgreSQL 10 хеш-индексы не журналировались

Недостатки: кластеризация таблицы по хешу нет, упорядочить кортежи нельзя, а также не работает с null-атрибутами

B-дерево

B-дерево - сбалансированное дерево поиска

B-деревом называется дерево, удовлетворяющее следующим свойствам:

btree

Каждый узел дерева содержит несколько элементов, состоящих из ключа индексирования и ссылки

B-дерево является очень распространенным

GiST (Generilized Search Tree)

GiST - фреймворк, который позволяет создавать пользовательские реализации для различных видов данных

Например: для географических данных, полнотекстового поиска, интервалов, деревьев

GiST реализует B-дерево, R-дерево и другие деревья

Идея R-дерева состоит в том, что плоскость разбивается на прямоугольники, которые в сумме покрывают все индексируемые точки

Индексная запись хранит ограничивающий прямоугольник, а предикат можно сформулировать так: точка лежит внутри данного ограничивающего прямоугольника

rtree

Также GiST используется для выбора из набора документов те, которые соответствуют поисковому запросу (то есть полнотекстовый поиск, Full Text Search). Чтобы полнотекстовый поиск работал быстро, его нужно поддержать индексом. Поскольку индексируются не сами документы, а значения типа tsvector, есть два варианта: построить индекс по выражению, с приведением типа, или создать отдельный столбец типа tsvector и индексировать его

GIN (Generalized Inverted Index)

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

This site is open source. Improve this page.