Контроль паралельної роботи в СУБД: протоколи блокування та на основі позначок часу
Фіона Браун
⚡ Розумний підсумок
Контроль паралельності в СУБД керує одночасними транзакціями, щоб вони виконувалися точно, не порушуючи цілісність даних. Він запобігає аномаліям, таким як втрачені оновлення та «брудні» зчитування, використовуючи протоколи на основі блокувань, двофазних протоколів, протоколів на основі позначок часу та протоколів перевірки, що гарантують серіалізовані результати.
Що таке контроль паралельності?
Контроль паралельності У системі керування базами даних (СБД) це процедура для керування одночасними операціями без конфліктів між собою. Вона забезпечує одночасне та точне виконання транзакцій бази даних для отримання правильних результатів без порушення цілісності даних відповідної бази даних.
Одночасний доступ досить простий, якщо всі користувачі лише читають дані, оскільки вони ніяк не можуть перешкоджати один одному. Однак будь-яка практична база даних має поєднання операцій ЧИТАННЯ та ЗАПИСУ, тому паралельність стає проблемою.
Контроль паралельної роботи в СУБД використовується для вирішення таких конфліктів, які здебільшого виникають у багатокористувацькій системі. Тому контроль паралельної роботи є одним із найважливіших елементів для належного функціонування бази даних, де дві або більше транзакцій виконуються одночасно та потребують доступу до одних і тих самих даних. Він працює пліч-о-пліч із управління транзакціями, який визначає одиниці роботи, які керування паралельністю має безпечно чергувати.
Потенційні проблеми паралельності
Ось деякі проблеми, з якими ви, ймовірно, зіткнетеся без належного контролю паралельності СУБД:
- Втрачені оновлення виникають, коли кілька транзакцій вибирають один і той самий рядок та оновлюють його на основі вибраного значення.
- Незафіксована залежність (брудне читання) відбувається, коли друга транзакція вибирає рядок, який був оновлений іншою транзакцією, що ще не зафіксувала зміни.
- Неповторне читання відбувається, коли друга транзакція звертається до того самого рядка кілька разів і щоразу зчитує різні дані.
- Неправильний зведений опис відбувається, коли одна транзакція отримує підсумок за значенням усіх екземплярів повторюваного елемента даних, тоді як друга транзакція оновлює кілька з цих екземплярів. Отриманий підсумок не відображає правильний результат.
Навіщо використовувати метод паралельності?
Причини використання методу керування паралельністю в СУБД:
- Застосовувати ізоляцію шляхом взаємного виключення між конфліктуючими транзакціями.
- Щоб вирішити проблеми конфліктів читання-запису та запису-запису.
- Збереження узгодженості бази даних шляхом постійного застосування обмежень на виконання.
- Для контролю взаємодії між паралельними транзакціями, що досягається за допомогою схем контролю паралельності.
- Щоб забезпечити серіалізованість.
Приклад
Припустимо, що двоє людей одночасно звертаються до електронних кіосків, щоб купити квиток у кіно на той самий фільм і на той самий час сеансу.
Однак у кінотеатрі залишилося лише одне місце на цю виставу. Без контролю паралельності можливо, що обидва кіноглядачі зрештою придбають квиток. Контроль паралельності цього не дозволяє. Обидва кіноглядачі все ще можуть отримати доступ до інформації в базі даних місць у кінотеатрі, але контроль паралельності надає квиток лише покупцю, який першим завершить процес транзакції.
Протоколи керування паралелізмом
Різні протоколи керування паралельністю пропонують різні компроміси між дозволеним обсягом паралельності та накладними витратами. Основні методи керування паралельністю в СУБД:
- Протоколи на основі блокування
- Протокол двофазного блокування
- Протоколи на основі часових позначок
- Протоколи на основі перевірки
Кожен з них розглядається по черзі нижче, починаючи з найпоширеніших протоколів на основі блокувань.
Протоколи на основі блокування
Протоколи на основі блокувань У СУБД (системах управління базами даних) являють собою механізм, за якого транзакція не може читати або записувати елемент даних, доки не отримає відповідне блокування. Протоколи на основі блокування допомагають усунути проблему паралельності, блокуючи або ізолюючи певний елемент даних для однієї транзакції.
Блокування — це змінна даних, пов'язана з елементом даних, яка вказує, які операції можна над ним виконувати. Блокування допомагають синхронізувати доступ до елементів бази даних за допомогою одночасних транзакцій. Усі запити на блокування надсилаються до менеджера керування паралельністю, а транзакції виконуються лише після задоволення запиту на блокування.
Двійкові блокування: Бінарний замок на елементі даних може бути як у заблокованому, так і в розблокованому стані.
Спільне/Ексклюзивне: Цей механізм блокування розділяє блокування залежно від їх використання. Якщо блокування отримується для виконання операції запису, воно називається ексклюзивним блокуванням.
1. Спільний замок (S): Спільне блокування також називається блокуванням лише для читання. За допомогою спільного блокування елемент даних може бути спільним для транзакцій, оскільки жодна з них не має дозволу на оновлення елемента. Наприклад, якщо дві транзакції зчитують баланс рахунку особи, база даних дозволяє їм читати, встановивши спільне блокування. Якщо інша транзакція хоче оновити цей баланс, спільне блокування запобігає цьому, доки читання не завершиться.
2. Ексклюзивний замок (X): За допомогою ексклюзивного блокування елемент даних можна як зчитувати, так і записувати. Воно є ексклюзивним і не може зберігатися одночасно на одному й тому ж елементі даних. X-блокування запитується за допомогою інструкції lock-x. Наприклад, коли транзакції потрібно оновити баланс рахунку, це дозволяється шляхом встановлення X-блокування; тоді друга транзакція, яка хоче зчитувати або записувати, забороняється.
3. Протокол спрощеного блокування: Це дозволяє транзакціям отримати блокування на кожному об'єкті перед початком операції. Транзакції можуть розблокувати елемент даних після завершення операції запису.
4. Блокування перед поданням заяви: Цей протокол оцінює операції та створює список елементів даних, необхідних для початку виконання. Коли всі блокування надано, транзакція виконується, і всі блокування знімаються після завершення її операцій.
голодування: Голодування — це ситуація, коли транзакція очікує блокування протягом невизначеного періоду. Причини включають погано керовану схему очікування для заблокованих елементів, витік ресурсів або повторний вибір однієї й тієї ж транзакції як жертви.
Безвихідь: Взаємоблокування — це ситуація, коли два або більше процесів чекають один на одного, поки вони звільнять ресурс, утворюючи циклічний ланцюг.
Протокол двофазного блокування (2PL)
Команда Протокол двофазного блокування, також відомий як 2PL, — це метод керування паралельністю, який забезпечує серіалізованість шляхом застосування блокування до даних транзакцій, що блокує інші транзакції від одночасного доступу до тих самих даних.
Протокол двофазного блокування дозволяє кожній транзакції робити запит на блокування або розблокування у два кроки:
- Фаза вирощування: На цьому етапі транзакція може отримати блокування, але не звільнити жодне.
- Фаза скорочення: На цьому етапі транзакція може звільнити блокування, але не отримати нове блокування.
Це правда, що 2PL пропонує серіалізованість. Однак це не гарантує відсутності блокувань. На діаграмі вище локальні та глобальні детектори блокувань шукають блокування та вирішують їх, відновлюючи транзакції до їх початкових станів.
Суворий двофазний метод блокування
Strict 2PL майже такий самий, як і 2PL. Єдина відмінність полягає в тому, що Strict-2PL ніколи не знімає блокування після його використання. Він утримує всі блокування до точки фіксації (commit) і знімає їх усі одночасно, коли процес завершено.
Централізована 2ПЛ
У централізованій 2PL-системі за процес керування блокуваннями відповідає один сайт. Він має лише одного менеджера блокувань для всієї СУБД.
Первинна копія 2PL
У механізмі первинної копії 2PL багато менеджерів блокувань розподілені по різних сайтах, і певний менеджер блокувань відповідає за керування блокуванням для набору елементів даних. Коли первинна копія оновлюється, зміни поширюються на підлеглі пристрої.
Роздано 2ПЛ
У цьому механізмі менеджери блокувань розподілені по всіх сайтах і відповідають за керування блокуваннями даних на цьому сайті. Якщо дані не реплікуються, це еквівалентно первинній копії 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.
- Немає потреби чекати на транзакцію, що виключає можливість блокування.
Недоліки: Голодування можливе, якщо одну й ту саму транзакцію перезапускають і постійно переривають.
Протокол на основі валідації
Команда Протокол на основі валідації У СУБД, також відомий як метод оптимістичного керування паралельністю, — це метод уникнення конфліктів паралельності в транзакціях. У цьому протоколі оновлюються локальні копії даних транзакцій, а не самі дані, що призводить до меншого перешкод під час виконання.
Протокол на основі валідації виконується у три етапи:
- Прочитайте фазу
- Етап перевірки
- Напишіть фазу
Прочитайте фазу
На етапі читання значення даних можуть бути прочитані транзакцією, але операції запису або оновлення застосовуються лише до локальних копій даних, а не до фактичної бази даних.
Етап перевірки
На етапі перевірки дані перевіряються, щоб переконатися, що застосування оновлень не порушить серіалізованість.
Напишіть фазу
На етапі запису оновлення застосовуються до бази даних, якщо перевірка пройшла успішно; в іншому випадку оновлення відкидаються, а транзакція скасовується.
Порівняння протоколів керування паралельністю
Чотири сімейства протоколів по-різному впливають на частоту конфліктів транзакцій. У таблиці нижче підсумовано, де кожне з них відповідає своєму призначенню.
| протокол | Підхід | Deadlock | Найкраще, коли |
|---|---|---|---|
| На основі блокування | Песимістично, блокування перед доступом | це можливо | Конфлікти трапляються часто |
| Двофазне блокування | Песимістична, зростаюча та скорочувальна фази | це можливо | Серіалізовність обов'язкова |
| На основі позначок часу | Замовлення за міткою часу | Без глухих кутів | Замовлення має значення, очікування дорого коштує |
| На основі валідації | Оптимістично, перевірте перед написанням | Без глухих кутів | Конфлікти трапляються рідко |
Коротше кажучи, протоколи на основі блокувань та 2PL припускають, що конфлікт є поширеним явищем і запобігають йому заздалегідь, тоді як протоколи часових позначок та перевірки припускають, що конфлікт є рідкісним явищем і вирішують його лише тоді, коли він виникає.
Характеристики хорошого протоколу паралельного доступу
Ідеальний механізм керування паралельністю має такі цілі:
- Він має бути стійким до збоїв на сайті та в комунікації.
- Це дозволяє паралельно виконувати транзакції для досягнення максимального паралелізму.
- Його механізми зберігання та обчислювальні методи повинні бути скромними, щоб мінімізувати накладні витрати.
- Він повинен запроваджувати деякі обмеження на структуру атомарних дій транзакцій.
