Выполнение транзакций, ориентированное на данные

Иппократис Пандис, Райан Джонсон, Никос Харадавеллас и Анастасия Айламаки
Перевод: Сергей Кузнецов

Назад Содержание Вперёд

4. Ориентированная на данные архитектура для поддержки OLTP

В этом разделе мы представим архитектуру системы OLTP, в которой используется политика назначения потоков управления данным. Мы применяем координированные паттерны доступа к данным этой политики для устранения чреватых конкуренцией взаимодействий с централизованным менеджером блокировок. В то же время, мы поддерживаем свойства ACID и не разделяем данные на физическом уровне. Мы называем эту архитектуру архитектурой, ориентированной на данные (data-oriented architecture), или DORA.

4.1. Обзор архитектуры

Функциональность DORA характеризуется тремя основными аспектами:

1. она связывает рабочие потоки управления с отдельными частями базы данных;
2. она распределяет работу каждой транзакции по потокам управления в соответствии с данными, к которым обращаются транзакции;
3. она по возможности избегает взаимодействий с централизованным менеджером блокировок при обработке запросов блокировок.

В этом разделе подробно описывается каждый из аспектов. В качестве сквозного примера мы используем транзакцию Payment (платеж) из тестового набора TPC-C. Транзакция Payment обновляет остаток на счету клиента (Customer), отражает платеж в статистике продаж округа (District) и склада (Warehouse) и сохраняет данные о платеже в журнале истории (History) [20].

4.1.1. Связывание потоков управления с данными

В DORA рабочие потоки управления связываются с данными путем установки правила маршрутизации (routing rule) для каждой таблицы базы данных. Правило маршрутизации задает отображение наборов записей, или наборов данных (dataset) на рабочие потоки управления, называемые исполнителями (executor). Каждый набор данных приписывается одному исполнителю, и исполнителю может быть приписано несколько наборов данных одной таблицы. Единственное требование к правилу маршрутизации состоит в том, чтобы каждая возможная запись таблицы отображалась в один и только один набор данных. При использовании правил маршрутизации каждая таблица логически разбивается на разъединенные наборы записей. Все данные располагаются в одном и том же буферном пуле, и правила не предполагают какого либо физического разделения или перемещения данных.

Столбцы, используемые в правиле маршрутизации, называются полями маршрутизации (routing field). Поля маршрутизации могут являться любой комбинацией столбцов соответствующей таблицы. Практика показывает, что в качестве полей маршрутизации хорошо работают столбцы первичного или возможного ключа. В примере с транзакцией Payment (платеж) мы предполагаем, что столбец идентификатора склада (Warehouse_id) является полем маршрутизации для каждой из четырех затрагиваемых таблиц. Правила маршрутизации поддерживаются во время выполнения менеджером ресурсов DORA. Для балансировки нагрузки менеджер ресурсов периодически обновляет правила маршрутизации. Менеджер ресурсов изменяет число исполнителей для каждой таблицы в зависимости от размеров таблицы, числа запросов к этой таблице и объема доступных аппаратных ресурсов.

4.1.2. Графы потоков транзакций

Чтобы распределить работу каждой транзакции по соответствующим исполнителям, DORA транслирует каждую транзакцию в граф потока транзакции (transaction flow graph). Граф потока транзакции – это граф, соединяющий действия (action) с наборами данных. Действие – это часть кода транзакции, включающая обращения к одной записи или небольшому набору записей одной таблицы. Идентификатор (identifier) действия идентифицирует набор записей, к которым это действие намеревается обратиться. В зависимости от типа доступа идентификатор может являться некоторым набором значений полей маршрутизации или пустым набором. Два последовательных действия можно слить, если у них имеется один и тот же идентификатор (соответствующий одному и тому же набору).

