Лекция 11. Методи за сериализация на транзакциите

Лекция 11. Методи за сериализация на транзакциите

Предварително ще отбележим, че за двата подхода си има две разновидности – песимистична и оптимистична. При използването на песимистичните методи, ориентирани към ситуации, когато конфликтите възникват често, конфликтите се разпознават и се разрешават незабавно при тяхното възникване. Оптимистичните методи се основават на това, че резултатите на всичките операции за модификация на базата от данни се съхраняват в работната памет на транзакциите. Реалната модификация на базата от данни се извършва чак на стадий фиксация на транзакцията. Тогава се проверява и дали не възникват конфликти с други транзакции.

Ще се ограничим с разглеждането на по-разпространените песимистични разновидности на методите за сериализация на транзакциите. Песимистичните методи сравнително лесно се трансформират в своите оптимистични варианти

11.1. Синхронизационни захвати

Основните режими на синхронизационни захвати са:

• 
  съвместен режим - S (Shared), означаващ разделяем захват на обекта и необходим за изпълнение на операция четене на обекта;
  
• 
  монополен режим - X (eXclusive), означаващ монополен захват на обекта и необходим за изпълнение на операции записване, изтриване и модификация.
  

Да отбележим, че думата ,,не” в таблицата съответства на описаните по-рано възможни случаи на конфликт на транзакциите по достъпа към обектите от база данни (WW, RW, WR). Съвместимостта на S-захватите съответства на това, че конфликт RR не съществува.

За осигуряване на сериализацията на транзакциите (от трето ниво на изолираност) синхронизационните захвати на обектите, извършени по инициатива на транзакцията, може да се свалят след нейното приключване. Това изискване поражда двуфазния протокол на синхронизационните захвати - 2PL. В съответствие с този протокол изпълнението на транзакция се разделя на две фази:

• 
  първа фаза на транзакцията – събиране на блокировките;
  
• 
  втора фаза (фиксация или откат) – освобождаване на блокировките.
  

В контекста на релационните бази от данни са възможни следните алтернативи:

• 
  файл - физически (от гледна точка на базата от данни) обект, област за съхранение на няколко отношения и възможно на индекси;
  
• 
  отношение - логически обект, съответстващ на множество кортежи от дадено отношение;
  
• 
  страница данни - физически обект, съхраняващ кортежи от едно или няколко отношения, индексна или служебна информация;
  
• 
  кортеж - елементарен физически обект на база от данни.
  

Колкото по-голям е обекта на синхронизационен захват (не е важно, каква е природата на този обект - логически или физически), толкова по-малко синхронизационни блокировки ще се поддържат в системата, и за това, съответно, ще има по-малки съпътстващи разходи. Освен това, ако се избере в качеството на ниво на обектите за захват файл или отношение, то ще бъде решен даже проблема за фантомите.

Целият проблем е в това, че при използването на блокировки на крупни обекти нараства вероятността за конфликти на транзакциите и по този начин намалява допусканата степен на паралелното изпълнение. Фактически, при укрупняването на обекта на синхронизационна блокировка ние умишлено огрубяваме ситуацията и виждаме конфликти, когато всъщност конфликти няма.

Разработчиците на много от системите са започвали с използването на блокировки на страници, полагайки това за някакъв компромис между стремежите да се съкратят съпътстващите разходи и да се запази достатъчно високо ниво на паралелност на транзакциите. Но това не е много добър избор. Няма да се спираме на подробностите, но ще отбележим, че използването на захвати на страници в двуфазния протокол понякога предизвиква много неприятни синхронизационни проблеми, усложняващи организацията на СУБД. В повечето съвременни системи се използват покортежни синхронизационни захвати.

Но при това възниква поредния въпрос. Ако единица за захват е кортежа, то какви синхронизационни захвати ще са необходими при изпълнението на такива операции като унищожаване на отношение? Би било нелепо преди изпълнението на такава операция да се поиска захват на всички съществуващи кортежи на отношението. И друго, това не би предотвратило възможността за паралелно вмъкване в друга транзакция на нов кортеж в унищожаваното отношение.

11.1.1. Гранулирани синхронизационни захвати

Сега най-важното различие, което, собствено, обуславя съответствието на захватите от различните нива. Въвеждат се специален протокол на гранулираните захвати и нови типове захвати: преди блокирането на обект в режим S или X съответният обект от по-високо ниво трябва да бъде бъде блокиран в режим IS, IX или SIX. Какво представляват тези режими на блокиране?

Много трудно е да се опишат всички възможни ситуации. Ще се ограничим с привеждането на пълната таблица на съвместимостта на блокировките, с която може да се покажат всички случаи:

11.1.2. Предикатни синхронизационни блокировки

Независимо от привлекателността на метода на гранулираните синхронизационни блокировки, трябва да отбележим, че той не решава проблема на фантомите (ако, разбира се, не се ограничим с използването на блокировки на отношения в режими S и X). Известно е, че за решаването на този проблем трябва да се премине от блокировки на индивидуални обекти на базата от данни, към захват на условията (предикатите), които удовлетворяват тези обекти. Проблемът на фантомите не възниква при използване за синхронизация на ниво отношение именно, защото отношението като логически обект представлява неявно условие за входящите в него кортежи. Блокирането на отношение е прост и частен случай на предикатен захват.

