so:transakcje [mgr Wiki]

[[so:transakcje]]
mgr Wiki

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.

Więcej ...

Zobacz także 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 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

so/transakcje.txt · Last modified: 2006/05/22 10:30 by 213.134.172.237