A.1. Детальный пример выполнения транзакции

В этом разделе подробно описывается выполнение в среде DORA транзакции Payment из тестового набора TPC-C. Напомним, что транзакция Payment обновляет остаток на счету клиента (Customer), отражает факт совершения платежа в статистике округа (District) и склада (Warehouse) и фиксирует этот факт в журнале истории (History). Граф потока транзакции для транзакции Payment показан на рис. 4.

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

На рис. 9 показан поток выполнения в среде DORA транзакции Payment. Все круги раскрашены, чтобы показать потоки управления, выполняющий соответствующие шаги. При выполнении этой транзакции имеется всего 12 шагов.

Рис. 9. Пример выполнения транзакции Payment из тестового набора TPC-C в среде DORA.

Шаг1:	Выполнение транзакции начинается с потока управления, получающего запрос (например, из сети). Этот поток управления, называемый также диспетчером (dispatcher), ставит в очереди к соответствующим исполнителям действия первой фазы транзакции.
Шаг 2:	Когда действие достигает начала входной очереди, оно выбирается соответствующим исполнителем.
Шаг 3:	Каждый исполнитель производит поиск в своей локальной таблице блокировок, чтобы определить, может ли он обработать действие, обслуживаемое в данное время. Если имеется конфликт, то действие добавляется к списку заблокированных действий. Его выполнение возобновится, когда завершится транзакция, действие которой заблокировало данное действие. В противном случае исполнитель выполняет действие в основном без использования общесистемного управления параллелизмом.
Шаг 4:	Когда действие завершается, исполнитель уменьшает на единицу счетчик RVP первой фазы (RVP1).
Шаг 5:	Исполнитель, действие которого обнулило счетчик RVP1, инициирует следующую фазу, помещая соответствующее действие в очередь к исполнителю History.
Шаг 6:	Исполнитель History выбирает действие из начала входной очереди.
Шаг 7:	Исполнитель таблицы History производит поиск в локальной таблице блокировок.
Шаг 8:	Транзакция Payment вставляет запись в таблицу History, и по причине, которую мы объясняли в п. 4.2.1, исполнитель действия нуждается во взаимодействии с централизованным менеджером блокировок.
Шаг 9:	Когда действие завершается, исполнитель History обновляет последнюю RVP и вызывает фиксацию транзакции.
Шаг 10:	Когда основной сервер хранения данных производит возврат из общесистемной фиксации (с выталкиванием буфера журнала и освобождением всех централизованных блокировок), исполнитель History ставит идентификаторы всех действий в очереди к их исполнителям.
Шаг 11:	Исполнитель выбирает идентификатор зафиксированного действия.
Шаг 12:	Исполнители удаляют соответствующие элементы из своих локальных таблиц блокировок и ищут в списке отложенных действий действие, выполнение которого теперь можно продолжить.

<
Этот детальный пример выполнения транзакции, в особенности, его шаги 9-12 показывают, что операция фиксации в DORA похожа на двухфазный протокол фиксации (two-phase commit protocol, 2PC) в том смысле, что поток управления, вызывающий фиксацию (координатор в 2PC), также посылает сообщения различным исполнителям (участникам в 2PC) сообщения для освобождения локальных блокировок. Основное отличие от традиционного двухфазного протокола фиксации состоит в том, что рассылка сообщений происходит асинхронно, и что участники не вынуждаются голосовать. Поскольку все изменения журнализуются с одним и тем же идентификатором транзакции, нет потребности в дополнительных сообщениях и вставках в журнал (раздельных сообщениях и записях Prepare и Commit [A.3]). Иначе говоря, фиксация – это одиночная операция с точки зрения журнализации, хотя по-прежнему включает асинхронную посылку сообщений от координатора участникам для освобождения локальных блокировок.

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

A.2.1. Балансировка нагрузки

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

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

Каждое изменение правила маршрутизации задевает двух исполнителей: того, область ответственности которого сокращается, или сокращаемого исполнителя (shrinking executor), и того, которому назначается большая доля таблицы, или расширяемого исполнителя (growing executor). Для изменения размеров наборов данных менеджер ресурсов ставит во входные очереди каждого из этих двух исполнителей некоторое системное действие и модифицирует правило маршрутизации. Когда это системное действие выбирается сокращаемым исполнителем, он прекращает обслуживать новые действия до тех пор, пока систему не покинут все действия, уже обслуженные этим исполнителем. Иначе говоря, сокращаемому исполнителю нужно завершить все выполняемые действия. Иначе он мог бы выполнить действия, направленные на модификацию части данных, за которые после изменения размеров отвечает расширяемый исполнитель.
Расширяемый исполнитель может обычным образом продолжать обслуживать действия над своим "старым" набором данных. Когда все действия, выполняемые сокращаемым исполнителем, завершатся, расширяемый исполнитель сможет начать обслуживать действия, относящиеся к заново назначенному ему набору данных.

С изменением наборов данных во время выполнения связаны также и некоторые косвенные накладные расходы. Для данных, к которым должен теперь обращаться исполнитель, работающий на другом ядре, теряется локальность кэша. Данные должны переместиться в кэш другого ядра, и система претерпевает возрастающий трафик когерентности (coherence traffic) для сбора модифицированных данных, а также возрастающую интенсивность "непопаданий" (miss rate) во время "разогрева" кэша. Поэтому к восстановлению сбалансированности нагрузки во время выполнения системы следует относиться благоразумно, учитывая все упомянутые аспекты. И все равно эта процедура в DORA менее болезненна, чем в системах без совместного использования ресурсов.

A.2.2. Обращения к данным, не согласованные со схемами разделения

Некоторым приложениям может понадобиться доступ к данным, не согласованный со схемой разделения. Например, рассмотрим разделение таблицы Customer из базы данных TPC-C на основе Warehouse_id и транзакцию, пытающуюся обратиться к записям клиентов по именам клиентов. Если эта транзакция выполняется достаточно часто, требуется построить вторичный индекс на столбце имен клиентов таблицы Customer. В системе без совместного использования ресурсов такой индекс пришлось бы построить для каждого раздела.

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

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

