Мартин клеппман
Проектирование высоконагруженных приложений

(Designing Data-Intensive Applications)

Глава 3. Хранение и извлечение данных
Wer Ordnung hält, ist nur zu faul zum Suchen.
(У кого всегда порядок, тот просто ленив, чтобы искать)
Немецкая пословица
На самом фундаментальном уровне база данных должна делать две вещи: когда вы даёте ей некоторые данные, она должна их сохранить, а когда вы запрашиваете их позже, она должна вам их вернуть.
В главе 2 мы обсудили модели данных и языки запросов — т.е. формат, в котором вы (разработчик приложений) передаёте базе данных свои данные, и механизм, с помощью которого вы можете запросить их позже. В этой главе мы обсудим то же самое с точки зрения базы данных: как мы можем хранить данные, которые нам переданы и как мы можем найти их снова, когда нас об этом попросят.
Почему вам, как разработчику приложений, должно быть дело до того, как база данных справляется с хранением и извлечением внутри себя? Вы, вероятно, не собираетесь реализовывать свою собственную подсистему хранения с нуля, но вам нужно выбрать подсистему хранения, подходящую для вашего приложения, из множества доступных. Чтобы настроить подсистему хранения для хорошей работы с вашей рабочей нагрузкой, вам нужно иметь приблизительное представление о том, как работает подсистема хранения под капотом.
В частности, существует большая разница между механизмами хранения, оптимизированными для транзакционных рабочих нагрузок, и теми, которые оптимизированы для аналитики.
Мы рассмотрим это различие позже в секции «Обработка транзакций или аналитика?», а в секции «Хранилище, ориентированное на столбцы» мы обсудим семейство механизмов хранения, оптимизированных для аналитики.
Однако, начнём мы эту главу с рассказа о механизмах хранения данных, которые используются в базах данных, с которыми вы, вероятно, знакомы: традиционные реляционные базы данных, а также в большинство так называемых NoSQL-баз данных. Мы рассмотрим два семейства механизмов хранения: лог-структурированные (log-structured) и ориентированные на страницы (page-oriented) системы хранения, такие как B-деревья.
Структуры данных, которые
наполняют вашу базу данных
Рассмотрим самую простую в мире базу данных, реализованную в виде двух функций Bash:
#!/bin/bash
 
