Egzamin, zadanie 3

back

Treść

Dany jest schemat

CREATE TABLE tasks (id INTEGER PRIMARY KEY);  
CREATE TABLE completed (id INTEGER PRIMARY KEY);  

oraz dwie transakcje, A i B,

A.1: SELECT MIN(t.id) INTO t_id FROM tasks t WHERE t.id NOT IN (SELECT id FROM completed);  
A.2: INSERT INTO completed(id) VALUES (t_id);  
A.3: COMMIT;

B.1: SELECT MIN(t.id) INTO t_id FROM tasks t WHERE t.id NOT IN (SELECT id FROM completed);  
B.2: DELETE FROM tasks WHERE id = t_id;  
B.3: COMMIT;

Przyjmijmy, że każda z sześciu instrukcji powyżej jest atomowa i wykonuje się bezpośrednio na instancji bazy danych (tzn. instrukcje INSERT i DELETE faktycznie modyfikują instancję, a instrukcja COMMIT po prostu kończy transakcję). Wypisz wszystkie nieszeregowalne przeploty tych dwóch transakcji. Wyjaśnij, dlaczego są nieszeregowalne i uzasadnij, że pozostałe są szeregowalne. Dla każdego z nieszeregowalnych przeplotów wskaż poziomy izolacji (wg. standardu ISO SQL), które go wykluczają. Odpowiedź uzasadnij w poparciu o definicje poziomów izolacji.

Wzorcówka

Przy sekwencyjnym wykonaniu A; B lub B; A jest niemożliwe, aby zmienna t_id w obu transakcjach miała taką samą wartość. W pierwszym przypadku taka liczba nie spełnia już NOT IN (SELECT id FROM completed), w drugim nie istnieje już w tasks.

Przeploty zaczynające się od A.1 A.2 lub B.1 B.2 są oczywiście szeregowalne, bo COMMIT jest defacto pustą operacją.

Przeploty zaczynające się od A.1 B.1 lub B.1 A.1 nie są szeregowalne, gdyż t_id przyjmie tę samą wartość w obu transakcjach, a nie jest to możliwe przy wykonaniu sekwencyjnym.

Przy tych przeplotach nie występuje żadna z anomalii wymienionych w standardzie SQL. Zarówno A.1 jak i B.1 odczytują niezmodyfikowane tabele tasks i completed. Następnie, w dowolnej kolejności:

• A.2 odczytuje (musi sprawdzić constraint PK) i modyfikuje completed;
• B.2 odczytuje i modyfikuje tasks,

a więc żadna transakcja nie widzi zmian drugiej. Jednak operacje nie są szeregowalne, mamy więc do czynienia z serialization anomaly i nie istnieje taki poziom izolacji w standardzie SQL, który nas przed tym uchroni.

Ocenianie

Za scharakteryzowanie przeplotów wraz z uzasadnieniem było $7$ punktów. Za poprawne wskazanie, które przeploty są szeregowalne, a które nie, ale z błędnym uzasdanieniem, można było dostać $3$ punkty.

Pozostałe $3$ punkty były za wskazanie anomalii zachodzących przy nieszeregowalnych przeplotach i odpowiedniego poziomu izolacji – t.j. powiedzenie, że takiego nie ma. Tutaj z reguły ocena była binarna, albo było dobrze, albo student znalazł w przeplocie non-repeatable read/phantom read który w rzeczywistości tam nie występuje.

Diatryba

Intuicja

Warto zobrazować na przykładzie, dlaczego A.1 B.1 oraz B.1 A.1 są nieszeregowalne.

Jeśli na początku w tasks mamy $\{1, 2\}$, a w completed nic ($\emptyset$), to możliwe stany końcowe przy wykonaniu sekwencyjnym to:

• A; B $\rightarrow tasks = \{1\}, completed = \{1\}$
• B; A $\rightarrow tasks = \{2\}, completed = \{2\}$

Z kolei przeploty nieszeregowalne dają nam zawsze
$$tasks = \{2\}, completed = \{1\}.$$

Dlaczego nie ma tu standardowych anomalii

Kilka osób twierdziło, że przeploty A.1 A.2 B.1 ... oraz B.1 B.2 A.1 ... są nieszeregowalne, bo odczyt drugiej transakcji jest dirty readem. O ile rzeczywiście taki przeplot nie będzie miał miejsca w żadnej bazie na poziomie wyższym niż READ UNCOMMITTED, to nie jest nieszeregowalny. Przeploty te są równoważne odpowiednio z A; B i B; A, co można łatwo udowodnić.

Wielu studentów (ponad połowa zgłoszeń!) uznawało za anomalię zdarzenie, które hipotetycznie mogłoby coś popsuć, gdyby tylko powtórzyć którąś operację (albo całą transakcję). Definicje anomalii takie nie są i bazy danych tak nie działają. W szczególności:

• non-repeatable read zachodzi wtedy i tylko wtedy, kiedy któraś transakcja odczytuje dwukrotnie ten sam wiersz i przy drugim odczycie widzi modyfikację innej transakcji na tym wierszu, która zaszła pomiędzy odczytami
• phantom read podobnie, zachodzi wtedy i tylko wtedy, kiedy któraś transakcja odczytuje dwukrotnie wynik zapytania i przy drugim odczycie widzi wiersze, które zostały dodane przez inną transakcję pomiędzy odczytami.

