Транзакции
Транзакция е последователност от операции с данни, която има начало и край.
Транзакцията е последователно изпълнение на операции за четене и запис. Завършването на транзакцията може да бъде или запазване на промените (фиксация, commit), или анулиране на промените (откат, rollback). В контекста на базите данни транзакцията представлява няколко заявки, които се третират като единична заявка.
Транзакциите трябва да отговарят на свойствата ACID.
Атомарност. Транзакцията или се изпълнява напълно, или изобщо не се изпълнява.
Съгласуваност. При завършване на транзакцията не трябва да бъдат нарушени ограниченията, наложени на данните (например constraints в базата данни). Съгласуваността предполага, че системата ще бъде преместена от едно коректно състояние в друго коректно.
Изолираност. Паралелно изпълнявани транзакции не трябва да влияят една на друга, например да променят данни, които се използват от друга транзакция. Резултатът от изпълнението на паралелни транзакции трябва да е такъв, сякаш транзакциите са били изпълнени последователно.
Устойчивост. След фиксация промените не трябва да бъдат загубени.
Журнал на транзакциите.
Журналът съхранява промените, извършени от транзакциите, осигурявайки атомарност и устойчивост на данните в случай на срив на системата.
Журналът съдържа стойностите, които данните са имали преди и след тяхната промяна от транзакцията. Стратегията Write-ahead log задължава добавянето в журнала на записа за предишните стойности преди началото, а за крайни след завършването на транзакцията. В случай на внезапно спиране на системата, базата данни чете журнала в обратен ред и отменя промените, направени от транзакциите. При среща с прекратена транзакция, базата данни я изпълнява и внася измененията й в журнала. В състояние на момента на срив, базата данни чете журнала в прав ред и връща измененията, направени от транзакциите. По този начин се запазва устойчивостта на транзакции, които вече са били фиксирани, и атомарността на прекратената транзакция.
Просто повторно изпълнение на грешни транзакции не е достатъчно за възстановяване.
Пример. В сметке на счету на потребителя 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 е била вече комитирана, ще възникне нарушение на принципа за устойчивост.
Едно от решенията за каскадни отмени. Транзакцията извършва всички записи в края, като другите транзакции трябва да изчакат завършването на тази операция. Транзакциите изчакват комитиране преди четене.
Правило на Тома — вариация на метода на времевите маркировки, при която данни, актуализирани от по-млада транзакция, не могат да бъдат презаписвани от по-стара.
Транзакция T изисква промяна на данни Q. Ако TS(T) < W-TS(Q), тъй като транзакцията се опитва да презапише по-нова стойност, транзакция T не бива отменена, както в метода на времевите маркировки.
Източник: habr.com
