//Pytanie: "Sposoby implementacji transakcj"//


===== Wprowadzenie =====


Zbiór instrukcji (operacji), które wykonują logicznie spójną funkcję, nazywa się
transakcją (ang. transaction). Podstawową kwestią rozważaną w przetwarzaniu
transakcji jest zachowanie ich niepodzielności pomimo ewentualnych awarii
systemu komputerowego. W tym punkcie opisujemy różne mechanizmy zapewniania
niepodzielności transakcji. Najpierw rozważamy środowisko, w którym w danej
chwili może być wykonywana tylko jedna transakcja.  Następnie bierzemy pod uwagę
przypadek, w którym wiele transakcji przebiega jednocześnie.  

[[so:transakcja_def| Więcej ...]]

Zobacz także [[bazy_danych:transakcje|transakcje w bazach danych]].

===== Odtwarzanie za pomocą rejestru =====


Jednym ze sposobów zapewniania niepodzielności jest zapisywanie w pamię­ci
trwałej informacji określających wszystkie zmiany wykonywane przez transakcję w
danych, do których ma ona dostęp.  Najczęściej stosuje się w tym celu metodę
rejestrowania z wyprzedzeniem (ang.  write-ahead logging). System utrzymuje w
pamięci trwałej strukturę danych nazywaną rejestrem (ang. log). Każdy rekord
rejestru opisuje jedną operację pisania w transakcji i ma następujące pola: 


  * **nazwa transakcji** - jednoznaczna nazwa transakcji wykonującej operację pisania;
  * **nazwa jednostki danych** - jednoznaczna nazwa zapisywanej jednostki danych;
  * **stara wartość** - wartość jednostki danych przed zapisem;
  * **nowa wartość** - wartość jednostki danych po zapisie.  


Rejestr zawiera też inne, specjalne rekordy odnotowujące istotne zdarzenia
występujące podczas przetwarzania transakcji, takie jak początek transakcji oraz
jej zatwierdzenie lub zaniechanie.  

Zanim rozpocznie się wykonywanie transakcji Ti, w rejestrze zapisuje się rekord
**<Ti, rozpoczęcie>**.  Podczas wykonywania transakcji każda należąca do niej
operacja pisz jest poprzedzana zapisaniem odpowiedniego rekordu w rejestrze. Gdy
dochodzi do zatwierdzenia transakcji, wówczas w rejestrze zapisuje się rekord
**<Ti, zatwierdzenie>**.  

Ponieważ informacje w rejestrze są używane do rekonstrukcji stanu danych
przetwarzanych przez różne transakcje, nie możemy pozwolić na faktyczne
uaktualnienie jednostki danych, zanim nie zostanie zapisany odpowiedni rekord w
rejestrze przechowywanym w pamięci trwałej. Żądamy więc, aby przez wykonaniem
operacji ''pisz(X)'', w trwałym rejestrze zapisano rekord dotyczący ''X''.  

Zwróćmy uwagę na straty, jakie przychodzi w takim systemie ponosić na
wydajności. Na każde logiczne zamówienie pisania przypadają dwie fizyczne
operacje zapisu. Potrzeba też więcej pamięci - na same dane oraz na rejestr
wykonanych w nich zmian. Jednak w przypadkach niezwykle ważnych danych i
konieczności szybkiego odtwarzania stanu systemu po awarii cena ta jest
opłacalna.  

Na podstawie rejestru system potrafi poradzić sobie z każdą awarią, która nie
spowodowała zaginięcia danych w pamięci nieulotnej. W algorytmie rekonstrukcji
korzysta się z dwu procedur: 


  * **wycofaj //(ang. undo)//** - ta procedura odtwarza wszystkie dane uaktualnione przez transakcję Ti nadając im stare wartości; 
  * **przywróć //(ang. redo)//** - ta procedura nadaje nowe wartości wszystkim danym uaktualnionym przez transakcję Ti.  



Zbiór danych uaktualnionych przez transakcję Ti oraz odpowiadających im
starych i nowych wartości można odnaleźć w rejestrze. 

Aby zagwarantować poprawność działania nawet w przypadku awarii występującej
podczas odtwarzania, operacje wycofaj i przywróć muszą być idempotentne (tzn.
ich wielokrotne wykonywanie wywołuje takie same skutki jak wykonanie
jednorazowe).


