Управление параллельным доступом в СУБД: протоколы на основе блокировок и временных меток.

Что такое управление параллелизмом?

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

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

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

Потенциальные проблемы параллельного выполнения

Вот некоторые проблемы, с которыми вы, вероятно, столкнетесь без надлежащего управления параллельным доступом в СУБД:

• Утраченные обновления Это происходит, когда несколько транзакций выбирают одну и ту же строку и обновляют её на основе выбранного значения.
• Незакрепленная зависимость Ошибка "грязного чтения" (dirty read) возникает, когда вторая транзакция выбирает строку, которая была обновлена ​​другой транзакцией, еще не подтвержденной.
• Неповторяемое чтение Это происходит, когда вторая транзакция обращается к одной и той же строке несколько раз и каждый раз считывает разные данные.
• Неверное резюме Это происходит, когда одна транзакция вычисляет сводную информацию по значению всех экземпляров повторяющегося элемента данных, в то время как вторая транзакция обновляет лишь некоторые из этих экземпляров. Полученная сводная информация не отражает корректный результат.

Зачем использовать методы параллельного выполнения?

Причины использования методов управления параллельным доступом в СУБД:

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

Пример

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

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

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

Различные протоколы управления параллельным доступом предлагают разные компромиссы между допустимым уровнем параллельного доступа и накладными расходами. Основные методы управления параллельным доступом в СУБД:

• Протоколы на основе блокировок
• Двухфазный протокол блокировки
• Протоколы на основе временных меток
• Протоколы, основанные на проверке

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

Протоколы на основе блокировок

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

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

Бинарные блокировки: Бинарный блокировщик элемента данных может находиться либо в заблокированном, либо в разблокированном состоянии.

Общий/Эксклюзивный: Этот механизм блокировки разделяет блокировки в зависимости от их назначения. Если блокировка получена для выполнения операции записи, она называется эксклюзивной блокировкой.

1. Общий замок (S): Разделяемая блокировка также называется блокировкой только для чтения. При разделяемой блокировке элемент данных может быть общим для нескольких транзакций, поскольку ни одна из них не имеет разрешения на обновление этого элемента. Например, если две транзакции считывают баланс счета человека, то база данных Это позволяет им читать данные, устанавливая разделяемую блокировку. Если другая транзакция захочет обновить этот баланс, разделяемая блокировка предотвратит это до завершения чтения.

2. Эксклюзивный замок (X): При использовании эксклюзивной блокировки элемент данных может быть как считан, так и записан. Она является эксклюзивной и не может одновременно удерживаться для одного и того же элемента данных. X-блокировка запрашивается с помощью инструкции lock-x. Например, когда транзакции необходимо обновить баланс счета, это разрешается путем установки X-блокировки; вторая транзакция, которая хочет прочитать или записать данные, в этом случае предотвращается.

3. Упрощенный протокол блокировки: Это позволяет транзакциям получать блокировку каждого объекта перед началом операции. Транзакции могут разблокировать элемент данных после завершения операции записи.

4. Предварительная блокировка заявки: Этот протокол оценивает операции и создает список элементов данных, необходимых для начала выполнения. Когда все блокировки предоставлены, транзакция выполняется, и все блокировки снимаются после завершения ее операций.

Голодание: «Голодание» — это ситуация, когда транзакция ожидает получения блокировки неопределенное время. Причины могут включать в себя плохо управляемую схему ожидания заблокированных элементов, утечку ресурсов или неоднократное выбор одной и той же транзакции в качестве жертвы.

Тупик: Взаимная блокировка (deadlock) — это ситуация, когда два или более процесса ожидают освобождения ресурса друг другом, образуя замкнутую цепочку.

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

Двухфазный протокол блокировки2PL (также известный как 2PL) — это метод управления параллельным доступом, который обеспечивает сериализуемость путем применения блокировки к данным транзакции, что препятствует одновременному доступу других транзакций к тем же данным.

Протокол двухфазной блокировки позволяет каждой транзакции отправлять запрос на блокировку или разблокировку в два этапа:

• Фаза роста: На этом этапе транзакция может получить блокировки, но не может снять ни одну из них.
• Фаза сокращения: На этом этапе транзакция может снять блокировки, но не может получить новую блокировку.

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

Строгий метод двухфазной блокировки

Strict 2PL практически идентичен 2PL. Единственное отличие заключается в том, что Strict-2PL никогда не снимает блокировку после её использования. Он удерживает все блокировки до точки фиксации и снимает их все сразу после завершения процесса.

Централизованный 2PL

В централизованной системе 2PL за процесс управления блокировками отвечает один объект. Для всей СУБД используется только один менеджер блокировок.

Первичная копия 2PL

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

Распределенный 2PL

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

Протоколы на основе временных меток

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

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

Пример:

Suppose there are three transactions T1, T2, and T3.
T1 has entered the system at time 0010
T2 has entered the system at 0020
T3 has entered the system at 0030
Priority will be given to transaction T1, then T2 and lastly T3.

Преимущества:

• Расписания являются сериализуемыми, как и протоколы 2PL.
• Не требуется ждать завершения транзакции, что исключает возможность тупиковых ситуаций.

Минусы: Приостановка работы одной и той же транзакции может произойти, если она перезапускается и постоянно прерывается.

Протокол, основанный на валидации

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

Протокол, основанный на валидации, выполняется в три этапа:

1. Фаза чтения
2. Фаза проверки
3. Фаза записи

Фаза чтения

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

Фаза проверки

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

Фаза записи

На этапе записи обновления применяются к базе данных, если проверка прошла успешно; в противном случае обновления отменяются, и транзакция откатывается.

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

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

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

Характеристики хорошего протокола параллельного выполнения

Идеальный механизм управления параллельным доступом преследует следующие цели:

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

Часто задаваемые вопросы (FAQ)