db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
Эти две функции реализуют хранилище ключ-значение. Вы можете вызвать функцию командой вида db_set key value, которая сохранит ключ и значение в базе данных. Ключ и значение могут быть (почти) всем, что вам нужно — например, значение может быть документом JSON. Затем вы можете вызвать команду db_get key, которая найдёт самое последнее значение, связанное с этим конкретным ключом и вернёт его.
И это работает:
$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}' 

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
Базовый формат хранения очень прост: текстовый файл, где каждая строка содержит пару ключ-значение, разделенную запятой (примерно как файл CSV, без учета проблем с экранированием). Каждый результат вызова функции db_set добавляется в конец файла, поэтому если вы обновляете ключ несколько раз, старые версии значения не перезаписываются — вам нужно посмотреть на последнее вхождение ключа в файл, чтобы найти последнее значение (отсюда хвост -n 1 в db_get):
$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
 
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]} 
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]} 
42,{"name":"San Francisco","attractions":["Exploratorium"]}
Наша функция db_set на самом деле имеет довольно хорошую производительность для такой простой функции, потому что добавлять что-то в файл, как правило, очень эффективно. Подобно тому, что делает db_set, многие базы данных внутри используют журнал, который является файлом данных только для добавления. Реальные базы данных имеют больше проблем (таких как контроль параллелизма, освобождение дискового пространства, чтобы журнал не рос вечно и обработка ошибок и частично записанных записей), но основной принцип тот же. Журналы невероятно полезны, и мы ещё не раз столкнемся с ними в этой книге.
Слово журнал (log) часто используется для обозначения журналов приложений, в которых приложение выводит текст, описывающий происходящее. В этой книге слово журнал используется в более общем смысле: последовательность записей, в которую можно только добавлять новые. Она не обязательно должна быть читаемой человеком; она может быть представлена в двоичном формате и предназначена только для чтения другими программами.
С другой стороны, наша функция db_get имеет ужасную производительность, если у вас большое количество записей в базе данных. Каждый раз, когда вы хотите найти ключ, db_get должен сканировать весь файл базы данных от начала до конца, в поисках вхождения ключа. С алгоритмической точки зрения стоимость поиска составляет O(n): если вы удвоите количество записей n в своей базе данных, поиск займет в два раза больше времени. Это плохо.
Чтобы эффективно найти значение конкретного ключа в базе данных, нам нужна другая структура данных — индекс. В этой главе мы рассмотрим ряд структур индексации и посмотрим, чем они отличаются друг от друга. Общая идея заключается в том, чтобы сохранить некоторые дополнительные метаданные, которые действуют как указатель и помогают вам найти нужные данные. Если вы хотите искать одни и те же данные несколькими разными способами, вам может понадобиться несколько разных индексов для разных частей данных.
Индекс — это дополнительная структура, полученная из первичных данных. Многие базы данных позволяют добавлять и удалять индексы, и это не влияет на содержимое базы данных, это влияет только на производительность запросов. Поддержание дополнительных структур влечёт за собой накладные расходы, особенно при записи. При записи трудно превзойти производительность простого добавления в файл, потому что это самая простая возможная операция записи. Любой индекс обычно замедляет запись, поскольку индекс также необходимо обновлять каждый раз при записи данных.
Это важный компромисс в системах хранения: хорошо подобранные индексы ускоряют запросы на чтение, но каждый индекс замедляет запись. По этой причине базы данных обычно не индексируют всё по умолчанию, но требуют, чтобы вы — разработчик приложений или администратор баз данных — выбирали индексы вручную, используя свои знания о типичных шаблонах запросов приложения. Затем вы можете выбрать индексы, которые дают вашему приложению наибольшие преимущества, не вводя больше накладных расходов, чем необходимо.
Хэш-индексы
Давайте начнем с индексов для данных «ключ-значение». Это не единственный вид данных, которые вы можете индексировать, но они очень распространены и это полезный строительный блок для более сложных индексов.
Хранилища ключей-значений очень похожи на тип «словарь» (dictionary), который можно найти в большинстве языков программирования и который обычно реализуется в виде хэш-карты (хэш-таблицы). Хэш-карты описаны во многих учебниках по алгоритмам, поэтому мы не будем здесь вдаваться в подробности о том, как они работают. Поскольку у нас уже есть хэш-карты для наших структур данных в памяти, почему бы не использовать их для индексации наших данных на диске?
Предположим, что наше хранилище данных состоит только из добавления в файл, как в предыдущем примере. Тогда самая простая возможная стратегия индексирования заключается в следующем: сохраните в памяти хэш-карту, в которой каждый ключ сопоставляется со смещением в файле данных — местом, в котором можно найти значение, как показано на рисунке 3-1. Каждый раз, когда вы добавляете новую пару ключ-значение в файл, вы также обновляете хэш-карту, чтобы отразить смещение только что записанных данных (это работает как для вставки новых ключей, так и для обновления существующих ключей). Если вы хотите найти значение, используйте хэш-карту, чтобы узнать смещение в файле данных, найдите это место в файле и считайте значение.
Рисунок 3-1. Хранение журнала пар ключ-значение в формате CSV, индексированном хэш-картой в памяти
Это может показаться упрощением, но это рабочий подход. На самом деле, это, по сути, то, что делает, например, Bitcask (механизм хранения по умолчанию в Riak). Bitcask предлагает высокопроизводительное чтение и запись при условии соблюдения требования, что все ключи помещаются в доступную оперативную память, так как хэш-карта полностью хранится в памяти. Значения могут занимать больше места, чем доступная память, так как они могут быть загружены с диска с помощью одной операции чтения (disk seek). Если эта часть файла данных уже находится в кэше файловой системы, чтение вообще не требует дискового ввода-вывода.
Такой механизм хранения, как Bitcask, хорошо подходит для ситуаций, когда значение каждого ключа часто обновляется. Например, ключом может быть URL-адрес видео с кошкой, а значением — количество раз, когда оно воспроизводилось (увеличивается каждый раз, когда кто-то нажимает кнопку воспроизведения). В такой рабочей нагрузке много записей, но не слишком много различных ключей — у вас большое количество записей на ключ, но вполне можно хранить все ключи в памяти.
Как было сказано ранее, мы только добавляем данные в файл, так как нам избежать нехватки места на диске? Хорошим решением будет разбить журнал на сегменты определённого размера, закрывая файл сегмента каждый раз, когда он достигает определённого размера, и добавлять последующие записи в файл нового сегмента. Затем мы можем выполнить сжатие, уплотнение (compaction) на этих сегментах, как показано на рисунке 3-2. Сжатие означает исключение дубликатов ключей из журнала и сохранение только последнего обновления для каждого ключа.
Рисунок 3-2. Сжатие журнала обновления ключ-значение (подсчёт количества раз, когда воспроизводилось каждое видео с кошкой), с сохранением только самого последнего значения для каждого ключа
Кроме того, поскольку сжатие часто делает сегменты намного меньше (при условии, что ключ перезаписывается в среднем несколько раз в пределах одного сегмента), мы также можем объединить несколько сегментов одновременно с выполнением уплотнения, как показано на рисунке 3-3. Сегменты никогда не изменяются после записи, поэтому объединенный сегмент записывается в новый файл. Слияние и сжатие сегментов может быть выполнено в фоновом потоке, и пока это происходит, мы всё ещё можем продолжать обслуживать запросы на чтение с использованием старых файлов сегментов и записывать запросы в последний файл сегментов. После завершения процесса объединения мы переключаем запросы на чтение на использование нового объединённого сегмента вместо старых сегментов, а затем старые файлы сегментов могут быть просто удалены.
Рисунок 3-3. Выполнение уплотнения и слияния сегментов одновременно
Каждый сегмент теперь имеет свою собственную хэш-таблицу в памяти, сопоставляющую ключи со смещениями файлов. Чтобы найти значение ключа, мы сначала проверяем хэш-карту последнего сегмента. Если ключ отсутствует, мы проверяем второй самый последний сегмент и так далее. Процесс слияния сохраняет количество сегментов небольшим, поэтому при поиске не нужно проверять большое количество хэш-карт.
Чтобы эта простая идея работала на практике, приходится попотеть. Вкратце, вот некоторые из вопросов, которые будут важны в реальной реализации:
Формат файла
CSV — не лучший формат для журнала. Быстрее и проще использовать двоичный формат, который сначала кодирует и указывает длину последующей строки значения в байтах, а затем хранит необработанную строку (без необходимости экранирования).
Удаление записей
Если вы хотите удалить ключ и связанное с ним значение, вы должны добавить специальную запись об удалении в файл данных (иногда называемую «надгробием» — tombstone). Когда сегменты журнала объединяются, надгробие указывает процессу объединения отбросить все предыдущие значения для удаленного ключа.
Аварийное восстановление
При перезапуске базы данных хэш-карты в памяти теряются. В принципе, вы можете восстановить хэш-карту каждого сегмента, прочитав весь файл сегмента от начала до конца и отметив смещение последнего значения для каждого ключа по мере продвижения вперед. Однако это может занять много времени, если файлы сегментов большие, что сделает перезапуск сервера болезненным. Bitcask ускоряет восстановление за счёт хранения снимка хэш-карты каждого сегмента на диске, который можно быстрее загрузить в память.
Частично сделанные записи
База данных может выйти из строя в любое время, в том числе на полпути в ходе добавления записи в журнал. Файлы Bitcask содержат контрольные суммы, позволяющие обнаруживать и игнорировать такие повреждённые части журнала.
Управление параллелизмом
Поскольку записи добавляются в журнал в строго последовательном порядке, общий подход к реализации заключается в том, чтобы иметь только один поток записи. Сегменты файлов данных доступны только для добавления и в остальном неизменны, поэтому они могут быть прочитаны одновременно несколькими потоками.
Журнал, который позволяет только добавлять записи,на первый взгляд кажется ресурсозатратным: почему бы вам не обновить файл в нужном месте, перезаписав старое значение новым? Но подход «только добавляем» хорош по нескольким причинам:
  • Добавление и слияние сегментов — это операции последовательной записи, которые в целом намного быстрее, чем произвольная (random) запись, особенно для жёстких дисков с магнитным вращающимся диском (HDD). В некоторой степени последовательная запись также предпочтительнее для флеш-накопителя на основе флэш-памяти (SSD). Мы обсудим этот вопрос далее в разделе «Сравнение B-деревьев и LSM-деревьев» .
  • Параллельный доступ и аварийное восстановление намного проще, если файлы сегментов только расширяются или неизменны. Например, вам не нужно беспокоиться в случае, когда во время перезаписи значения произошел сбой, в результате чего в файле осталась часть старого и часть нового значения, соединенные вместе.
  • Объединение старых сегментов позволяет избежать проблемы фрагментации файлов данных с течением времени.