Чем более точен идентификатор действия, тем проще для DORA направить этой действие соответствующему исполнителю. Другими словами, действия, идентификаторы которых содержат, по крайней мере, значения всех полей маршрутизации, направляются к соответствующему исполнителю путем обращения к правилу маршрутизации. Действия, идентификаторы которых содержат только часть значений полей маршрутизации, могут отображаться на несколько наборов данных. В этом случае действие разбивается на набор более мелких действий, каждое из которых соответствует некоторому одному набору данных. Обычно в эту категорию попадают вторичные индексы. Наконец, для действий с пустыми идентификаторами – вторичных действий (secondary action) – система не может решить, какой исполнитель за них отвечает. В п. 4.2.2 мы обсуждаем, как DORA обрабатывает вторичные действия.

В DORA для действий одной и той же транзакции используются разделяемые объекты (shared object), служащие для управления распределенным выполнением транзакции и передачи данных между действиями на основе зависимостей по данным. Эти разделяемые объекты называются точками рандеву (rendezvous point), или RVP. Если между двумя действиями имеется зависимость по данным, между ними помещается RVP. RVP разделяют выполнение транзакции на фазы (phase). Система не может одновременно выполнять действия одной транзакции, относящиеся к разным фазам. У каждой RVP имеется счетчик, изначально содержащий число действий, которые должны ей "доложиться". Каждый исполнитель, заканчивая выполнение некоторого действия, уменьшает на единицу счетчик соответствующей RVP. Когда значение счетчика RVP становится нулевым, начинается следующая фаза. Следующую фазу инициирует исполнитель, обнуливший счетчик RVP, путем постановки действий этой фазы в очереди к соответствующим исполнителям. Исполнитель, обнуливший счетчик последней RVP в графе потока транзакции, запрашивает фиксацию данной транзакции. С другой стороны, любой исполнитель может аварийно завершить транзакцию и передать ее на восстановление.

Рис. 4. Граф потока транзакции Payment из тестового набора TPC-C.

На рис. 4 показан граф потока транзакции Payment. Каждая транзакция Payment зондирует записи таблиц Warehouse и District, а потом обновляет их. В обоих случаях у обоих действий (выбор и обновление записи) имеется один и тот же идентификатор, и их можно слить. С другой стороны, таблица Customer 60% времени зондируется через вторичный индекс, а затем обновляется. Этот вторичный индекс включает столбцы идентификатора склада (Warehouse_id), идентификатора округа (District_id) и фамилии клиента (Customer_last_name). Если в правиле маршрутизации для таблицы Customer используется только столбец Warehouse_id или столбец District_id, то система знает, какой исполнитель отвечает за этот вторичный индекс. Если же в правиле маршрутизации также используется и столбец идентификатора клиента (Customer_id), входящий в первичный ключ, то доступ к вторичному индексу требуется разбить на более мелкие действия, соответствующие всем возможным значениям Customer_id. Если в правиле маршрутизации используется только Customer_id, то система не может решить, какой исполнитель отвечает за выполнение, и этот доступ к вторичному индексу становится вторичным действием. В нашем примере мы предполагаем, что полем маршрутизации является Warehouse_id. Следовательно, у действий зондирования вторичного индекса и последующего обновления записи имеется один и тот же идентификатор, и их можно слить. Наконец, RVP разделяет транзакцию Payment на две фазы, поскольку имеется зависимость по данным между действием по вставке записи в таблицу History и тремя другими действиями.

В спецификации транзакции Payment требуется, чтобы 15% времени выбирался клиент, приписанный к удалённому складу. В этом случае, системе без совместного использования ресурсов, которая разделяет базу данных по складам, придется выполнять распределенную транзакцию со всеми требуемыми накладными расходами. С другой стороны, DORA изящно справляется с такими транзакциями, просто направляя действия над таблицей Customer другому исполнителю. Так что на производительность этой системы не влияет процентное соотношение "удаленных" транзакций.

4.1.3. Выполнение запросов

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

