\chapter{Sicherungspunkte f"ur Tycoon-interne Zust"ande}
\label{intern-kap}

Die erste Teilaufgabe der Implementierung persistenter Sicherungspunkte in
Tycoon besteht in der Erweiterung des Tycoon-eigenen flachen
Transaktionsmodells.  Dabei ist zu
beachten, da"s in Tycoon der f"ur die Persistenz zust"ande Objektspeicher "uber
ein abstraktes Speicherprotokoll
({\em Tycoon Store Protocol}, im folgenden als {\em TSP} \cite{MMS92}
bezeichnet).
angebunden wird, welches nur flache Transaktionen 
unterst"utzt. Eine Randbedingung bei der Erweiterung ist deshalb die
Beibehaltung der existierenden Speicherarchitektur und damit des
Speicherprotokolls
Um dieser Anforderung gerecht zu werden, sind die Sicherungspunkte durch eine
Schicht oberhalb des TSP implementiert; diese Schicht bietet ein um persistente
Sicherungspunkte
erweitertes, ansonsten aber mit dem TSP identisches, Speicherprotokoll an. Der
Realisierungsansatz beruht auf dem chronologischen Verzeichnen ({\em Logging})
von ge"anderten Objekten und der Abbildung von Sicherungspunkten auf
abgeschlossenen Transaktionen auf der Ebene des Objektspeichers. Zum
Zur"ucksetzen werden dann, analog zu den transaktionalen externen Daten,
kompensierende Operationen auf dem Objektspeicher ausgef"uhrt. 

Dieses Kapitel beginnt mit einer Beschreibung des abstrakten Speicherprotokolls
und seiner architekturellen Erg"anzung durch die Logging-Zwischenschicht. Nach
der Darstellung der Log-Struktur und der Log-Operationen wird auf die
Algorithmen f"ur die transaktionalen Operationen eingegangen. Zum Abschlu"s
wird anhand von Vor"uberlegungen und
empirischer Messungen gezeigt, da"s die Implementierung von
Sicherungspunkten nur einen marginalen Performanzverlust bewirkt.
	
\section{Anforderungen durch das abstrakte Speicherprotokoll}

Die Speicherarchitektur von Tycoon unterscheidet sich grundlegend von der
konventioneller Programmiersprachen, da sie keinen eigenen Objektspeicher
vorsieht, sondern eine flexible Anbindung beliebiger Objektspeicher durch das
abstrakte Speicherprotokoll TSP \cite{MMS92} erlaubt. 
Das TSP ist in seiner Funktionalit"at an einem generischen Objektspeicher
angelehnt und dient dem Tycoon-Laufzeitsystem als alleinige Schnittstelle zum
persistenten Speicher. 
Das Tycoon-Laufzeitsystem verwaltet alle anfallenden Daten "uber das TSP, wobei
auch adminstrative Datenstrukturen von Daten, Programmen und Threads
eingeschlossen
sind. Zur Anpassung eines bestimmten Objektspeichers an Tycoon
mu"s ein Adaptermodul geschrieben werden, welches die TSP-Funktionen mit dem
Objektspeicher implementiert. Der Vorteil eines solchen Konzeptes ist die
leichte Portierbarkeit der Schnittstelle auf beliebige Systeme und die
Einsetzbarkeit selbst der neuesten kommerziellen Objektspeichertechnologie
(beispielsweise existiert eine Anbindung von ObjectStore \cite{LLOW92})
ohne eigenen
Implementierungsaufwand. Die Verwendung eines abstrakten Speicherprotokolls
entspricht deshalb der Tycoon-Philosophie, existierende Technologien in das
System einzubinden anstatt sie zu reimplementieren.
Abbildung~\ref{tycoon-arch1-fig} (aus \cite{Matt93})
gibt einen "Uberblick der Architektur. Die
Abk"urzungen TL, TML und TVM bezeichnen weitere Schichten in der
Tycoon-Architektur und sind in \cite{Matt93} erl"autert.
\begin{figure}[tb]
%\leavevmode
\def\epsfsize#1#2{0.8\textwidth}
\centerline{\epsffile{tycoon-arch1.eps}}
\caption{\label{tycoon-arch1-fig} Die Tycoon-Architektur}
\end{figure}

