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

В главе 2 мы обсудили модели данных и языки запросов — т.е. формат, в котором вы (разработчик приложений) передаёте базе данных свои данные, и механизм, с помощью которого вы можете запросить их позже. В этой главе мы обсудим то же самое с точки зрения базы данных: как мы можем хранить данные, которые нам переданы и как мы можем найти их снова, когда нас об этом попросят.

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

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

Однако, начнём мы эту главу с рассказа о механизмах хранения данных, которые используются в базах данных, с которыми вы, вероятно, знакомы: традиционные реляционные базы данных, а также в большинство так называемых NoSQL-баз данных. Мы рассмотрим два семейства механизмов хранения: лог-структурированные (log-structured) и ориентированные на страницы (page-oriented) системы хранения, такие как B-деревья.

Рассмотрим самую простую в мире базу данных, реализованную в виде двух функций Bash:

Эти две функции реализуют хранилище ключ-значение. Вы можете вызвать функцию командой вида db_set key value, которая сохранит ключ и значение в базе данных. Ключ и значение могут быть (почти) всем, что вам нужно — например, значение может быть документом JSON. Затем вы можете вызвать команду db_get key, которая найдёт самое последнее значение, связанное с этим конкретным ключом и вернёт его.

И это работает:

Базовый формат хранения очень прост: текстовый файл, где каждая строка содержит пару ключ-значение, разделенную запятой (примерно как файл CSV, без учета проблем с экранированием). Каждый результат вызова функции db_set добавляется в конец файла, поэтому если вы обновляете ключ несколько раз, старые версии значения не перезаписываются — вам нужно посмотреть на последнее вхождение ключа в файл, чтобы найти последнее значение (отсюда хвост -n 1 в db_get):

Наша функция db_set на самом деле имеет довольно хорошую производительность для такой простой функции, потому что добавлять что-то в файл, как правило, очень эффективно. Подобно тому, что делает db_set, многие базы данных внутри используют журнал, который является файлом данных только для добавления. Реальные базы данных имеют больше проблем (таких как контроль параллелизма, освобождение дискового пространства, чтобы журнал не рос вечно и обработка ошибок и частично записанных записей), но основной принцип тот же. Журналы невероятно полезны, и мы ещё не раз столкнемся с ними в этой книге.

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

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

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

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

Давайте начнем с индексов для данных «ключ-значение». Это не единственный вид данных, которые вы можете индексировать, но они очень распространены и это полезный строительный блок для более сложных индексов.

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

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

Это может показаться упрощением, но это рабочий подход. На самом деле, это, по сути, то, что делает, например, Bitcask (механизм хранения по умолчанию в Riak). Bitcask предлагает высокопроизводительное чтение и запись при условии соблюдения требования, что все ключи помещаются в доступную оперативную память, так как хэш-карта полностью хранится в памяти. Значения могут занимать больше места, чем доступная память, так как они могут быть загружены с диска с помощью одной операции чтения (disk seek). Если эта часть файла данных уже находится в кэше файловой системы, чтение вообще не требует дискового ввода-вывода.

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

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

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

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

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

Формат файла
CSV — не лучший формат для журнала. Быстрее и проще использовать двоичный формат, который сначала кодирует и указывает длину последующей строки значения в байтах, а затем хранит необработанную строку (без необходимости экранирования).

Удаление записей
Если вы хотите удалить ключ и связанное с ним значение, вы должны добавить специальную запись об удалении в файл данных (иногда называемую «надгробием» — tombstone). Когда сегменты журнала объединяются, надгробие указывает процессу объединения отбросить все предыдущие значения для удаленного ключа.

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

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

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

Журнал, который позволяет только добавлять записи,на первый взгляд кажется ресурсозатратным: почему бы вам не обновить файл в нужном месте, перезаписав старое значение новым? Но подход «только добавляем» хорош по нескольким причинам:

Однако индексы хэш-таблицы также имеют ограничения:

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

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

Теперь мы можем внести простые изменения в формат файлов наших сегментов: мы требуем, чтобы последовательность пар ключ-значение сортировалась по ключу. Этот формат называется Sorted String Table или сокращенно SSTable. С помощью этого формата мы не можем немедленно добавить новые пары ключ-значение к сегменту, так как записи могут происходить в любом порядке; в ближайшее время мы рассмотрим, как писать сегменты SSTable с использованием последовательного ввода-вывода.

SSTables имеют несколько больших преимуществ перед сегментами журнала с хэш-индексами:

1. Объединение сегментов просто и эффективно, даже если файлы больше доступной памяти. Подход похож на тот, который используется в алгоритме mergesort (сортировка слиянием), и показан на рисунке 3-4: вы начинаете читать входные файлы одновременно, смотрите на первый ключ в каждом файле, копируете наименьший ключ (в соответствии с порядком сортировки) в выходной файл и повторяете. Это приводит к новому объединенному файлу сегмента, также отсортированному по ключу.

Что делать, если один и тот же ключ появляется в нескольких входных сегментах? Помните, что каждый сегмент содержит все значения, записанные в базу данных в течение некоторого периода времени. Это означает, что все значения в одном входном сегменте должны быть свежее, чем все значения в другом сегменте (при условии, что мы всегда объединяем соседние сегменты). Когда несколько сегментов содержат один и тот же ключ, мы можем сохранить значение из последнего сегмента и отбросить значения в более старых сегментах.

