Глава 3. Подсистемы хранения и извлечения данных

Вступление

Журнал - самая простая структура для хранения данных в принципе. Она позвляет дописывать данные только в конец.
Если рассмотреть данные вида ключ-значение, то при вставке записи с тем же ключом в журнале будут дублирующие данные.
Сложность поиска по журналу - O(n). Это много.
Для более эффективного поиска данных используются вспомогательные структуры, производные от основных данных - индексы.
Поддержка индексов приводит к более быстрому поиску, но более медленной вставке и удалению, так как индексы тоже подлежат обновлению.
Поэтому на усмотрение разработчика выбор индексов.

Индексы

Журнал + хэш карта

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

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

Плюсы:

быстрое чтение O(1) поиск по индексу + перемещение на позицию в файле.
реализация конкурентного доступа упрощается, так как данные идемпотентны, ведь любое изменение записи ведет к созданию новой записи
добавление в конец и слияние - очень быстрые операция на SSD и особенно на HDD дисках
благодаря слиянию достигается лишь небольшая фрагментация данных

Минусы:

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

Также нужно обдумать следующие вопросы:

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

Описываемый метод исользуется в подсистеме BitCask NoSQL БД RiakDB

Sorted String Table + хэш карта

Журнал обладал тем минусом, что данные в нем не были отсортированы. Поэтому объединение сегментов там выполнялось за O(n^2), а для поиска по интервалу требовалось для каждого значения из интервала осуществлять отдельный поиск.

Поэтому эффективнее держать часть данных в оперативной памяти, а часть - на диске.
В памяти удобно держать сбалансированную структуру данных (данные в ней отсортированы - при вставке происходит ребаланс),
которую бы можно было при достижении определенного размера скидывать на диск в виде Sorted String Table (отсортированная строковая таблица), которая в фоне уплотняется, как в сортировке слиянием - O(n).

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

Описываемый метод используется в БД LevelDB

В-деревья

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

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

Если на странице нет места, то создается 2 новых полупустых страницы, куда копируются данные из старой таблицы и со стороны родителей перевешиваются указатели на новые страницы.

B-дерево - сбалансированное дерево. Его высота и сложность поиска - O(log(n)).

На практике дерево содержит высоту 3-4 уровня.

Чтобы сделать бд с индексом на основе B-дерева отказоустойчивой, используются журнал упреждающей записи (WAL - write ahead log),
в который записывается действие - только после этого происходит изменение самого B-дерева (а само изменение из-за ребаланса может быть значительным).

Оптимизации:

можно хранить на страницах не полные значение ключей, а часть (актуально, если ключ - строка), ведь во внутренних узлах при сравнении используется лишь часть ключа.
вместо wal журнала можно делать копию узлов b дерева, которые связаны с измененной страницей. Это полезно при конкурентном доступе.

По итогу SS таблицы быстрее при записи, но медленнее при чтении, чем B-деревья.

Хранение в памяти, а не на диске

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

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

Поэтому в последнее десятилетие активно развивается направление in-memory баз данных, например, Memcached.

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

Паттерны использования БД

Существует 2 сценария использования БД - обработка транзакций в реальном времени (OLTP) и аналитика данных (OLAP). Первый используется обычными пользователями, а второй - аналитиками данных.
При обработке транзаций в реальном времени обычно ищется небольшое кол-во записей по ключу (а общий размер всех данных от гб до тб). При аналитике происходит агрегация больших объемов данных (от тб до пб).

Поступление данных в OLAP и OLTP.

Поступление данных в OLTP хранилища происходит через какие-то бизнес процессы (работы клиента с системой обслуживания или работа с POS терминалом). Соответственно, требуется высокая доступность БД и низкая задержка в ответе.

Поступление данных в OLAP хранилища осуществляется через групповой испорт (ETL - extract transform load) или потоковую загрузку.

Схемы для аналитики

В аналитике популярна схема звезда и ее развитие - снежинка.

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

В снежинке точно так же, только измерения разделяются на подизмерения.

Столбцовое хранение

В таблице могут быть триллионы строк и петабайты данных. Значения соседних полей одной строки лежат рядом на диске. В аналитике обычно требуются не все поля, но все строки. Поэтому удобно хранить данные не по строкам, а по столбцам.
Тогда можно на диске иметь свой файл под каждое поле.