Эта статья является конспектом книги «Designing Data-Intensive Applications».

В этом конспекте рассмотрим, как сохранить полученные от пользователя данные и как найти их снова в случае запроса с точки зрения БД.

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

Базовые структуры данных БД

Наверное, самой простой БД в мире, реализованная в виде двух функций, является командная оболочка Bash. Обе функции реализуют хранилище типа «ключ — значение». Можно вызвать команду db_set key value для сохранения key и value в базе данных. Затем можно вызвать команду db_get key для поиска последнего относящегося к искомому ключу значения и его возврата.

Лежащий в их основе формат хранения очень прост: он представляет собой текстовый файл, в котором каждая строка содержит пару «ключ — значение», разделенную запятой. Каждый вызов функции db_set приводит к добавлению данных в конец файла, так что при обновлении ключа несколько раз старые версии значений не будут затерты. Такой механизм называется журналом, представляющий собой файл, предназначенный только для добавления данных в его конец.

Производительность функции db_get ужасна в случае большого количества записей в БД. Каждый раз, когда нужно найти ключ, db_get приходится просматривать всю базу от начала до конца, выискивая вхождения ключа. Говоря в алгоритмических терминах, сложность поиска — порядка O(n): при удвоении количества записей n в БД поиск занимает вдвое больше времени.

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

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

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

Хеш-индексы

Хранилища данных типа «ключ — значение» очень схожи с типом «словарь», реализуемым обычно в виде хеш-карты (hash map)/хеш-таблицы (hash table).

Предположим, что наше хранилище работает только путем добавления в конец файла. Тогда простейшая стратегия индексации такова: хранить в оперативной памяти хеш-карту, в которой каждому ключу поставлено в соответствие смещение (относительный адрес) в файле данных — место, где находится значение, как показано на рис. 2. При добавлении в файл новой пары «ключ — значение» происходит также обновление хеш-карты для отражения в ней относительного адреса только что записанных данных. Если нужно найти значение, то можно воспользоваться хеш-картой для поиска относительного адреса в файле данных, перейти в это место и прочитать значение.

Представленный подход может показаться некоторым упрощением, но вполне жизнеспособен. Фактически именно так работает Bitcask (подсистема хранения в распределенной NoSQL СУБД Riak). Более подробно можно прочесть в книге.

Рис. 2 - Сохранение журнала пар «ключ — значение» в CSV-подобном формате, индексированном с помощью хеш-карты в оперативной памяти

Пока что рассматривали только запись в конец файла. Как же избежать ситуации исчерпания места на диске? Хорошим решением будет разбить журнал на сегменты определенного размера, закрывая файл сегмента при достижении им определенного размера и записывая последующие данные уже в новый файл. Затем можно выполнить уплотнение (compaction) этих сегментов, как показано на рис. 3. Уплотнение означает отбрасывание дублирующихся ключей из журнала и сохранение только последней версии данных для каждого ключа. Более того, поскольку уплотнение часто приводит к значительному уменьшению размера сегментов, можно также слить несколько сегментов в один во время уплотнения.

Рис. 3 - Уплотнение журнала типа «ключ — значение» (например, учет количества воспроизведений каждого видео) с сохранением только последнего значения для каждого ключа

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

Чтобы воплотить эту простую идею в жизнь, понадобится учесть немало нюансов. Более подробно можно прочесть в книге. Если кратко, то нужно учесть – формат файлов, удаление записи, восстановление после сбоев, недописанные записи, управление конкурентным доступом.

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

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

Однако у индексов хеш-таблиц тоже есть ограничения.

Хеш-таблица должна помещаться в оперативной памяти, так что если очень много ключей, то данный тип индекса скорее всего не подойдет. В принципе, можно поддерживать хеш-карту на диске, но, к сожалению, добиться хорошей ее производительности непросто.
Запросы по диапазону неэффективны. Например, невозможно с легкостью просмотреть все записи между kitty00000 и kitty99999 — необходимо искать каждый ключ отдельно в хеш-картах.

Далее рассмотрим индексную структуру, у которой нет этих ограничений.

SS-таблицы

Давайте теперь поменяем формат файлов сегментов: потребуем, чтобы последовательность пар «ключ — значение» была отсортирована по ключу.

Назовем новый формат отсортированной строковой таблицей (sorted string table, SSTable) или SS-таблицей. Потребуем также, чтобы каждый ключ встречался лишь один раз в каждом объединенном файле сегмента (процесс уплотнения сразу гарантирует это). У SS-таблиц есть несколько больших преимуществ перед журнальными сегментами с хеш-индексами.