Das TSP definiert ein bestimmtes Objektmodell sowie eine Reihe von
Objektverwaltungsfunktionen und sieht einen {\em Garbage Collection}-Mechanismus
vor, im folgenden auch als Garbage Collection
bezeichnet. Ein Objekt stellt sich dem
TSP-Anwender als ein Array von beliebigen Werten dar, denen sonst keine
Struktur auferlegt wird und das anhand einer eindeutigen
Objektreferenz ({\em OID})
identifiziert werden kann. Zur Unterst"utzung der Garbage Collection
m"ussen allerdings
Objektreferenzen gesondert markiert sein. Neben den eigentlichen Nutzdaten hat
jedes Objekt auch einen Header, in dem verschiedene Statusinformationen "uber
das Objekt gespeichert werden (beispielsweise ob es ver"anderbar ist).

Objekte werden mit den in mehreren Varianten zur Verf"ugung stehenden
Erzeugungsfunktionen angelegt und sind immer persistent.
Durch die
Garbage Collection
entf"allt die Notwendigkeit f"ur den TSP-Benutzer, Objekte explizit zu
l"oschen. Die Garbage Collection
wird periodisch aufgerufen und entfernt alle nicht mehr
referenzierten Objekt selbstt"atig. Die Lebendigkeit eines Objektes wird anhand
transitiver Erreichbarkeit von eines designierten Wurzelobjekt festgestellt.
Um einen Zugriff auf das Objekt zu erm"oglichen, sind in TSP Funktionen zum
Lesen und Schreiben des Objektinhaltes und einiger Objektattribute vorgesehen. 
"Uber die reine Objektpersistenz hinaus mu"s ein TSP-konformer Objektspeicher
auch flache Transaktionen unterst"utzen. Diese werden in TSP durch die
Funktionen {\sl tsp\_commit()} und {\sl tsp\_rollback()} zur Verf"ugung
gestellt.
Dar"uberhinaus gibt es noch administrative
Funktionen, die jedoch f"ur die vorgenommene Erweiterung keine Bedeutung
haben.

Eine Grundvoraussetzung bei der Implementierung persistenter Sicherungspunkte
war die
Beibehaltung dieser Speicherarchitektur, deren zentrales Element TSP ist.
Deswegen war es nicht m"oglich, die Erweiterung des flachen Transaktionsmodells
direkt in TSP zu verankern.  Statt einer Implementierung von
Sicherungspunkten in der Store-Anpassung werden diese deshalb von einer
Zwischenschicht oberhalb des TSP realisiert. Diese Zwischenschicht
implementiert ein um die fehlenden transaktionalen Operationen wie
{\sl tsp\_savepoint()}
und {\sl tsp\_rollbackTo()} erweitertes TSP. Die erweiterte Architektur ist in
Abbildung~\ref{tycoon-arch2-fig}
dargestellt. Die Zwischenschicht selbst greift selber ausschlie"slich auf
das zugrundeliegende TSP zu und ist damit ebenso portabel und flexibel wie das
Tycoon-Laufzeitsystem; insbesondere stehen damit f"ur jeden TSP-konformen 
Objektspeicher automatisch persistente Sicherungspunkte zur Verf"ugung.
\begin{figure}[tb]
%\leavevmode
\def\epsfsize#1#2{0.8\textwidth}
\centerline{\epsffile{tycoon-arch2.eps}}
\caption{\label{tycoon-arch2-fig} Die erweiterte Tycoon-Architektur}
\end{figure}

Um nun persistente Sicherungspunkte auf einem Objektspeicher zu simulieren, der
nur flache Transaktionen unterst"utzt, wird, genauso wie f"ur transaktionale
externe Daten auch, bei Setzen eines Sicherungspunktes die laufende Transaktion
im Speicher durch eine Commit-Operation
abgeschlossen. Dadurch ergibt sich auch f"ur
Tycoon-interne Daten eine zweistufige Transaktions"`schichtung"'. 
Im folgenden soll deshalb zwischen
Tycoon-Transaktionen, welche durch die erweiterte Zwischenschicht angeboten
werden und Sicherungspunkte enthalten k"onnen, und Store-Transaktionen, welche
zur Implementierung der Tycoon-Transaktionen dienen und nicht mehr direkt
sichtbar sind, unterschieden werden. Das Zur"ucksetzen einer Tycoon-Transaktion
auf einen beliebigen Sicherungspunkt oder den Transaktionsanfang wird durch
Ausf"uhrung kompensierender Store-Operationen durch die Zwischenschicht
erreicht. Die zur Kompensation
erforderlichen Operationen werden anhand der chronologisch in einer
Log-Datenstruktur verzeichneten TSP-Operationen ermittelt. Die Eintragungen in
der Log-Struktur werden als "`Nebeneffekte"' der TSP-Operationen von der
Logging-Zwischenschicht vorgenommen und sind somit transparent f"ur das
Laufzeitsystem und alle h"oheren Ebenen des Tycoon-Systems. Dadurch wird
erreicht, da"s alle persistenten Daten des Tycoon-Systems\footnote{Zu den
persistenten Daten z"ahlen nicht nur die in der Anwendungsebene erzeugten,
sondern auch viele Datenstrukturen des Laufzeitsystems, wie zum Beispiel
der Programm-Stack oder die Liste der Threads.} in der Log-Struktur
ber"ucksichtigt
werden, ohne da"s daf"ur die Architektur des Tycoon-Systems in grundlegender
Weise ge"andert werden m"u"ste. 

Um den Store-Zustand auf einen vorigen Sicherungspunkt zur"uckzusetzen, m"ussen
im Log gen"ugend Informationen zur Kompensation aller seit dem Sicherungspunkt
erfolgten TSP-Operationen vorhanden sein. \cite{HaRe83} sprechen in
diesem Zusammenhang auch von einem Undo-Log. Demhingegen ist es nicht
erforderlich, beim Wiederanlauf den Store-Zustand durch Wiederholung von
TSP-Operationen auf den Stand des letzten gesetzten Sicherungspunktes zu
bringen, da der Tycoon-Sicherungspunkt auf ein Store-Commit
abgebildet und so der Zustand automatisch festgeschrieben wurde. Der
Wiederanlauf wird also im Store wahrgenommen, weswegen in der
Logging-Zwischenschicht keine Redo-Information 
im Log verzeichnet werden mu"s; die Zwischenschicht h"alt also einen reinen
Undo-Log.


