Керування паралелізмом СУБД: мітки часу та протоколи на основі блокувань

Одночасний доступ досить простий, якщо всі користувачі просто читають дані. Вони ніяк не можуть заважати один одному. Хоча для будь-якої практичної бази даних вона матиме поєднання операцій READ і WRITE, а отже, паралелізм є проблемою.

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

Потенційні проблеми паралелізму

Ось деякі проблеми, з якими ви, ймовірно, зіткнетеся під час використання методу керування паралелізмом СУБД:

• Втрачені оновлення виникає, коли кілька транзакцій вибирають один рядок і оновлюють рядок на основі вибраного значення
• Проблеми незафіксованої залежності виникають, коли друга транзакція вибирає рядок, який оновлюється іншою транзакцією (брудне читання)
• Неповторне читання виникає, коли друга транзакція намагається отримати доступ до одного рядка кілька разів і кожного разу зчитує різні дані.
• Проблема з неправильним підсумком відбувається, коли одна транзакція підсумовує значення всіх екземплярів повторюваного елемента даних, а друга транзакція оновлює кілька екземплярів цього конкретного елемента даних. У такій ситуації кінцевий підсумок не відображає правильний результат.

Навіщо використовувати метод Concurrency?

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

• Щоб застосувати ізоляцію через взаємне виключення між суперечливими транзакціями
• Для вирішення проблем читання-запису та запису-запису
• Для збереження узгодженості бази даних шляхом постійного збереження перешкод виконання
• Системі необхідно контролювати взаємодію між одночасними транзакціями. Цей контроль досягається за допомогою схем паралельного керування.
• Контроль паралельності допомагає забезпечити можливість серіалізації

Приклад

Припустимо, що двоє людей одночасно заходять до електронних кіосків, щоб купити квиток на той самий фільм і в той самий час.

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

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

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

• Протоколи на основі блокування
• Двофазний протокол блокування
• Протоколи на основі часових позначок
• Протоколи на основі перевірки

Блокування — це змінна даних, пов’язана з елементом даних. Це блокування означає, що операції, які можна виконувати з елементом даних. Блокування в СУБД допомагають синхронізувати доступ до елементів бази даних за допомогою одночасних транзакцій.

Усі запити на блокування надсилаються диспетчеру паралельного керування. Транзакції тривають лише після того, як буде надано запит на блокування.

Двійкові блокування: Двійкове блокування для елемента даних може бути заблокованим або розблокованим.

Спільний/ексклюзивний: Цей тип механізму блокування розділяє блокування в СУБД на основі їх використання. Якщо блокування отримано для елемента даних для виконання операції запису, це називається ексклюзивним блокуванням.

1. Спільний замок (S):

Спільне блокування також називається блокуванням лише для читання. За допомогою спільного блокування елемент даних може бути спільним для транзакцій. Це пояснюється тим, що ви ніколи не матимете дозволу на оновлення даних в елементі даних.

Наприклад, розглянемо випадок, коли дві транзакції зчитують баланс рахунку особи. The база даних дозволить їм читати, розмістивши спільний замок. Однак, якщо інша транзакція хоче оновити баланс цього облікового запису, спільне блокування запобігає цьому, доки не завершиться процес читання.

2. Ексклюзивний замок (X):

За допомогою ексклюзивного блокування елемент даних можна читати та записувати. Це є ексклюзивним і не може зберігатися одночасно на одному елементі даних. X-lock запитується за допомогою інструкції lock-x. Трансакції можуть розблокувати елемент даних після завершення операції «запису».

Наприклад, коли транзакція потребує оновлення балансу рахунку особи. Ви можете дозволити цю транзакцію, поставивши на неї блокування X. Тому, коли друга транзакція хоче читати або писати, ексклюзивне блокування запобігає цій операції.

3. Спрощений протокол блокування

Цей тип протоколів на основі блокування дозволяє транзакціям отримати блокування кожного об’єкта перед початком операції. Трансакції можуть розблокувати елемент даних після завершення операції «запису».

4. Попереднє блокування

Протокол блокування попереднього запиту допомагає оцінити операції та створити список необхідних елементів даних, необхідних для ініціювання процесу виконання. У ситуації, коли всі блокування надані, транзакція виконується. Після цього всі блокування знімаються, коли всі його операції закінчуються.

Голодування

Голод — це ситуація, коли транзакція повинна чекати невизначений період, щоб отримати блокування.