Первое преимущество. Объединение сегментов выполняется просто и эффективно, даже если размер файлов превышает объем доступной оперативной памяти. Этот подход близок к используемому в алгоритме сортировки слиянием (mergesort). Он показан на рис. 4: начинаем с одновременного чтения входных файлов, просматриваем первый ключ в каждом из файлов, копируем ключ в соответствии с порядком сортировки в выходной файл и повторяем эти действия. В результате получаем новый объединенный файл сегмента, также отсортированный по ключу. А если один и тот же ключ встретится в нескольких входных сегментах? Каждый сегмент содержит все записанные в БД значения за некоторый период времени. Это значит, что все значения одного из входных сегментов должны оказаться более свежими, чем все значения другого (при условии обязательного слияния воедино соседних сегментов). Если несколько сегментов содержат один и тот же ключ, то можно взять значение из наиболее нового сегмента и отбросить значения из более старых.

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

Второе преимущество. Чтобы найти в файле конкретный ключ, не нужно больше хранить индекс всех ключей в оперативной памяти. Например, нам нужен ключ handiwork, но мы не знаем точного смещения этого ключа в файле сегмента. Однако нам известно смещение для ключей handbag и handsome и (благодаря сортировке) то, что handiwork должен находиться между ними. Как следствие, можно перейти по смещению для handbag и просматривать, начиная с этого места, до тех пор, пока не найдем handiwork (впрочем, можем и не найти, если ключ отсутствует в данном файле).

Рис. 5 - SS-таблица с индексом в оперативной памяти

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

Третье преимущество. Поскольку для выполнения запроса на чтение все равно необходимо просмотреть несколько пар «ключ — значение» из заданного диапазона, вполне можно сгруппировать эти записи в блок и сжать его перед записью на диск. Каждая запись разреженного индекса в оперативной памяти затем будет указывать на начало сжатого блока. Помимо экономии пространства на диске, сжатие также снижает использование полосы пропускания ввода/вывода.

Создание и поддержание SS-таблиц

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

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

Теперь организуем работу подсистемы хранения следующим образом.

При поступлении записи добавляем ее в располагающуюся в оперативной памяти сбалансированную структуру данных (например, красно-черное дерево). Это располагающееся в оперативной памяти дерево называется MemTable (от memory table — «таблица, расположенная в памяти»).
Когда размер MemTable превышает определенное пороговое значение — обычно несколько мегабайт, — записываем его на диск в виде файла SS-таблицы. Эта операция выполняется достаточно эффективно, поскольку дерево поддерживает пары «ключ — значение» в отсортированном по ключу виде. Новый файл SS-таблицы становится последним сегментом базы данных. А пока SS-таблица записывается на диск, операции записи продолжают выполняться в новый экземпляр MemTable.
Время от времени запускаем в фоне процесс слияния и уплотнения, чтобы объединить файлы сегментов и отбросить перезаписанные или удаленные значения.

Представленная схема работает отлично. У нее есть только одна проблема: если происходит фатальный сбой БД, то записанные позже всего данные (находящиеся в MemTable, но еще не записанные на диск) теряются. Чтобы избежать этой проблемы, можно держать на диске отдельный журнал, в конец которого немедленно добавляются все записываемые данные. Сам журнал не упорядочен, но это неважно, ведь его единственное назначение — восстановление MemTable после сбоя. Всякий раз, когда MemTable записывается в SS-таблицу, соответствующий журнал можно удалять.

Создание LSM-дерева из SS-таблиц

Подсистемы хранения, основанные на принципе слияния и уплотнения отсортированных файлов, часто называются LSM-подсистемами хранения (Log-Structured Merge).

Основная идея LSM-деревьев — применение каскада SS-таблиц, объединяемых в фоновом режиме, — проста и эффективна. Она хорошо работает даже в случае, когда размер набора данных значительно превышает доступный объем оперативной памяти. То, что данные хранятся в отсортированном виде, дает возможность эффективно выполнять запросы по диапазонам (просмотр всех ключей между установленными минимальным и максимальным значениями), а поскольку записи на диск осуществляются последовательно, LSM-дерево способно поддерживать весьма высокую пропускную способность по записи.

B-деревья

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

Аналогично SS-таблицам B-деревья хранят пары «ключ — значение» в отсортированном по ключу виде, что позволяет эффективно выполнять поиск значения по ключу и запросы по диапазонам. Но на этом сходство заканчивается: конструктивные принципы B-деревьев совершенно другие.

Журналированные индексы, которые рассматривались ранее, разбивают базу данных на сегменты переменного размера и всегда записывают их на диск последовательно. В отличие от них, B-деревья разбивают БД на блоки или страницы фиксированного размера, обычно 4 Кбайт, и читают/записывают по одной странице за раз. Такая конструкция лучше подходит для нижележащего аппаратного обеспечения, поскольку диски тоже разбиваются на блоки фиксированного размера.

Все страницы имеют свой адрес/местоположение, благодаря чему одни страницы могут ссылаться на другие — аналогично указателям, но на диске, а не в памяти. Этими ссылками на страницы можно воспользоваться для создания дерева страниц, как показано на рис. 6.