Тъй като всяка операция над релационната база от данни се задава с някакво условие (т.е. в нея се указва не конкретен набор обекти на базата от данни, над които трябва да се изпълни операция, а условие, което са длъжни да удовлетворят обекти от този набор), идеалният избор би бил да се заяви синхронизационен захват в режим S или X именно на това условие. Но ако се погледне към общия вид на условията, допускани, например, в езика SQL, то става абсолютно неясно, как да се определя съвместимостта на два предикатни захвата. Ясно е, че без да се използват предикатни блокировки за синхронизация на транзакциите е невъзможно, а в общия си вид проблемът е неразрешим.

За щастие, този проблем сравнително лесно се решава в случай на прости условия. Ще наричаме просто условие конюнкцията на прости предикати, имащи вида

име-атрибут { = > < } значение

В типичните СУБД, поддържащи двустепенна организаци, (езиково ниво и ниво на управление на външната памет), в интерфейса на подсистемите за управление на паметта (която обикновено отговаря и за сериализацията на транзакците) се допускат само прости условия. Подсистемата за езиково ниво извършва компилацията на изходния оператор със сложно условие в последователност от обръщения към ядрото на СУБД, във всяко от които се съдържат само прости условия. Следователно, при типовата организация на релационна СУБД простите условия може да се използват като основа за предикатни захвати.

За простите условия съвместимостта на предикатните захвати лесно се определя на основата на следната геометрична интерпретация. Нека R е отношение с атрибути a₁, a₂, ..., a_n, а m₁, m₂, ..., m_n - множествата от допустими стойности на a₁, a₂, ..., a_n съответно (всички тези множества са крайни). Тогава може на R да се съпостави крайно n-мерно пространство от възможни значения на кортежите на R. Всяко просто условие "изрязва" m-мерен правоъгълник в това пространство (m <= n).

Тогава S-X, X-S, X-X - предикатни захвати от различни транзакции са съвместими, ако съответните правоъгълници не се пресичат.

Това се илюстрира със следния пример, показващ, че в каквито и режими да заявява транзакция 1 захват на условието (1<=a<=4) & (b=5), а транзакция 2 - условието (1<=a<=5) & (1<=b<=3), тези блокировки винаги са съвместими.

Пример: (n = 2)

Предикатните захвати на прости условия се описват в таблици, които не се различават много от таблиците на традиционните синхронизатори.

11.1.3. Взаимоблокировки, разпознаване и разрушаване

Един най най-чувствителните недостатъци на метода за сериализация на транзакциите на основата на синхронизационните захвати е възможността за възникване на взаимоблокировки (deadlocks) между транзакциите. Взаимоблокировки са възможни при прилагането на всеки от разгледаните от нас варианти.

Един прост пример за възникване на взаимоблокировка между транзакциите T₁ и T₂:

• 
  транзакции T₁ и T₂ са установили монополни блокировки на обекти r₁ и r₂ съответно;
  
• 
  след това на T₁ е необходим съвместен захват на r₂, а на T₂ - съвместен захват на r₁;
  
• 
  нито една от транзакциите не може да продължи, следователно, монополните блокировки няма да бъдат свалени, а съвместните – няма да бъдат удовлетворени.
  

Тъй като взаимоблокировките са възможни, и не съществува никакъв естествен изход от взаимоблокировкова ситуация, то тези ситуации трябва да се откриват и изкуствено да се отстраняват.

Основа за откриване на ситуации на взаимоблокировки е построяването (или постоянното поддържане) на графа на изчакването на транзакциите. Графът на изчакването на транзакциите е ориентиран двупосочен граф, в който има два типа върхове - върхове, съответстващи на на транзакциите, и върхове, съответстващи на обектите на захват. В този графе съществува дъга, водеща от върхове-транзакции към връх-обект, ако за тази транзакция съществува предоставен захват на обекта. В графа съществува дъга от връх-обект към връх-транзакция, ако транзакцията изчаква предоставянето на захвата на обекта.

Лесно се показва, че в системата съществува ситуация на взаимоблокировка, ако в графа на изчакване на транзакциите има поне един цикъл.

За разпознаване на взаимоблокировки периодично се извършва построяване на граф на изчакване на транзакциите (както беше отбелязано, понякога графът на изчакване се поддържа постоянно), и в този граф се търсят цикли. Традиционна техника (която има много разновидности) за намиране на цикли в ориентиран графе е редукцията на графа. Без да детайлизираме, редукцията се състои в това, че преди всичко от графа на изчакването се премахват всички дъги, излизащи от върховете-транзакции, в които не влизат дъги от върхове-обекти. (Това съответствува на ситуацията, когато транзакциите, неизчакващи предоставянето на блокировки, успешно са завършили и са освободили захватите). За тези върхове-обекти, за които не са останали входящи дъги, но съществуват изходящи, ориентацията на изходящите дъги се променя на противоположната (това моделира предоставянето на блокировките). След това отново сработва първата стъпка и така дотогава, докато на първата стъпка не се прекрати премахването на дъгите. Ако в графа са останали дъги, то те задължително образуват цикъл.