Причини голодування:

• Коли схема очікування для заблокованих елементів не керується належним чином
• У разі витоку ресурсу
• Одна і та ж транзакція неодноразово вибирається жертвою

Deadlock

Взаємоблокування відноситься до конкретної ситуації, коли два або більше процесів чекають один одного, щоб звільнити ресурс, або більше двох процесів очікують на ресурс у циклічному ланцюжку.

Цей протокол блокування розділяє фазу виконання транзакції на три різні частини.

• На першому етапі, коли транзакція починає виконуватися, їй потрібен дозвіл на блокування, які їй потрібні.
• У другій частині транзакція отримує всі блокування. Коли транзакція знімає перше блокування, починається третій етап.
• На цьому третьому етапі транзакція не може вимагати нових блокувань. Натомість він звільняє лише отримані замки.

Протокол двофазного блокування дозволяє кожній транзакції робити запит на блокування або розблокування в два етапи:

• Фаза росту: на цьому етапі транзакція може отримати блокування, але не може звільнити жодне блокування.
• Фаза скорочення: на цьому етапі транзакція може зняти блокування, але не отримати нового блокування

Це правда, що протокол 2PL пропонує можливість серіалізації. Однак це не гарантує, що взаємоблокування не відбудеться.

На наведеній вище діаграмі ви можете бачити, що локальні та глобальні детектори взаємоблокувань шукають взаємоблокування та вирішують їх, відновлюючи транзакції до початкового стану.

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

Сувора двофазна система блокування майже схожа на 2PL. Єдина відмінність полягає в тому, що Strict-2PL ніколи не знімає блокування після його використання. Він утримує всі блокування до точки фіксації та знімає всі блокування за один раз, коли процес завершується.

Централізована 2ПЛ

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

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

Механізм первинної копії 2PL, багато менеджерів блокувань розподілені по різних сайтах. Після цього окремий менеджер блокувань відповідає за керування блокуванням для набору елементів даних. Коли первинну копію оновлено, зміни поширюються на підлеглі.

Роздано 2ПЛ

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

Старіша транзакція завжди має пріоритет у цьому методі. Він використовує системний час для визначення позначки часу транзакції. Це найбільш часто використовуваний протокол паралельного виконання.

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

приклад:

Suppose there are there 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 transaction T2 and lastly Transaction T3.

Переваги:

• Розклади можна серіалізувати, як і протоколи 2PL
• Відсутність очікування транзакції, що виключає можливість тупикових ситуацій!

Недоліки:

Голод можливий, якщо одна і та ж транзакція перезапускається та постійно переривається

Протокол на основі перевірки виконується в наступні три етапи:

1. Прочитайте фазу
2. Етап перевірки
3. Напишіть фазу

Прочитайте фазу

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

Етап перевірки

На етапі перевірки дані перевіряються, щоб переконатися, що немає порушення серіалізації під час застосування оновлень транзакцій до бази даних.

Напишіть фазу

На етапі запису оновлення застосовуються до бази даних, якщо перевірка пройшла успішно, інакше; оновлення не застосовуються, і транзакція відкочується.

Характеристики хорошого протоколу паралелізму

Ідеальний механізм управління паралелізмом СУБД має такі цілі:

• Має бути стійким до збоїв на сайті та зв’язку.
• Це дозволяє паралельно виконувати транзакції для досягнення максимального паралелізму.
• Його механізми зберігання та обчислювальні методи повинні бути скромними, щоб мінімізувати накладні витрати.
• Він повинен накладати деякі обмеження на структуру атомарних дій транзакцій.

Підсумки

• Управління паралелізмом — це процедура в СУБД для керування одночасними операціями без конфлікту один з одним.
• Втрата оновлень, брудне читання, неповторюване читання та неправильне резюме є проблемами, з якими стикаються через відсутність контролю паралельності.
• На основі блокування, двофазний, на основі мітки часу, на основі перевірки є типами протоколів обробки паралелізму
• Замок може бути спільним (S) або ексклюзивним (X)
• Двофазний протокол блокування, який також відомий як протокол 2PL, потребує транзакції, яка повинна отримати блокування після звільнення одного зі своїх блокувань. Має 2 фази зростання і скорочення.
• Алгоритм на основі мітки часу використовує мітку часу для серіалізації виконання одночасних транзакцій. Протокол використовує Системний час або логічний підрахунок як мітка часу.