Контрол на паралелността в СУБД: Протоколи, базирани на заключване и времеви марки

Какво е контрол на паралелността?

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

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

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

Потенциални проблеми с едновременността

Ето някои проблеми, с които вероятно ще се сблъскате без подходящ контрол на паралелността в СУБД:

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

Защо да използваме метод за паралелизъм?

Причини за използване на метод за контрол на паралелността в СУБД:

• Да се ​​приложи изолация чрез взаимно изключване между конфликтуващи транзакции.
• За разрешаване на проблеми с конфликти при четене и запис и запис.
• За да се запази съгласуваността на базата данни чрез постоянно прилагане на ограничения за изпълнение.
• За да се контролира взаимодействието между едновременните транзакции, се постига чрез схеми за контрол на паралелността.
• За да се гарантира сериализируемост.

Пример

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

Въпреки това, в киносалоната е останало само едно място за това представление. Без контрол на едновременността е възможно и двамата зрители да закупят билет. Контролът на едновременността не позволява това. И двамата зрители все още могат да имат достъп до информацията в базата данни за местата в киносалоните, но контролът на едновременността предоставя билет само на купувача, който пръв завърши процеса на транзакция.

Протоколи за контрол на паралелността

Различните протоколи за контрол на паралелността предлагат различни компромиси между количеството паралелност, което позволяват, и натоварването, което налагат. Основните техники за контрол на паралелността в СУБД са:

• Базирани на заключване протоколи
• Протокол за двуфазно заключване
• Протоколи, базирани на времево клеймо
• Базирани на валидиране протоколи

Всеки от тях е разгледан по-долу, като се започне с най-широко използваните протоколи, базирани на заключване.

Базирани на заключване протоколи

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

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

Двоични ключалки: Двоичното заключване на елемент от данни може да бъде в заключено или отключено състояние.

Споделено/Ексклузивно: Този заключващ механизъм разделя заключванията въз основа на тяхното използване. Ако заключването е придобито за извършване на операция за запис, то се нарича ексклузивно заключване.

1. Споделено заключване (S): Споделеното заключване се нарича още заключване само за четене. При споделено заключване елементът от данни може да се споделя между транзакции, тъй като никоя от тях няма разрешение да го актуализира. Например, ако две транзакции четат салдото по сметката на дадено лице, база данни позволява им да четат, като поставят споделено заключване. Ако друга транзакция иска да актуализира този баланс, споделеното заключване го предотвратява, докато четенето не приключи.

2. Изключително заключване (X): С ексклузивно заключване, даден елемент от данни може да бъде четен, както и записван. То е ексклузивно и не може да се съхранява едновременно върху един и същ елемент от данни. X-заключване се изисква с помощта на инструкцията lock-x. Например, когато транзакция трябва да актуализира салдото по сметката, това се разрешава чрез поставяне на X-заключване; втора транзакция, която иска да чете или записва, след това се предотвратява.

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

4. Заключване преди предявяване на иск: Този протокол оценява операциите и създава списък с данни, необходими за започване на изпълнението. Когато всички заключвания са разрешени, транзакцията се изпълнява и всички заключвания се освобождават, след като операциите ѝ приключат.

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

Безизходица: Безизходицата се отнася до ситуация, при която два или повече процеса чакат един друг да освободи ресурс, образувайки кръгова верига.

Протокол за двуфазно заключване (2PL)

- Протокол за двуфазно заключване, известен още като 2PL, е метод за контрол на паралелността, който осигурява сериализируемост чрез прилагане на заключване към данните от транзакциите, което блокира други транзакции от едновременен достъп до същите данни.

Протоколът за двуфазно заключване позволява всяка транзакция да направи заявка за заключване или отключване в две стъпки:

• Фаза на растеж: В тази фаза транзакцията може да получи заключвания, но може да не ги освободи.
• Фаза на свиване: В тази фаза транзакцията може да освободи заключвания, но може да не получи ново заключване.

Вярно е, че 2PL предлага сериализируемост. Това обаче не гарантира, че няма да се случат блокирания. На диаграмата по-горе, локалните и глобалните детектори на блокирания търсят блокирания и ги разрешават, като възобновяват транзакциите до първоначалните им състояния.

Стриктен двуфазен метод на заключване

Strict 2PL е почти същият като 2PL. Единствената разлика е, че Strict-2PL никога не освобождава заключване след използването му. Задържа всички заключвания до точката на commit и ги освобождава всички наведнъж, когато процесът приключи.

Централизирано 2PL

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

Основно копие 2PL

В механизма Primary Copy 2PL, много мениджъри на заключвания са разпределени на различни сайтове и определен мениджър на заключвания е отговорен за управлението на заключването за набор от елементи от данни. Когато първичното копие се актуализира, промяната се разпространява към подчинените устройства.

Разпределени 2PL

При този механизъм, мениджърите на заключвания са разпределени до всички сайтове и са отговорни за управлението на заключванията за данни на този сайт. Ако не се репликират данни, това е еквивалентно на Primary Copy 2PL. Разходите за комуникация на Distributed 2PL са доста по-високи от тези на Primary Copy 2PL.

Протоколи, базирани на времево клеймо

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

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

Пример:

Suppose there are three transactions T1, T2, and T3.
T1 has entered the system at time 0010
T2 has entered the system at 0020
T3 has entered the system at 0030
Priority will be given to transaction T1, then T2 and lastly T3.

Предимства:

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

Недостатъци: Гладът е възможен, ако една и съща транзакция се рестартира и непрекъснато се прекъсва.

Протокол, базиран на валидиране

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

Протоколът, базиран на валидиране, се изпълнява в три фази:

1. Прочетете фаза
2. Фаза на валидиране
3. Напишете фаза

Прочетете фаза

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

Фаза на валидиране

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

Напишете фаза

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

Сравнение на протоколите за контрол на паралелизма

Четирите семейства протоколи правят различни залози за това колко често транзакциите действително конфликтират. Таблицата по-долу обобщава къде се вписва всяко от тях.

Накратко, протоколите, базирани на заключване, и 2PL протоколите приемат, че конфликтът е често срещан и го предотвратяват предварително, докато протоколите за времеви марки и валидиране приемат, че конфликтът е рядък и го разрешават само когато се появи.

Характеристики на добър протокол за паралелизъм

Идеалният механизъм за контрол на паралелизма има следните цели:

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

Въпроси и Отговори