A.2. DORA и системы без совместного использования ресурсов

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

Система без совместного использования ресурсов может столкнуться с существенной проблемой производительности из-за несбалансированности, вызываемой "скошенностью" данных или запросов, или из-за наличия обращений к данным, которые не согласуются со схемой разделения. Следовательно, производительность таких систем чувствительна к архитектуре приложений [A2]. Системам без совместного использования ресурсов нужны приложения, рабочая нагрузка которых разделяется таким образом, что лишь небольшую ее часть составляют многораздельные транзакции, нагрузка балансируется между разделами и имеется минимальное число обращений к данным, не согласованных со схемой разделения (см., например, [A.8]).

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

A.3. Сравнение паттернов доступа и потенциальные возможности

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

Рис. 10a. Трасса обращений потоков управления к записям в традиционной системе; обращения к данным являются некоординированными и сложными.

Различие между выполнением транзакций на основе политики назначения транзакций потокам управления (т.е. традиционной политики) и политики назначения потоков управления данным (т.е. политики DORA) становится очевидным, если прибегнуть к визуальному осмотру. На рис. 10(a) показаны обращения всех рабочих потоков управления традиционной системы обработки транзакций к записям таблицы District базы данных TPC-C c 10 складами. В системе имелось 10 рабочих потоков управления, и рабочая нагрузка задавалась 20 клиентами, непрерывно запрашивающими выполение транзакций Payment из тестового набора TPC-C, хотя трассировка производилась только в течение 0,7 секунды работы системы. Обращения к данным являются полностью некоординированными. Для обеспечения согласованности данных системе приходится использовать защелки, расходы на поддержку которых возрастают при росте уровня параллелизма системы.

Рис. 10b. Трасса обращений потоков управления к записям в системе DORA; обращения к данным являются координированными и демонстрируют регулярность.

С другой стороны, рис. 10(b) иллюстрирует воздействие на паттерны доступа к данным политики назначения потоков управления данным. Здесь изображены паттерны доступа к данным в системе DORA при той же рабочей нагрузке, что в случае рис. 10(a). Доступы к данным в DORA являются координированными и демонстрируют регулярность.

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

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

Кроме того, основной характеристикой микроархитектур традиционных систем OLTP является очень большое число обращений по чтению и записи к общей памяти от нескольких процессорных ядер [A1]. К сожалению, эти обращения производятся очень непредсказуемым образом [A6]. Поэтому существенному повышению производительности традиционных систем OLTP не слишком помогают даже такие новые аппаратные технологии, как распределенные на кристалле кэши с обратной связью (reactive distributed on-chip cache) (см., например, [A4, A1]) и/или наиболее развитые средства аппаратного упреждающего чтения (hardware prefetcher) (см., например, [A7]). Поскольку архитектура DORA основана на том, что большая часть обращений к любой заданной части данных происходит из некоторого заданного потока управления, мы ожидаем от нее более "дружеского" поведения, которое позволит использовать все потенциальные возможности современных аппаратных средств за счет обеспечения более частного и предсказуемого доступа к основой памяти.

В будущей работе мы планируем исследовать возможности архитектуры DORA на этих двух фронтах.

A.4. Внутритранзакционный параллелизм при наличии аварийных завершений транзакций

DORA спроектирована в расчете на использование внутритранзакционного параллелизма. Возможности межъядерного взаимодействия современных многоядерных процессоров, обеспечивающие низкие задержки и высокую пропускную способность, позволяют выполнению транзакций в DORA переходить из одного потока управления в другой поток с минимальными накладными расходами, поскольку каждая транзакция обращается к разным частям данных. Одной из проблем внутритранзакционного параллелизма являются транзакции с заметной интенсивностью аварийных завершений. Например, тестовый набор TM1 отличается тем, что в нем большая часть транзакций (∼25%) аварийно завершается из-за неверных входных данных. При выполнении таких рабочих нагрузок DORA может оборвать выполнение действий аварийно завершенных транзакций.

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

Рис. 11. Производительность при выполнении транзакции UpdateSubscriberData из тестового набора TM1, которой свойственна высокая интенсивность аварийных завершений.

На рис. 11 сравнивается пропускная способность базовой системы и двух вариантов DORA при возрастании числа клиентов, постоянно запрашивающих выполнение транзакции UpdateSubscriberData из тестового набора TM1. Эта транзакция, параллельный и последовательный графы потока которой изображены в правой части рисунка, состоит из двух независимых действий. Одно действие пытается обновить таблицу Subscriber и всегда успешно завершается.
Другое действие пытается обновить соответствующий элемент таблицы SpecialFacility, и это удается ему в 62,5% случаев, а в остальных случаях приводит к аварийному завершению всей транзакции из-за неверных входных данных.

Мы представляем графики пропускной способности DORA при применении обеих стратегий выполнения транзакций. Параллельное выполнение обозначается как DORA-P, и последовательное выполнение, при котором сначала предпринимается попытка обновить SpecialFacility, и лишь в случае успешного завершения этого действия обновляется таблица Subscriber, обозначается как DORA-S. Как показывает рисунок, для этой рабочей нагрузки параллельное выполнение является плохим выбором. DORA-P демонстрирует худшую производительность даже по сравнению с базовой системой, в то время как DORA-S масштабируется, как и ожидалось.

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

A. Приложение

Приложение содержит четыре раздела. Сначала для лучшего понимания системы DORA мы подробно описываем выполнение в среде DORA одной транзакции (разд. A.1). Затем мы обсуждаем два преимущества того, что DORA является системой с совместным использованием всех ресурсов (shared-everything), а не системой без совместного использования ресурсов (shared-nothing) (разд. A.2). Далее, чтобы обеспечть лучшее понимание различий между традиционным выполнением транзакций и их выполнением в среде DORA, мы графически демонстрируем различия в их паттернах доступа к данным и обсуждаем возможности использования регулярности паттернов доступа к данным в DORA (разд. A.3). Наконец, мы обсуждаем еще одну проблему DORA, которую составляет выполнение транзакций с заметной интенсивностью аварийных завершений и внутритранзакционным параллелизмом (разд. A4).