W przypadku zaniechania transakcji Ti odtworzenie stanu zmienionych przez nią
danych odbywa się po prostu przez wykonanie operacji ''wycofaj(Ti)''. Jeśli nastąpi
awaria systemu, to stan wszystkich zmienionych danych jest odtwarzany na
podstawie analizowania rejestru w celu ustalenia, które transakcje należy
przywrócić, a które wycofać. Owa klasyfikacja transakcji przebiega następująco:


  * transakcja Ti musi być wycofana, jeżeli w rejestrze znajduje się rekord **<Ti, rozpoczęcie>**, lecz nie ma w nim rekordu **<Ti, zatwierdzenie>**;
  * transakcja Ti musi być przywrócona, jeżeli rejestr zawiera zarówno rekord **<Ti, rozpoczęcie>**, jak i rekord **<Ti, zatwierdzenie>**.  


===== Punkty kontrolne =====


Po awarii systemu należy przeanalizować rejestr transakcji, aby określić, które
transakcje muszą być przywrócone, a które wycofane. Aby to rozstrzygnąć, w
zasadzie należałoby przeglądnąć cały rejestr. Postępowanie takie ma dwie poważne
wady:


  * Proces przeglądania jest czasochłonny.  
  * Większość transakcji, których skutki, zgodnie z naszym algorytmem, powinny być przywrócone, spowodowało już zaktualizowanie danych, o których na podstawie rejestru można by wnosić, że wymagają modyfikacji.  

Aczkolwiek powtórne wykonanie tych zmian w danych nie spowoduje żadnej szkody
(dzięki idempotentności działań), jednak wydłuży czas rekonstrukcji.  

Aby zmniejszyć tego rodzaju koszty, wprowadza się pojęcie punktów kontrolnych
(ang.  checkpoints). System podczas działania rejestruje z wyprzedzeniem
operacje pisania, a ponadto co pewien czas organizuje punkty kontrolne, w
których należy wykonać następujący ciąg czynności: 


  * Wszystkie rekordy aktualnie pozostające w pamięci ulotnej (zazwyczaj w pamięci operacyjnej) mają być zapisane w pamięci trwałej.  
  * Wszystkie zmienione dane pozostające w pamięci   ulotnej  mają być umieszczone w pamięci trwałej. 
  * W przechowywanym w pamięci trwałej rejestrze transakcji należy zapisać rekord <punkt kontrolny>. 


Obecność rekordu <punkt kontrolny> w rejestrze transakcji pozwala systemowi
upłynnić procedurę rekonstrukcji. Rozważmy transakcję Ti, której zatwierdzenie
nastąpiło przed punktem kontrolnym. Rekord <Ti, zatwierdzenie> pojawia się w
rejestrze przed rekordem <punkt kontrolny>. Wszystkie zmiany dokonane przez
transakcję Ti, musiały być zapisane w pamięci trwałej albo przed punktem
kontrolnym, albo w trakcie wykonywania jego operacji. Wobec tego w czasie
rekonstrukcji wykonywanie operacji przywróć w odniesieniu do transakcji Ti jest
zbyteczne.  

To spostrzeżenie pozwala ulepszyć nasz poprzedni algorytm rekonstrukcji stanu
danych. Po wystąpieniu awarii procedura rekonstrukcji przegląda rejestr w celu
odnalezienia ostatniej transakcji Ti której wykonywanie rozpoczęto przed
wykonaniem ostatniego punktu kontrolnego. Transakcja taka zostaje odnaleziona
przez wsteczne przeszukanie rejestru w celu napotkania pierwszego rekordu <punkt
kontrolny>, a następnie odnalezienie pierwszego rekordu <Ti , rozpoczęcie>
występującego po nim.  

Po zidentyfikowaniu transakcji Ti operacje przywróć i wycofaj wystarczy wykonać
tylko w odniesieniu do transakcji Ti i wszystkich transakcji, których
wykonywanie rozpoczęło się po niej. Oznaczmy zbiór tych transakcji jako T.
Resztę rejestru można więc pominąć. Oto wymagane operacje odtwarzania:      


  * Dla wszystkich transakcji Tk ze zbioru T, dla których w rejestrze występuje rekord <Tk, zatwierdzenie>, należy wykonać operację przywróć(Tk). 
  * Dla wszystkich transakcji Tk ze zbioru T, dla których w rejestrze rekord <Tk, zatwierdzenie> nie występuje, należy wykonać operację wycofaj(Tk).  


===== Współbieżne transakcje niepodzielne =====


