Индексы на основе B-деревьев для поддержки высокого темпа обновлений
Гоц Грейф (Goetz Graefe)
Перевод – Сергей Кузнецов

Оригинал: B-tree indexes for high update rates
(http://www.sigmod.org/sigmod/record/issues/0603/p39-article-graefe.pdf), SIGMOD Record, Vol. 35, No. 1, Mar. 2006

Предисловие переводчика
Статья Грейфа привлекла меня тем, что уже давно не попадались обзоры, посвященные алгоритмам работы с B-деревьями. Должен сразу сказать, что во многом статья не оправдала мои ожидания: многие, по-видимому, интересные методы и структуры данных описаны слишком кратко и сумбурно, очень не хватает иллюстраций. Во время перевода мне постоянно хотелось исправить недостатки статьи, благо, что большая часть источников, упоминаемых в списке литературы, свободно доступна в Internet. Однако я сдержал себя и представляю вам чистый перевод статьи. В целом он дает представление о существующих подходах, а с подробностями вы можете при желании ознакомиться сами, воспользовавшись списком литературы и поставленными мной ссылками на публикации в Web.
1. Аннотация
В некоторых приложениях сбор данных доминирует над обработкой данных. Например, при мониторинге движущихся объектов часто требуется больше операций вставки и обновления, чем запросов. Это дисбаланс часто демонстрируется при сборе данных с использованием автоматических сенсоров. В более широкой постановке, нерешенной проблемой является индексирование потоков.
Для этих приложений хорошим вариантом являются индексы на основе B-деревьев, если принять некоторые компромиссные решения, направленные на оптимизацию скорее операций обновления, чем запросов. В этой статье приводится обзор некоторых методов, которые за счет снижения эффективности обработки запросов позволяют B-деревьям выдерживать очень высокий темп обновлений, на несколько порядков более высокий, чем могут допустить традиционные B-деревья. Не удивительно, что некоторые из этих методов напоминают методы, используемые при создании, перестройке индексов и т.д., а другие выводятся из известных технологий, таких как дифференциальные файлы и файловые системы с журнальной структурой (log-structured file system).

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

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

3 Оптимизация ввода/вывода
Как и в большинстве операций баз данных, фокусирование на эффективности дисковых операций ввода/вывода является действенным способом повышения производительности и масштабируемости. Однако необходимо разделять совершенствование общей пропускной способности системы и сокращение времени отклика отдельных транзакций, что может быть очень интересно в данном случае, а может быть и совсем не интересно.
Имеется несколько очень общих технологий совершенствования производительности, например, сжатие данных [WKH 00]. В рабочих нагрузках с интенсивным обновлением данных существенное сжатие применяется не только к данным, но и к журналу транзакций. Здесь достаточно заметить, что некоторые методы сжатия являются удивительно простыми, например, отбрасывание лидирующих или хвостовых нулей или пробелов и объединение нескольких журнальных записей от одной транзакции в одну журнальную запись для сокращения накладных расходов, вызываемых наличием в журнале транзакций множественных заголовков записей.

3.1 Предварительная выборка, упреждающее чтение и отложенная запись
Отложенная запись (write-behind) страниц журнала и данных является хорошо известным методом. Сама по себе отложенная запись не повышает пропускную способность системы, поскольку объем записи не сокращается. Однако отложенная запись часто обеспечивает возможность записи данных большого объема, что является еще более эффективным, чем поддержка очередей ввода/вывода. Кроме того, отложенная запись полезна в случае пиков рабочей нагрузки и позволяет производить дополнительную оптимизацию. Например, в современных дисковых устройствах поддерживаются собственные очереди команд, и обмены выполняются лучше, если всегда имеются десятки ждущих операций ввода/вывода [ADR 03].

Упреждающее чтение (read-ahead, обычно используемое при сканировании) не применяется к операциям обновления, но оно применяется для присоединения всей ветви модификаций к существующему B-дереву. При слиянии нескольких разделов B-дерева (обсуждаемом ниже) в один раздел упреждающее чтение с использованием прогнозирования может улучшить производительность, поскольку слияние разделов, по существу, представляет ту же проблему, что и слияние прогонов при выполнении внешней сортировки со слиянием [G 03a]

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

3.2 B-деревья, оптимизированные для записи
В дополнение к асинхронному вводу-выводу, эффективность операций записи может быть улучшена за счет динамического размещения содержимого на диске [G 04]. Этот эффект хорошо известен и интенсивно исследовался для файловых систем с журнальной структурой [OD 89], в частности, в контексте RAID-хранилищ [PGK 88]. Основная идея B-деревьев, оптимизированных для записи, состоит в выделении нового места на диске при каждой записи страницы на диск при выполнении операции записи, т.е. позже принятия решения менеджером буферов о замещении буфера. При этом новое место для страницы выделяется таким образом, что несколько параллельных операций записи нацеливается на одну и ту же область диска.
Чтобы избежать последующего обновления соседних страниц, традиционная цепочка страниц с использованием физических идентификаторов страниц заменяется логической цепочкой страниц с использованием разделительных ключей (separator key), т.е. каждая страница несет в качестве нижнего и верхнего барьеров разделительный ключ, копируемый в страницу родительского узла при отщеплении страницы от ее соседей. В дополнение к поддержке тех же проверок согласованности и других технических операций, что и те, которые поддерживаются традиционными физическими цепочками страниц, барьерные ключи упрощают и улучшают блокировку диапазонов значений ключа, поскольку никогда не требуется перемещаться к соседней листовой странице для нахождения правого значения ключа в диапазоне. После замены физических цепочек страниц логическими барьерными ключами физические идентификаторы страниц остаются только в указателях детей, и только их требуется изменять при перемещении узла на новое место на диске.

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

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

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

4.1 Буферизация в пределах блоков дерева
Некоторые исследователи анализировали структуры данных и алгоритмы, добавляющие большой буфер к каждому внутреннему узлу дерева [A 96, AHV 02, VSW 97]. Часто размер этого буфера превышает размер области, предназначенной для традиционных пар «ключ-указатель», не только потому, что каждая буферизованная новая запись больше пары «ключ-указатель», но также и потому, что число сохраняемых записей может быть больше числа пар «ключ-указатель». Когда буфер полностью заполняется, соответствующие записи выталкиваются в его ребенка с наибольшим числом сохраняемых записей.
Как кажется, записи должны удерживаться только для тех детей, которые не находятся непосредственно в буфере ввода-вывода. На основе того, что в большинстве B-деревьев имеется не менее ста ветвей, что в большинстве серверов баз данных размер памяти превосходит 1% размера диска, и что обсуждаемые здесь B-деревья являются наиболее активно используемыми и критически влияющими на производительность индексами внутри базы данных, можно заключить, что такая буферизация применима только к узлам, являющимся непосредственными предками листьев. Другими словами, могут быть возможны дополнительные усовершенствования опубликованных методов, позволяющие буферизовать узлы всех уровней B-дерева.

4.2 Буферизация в отдельных структурах
Альтернативой буферизации вставок в узлах дерева является создание отдельной структуры данных для буферизации новых вставок [LJB 95, MOP 00, OCG 96]. Эта структура данных может быть еще одним B-деревом или может представлять другую разновидность структуры данных в основной памяти, например, хэш-таблицу. На самом деле, она может являться и набором структур данных, образующих иерархию или каскад областей хранения. Интересно, что эта организация напоминает обе организации, предлагавшиеся сборку мусора по поколениям [U 84].
Использование новых структур предполагает наличие новых механизмов для управления параллельным выполнением операций и восстановления. Таким образом, предпочтительным механизмом была бы уже реализованная индексная структура. В противном случае для новых моделей или протоколов блокировки потребуются доказательства корректности, реализация, тестирование и т.д. Возможно, в наиболее желательной реализации должны избегаться и отдельные структуры, и модификации существующих структур, а вместо этого существующие механизмы должны использоваться другим образом.

4.3 Буферизация в разделах B-дерева
В одной из работ, мотивируемой желанием избежать кодирования частных случаев, используется основное B-дерево как собственная буферная структура данных за счет введения разделов внутри каждого B-дерева [G 03a]. За счет введения искусственного лидирующего столбца ключа сохраняется традиционная структура B-дерева. «Основное» B-дерево определяется общим значением искусственного лидирующего столбца ключа, скажем, 0 или null, а один или более буферов определяются другими значениями этого столбца, скажем, 1, 2 и т.д.
Традиционное управление буферами вместе с ограничениями на размер заново добавленных разделов обеспечивают, что вставки данных пользовательскими транзакциями могут полностью происходить в основной памяти. В предельном случае разделы новых вставок могут состоять из одной записи, т.е. каждая вставка определяет новый раздел и, таким образом, может выполняться практически без поиска или реорганизации страницы внутри B-дерева. Таким образом, максимизируется скорость вставок и пропускная способность пользовательских транзакций за счет потребности больших усилий для оптимизации и реорганизации индекса.

При выполнении запросов требуется производить поиск в каждом разделе с использованием традиционных методов, ограничивающих значения некоторых столбцов индекса, за исключением лидирующего [LJB 95], которые, возможно, дополняются оптимизацией на основе того факта, что в качестве идентификаторов разделов используются последовательные целые значения. В качестве альтернативы, при выполнении запросов могут возникать некоторые слияния, выполняемые до реальной выборки данных и реализуемые с использованием системных транзакций. Таким образом, работа по поддержке B-дерева, традиционно выполняемая как часть операций обновления, перемещается в состав операций запросов или реорганизации, которая может случаться в любое время между вставкой и запросом. В крайнем случае, запрос может привести к полному слиянию и оптимизации всех разделов за исключением, может быть, одного раздела, предназначенного для текущих вставок.

Некоторые интересные аспекты таких B-деревьев состоят в том, что 

операция реорганизации, которая объединяет несколько разделов в один раздел, очень похожа на шаг слияния в традиционной внешней сортировке со слиянием;
такие операции слияния могут выполняться как системные транзакции и фиксировать каждый раз очень небольшой диапазон ключей;
такие операции слияния и реорганизации могут приостанавливаться и возобновляться в любое время, если возникают периоды пиковой нагрузки;
тот же метод может способствовать выполнению массовых удалений, т.е. удаляемые элементы B-дерева перемещаются небольшими системными транзакциями в выделенный раздел, а затем удаляются в одной из быстрых пользовательских транзакций, которая вырезает из B-дерева несколько полных страниц.
4.4 Плавное снижение эффективности
Помимо общего повышения производительности, буферизованные вставки обеспечивают плавное снижение эффективности в случае ошибочных оценок мощности в ходе оптимизации запросов. Сегодня при оптимизации запросов можно выбирать между обработкой операций обновления в режиме «строка-за-строкой» и обработкой в режиме «индекс-за-индексом». При выполнении операции обновления в режиме «строка-за-строкой» обновление всех нужных индексов производится сразу после обновления очередной строки. Обновление в режиме «индекс-за-индексом» означает, что к каждому индексу сразу применяются все обновления, возможно, после расщепления каждой операции модификации на соответствующую пару операций удаления и вставки, сортировки изменений по значениям ключа индекса и рекомбинирования изменений, если это оказывается уместным. Обобщенная версия методов, описанных в [GKK 01], реализуется Microsoft SQL Server, начиная с выпуска 7.0. Обновления в режиме «строка-за-строкой» наиболее уместны для небольших изменений, например, при оперативной обработке транзакций, в обновления в режиме «индекс-за-индексом» являются более эффективными для крупных обновлений, в особенности таких, которые затрагивают не только листовые страницы индексов, например, массовых вставок или удалений. Для обеспечения плавного снижения эффективности план выполнения может предписывать обработку обновления в режиме «строка-за-строкой» при ожидаемом небольшом множестве обновлений, а при реальном выполнении можно обнаружить, что множество обновлений является гораздо более крупным, и переключиться на режим выполнения «индекс-за-индексом».
Описанные выше буферизованные вставки с использованием разделенных B-деревьев представляют собой третий способ применению обновлений к индексу на основе B-дерева, и тем самым обеспечивают еще один вариант плавного снижения эффективности. Обработка в режиме «строка-за-строкой», нацеленная на новый раздел, сулит лучшие модель ввода/вывода и производительность, чем те, которые обеспечиваются при обработке в режиме индекс-за-индексом, хотя при этом сохраняется недостаток неоптимальности индексов. Для обеспечения плавного снижения эффективности план выполнения операции обновления может предусматривать выполнение обновления в режиме «строка-за-строкой» в главном разделе до тех пор, пока не выяснится реальный размер множества обновлений, а затем переключение на буферизованные или разделенные обновления. Хотя можно реализовать плавное снижение эффективности путем смены режима «строка-за-строкой» на режим «индекс-за-индексом» с использованием условного выполнения в традиционном плане выполнения запроса, назначение индексным изменениям нового идентификатора раздела (искусственного лидирующего столбца ключа) является гораздо более простым действием и содействует повышению эффективности обновлений.

5. Дифференциальные файлы и индексы
Хотя методы, обсуждавшиеся в предыдущем разделе, пригодны для буферизации вставок, они не позволяют буферизовать другие операции обновления, т.е. модификации и удаления. Однако, эти методы можно расширить путем адаптации к B-деревьям идей из области дифференциальных файлов [SL 76]. Интересно, что некоторые адаптации B-деревьев для версионного управления параллельным выполнением операций и для исторических индексов являются очень похожими, включая логику, требуемую в течение обработки запросов.
Основной подход состоит в добавлении записей, которые делают недействительными предыдущие записи, без реального изменения этих предыдущих записей. При обновлении новая запись замещает предыдущий элемент B-дерева с тем же ключом. При удалении заново добавляемая запись просто указывает на конец истории данного ключа, или, по крайней мере, на конец истории до тех пор, пока впоследствии не произойдет новая вставка с тем же ключом.

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

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

Конечно, имеется также взаимосвязь между дифференциальными файлами и реализацией версионной изоляции на основе мгновенных снимков (multi-version snapshot isolation). Однако основное различие состоит в том, что в дифференциальных файлах сохраняется самая старая версия плюс набор «дельт» в прямом времени, а реализации версионной изоляции на основе мгновенных снимков обычно ориентированы на обеспечение доступа к наиболее свежим версиям, т.е. в них обычно сохраняется наиболее свежая версия плюс набор «дельт» в обратном времени.

6. Гарантии транзакций
Еще одна возможность улучшения производительности может основываться на ослаблении транзакционных гарантий для некоторых индексов, в частности, для избыточных некластеризованных индексов. Мы рассмотрим три метода: ослабление разделения индивидуальных транзакций за счет пакетирования; ослабление гарантий в случае системных сбоев; запись изменений только в журнал транзакции без попыток их применения к индексу с неявной опасностью того, что попытка применения таких изменений в более позднее время может закончиться неудачей. Очевидно, что эти методы применимы только в тех случаях, когда оставшиеся транзакционные гарантии являются достаточно строгими для имеющихся приложений.
6.1 Операции только над журналом
Если операции поддержки индекса не могут справиться с потоком обновлений, может быть, их удастся хотя бы зарегистрировать в журнале транзакций. В этом случае можно было бы помещать в журнал транзакции логические записи redo и впоследствии их применять, используя, по существу, восстановление redo (восстановление с повторным выполнением операций). Конечно, этот процесс нарушает несколько традиционных предположений о журнализации, например, что операции redo – это всегда физические операции, которые уже совершились, что операции redo не могут заканчиваться неудачно и т.д. Однако в зависимости от приложения такие сбойные ситуации могли бы не являться катастрофой, и их можно было бы игнорировать, например, вполне допустимы ситуации, когда в приложении отслеживания движущихся средств некоторые отдельные отчеты о местоположении не могут быть записаны в исторический индекс. Ясно, что эту идею можно было бы применить, но ее детали требуют проработки, например, что сулит и гарантирует фиксация транзакции, как работают контрольные точки и что они гарантируют и т.д.
6.2 B-деревья без журнализации
В некоторых системах баз данных при создании индексов используются специальные методы, препятствующие появлению содержимого нового индекса в журнале транзакции. Вместо этого журнализуются только изменения каталога и выделение страниц. Сбой в процессе создания индекса приводит к возврату этих страниц и подчистке информации о новом индексе в каталоге. Создание индекса заканчивается сбросом на диск всех заново выделенных и заполненных страниц и последующими операциями резервного копирования базы данных и даже журнала транзакций, удерживающего информацию об этих новых страницах. Последующие пользовательские транзакции журнализуют свои изменения в новом индексе обычным образом.
Эту идею можно расширить следующим образом. Если индекс является действительно избыточным, подобно традиционному кэшу, и если допустимо разрушение индекса в течение восстановления носителя данных или системы, то все операции над этим индексом могут не журнализоваться, т.е. журнализуется только распределение памяти. Это включает и пользовательские транзакции, выполняемые после завершения создания индекса. Откат пользовательской транзакции управляется виртуальными журнальными записями, подсоединенными к описателю транзакции в основной памяти, аналогично виртуальным журнальным записям, которые используются в других методах управления транзакциями [G 04, GK 85]. Детали этого метода в настоящее время не опубликованы, но для некоторых приложений этот метод кажется вполне обещающим, в частности, для временных кэшей и индексов, существующих только в основной памяти.

6.3 Пакетные обновления
Наконец, можно группировать несколько операций обновления и транзакций в одну транзакцию. Однако кажется важным отделять семантику транзакций от структуры данных. Например, как описывалось выше, много небольших пользовательских транзакций могут производить вставки в один буфер, оставляя на последующую системную транзакцию (или последовательность небольших системных транзакций) работу по вливанию этих вставок в основное B-дерево. Другими словами, для достижения делаемого улучшения производительности и масштабируемости может не требоваться или не быть полезным модификация или ослабление границ и семантики пользовательских транзакций.
7. Резюме и заключение
Таким образом, если согласиться с ухудшением производительности при обработке запросов на порядок, например, за счет поиска в нескольких разделах, то производительность операций обновления и вставки можно поднять не менее чем на два порядка, например, путем преобразования операций вставки в операции дополнения и преобразования случайных одиночных записей в крупные последовательные записи в заново выделяемое дисковое пространство. Имеются и менее драматические компромиссы. Хотя в большинстве приложений выполняется больше запросов, чем операций обновления, и это приводит к организации базы данных, ориентированной на оптимизацию запросов, некоторые приложения (например, отслеживание движущихся объектов) больше заняты записью изменений, чем предоставлением ответов на запросы (например, о текущей позиции объекта). Для таких приложений уже имеются многочисленные методы, которые осталось реализовать поставщикам баз данных. Некоторые из этих методов доступны даже для пользователей баз данных, например, введение искусственного лидирующего столбца ключа в видимой схеме базы данных и использование его для создания индекса и, возможно, для его поддержки при выполнении массовых операций [G 03b].
В этом обзоре мы старались перечислить разнообразные возможные методы. Новые методы включают B-деревья, оптимизированные для записи, разделяемые B-деревья, в которых разделы используются для буферизации вставок или всех модификаций в манере дифференциальных файлов, и B-деревья без журнализации. Однако наша интуитивная оценка нуждается в подтверждении с использованием прототипирования или даже производственной реализации.

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