Аннотация

Хотя в последнее десятилетие технология компьютерной аппаратуры подверглась значительному развитию, системы обработки транзакций остались, в основном, неизменными. Следуя закону Мура, экспоненциально возрастает число ядер в чипе, что позволяет параллельно выполнять постоянно увеличивающееся число транзакций. По мере возрастания этого числа препятствием к масштабируемости становятся конфликтующие критические участки (critical section). В типичной системе обработки транзакций конфликтующим компонентом и фактором, ограничивающим масштабирование, прежде всего, является менеджер блокировок.

В этой статье мы устанавливаем, что основной причиной конфликтов является традиционная политика назначения каждой транзакции своего потока управления. Затем мы описываем архитектуру системы DORA, которая разбивает транзакции на более мелкие действия и назначает действия потокам управления на основе того, к каким данным, вероятно, обратится каждое действие. Конструктивное решение DORA позволяет каждому потоку управления в основном обращаться к структурам данным, локальным для этого потока, что минимизирует чреватые конфликтами обращения к централизованному менеджеру блокировок. DORA строится поверх традиционного механизма хранения данных и поддерживает все свойства ACID. Экспериментальная оценка прототипной реализации DORA на многоядерной системе при прогонах различных искусственных и реальных рабочих нагрузок показали, что DORA обеспечивает производительность, более чем в 4,8 раз превышащую производительность современных механизмов хранения данных.

Благодарности

Мы сердечно благодарим Майкла Абд Эль Малека (Michael Abd El Malek), Кирияки Леванти (Kyriaki Levanti) и сотрудников лаборатории DIAS за их отзывы и техническую поддержку. Мы благодарны рецензентам PVLDB за их ценные отзывы на ранние варианты этой статьи. Эта работа частично поддерживалась исследовательской стипендией Sloan, грантами NFS CCR-0205544, IIS-0133686 и IIS-0713409, премией ESF EurYI и Swiss National Foundation.

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

Чтобы распределить работу каждой транзакции по соответствующим исполнителям, 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 другому исполнителю. Так что на производительность этой системы не влияет процентное соотношение "удаленных" транзакций.

Экспериментальные среда и рабочие нагрузки

Аппаратура: Мы выполняли все свои эксперименты на машине Sun T5220 "Niagara II", сконфигурированной с 32 гигабайтами основной памяти и функционирующей под управлением Sun Solaris 10. В чипе Sun Niagara II содержится 8 ядер, каждое из которых может поддерживать 8 аппаратных контекстов, что в целом образует 64 процессора, "видимых операционной системой". В каждом ядре имеется два исполнительных конвейера (execution pipeline), что позволяет одновременно обрабатывать команды из любых двух потоков управления. Таким образом, процессор может выполнять до 16 команд за один аппаратный цикл, используя много доступных контекстов для перекрытия задержек в каком-либо одном потоке управления.

Подсистема ввода-вывода: При выполнении рабочих нагрузок OLTP на процессоре Sun Niagara II обе системы способны продемонстрировать высокую производительнось. Требования к подсистеме ввода-вывода возрастают с ростом пропускной способности из-за потребности в выталкивании на диск модифицированных страниц и записи данных в журнал. Если операции ввода-вывода генерируются произвольным образом, то для удовлетворения этого требования могут понадобиться сотни или даже тысячи дисков. Из-за ограниченного бюджета проекта, а также из-за того, что нас интересовало поведение систем при использовании большого числа аппаратных контекстов, мы сохраняли базу данных и журнал в файловой системе в основной памяти. Это решение позволило нам нагрузить центральный процессор, при том, что задействуются все пути выполнения кода менеджера хранения данных. Предварительные эксперименты с использованием высокопроизводительного твердотельного накопителя показывают, что относительное поведение систем остается тем же самым.

Рабочие нагрузки: Мы использовали транзакции из трех тестовых наборов OLTP: Network Database Benchmark или TM-1 [19] компании Nokia, TPC-C [20] и TPC-B [1]. Аналитические рабочие нагрузки типа тестового набора TPC-H приводят к тому, что значительная часть работы выполняется вне менеджера хранения данных, и такие транзакции оказывают небольшое давление на менеджер блокировок.

Поэтому для этого исследования такие

Поэтому для этого исследования такие рабочие нагрузки неинтересны.

TM-1 состоит из семи транзакций, оперирующих с четырьмя таблицами, выполняя различные операции, которые свойственны мобильным сетям. Три транзакции выполняют только чтения, а четвертая обновляет базу данных. Все транзакции являются исключительно короткими, хотя при их выполнении задействуются все пути выполнения кода типичной системы обработки транзакций. Каждая транзакция обращается только к 1-4 записям, и они должны выполняться с небольшой задержкой даже при высоком уровне нагрузки. Мы использовали базу данных с пятью миллионами подписчиков (примерно 7,5 гигабайт). В TPC-C моделируется база данных розничного магазина. Этот тестовый набор состоит из пяти транзакций, поддерживающих заказы клиентов от их создания до доставки и оплаты покупок. Мы использовали набор данных со 150 складами (около 20 гигабайт) и буферный пул в 4 гигабайта. При наличии 150 складов можно поддерживать достаточное число параллельных запросов, чтобы загрузить машину, но при этом база данных остается достаточно небольшой, помещаясь в файловой системе в основной памяти. В TPC-B моделируется банк, в котором пользователи заносят деньги на свои счета и снимают их. Мы использовали набор данных TPC-B со 100 банковскими отделениями (примерно 2 гигабайта).