Однако индексы хэш-таблицы также имеют ограничения:
  • Хэш-таблица должна вписываться в память, поэтому, если у вас очень большое количество ключей, вам не повезло. В принципе, вы можете хранить хэш-карту на диске, но, к сожалению, трудно добиться хорошей работы хэш-карты на диске. Она требует много операций ввода-вывода с произвольным доступом, её дорого увеличивать, когда она становится полной и хэш-коллизии требуют сложной логики.
  • Интервальные запросы (range queries) неэффективны. Например, вы не можете легко просмотреть все ключи между kitty00000 и kitty99999 — вам придётся искать ключ каждого по отдельности на хэш-картах.
В следующем разделе мы рассмотрим структуру индексирования, которая не имеет таких ограничений.
SST-таблицы и LSM-деревья
На рисунке 3-3 каждый сегмент структурированного хранения журнала представляет собой последовательность пар ключ-значение. Эти пары появляются в том порядке, в котором они были записаны, и значения, записанные в журнале позднее, имеют приоритет над значениями того же ключа, записанного в журнале ранее. Кроме того, порядок пар ключ-значение в файле не имеет значения.
Теперь мы можем внести простые изменения в формат файлов наших сегментов: мы требуем, чтобы последовательность пар ключ-значение сортировалась по ключу. Этот формат называется Sorted String Table или сокращенно SSTable. С помощью этого формата мы не можем немедленно добавить новые пары ключ-значение к сегменту, так как записи могут происходить в любом порядке; в ближайшее время мы рассмотрим, как писать сегменты SSTable с использованием последовательного ввода-вывода.
SSTables имеют несколько больших преимуществ перед сегментами журнала с хэш-индексами:
1. Объединение сегментов просто и эффективно, даже если файлы больше доступной памяти. Подход похож на тот, который используется в алгоритме mergesort (сортировка слиянием), и показан на рисунке 3-4: вы начинаете читать входные файлы одновременно, смотрите на первый ключ в каждом файле, копируете наименьший ключ (в соответствии с порядком сортировки) в выходной файл и повторяете. Это приводит к новому объединенному файлу сегмента, также отсортированному по ключу.
Рисунок 3-4. Объединение нескольких сегментов SSTable, с сохранением только самого последнего значения для каждого ключа
Что делать, если один и тот же ключ появляется в нескольких входных сегментах? Помните, что каждый сегмент содержит все значения, записанные в базу данных в течение некоторого периода времени. Это означает, что все значения в одном входном сегменте должны быть свежее, чем все значения в другом сегменте (при условии, что мы всегда объединяем соседние сегменты). Когда несколько сегментов содержат один и тот же ключ, мы можем сохранить значение из последнего сегмента и отбросить значения в более старых сегментах.
2. Чтобы найти конкретный ключ в файле, вам больше не нужно хранить индекс всех ключей в памяти. См. рисунок 3-5 для примера: предположим, что вы ищете ключ handiwork, но не знаете точное смещение этого ключа в файле сегмента. Тем не менее, вы знаете смещения для ключей handbag и handsome, и благодаря сортировке вы знаете, что handiwork должен находиться между этими двумя ключами. Это означает, что вы можете перейти к смещению для handbag и начать сканировать оттуда, пока не найдёте handiwork (или не найдете , если ключа нет в файле).
Рисунок 3-5. SSTable с резидентным индексом
Вам всё ещё нужен резидентный индекс, чтобы сообщить вам смещения для некоторых ключей, но он может быть разреженным: одного ключа на каждые несколько килобайт файла сегмента достаточно, потому что несколько килобайт можно отсканировать очень быстро.1
3. Поскольку запросы на чтение в любом случае должны сканировать несколько пар ключ-значение в запрашиваемом диапазоне, можно сгруппировать эти записи в блок и сжать их перед записью на диск (обозначается заштрихованной областью на рисунке 3-5). Тогда каждый разреженный резидентный индекс указывает на начало сжатого блока. Помимо экономии дискового пространства, сжатие также снижает использование полосы пропускания ввода-вывода.
Построение и обслуживание SSTables
Пока всё идет хорошо, но как сделать так, чтобы ваши данные были отсортированы по ключу? Наши входные записи могут добавляться в любом порядке.
Поддерживать отсортированную структуру на диске можно (см. «B-деревья» на стр. 11), но делать это в памяти намного проще. Существует множество известных древовидных структур данных, которые вы можете использовать, таких как красно-черные деревья или АВЛ-деревья. С помощью этих структур данных вы можете вставлять ключи в любом порядке и считывать в отсортированном порядке.
Теперь мы можем заставить наш механизм хранения работать следующим образом:
  • Когда появляется запись, добавьте её в структуру данных сбалансированного резидентного дерева (например, красно-чёрное дерево). Это резидентное дерево иногда называют memtable.
  • Когда размер memtable превышает какой-то порог — обычно на несколько мегабайт — запишите его на диск как файл SSTable. Это эффективно, потому что дерево уже содержит пары ключ-значение, отсортированные по ключам. Новый файл SSTable становится самым последним сегментом базы данных. Пока SSTable записывается на диск, запись может продолжаться в новый экземпляр memtable.
  • Чтобы выполнить запрос на чтение, сначала попробуйте найти ключ в memtable, затем в последнем записанном на диск сегменте, затем в предыдущем записанном сегменте и т. д.
  • Время от времени запускайте процесс слияния и сжатия в фоновом режиме, чтобы объединить файлы сегментов и отбросить перезаписанные или удалённые значения.
