Lehrgebiet Informationssysteme

FB Informatik

LG IS

AG DBIS

(C) AG DBIS

Eine WAL-basierte und objektorientierte Recovery-Strategie

Fernando de Ferreira Rezende, Thomas Baier

University of Kaiserslautern
P.O. Box 3049, 67653 Kaiserslautern, Germany
e-mail: haerder@informatik.uni-kl.de

Extended abstract (postscript version compressed by gzip)

Abstract:

Wir stellen eine WAL-basierte und objektorientierte Recovery-Strategie (WALORS) vor. WALORS ist geeignet f|r den Einsatz in objektorientierten Datenbanksystemen, da der Recovery-Mechanismus objektbasiert arbeitet und ein Objekt als logische Einheit betrachtet wird. Zur effektiven Realisierung der Recovery-Komponente wird jedes Objekt mit einer LSN (log sequence number) ausgestattet. Die LSN beschreibt den logischen Zeitpunkt, zu dem das Objekt das letzte Mal modifiziert wurde. Jede Dnderungsoperation wird in der Log-Datei in Form eines Log-Satzes mitprotokolliert. Bei der Gewinnung der Log-Informationen benutzt WALORS die Strategie des Eintrags-Logging, welches auf der Objekt-Ebene durchgef|hrt wird. Jeder Log-Satz enthdlt unter anderem auch eine LSN. Die LSN ist monoton wachsend, der jeweils letzte Log-Satz der Log-Datei erhdlt demnach die bis zu diesem Zeitpunkt grv_te LSN. Die LSN wird nicht explizit im Log-Satz vermerkt, sie wird durch die Adresse des Log-Satzes in der Log-Datei reprdsentiert. So kann man sehr effizient auf einen bestimmten Log-Satz in der Log-Datei zugreifen, ohne da_ mit Hilfe von komplizierten Hash-Verfahren aus einer gegebenen LSN die Adresse des entsprechenden Log-Satzes ermittelt werden mu_. Durch die Zuordnung einer LSN zu jedem Log-Satz besitzt jede Dnderungsoperation eine Art logischen Zeitstempel. Wenn man diesen Stempel auch dem Objekt aufdr|ckt, welches durch die entsprechende Dnderungsoperation modifiziert wurde, kann in einem Fehlerfall sehr effizient entschieden werden, ob auf dieses Objekt Recovery-Ma_nahmen anzuwenden sind oder nicht.

Es werden Transaktions-Recovery, Crash-Recovery und Platten-Recovery unterst|tzt. Aktive Transaktionen kvnnen sowohl teilweise (partial rollback) als auch vollstdndig (total rollback) zur|ckgesetzt werden. Bei einem Systemwiederanlauf wird die Log-Datei in drei Durchldufen abgearbeitet. Es erfolgen ein ANALYSE-, ein UNDO- und ein sich anschlie_ender REDO-Lauf. WALORS arbeitet (im Gegensatz zu ARIES [MHLPS89, MoNa94, RoMo89]) mit einer selektiven REDO-Strategie. Es werden lediglich verlorene Dnderungen von Gewinnertransaktionen wiederholt. Dieses Vorgehen ist vorteilhaft, da teuere E/A-Operationen eingespart werden und die Effizienz beim Systemwiederanlauf nach einem Fehler erhvht wird [BHG87]. Bei einer REDO-Strategie hingegen, die alle nicht materialisierten Dnderungen wiederholt (redo all), wird ein Teil der Operationen nur durchgef|hrt, um sie im anschlie_enden UNDO-Lauf wieder zur|ckzusetzen. Der Vorteil des selektiven REDO in Verbindung mit selektivem UNDO ist dadurch gekennzeichnet, da_ Dnderungen von Verlierertransaktionen, die nicht materialisiert wurden, keinen physischen UNDO- bzw. REDO-Aufwand verursachen.

Um festzustellen, welche der vollzogenen Dnderungen zur|ckgesetzt werden m|ssen, wird der LSN-Wert des materialisierten Objekts benutzt. Eine Dnderung mu_ zur|ckgesetzt werden, wenn die Objekt-LSN grv_er oder gleich der LSN des zugehvrigen UNDO-Log-Satzes ist. Ist die Objekt-LSN kleiner als die des Log-Satzes, dann wurde die Dnderung noch nicht in die Datenbank eingebracht und deshalb ist ein UNDO dieser Dnderung auch nicht notwendig. Andererseits mu_ eine Dnderung wiederholt werden, wenn sie noch nicht materialisiert wurde. Dazu wird auch hier die LSN des entsprechenden Log-Satzes mit der Objekt-LSN verglichen. Ist die Objekt-LSN kleiner als die LSN des zugehvrigen REDO-Log-Satzes, dann ist eine Wiederholung der Dnderungsoperation notwendig.

