Глава 3. Подсистемы хранения и извлечения данных
Published: 2023-11-12 20:56:32

## Вступление

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

## Индексы

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

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/791bc5lt1kotbd8wx9yl.png)


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

Плюсы:

- быстрое чтение O(1) поиск по индексу + перемещение на позицию в файле.

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

- добавление в конец и слияние - очень быстрые операция на SSD и особенно на HDD дисках

- благодаря слиянию достигается лишь небольшая фрагментация данных

Минусы:

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

- нет возможности поиска по интервалу


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

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

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

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

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

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

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x0l3nnxmvhnhql9g00hn.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pq4f40bqb225k8wczxur.png)



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


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



### В-деревья


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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v8c3vquqtho0ejsil2dp.png)



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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6tia5wi06iyigr6pyam8.png)



Если на странице нет места, то создается 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) или потоковую загрузку.


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


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

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



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x5rml5t2yvfqzc40qj57.png)




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




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

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oqfk6y4lop5j2dlemepc.png)




Для оптимизации хранения полей, у которых фикисрованный набор значений, можно использовать битовые маски.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/blkmbb9blrcto56enfhj.png)