Эта схема отлично работает. Её недостаток лишь в одном: в случае сбоя базы данных самые последние записи (которые находятся в записываемом файле, но еще не записаны на диск) теряются. Чтобы избежать этой проблемы, мы можем вести отдельный журнал на диске, к которому сразу добавляется каждая запись, как и в предыдущем разделе. Этот журнал не отсортирован, но это не имеет значения, потому что его единственная цель — восстановить memtable после сбоя. Каждый раз, когда memtable записывается в SSTable, соответствующий ему журнал может быть сброшен.
Создание LSM-дерева из SSTables
Алгоритм, описанный здесь, по сути является тем, что используется в 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-деревья
Лог-структурированные индексы, которые мы обсуждали до сих пор, набирают популярность, но они не являются наиболее распространенным типом индекса. Наиболее широко используемая структура индексации совершенно иная: B-дерево. Введенные в 1970 году и названные «вездесущими» менее, чем через 10 лет после этого, B-деревья успешно прошли испытание временем. Они остаются стандартной реализацией индексов почти во всех реляционных базах данных, и многие нереляционные базы данных также используют их.
Как и SSTables, B-деревья хранят пары ключ-значение, отсортированные по ключу, что позволяет эффективно искать ключ-значение и выполнять запросы к диапазонам. Но на этом заканчивается сходство: B-деревья имеют совершенно другую философию проектирования.
Лог-структурированные индексы, которые мы видели ранее, разбивают базу данных на сегменты переменного размера, обычно размером в несколько мегабайт или более и всегда производят запись последовательно. B-деревья, напротив, разбивают базу данных на блоки или страницы фиксированного размера, традиционно размером 4 КБ (иногда больше) и считывают или записывают по одной странице за раз. Эта конструкция более точно соответствует базовому оборудованию, так как диски также расположены в блоках фиксированного размера.
Каждая страница может быть идентифицирована по адресу или местоположению, что позволяет одной странице ссылаться на другую — аналогично указателю, но на диске, а не в памяти. Мы можем использовать эти ссылки на страницы для создания дерева страниц, как показано на рисунке 3-6.
Рисунок 3-6. Поиск ключа с использованием индекса B-дерева
Одна страница обозначается как корень B-дерева; всякий раз, когда вы хотите найти ключ в индексе, вы начинаете с этой страницы. Страница содержит несколько ключей и ссылок на дочерние страницы. Каждый дочерний элемент несет ответственность за непрерывный диапазон ключей, а ключи между ссылками указывают, где находятся границы между этими диапазонами.
В примере на рисунке 3-6 мы ищем ключ 251, поэтому мы знаем, что нам нужно перейти по ссылке на страницу между границами 200 и 300. Это приводит нас к аналогичной странице, которая еще больше разбивает диапазон 200-300 на поддиапазоны.
В конечном итоге мы перейдем к странице, содержащей отдельные ключи (страница «лист»), которая либо содержит значение для каждого встроенного ключа, либо содержит ссылки на страницы, где можно найти значения.
Количество ссылок на дочерние страницы в одной странице B-дерева называется коэффициентом ветвления. Например, на рисунке 3-6 коэффициент ветвления составляет шесть. На практике коэффициент ветвления зависит от объема пространства, необходимого для хранения ссылок на страницу, и границ диапазона, но обычно он составляет несколько сотен.
Если вы хотите обновить значение существующего ключа в B-дереве, выполните поиск страницы-листа, содержащей этот ключ, измените значение в этой странице и запишите страницу обратно на диск (любые ссылки на эту страницу остаются действительными). Если вы хотите добавить новый ключ, вам нужно найти страницу, диапазон которой включает в себя новый ключ, и добавить его на эту страницу. Если на странице недостаточно свободного места для размещения нового ключа, она делится на две полуполные страницы, а родительская страница обновляется с учетом нового представления диапазонов ключей — см. Рисунок 3-7.2
Рисунок 3-7. Выращивание B-дерева путем разделения страницы
Этот алгоритм гарантирует, что дерево остается сбалансированным: B-дерево с n ключами всегда имеет глубину O(log n). Большинство баз данных могут поместиться в B-дерево глубиной на три-четыре уровня, поэтому вам не нужно переходить по многим ссылкам на страницы, чтобы найти страницу, которую вы ищете. (Четырехуровневое дерево страниц размером 4 КБ с коэффициентом ветвления 500 может хранить до 250 ТБ).
Делаем B-деревья надёжными
Основная базовая операция записи в B-дерево заключается в перезаписывании на диск страницы с новыми данными. Предполагается, что перезапись не меняет местоположение страницы, т.е. все ссылки на эту страницу остаются нетронутыми, когда страница перезаписывается. Это резко контрастирует с лог-структурированными индексами, такими как LSM-деревья, которые только дополняют файлы (и в конечном итоге удаляют устаревшие файлы), но никогда не изменяют файлы на месте.
Мы можем рассматривать перезапись страницы на диске как реальную аппаратную операцию. На магнитном жестком диске это означает перемещение головки диска в нужное место, ожидание правильного положения на вращающейся пластине, а затем перезапись соответствующего сектора новыми данными. На твердотельных накопителях всё происходит несколько сложнее из-за того, что SSD должен стирать и переписывать довольно большие блоки микросхемы памяти за раз.
Кроме того, некоторые операции требуют перезаписи нескольких разных страниц. Например, если вы разделили страницу из-за того, что вставка привела к её переполнению, вам нужно записать две разделённые страницы, а также перезаписать их родительскую страницу, чтобы обновить ссылки на две дочерние страницы. Это опасная операция, потому что если база данных вылетает после того, как были перезаписаны только некоторые страницы, вы в конечном итоге получаете поврежденный индекс (например, может появиться потерянная страница, на которую нет ссылок ни на одной другой странице).
Чтобы сделать базу данных устойчивой к сбою, обычно необходимо, чтобы реализации B-дерева включали дополнительную структуру данных на диске: журнал предзаписи (WAL, также известный как redo log). Это файл только для записи, в который необходимо записать каждую модификацию B-дерева, прежде чем ее можно будет применить к страницам самого дерева. Когда база данных приходит в норму после сбоя, этот журнал используется для восстановления B-дерева до согласованного состояния.
Дополнительная сложность в обновлении страниц заключается в том, что требуется тщательный контроль параллелизма, если несколько потоков будут получать доступ к B-дереву одновременно — в противном случае поток может видеть дерево в несогласованном состоянии. Обычно это делается путем защиты структур данных дерева с помощью защелок (облегченных блокировок). Лог-структурированные подходы проще в этом отношении, потому что они выполняют все слияния в фоновом режиме, не мешая входящим запросам, и время от времени атомарно меняют старые сегменты на новые сегменты.
Оптимизация B-дерева
Поскольку B-деревья существуют так долго, неудивительно, что за эти годы было разработано много способов оптимизации. Упомяну лишь некоторые из них:
  • Вместо перезаписи страниц и поддержания WAL для аварийного восстановления некоторые базы данных (например, LMDB) используют схему копирования при записи. Измененная страница записывается в другое место, и новая версия родительских страниц в дереве создается со ссылкой на новое местоположение. Этот подход также полезен для контроля параллелизма, как мы увидим в главе 7.
  • Мы можем сэкономить место на страницах, не сохраняя весь ключ, а сокращая его. Особенно на страницах внутри дерева, где ключи нужны только для того, чтобы предоставить достаточно информации, чтобы выступать в качестве границ между диапазонами ключей. Упаковка большего количества ключей на страницу позволяет дереву иметь более высокий коэффициент ветвления и, следовательно, меньше уровней.3
  • Как правило, страницы могут быть размещены в любом месте на диске; не существует требований, при которых страницы с близлежащими диапазонами ключей должны находиться рядом на диске. Если запросу нужно сканировать большую часть диапазона ключей в отсортированном порядке, этот вид расположения может быть неэффективным, потому что для каждой прочитанной страницы может потребоваться обращение к диску. Поэтому многие реализации B-деревьев пытаются расположить дерево так, чтобы страницы листа отображались на диске в последовательном порядке. Тем не менее, трудно поддерживать этот порядок по мере роста дерева. Напротив, поскольку LSM-деревья переписывают большие сегменты хранилища за один раз во время объединения, им легче держать последовательные ключи близко друг к другу на диске.
  • Добавление в дерево дополнительных указателей. Например, каждая страница листа может иметь ссылки на соседние равнозначные страницы слева и справа, что позволяет сканировать ключи по порядку, не возвращаясь к родительским страницам.
  • Фрактальные деревья, являющиеся разновидностью B-деревьев, заимствуют некоторые идеи лог-структур, чтобы уменьшить поиск по диску (и они не имеют ничего общего с фракталами).
1 Если бы все ключи и значения имели фиксированный размер, вы могли бы использовать двоичный поиск в файле сегмента и полностью избегать использования индекса в памяти. Однако на практике они обычно имеют переменную длину, что затрудняет определение того, где заканчивается одна запись, а следующая начинается, если у вас нет индекса.
2 Вставка нового ключа в B-дерево достаточно интуитивно понятна, но удаление ключа (при сохранении баланса дерева) несколько сложнее.
3 Этот вариант иногда называют деревом B+, хотя эта оптимизация настолько распространена, что часто не отличается от других вариантов B-дерева.
Часть 2. Глава 3. Хранение и извлечение данных