Да предположим, че сме успели да намерим цикъл в графа на изчакването на транзакциите. Какво трябва да направим? Трябва по някакъв начин да осигурим възможност за продължаване на работата поне за някои от транзакциите, попаднали във взаимоблокировки. Разрушаването на взаимоблокировка започва с избора в цикъла на транзакции на така наречените транзакции-жертви, т.е. транзакции, които ще решим да пожертваме, за да се осигури възможност за продължаване на работата на други транзакции.

Грубо казано, критерият за избор е стойността на транзакцията; за жертва се избира най-евтината транзакция. Стойността на транзакцията се определя на основата на многофакторна оценка, в която с различни тегла се включват времето за изпълнение, броя натрупани захвати, приоритетът.

След избора на транзакцията-жертва се изпълнява откат на тази транзакция, който може да има пълен или частичен характер. При това, естествено, се освобождават блокировките и може да бъде продължено изпълнението на другите транзакции.

Естествено, такова насилствено отстраняване на ситуации на взаимоблокировки е нарушение на принципа на изолираност на потребителите, което е невъзможно да се избегне.

В централизираните системи стойността на построяването на графа на изчакването е сравнително неголяма, но тя става твърде голяма в истински разпределените СУБД, в които транзакциите могат да се изпълняват в различни възли на мрежата. Затова в такива системи обикновено се използват други методи за сериализация на транзакциите.

За да се минимизира броят на конфликтите между транзакциите, в някои СУБД (например, в Oracle) се използва следното развитие на подхода. Монополният захват на обекта спира само изменящите транзакции. След изпълнението на операция модификация предишната версия на обекта остава достъпна за четене в другите транзакции. Кратковременна блокировка за четене се изисква само за периода на фиксация на изменящата транзакция, когато обновените обекти стават текущи.

11.2. Метод на времевите маркери

Алтернативен метод за сериализация на транзакцията, който добре работи в условията на редки конфликти на транзакции и не изисква построяване на граф на изчакването на транзакциите се основава на използването на времеви маркери.

Основната идея на метода (който има множество разновидности) се състои в следното: ако транзакция T₁ е започала преди транзакция T₂, то системата осигурява такъв режим на изпълнение, както ако T₁ изцяло е изпълнена преди началто на T₂.

За това на всяка транзакция T се приписва времеви маркер t, съответствуващ на времето, когато е започнала T. При изпълнение на операция над обект r транзакцията T го маркира със своя времеви маркер и типа на операцията (четене или изменение).

Преди изпълнението на операция над обекта r транзакцията T₁ изпълнява следните действия:

• 
  Проверява, не е ли завършила транзакцията T, маркирала този обект. Ако T е завършила, T₁ маркира обекта r и изпълнява своята операция.
  
• 
  Ако транзакцията T не е завършила, то T₁ проверява конфликтността на операциите. Ако операциите са неконфликтни, при обекта r остава или се поставя времевия маркер с по-малката стойност, и транзакцията T₁ изпълнява своята операция.
  
• 
  Ако операциите на T₁ и T конфликтуват, то ако t(T) > t(T₁) (т.е. транзакцията T е “по- млада”, от T), то T се рестартира и T₁ продължава работата си.
  
• 
  Ако t(T) < t(T₁) (T е "по-стара" от T₁), то T₁ получава нов времеви маркер и започва отново.
  

Към недостатъците на метода на времевите маркери се отнасят потенциално по-честите откати на транзакции, отколкото в случая на използване на синхронизационни блокировки. Това е свързано с това, че конфликтността на транзакциите се определя по-грубо. Освен това, в разпределените системи не е много лесно да се израбатват глобални времеви маркери с отношение на пълен ред.

Но в разпределените системи тези недостатъци се изкупват с това, че не е нужно да се разпознават взаимоблокировките, а както вече отбелязахме, построяването на графа на изчакването в разпределените системе струва много скъпо.

Каталог: tadmin -> upload -> storage
storage -> Литература на факта. Аналитизъм. Интерпретативни стратегии. Въпроси и задачи
storage -> Лекция №2 Същност на цифровите изображения Въпрос. Основни положения от теория на сигналите
storage -> Лекция 5 система за вторична радиолокация
storage -> Толерантност и етничност в медийния дискурс
storage -> Ethnicity and tolerance in media discourse revisited Desislava St. Cheshmedzhieva-Stoycheva abstract
storage -> Тест №1 Отбележете невярното твърдение за подчертаните думи
storage -> Лекции по Въведение в статистиката
storage -> Търсене на живот във вселената увод
storage -> Еп. Константинови четения – 2010 г някои аспекти на концептуализация на богатството в руски и турски език

Изтегляне 1.71 Mb.

Сподели с приятели: