Нереляционные базы данных

Нереляционные базы данных (NoSQL) – обобщённое семейство систем управления данными, в которых отсутствует жёсткая таблицебазированная модель с фиксированной схемой и декларативным SQL в его классическом виде. NoSQL-СУБД ориентированы на горизонтальное масштабирование, высокую доступность и работу с полуструктурированными и распределёнными данными. Для подготовки к ЕГЭ по информатике эта тема важна, поскольку систематизирует знания о структурах данных (хеш-таблицы, графы, деревья), графовых алгоритмах (BFS/DFS), оценке сложностей, консистентности и моделировании вычислений в распределённой среде.

Формальная постановка и отличие от реляционной модели

1. Абстрактная СУБД
   

   Любая СУБД можно задать кортежем:

   DB = <D, Q, O, Σ, Consistency>

   где

   • D – модель данных (множество допустимых структур записей/объектов);

   • Q – модель запросов (операции чтения/записи/агрегации);

   • O – операционные свойства (репликация, шардирование);

   • Σ – ограничения целостности (уникальность, ссылки);

   • Consistency – модель согласованности (см. §3).

   В реляционной модели D – отношения (таблицы), Q – реляционная алгебра/SQL, Σ – ключи/СУБД-ограничения; в NoSQL D варьируется (ключ–значение, документ, широкая колонка, граф), Q – специализированные API, а транзакционные гарантии чаще локализованы.

2. Классы NoSQL (модель данных и запросов)
   

   1. Ключ–значение (Key–Value)

   2. D: K → V, где K – уникальный ключ, V – непрозрачное значение (байтовый буфер/строка)

   3. Q: Get(K), Put(K,V), Delete(K), иногда Scan(prefix)

   Основа – хеш-индексация; простейшая и самая быстрая модель точечных операций.

   1. Документные

   2. D: коллекции документов (JSON/BSON/двойки «поле:значение», допускается вложенность и разреженность)

   3. Q: поиск по полям, индексы по путям, агрегирующие конвейеры

   Схема «мягкая» (schema-optional), денормализация приветствуется.

   1. Колонночные/широкие колонки (Wide-Column)

   2. D: семейства колонок; ключ строки → множество (колонка → значение)

   3. Q: чтение диапазонов по ключу, слайсы по колонкам, TTL

   Эффективны для временных рядов и больших сканирований по ключевым диапазонам.

   1. Графовые

   2. D: G = (V, E, A_V, A_E) – вершины, рёбра и их атрибуты

   3. Q: обходы по рёбрам, поиски путей/шаблонов, центральности

   Основаны на индексах по идентификаторам и списках смежности.

ACID vs BASE, и транзакционные шаблоны

• ACID (Atomicity, Consistency, Isolation, Durability) – классический транзакционный набор гарантий, типичен для реляционных БД.
• BASE (Basically Available, Soft state, Eventual consistency) – инженерный принцип для распределённых систем: «в основном доступно», «состояние может временно расходиться», «в итоге согласуется».

В NoSQL часто применяются локальные транзакции (на одном ключе/разделе). Для сложных инвариантов:

• «Саги» (распределённые цепочки с компенсациями);
• Идемпотентные операции и условные обновления (CAS – compare-and-set).

Модели согласованности и кворумные записи

1. CAP-шаблон и PACELC (инженерная эвристика)
   

   • CAP: при сетном разделении (P) система выбирает между строгой согласованностью (C) и доступностью (A).

   • PACELC дополняет: Else (когда нет разделения) – дилемма «Latency vs Consistency».

2. Уровни согласованности
   

   • Strong consistency – чтение сразу видит последний подтверждённый записью результат (обычно при кворуме и синхронной репликации).

   • Eventual consistency – при отсутствии новых обновлений все копии «в итоге» сходятся.

   • Read-your-writes, Monotonic reads/writes – причинно-согласованные свойства для одного клиента.

