Методы контроля параллелизма обеспечивают одновременное выполнение нескольких транзакций, сохраняя свойства ACID транзакций и сериализуемость в расписаниях.
В этой главе мы рассмотрим различные подходы к управлению параллелизмом.
Протоколы управления параллелизмом на основе блокировки
В протоколах управления параллелизмом на основе блокировки используется концепция блокировки элементов данных. Блокировка — это переменная, связанная с элементом данных, которая определяет, могут ли операции чтения / записи выполняться над этим элементом данных. Обычно используется матрица совместимости блокировок, в которой указывается, может ли элемент данных быть заблокирован двумя транзакциями одновременно.
Системы управления параллелизмом на основе блокировки могут использовать однофазные или двухфазные протоколы блокировки.
Протокол однофазной блокировки
В этом методе каждая транзакция блокирует элемент перед использованием и снимает блокировку, как только завершает его использование. Этот метод блокировки обеспечивает максимальный параллелизм, но не всегда обеспечивает сериализуемость.
Протокол двухфазной блокировки
В этом методе все операции блокировки предшествуют первой операции разблокировки или разблокировки блокировки. Сделка состоит из двух этапов. На первом этапе транзакция получает только все необходимые блокировки и не снимает блокировки. Это называется расширяющейся или растущей фазой . На втором этапе транзакция снимает блокировки и не может запрашивать новые блокировки. Это называется фазой сжатия .
Каждая транзакция, которая следует протоколу двухфазной блокировки, гарантированно сериализуется. Однако такой подход обеспечивает низкий параллелизм между двумя конфликтующими транзакциями.
Алгоритмы управления параллелизмом временной метки
Алгоритмы управления параллелизмом на основе временной метки используют временную метку транзакции для координации одновременного доступа к элементу данных для обеспечения сериализуемости. Отметка времени — это уникальный идентификатор, назначаемый СУБД для транзакции, который представляет время начала транзакции.
Эти алгоритмы гарантируют, что транзакции фиксируются в порядке, определяемом их временными метками. Более старая транзакция должна быть зафиксирована до более молодой транзакции, так как более старая транзакция поступает в систему раньше, чем младшая.
Методы управления параллелизмом на основе временных меток генерируют сериализуемые расписания так, чтобы эквивалентное последовательное расписание располагалось в порядке возраста участвующих транзакций.
Некоторые из алгоритмов управления параллелизмом на основе временных меток:
- Основной алгоритм упорядочения временных меток.
- Консервативный алгоритм упорядочения временных меток.
- Мультиверсионный алгоритм, основанный на упорядочении временных меток.
Порядок на основе меток времени следует трем правилам для обеспечения сериализуемости —
-
Правило доступа — когда две транзакции пытаются получить доступ к одному и тому же элементу данных одновременно, для конфликтующих операций приоритет отдается более старой транзакции. Это приводит к тому, что младшая транзакция ожидает первой транзакции.
-
Правило поздней транзакции — если младшая транзакция записала элемент данных, то более старой транзакции не разрешается читать или записывать этот элемент данных. Это правило предотвращает фиксацию более старой транзакции после того, как более ранняя транзакция уже зафиксирована.
-
Младшее правило транзакции — младшая транзакция может считывать или записывать элемент данных, который уже был записан более старой транзакцией.
Правило доступа — когда две транзакции пытаются получить доступ к одному и тому же элементу данных одновременно, для конфликтующих операций приоритет отдается более старой транзакции. Это приводит к тому, что младшая транзакция ожидает первой транзакции.
Правило поздней транзакции — если младшая транзакция записала элемент данных, то более старой транзакции не разрешается читать или записывать этот элемент данных. Это правило предотвращает фиксацию более старой транзакции после того, как более ранняя транзакция уже зафиксирована.
Младшее правило транзакции — младшая транзакция может считывать или записывать элемент данных, который уже был записан более старой транзакцией.
Алгоритм управления оптимистичным параллелизмом
В системах с низкой частотой конфликтов задача проверки каждой транзакции на сериализуемость может снизить производительность. В этих случаях тест на сериализуемость откладывается непосредственно перед фиксацией. Поскольку частота конфликтов низкая, вероятность прерывания транзакций, которые не сериализуются, также низка. Этот подход называется оптимистичным методом управления параллелизмом.
При таком подходе жизненный цикл транзакции делится на следующие три фазы:
-
Этап выполнения — транзакция извлекает элементы данных в память и выполняет над ними операции.
-
Этап проверки — транзакция выполняет проверки, чтобы убедиться, что фиксация изменений в базе данных прошла тест на сериализуемость.
-
Фаза фиксации — транзакция записывает измененный элемент данных в памяти на диск.
Этап выполнения — транзакция извлекает элементы данных в память и выполняет над ними операции.
Этап проверки — транзакция выполняет проверки, чтобы убедиться, что фиксация изменений в базе данных прошла тест на сериализуемость.
Фаза фиксации — транзакция записывает измененный элемент данных в памяти на диск.
Этот алгоритм использует три правила для обеспечения сериализуемости на этапе проверки —
Правило 1 — Если для двух транзакций T i и T j , если T i читает элемент данных, который пишет T j , фаза выполнения T i не может перекрываться с фазой фиксации T j . T j может зафиксировать только после того, как T i закончил выполнение.
Правило 2 — Если для двух транзакций T i и T j , если T i записывает элемент данных, который читает T j , фаза фиксации T i не может перекрываться с фазой выполнения T j . T j может начать выполняться только после того, как T i уже зафиксировано.
Правило 3. Если для двух транзакций T i и T j записывается элемент данных, который также записывает T j , то фаза фиксации T i не может перекрываться с фазой фиксации T j . T j может начать фиксироваться только после того, как T i уже зафиксировал.
Управление параллелизмом в распределенных системах
В этом разделе мы увидим, как описанные выше методы реализованы в распределенной системе баз данных.
Распределенный двухфазный алгоритм блокировки
Основной принцип распределенной двухфазной блокировки такой же, как и основной протокол двухфазной блокировки. Однако в распределенной системе есть сайты, обозначенные как менеджеры блокировок. Менеджер блокировок контролирует запросы на получение блокировки от мониторов транзакций. Для обеспечения координации между менеджерами блокировок на разных сайтах, по крайней мере, одному сайту предоставлены полномочия просматривать все транзакции и обнаруживать конфликты блокировок.
В зависимости от количества сайтов, которые могут обнаружить конфликты блокировок, подходы распределенной двухфазной блокировки могут быть трех типов:
-
Централизованная двухфазная блокировка. При таком подходе один сайт назначается диспетчером центральной блокировки. Все сайты в среде знают местонахождение диспетчера центральной блокировки и получают блокировку от него во время транзакций.
-
Первичная копия двухфазной блокировки — при этом подходе ряд сайтов обозначаются как центры управления блокировками. Каждый из этих сайтов отвечает за управление определенным набором блокировок. Все сайты знают, какой центр управления блокировкой отвечает за управление блокировкой какой таблицы данных / элемента фрагмента.
-
Распределенная двухфазная блокировка. При таком подходе существует несколько менеджеров блокировок, где каждый диспетчер блокировок контролирует блокировки элементов данных, хранящихся на его локальном сайте. Расположение диспетчера блокировки основано на распределении и репликации данных.
Централизованная двухфазная блокировка. При таком подходе один сайт назначается диспетчером центральной блокировки. Все сайты в среде знают местонахождение диспетчера центральной блокировки и получают блокировку от него во время транзакций.
Первичная копия двухфазной блокировки — при этом подходе ряд сайтов обозначаются как центры управления блокировками. Каждый из этих сайтов отвечает за управление определенным набором блокировок. Все сайты знают, какой центр управления блокировкой отвечает за управление блокировкой какой таблицы данных / элемента фрагмента.
Распределенная двухфазная блокировка. При таком подходе существует несколько менеджеров блокировок, где каждый диспетчер блокировок контролирует блокировки элементов данных, хранящихся на его локальном сайте. Расположение диспетчера блокировки основано на распределении и репликации данных.
Управление параллельным распределением меток времени
В централизованной системе временная метка любой транзакции определяется показанием физических часов. Но в распределенной системе показания локальных физических / логических часов любого сайта не могут использоваться в качестве глобальных временных меток, поскольку они не являются глобально уникальными. Таким образом, временная метка содержит комбинацию идентификатора сайта и времени чтения этого сайта.
Для реализации алгоритмов упорядочения меток времени каждый сайт имеет планировщик, который поддерживает отдельную очередь для каждого менеджера транзакций. Во время транзакции менеджер транзакций отправляет запрос на блокировку в планировщик сайта. Планировщик помещает запрос в соответствующую очередь в порядке возрастания отметки времени. Запросы обрабатываются с начала очередей в порядке их меток времени, т. Е. Самые старые сначала.
Конфликт Графики
Другой метод заключается в создании графиков конфликтов. Для этой транзакции определены классы. Класс транзакции содержит два набора элементов данных, называемых набором чтения и набором записи. Транзакция принадлежит определенному классу, если набор чтения транзакции является подмножеством набора чтения класса, а набор записи транзакции является подмножеством набора записи класса. На этапе чтения каждая транзакция выдает свои запросы на чтение для элементов данных в своем наборе чтения. На этапе записи каждая транзакция выдает свои запросы на запись.
Граф конфликтов создается для классов, к которым относятся активные транзакции. Он содержит набор вертикальных, горизонтальных и диагональных ребер. Вертикальное ребро соединяет два узла внутри класса и обозначает конфликты внутри класса. Горизонтальное ребро соединяет два узла между двумя классами и обозначает конфликт записи-записи между различными классами. Диагональное ребро соединяет два узла в двух классах и обозначает конфликт между двумя классами: запись-чтение или чтение-запись.
Графики конфликтов анализируются, чтобы определить, можно ли параллельно выполнять две транзакции в одном и том же классе или в двух разных классах.
Алгоритм распределенного оптимистического параллелизма
Алгоритм распределенного оптимистического параллелизма расширяет алгоритм оптимистичного параллелизма. Для этого расширения применяются два правила:
Правило 1. Согласно этому правилу транзакция должна быть проверена локально на всех сайтах при ее выполнении. Если транзакция признана недействительной на каком-либо сайте, она прерывается. Локальная проверка гарантирует, что транзакция поддерживает сериализуемость на сайтах, где она была выполнена. После того, как транзакция проходит локальный проверочный тест, она проверяется на глобальном уровне.
Правило 2 — Согласно этому правилу, после того, как транзакция прошла локальный проверочный тест, она должна быть проверена на глобальном уровне. Глобальная проверка гарантирует, что если две конфликтующие транзакции выполняются вместе на более чем одном сайте, они должны фиксироваться в одинаковом относительном порядке на всех сайтах, которые они запускают вместе. Для этого может потребоваться, чтобы транзакция ожидала другую конфликтующую транзакцию после проверки перед фиксацией. Это требование делает алгоритм менее оптимистичным, поскольку транзакция не сможет быть зафиксирована, как только она будет проверена на сайте.