Транзакції
Транзакцією називається послідовність операцій над даними, що має початок і кінець
Транзакція це послідовне виконання операцій читання та запису. Закінченням транзакції може бути збереження змін (фіксація, commit) або скасування змін (відкат, rollback). Стосовно БД транзакція це кілька запитів, які трактуються як єдиний запит.
Транзакції повинні задовольняти властивості ACID
Атомарність. Транзакція або виконується повністю або зовсім не виконується.
Узгодженість. При завершенні транзакції не повинні бути порушені обмеження, що накладаються на дані (наприклад, constraints в БД). Узгодженість має на увазі, що система буде переведена з одного коректного стану до іншого коректного.
Ізольованість. Паралельно виконувані транзакції повинні впливати друг на друга, наприклад змінювати дані які використовує інша транзакція. Результат виконання паралельних транзакцій має бути таким, ніби транзакції виконувались послідовно.
Стійкість. Після фіксації зміни не повинні бути втрачені.
Журнал транзакцій
Журнал зберігає зміни виконані транзакціями, забезпечує атомарність та стійкість даних у разі збою системи.
Журнал містить значення, які дані мали до та після їх зміни транзакцією. Write-ahead log strategy зобов'язує додавати до журналу запис про попередні значення до початку, а про кінцеві після завершення транзакції. У разі раптової зупинки системи БД читає лог у зворотному порядку та скасовує зміни, зроблені транзакціями. Зустрівши перервану транзакцію БД виконує її та вносить зміни про неї до журналу. Перебуваючи у стані на момент збою, БД читає лог у прямому порядку та повертає зміни, зроблені транзакціями. Таким чином зберігається стійкість транзакцій, які вже були зафіксовані і атомарність перерваної транзакції.
Просте повторне виконання помилкових транзакцій недостатньо відновлення.
приклад. На рахунку користувача 500$ і користувач вирішує зняти їх через банкомат. Виконуються дві транзакції. Перша читає значення балансу і якщо на балансі достатньо коштів видає гроші користувачеві. Друга віднімає з балансу необхідну суму. Допустимо, стався збій системи і перша операція не виконалася, а друга виконалася. У цьому випадку ми не можемо повторно видати гроші користувачу без повернення системи до початкового стану з позитивним балансом.
Рівні ізоляції
Читання фіксованих даних (Read Committed)
Проблема брудного читання (Dirty Read) у тому, що транзакція може прочитати проміжний результат роботи інший транзакції.
приклад. Початкове значення балансу 0 $. Т1 додає до балансу 50 $. Т2 зчитує значення балансу (50 $). Т1 скасовує зміни та завершується. T2 продовжує виконання маючи неправильні дані про баланс.
Рішенням є читання фіксованих даних (Read Committed), що забороняє читати дані, змінені транзакцією. Якщо транзакція A змінила деякий набір даних, то транзакція B при зверненні за цими даними змушена чекати завершення транзакції A.
Повторюване читання (Repeatable Read)
Проблема втрачених змін (Lost Updates). Т1 зберігає зміни поверх змін Т2.
приклад. Початкове значення балансу 0$ та дві транзакції одночасно поповнюють баланс. T1 і T2 читають баланс, що дорівнює 0$. Потім T2 додає 200 $ до 0 $ і зберігає результат. T1 додає 100 $ до 0 $ і зберігає результат. Підсумковий результат 100 $ замість 300 $.
Проблема неповторного читання (Unrepeatable read). Повторне читання тих самих даних повертає різні значення.
приклад. Т1 читає значення балансу 0$. Потім Т2 додає до балансу 50 $ і завершується. Т1 повторно читає дані та виявляє невідповідність з попереднім результатом.
Повторюване читання (Repeatable Read) гарантує, що повторне читання поверне той самий результат. Дані, прочитані однією транзакцією, заборонено змінювати в інших до завершення транзакції. Якщо транзакція A прочитала деякий набір даних, то транзакція B при зверненні за цими даними змушена чекати завершення транзакції A.
Впорядковане читання (Serializable)
Проблема фантомного читання (Phantom Reads). Два запити вибирають дані за певною умовою повертають різні значення.
приклад. T1 запитує кількість всіх користувачів баланс яких більше 0$ але менше 100$. T2 віднімає 1$ у користувача з балансом 101$. T1 повторно виконує запит.
Упорядковане читання (Serializable). Транзакції виконуються як послідовні. Забороняється оновлювати та додавати записи, які підпадають під умови запиту. Якщо транзакція A запросила дані всієї таблиці, таблиця цілком заморожується інших транзакцій до завершення транзакції A.
Планувальник (Scheduler)
Встановлює черговість в якій повинні виконуватися операції при транзакціях, що паралельно протікають.
Забезпечує заданий рівень ізольованості. Якщо результат виконання операцій залежить від їх черговості, такі операції коммутативные (Permutable). Комутативні операції читання та операції над різними даними. Операції читання-запису та запису-запису не коммутативні. Завдання планувальника чергувати операції, що виконуються паралельними транзакціями так, щоб результат виконання був еквівалентний послідовному виконанню транзакцій.
Механізми контролю паралельних завдань (Concurrency Control)
Оптимістичний заснований на виявленні та вирішенні конфліктів, песимістичний на запобіганні виникненню конфліктів
При оптимістичному підході кілька користувачів отримують копію даних. Перший, хто завершив редагування, зберігає зміни, решта ж має здійснити злиття змін. Оптимістичний алгоритм дозволяє конфлікту відбутися, але система має відновитись після конфлікту.
При песимістичному підході перший користувач, що захопив дані, перешкоджає отриманню даних іншим. Якщо конфлікти рідко розумно вибрати оптимістичну стратегію, оскільки вона забезпечує вищий рівень паралелізму.
Блокування (Locking)
Якщо одна транзакція заблокувала дані, то інші транзакції при зверненні до даних повинні чекати на розблокування
Блок може накладатися на базу даних, таблицю, рядок або аттрибут. Спільне захоплення (Shared Lock) може бути накладене на одні дані декількома транзакціями, дозволяє всім транзакціям (включаючи читання), забороняє зміну і монопольне захоплення. Монопольне захоплення (Exclusive Lock) може бути накладене лише однією транзакцією, дозволяє будь-які дії транзакції, що наклала, забороняє будь-які дії іншим.
Взаємоблокуванням вважається ситуація, коли транзакції опиняються в режимі очікування, що триває нескінченно довго.
приклад. Перша транзакція чекає на звільнення даних захоплених другою, тоді як друга чекає на звільнення даних, захоплених першою.
Оптимістичне вирішення проблеми взаємоблокування дозволяє взаємоблокуванню відбутися, але потім відновлює систему, відкочуючи одну з транзакцій, що беруть участь у взаємоблокуванні.
З певною періодичністю провадиться пошук взаємоблокувань. Один із способів виявлення — за часом, тобто вважати, що взаємоблокування відбулося, якщо транзакція виконується занадто довго. Коли знайдено взаємоблокування, то одна з транзакцій відкочується, що дає можливість іншим транзакціям брати участь у взаємоблокуванні завершитися. Вибір жертви може бути заснований на вартості транзакцій або їх старшинства (Wait-Die та Wound-wait схеми).
кожній транзакції T присвоюється тимчасова мітка TS містить час початку виконання транзакції.
Wait-Die.
Якщо TS(Ti) < TS(Tj), То Ti чекає, інакше Ti відкочується і починається заново з тією ж тимчасовою міткою.
Якщо молода транзакція захопила ресурс, а стара запитує той самий ресурс, то старшої транзакції можна очікувати. Якщо більш стара транзакція захопила ресурс, то молода транзакція, яка запитує цей ресурс, буде відкачена.
Wound-wait.
Якщо TS(Ti) < TS(Tj), То Tj відкочується і починається заново з тією ж тимчасовою міткою, інакше Ti чекає.
Якщо молодша транзакція захопила ресурс, а стара транзакція запитує той самий ресурс, то молода транзакція буде відкачена. Якщо старіша транзакція захопила ресурс, то молодшої транзакції, що запитує цей ресурс можна очікувати. Вибір жертви заснований на старшинстві запобігає появі взаємоблокувань, але відкочує транзакції, які не перебувають у стані взаємоблокування. Проблема у тому, що транзакції можуть відкочуватися багато разів, т.к. Старіша транзакція може довго утримувати ресурс.
Песимістичне вирішення проблеми взаємоблокувань не дозволяє транзакції розпочати виконання, якщо є ризик виникнення взаємоблокування.
Для виявлення взаємоблокування будується граф (граф очікування, wait-for-graph), вершини якого транзакції, а ребра направлені від транзакцій, що очікують звільнення даних до транзакції, що захопили ці дані. Вважається, що взаємоблокування відбулося, якщо граф має зацикленість. Побудова графа очікування, особливо у розподілених БД, дорога процедура.
Двофазне блокування — запобігання взаємоблокуванню шляхом захоплення всіх ресурсів, що використовуються транзакцією на початку транзакції та звільнення їх наприкінці
Усі блокуючі операції повинні передувати першій розблокувальній. Має дві фази - Growing Phase, при якій відбувається накопичення захоплень і Shrinking Phase, при якій відбувається звільнення захоплень. При неможливості захоплення однієї з ресурсів транзакція починається спочатку. Можлива ситуація, коли транзакція не зможе захопити необхідні ресурси, наприклад, якщо кілька транзакцій будуть конкурувати за одні ресурси.
Двофазний коміт забезпечує виконання комміту на всіх репліках БД
Кожна БД вносить інформацію про дані, які будуть змінені в лог і відповідає координатору ОК (Voting Phase). Після того як всі відповіли ОК координатор відсилає сигнал, що зобов'язує всіх зробити коміт. Після комміту сервера відповідають ОК, якщо хоч один не відповів ОК, координатор відсилає сигнал скасування змін всім серверам (Completion Phase).
Метод тимчасових міток
Старша транзакція відкочується при спробі доступу до даних, задіяних молодшою транзакцією
Кожній транзакції призначається тимчасова мітка TS відповідна часу початку виконання. Якщо Ti старше Tj, То TS(Ti) < TS(Tj).
Коли транзакція відкочується, їй призначається нова мітка. Кожен об'єкт даних Q задіяний транзакцією позначається двома мітками. W-TS(Q) — тимчасова мітка наймолодшої транзакції, яка успішно виконала запис над Q. R-TS(Q) - тимчасова мітка наймолодшої транзакції, яка виконала запис читання над Q.
Коли транзакція T запитує читання даних Q можливі два варіанти.
Якщо TS(T) < W-TS(Q), тобто дані були оновлені молодшою транзакцією, то транзакція T відкочується.
Якщо TS(T) >= W-TS(Q), то читання виконується і R-TS(Q) стає MAX(R-TS(Q), TS(T)).
Коли транзакція T запитує зміну даних Q можливі два варіанти.
Якщо TS(T) < R-TS(Q), тобто дані вже були прочитані молодшою транзакцією і якщо зробити зміну, виникне конфлікт. Транзакція T відкочується.
Якщо TS(T) < W-TS(Q), тобто транзакція намагається перезаписати новіше значення, транзакція T відкочується. В інших випадках зміна виконується та W-TS(Q) стає рівним TS(T).
Не потрібно дорогої побудови графа очікування. Старші транзакції залежать від новіших, отже у графі очікування немає циклів. Немає взаємоблокувань, оскільки транзакції не очікують, а одразу відкочуються. Можливі каскадні відкати. Якщо Ti відкотилася, а Tj прочитала дані які змінила Ti, То Tj теж має відкотитися. Якщо при цьому Tj вже було закоммічено, то виникне порушення принципу стійкості.
Одне із рішень каскадних відкатів. Транзакція виконує всі операції запису наприкінці, причому інші транзакції мають очікувати завершення цієї операції. Транзакції очікують на комміт перед читанням.
Thomas write rule — варіація методу тимчасових міток, при якій дані оновлені молодшою транзакцією заборонено перезаписувати старішою
транзакція T запитує зміну даних Q. Якщо TS(T) < W-TS(Q), тобто транзакція намагається перезаписати більш нове значення, транзакція T не відкочується як у методі тимчасових міток.
Джерело: habr.com