Лекція № 12 Методи серіалізації транзакцій. – 2 год Серіалізація транзакцій. Розв'язання проблем транзакцій за допомогою блокування. Синхронізаційні захоплення Гранульовані синхронізаційні захоплення (навмисні блокування). Предикатні синхронізаційні захоплення (предикатні блокування) Проблеми сумісності блокувань Тупики, їх розпізнавання та руйнування Метод часових міток Двофазне блокування. Теорема Есварана про серіалізованість (Пушніков, гл. 10). Розв'язання проблем транзакцій за допомогою ізольованості користувачів. Засоби SQL управління транзакціями 1. Серіалізація транзакцій. Розв'язання проблем транзакцій за допомогою блокування (захоплення) Як вже говорилося, є два способи розв'язати конкуренцію між надходячими в довільні моменти транзакціями: "Пригальмовувати" деякі з що надходять транзакцій настільки, наскільки це необхідно для забезпечення правильності суміші транзакцій у кожен момент часу (тобто забезпечити, щоб конкуруючі транзакції виконувалися в різний час). Надати конкуруючим транзакціям "різні" екземпляри даних (тобто забезпечити, щоб конкуруючі транзакції працювали з різними версіями даними). Перший метод - "пригальмовування" транзакцій - реалізується шляхом використанням блокувань різних видів чи методу часових міток. Другий метод - надання різних версій даних - реалізується шляхом використанням даних з журналу транзакцій. 1.1. Блокування. Синхронізаційні захоплення Основна ідея блокувань, які ще називають синхронізаційними захопленнями, полягає в тому, що якщо для виконання певної транзакції необхідно, щоб деякий об'єкт не змінювався без відома цієї транзакції, то цей об'єкт повинен бути заблокований, тобто доступ до цього об'єкта з боку інших транзакцій обмежується на час виконання транзакції, що викликала блокування. Реалізація блокувань заснована на дотриманні двухфазного протоколу синхронізаційних захоплень об'єктів БД. Загалом протокол полягає в тому, що перед виконанням будь-якої операції в транзакції T над об'єктом бази даних r від імені транзакції T заппрошується синхронизаційне захоплення об'єкта r у відповідному режимі (у залежності від виду операції). Розрізняють два типи блокувань (захоплень): Монопольні блокування (X-блокування, X-locks - eXclusive locks) - блокування без взаємного доступу (блокування запису). Поділювані блокування (S-блокування, S-locks - Shared locks) - блокування з взаємним доступом (блокування читання). Якщо транзакція A блокує об'єкт за допомогою X-блокування, то всякий доступ до цього об'єкта з боку інших транзакцій відхиляється. Якщо транзакція A блокує об'єкт за допомогою S-блокування, то запити з боку інших транзакцій на X-блокування цього об'єкта будуть відкинуті, запити з боку інших транзакцій на S-блокування цього об'єкта будуть прийняті. Транзакція, що запросила доступ до об'єкта, уже захопленого іншою транзакцією в несумісному режимі, зупиняється доти, доки захоплення цього об'єкта не буде зняте. Правила взаємного доступу до заблокованих об'єктів можна представити у вигляді наступної матриці сумісності блокувань. Якщо транзакція A наклала блокування на деякий об'єкт, а транзакція B після цього намагається накласти блокування на цей же об'єкт, то успішність блокування транзакцією B об'єкта описується таблицею: Транзакція B намагається накласти блокування:
Транзакція A наклала блокування: S-блокування X-блокування
S-блокування Так НІ(КонфліктR-W)
X-блокування НІ (КонфліктW-R) НІ(КонфліктW-W)
Таблиця 1 Матриця сумісності S- і X-блокувань Три випадки, коли транзакція B не може блокувати об'єкт, відповідають трьом видам конфліктів між транзакціями. Доступ до об'єктів бази даних на читання і запис повинен здійснюватися у відповідності з наступним протоколом доступу до даних: Перш ніж прочитати об'єкт, транзакція повинна накласти на цей об'єкт S-блокування. Перш ніж обновити об'єкт, транзакція повинна накласти на цей об'єкт X-блокування. Якщо транзакція вже заблокувала об'єкт S-блокуванням (для читання), то перед оновленням об'єкта S-блокування повинне бути замінене X-блокуванням. Якщо блокування об'єкта транзакцією B відхиляється тому, що об'єкт уже заблокований транзакцією A, то транзакція B переходить у стан чекання. Транзакція B буде знаходитися в стані чекання доти, поки транзакція A не зніме блокування об'єкта. X-блокування, накладені транзакцією A, зберігаються до кінця транзакції A. Доведено, що серіалізованість транзакцій (чи, інакше, їхня ізоляція) забезпечується при використанні двофазного протоколу блокувань (2LP - Two-Phase Locks), відповідно до якого всі блокування, зроблені транзакцією, знімаються тільки при її завершенні. Тобто виконання транзакції розбивається на дві фази: - нагромадження блокувань, (2) - звільнення блокувань у результаті фіксації чи відкату. На жаль, застосування механізму блокування приводить до уповільнення обробки транзакцій, оскільки система змушена очікувати, поки звільняться дані, захоплені конкуруючої транзакцією. Вирішити цю проблему можна за рахунок зменшення фрагментів даних, захоплюваних транзакцією. У залежності від захоплюваних об'єктів розрізняють кілька рівнів блокування: блокується вся база даних - очевидно, цей варіант непридатний, оскільки зводить багатокористувацький режим роботи до однокористувальницького блокуються окремі таблиці блокуються сторінки (сторінка - фрагмент таблиці розміром звичайно 2-4 Кб, одиниця виділення пам'яті для обробки даних системою) блокуються записи блокуються окремі поля Сучасні СУБД, як правило, можуть здійснювати блокування на рівні записів чи сторінок. Мова SQL також надає спосіб непрямого управління швидкістю виконання транзакцій за допомогою вказування рівня ізоляції транзакції. Під рівнем ізоляції транзакції розуміється можливість виникнення однієї з описаних вище помилкових ситуацій. У стандарті SQL визначені 4 рівні ізоляції: Рівень ізоляції Брудне читання Розмите читання Фантом
Незафіксоване читання(READ UNCOMMITTED) можливо можливо можливо
Зафіксоване читання(READ COMMITED) неможливо можливо можливо
Повторюване читання(REPEATABLE READ) неможливо неможливо можливо
Серіалізованість(SERIALIZABLE) неможливо неможливо неможливо
Для визначення характеристик транзакції використовується оператор SET TRANSACTION <режим_доступу>, <рівень_ізоляції> Список рівнів ізоляції приведений у таблиці. Режим доступу за замовчуванням використовується READ WRITE (читання запис), якщо заданий рівень ізоляції READ UNCOMMITED, те режим доступу повинен бути READ ONLY (тільки читання). 1.2. Навмисні блокування (гранульовані синхронізаційні захоплення) Як видно з аналізу поводження транзакцій, при використанні протоколу доступу до даних не вирішується проблема фантомів. Це відбувається тому, що були розглянуті тільки блокування на рівні рядків. Можна розглядати блокування й інших об'єктів бази даних: Блокування самої бази даних. Блокування файлів бази даних. Блокування таблиць бази даних. Блокування сторінок (Одиниць обміну з диском, звичайно 2-16 Кб. На одній сторінці міститься кілька рядків однієї чи кількох таблиць). Блокування окремих рядків таблиць. Блокування окремих полів. Крім того, можна блокувати індекси, заголовки таблиць чи інші об'єкти. Чим крупніше об'єкт блокування, тим менше можливостей для рівнобіжної роботи. Перевагою блокувань великих об'єктів є зменшення накладних витрат системи і вирішення проблем, не розв'язуваних з використанням блокувань менш великих об'єктів. Наприклад, використання монопольного блокування на рівні таблиці, мабуть, вирішує проблему фантомів. Сучасні СУБД, як правило, підтримують мінімальний рівень блокування на рівні рядків чи сторінок. (У старих версіях настільної СУБД Paradox підтримувалося блокування на рівні окремих полів.). При использовании блокировок объектов разной величины возникает проблема обнаружения уже наложенных блокировок. Якщо транзакція A намагається заблокувати таблицю, то необхідно мати інформацію, чи не накладені вже блокування на рівні рядків цієї таблиці, несумісні з блокуванням таблиці. Для вирішення цієї проблеми використовується протокол навмисних блокувань, що є розширенням протоколу доступу до даних. Навмисні блокування деколи ще називають гранульованими захопленнями. Суть цього протоколу в тому, що перед тим, як накласти блокування на об'єкт (наприклад, на рядок таблиці), необхідно накласти спеціальне навмисне блокування (блокування наміру) на об'єкти, до складу яких входить блокований об'єкт - на таблицю, що містить рядок, на файл, що містить таблицю, на базу даних, що містить файл. Тоді наявність навмисного блокування таблиці буде свідчити про наявність блокування рядків таблиці і для іншої транзакції, що намагається блокувати цілу таблицю не потрібно перевіряти наявність блокувань окремих рядків. Більш точно, уводяться наступні нові типи блокувань: Навмисне блокування з можливістю взаємного доступу (IS-блокування - Intent Shared lock). Накладається на деякий складений об'єкт T і означає намір блокувати певний вхідний у T об'єкт у режимі S-блокування. Наприклад, при намірі читати рядки з таблиці T, ця таблиця повинна бути заблокована в режимі IS (до цього в такому ж режимі повинен бути заблокований файл). Навмисне блокування без взаємного доступу (IX-блокування - Intent eXclusive lock). Накладається на деякий складений об'єкт T і означає намір блокувати певний вхідний у T об'єкт у режимі X-блокування. Наприклад, при намірі видаляти чи модифікувати рядки з таблиці T ця таблиця повинна бути заблокована в режимі IX (до цього в такому ж режимі повинен бути заблокований файл). Навмисне блокування як з можливістю взаємного доступу, так і без нього (SIX-блокування - Shared Intent eXclusive lock). Накладається на деякий складений об'єкт T і означає поділюване блокування всього цього об'єкта з наміром згодом блокувати які-небудь вхідні в нього об'єкти в режимі X-блокувань. Наприклад, якщо виконується довга операція перегляду таблиці з можливістю видалення деяких рядків, що переглядаються, то можна заблокувати цю таблицю в режимі SIX (до цього захопити файл у режимі IS). IS, IX і SIX-блокування повинні накладатися на складні об'єкти бази даних (таблиці, файли). Крім того, на складні об'єкти можуть накладатися і блокування типів S і X. Для складних об'єктів (наприклад, для таблиці бази даних) таблиця сумісності блокувань має наступний вигляд Транзакція B намагається накласти на таблицю блокування:
Транзакція A наклала на таблицю блокування: IS S IX SIX X
IS Так Так Так Так Ні
S Так Так Ні Ні Ні
IX Так Нет Так Ні Ні
SIX Так Ні Ні Ні Ні
X Ні Ні Ні Ні Ні
Таблиця 2 Розширена таблиця сумісності блокувань Більш точне формулювання протоколу навмисних блокувань для доступу до даних виглядає в такий спосіб: При завданні X-блокування для складного об'єкта неявним образом задається X-блокування для всіх дочірніх об'єктів цього об'єкта. При завданні S- чи SIX-блокування для складного об'єкта неявним образом задається S-блокування для всіх дочірніх об'єктів цього об'єкта. Перш ніж транзакція накладе S- чи IS-блокування на заданий об'єкт, вона повинна задати IS-блокування (чи більш сильне) принаймні для одного батьківського об'єкта цього об'єкта. Перш ніж транзакція накладе X-, IX- чи SIX-блокування на заданий об'єкт, вона повинна задати IX-блокування (чи більш сильне) для всіх батьківських об'єктів цього об'єкта. Перш ніж для даної транзакції буде скасоване блокування для даного об'єкта, повинні бути скасовані всі блокування для дочірніх об'єктів цього об'єкта. Поняття відносної сили блокувань можна описати за допомогою наступної діаграми пріоритету (зверху - більш сильні блокування, знизу - більш слабкі):
Таблиця 3 Діаграма пріоритету блокувань Протокол навмисних блокувань не визначає однозначно, які блокування повинні бути накладені на батьківський об'єкт при блокуванні дочірнього об'єкта. Наприклад, при намірі задати S-блокування рядка таблиці, на таблицю, що включає цей рядок, можна накласти кожну з блокувань типу IS, S, IX, SIX, X. При намірі задати X-блокування рядка, на таблицю можна накласти кожну з блокувань типу IX, SIX, X. Оскільки транзакція A збирається тільки читати рядки таблиці, то мінімально необхідною умовою відповідно до протоколу навмисних блокувань є навмисне IS-блокування таблиці. Однак цей тип блокування не запобігає появі фантомів. Проблема фіктивних елементів (фантомів) зважується, якщо транзакція A використовує навмисне S-блокування чи більш сильне. Таким чином, транзакцію A можна запускати з різними рівнями ізольованості - запобігаючи чи допускаючи появу фантомів. Причому, обидва способи запуску відповідають протоколу навмисних блокувань для доступу до даних. 1.3. Предикатні блокування (предикатні синхронізаційні захоплення) Іншим способом блокування є блокування не об'єктів бази даних, а умов, яким можуть задовольняти об'єкти. Такі блокування називаються предикатними блокуваннями, або предикатними синхронізаційними захопленнями. Оскільки будь-яка операція над реляційною базою даних задається певною умовою (тобто в ній указується не конкретний набір об'єктів бази даних, над якими потрібно виконати операцію, а умова, якій повинні задовольняти об'єкти цього набору), то зручним способом було б S чи X-блокування саме цієї умови. Однак при спробі використовувати цей метод у реальній СУБД виникають труднощі визначення сумісності різних умов. Дійсно, у мові SQL допускаються умови з підзапитами й іншими складними предикатами. Проблема сумісності порівняно легко зважується для випадку простих умов, що мають вигляд: {Ім'я атрибута {= | <> | > | >= | < | <=} Значення} [{OR | AND} {Ім'я атрибута {= | <> | > | >= | < | <=} Значення}.,..] Проблема фіктивних елементів (фантомів) легко вирішується з використанням предикатних блокувань, тому що друга транзакція не може вставити нові рядки, що задовольняють уже заблокованій умові. Блокування всієї таблиці в якому-небудь режимі фактично є предикатне блокування, тому що кожна таблиця має предикат, що визначає, які рядки містяться в таблиці і блокування таблиці є блокування предиката цієї таблиці. 1.4. Виникнення і руйнування тупиків При використанні протоколу доступу до даних з використанням блокувань знялася (рішилася) частина проблем (читання "брудних" даних, неакуратне зчитування, проблема незафіксованої залежності, неповторювальне зчитування), не розв'язалася проблема появи фіктивних елементів і виникла нова проблема – тупики – при спробі вирішення проблем утрати результатів оновлення і несумісного аналізу Можливість виникнення тупиків (dead locks) між транзакціями є одним з найбільш серйозних недоліків методу серіалізації транзакцій на основі механізму блокувань. Тупики можливі при застосуванні кожного з розглянутих нами варіантів. Нехай, наприклад, транзакція Т1 наклала монопольне блокування на об'єкт О1 і претендує на доступ до об'єкта О2, що уже монопольно заблокований транзакцією Т2, що очікує доступу до об'єкта О1. У цьому випадку жодна з транзакцій продовжуватися не може, отже, блокування об'єктів О1 і О2 ніколи не будуть зняті. Інший приклад виникнення тупика між транзакціями T1 і T2: транзакції T1 і T2 установили монопольні захоплення об'єктів r1 і r2 відповідно; після цього T1 потрібно спільне захоплення r2, а T2 - спільне захоплення r1. Жодна з транзакцій не може продовжуватися, отже, монопольні захоплення не будуть зняті, а спільні - не будуть задоволені. Природного виходу з такої ситуації не існують, тому тупикові ситуації виявляються й усуваються штучно. При цьому СУБД відкочує одну з транзакцій, що потрапили в тупик ("жертвує" нею), що дає можливість продовжити виконання іншої транзакції. Загальний вигляд тупика (dead locks) наступний Транзакція A Час Транзакція B
Блокування об'єкта P1 - успішне t1 ….
…. t2 Блокування об'єкта P2 - успішне
Блокування об'єкта P2 - конфліктує із блокуванням, накладеним транзакцією B t3 …,
Як видно, ситуація тупика може виникати при наявності не менш двох транзакцій, кожна з який виконує не менш двох операцій. Насправді в тупику може брати участь багато транзакцій, що очікують один одного. Оскільки тупики можливі, і ніякого природного виходу з тупикової ситуації не існує, те ці ситуації необхідно виявляти, розпізнавати і штучно усувати. Методом вирішення тупикової ситуації є відкіт однієї з транзакцій (транзакції-жертви) так, щоб інші транзакції продовжили свою роботу. Після розв'язання тупика, транзакцію, обрану як жертву можна повторити заново. Можна представити два принципових підходи до виявлення тупикової ситуації і вибору транзакції-жертви: СУБД не стежить за виникненням тупиків. Транзакції самі приймають рішення, чи бути їм жертвою. За виникненням тупикової ситуації стежить сама СУБД, вона ж приймає рішення, який транзакцією пожертвувати. Перший підхід характерний для так званих настільних СУБД (FoxPro і т.п.). Цей метод є більш простим і не вимагає додаткових ресурсів системи. Для транзакцій задається час чекання (чи число спроб), протягом якого транзакція намагається установити потрібне блокування. Якщо за зазначений час (чи після зазначеного числа спроб) блокування не завершується успішно, то транзакція відкочується (чи генерується помилкова ситуація). За простоту цього методу доводиться платити тим, що транзакції-жертвы вибираються, узагалі говорячи, випадковим образом. У результаті через одне простий транзакції може відкотитися дуже дорога транзакція, на виконання якої уже витрачено багато часу і ресурсів системи. Другий спосіб характерний для промислових СУБД (ORACLE, MS SQL Server і т.п.). У цьому випадку система сама стежить за виникненням ситуації тупика, шляхом побудови (чи постійної підтримки) графа чекання транзакцій. Побудова (чи постійна підтримка) графа чекання транзакцій є основою виявлення тупикових ситуацій. Граф чекання транзакцій - це орієнтований двочастковий граф, у якому існує два типи вершин - вершини, що відповідають транзакціям, і вершини, що відповідають об'єктам захоплення. У цьому графі існує дуга, що веде з вершини-транзакції до вершини-об'єкта, якщо для цієї транзакції існує вдоволене захоплення об'єкта. У графі існує дуга з вершини-об'єкта до вершини-транзакції, якщо транзакція очікує задоволення захоплення об'єкта. Ситуація тупика виникає, якщо в графі чекання транзакцій є хоча б один цикл. Для розпізнавання тупика періодично провадиться побудова графа чекання транзакцій (як уже відзначалося, іноді граф чекання підтримується постійно), і в цьому графі шукаються цикли. Традиційною технікою (для який існує безліч різновидів) перебування циклів в орієнтованому графі є редукція графа: із графа чекання віддаляються всі дуги, що виходять з вершин-транзакцій, у які не входять дуги з вершин-об'єктів. (Це як би відповідає тій ситуації, що транзакції, що не очікують задоволення захоплень, успішно завершилися і звільнили захоплення). Для тих вершин-об'єктів, для яких не залишилося вхідних дуг, але існують вихідні, орієнтація вихідних дуг змінюється на протилежну (це моделює задоволення захоплень). Після цього знову спрацьовує перший крок і так доти, поки на першому кроці не припиниться видалення дуг. Якщо в графі залишилися дуги, то вони обов'язково утворять цикл. Якщо нам вдалося знайти цикл у графі чекання транзакцій, потрібно якимсь чином забезпечити можливість продовження роботи хоча б для частини транзакцій, що потрапили в тупик. Одну з транзакцій, що потрапили в цикл, необхідно відкотити, причому, система сама може вибрати цю транзакцію відповідно до деяких вартісних міркувань (наприклад, саму коротку, чи з мінімальним пріоритетом і т.п.). Тобто руйнування тупика починається з вибору в циклі транзакцій так називаної транзакції-жертви, тобто транзакції, що вирішено пожертвувати, щоб забезпечити можливість продовження роботи інших транзакцій. Критерієм вибору є вартість транзакції; жертвою вибирається найдешевша транзакція. Вартість транзакції визначається на основі багатофакторної оцінки, у яку з різними вагами входять час виконання, число накопичених захоплень, пріоритет. Після вибору транзакції-жертви виконується відкат цієї транзакції, що може носити повний чи частковий характер. При цьому, природно, звільняються захоплення і може бути продовжене виконання інших транзакцій. Таке насильницьке усунення тупикових ситуацій є порушенням принципу ізольованості користувачів, якого неможливо уникнути. У централізованих системах вартість побудови графа чекання порівняно невелике, але вона стає занадто великою у по-справжньому розподілених СУБД, у яких транзакції можуть виконуватися в різних вузлах мережі. Тому в таких системах звичайно використовуються інші методи серіалізації транзакцій. 2. Метод часових міток Альтернативний метод серіалізації транзакцій, що добре працює в умовах рідких конфліктів транзакцій і не потребує побудови графа чекання транзакцій заснований на використанні часових міток. Основна ідея методу полягає в наступному: якщо транзакція A почалася раніш транзакції B, те система забезпечує такий режим виконання, як якби A була цілком виконана до початку B. Для цього кожній транзакції T надається часова мітка t, що відповідає часу початку T. При виконанні операції над об'єктом r бази даних транзакція T позначає його своєю часовою міткою і типом операції ( читання чи зміна). Перед виконанням операції над об'єктом r транзакція B виконує наступні дії: Перевіряє, чи не закінчилася транзакція A, що позначила цей об'єкт. Якщо A закінчилася, B позначає об'єкт r своєю часовою міткою і виконує операцію. Якщо транзакція A не завершилася, то B перевіряє конфліктність операцій. Якщо операції неконфліктні, при об'єкті r залишається чи проставляється часова мітка з меншим значенням (більш рання), і транзакція B виконує свою операцію. Якщо операції B і A конфліктують, то якщо t(A) > t(B) (тобто транзакція A є "молодшою" за B), те транзакція A відкочується і, одержавши нову часову мітку, починається заново. Транзакція B продовжує роботу. Якщо ж t(A) < t(B) (A "старше" B), то транзакція B відкочується і, одержавши нову часову мітку, починається заново. Транзакція A продовжує роботу. У підсумку система забезпечує таку роботу, при якій при виникненні конфліктів завжди відкочується більш молода транзакція ( щопочалася пізніше). Очевидним недоліком методу часових міток є те, що може відкотитися більш дорога транзакція, що почалася пізніше більш дешевої. До інших недоліків методу часових міток відносяться потенційно більш часті відкоти транзакцій, чим у випадку використання блокувань. Це зв'язано з тим, що конфліктність транзакцій визначається більш грубо. 3. Механізм виділення версій даних Використання блокувань гарантує серіальність планів виконання суміші транзакцій за рахунок загального уповільнення роботи - конфліктуючі транзакції очікують, коли транзакція, яка першою заблокувала певний об'єкт, не звільнить його. Без блокувань не обійтися, якщо всі транзакції змінюють дані. Але якщо в суміші транзакцій присутні як транзакції, що змінюють дані, так і тільки читаючі дані, можна застосувати альтернативний механізм забезпечення серіальностіи, вільний від недоліків методу блокувань. Цей метод полягає в тому, що транзакціям, що читає дані, надається як би "своя" версія даних, що була в момент початку читаючої транзакції. При цьому транзакція не накладає блокувань на читані дані, і, тому, не блокує інші транзакції, що змінюють дані. Такий механізм називається механізм виділення версій і полягає у використанні журналу транзакцій для генерації різних версій даних. Журнал транзакцій призначений для виконання операції відкоту при неуспішному виконанні транзакції чи для відновлення даних після збою системи. Журнал транзакцій містить старі копії даних, змінених транзакціями. Коротко суть методу полягає в наступному: Для кожної транзакції (чи запиту) запам'ятовується поточний системний номер (SCN - System Current Number). Чим пізніше почата транзакція, тим більше її SCN. При записі сторінок даних на диск фіксується SCN транзакції, що робить цей запис. Цей SCN стає поточним системним номером сторінки даних. Транзакції, тільки читаючі дані, не блокують нічого в базі даних. Якщо транзакція A читає сторінку даних, то SCN транзакції A порівнюється з SCN сторінки даних, що читається. Якщо SCN сторінки даних менше чи дорівнює SCN транзакції A, то транзакція A читає цю сторінку. Якщо SCN сторінки даних більше SCN транзакції A, то це означає, що деяка транзакція B, що почалася пізніше транзакції A, устигла змінити чи зараз змінює дані сторінки. У цьому випадку транзакція A переглядає журнал транзакція назад у пошуку першого запису про зміну потрібної сторінки даних з SCN меншим, ніж SCN транзакції A. Знайшовши такий запис, транзакція A використовує старий варіант дані сторінки. C використанням механізму виділення версій зважується проблема несумісного аналізу. Транзакція A, що почалася першою, не гальмує конкуруючу транзакцію B. При виявленні конфлікту транзакції A надається своя версія даних, що була на момент початку транзакції A. 4. Теорема Есварана про серіалізованість Концепція здатності до упорядкування була вперше запропонована Есвараном. У цій роботі був запропонований протокол двофазного блокування: Перед виконання яких-небудь операцій з деяким об'єктом, транзакція повинна заблокувати цей об'єкт. Після зняття блокування, транзакція не повинна накладати ніяких інших блокувань. Транзакції, використовувані в цьому протоколі, не різняться по типах і вважаються монопольними. Описані вище протоколи доступу до даних з використанням S- і X-блокувань і протокол навмисних блокувань є модифікаціями протоколу двофазного блокування для випадку, коли блокування мають різні типи. Есвараном сформульована наступна теорема: Теорема Есварана. Якщо всі транзакції в суміші підкоряються протоколу двофазного блокування, то для всіх графіків запуску, що чергуються, існує можливість упорядкування. Протокол називається двухфазным, тому що він характеризується двома фазами: 1 фаза - наростання блокувань. Під час цієї фази накладаються блокування, і провадиться робота з заблокованими об'єктами. 2 фаза - зняття блокувань. Під час цієї фази блокування тільки знімаються. Робота з раніше заблокованими даними може продовжуватися. 5. Реалізація ізольованості транзакцій засобами SQL 5.1. Рівні ізоляції Стандарт SQL не передбачає поняття блокувань для реалізації серіалізованості суміші транзакцій. Замість цього вводиться поняття рівнів ізоляції. Цей підхід забезпечує необхідні вимоги до ізольованості транзакцій, залишаючи можливість виробникам різних СУБД реалізовувати ці вимоги своїми способами (зокрема, з використанням блокувань чи виділенням версій даних). Стандарт SQL передбачає 4 рівні ізоляції: READ UNCOMMITTED - рівень незавершеного зчитування. READ COMMITTED - рівень завершеного зчитування. REPEATABLE READ - рівень повторюваного зчитування. SERIALIZABLE - рівень здатності до упорядкування. Якщо усі транзакції виконуються на рівні здатності до упорядкування (прийнятому за замовчуванням), то виконання, що чергується, будь-якої множини паралельних транзакцій може бути упорядковано. Якщо деякі транзакції виконуються на більш низьких рівнях, то є безліч способів порушити здатність до упорядкування. У стандарті SQL виділені три особливих випадки порушення здатності до упорядкування, фактично саме ті, котрі були описані вище як проблеми паралелізму: Неакуратне зчитування ("Брудне" читання, незафіксована залежність). Неповторювальне зчитування (Окремий випадок неспільного аналізу). Фантоми (Фіктивні елементи - окремий випадок неспільного аналізу). Утрата результатів відновлення стандартом SQL не допускається, тобто на найнижчому рівні ізольованості транзакції повинні працювати так, щоб не допустити втрати результатів відновлення. Різні рівні ізоляції визначаються по можливості чи виключенню цих особливих випадків порушення здатності до упорядкування. Ці визначення описуються наступною таблицею: Рівень ізоляції Неакуратне зчитування Неповторювальне зчитування Фантоми
READ UNCOMMITTED Так Так Так
READ COMMITTED Ні Так Так
REPEATABLE READ Ні Ні Так
SERIALIZABLE Ні Ні Ні
Таблиця 4 Рівні ізоляції стандарту SQL 5.2. Синтаксис операторів SQL, що визначають рівні ізоляції Рівень ізоляції транзакції задається наступним оператором: SET TRANSACTION {ISOLATION LEVEL {READ UNCOMMITTED | READ COMMITTED | REPEATABLE READ | SERIALIZABLE} | {READ ONLY | READ WRITE}}.,.. Цей оператор визначає режим виконання наступної транзакції, тобто цей оператор не впливає на зміну режиму тієї транзакції, у якій він подається. Звичайно, виконання оператора SET TRANSACTION виділяється як окрема транзакція: … (попередня транзакція виконується зі своїм рівнем ізоляції) COMMIT; SET TRANSACTION ISOLATION LEVEL REPEATABLE READ; COMMIT; … (наступна транзакція виконується з рівнем ізоляції REPEATABLE READ) Якщо задане речення ISOLATION LEVEL, то за ним повинен іти один з параметрів, що визначають рівень ізоляції. Крім того, можна задати ознаки READ ONLY чи READ WRITE. Якщо зазначена ознака READ ONLY, то передбачається, що транзакція буде тільки читати дані. При спробі запису для такої транзакції буде сгенерирована помилка. Ознака READ ONLY уведена для того, щоб дати виробникам СУБД можливість зменшувати кількість блокувань шляхом використання інших методів серіалізації (наприклад, метод виділення версій). Оператор SET TRANSACTION повинен задовольняти наступним умовам: Якщо речення ISOLATION LEVEL відсутнє, то за замовчуванням приймається рівень SERIALIZABLE. Якщо задана ознака READ WRITE, то параметр ISOLATION LEVEL не може приймати значення READ UNCOMMITTED. Якщо параметр ISOLATION LEVEL визначений як READ UNCOMMITTED, то транзакція стає за замовчуванням READ ONLY. У противному випадку за замовчуванням транзакція вважається як READ WRITE. Висновки Сучасні багатокористувацькі системи допускають одночасну роботу великого числа користувачів. При цьому якщо не прийняти спеціальних заходів, транзакції будуть заважати один одному. Цей ефект відомий як проблема паралелізму. Рішення проблем паралелізму полягає в знаходженні такої стратегії запуску транзакцій, щоб забезпечити серіалізованість графіка запуску і не занадто зменшити ступінь паралельності. Одним з методів забезпечення серіальності графіка запуску є протокол доступу до даних за допомогою блокувань. У найпростішому випадку розрізняють S-блокування (поділювані) і X-блокування (монопольні), для яких прописано протокол доступу. Якщо всі транзакції в суміші підкоряються протоколу доступу до даних, то проблеми паралелізму знімаються (майже всі, крім "фантомів"), але з'являються тупики. Стан тупика (dead locks) характеризується тим, що дві чи більше транзакції намагаються заблокувати ті самі об'єкти, і нескінченно довго очікують один одного. Для руйнування тупиків система періодично чи постійно підтримує графа чекання транзакцій. Наявність циклів у графі чекання свідчить про виникнення тупика. Для руйнування тупика одна з транзакціий (найбільш дешева з погляду системи) вибирається як жертву і відкочується. Для рішення проблеми "фантомів", а також для зменшення накладних витрат, викликуваних великою кількістю блокувань, застосовуються більш складні методи. Одним з таких методів є навмисні блокування, що блокують об'єкти різної величини - рядка, сторінки, таблиці, файли й ін. Альтернативним є метод предикатних блокувань Є також методи серіалізації, що не використовують блокування. Це метод часових міток і механізм виділення версій. Механізм виділення версій зручний тим, що він дозволяє одночасно, і читати, і змінювати ті самі дані різними транзакціями. Це збільшує ступінь паралельності, і загальну продуктивність системи. Стандарт SQL не передбачає поняття блокувань. Замість цього вводиться поняття рівнів ізоляції. Стандарт передбачає 4 рівні ізоляції: READ UNCOMMITTED - рівень незавершеного зчитування. READ COMMITTED - рівень завершеного зчитування. REPEATABLE READ - рівень повторюваного зчитування. SERIALIZABLE - рівень здатності до упорядкування. Транзакції можуть запускатися з різними рівнями ізоляції.