С каждым исполнителем ассоциируются три структуры данных: очередь поступающих действий, очередь завершенных действий и локальная для потока управления таблица блокировок. Действия обрабатываются в том порядке, в каком они заносятся во входную очередь. Для выявления конфликтных действий исполитель использует локальную таблицу блокировок. Разрешение конфликтов происходит на уровне идентификаторов действий. Другими словами, на вход локальной таблицы блокировок поступают идентификаторы действий. У локальных блокировок имеется всего два режима: совместный (shared) и монопольный (exclusive). Поскольку идентификаторы действий могут содержать только часть первичного ключа, используемая схема блокировок похожа на схему блокировок префиксов ключей (key-prefix locks) [8]. Действие, получившее требуемую блокировку, может продолжать выполнение без централизованного управления параллелизмом. Каждое действие сохраняет полученную им локальную блокировку до фиксации (или аварийного завершения) всей транзакции. В заключительной RVP каждая транзакция сначала ожидает ответа от основного менеджера хранения данных относительно завершения фиксации (или аварийного прекращения транзакции). Затем все действия, участвовавшие в транзакции, ставятся в очереди завершенных действий своих исполнителей. Каждый исполнитель удаляет из своей локальной таблицы блокировок элементы, соответствующие блокировкам этих действий, и последовательно выполняет ранее блокированные действия, которые теперь могут получить требуемые блокировки.

Каждый исполнитель неявно удерживает блокировку монопольного намерения (intent exclusive, IX) для всей таблицы и не вынужден взаимодействовать с централизованным менеджером блокировок для ее получения для каждой транзакции. Транзакции, намеревающиеся модифицировать крупные диапазоны данных, охватывающие несколько наборов данных или покрывающие всю таблицу, (например, уничтожающие таблицу) ставят действие в очередь ко всем исполнителям, обрабатывающим части этой таблицы. Такую "многораздельную" транзакцию можно будет выполнить, как только всем ее действиям будет разрешен доступ. В рабочих нагрузках обработки транзакций такие операции препятствуют параллелизму, и поэтому в масштабируемых приложениях они встречаются редко.

4.2. Проблемы

В этом разделе мы опишем три проблемы архитектуры DORA: выполнение вставок и удалений записей, обработка вторичных действий и предотвращение тупиковых сихронизационных ситуаций. В приложении (подраздел A.2.1) мы также обсуждаем, каким образом в DORA эффективно изменяются размеры наборов данных для балансировки нагрузки.

4.2.1. Вставки и удаления записей

Для поиска и обновления записей в DORA требуется использование только локального механизма блокировок в каждом исполнителе. Однако при параллельном выполнении операций вставки и удаления записей (выполняемых разными исполителями), тем не менее, требуется централизованная координация их доступа к слотам одной и той же страницы.

Другими словами, при удалении записи можно безопасно обойтись без централизованного управления параллелизмом по отношению ко всем операциям чтения этой записи, поскольку все поиски этой записи будут выполняться последовательно исполнителем, ответственным за соответствующий набор данных. Но имеется проблема со вставками записей другими исполнителями. Проблему может вызвать следующее чередование операций транзакции T1, выполняемой исполнителем E1, и транзакции T2, выполняемой исполнителем E2. T1 удаляет запись R1. T2 зондирует страницу, в которой находилась запись R1, и обнаруживает, что соответствующий слот занят. T2 вставляет свою запись. Затем T1 аварийно завершается. Ее откат невозможно выполнить, поскольку нельзя заново использовать слот, который теперь используется транзакцией T2. Это физический конфликт (T1 и T2 не намереваются обращаться к одним и тем же данным), который обычно предотвращается блокировками на уровне записей, и который DORA обязана разрешать.

Чтобы избежать этой проблемы, операции вставки и удаления записей блокируют RID (record identifier – идентификатор записи и соответствующий ему слот) через централизованный менеджер блокировок. Хотя централизованный менеджер блокировок может служить источником конкуренции, обычно блокировки на уровне записи, получение которых требуется для выполнения операций вставки и удаления записей, не конкурируют, и они составляют лишь небольшую часть от общего числа блокировок, которые потребовались бы в традиционной системе. Например, тразакциям Payment требуется получить всего одну блокировку (для вставки записи в таблицу History) вместо 19 блокировок, которые потребовались бы при их выполнении в традиционной системе.

4.2.2. Вторичные действия

Проблема вторичных действий состоит в том, что системе неизвестно, какой исполнитель отвечает за их выполнение. Для преодоления этой трудности в каждом листовом элементе индексов, обращения к данным через которые невозможно отобразить на исполнители, сохраняются не только поля маршрутизации, но и RID. Эти вторичные действия выполняет поток управления, обрабатывающий RVP предыдущей фазы транзакции, используя дополнительную информацию для определения того, какому исполнителю следует произвести доступ к записи в неупорядоченном файле (heap file).