2. Чтобы найти конкретный ключ в файле, вам больше не нужно хранить индекс всех ключей в памяти. См. рисунок 3-5 для примера: предположим, что вы ищете ключ handiwork, но не знаете точное смещение этого ключа в файле сегмента. Тем не менее, вы знаете смещения для ключей handbag и handsome, и благодаря сортировке вы знаете, что handiwork должен находиться между этими двумя ключами. Это означает, что вы можете перейти к смещению для handbag и начать сканировать оттуда, пока не найдёте handiwork (или не найдете , если ключа нет в файле).

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

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

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

Поддерживать отсортированную структуру на диске можно (см. «B-деревья» на стр. 11), но делать это в памяти намного проще. Существует множество известных древовидных структур данных, которые вы можете использовать, таких как красно-черные деревья или АВЛ-деревья. С помощью этих структур данных вы можете вставлять ключи в любом порядке и считывать в отсортированном порядке.

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

Эта схема отлично работает. Её недостаток лишь в одном: в случае сбоя базы данных самые последние записи (которые находятся в записываемом файле, но еще не записаны на диск) теряются. Чтобы избежать этой проблемы, мы можем вести отдельный журнал на диске, к которому сразу добавляется каждая запись, как и в предыдущем разделе. Этот журнал не отсортирован, но это не имеет значения, потому что его единственная цель — восстановить memtable после сбоя. Каждый раз, когда memtable записывается в SSTable, соответствующий ему журнал может быть сброшен.

Алгоритм, описанный здесь, по сути является тем, что используется в LevelDB и RocksDB, библиотеках подсистем хранения типа ключ-значение, которые предназначены для встраивания в другие приложения. Среди прочего, LevelDB можно использовать в Riak в качестве альтернативы Bitcask. Аналогичные системы хранения используются в Cassandra и HBase, которые были вдохновлены работой Google Bigtable (где были введены термины SSTable и memable).

Первоначально эта структура индексации была описана Патриком О'Нилом и др. под названием Log-Structured Merge-Tree (или LSM-Tree), опираясь на более раннюю работу по лог-структурированным файловым системам. Подсистемы хранения, основанные на этом принципе объединения и уплотнения отсортированных файлов, часто называют подсистемами хранения LSM. Lucene, система индексации полнотекстового поиска, используемая Elasticsearch и Solr, использует аналогичный метод хранения своего словаря терминов. Полнотекстовый индекс гораздо сложнее, чем индекс ключевого значения, но основан на аналогичной идее: учитывая слово в поисковом запросе, найти все документы (веб-страницы, описания продуктов и т. д.), в которых упоминается это слово. Это реализовано со структурой ключ-значение, где ключ — это слово (термин), а значение — это список идентификаторов всех документов, содержащих слово (список публикаций). В Lucene это сопоставление термина и списка публикаций хранится в отсортированных файлах, похожих на SSTable, которые объединяются в фоновом режиме по мере необходимости.

Как всегда, много деталей уходит на то, чтобы система хранения хорошо работала на практике. Например, алгоритм LSM-дерева может быть медленным при поиске ключей, которых нет в базе данных: вы должны проверить memtable, а затем сегменты вплоть до самого старого (возможно, придется считывать данные с диска), прежде чем вы сможете быть уверены, что ключ не существует. Для оптимизации такого доступа системы хранения часто используют дополнительные фильтры Блума.

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

Лог-структурированные индексы, которые мы обсуждали до сих пор, набирают популярность, но они не являются наиболее распространенным типом индекса. Наиболее широко используемая структура индексации совершенно иная: B-дерево. Введенные в 1970 году и названные «вездесущими» менее, чем через 10 лет после этого, B-деревья успешно прошли испытание временем. Они остаются стандартной реализацией индексов почти во всех реляционных базах данных, и многие нереляционные базы данных также используют их.

Как и SSTables, B-деревья хранят пары ключ-значение, отсортированные по ключу, что позволяет эффективно искать ключ-значение и выполнять запросы к диапазонам. Но на этом заканчивается сходство: B-деревья имеют совершенно другую философию проектирования.

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

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

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

В примере на рисунке 3-6 мы ищем ключ 251, поэтому мы знаем, что нам нужно перейти по ссылке на страницу между границами 200 и 300. Это приводит нас к аналогичной странице, которая еще больше разбивает диапазон 200-300 на поддиапазоны.

В конечном итоге мы перейдем к странице, содержащей отдельные ключи (страница «лист»), которая либо содержит значение для каждого встроенного ключа, либо содержит ссылки на страницы, где можно найти значения.

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

Если вы хотите обновить значение существующего ключа в B-дереве, выполните поиск страницы-листа, содержащей этот ключ, измените значение в этой странице и запишите страницу обратно на диск (любые ссылки на эту страницу остаются действительными). Если вы хотите добавить новый ключ, вам нужно найти страницу, диапазон которой включает в себя новый ключ, и добавить его на эту страницу. Если на странице недостаточно свободного места для размещения нового ключа, она делится на две полуполные страницы, а родительская страница обновляется с учетом нового представления диапазонов ключей — см. Рисунок 3-7.²

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

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

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

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

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

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

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

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

² Вставка нового ключа в B-дерево достаточно интуитивно понятна, но удаление ключа (при сохранении баланса дерева) несколько сложнее.

³ Этот вариант иногда называют деревом B+, хотя эта оптимизация настолько распространена, что часто не отличается от других вариантов B-дерева.