Для каждого прогона тестовый набор порождает некоторое число клиентов, и они начинают подавать запросы на образование транзакций. Хотя клиенты выполняются на той же машине, что и система, они добавляют лишь небольшие накладные расходы (<3%). Мы повторяли измерения несколько раз, и измеренное относительное среднеквадратическое отклонение составило меньше 5%. Мы применяли опции наивысшей оптимизации в компиляторе Sun CC v5.10. В измерениях, для которых требовалось прифилирование, применялись инструментальные средства из набора Sun Studio 12. Средства профилировки порождали некоторые накладные расходы (∼15%), но относительное поведение обеих систем оставалось неизменным.

Литература

[1] Anon, et al. A measure of transaction processing power. Datamation, 1985.

[2] E. Bugnion, et al. Disco: running commodity operating systems on scalable multiprocessors. ACM TOCS, 15(4), 1997.

[3] M. Carey, et al. Shoring Up Persistent Applications. In Proc. SIGMOD, 1994.

[4] C. Colohan, et al. Optimistic Intra-Transaction Parallelism on Chip Multiprocessors. In Proc. VLDB, 2005.

[5] G. DeCandia, et al. Dynamo: Amazon's Highly Available Key-value Store. In Proc. SOSP, 2007.

[6] D. J. DeWitt, et al. The Gamma Database Machine Project. IEEE TKDE 2(1), 1990.

[7] H. Garcia-Molina, and K. Salem. Sagas. In Proc. SIGMOD, 1987.

[8] G. Graefe. Hierarchical locking in B-tree indexes. In Proc. BTW, 2007.

[9] S. Harizopoulos, et al. OLTP Through the Looking Glass, and What We Found There. In Proc. SIGMOD, 2008.

Перевод на русский язык: Ставрос Харизопулос, Дэниэль Абади, Сэмюэль Мэдден, Майкл Стоунбрейкер. OLTP в Зазеркалье, 2008.

[10] S. Harizopoulos, V. Shkapenyuk, and A. Ailamaki. QPipe: A Simultaneously Pipelined Relational Query Engine. In Proc. SIGMOD, 2005.

[11] P. Helland. Life Beyond Distributed Transactions: an Apostate's Opinion. In Proc. CIDR, 2007.

[12] R. Johnson, et al. A New Look at the Roles of Spinning and Blocking. In Proc. DaMoN, 2009.

[13] R. Johnson, I. Pandis, and A. Ailamaki. Improving OLTP Scalability with Speculative Lock Inheritance. In Proc. VLDB, 2009.

[14] R. Johnson, I. Pandis, N. Hardavellas, A. Ailamaki, and B. Falsafi. Shore-MT: A Scalable Storage Manager for the Multicore Era. In Proc. EDBT, 2009.

[15] E. Jones, D. Abadi, and S. Madden. Low Overhead Concurrency Control for Partitioned Main Memory Databases. In Proc. SIGMOD, 2010.

Перевод на русский язык: Эван Джонс, Дэниэль Абади и Сэмуэль Мэдден. Управление параллелизмом с низкими накладными расходами для разделенных баз данных в основной памяти, 2009.

[16] A. Joshi. Adaptive Locking Strategies in a Multi-node Data Sharing Environment. In Proc. VLDB, 1991.

[17] T. Lahiri, et al. Cache Fusion: Extending shared-disk clusters with shared caches. In Proc. VLDB, 2001.

[18] C. Mohan, et al. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM TODS 17(1), 1992.

[19] Nokia. Network Database Benchmark.

[20] Transaction Processing Performance Council. TPC - C v5.5: On-Line Transaction Processing (OLTP) Benchmark.