3. Кворумная репликация.
   

   Пусть N – число реплик (репликационный фактор), W – кворум записи, R – кворум чтения. Классическая достаточная эвристика строгой согласованности:

   W + R > N

   а также

   W > N/2  и  R > N/2

   Чтение «последнего» значения обеспечивается перекрытием множеств реплик.

Физические структуры хранения и индексация

1. LSM-деревья и компакции
   

   Для логически последовательной записи используются LSM-деревья (Log-Structured Merge-Trees):

   • записи сначала буферизуются в памяти (memtable), затем сбрасываются сегментами;

   • чтение объединяет несколько сегментов + Bloom-фильтры для отбрасывания ложных поисков.

   Приближённая вероятность ложноположительного ответа Bloom-фильтра:

   p ≈ (1 - e^{-(k * n) / m})^k

   где m – число битов фильтра, n – число ключей, k – число хеш-функций. Оптимальный k ≈ (m/n) * ln 2.

2. B-деревья и вариации
   

   В некоторых NoSQL (особенно документовых) основой служат B+-деревья для вторичных индексов (по полям/путям).
   Правило: при частых «горячих» вставках и больших ключах – предпочтительнее LSM; при преимущественно чтениях по точным ключам – B+ может давать лучшую латентность.

3. Индексы
   

   • Первичный (по ключу раздела/идентификатору) – определяет физическое размещение.

   • Вторичные (по атрибутам) – могут быть:

   • глобальными (охватывают все разделы, дороже в записи),

   • локальными (внутри раздела, дешевле, но ограничены диапазоном ключа).

Проектирование схемы и запросов (правила)

Правило 1. Запросы диктуют схему.
Сначала фиксируйте набор критичных запросов и шаблонов доступа, затем выбирайте модель данных (денормализация допустима и ожидаема).

Правило 2. Минимизируйте join-операции.
В документных БД – вкладывайте тесно связанные данные «рядом» (в один документ), чтобы обеспечить атомарность на уровне документа.

Правило 3. Подбирайте ключ раздела под распределение нагрузки.
Избегайте «горячих ключей». Для временных рядов применяйте «бакетизацию»:  partition_key = (device_id, floor(timestamp / window))

Правило 4. Ограничивайте размер единицы атомарности.
Документ большого размера → рост латентности, сложности обновлений и риск фрагментации.

Правило 5. Индексы – осознанная цена.
Каждый вторичный индекс – это дополнительные записи/компакации; поддерживайте только те, которые обслуживают реальные запросы.

Правило 6. TTL и архивирование.
Для потоковых/логовых данных задавайте время жизни (TTL) и политику компакций.

Правило 7. Консистентность как контракт API.
Явно документируйте «уровень чтения/записи» (например, QUORUM/ONE) и последствия для клиента.

Алгоритмы на моделях NoSQL и оценка сложности

• Key–Value: точечный доступ O(1) амортизированно (хеш-индекс/LSM с Bloom), сканы по префиксу – O(k + r) (k – длина префикса, r – количество результатов).
• Документы: поиск по индексу – O(log n) (B+-дерево) или O(1) амортизированно (LSM+фильтр); агрегирующие конвейеры линейны по числу затронутых документов.
• Колонки: чтение диапазона по ключу – O(log n + r); массовые вставки – быстрая запись (LSM).
• Граф: обход в ширину BFS – O(|V|+|E|); запросы путей – контролировать глубину/фильтры. 

Типичные ошибки и анти-паттерны

1. Горячий раздел (hot partition). Симптомы – дисбаланс нагрузки, рост латентности. Лечение – переразбиение ключа, соление (salting).
2. Слишком глубокие документы. Тяжёлые обновления и большие IO – нормализовать до разумной вложенности.
3. Индекс на каждый атрибут. Избыточные обновления и компакции – оставьте только нужные.
4. Смешение уровней согласованности. Клиент читает ONE, пишет QUORUM и ожидает сильной консистентности – документируйте и проверяйте W+R>N.
5. Непродуманная TTL: лавина удалений/компакций в один момент – разнести окна истечения.

Связь с ЕГЭ по информатике