\section{Implementationstechniken f"ur Vorw"artsverarbeitung, Zur"ucksetzen und
Wiederanlauf}

In diesem Abschnitt werden die Algorithmen beschrieben, die als Grundlage f"ur
die Implementierung der transaktionalen Operationen ({\sl commit()},
{\sl savepoint()}, {\sl rollbackTo()}) dienen. Als Vorbereitung wird die
Log-Struktur und
die Logging-Aktivit"at w"ahrend des normalen Programmablaufs (der {\em
Vorw"artsverarbeitung}) dargestellt, im Anschlu"s daran wird gezeigt, da"s die
Existenz eines Logs die Wirksamkeit der Garbage Collection nicht
beeintr"achtigt.

\subsection{Logstrukturen f"ur persistente Programmiersprachen mit abstraktem
Speicherprotokoll}

Wie bereits erw"ahnt, werden im Log die kompensierenden Operationen verzeichnet,
die zum Zur"ucksetzen der Tycoon-Transaktion notwendig sind. Ein
naheliegender
Ansatz, der auch h"aufig in relationalen Datenbanksystemen
(siehe zum Beispiel \cite{Gray81,HaRe83,Moha92,GrRe93})
gew"ahlt wird, k"onnte wie folgt
aussehen: Vor jeder "Anderung wird der noch g"ultige Wert im Log verzeichnet,
beim
Zur"ucksetzen wird dann das Log umgekehrt chronologisch abgearbeitet und alle
gesicherten alten Werte werden wiederhergestellt. Auf diese Weise wird
sichergestellt, da"s jede Zustands"anderung garantiert zur"uckgenommen wird.
Dieses Verfahren ist f"ur relationale Datenbanksysteme
durchaus angemessen, sollte jedoch f"ur
persistente Programmiersprachen vermieden werden, weil in diesem Kontext
einzelne Objekte oft mehrfach im Laufe einer Transaktions ge"andert werden
(vergleiche dazu \cite{KGC85}). Beispielsweise kann es vorkommen, da"s eine
Schleifenvariable mehrere hundert "Anderungen in einem sehr kurzen Zeitraum
erf"ahrt. Das sofortige Logging von Undo-Information mit dem Auftreten einer
"Anderung ist aus mehreren Gr"unden zu vermeiden:
\begin{itemize}
\item Es entstehen viele "uberfl"ussige Eintr"age, weil in einer Sequenz von
Undo-Eintr"agen f"ur ein bestimmtes Objekt nur die jeweils ersten nach 
Synchronisationspunkten erforderlich sind.
\item Das Anlegen eines Log-Eintrages stellt einen hohen konstanten Zeitaufwand
f"ur eine "Anderungsoperation dar.
\item Beim Zur"ucksetzen werden entweder eine Menge "uberfl"ussiger Operationen
ausgef"uhrt oder es wird eine Log-Analysephase erforderlich, die die
relevanten Logeintr"age ermittelt. In beiden F"allen ist jedoch mit
zus"atzlichem Aufwand zu rechnen.
\end{itemize}

Das Ziel mu"s es also sein, nur bei der ersten "Anderung eines Objekt zwischen
je zwei Synchronisationspunkten
die notwendige Undo-Information zu verzeichnen und
dies bei Folge"anderungen zu vermeiden. \cite{WhDe95} beschreiben
eine Logging-Variante f"ur
einen Objektspeicher, die auf Seitenbasis kumulierte "Anderungen (also
Redo/Undo-Information) loggt und damit genau diesen Effekt erzielt.  Dieser
Ansatz mu"s f"ur die Anwendung in der Logging-Schicht abge"andert werden,
weil hier keine Speicherseiten sichtbar sind. Da oberhalb des TSP nur
Objekte sichtbar sind, wird die Zwischenschicht Undo-Information auf der Basis
von ganzen Objekten kumulieren. Das implementierte Verfahren funktioniert wie
folgt:
\begin{itemize}
\item Vor der ersten "Anderung eines Objektes nach einem
Synchronisationspunkt wird eine vollst"andige Kopie des Objektes im Log
verzeichnet und das Objekt als kopiert markiert.
\item Folgeoperationen, ganz gleich welchen Teil des Objektes sie betreffen,
erkennen, da"s
das Objekt als geloggt markiert ist und m"ussen selbst kein Logging
mehr durchf"uhren. Der mit jeder "Anderungsoperation verbundene konstante
Zusatzaufwand ist jetzt also auf das Pr"ufen der Markierung reduziert worden
und damit unerheblich (wie auch die sp"ater vorgestellten Messungen beweisen).
\item Beim Zur"ucksetzen wird der vollst"andige Objektzustand, welcher durch
die Kopie verf"ugbar ist, wiederhergestellt.
\end{itemize}

Der Nachteil dieses Verfahrens ist, da"s selbst bei nur partieller "Anderung
eines Objektes immer eine vollst"andige Kopie angelegt wird, so da"s auch
Objektdaten im Log verzeichnet sind, die nicht ge"andert wurden. Als Folge wird
das Log-Volumen erh"oht und das Zur"ucksetzen aufwendiger. Anstelle von
Objektkopien k"onnten deswegen auch {\em Objektdeltas} im Log verzeichnet
werden. Diese enthalten ausschlie"slich den Originalzustand der {\em
ge"anderten} Objektdaten und m"u"sten ermittelt werden, indem vor der ersten
Objekt"anderung eine vollst"andige Kopie angelegt wird, die dann vor dem
n"achsten Synchronisationspunkt mit dem aktuellen Wert des Objektes verglichen
wird. Das Verzeichnen von Objektdeltas setzt aber laufzeitintensive
Analysealgorithmen voraus, weshalb davon abgesehen wurde und stattdessen
vollst"andige Objektkopien im Log verzeichnet werden.
Ein Nachteil ist, da"s
auch gro"se Objekte wie zum Beispiel Audiodaten
vollst"andig kopiert werden, selbst 
wenn darin nur ein kleiner Bereich ge"andert wurde.
Allerdings werden Objekte dieser Art im allgemeinen
als Ganzes gelesen und geschrieben,
so da"s dieses Problem nicht auftritt.

Bei der Implementierung der Log-Struktur stellt sich noch die Frage, ob diese
intern oder extern gespeichert werden soll. Bei einer internen Speicherung ist
das Log eine Datenstruktur im Objektspeicher, z.B. eine verkettete Liste, die
auch durch TSP-Operationen erzeugt und ge"andert wird. Die Objektkopien, die
als Eintr"age im Log verkettet sind, werden bei dieser Alternative ebenfalls im
Store als regul"are Objekte abgespeichert. Bei einer externen Speicherung
wird das Log in einer eigenen Daten au"serhalb des Objektspeichers aufbewahrt.
Die ge"anderten Objekte m"ussen dann in diese Datei kopiert werden, was
technisch aber auch keine Schwierigkeiten bereitet, weil hierbei keine
"`tiefe"' Kopie aller transitiv erreichbaren Objekte erforderlich ist. Bei der
externen Speicherung besteht das Potential zur h"oheren Performanz als bei
einer Speicherung im Objektspeicher, weil extern das Speicherformat, z.B. als
rein sequentiell beschriebene Datei auf einer dedizierten Platte, optimiert
werden kann. Hierbei ergibt sich aber die Schwierigkeit, da"s die
Durchf"uhrung eines Store-Commit mit dem externen Log "uber ein zweiphasiges
Commitprotokoll (\cite{Gray78,BHG87})
synchronisiert werden m"u"ste, da sonst die
Konsistenz des externen Logs nicht garantiert werden kann. Hinzu kommt, da"s
die in den Objektkopien enthaltenen Referenzen auf andere Objekte bei jeder
Garbage Collection aktualisiert werden m"ussen, da sich Objektreferenzen dadurch
"andern k"onnen. Bei Verzeichnen der Objektkopie im Objektspeicher wird
die Aktualisierung der OIDs selbstt"atig bei der Garbage Collection
vorgenommen. Die erh"ohte
Komplexit"at, die eine externe Speicherung der Logstruktur mit sich bringt,
stellt den erzielbaren Performanzgewinn in Frage und f"uhrte zu der
Entscheidung, die Logstruktur intern zu speichern.

Die Logstruktur wird in der Zwischenschicht als Liste
von Logeintr"agen, bei denen es sich im wesentlichem um Objektkopien handelt,
mit Hilfe des darunterliegenden Objektspeichers realisiert. Die Objektkopien
sind folglich f"ur den Objektspeicher persistente Objekte, die von denen der
Tycoon-Laufzeitumgebung nicht zu unterscheiden sind. Wird bei einem
Sicherungspunkt ein Store-Commit durchgef"uhrt, dient dies auch gleichzeitig
zur Sicherung der Logstruktur. Wird ein Objekt wiederholt "uber den Verlauf
mehrerer Sicherungspunkte ge"andert, mu"s f"ur jeden der Sicherungspunkte genau
eine Kopie im Log vorhanden sein; somit l"auft dieses Loggingverfahren auf eine
auf die Sicherungspunkte ausgerichtete Objektversionierung heraus.

Nach dieser "Ubersicht sollen an dieser Stelle die Vorteile
zusammengefa"st werden, die sich aus der Abbildung eines
Tycoon-Sicherungspunktes auf ein Store-Commit ergeben:
\begin{itemize}
\item Durch die Sicherung des Store-Zustandes durch ein Commit ist es nicht
erforderlich, im Log auch Redo-Information zu verzeichnen, was das Logvolumen
reduziert und auch den Laufzeitaufwand verringert.
\item Aus diesem Grund wird auch der Wiederanlauf erheblich vereinfacht, weil
der Objektspeicher automatisch auf den Stand des letzten Sicherungspunktes
gebracht wird. 
\item Da das Log nur f"ur das Zur"ucksetzen ben"otigt wird, kann der Log-Inhalt
bei einem Tycoon-Commit gel"oscht werden.  In
relationalen Datenbanksystemen
ist daf"ur ein aufwendiger Checkpointmechanismus in
Verbindung mit einer Logarchivierung erforderlich (siehe auch wieder
\cite{Gray81,Moha92,BHG87}).
\end{itemize}

\subsection{Loggingaktivit"at w"ahrend der Vorw"artsverarbeitung}

Die zum Zur"ucksetzen ben"otigte Undo-Information mu"s w"ahrend der
Vorw"artsverarbeitung in Form von Logeintr"agen gesammelt werden. Bei diesen
handelt es sich weitgehend um Objektkopien, teilweise kommt man aber auch mit
weniger Information aus. Im folgenden wird f"ur jede einzelne Operation bzw.
Operationsgruppe mit Seiteneffekten beschrieben, welche Logging-Operationen
f"ur diese
in der Zwischenschicht ausgef"uhrt werden. Abbildung~\ref{interneintraege-fig}
zeigt anhand eines Beispiels die verschiedenen Log-Eintr"age.
\begin{figure}[tb]
%\leavevmode
\def\epsfsize#1#2{0.8\textwidth}
\centerline{\epsffile{interneintraege.eps}}
\caption{\label{interneintraege-fig} Ausschnitt aus der Log-Struktur mit
Neuliste}
\end{figure}

\paragraph{"Anderungsoperationen} Dazu geh"oren alle Funktionen zum Setzen
eines Slots oder eines Header-Datums von einem Objekt sowie die Funktion
{\sl tsp\_openReadWrite()}, die an sich noch keine "Anderung durchf"uhrt, aber
vorbereitet. Vor Ausf"uhrung der "Anderung wird eine vollst"andige Objektkopie
mitsamt dem Header angelegt und ein Log-Eintrag
mit zwei Teilfeldern konstruiert.
Das erste Teilfeld enth"alt eine Referenz auf die Objektkopie, das zweite eine
Referenz auf das Originalobjekt. Im Anschlu"s daran wird das Originalobjekt
durch ein Feld in seinem Header als kopiert markiert, so da"s keine weiteren
Kopien von darauffolgenden "Anderungsoperationen angelegt werden.

\paragraph{"Anderung der Wurzel des Objektspeichers} Da es sich bei der Wurzel
des Objektspeichers nicht um ein Objekt mit einem Header handelt, mu"s die
"Anderung dieses "`Objektes"' gesondert behandelt werden. Zu diesem Zweck wird
ein eigener Log-Eintrag f"ur diese "Anderungsoperation festgelegt, der den alten
Wurzelwert enth"alt. Da die Wurzel nicht als kopiert markiert werden kann, wird
diese Tatsache in einer booleschen Variablen in der Zwischenschicht
gespeichert, die bei darauffolgenden Wurzel"anderungen abgepr"uft wird. 

\paragraph{Objekterzeugung} Um die Objekterzeugung zu kompensieren, m"u"ste das
Objekt wieder gel"oscht werden. Weil aber das L"oschen von Objekten automatisch
durch die Garbage Collection
durchgef"uhrt wird, ist f"ur die Objekterzeugung keinerlei
Undo-Information n"otig. Es mu"s nur gew"ahrleistet sein, da"s beim
Zur"ucksetzen alle Referenzen auf das neuangelegte Objekt entfernt werden, was
durch die Kompensation der Objekt"anderungen der referenzierenden Objekte
erreicht wird. Um neuangelegte Objekte davor zu bewahren, "uberfl"ussigerweise
bei einer darauffolgenden "Anderungsoperation kopiert zu werden, werden die
neuen Objekte bereits initial 
als "`kopiert"' markiert. Zus"atzlich werden sie f"ur die im
n"achsten Abschnitt beschriebenen transaktionalen Algorithmen in eine eigene
Liste, die Neuliste, eingetragen. Diese Liste mu"s ebenso wie die Log-Liste im
Store gespeichert sein, damit die enthaltenen Objektreferenzen nicht durch eine
Garbage Collection ung"ultig werden.

\paragraph{"Anderung der Objektgr"o"se} Das TSP unterst"utzt auch die "Anderung
der Slot-Anzahl eines Objektes, wobei es dem Adaptionsmodul des jeweiligen
Objektspeichers "uberlassen ist, wie dies implementiert ist. Bei einem
{\sl tsp\_resize()} kann deshalb das Objekt direkt ver"andert werden, es ist aber
auch m"oglich, da"s eine Kopie des Objektes mit ge"anderter Slot-Anzahl angelegt
wird. Selbst innerhalb eines Stores mu"s dies nicht einheitlich geregelt sein;
so ist es zul"assig, da"s beim Vergr"o"sern eines Objektes ein neues angelegt
wird und beim Verkleinern das Objekt ge"andert wird. Aus diesem Grund ist es
nicht m"oglich, eine Objektverkleinerung durch eine Vergr"o"serung auf die alte
Gr"o"se zu kompensieren (auch nicht bei Nachlieferung der fehlenden Slotwerte):
wird die Verkleinerung direkt am Objekt vorgenommen, bei der kompensierenden
Vergr"o"serung aber ein neues Objekt angelegt, m"u"sten auch die
referenzierenden Objekte aktualisiert werden, was unm"oglich ist. In der
Logging-Zwischenschicht wird deshalb die "`Gr"o"sen"anderung"' selbst
vorgenommen, indem eine Objektkopie mit der geforderten Slotanzahl nach dem
vorigen Schema (Markierung als kopiert und Eintrag in Neuliste) angelegt wird.
Das Originalobjekt mit der
alten Slot-Anzahl mu"s nicht explizit im Log verzeichnet
werden, weil dieses durch die bestehenden Referenzen noch erreichbar ist.
Falls ein in der Gr"o"se zu "anderndes Objekt bereits als kopiert markiert ist,
kann auf das explizite Anlegen einer Kopie verzichtet und die Store-Funktion
{\sl tsp\_resize()}
aufgerufen werden, weil diese Gr"o"sen"anderung nicht kompensiert
werden mu"s. 

\subsection{Beschreibung der Transaktionsalgorithmen}

Die transaktionalen Operationen {\sl tsp\_commit()}, {\sl tsp\_savepoint()},
{\sl tsp\_rollback()}  und {\sl tsp\_rollbackTo()}
werden unter Zuhilfenahme des Logs und der
Store-Transaktionen implementiert. 

Beim Setzen eines Synchronisationspunktes ist es notwendig, die Markierungen
der kopierten Objekte wieder zur"uckzunehmen, damit bei der n"achsten darauf
folgenden "Anderungsoperation erneut eine Kopie angelegt wird. Wie bereits
erw"ahnt, handelt es sich bei den markierten Objekten einmal um ge"anderte
Objekte, f"ur die Logeintr"age erzeugt wurde, und um neu angelegte Objekte.
Bei den ersteren kann die Kopie-Markierung einfach bei einem Log-Durchlauf 
zur"uckgesetzt werden, die neuen Objekte sind "uber eine gesonderte Liste
erreichbar. 
F"ur das Setzen eines Sicherungspunktes werden folgende Schritte ausgef"uhrt:
\begin{enumerate}
\item Durchlauf des Logs bis zum letzten Sicherungspunkt oder alternativ bis
zum Anfang des Logs, wobei die Markierung der kopierten Originalobjekte
zur"uckgesetzt wird;
\item Durchlauf der Neuliste mit Zur"ucksetzen der Markierung der
neu angelegten
Objekte; danach kann der Inhalt der Neuliste "`gel"oscht"' werden (Referenz
wird entfernt);
\item Schreiben eines Log-Eintrages zur Markierung des Sicherungspunktes; dieser
Log-Eintrag enth"alt die Nummer des Sicherungspunktes und dient als Zielmarke
der Funktion {\sl tsp\_rollbackTo}
sowie beim Zur"ucksetzen der Objektmarkierungen in
Schritt 1 dieser Operation;
\item Ausf"uhrung eines Store-Commit, um den Zustand des
Tycoon-Systems und des Logs festzuschreiben.
\end{enumerate}
Abbildung~\ref{internlog-fig} zeigt den Log-Ausschnitt aus
Abbildung~\ref{interneintraege-fig} nach Setzen eines Sicherungspunktes.
Zur Durchf"uhrung eines Tycoon-Commit werden nahezu dieselben Schritte
ausgef"uhrt. Der einzige Unterschied ist, da"s statt einen Log-Eintrag f"ur das
Commit zu schreiben das Log abgeschnitten wird. 
\begin{figure}[tb]
%\leavevmode
\def\epsfsize#1#2{1.1\textwidth}
\centerline{\epsffile{internlog.eps}}
\caption{\label{internlog-fig} Logstruktur mit Neuliste nach Sicherungspunkt}
\end{figure}

Um den Zustand des Objektspeichers bis zu einem bestimmten Sicherungspunkt
zur"uckzusetzen, werden die Logeintr"age in umgekehrt chronologischer
Reihenfolge abgearbeitet, bis man beim geforderten Sicherungspunkt angelangt
ist. Letzteres l"a"st sich "uber die im Log vorhandenen Eintr"age f"ur
Sicherungspunkte feststellen. Bei Antreffen eines "Anderungseintrages wird die
Kopie wieder auf das Originalobjekt vollst"andig zur"uckkopiert; bei Antreffen
eines Eintrags f"ur eine "Anderung der Wurzel wird der im Eintrag
enthaltene Wert auf die Wurzel zur"uckkopiert.
Bei Erreichen des Log-Eintrages f"ur den anvisierten Sicherungspunkt wird das
Log hinter diesem Eintrag abgeschnitten, so da"s auch auf Seiten des Logs der
zum Zielsicherungspunkt
g"ultige Zustand wieder vollst"andig hergestellt ist. Zum Abschlu"s
mu"s ein Store-Commit durchgef"uhrt werden, um den restaurierten Zustand
festzuschreiben. Handelt es sich beim den angepeilten Sicherungspunkt um den
letzten gesetzen, ist die Ausf"uhrung einer kompensierenden
Store-Transaktion nicht notwendig und die Durchf"uhrung eines Store-Rollbacks
gen"ugt.

\subsection{Interaktion von Logging und Garbage Collection}

Da die Log-Struktur im Store gespeichert wird, ist sie einerseits der Garbage
Collection unterworfen, andererseits beeinflu"st sie die Garbage Collection
aber auch, weil in den Log-Eintr"agen teilweise Referenzen auf Objekte vorhanden
sind, die sonst nicht weiter referenziert werden. Beim Zusammenwirken von
Logging und Garbage Collection m"ussen die folgenden beiden Ph"anomene
unbedingt vermieden werden.
\begin{itemize}
\item Teile der Logstruktur oder der dazugeh"origen Daten wie z.B. Objektkopien
werden durch die Garbage Collection
entfernt und bewirken ein Scheitern des Zur"ucksetzens.
Dieser Effekt kann unm"oglich eintreten, weil eine Referenz auf den Anfang der
Log-Liste persistent und von der Speicherwurzel aus transitiv erreichbar
gespeichert wird, somit die gesamte Logliste transitiv erreichbar ist und bei
einer Garbage Collection
nicht entfernt wird. Gleiches gilt f"ur die von den Log-Eintr"agen
referenzierten Objektkopien sowie f"ur die Liste der neu angelegten Objekte,
deren Anfang auch transitiv vom Wurzelobjekt erreichbar ist.
\item Die Garbage Collection
wird durch das Logging behindert, weil in der Log-Struktur
Referenzen auf Objekte enthalten sind, die auch beim Zur"ucksetzen nicht mehr
gebraucht werden. Hierdurch wird Speicherplatz verschwendet und letztlich die
Performanz des Systems beeintr"achtigt.
\end{itemize}
Der letzte Punkt l"a"st sich durch eine Analyse der Log-Struktur und des
Logging-Verhaltens widerlegen.

Am h"aufigsten sind im Log "Anderungseintr"age zu finden, die f"ur ein
eventuelles
Zur"ucksetzen ben"otigt werden und demzufolge wie schon im ersten Punkt erw"ahnt
nicht entfernt werden d"urfen. Durch die Markierung der im Log verzeichneten
Objekte wird
verhindert, da"s pro Sicherungspunkt und ge"andertem Objekt mehr als eine Kopie
angelegt wird. Wird ein Sicherungspunkt durch ein Tycoon-Commit unerreichbar,
wird durch Abschneiden des Logs sichergestellt, da"s auch alle mit diesem
Sicherungspunkt zusammenh"angenden Log-Eintr"age und Objektkopien nicht mehr
transitiv erreichbar sind. Es kann vorkommen, da"s Objektkopien Referenzen auf
ansonsten unreferenzierte (und auch nicht im Log verzeichnete)
Objekte enthalten; diese
d"urfen aber auch nicht durch eine Garbage Collection
entfernt werden, weil sie f"ur ein
eventuelles Zur"ucksetzen erhalten werden m"ussen. 

Die einzige Behinderung der Garbage Collection
entsteht bei tempor"aren Objekten wie z.B.
lokalen Variablen, die beim Eintritt in eine Funktion angelegt werden und
eigentlich gleich bei Verlassen der Funktion entfernt werden k"onnten. Da eine
Referenz auf diese Objekte in der Neuliste verzeichnet wird, und diese Liste
erst beim n"achsten Sicherungspunkt aufgel"ost wird, besteht immer mindestens
eine Referenz auf die tempor"aren Objekte, so da"s eine fr"uhzeitige Garbage
Collection der
"uberfl"ussigen tempor"aren Objekte verhindert wird. Dieses Problem k"onnte
durch die Einf"uhrung sogenannter schwacher Referenzen ({\em weak
references}, dazu Ref??) verhindert werden. Diese werden von der Garbage
Collection
nicht als
vollwertige Referenzen behandelt und ein ausschlie"slich schwach referenziertes
Objekt wird trotzdem entfernt, allerdings werden die bestehenden schwachen
Referenzen auf ung"ultige Werte gesetzt. W"urde das TSP einen solchen
Mechanismus vorsehen, lie"sen sich die neuen Objekte durch schwache Referenzen
in der Neuliste verzeichnen und die Garbage Collection f"ur die neuen Objekt
k"onnten ungehindert stattfinden.

Zusammenfassend kann gesagt werden, da"s ein sinnvolles
Zusammenwirken von Logging und
Gargabe Collection mit vertretbarem Aufwand erreicht wurde. Der derzeitige
Implementierungsstand ist in dieser Hinsicht bereits fast optimal und kann nur
noch mit der Einf"uhrung schwacher Referenzen verbessert werden.


\section{Bewertung des Logging-Verfahrens}

Durch die Logging-Zwischenschicht entsteht f"ur viele TSP-Funktionen ein
Zusatzaufwand, der, wenn er zu hoch w"are, die Einsetzbarkeit des gew"ahlten
Implementierungsansatzes in Frage stellen w"urde.
Empirische Vergleichsmessungen
einiger ausgew"ahlter Tycoon-Programme best"atigen allerdings, da"s der durch
die Logstruktur erforderliche Zusatzaufwand weniger als 30\%
Performanzunterschied
mit sich bringt. Bevor die Vergleichsmessungen pr"asentiert werden, soll noch
einmal die Belastung der Operationen durch das Logging zusammengefa"st werden.
Zum Abschlu"s wird das in diesem Kapitel entwickelte Verfahren einem anderen
f"ur Tycoon entwickelten Logging-Ansatz (\cite{Nied92}) gegen"ubergestellt.

Loggingaktivit"at ist nur bei Operationen mit einem Seiteneffekten
(z.B. Objekt"anderung, aber auch Erzeugung) oder bei
transaktionalen Operationen, die auf das Log zur"uckgreifen m"ussen,
erforderlich. Im einzelnen lassen sich folgende
Zusatzaufw"ande feststellen:
\begin{itemize}
\item Bei wiederholter "Anderung eines Objektes wird zuerst eine Kopie angelegt
und im Log verzeichnet, danach werden nur noch die Kopie-Markierungen gepr"uft.
Der mit dem Pr"ufen der Markierung verbundene Aufwand ist sehr klein und kann
daher vernachl"assigt werden. Der mit dem Kopieren eines Objektes und Anlegen
eines Log-Eintrages verbundene hohe Aufwand mu"s auf die gesamte Anzahl der
"Anderungsoperationen umgelegt werden. Mit steigender Anzahl von
"Anderungsoperationen f"ur ein bestimmtes Objekt nimmt folglich der
Zusatzaufwand pro Einzeloperation ab.
\item Objekterzeugungen haben demgegen"uber h"ohere konstante Zusatzkosten,
weil damit auch immer die Erzeugung eines Eintrages f"ur die Neuliste verbunden
ist. Objekterzeugungen sind jedoch im Vergleich zu Objekt"anderung seltener,
weswegen man erwarten kann, da"s die hohen Zusatzkosten der Objekterzeugung
w"ahrend der Laufzeit weniger ins Gewicht fallen.
\item Die "Anderung der Wurzel des Objektspeichers wird immer von der Erzeugung
eines Log-Eintrages begleitet und hat so ebenfalls hohe konstante Zusatzkosten.
Diese Operation ist aber so selten, da"s die damit verbundenen Kosten
unbedeutend sind.
\item Der Aufwand zum Setzen eines Synchronisationspunktes durch {\sl
transaction.commit()} oder {\sl transaction.savepoint()} erh"oht sich
gegen"uber der Durchf"uhrung einer Store-Commit-Operation ebenfalls, weil
zus"atzlich noch Log und Neuliste inspiziert werden. Allerdings wird immer nur
ein Ausschnitt des Logs inspiziert und die Neuliste anschlie"send entfernt, so
da"s der auf die TSP-Operationen umgelegte Zusatzaufwand konstant ist und nicht
mit der Anzahl der Synchronisationspunkte ansteigt.
\end{itemize}

Die Auswirkungen der Logging-Aktivit"at auf die Laufzeit wurde in einem
Tycoon-System durch Kompilation mehrere Module gemessen. Der Grund f"ur die
Auswahl von Kompilationsvorg"angen als Basis der Messungen war, da"s
die Kompilation
sehr rechenintensiv ist und viele Schreib- und Lesezugriffe macht, aber auch
viele tempor"are Objekte erzeugt, so da"s alle TSP-Operationen in einem
ausgewogenen Verh"altnis in Anspruch genommen werden. Die Messungen wurden
wiederholt mit und ohne Logging f"ur zwei Module der Standardbibliothek, {\sl
print} und {\sl int}, durchgef"uhrt; die gemittelten Me"sergebnisse sind in
Tabelle~\ref{perf-tab} abgebildet. Man kann an den Zahlen erkennen, da"s der
Performanzunterschied 30\% nicht "ubersteigt. Eine Messung des durch Logging
entstehenden zus"atzlichen Platzbedarf wurde vorerst unterlassen, weil mit dem
Fehlen von schwachen Referenzen im TSP noch keine Garbage Collection von
tempor"aren Objekten m"oglich ist.
\begin{table}[tbh]
\begin{tabular}{l|lll}
&ohne Logging&mit Logging&Performanzverlust\\
\hline
Kompilation Modul {\sl print}&23 s&31 s&25,9 \%\\
Kompilation Modul {\sl int}&35 s&48 s&27,1 \% 
\end{tabular}
\caption{\label{perf-tab} Resultate der Performanzmessungen beim Einsatz vom
Logging}
\end{table}
% die Vergleichswerte f"ur die Storegr"osse waren:
%			mit logging 		ohne logging
% leer			2573000			2572972
% nach import von stdenv			4911500
% (Sichern durch Savept) 8713236
% (Sichern durch Commit) 5103672

In \cite{Nied92} wird ein Verfahren zur Implementation von Transaktionen auf
Tycoon-internen Daten vorgestellt, das auch auf einem im Tycoon-Store
liegenden Undo-Log basiert. Die Arbeit spricht auch eine Erweiterung zur
Unterst"utzung von Sicherungspunkten an und schl"agt ebenfalls vor, f"ur
diese spezielle Eintr"age im Log zu verzeichnen. Im Unterschied zu dem in
diesem Kapitel entwickelten Verfahren wird aber das Logging in der
Anwendungsebene durchgef"uhrt, weshalb im Log als Kompensationsinformation
Operationen verzeichnet werden.\footnote{Es handelt sich also um ein
Operations-Logging-Verfahren, das jedoch nicht f"ur fl"uchtige oder
transaktionale externe Daten geeignet ist und sich auch vollst"andig von den
in den n"achsten beiden Kapiteln vorgestellten Verfahren unterscheidet.}
Ein solches Verfahren hat zwei prinzipielle
Nachteile gegen"uber einem Logging-Verfahren auf TSP-Ebene. Zum einen mu"s
die Anwendung selbst das Logging durchf"uhren, was den Implementationsaufwand
des Anwendungsprogrammierers deutlich erh"oht. Zum anderen ist es nicht
m"oglich, den vollst"andigen Anwendungszustand in das Transaktionskonzept
einzubeziehen, weil beispielsweise interne Datenstrukturen wie die
Thread-Liste des
Laufzeitsystems nicht in der Anwendungsebene zur Verf"ugung stehen. Folglich
k"onnen deren Modifikation im Verlauf einer Transaktion auch nicht durch
Ausf"uhrung von im Log verzeichneten Operationen in der Anwendungsebene
kompensiert werden.