Рис. 6 - Поиск ключа с помощью индекса на основе B-деревьев

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

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

Представленный алгоритм гарантирует, что дерево останется сбалансированным, то есть глубина B-дерева с n ключами будет равна O(log n). Большинству баз данных хватает деревьев глубиной три или четыре уровня, поэтому не придется проходить по множеству ссылок на страницы с целью найти нужную (четырехуровневое дерево страниц по 4 Кбайт с коэффициентом ветвления в 500 может хранить до 256 Тбайт информации).

Количество ссылок на дочерние страницы на одной странице B-дерева называется коэффициентом ветвления

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

Чтобы сделать БД отказоустойчивой, реализации B-деревьев обычно включают дополнительную структуру данных на диске: журнал упреждающей записи (writeahead log, WAL). Он представляет собой файл, предназначенный только для добавления, в который все модификации B-деревьев должны записываться еще до того, как применяться к самим страницам дерева. Когда база возвращается в норму после сбоя, этот журнал используется для восстановления B-дерева в согласованное состояние.

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

Сравнение B- и LSM-деревьев

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

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

Автор книги затрагивает немного и другие типы индексов, например, составные и нечеткие индексы.

Обработка транзакций или аналитика?

«Транзакция» - это группа операций чтения и записи, составляющей логически единое целое. Транзакция не обязательно должна обладать свойствами ACID (Atomicity, Consistency, Isolation, Durability — атомарность, согласованность, изоляция и сохраняемость). Обработка транзакций означает просто возможность для клиентов выполнять операции чтения и записи с низким значением задержки — в противоположность заданиям пакетной обработки, запускаемым лишь периодически (например, один раз в день).

Приложение обычно ищет с помощью индекса небольшое количество записей по какому-либо ключу. На основе вводимых пользователем данных вставляются или обновляются записи. В силу интерактивности этих приложений такой паттерн доступа получил название «обработка транзакций в реальном времени» (online transaction processing, OLTP).

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

Эти запросы чаще всего написаны бизнес-аналитиками и вставлены в отчеты, которые руководство компании использует для оптимизации коммерческих решений (бизнес-аналитика, business intelligence). Чтобы отличать этот паттерн применения БД от обработки транзакций, его назвали аналитической обработкой данных в реальном времени (online analytical processing, OLAP).

Смысл слова online в OLAP не вполне четко определен; вероятно, речь идет не только о том, что эти запросы используются для встроенных отчетов, но и что аналитики могут задействовать OLAP-системы интерактивно для исследовательских запросов.

Рис. 7 - Сравнительные характеристики обработки транзакций и аналитических систем

Сначала как для обработки транзакций, так и для аналитических запросов использовались одни и те же базы данных. Язык SQL оказался в этом смысле весьма гибок: он работает при OLTP-запросах ничуть не хуже, чем при OLAP-запросах. Тем не менее в конце 1980-х — начале 1990-х годов возникла такая тенденция: компании прекращали задействовать OLTP-системы для целей аналитики и выполняли анализ на отдельных БД, которые назывались складами данных (data warehouse).

Складирование данных

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

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

Склад данных, напротив, представляет собой отдельную БД, которую аналитики могут опрашивать так, как им заблагорассудится, не влияя при этом на OLTP-операции. Склад содержит предназначенную только для чтения копию данных из всех различных OLTP-систем компании. Данные извлекаются из баз OLTP (с помощью выполнения периодических дампов данных или непрерывного потока обновлений данных), преобразуются в удобный для анализа вид, очищаются и затем загружаются в склад. Процесс их помещения в склад известен под названием «извлечение — преобразование — загрузка» (extract — transform — load, ETL).

Рис. 8 – Упрощенная схема ETL в складе данных

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

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

Резюме

В этом конспекте мы попытались разобраться в том, как БД хранят и извлекают данные. Что же происходит при сохранении данных в базе и что делает база, когда позднее запрашиваются эти данные? На высоком уровне абстракции мы видим, что подсистемы хранения делятся на две широкие категории: оптимизированные для обработки транзакций (OLTP) и оптимизированные для аналитики (OLAP). Между паттернами доступа в этих сценариях использования есть большие различия.

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

С точки зрения OLTP мы рассмотрели два различных подхода к подсистемам хранения.

Журналированный подход, при котором допускается только дописывание данных в файлы и удаление устаревших файлов, а не обновление записанного файла. Сюда относятся: Bitcask, SS-таблицы, LSM-деревья и другие.
Подход с обновлением на месте, при котором диск рассматривается как набор страниц заданного размера, допускающих перезапись. Крупнейший представитель этой философии — B-деревья, используемые во всех основных реляционных базах данных, а также и во многих нереляционных.

Ссылки на все части

Подсистемы хранения и извлечение данных. Конспект книги «Designing Data-Intensive Applications»