• Структуры данных: ключ-значение ↔ хеш-таблица; индексы ↔ деревья поиска; графовые БД ↔ списки смежности.
• Алгоритмы: BFS/DFS (графы), подсчёт частот (ассоциативные массивы), сортировка/агрегации.
• Сложности: аргументация O(·) для обходов и запросов.
• Моделирование: причинно-следственные зависимости, кворумы, инварианты – логика, полезная для доказательства корректности решений.
• Файловые форматы: JSON/CSV и обработка массивов – типовое умение для задач анализа данных.

Мини-шпаргалка (формулы и определения)

Кворумная согласованность:

N – число реплик, W – кворум записи, R – кворум чтения

Достаточно: W + R > N; обычно W > N/2 и R > N/2. 

Bloom-фильтр (ложноположит. вероятность):

p ≈ (1 - e^{-(k * n) / m})^k,  оптимальный k ≈ (m/n) * ln 2. 

Сложности:

BFS (граф): O(|V| + |E|)

Поиск по B+-дереву: O(log n)

Скан по префиксу (LSM + индекс): O(log n + r) ~ O(r) на длинных диапазонах

Пять упражнений (академический формат)

Упражнение 1. Проектирование ключа раздела и предотвращение «горячего» ключа
Система хранит события сенсоров events(device_id, ts, payload) с интенсивностью: у одного устройства – в 100 раз больше событий, чем у остальных.
a) Предложите ключ раздела и кластеризации для колонночной БД, чтобы избежать «hot partition».
b) Докажите равномерность распределения (на уровне ожидания) при выбранном ключе.
c) Оцените сложность чтения последних r событий конкретного устройства.

Упражнение 2. Кворумы и согласованность
Репликационный фактор N=5.
a) Назовите пары (W,R), обеспечивающие строгую согласованность, и объясните почему.
b) Сравните латентность чтения R=1 vs R=3 при фиксированном W=3.
c) Для нагрузки «много чтений, мало записей» предложите W,R и обоснуйте выбор.

Упражнение 3. Документная модель и индексы
Дан документ order с массивом items[] и полями user_id, created_at, status. Типовые запросы:

1. последние заказы пользователя;

2. поиск заказов по status и интервалу дат;

3. подсчёт популярности товара по item_id.
   a) Спроектируйте индексы (какие – составные, какие – одиночные).
   b) Объясните, когда потребуется денормализация «товар → список заказов» и её цена.
   c) Оцените асимптотику запросов с предложенными индексами.

Упражнение 4. LSM-дерево и Bloom-фильтр
Пусть n=10^6 ключей, фильтр m=10^7 бит.
a) Оцените оптимальное число хешей k и приближённую вероятность ложноположительного ответа p по формуле из шпаргалки.
b) Объясните влияние p на число чтений с диска при отсутствии ключа.
c) Предложите, как изменить m для достижения p ≤ 1% и оцените затраты памяти.

Упражнение 5. Графовая БД и запросы путей
Хранится ориентированный граф «пользователь → интерес». Требуется: найти всех пользователей, у которых есть путь к интересу X длины ≤ 3, и вывести кратчайшую длину.
a) Опишите структуру хранения (списки смежности, индексация по вершинам).
b) Предложите алгоритм (BFS с ограничением глубины) и оцените сложность.
c) Укажите, какие вторичные индексы ускорят фильтрацию начальных вершин по атрибутам.

Заключение

Нереляционные СУБД объединяют разнообразные модели данных и уровни согласованности, предлагая инженеру широкий спектр компромиссов между скоростью, доступностью и целостностью. Чёткое понимание классов NoSQL, кворумной репликации, структур хранения (LSM/B+), индексации, а также правил проектирования («запросы диктуют схему», «избегать hot-keys») позволяет строить масштабируемые и корректные решения. Эти же принципы усиливают навыки, проверяемые на ЕГЭ по информатике: работа со структурами данных, графовыми алгоритмами, оценками сложности и аккуратной формализацией условий и инвариантов.