| ||||||||||||
| ||||||||||||
|
2010 г.
Выполнение транзакций, ориентированное на данныеИппократис Пандис, Райан Джонсон, Никос Харадавеллас и Анастасия Айламаки
Содержание
Почти "shared-nothing" в среде "shared-everything" – от переводчикаВ последнее время специалисты в области баз данных больше всего говорят про архитектуры параллельных СУБД без совместного использования ресурсов, ориентированные на поддержку как аналитических, так и транзакционных приложений. Это, в частности, подтверждается выборкой статей, переводы которых были опубликованы в библиотеке CITForum в последние несколько лет. Активный интерес к архитектурам shared-nothing естественным образом объясняется возможностями неограниченного горизонтального масштабирования аппаратных средств за счет использования кластерных систем, в узлах которых применяются компьютеры из категории товаров широкого потребления (commodity). АннотацияХотя в последнее десятилетие технология компьютерной аппаратуры подверглась значительному развитию, системы обработки транзакций остались, в основном, неизменными. Следуя закону Мура, экспоненциально возрастает число ядер в чипе, что позволяет параллельно выполнять постоянно увеличивающееся число транзакций. По мере возрастания этого числа препятствием к масштабируемости становятся конфликтующие критические участки (critical section). В типичной системе обработки транзакций конфликтующим компонентом и фактором, ограничивающим масштабирование, прежде всего, является менеджер блокировок.В этой статье мы устанавливаем, что основной причиной конфликтов является традиционная политика назначения каждой транзакции своего потока управления. Затем мы описываем архитектуру системы DORA, которая разбивает транзакции на более мелкие действия и назначает действия потокам управления на основе того, к каким данным, вероятно, обратится каждое действие. Конструктивное решение DORA позволяет каждому потоку управления в основном обращаться к структурам данным, локальным для этого потока, что минимизирует чреватые конфликтами обращения к централизованному менеджеру блокировок. DORA строится поверх традиционного механизма хранения данных и поддерживает все свойства ACID. Экспериментальная оценка прототипной реализации DORA на многоядерной системе при прогонах различных искусственных и реальных рабочих нагрузок показали, что DORA обеспечивает производительность, более чем в 4,8 раз превышащую производительность современных механизмов хранения данных. 1. ВведениеСнижающийся эффект повышения внутрикристальной частоты вкупе с ограничениями потребления энергии и отвода тепла заставляют поставщиков аппаратных средств размещать в одном кристалле несколько процессорных ядер и полагаться на параллелизм на уровне потоков управления для повышения производительности. В сегодняшних многоядерных процессорах в одном восьмиядерном чипе поддерживается 64 аппаратных контекста1, и спросом пользуются многоядерные процессоры с еще большим числом контекстов, ориентированные на специализированное использование. Эксперты из индустрии и академии предсказывают, что число ядер в одном кристалле будет возрастать в соответствии с законом Мура, т.е. в геометрической прогрессии.По мере экспоненциального роста числа аппаратных контекстов в одном чипе становится возможно параллельно выполнять небывалое число потоков управления, конкурурирующих за доступ к совместно используемым ресурсам. Приложениям, распараллеливаемым на уровне потоков управления, таким как приложения оперативной обработки транзакций (online transaction processing, OLTP), свойственны все более длительные задержки при вхождении в сильно конфликтные критические участки (critical section), что отрицательно влияет на производительность [14]. Для полезного использования вычислительной мощности многоядерных процессоров необходимо ослабить влияние таких конфликтных узких мест в программных системах и добиться соразмерного возрастания производительности при росте числа ядер. OLTP необходима для большинства предприятий. В последние десятилетия системы обработки транзакций превратились в сложные программные системы, базы кода которых включают миллионы строк. Однако со времени зарождения таких систем почти неизменными остались основные принципы их разработки. При обработке транзакций имеется множество критических участков [14]. Поэтому при использовании высокопараллельной аппаратуры таким системам свойственны проблемы производительности и масштабирования. Чтобы справиться с проблемами масштабируемости, исследователи предлагают использовать конфигурации без совместного использования ресурсов [6] в одном чипе [21] и/или отказываться от каких-либо свойств ACID [5]. 1.1. Поток управления для транзакции или поток управления для данных?В этой статье мы утверждаем, что основной причиной проблемы конфликтов являются некоординированные обращения к данным, характерные для традиционных систем обработки транзакций. В этих системах каждой транзакции назначается некоторый рабочий поток управления; этот механизм мы называем назначением потоков управления транзакциям. Поскольку каждая транзакция выполняется в отдельном потоке управления, потоки управления конфликтуют между собой при доступе к совместно используемым данным.Схемы доступа к данным у каждой транзакции и, следовательно, у каждого потока управления являются произвольными и некоординированными. Для обеспечения целостности данных каждый поток управления при выполнении соответствующей транзакции на короткое время входит в большое число критических участков. Однако для входа в критический участок и выхода из него требуется закрытие и открытие соответствующей "защелки" (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)). 1.2. Вклад и организация статьиВкладом статьи является следующее:
Оставшаяся часть статьи организована следующим образом. В разд. 2 обсуждаются родственные работы. В разд. 3 объясняется, почему традиционная система обработки транзакций может испытывать трудности из-за конкуренци внутри своего менеджера блокировок. В разд. 4 представляется DORA – арихитектура, основанная на назначении потоков управления данным. В разд. 5 оценивается производительность протитипа DORA, и в разд. 6 содержатся заключительные выводы. 2. Родственные работыНакладные расходы блокировок – это хорошо известная проблема даже однопотоковых систем. Харизопулос (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 требуются только быстрые коммуникации между ядрами, которые уже поддерживаются в аппаратуре многоядерных процессоров. 1 В современных процессорных ядрах имеется несколько аппаратных контекстов, позволяющих им перемежать выполнение нескольких потоков команд. |
 | |||||||||
| |||||||||
|
CITForum © 1997–2025