[21] M. Stonebraker, et al. The End of an Architectural Era (It's Time for a Complete Rewrite). In Proc. VLDB, 2007.

Перевод на русский язык: Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд. Конец архитектурной эпохи, или Наступило время полностью переписывать системы управления данными, 2007.

Литература к приложению

[A1] B. M. Beckmann, and D. A. Wood. Managing Wire Delay in Large Chip-Multiprocessor Caches. In Proc. MICRO, 2004.

[A2] C. Curino, Y. Zhang, E. Zones, and S. Madden. Schism: a Workload-Driven Approach to Database Replication and Partitioning. In Proc. VLDB, 2010.

Перевод на русский язык: Карло Курино, Эван Джонс, Янг Жанг и Сэм Мэдден. Schism: управляемый рабочей нагрузкой подход к репликации и разделению баз данных, 2010.

[A3] J. Gray, and A. Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.

[A4] N. Hardavellas, M. Ferdman, B. Falsafi and A. Ailamaki. Reactive NUCA: Near-Optimal Block Placement and Replication in Distributed Caches. In Proc. ISCA, 2009.

[A5] S.-W. Lee, et al. A Case for Flash Memory SSD in Enterprise Database Applications. In Proc. SIGMOD, 2008.

[A6] S. Somogyi, et al. Memory Coherence Activity Prediction in Commercial Workloads. In Proc. WMPI, 2004.

[A7] S. Somogyi, T. F. Wenisch, A. Ailamaki, and B. Falsafi. Memory Coherence Activity Prediction in Commercial Workloads. In Proc. ISCA, 2009.

[A8] VoltDB. Developing VoltDB Applications.

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

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

Максимальная пропускная способность

Контроль доступа (admission control) может ограничивать число выполняемых транзакций, что, в свою очередь, ограничивает уровень конкуренции внутри менеджера блокировок системы. При должной настройке контроль доступа позволяет системе достичь предельно возможной пропускной способности, даже если это означает недоиспользуемость ресурсов машины. На рис. 8 приведены результаты сравнения максимальной пропускной способности базовой системы и DORA при использовании идеального контроля доступа. Для каждой системы и рабочей нагрузки показан коэффициент использования процессора, при котором достигается максимальная пропускная способность. DORA достигает более высокой максимальной пропускной способности на всех исследованных нами рабочих нагрузках, и эта пиковая пропускная способности достигается на пределе возможностей аппаратуры.

Для транзакций из тестовых наборов TPC-C и TPC-B DORA демонстрирует менее значительные преимущества. Это объясняется двумя причинами. Во-первых, этим транзакциям свойственна меньшая конкуренция внутри менеджера блокировок, что лишает DORA основного ее преимущества над базовой системой. Во-вторых, некоторые из этих транзакций (такие как NewOrder и Payment из TPC-C и TPC-B) оказывают сильное давление на менеджер журнала, который становится новым узким местом.

Менеджер блокировок как источник конкуренции

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

Типичная рабочая нагрузка OLTP состоит из большого числа параллельных кратковременных транзакций, каждая из которых обращается к небольшой части (от одной до десяти записей) крупного набора данных. Каждая транзакция независимо выполняется в отдельном потоке управления. Для обеспечения целостности данных транзакции входят в большое число критических участков, координирующих доступ к совместно используемым ресурсам. Одним из совместно используемых ресурсов являются блокировки. Менеджер блокировок отвечает за поддержку изоляции параллельно выполняемых транзакций, обеспечивая транзакциям интерфейс для запросов (request), повышения уровня (upgrade) и освобождения (release) блокировок. Скрытым образом менеджер блокировок также обеспечивает получение транзакциями соответствующих блокировок намерений (intention lock) и выполняет действия для предотвращения и выявления синхронизационных тупиков (deadlock).

Опишем менеджер блокировок сервера хранения данных Shore-MT [14]. Хотя детали реализации менеджеров блокировок в коммерческих системах в основном неизвестны, мы полагаем, что они устроены аналогичным образом. Они могут различаться только реализацией защелок. В Shore-MT для этого используется допускающий вытеснения (preemption-resistant) вариант MCS-спинлоков с очередями. (MCS происходит от фамилий авторов алгоритма – Меллора-Крамми (Mellor-Crummey) и Скотта (Scott); см. их оригинальную статью. Прим. переводчика.) При использовании аппаратуры нашего испытательного стенда Sun Niagara II и при той загрузке процессора, которая применялась в нашем исследовании (<120%), реализации на основе спинлоков превосходят про производительности любое другое известное нам решение, включая блокирование (blocking) [12].

В Shore-MT каждая логическая блокировка представляется структурой данных, содержащей режим блокировки, указатель на начало списка запросов этой блокировки (удовлетворенных или ожидающих удовлетворения), а также защелку.
Когда транзакция пытается получить некоторую блокировку, менеджер блокировок сначала убеждается в том, что эта транзакция удерживает требуемые блокировки намерений более высокого уровня, автоматически запрашивая их в случае надобности. Если обнаруживается подходящая удерживаемая транзакцией блокировка более высокого уровня, то запрос немедленно удовлетворяется. Иначе менеджер блокировок зондирует хэш-таблицу, чтобы найти требуемую блокировку. После обнаружения блокировки она "защелкивается", и к списку запросов добавляется новый запрос. Если этот запрос несовместим с текущим режимом блокировки, транзакция блокируется. В конечном счете, защелка с блокировки снимается, и выполняется возврат из менеджера блокировок. В каждой транзакции поддерживается список всех ее запросов блокировок в порядке их получения. При завершении транзакции она по очереди освобождает блокировки, начиная с первой полученной блокировки. Для освобождения блокировки менеджер блокировок "защелкивает" ее и выбирает из списка запросов соответствующий запрос. Прежде чем снять защелку, менеджер просматривает список запросов для определения нового режима блокировки и нахождения всех отложенных запросов, которые теперь могут быть удовлетворены.

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

Рис. 3. Распределение времени внутри менеджера блокировок Shore-MT при выполнении тестового набора TPC-B и повышении уровня загрузки процессора.

Рис. 3 показывает, на что тратится время внутри менеджера блокировок Shore-MT при выполнении тестового набора TPC-B (коэффициент использования системы возрастает по оси абцисс). В общее время включается время, тратящееся на получение блокировок, на освобождение блокировок и на обслуживание конкуренции за выполнение этих операций. Когда система загружена слабо, более 85% времени работы менеджера блокировок тратится на выполнение полезной работы. Однако по мере возрастания загрузки начинает доминировать время, уходящее на обслуживание конкуренции. При стопроцентной загрузке процессора 85% времени работы менеджера блокировок тратится на обслуживание конкуренции (циклическое опрашивание (spinning) защелок).

Мы используем термин логические блокировки (logical locking), а не просто блокировки (locking), чтобы подчеркнуть их отличие от защелок (latching). Защелки используются для поддержки физической согласованности структур данных в основной памяти; логические блокировки позволяют поддерживать логическую согласованность ресурсов базы данных, таких как записи и таблицы.

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

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

она связывает рабочие потоки управления с отдельными частями базы данных;

она распределяет работу каждой транзакции по потокам управления в соответствии с данными, к которым обращаются транзакции;

она по возможности избегает взаимодействий с централизованным менеджером блокировок при обработке запросов блокировок.

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

Оценка производительности

Для сравнения прототипа DORA c системой Shore-MT (называемой далее "базовой системой") мы используем один из наиболее параллельных многоядерных процессоров, доступных на рынке. Имеющиеся производительность и масштабируемость Shore-MT привели к тому, что эта система одной из первых столкнулась с проблемой конкуренции. По мере роста уровня аппаратного параллелизма и решения в системах обработки транзакций других проблем масштабируемости этим системам, скорее всего, тоже придется встретиться с проблемой конкуренции в менеджере блокировок.

Наша оценка затрагивает три области. Во-первых, мы оцениваем, насколько эффективно DORA сокращает число взаимодействий с централизованным менеджером блокировок, и как это воздействует на производительность (подраздел 5.2). Затем мы количественно оцениваем, насколько хорошо в DORA используется внутритранзакционный параллелизм (подраздел 5.3). И, наконец, мы складываем все вместе и сравниваем пиковую производительность, достигаемую DORA и Shore-MT при использовании некоторого идеального механизма контроля доступа (подраздел 5.4).

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

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

Почти "shared-nothing" в среде "shared-everything" – от переводчика

В последнее время специалисты в области баз данных больше всего говорят про архитектуры параллельных СУБД без совместного использования ресурсов, ориентированные на поддержку как аналитических, так и транзакционных приложений. Это, в частности, подтверждается выборкой статей, переводы которых были опубликованы в библиотеке CITForum в последние несколько лет. Активный интерес к архитектурам shared-nothing естественным образом объясняется возможностями неограниченного горизонтального масштабирования аппаратных средств за счет использования кластерных систем, в узлах которых применяются компьютеры из категории товаров широкого потребления (commodity).

Но задумаемся, что такое сегодня "компьютер массового спроса"? Этот компьютер снабжается, как минимум, двухъядерным (а завтра четырехъядерным, а послезавтра восьмиядерным) процессором, в ядрах которого на аппаратном уровне поддерживается выполнение нескольких потоков управления. Т.е. это мощная параллельная машина, и не использовать ее параллелизм для поддержки локальных СУБД, входящих в состав параллельной СУБД без совместного использования ресурсов, по меньшей мере, безнравственно, а по большому счету, экономически нецелесообразно.

Кроме того, на переднем крае развития микропроцессорной технологии находятся такие процессоры, как использованный в работе авторов представляемой вам статьи процессор Sun T5220 "Niagara II", уже сегодня обеспечивающий (с точки зрения операционной системы) 64-процессорную систему с общей памятью. При наличии правильно спроектированной СУБД мощности "однопроцессорной" системы, оснащенной таким процессором (а послезавтра процессором "массового спроса"), хватит для поддержки системы OLTP не самого мелкого предприятия.

Так что развитие технологии СУБД, выполняемых на машинах с общим использованием всех ресурсов, является очень актуальной задачей. Однако, как показывают авторы статьи, по мере роста числа ядер и совершенствования реального использования параллелизма в СУБД узким местом становится традиционный централизованный менеджер блокировок.
В представленной авторами архитектуре DORA эта проблема решается путем логического разделения таблиц базы данных по потокам управления. В каждом таком потоке управления (исполнителе) выполняются части транзакций (действия), обращающиеся только к данным соответствующего раздела, и логическая синхронизация доступа большей частью рассредоточена по исполнителям.

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

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

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

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

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

Сергей Кузнецов

Поток управления для транзакции или поток управления для данных?

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

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

Рис. 1. DORA в сравнении с традиционной системой при рабочей нагрузке, состоящей из транзакций GetSubscriberData тестового набора TM1: (a) пропускная способность в соответствии с коэффициентом использования процессора при возрастании этого коэффициента; (b) распределение времени традиционной системы; (c) распределение времени прототипа DORA.

Чтобы можно было оценить влияние на производительность накладных расходов на конкуренцию за вход в критические участки, на рис. 1(a) показана производительность традиционного менеджера хранения данных в соответствии с коэффициентом использования процессора при возрастании этого коэффициента. Рабочая нагрузка основана на клиентах, постоянно запускающих транзакции GetSubscriberData из эталонного тестового набора TM1 (подробности об используемой методологии см. в разд. 5). По мере возрастания коэффициента использования машины производительность системы в соответствии с этим коэффициентом падает. При использовании всех 64 аппаратных контекстов производительность в расчете на один контекст падает более чем на 80%.
Как показывает рис. 1(b), в общем времени работы системы быстро начинает доминировать конкуренция внутри менеджера блокировок. Каждый из 64 аппаратных контекстов тратит более 85% своего времени выполнения на потоки управления, ожидающие входа в критические участки внутри менеджера блокировок.

Основываясь на том наблюдении, что некоординированный доступ к данным приводит к высокому уровню конкуренции, мы предлагаем для снижения этого уровня архитектуру системы, ориентированную на данные (data-oriented architecture, DORA). Вместо связывания каждого потока управления с некоторой транзакцией, в DORA каждый поток управления связывается с некоторой отдельной частью базы данных. Транзакции переходят из одного потока управления в другой поток, когда им требуется обращаться к другим данным; мы называем этот механизм назначением потоков управления данным. DORA разбивает транзакции на более мелкие действия в соответствии с тем, к каким данным они обращаются, и направляет их для выполнения в соответствующие потоки управления. По сути, вместо "вытягивания" (pull) данных (записей базы данных) к вычислениям (транзакциям) DORA распределяет вычисления в соответствии с отображением данных на потоки управления.

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

Рис. 2. Распределение времени традиционной системы обработки транзакций и прототипа DORA при полном использовании всех 64 аппаратных контекстов чипа Sun Niagara II при пропуске (a) тестового набора TM1 и (b) транзакций OrderStatus тестового набора TPC-C.

В DORA используется высокопропускной механизм коммуникаций с малыми задержками между ядрами многоядерной системы.Транзакции переходят от одного потока управления к другому потоку с минимальными накладными расходами, поскольку в каждом потоке управления производится доступ к отдельной части базы данных. На рис. 2 сравнивается распределение времени традиционной системы управления транзакциями и прототипной реализации DORA при использовании всех 64 аппаратных контекстов чипа Sun Niagara II при пропуске тестового набора TM1 компании Nokia и транзакций OrderStatus тестового набора TPC-C [20]. В прототипе DORA устраняется конкуренция в менеджере блокировок (рис. 2(a)). Кроме того, централизованное управление блокировками заменяется облегченным механизмом блокирования, локальным для потоков управления (рис. 2(b)).

Проблемы

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

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

Чтобы получить возможность оценить архитектуру 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

Родственные работы

Накладные расходы блокировок – это хорошо известная проблема даже однопотоковых систем. Харизопулос (Harizopoulos) и др. [9] анализируют поведение однопотокового менеджера хранения данных SHORE [3] при пропуске двух транзакций из тестового набора TPC-C. При пропуске транзакции Payment система тратит 25% времени на выполнение кода, имеющего отношение к блокировкам, а при пропуске транзакции NewOrder – 16%. Мы подтверждаем эти результаты и раскрываем скрытую проблему конкуренции за защелки, которая делает менеджер блокировок узким местом при возрастании уровня аппаратного параллелизма.

Организация параллельной системы баз данных Rdb/VMS [16] оптимизирована в расчете на устранение узкого места при коммуникации узлов. Чтобы сократить стоимость сетевых передач запросов блокировок, в Rdb/VMS логическая блокировка удерживается в том узле, который ее последним использовал, до тех пор, пока этот узел не возвратит ее узлу-владельцу, или пока не поступит запрос от другого узла. Система Cache Fusion [17], используемая в Oracle RAC, позволяет в кластерах с совместно используемыми дисками объединять буферные пулы узлов и сокращать число обращений к совместно используеым дискам. Подобно тому, как это делается в DORA, Cache Fusion не разделяет данные физическим образом, а распределяет логические блоки. Однако ни в Rdb/VMS, ни в Cache Fusion не затрагивается проблема конкуренции. Большое число потоков управления может обращаться в одно и то же время к одним и тем же ресурсам, что приводит к плохой масштабируемости. В DORA обеспечивается обращение к большинству ресурсов только в некотором одном потоке управления.

В традиционной системе потенциально можно было бы добиться наличия функциональных возможностей DORA, если бы в каждом потоке управления, выполняющем некоторую тразакцию, удерживалась монопольная блокировка некоторой области записей. Монопольная блокировка ассоциируется с потоком управления, а не с какой-либо транзакцией, и удерживается для нескольких транзакций.
Для реализации такого поведения можно было бы использовать разделительные ключи (separator key) [8].

Метод спекулятивного наследования блокировок (speculative lock inheritance, SLI) [13] выявляет во время выполнения "ходовые" ("hot") блокировки, и эти блокировки могут удерживаться потоками управления, выполняющими транзакции, для нескольких транзакций. Как и DORA, SLI снижает конкуренцию в менеджере блокировок. Однако этот метод не позволяет существенно сократить другие накладные расходы внутри менеджера блокировок.

Достижения в области технологии виртуальных машин [2] позволяют применять в многоядерных установках системы без совместного использования ресурсов (shared-nothing). В конфигурациях без совместно используемых ресурсов база данных разделяется на физическом уровне, и имеется репликация как команд, так и данных. Для транзакций, затрагивающих несколько разделов, требуется применять распределенные алгоритмы консенсуса. В H-Store [21] подход отказа от совместного использования ресурсов доводится до крайности за счет использования набора однопотоковых серверов, которые последовательно обрабатывают запросы, избегая управления параллелизмом. В то же время Джонс (Jones) и др. [15] исследуют "спекулятивную" схему блокировок для H-Store, которая может применяться для рабочих нагрузок с многораздельными транзакциями. Значительными проблемами систем без совместного использования ресурсов являются сложность координации распределенных транзакций [11, 5] и неустойчивость, вызываемая "скошенными" (skewed) данными или запросами. Архитектура DORA с совместным использованием всех ресурсов менее чуствительна к таким проблемам и может легче адаптироваться к изменениям нагрузки. В приложении мы обсуждаем, в чем выигрывает DORA от возможности совместного использования ресурсов.

У систем баз данных с поэтапной обработкой запросов (staged database system) [10] имеются общие черты с подходом DORA. Такая система расщепляет запросы на несколько запросов, которые могут выполняться параллельно.

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

В DORA для снижения уровня конкуренции используется внутритранзакционный параллелизм. Внутритранзакционный параллелизм является темой исследований в течение более двух десятилетий (см., например, [7]). Колохэн (Colohan) и др. [4] используются для параллельного выполнения транзакций спекуляцию на уровне потоков управления. Они демонстрируют потенциал внутритранзакционного параллелизма, достигая времени ответа, на 75% меньшего, чем у традиционной системы. Однако спекуляция на уровне потоков управления – это метод, основанный на аппаратуре, и недоступный в сегодняшних аппаратных средствах. Для поддержки механизма DORA требуются только быстрые коммуникации между ядрами, которые уже поддерживаются в аппаратуре многоядерных процессоров.

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

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

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

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

Устранение конкуренции в менеджере блокировок

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

Результаты показаны на рис. 1. На самом левом рисунке показана пропускная способность в соответствии с коэффициентом использования процессора при возрастании этого коэффициента. На двух других диаграммах показано разделение времени каждой из двух систем. Можно видеть, что конкуренция в менеджере блокировок становится узким местом базовой системы, отбирая более 85% от общего времени выполнения. В отличие от этого, в DORA конкуренция в менеджере блокировок устраняется. Как можно заметить, накладные расходы механизма DORA невелики, намного меньше тех, которые возникают при работе централизованного менеджера блокировок даже при отсутствии конкуренции. Важно заметить, что GetSubscriberData – это только читающая транзакция. И, тем не менее, базовая система испытывает серьезные трудности из-за конкуренции внутри менеджера блокировок. Это объясняется тем, что потоки управления конкурируют даже в тех случаях, когда им требуется получить одну и ту же блокировку в совместимых режимах.

Рис. 5. Блокировки, запрошенные 100 транзакциями в базовой системе и в DORA при трех рабочих нагрузках.

Далее мы численым образом оценивали, насколько эффективно DORA сокращает число взаимодействий с централизованным менеджером блокировок, и как это влияет на производительность. Мы измеряли число блокировок, запрашиваемых в базовой системе и в DORA.
Мы инструментировали код для сбора данных о числе и типе запрашиваемых блокировок. На рис. 5 показано число блокировок, запрошенных 100 транзакциями при выполнении обеими системами транзакций из тестовых наборов TM1 и TPC-B, а также транзакции OrderStatus из TPC-C. Блокировки разбиваются на три типа: блокировки уровня записей, блокировки центрального менеджера блокировок, не являющиеся блокировками уровня записей (на рисунке они обозначены как "higher level"), и локальные блокировки DORA.

При типичной рабочей нагрузке OLTP конкуренция за блокировки уровня записей имеет ограниченный характер, поскольку имеется очень большое число записей, доступ к которым происходит случайным образом. Но по мере продвижения вверх по иерархии блокировок можно ожидать возрастания уровня конкуренции. Например, каждой транзакции требуется получить блокировки намерений на уровне таблиц. На рис. 5 показано, что в DORA имеются лишь минимальные взаимодействия с централизованным менеджером блокировок. При выполнении тестового набора TPC-B в DORA запрашивается блокировка не уровня записей из-за управления областью хранения данных (выделения новой области страниц).

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

Рис. 6. Производительность базовой системы и DORA при возрастании загрузки системы при выполнении транзакций тестовых наборов TM1 и TPC-B, а также транзакций OrderStatus из TPC-C.

Рис. 6 подтверждает эти ожидания. Мы представляем диаграммы производительности обеих систем при трех рабочих нагрузках. На оси абцисс показана предлагаемая загрузка процессора. Предлагаемая загрузка процессора вычисляется путем сложения измеряемого времени использования процессора и времени, которое потоки управления тратят на ожидание ресурса процессора в очереди потоков управления, готовых к выполнению. Мы видим, что базовой системе свойственны проблемы масштабируемости, наиболее серьезные в случае TM1. С другой стороны, производительность DORA масштабируется настолько хорошо, насколько это позволяют аппаратные ресурсы.

Когда предлагаемая загрузка процессора превышает 100%, производительность традиционной системы на всех трех рабочих нагрузках резко падает. Это происходит из-за того, что операционной системе приходится вытеснять потоки управления с процессора, и в некоторых случаях это происходит в середине конфликтных критических участков. С другой стороны, производительность DORA остается высокой; это еще раз доказывает, что в DORA число конфликтных критических участков уменьшается.

Вклад и организация статьи

Вкладом статьи является следующее:

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

Мы предлагаем ориентированную на данные архитектуру OLTP, которая обнаруживает предсказуемые схемы доступа к данным и позволяет заменить тежеловесный централизованный менеджер блокировок легковесным механизмом блокировок, локальным для потоков управления. Результатом является система с совместным использованием всех ресурсов (shared-everything), масштабируемая до большого числа ядер без ослабления свойств ACID.

Мы оцениваем протитипный механизм обработки транзакций DORA и показываем, что он позволяет достичь пиковой производительности, на 82% превышающей пиковую производительность традиционного менеджера хранения данных. При отсутствии контроля доступа (admission control) выигрыш в производительности DORA может достичь более 4,8 раз. Кроме того, в неполностью нагруженном состоянии DORA обеспечивает сокращение времени ответа на 60%, поскольку используется внутритранзакционный параллелизм, естественный для многих транзакций.

Оставшаяся часть статьи организована следующим образом. В разд. 2 обсуждаются родственные работы. В разд. 3 объясняется, почему традиционная система обработки транзакций может испытывать трудности из-за конкуренци внутри своего менеджера блокировок. В разд. 4 представляется DORA – арихитектура, основанная на назначении потоков управления данным. В разд. 5 оценивается производительность протитипа DORA, и в разд. 6 содержатся заключительные выводы.

Внутритранзакционный параллелизм

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

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

В эксперименте, результаты которого показаны на рис. 7, мы сравнивали среднее время ответа на запрос в базовой системе и в DORA, достигаемой в ситуации, когда от одного клиента поступают запросы на образование транзакций с внутренним параллелизмом из трех рабочих нагрузок, и журнал располагается в файловой системе в основной памяти. В DORA используется доступный внутритранзакционный параллелизм и достигается меньшее время ответа. Например, транзакции NewOrder из тестового набора TPC-C выполняются в среде DORA на 60% быстрее.

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

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

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

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

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

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

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

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

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

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

Снижающийся эффект повышения внутрикристальной частоты

Снижающийся эффект повышения внутрикристальной частоты вкупе с ограничениями потребления энергии и отвода тепла заставляют поставщиков аппаратных средств размещать в одном кристалле несколько процессорных ядер и полагаться на параллелизм на уровне потоков управления для повышения производительности. В сегодняшних многоядерных процессорах в одном восьмиядерном чипе поддерживается 64 аппаратных контекста, и спросом пользуются многоядерные процессоры с еще большим числом контекстов, ориентированные на специализированное использование. Эксперты из индустрии и академии предсказывают, что число ядер в одном кристалле будет возрастать в соответствии с законом Мура, т.е. в геометрической прогрессии.
По мере экспоненциального роста числа аппаратных контекстов в одном чипе становится возможно параллельно выполнять небывалое число потоков управления, конкурурирующих за доступ к совместно используемым ресурсам. Приложениям, распараллеливаемым на уровне потоков управления, таким как приложения оперативной обработки транзакций (online transaction processing, OLTP), свойственны все более длительные задержки при вхождении в сильно конфликтные критические участки (critical section), что отрицательно влияет на производительность [14]. Для полезного использования вычислительной мощности многоядерных процессоров необходимо ослабить влияние таких конфликтных узких мест в программных системах и добиться соразмерного возрастания производительности при росте числа ядер.
OLTP необходима для большинства предприятий. В последние десятилетия системы обработки транзакций превратились в сложные программные системы, базы кода которых включают миллионы строк. Однако со времени зарождения таких систем почти неизменными остались основные принципы их разработки. При обработке транзакций имеется множество критических участков [14]. Поэтому при использовании высокопараллельной аппаратуры таким системам свойственны проблемы производительности и масштабирования. Чтобы справиться с проблемами масштабируемости, исследователи предлагают использовать конфигурации без совместного использования ресурсов [6] в одном чипе [21] и/или отказываться от каких-либо свойств ACID [5].

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

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

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

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

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

Оригинал: Ippokratis Pandis, Ryan Johnson, Nikos Hardavellas, Anastasia Ailamaki. Data-Oriented Transaction Execution. 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore. Proceedings of the VLDB Endowment, Vol. 3, No. 1, 2010, pp. 928-939.

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

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

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

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

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

Назначение каждой транзакции своего потока

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