Распределенная СУБД - Контроль параллелизма

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

В этой главе мы изучим различные подходы к управлению параллелизмом.

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

Протоколы управления параллелизмом на основе блокировки используют концепцию блокировки элементов данных. Аlock- это переменная, связанная с элементом данных, которая определяет, могут ли операции чтения / записи выполняться с этим элементом данных. Как правило, используется матрица совместимости блокировок, которая указывает, может ли элемент данных быть заблокирован двумя транзакциями одновременно.

Системы управления параллелизмом на основе блокировки могут использовать протоколы однофазной или двухфазной блокировки.

Однофазный протокол блокировки

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

Протокол двухфазной блокировки

В этом методе все операции блокировки предшествуют первой операции снятия блокировки или разблокировки. Сделка состоит из двух этапов. На первом этапе транзакция получает только все необходимые блокировки и не снимает никаких блокировок. Это называется расширением илиgrowing phase. На втором этапе транзакция снимает блокировки и не может запрашивать новые блокировки. Это называетсяshrinking phase.

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

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

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

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

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

Некоторые из алгоритмов управления параллелизмом на основе временных меток:

Базовый алгоритм упорядочивания временных меток.
Консервативный алгоритм упорядочивания временных меток.
Многоверсионный алгоритм, основанный на упорядочивании по отметкам времени

Порядок на основе меток времени следует трем правилам для обеспечения сериализуемости:

Access Rule- Когда две транзакции пытаются получить доступ к одному и тому же элементу данных одновременно, для конфликтующих операций приоритет отдается более старой транзакции. Это заставляет младшую транзакцию ждать, пока старая транзакция не зафиксируется первой.
Late Transaction Rule- Если младшая транзакция записала элемент данных, то более старой транзакции не разрешено читать или записывать этот элемент данных. Это правило предотвращает фиксацию старой транзакции после того, как младшая транзакция уже зафиксирована.
Younger Transaction Rule - Младшая транзакция может читать или записывать элемент данных, который уже был записан более старой транзакцией.

Оптимистический алгоритм управления параллелизмом

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

При таком подходе жизненный цикл транзакции делится на следующие три фазы:

Execution Phase - Транзакция выбирает элементы данных в память и выполняет над ними операции.
Validation Phase - Транзакция выполняет проверки, чтобы гарантировать, что фиксация ее изменений в базе данных прошла тест сериализуемости.
Commit Phase - Транзакция записывает измененный элемент данных из памяти на диск.

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

Rule 1- Учитывая две транзакции T _i и T _j , если T _i читает элемент данных, который записывает T _j , то фаза выполнения T _i не может перекрываться с фазой фиксации T _j . T _j может зафиксироваться только после того, как T _i завершит выполнение.

Rule 2- Учитывая две транзакции T _i и T _j , если T _i записывает элемент данных, который читает T _j , то фаза фиксации T _i не может перекрываться с фазой выполнения T _j . T _j может начать выполнение только после того, как T _i уже зафиксирован.

Rule 3- Учитывая две транзакции T _i и T _j , если T _i записывает элемент данных, который также записывает T _j , то фаза фиксации T _i не может перекрываться с фазой фиксации T _j . T _j может начать фиксацию только после того, как T _i уже зафиксирован.

Контроль параллелизма в распределенных системах

В этом разделе мы увидим, как описанные выше методы реализованы в системе распределенных баз данных.

Распределенный двухфазный алгоритм блокировки

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

В зависимости от количества сайтов, которые могут обнаруживать конфликты блокировок, подходы распределенной двухфазной блокировки могут быть трех типов:

Centralized two-phase locking- При таком подходе один объект назначается менеджером центрального замка. Все сайты в среде знают местонахождение диспетчера центрального замка и получают от него блокировку во время транзакций.
Primary copy two-phase locking- При таком подходе ряд площадок обозначен как центры управления замками. Каждый из этих сайтов отвечает за управление определенным набором блокировок. Все сайты знают, какой центр управления блокировками отвечает за управление блокировкой какой таблицы данных / элемента фрагмента.
Distributed two-phase locking- В этом подходе есть несколько диспетчеров блокировок, каждый из которых управляет блокировками элементов данных, хранящихся на его локальном сайте. Расположение диспетчера блокировок зависит от распределения и репликации данных.

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

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

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

Графики конфликтов

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

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

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

Распределенный алгоритм управления оптимистическим параллелизмом

Распределенный алгоритм управления оптимистическим параллелизмом расширяет алгоритм управления оптимистическим параллелизмом. Для этого расширения применяются два правила:

Rule 1- Согласно этому правилу, транзакция должна проверяться локально на всех сайтах при ее выполнении. Если на каком-либо сайте обнаруживается, что транзакция недействительна, она прерывается. Локальная проверка гарантирует, что транзакция поддерживает сериализуемость на сайтах, где она была выполнена. После того, как транзакция проходит локальный проверочный тест, она проверяется глобально.

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