Należy zwrócić uwagę na stwierdzenie odczytuje. Rzeczywiście odczytuje. Przykładowo, transakcja A odczytuje tablicę tasks wyłącznie raz. Jest to więc trywialnie niemożliwe, żeby nastąpił non-repeatable read przez operację B.2, bo A nigdy tego usunięcia nie zaobserwuje. Uzasadnienie, że gdyby wziąć hipotetyczną transakcję A', która wykonuje:

A.1
A.2
A.1
COMMIT;

to wtedy przy drugim wykonaniu A.1 mielibyśmy non-repeatable read, to nie jest poprawne uzasadnienie.

Dlaczego to nie jest czepialstwo

To, że anomalie są zdefiniowane tak, a nie inaczej, jest bardzo ważne, aby bazy danych mogły sensownie wykonywać operacje współbieżnie. Po pierwsze, gdyby zastosować podobną definicję hipotetyczną do anomalii dirty read, to znajdziemy się w sytuacji, w której nikt nigdy nie jest w stanie nic zmodyfikować bez zatrzymania całej bazy danych. No bo przecież kiedy dana transakcja X zmodyfikuje dany wiersz, to gdyby jakaś inna transakcja próbowała go odczytać, to mielibyśmy dirty read. Zgodnie z taką definicją musimy odrzucić wszystkie przeploty, w których po modyfikacji X dzieje się cokolwiek innego niż X, a więc efektywnie zablokować całą bazę danych dopóki X się nie skończy.

Podobnie to wygląda dla non-repeatable read, ale może nie być to aż tak oczywiste. Spróbuję to zobrazować na przykładzie.

Załóżmy, że mamy bazę danych jakiejś dużej firmy. Wykonywane są w niej codziennie setki tysięcy skomplikowanych transakcji, które dotyka wielu tabel i wykonują pewne operacje finansowe. Każda z tych transakcji na początku działania odczytuje z tabeli configuration jeden wiersz określający parametr fee, który jest globalną prowizją wpływającą na ceny i wyniki w rzeczonych operacjach finansowych. Jest to tylko jeden read, który każda transakcja wykonuje na początku i zapisuje lokalnie, a potem korzysta na potrzeby swojej logiki. Te transakcje muszą wykonywać się na poziomie izolacji REPEATABLE READ, aby zapobiec błędom.

Świat jednak jest dynamiczny i konfiguracja, a w szczególności parametr fee, się zmienia. Co jakiś czas w bazie danych musi się odbyć banalna transakcja, która po prostu modyfikuje wartość fee w wierszu konfiguracyjnym, np. żeby reflektować zmiany w krajowych stopach procentowych. Co teraz?

Przy normalnej definicji REPEATABLE READ nic się nie dzieje. Transakcja modyfikuje wiersz, zatwierdza zmiany, wszystko działa. Co najwyżej jedna z transakcji próbujących odczytać w tym czasie fee będzie musiało chwileczkę zaczekać między writem a committem, jeśli baza stosuje zamki.

Ale gdyby użyć definicji “non-repeatable read jest wtedy, gdy hipotetyczne wykonanie któregoś zapytania jeszcze raz odczyta inny wynik”, to mamy katastrofę! Przecież po modyfikacji fee wszystkie transakcje, które w tym momencie już się wykonywały z poprzednim parametrem fee powodują niepoprawne przeploty! No bo hipotetycznie każda z nich mogłaby chcieć odczytać fee jeszcze raz i otrzymałaby inny wynik. W związku z tym jedynym poprawnym zachowaniem byłoby zatrzymanie całego systemu – nie pozwalamy nowym transakcjom się wykonywać, czekamy aż obecne się skończą, wtedy modyfikujemy fee i puszczamy wszystko na nowo.

Dla poważnej instytucji, która przez 24h na dobę przetwarza setki transakcji na sekundę byłoby to absolutnie niedopuszczalne.

Dlatego właśnie anomalie zdefiniowane są jako rzeczywiste błędne odczyty. Anomalia zachodzi, kiedy już coś jest niespójne, a nie wcześniej.

Praktyka

To, że jest jak jest, można zweryfikować logując się do Oracle’a albo Postgresa i puszczając sobie transakcje z zadania. Na wszystkich poziomach izolacji w Oraclu niepoprawne przeploty się udają. W Postgresie poziom SERIALIZABLE poprawnie wykrywa błąd i nie pozwala drugiej z transakcji się scommittować, bo SERIALIZABLE Postgresa jest mocniejsze niż zdefiniowane w standardzie.

Można się jeszcze zastanawiać jak sztuczny jest to przykład. Z jednej strony w tym przypadku da się bardzo łatwo rozwiązać konflikt po prostu dodając FK constraint między completed a tasks. Wtedy albo A.2 się nie powiedzie, bo nie będzie takiego klucza w tasks, albo B.2, bo usunięcie spowodowałoby naruszenie ograniczenia. Ale ciekawostka jest taka, że jest to bardzo uproszczona wersja problemu z prawdziwego systemu, w którym wykonanie pewnych dwóch operacji jednocześnie dla tego samego obiektu powodowało wyścig blokowany jedynie przez Postgresowe SERIALIZABLE.

back