Ponieważ każda transakcja jest niepodzielna, współbieżne wykonanie transakcji
musi być równoważne wykonaniu ich jedna po drugiej w pewnym dowolnym porządku.
Ta cecha, zwana szeregowalnością (ang.  serializability), może być
urzeczywistniona przez zwykłe wykonywanie każdej transakcji w sekcji krytycznej.
Należy przez to rozumieć, że wszystkie transakcje korzystają ze wspólnego
semafora mutex, który na początku jest równy 1. Transakcja rozpoczynająca
działanie wykonuje na samym początku operację czekaj(mutex). Gdy transakcja
zostanie zatwierdzona, lub po jej zaniechaniu, wykonuje się operację
sygnalizuj(mutex).  

Ten schemat, choć zapewnia niepodzielność wszystkich współbieżnie wykonywanych
transakcji, jest nazbyt ograniczający. Jak się przekonamy, istnieje wiele
sytuacji, w których można by dopuścić do zachodzenia w tym samym czasie działań
wykonywanych w transakcjach przy zachowaniu szeregowalności. Istnieje kilka
różnych algorytmów sterowania współbieżnością zapewniających [[so:trans_szeregowalnosc|szeregowalność]].
Opisujemy je poniżej. 

==== Protokół blokowania ====

Jeden ze sposobów zapewnienia szeregowalności polega na skojarzeniu z każdym
obiektem danych zamka i wymaganiu, aby w każdej transakcji przestrzegano
protokołu blokowania (ang. locking protocol), rządzącego blokowaniem i
zwalnianiem zasobów. Obiekt danych może być zablokowany na różne sposoby. W tym
punkcie ograniczymy naszą uwagę do dwu trybów blokowania: 


  * Tryb wspólny (ang. shared modę): Jeśli transakcja Ti zajmuje obiekt danych w trybie wspólnym (oznaczanym przez S), to może ona czytać ten obiekt, lecz nie może go zapisywać.  
  * Tryb wyłączny (ang. exclusive modę): Jeśli transakcja Ti zajmuje obiekt danych w trybie wyłącznym (oznaczanym przez X), to wolno jej zarówno czytać, jak i zapisywać ten obiekt.  


Wymaga się, aby każda transakcja zamawiała zamek blokujący obiekt danych Q w
odpowiednim trybie, stosownie do rodzaju operacji, które będzie ona na obiekcie
Q wykonywać.

Transakcja może zwolnić obiekt danych uprzednio przez nią zablokowany. Niemniej
jednak musi ona blokować obiekt danych dopóty, dopóki ma do niego dostęp.
Ponadto natychmiastowe zwalnianie obiektu danych przez transakcję, tuż po
wykonaniu przez nią ostatniego dostępu do obiektu, nie zawsze jest pożądane,
gdyż może to naruszyć szeregowalność jej operacji.  

Jednym z protokołów zapewniających szeregowalność jest protokół blokowania
dwufazowego (ang. two-phase locking protocol).  Protokół ten wymaga, aby każda
transakcja blokowała zasób i zwalniała go w dwu fazach. Są to: 


  * Faza wzrostu (ang. growingphase): Transakcja może zablokować zasób, lecz nie wolno jej zwolnić żadnego z już zablokowanych zasobów.  
  * Faza zmniejszania (ang. shrinking phase): Transakcja może zwolnić zasób, lecz nie wolno jej już blokować nowych zasobów.  


Początkowo transakcja jest w fazie wzrostu, zajmując potrzebne zasoby. Z chwilą
zwolnienia zasobu transakcja wchodzi w fazę zmniejszania, w której nie wolno jej
już blokować nowych zasobów.


Protokół blokowania dwufazowego zapewnia szeregowalność pod względem konfliktów.
Nie chroni jednak przed zakleszczeniem. Zaznaczmy, że dla zbioru transakcji mogą
istnieć uszeregowania pod względem konfliktów, których nie da się otrzymać za
pomocą protokołu blokowania dwufazowego. Jednak w celu uzyskania lepszej
wydajności od tej, którą osiąga się przy zastosowaniu protokołu blokowania
dwufazowego, należy dysponować dodatkowymi informacjami o transakcjach albo
narzucić zbiorowi danych pewną strukturę lub uporządkowanie.

==== Protokoły korzystające ze znaczników czasu ====