При применении этой схемы незафиксированные вставки и обновления записей должным образом сериализуются исполнителем, но операции удаления вызывают риск нарушения изоляции. Рассмотрим чередование операций транзакций T1 и T2, использующих первичный индекс Idx1 и вторичный индекс Idx2, доступ к которым производится в любом потоке управления. T1 удаляет запись Rec1 через индекс Idx1. T1 удаляет элемент из индекса Idx2. T2 зондирует Idx2 и не находит искомой записи. T1 откатывается, в результате чего Rec снова появляется в Idx2. T2 утрачивает изолированность, поскольку она видит незафиксированные (и, в конце концов, анулированные) результаты операции удаления записи, выполненной T1. Для преодоления этой проблемы мы можем добавлять к элементам индекса Idx2 флаг "удаленный". Когда некоторая транзакция удаляет некоторую запись, она не удаляет соответствующий элемент из индекса; любая транзакция, которая попытается обратиться к соответствующей записи, должна будет выполнить соответствующее действие в исполнителе, владеющем этой записью, и она обнаружит, что запись была удалена (или удаляется).

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

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

4.2.3. Выявление тупиковых ситуаций

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

В DORA предусматриваются меры для понижения вероятности возникновения тупиковых ситуаций. Всякий раз, когда в некотором потоке управления планируется рассылка действий некоторой фазы транзакции, ставятся защелки на очереди поступающих действий всех исполнителей, которым планируется передать действия, так что рассылка действий происходит атомарным образом.³ Это гарантирует, что тупиковая ситуация никогда не возникнет между транзакциями с одинаковыми графами потока транзакции. Действительно, между двумя транзакциями с одним и тем же графом потока транзакции мог бы возникнуть тупик, только если бы их конфликтующие запросы обрабатывались в противоположном порядке. Но это невозможно, поскольку рассылка действий выполяется атомарным образом, исполнители обслуживают действия в порядке FIFO (first in – first out, первым обсуживается первое поступившее действие), и локальные блокировки удерживаются до фиксации тразакции. Транзакция, первой поставившая свои действия в очередь, первой и закончится.

4.3. Реализация прототипа

Чтобы получить возможность оценить архитектуру DORA, мы реализовали на основе менеджера хранения данных Shore-MT [14] прототип сервера OLTP DORA. Shore-MT – это модифицированный вариант менеджера хранения данных SHORE [3] с многопотоковым ядром. В SHORE поддерживаются все основные возможности современных серверов баз данных: полная изоляция транзакций, иерархические блокировки, буферный пул с алгоритмом замещения CLOCK и набором подсказок по поводу замещения и упреждающего чтения, индексы на основе B-деревьев и журнализация и восстановление в стиле ARIES [18]. Мы используем Shore-MT, потому что показано, что эта система масштабируется лучше любого другого менеджера хранения данных с открытыми исходными текстами [14].

В нашем прототипе отсутствует какой-либо оптимизатор, преобразующий обычный код транзакций в графы потоков транзакций, и в Shore-MT отсутствует какой-либо интерфейс уровня пользователей. Поэтому все транзакции являются частично встроенными. Представление метаданных базы данных и серверная обработка не зависят от конкретной схемы базы данных, но в коде транзакций такая зависимость имеется. Это соглашение аналогично подходу статически компилируемых хранимых процедур, поддерживаемому в коммерческих серверах, когда аннотированный код на языке Си преобразуется в откопилированный объект, привязанный к конкретной базе данных и вызываемый напрямую. Например, для достижения максимально возможной производительности в среде DB2 разработчикам позволяется создавать разделяемые библиотеки "внешних подпрограмм" ("external routine"), которые динамически загружаются с помощью вызова dlopen и напрямую вызываются внутри ядра сервера.⁴

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

---

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

⁴ http://publib.boulder.ibm.com/infocenter/db2luw/v9r5/index.jsp

Назад Содержание Вперёд