Auf der Basis vergebener LSN-Werte wird auch das WAL-Protokoll (write ahead logging [Gray78]) realisiert. Im Log-Puffer werden tempordr die Log-Sdtze gehalten. Unter Beachtung des WAL-Protokolls werden erst dann die Log-Sdtze in die Log-Datei geschrieben, wenn ein modifiziertes Objekt aus dem Datenpuffer verdrdngt werden soll. In diesem Fall wird die Log-Datei mindestens bis zu der LSN geschrieben, die der Objekt-LSN entspricht. Das WAL-Protokoll garantiert, da_ die zugehvrigen Log-Sdtze in der Log-Datei protokolliert werden (UNDO-Informationen), bevor irgendwelche Dnderungen in die Datenbank eingebracht werden d|rfen. Andererseits, wenn eine Transaktion erfolgreich abgeschlossen wird, m|ssen spdtestens bis zum Commit alle Log-Sdtze dieser Transaktion in die Log-Datei geschrieben werden (REDO-Informationen).

WALORS unterst|tzt eine flexible Pufferverwaltung. Es werden sowohl die Ersetzungsstrategien STEAL und NOSTEAL als auch die Ausschreibstrategien FORCE und NOFORCE unterst|tzt [HaRe83]. Zur Verminderung des Wiederanlaufaufwandes nach dem Auftreten eines Systemfehlers arbeitet WALORS mit Fuzzy-Checkpoints, die das Herausschreiben von gednderten Objekten nicht erzwingen. Im wesentlichen werden nur Statusinformationen in die Log-Datei geschrieben. Dadurch ist der Aufwand f|r das Erzeugen eines Sicherungspunktes sehr gering.

F|r die Protokollierung von Dnderungen, die zur|ckgesetzt werden sollen, wird das Schreiben eines CLRs (compensation log record) veranla_t. Der Aufbau eines CLRs unterscheidet sich nicht wesentlich vom Aufbau eines herkvmmlichen Log-Satzes. Ein CLR enthdlt REDO-Informationen und einen Zeiger auf den Log-Satz derselben Transaktion, der in der R|ckwdrtsverkettung vor dem Log-Satz der zur|ckzusetzenden Dnderung steht. Durch die Existenz eines CLRs f|r jedes Zur|cksetzen einer Dnderungsoperation kann festgestellt werden, ob die protokollierte R|cksetzoperation bereits in die materialisierte Datenbank eingebracht wurde.

Der CLR dient auch zur Durchsetzung der Idempotenz der Recovery-Ma_nahmen. Anhand der CLRs kann man beim Wiederanlauf des Systems erkennen, ob die durch die CLRs beschriebenen UNDO-Operationen bereits materialisiert wurden. Aber im Gegensatz zu dem Vorgehen im Normalbetrieb kann beim Zur|cksetzen einer Transaktion nicht den CLR-Zeigern gefolgt werden, weil das bedeuten w|rde, da_ mvglicherweise Log-Sdtze von noch nicht materialisierten Dnderungen |bersprungen werden w|rden. (Der Grund daf|r ist, da_ WALORS selektives REDO macht und kein REDO-ALL Strategie folgt.) Die Konsequenz ist, da_ man jeden Log-Satz einer Transaktion untersuchen mu_. WALORS lvst das Problem durch die Verwaltung von zwei Ketten f|r die Verlierertransaktionen, eine NON-UNDO-Kette und eine CLR-EXIST-Kette (beide besitzen LIFO-Eigenschaften (last in first out)). Bei der Untersuchung von CLRs wird ein Eintrag in einer der beiden Ketten erzeugt. Wenn die UNDO-Operation bereits durchgef|hrt wurde, gelangt ein Eintrag in die NON-UNDO-Kette. Wurde der CLR noch nicht materialisiert, d. h. die UNDO-Operation noch nicht durchgef|hrt, so wird ein Eintrag in der CLR-EXIST-Kette erzeugt. Beim Lesen eines UPDATE-Log-Satzes wird unter Verwendung der beiden Ketten entschieden, ob der Log-Satz zur|ckgesetzt werden mu_. Existiert in der NON-UNDO-Kette f|r die Dnderung ein Eintrag, so ist die Dnderung bereits zur|ckgesetzt worden. Existiert f|r die Dnderung ein Eintrag in der CLR-EXIST-Kette, dann wird in Abhdngigkeit davon, ob die Dnderung selbst bereits materialisiert wurde, die UNDO-Operation durchgef|hrt. Existiert weder in der NON-UNDO- noch in der CLR-EXIST-Kette ein Eintrag f|r die Dnderungsoperation, so wird, wenn die Dnderung bereits materialisiert wurde, ein CLR geschrieben und die Dnderung zur|ckgesetzt. Mit diesem Verfahren gewdhrleistet WALORS, da_ die UNDO-Operationen in der richtigen Reihenfolge zur|ckgesetzt und keine CLRs von CLRs geschrieben werden.

Schlie_lich arbeitet WALORS mit speziellen UPDATE-Log-Sdtzen f|r Lvsch- und Einf|geoperationen (UPDATE_delete_obj bzw. UPDATE_create_obj), f|r die spezielle CLR-Log-Sdtze eingef|hrt wurden (CLR_create_obj bzw. CLR_delete_obj). F|r detaillierte Informationen sei auf [ReBa96, Baier95] verwiesen, wo auch die Erweiterungen von WALORS f|r Client/Server-Systeme und f|r geschachtelte Transaktionen beschrieben sind.

Published in Proc. of the 7th Workshop on Transaction Concepts, Nieheim-Ostwestfalen, Germany, Jan. 1996. GI Datenbank Rundbrief 17, May 1996.