W opisanych wyżej protokołach blokowania porządek w każdej parze konfliktowych
transakcji jest określony podczas ich wykonywania, kiedy dochodzi do
zablokowania pierwszego zasobu, o który obie ubiegają się w niezgodnych
trybach. Inna metoda określania kolejności transakcji polega na ich
uporządkowaniu z góry. W jednej z najpopularniejszych metod tego rodzaju stosuje
się schemat uporządkowania według znaczników czasu (ang. timestamp-ordering).

Z każdą transakcją Ti w systemie kojarzymy niepowtarzalny i stały znacznik
czasu; określimy go symbolem ZC(Ti). Transakcja otrzymuje znacznik czasu od
systemu, zanim rozpocznie się jej wykonywanie. Jeśli transakcji Ti przypisano
znacznik czasu ZC(Ti) i w późniejszym czasie w systemie pojawi się nowa
transakcja Tj, to ZC(Ti) < ZC(Tj). Schemat ten można zrealizować dwoma prostymi
sposobami: 


  * Należy użyć w roli znaczników czasu wartości zegara systemowego. Tak więc znacznik czasu transakcji będzie równy wartości zegara systemowego w chwili pojawienia się transakcji w systemie. Metody tej nie można zastosować do transakcji występujących w oddzielnych systemach ani w przypadku procesorów nie korzystających ze wspólnego zegara.  
  * Należy użyć w roli znaczników czasu wskazań licznika logicznego.  W tym przypadku znacznik czasu transakcji jest równy wartości tego licznika w chwili nadejścia transakcji do systemu. Po przypisaniu nowego znacznika czasu licznik ulega zwiększeniu.  


Znaczniki czasu transakcji określają porządek szeregowania transakcji. Jeśli
więc ZC(Ti) < ZC(Tj), to system musi zapewnić, że wytworzony plan jest
równoważny planowi szeregowemu, w którym transakcja Ti występuje przed
transakcją Tj.  

W celu implementacji tego schematu z każdym obiektem danych Q kojarzymy dwa
znaczniki czasu:


  * znacznik-czasu-P(Q) określający największy znacznik czasu transakcji, która pomyślnie wykonała operację pisz(Q); 
  * znacznik-czasu-C(Q) określający największy znacznik czasu transakcji, która pomyślnie wykonała operację czytaj(Q) 


Owe znaczniki czasu są uaktualniane podczas każdego wykonywania instrukcji
czytaj(Q) lub pisz(Q).

Protokół uporządkowania według znaczników czasu zapewnia, że wszelkie
konfliktowe operacje czytaj i pisz będą wykonywane w porządku znaczników czasu.
Protokół ten działa następująco: 	

  * Załóżmy, że transakcja Ti wydaje polecenie czytaj(Q)  
    * Jeśli ZC(Ti) < znacznik-czasu-P(Q) to z tego wynika, że transakcja Ti chce czytać wartość Q, która już została zmieniona. Dlatego operacja czytaj zostaje odrzucona, a transakcja Ti - wycofana.
    * Jeśli ZC(Ti) > znacznik-czasu-P(Q) to wykonuje się operację czytaj oraz określa znacznik-czasu-C(Q) jako maksimum z wartości znacznik-czasu-C(Q) i ZC(Ti).
  * Załóżmy, że transakcja Ti wydaje polecenie pisz(Q)
    * Jeśli ZC(Ti) < znacznik-czasu-C(Q) to z tego wynika, że wytwarzana przez transakcję Ti wartość Q była potrzebna wcześniej i przyjmuje się, że transakcja Ti nigdy nie wytworzyła tej wartości. Wobec tego rezygnuje się z operacji pisz i wycofuje transakcję Ti.
    * Jeśli ZC(Ti) < znacznik-czasu-P(Q) to z tego wynika, że transakcja Ti usiłuje zapisać przestarzałą wartość Q. Dlatego odrzuca się tę operację pisz i wycofuje transakcję Ti.
    * W przeciwnym razie wykonuje się operację pisz. 



Transakcja Ti, która w wyniku żądania wykonania operacji czytaj lub pisz została
przez algorytm sterowania współbieżnością wycofana, otrzymuje nowy znacznik
czasu i jest wznawiana.

Protokół porządkowania według znaczników czasu zapewnia szeregowalność z
uwzględnieniem konfliktów. Wynika to z tego, że konfliktowe operacje są
wykonywane w porządku znaczników czasu. Protokół jest także wolny od
zakleszczeń, ponieważ żadna transakcja nigdy na nic nie czeka.

----
Wyciąłem pare zdań wprowadzenia, ale tu naprawdę nie bardzo jest co wyciąć aby nie stracić treści