|
БАЗИ ДАНИХ. МОВИ ЗАПИТІВ, УПРАВЛІННЯ ТРАНЗАКЦІЯМИ, РОЗПОДІЛЕНА ОБРОБКА ДАНИХ |
|
2.5 Методи управління паралельним доступом
2.5.1 Методи блокувань
На практиці графіки в СКБД не перевіряються на впорядкованість. Замість цього використовуються спеціальні методи управління паралельним доступом: метод блокувань та метод часових відміток. Вище згадані методи відносять до консервативних (або песимістичних) підходів, оскільки вони відкладають виконання транзакцій, здатних в майбутньому в той чи інший момент часу вступити в конфлікт з іншими транзакціями.
Коли деяка транзакція отримує доступ до бази даних, механізм блокувань дозволяє заборонити спроби отримання доступу до цих же даних зі сторони інших транзакцій. Існує декілька варіантів цього механізму, однак всі вони побудовані на фундаментальному принципі: транзакція повинна затребувати виконати блокування для читання (поділюване) або для запису (виключне) деякого елемента даних до того, як вона зможе виконати в базі даних відповідну операцію читання чи запису. Блокування може бути виконане для елементів будь-якого розміру: від бази даних в цілому до окремого поля конкретного запису. Якщо в транзакції встановлене поділюване блокування елемента даних, то в ній може виконуватись лише читання цього елемента даних, але не його оновлення. Якщо в транзакції встановлене виключне блокування елемента даних, то в ній може виконуватись і читання цього елемента даних, і його оновлення. Оскільки поділювані блокування не можуть стати причиною конфлікту, допускається встановлювати поділювані блокування для одного і того ж елемента даних одночасно зі сторони декількох транзакцій. Виключне блокування можна встановити лише в одній транзакції. Встановлення блокувань відбувається за такими правилами. 1. Будь-яка транзакція, якій необхідно отримати доступ до елемента даних, повинна спочатку виконати блокування (поділюване або виключне). 2. Якщо елемент ще не заблокований іншою транзакцією , блокування елемента буде виконано успішно. 3. Якщо елемент даних в поточний момент вже заблокований, СКБД проаналізує, чи є сумісним тип отриманого запиту с типом вже існуючого блокування. У випадку поділюваного блокування запит на надання блокування виконається успішно. Інакше, транзакція переходить в стан очікування, який буде продовжуватись до тих пір, поки існуюче блокування не буде знято. 4. Транзакція повинна утримувати блокування елемента даних до тих пір, поки явним чином не вивільнить його або в ході свого виконання, або по завершенню (успішному чи неуспішному). 5. Лише після того, як з елемента даних буде знято виключне блокування, результати виконання операції запису стануть доступними для інших транзакцій. Окрім цих правил, в деяких системах транзакціям дозволяється встановлювати поділюване блокування на деякому елементі даних, а потім підвищувати рівень цього блокування до виключного. В такому випадку спочатку слід оцінити стан оброблюваних в транзакції даних, а потім прийняти рішення чи потрібно їх змінювати. В деяких системах навпаки, дозволено понижувати рівень блокування з виключного до поділюваного. Для забезпечення впорядкованості слід застосовувати додатковий протокол, який визначає моменти встановлення і зняття блокувань для кожної транзакції. Найбільш популярним є протокол двофазного блокування (2PL). Транзакція виконується по протоколу двофазного блокування, якщо в ній всі операції блокування передують першій операції розблокування. Відповідно до протоколу двофазного блокування кожна транзакція може бути розбита на дві фази: - фазу розширення, в якій встановлюються всі необхідні блокування і не вивільняється жодна з них; - фазу звуження, в якій вивільняються всі раніше встановлені блокування і не встановлюється жодне нове блокування. При цьому зовсім не обов’язково, щоб всі блокування були встановлені одночасно. Як правило, транзакція встановлює деякі блокування, виконує певну обробку, після чого знову може зажадати встановлення додаткових блокувань. Однак не може звільнити жодне з блокувань, поки не досягне стадії виконання, на якій встановлення нових блокувань вже не потрібне. Інший варіант протокола 2PL – обмежений протокол двофазного блокування – передбачає призупинення до кінця транзакції вивільнення тільки виключних блокувань. В більшості СКБД використовується один з двох варіантів протокола 2PL.
2.5.2 Методи обробки взаємоблокувань
Використання методів блокувань може призвести до проблеми, що носить назву взаємоблокування, яка є наслідком того факту, що будь-яка транзакція може бути переведена в стан очікування до вивільнення необхідного їй елемента даних. Якщо дві транзакції будуть очікувати вивільнення елементів, заблокованих другою транзакцією з цієї ж пари, то виникне стан взаємоблокування. Жодна з транзакцій не може продовжити свою роботу, оскільки кожна очікує завершення роботи іншої. Крім того, транзакції можуть також входити в стан активного взаємоблокування , при якому вони залишаються в стані очікування невизначено довгий час і не мають можливості встановлювати будь-які нові блокування. Ця ситуація можлива у випадках, коли алгоритм переведення транзакцій в стан очікування не надає рівні можливості всім транзакціям і не враховує час, проведений транзакціями у стані очікування. Для подолання активного взаємоблокування може використовуватись система пріоритетів, в якій пріоритет транзакції тим вище, чим довше вона знаходиться в стані очікування. Відповідальність за виявлення взаємоблокувань і усунення цієї проблеми повинна бути покладена на СКБД. На жаль, існує лише один спосіб подолати стан взаємоблокувань: виконання однієї або декількох транзакцій повинно бути відмінено, що супроводжується відкатом усіх змін, внесених відміненими транзакціями. Оскільки ситуація взаємоблокування повинна бути абсолютно прозорою для користувача, СКБД зобов’язана автоматично перезапустити всі відмінені нею транзакції. Найбільш поширеними є три методи обробки зваємоблокувань: 1. Установка тайм-аутів 2. Попередження взаємоблокувань. 3. Виявлення взаємоблокувань і відновлення нормальної роботи.
Установка тайм-аутів. Це найпростіший спосіб усунення взаємоблокувань, при якому транзакція, яка запитує блокування, може очікувати його отримання протягом певного періоду часу, встановленого в системі. Якщо протягом цього часу блокування не надається, відбувається відміна запиту на блокування по тайм-ауту. В такому випадку СКБД припускає, що дана транзакція могла виявитись у стані взаємоблокування, навіть якщо це не відповідає дійсності, тому ініціює аварійне завершення і автоматичний перезапуск транзакції.
Попередження взаємоблокувань – підхід, що базується на впорядкуванні транзакцій з використанням часових відміток. Кожна транзакція позначається відміткою часу її початку, яка повинна бути унікальною. Якщо деяка транзакція А запитує блокування елемента даних, який вже заблоковано транзакцією В, то може виконуватись один із двох можливих алгоритмів: - „Очікування-відміна”. При такому підході лише більш старі транзакції очікують завершення більш нових. Якщо виконання транзакції А почалось раніше, ніж транзакції В, то транзакція А переходить в стан очікування; в протилежному випадку відбувається її відміна. Це означає, що відбувається відкат і перезапуск транзакції А. - „Відміна-очікування”. При такому підході лише більш нові транзакції очікують завершення більш старих. Якщо виконання транзакції А почалось пізніше, ніж транзакції В, то транзакція А переходить в стан очікування; в протилежному випадку відбувається відміна транзакції В, тобто відбувається відкат і перезапуск транзакції В. Якщо транзакція має бути перезапущена, то їй після запуску присвоюється її початкова відмітка часу. Використання будь-якого з розглянутих алгоритмів гарантує, що ситуація взаємоблокування не виникне взагалі, і жодна з транзакцій не буде перезапускатись безкінечну кількість разів. Основним недоліком такого підходу є те, що необхідно виконувати досить багато відкатів транзакцій.
Виявлення взаємоблокувань і відновлення нормальної роботи. Виявлення взаємоблокувань, як правило, виконують за допомогою графа очікування, який відображає залежність транзакцій одна від одної. Транзакція Ті вважається залежною від транзакції Тj у тому випадку, якщо транзакція Тj заблокувала елемент даних, необхідний для продовження роботи транзакції Ті. При побудові графа створюється направлене ребро Ті->Tj, якщо тпранзакція Ті очікує вивільнення елемента даних, заблокованого в поточний момент часу транзакцією Тj. Взаємо блокування має місце лише в тому випадку, коли граф очікування містить цикл. Перевірка на наявність циклів у графі очікування проводиться через регулярні проміжки часу. Якщо встановлений проміжок часу буде занадто коротким, то виявлення взаємоблокувань буде потребувати значних додаткових витрат часу та ресурсів. При занадто довгих проміжках часу існує ризик того, що взаємоблокування довго не будуть помічені. Компромісним рішенням є динамічний алгоритм виявлення взаємоблокувань, при якому встановлюється деяке початкове значення проміжку часу. Після кожного сеансу виконання алгоритму контролюється наявність виявленого взаємоблокування. Якщо взаємоблокування не виявлене, то проміжок часу може бути збільшений, наприклад вдвічі, порівняно з початковим значенням. В протилежному випадку, проміжок часу скорочують наполовину. Після того як СКБД виявила взаємоблокування необхідно виконати аварійне завершення однієї або декількох транзакцій. Для цього необхідно вирішити декілька задач. 1. Вибрати транзакції, які підлягають відміні в результаті взаємоблокування. Як правило, слід обирати ті транзакції, відміна яких потребує мінімальних витрат. При цьому враховують такі фактори: - тривалість виконання транзакції (може виявитись більш доцільним аварійне завершення транзакції, яка була щойно розпочата, а не та транзакція, яка вже виконувалась протягом деякого часу); - кількість елементів даних, які оновлюються в транзакції (може виявитись доцільнішим аварійно завершити з декількох транзакцій ту, яка внесла менше змін в базу даних); - кількість елементів даних, які все ще підлягають оновленню в транзакції (доцільніше відмінити ту трансакцію, яка передбачає внесення більших змін у базу даних, ніж ту, для завершення якої необхідно внести невелику кількість змін). На жаль, такі відомості не завжди містяться в СКБД. 2. Визначити ступінь відкату транзакції. Найпростішим рішенням є відміна всіх змін, внесених транзакцією. Однак для усунення взаємо блокування іноді достатньо відмінити лише частину змін. 3. Попередити виникнення ситуацію виснаження ресурсів. Виснаження ресурсів виникає, коли для відміни завжди обирається одна і та ж транзакція, тому її так і не вдається виконати. В СКБД можна уникнути ситуації виснаження ресурсів шляхом реєстрації кількості таких випадків, коли для відміни була вибрана певна транзакція, і переходу до застосування іншого критерію відбору після досягнення деякої верхньої межі кількості випадків відміни. Враховуючи складність методу, його використання обмежене.
2.5.3 Методи управління паралельним доступом з використанням часових відміток
Методи управління паралельним доступом, які використовують часові відмітки, не потребують застосування будь-яких блокувань і не передбачають переведення транзакцій в стан очікування. Транзакції, які потрапити в конфліктну ситуацію, просто відміняються, а потім запускаються на виконання знову. Часова відмітка – це унікальний ідентифікатор, який створюється СКБД з метою визначення відносного моменту часу запуску транзакції. Часова відмітка може бути створена з використанням системного годинника для фіксації моменту часу запуску транзакції або шляхом збільшення значення деякого логічного лічильника при кожному запуску чергової транзакції. Метод з використанням часових відміток – це протокол управління паралельним виконанням, основна мета якого полягає у встановленні глобальної черговості виконання транзакцій, при якій більш старі транзакції (транзакції з меншим значенням часової відмітки) мають більш високий пріоритет при вирішенні конфліктних ситуацій. Якщо транзакція чинить спробу читання чи запису елемента даних, то ці операції виконуються тільки в тому випадку, якщо останнє оновлення затребуваного елемента даних було виконано більш старою транзакцією. В протилежному випадку, транзакція, що запросила операцію читання/запису, відміняється і пере запускається знову з присвоєнням їй нової часової відмітки. Нова часова відмітка повинна бути присвоєна перезапущеній транзакції для того, щоб попередити її потраплянні в цикл постійної відміни та перезапуску. Без отримання нової часової відмітки транзакція з більш старою часовою відміткою не зможе завершити свою роботу шляхом фіксації, оскільки більш нова транзакція вже встигла зафіксувати свої результати в базі даних. Окрім часових відміток для транзакції в системі повинні використовуватись часові відмітки для елементів даних. Кожний елемент даних повинен мати часову відмітку читання, яка містить часову відмітку останньої транзакції, що виконала його читання, та часову відмітку запису, яка містить часову відмітку останньої транзакції, що оновила вміст цього елемента даних.
2.5.4 Оптимістичні методи впорядкування транзакцій
На противагу песимістичним, оптимістичні підходи будуються на припущенні, що ймовірність конфлікту не висока, тому вони допускають асинхронне виконання транзакцій, а перевірка на наявність конфлікту відкладається на момент їх завершення та фіксації в базі даних. У випадку виявлення конфліктної ситуації, відбувається відкат транзакції та її повторний запуск. Застосування такої схеми доцільно лише у випадку, коли відкати транзакцій будуть відбуватись досить рідко. Такі методи дозволяють досягти більш високого рівня розпаралелення порівняно з традиційними протоколами, оскільки вони не потребують виконання механізму блокувань. Оптимістичний протокол управління паралельним виконанням включає дві або три стадії, в залежності від того, яка операція виконується в даній транзакції – читання чи запису. Стадія читання охоплює період від початку транзакції і до моменту, що передує фіксації результатів. Транзакція зчитує з бази даних значення всіх необхідних їй елементів даних і поміщає їх в локальні змінні. Будь-які оновлення застосовуються лише до локальної копії даних, а не до інформації, що зберігається в базі даних. Стадія перевірки наступає за стадією читання. Виконуються перевірки, необхідні для отримання гарантії відсутності порушення впорядковуваності у випадку переносу в базу даних змін, виконаних транзакцією. Для транзакцій, що включають тільки операції читання, перевірка полягає в підтвердженні того, що використані транзакцією значення все ще залишаються актуальними значеннями відповідних елементів даних. Якщо порушень не виявлено, транзакція завершує своє виконання шляхом фіксації. Якщо знайдені змінені значення, транзакція відміняється та перезапускається. Якщо в транзакції виконувалось оновлення даних, то перевірка включає виконання контролю за тим, чи збережеться база даних в узгодженому стані після внесення в неї результатів даної транзакції, а також чи не будуть порушені умови впрорядковуваності. У випадку виявлення помилки транзакція відміняється і пере запускається. Стадія запису виконується після успішного завершення стадії перевірки, але тільки у випадку транзакцій, що включають операції оновлення. На цій стадії всі зміни, внесені в локальні копії даних, переносять у базу даних. Хоча застосування оптимістичних методів досить ефективне у випадку незначної кількості конфліктів у системі, вони можуть викликати відкат окремих транзакцій. Оскільки відкат стосується лише локальних копій даних, виникнення каскадного відкату виключається. Якщо відкати виникають досить часто, це може вказувати на те, що оптимістичні методи не зовсім підходять для управління паралельним виконанням в конкретній системі.
|
|
Пєтух А.М., Романюк О.В., Романюк О.Н. ВНТУ 2016 |