DE69126066T2

DE69126066T2 - Verfahren und Gerät zur Optimierung des Logbuchaufhebungsgebrauchs

Info

Publication number: DE69126066T2
Application number: DE69126066T
Authority: DE
Inventors: Ashok M Joshi; David B Lomet; Ananth Raghavan; Tirumanjanam K Rengarajan; Peter M Spiro
Original assignee: Oracle Corp
Current assignee: Oracle International Corp
Priority date: 1990-06-29
Filing date: 1991-06-11
Publication date: 1997-09-25
Anticipated expiration: 2011-06-12
Also published as: EP0465018A3; JPH0683682A; JP2501152B2; KR940008605B1; EP0465018A2; US5524205A; EP0465018B1; DE69126066D1; KR920001347A

Description

Diese Anmeldung entspricht dem US-Patent 5 524 205.
Die vorliegende Erfindung bezieht sich allgemein auf das Gebiet der Behebung von bzw. des Neustarts nach Abstürzen in Gemeinschaftsplattensystemen, und insbesondere auf den Gebrauch von Logbüchern oder Protokollen bei einer solchen Behebung.
Alle Computersysteme können Daten verlieren, wenn der Computer abstürzt. Einige Systeme, wie Datenbanksysteme, sind besonders anfällig für den möglichen Verlust von Daten bei einem Systemausfall oder Absturz, da diese Systeme große Datenmengen zwischen Platten und Prozessorspeicher hin und her übertragen.
Die gewöhnliche Ursache für Datenverlust ist unvollständige Datenübertragung von einem flüchtigen Speichersystem (z.B. Prozessorspeicher) zu einem Dauerspeichersystem (z.B. Platte). Häufig kommt die unvollständige Datenübertragung vor, weil gerade eine Transaktion stattfindet, wenn sich ein Absturz ereignet. Eine Transaktion beinhaltet allgemein die Übertragung einer Reihe von Datensätzen (oder Veränderungen) zwischen den beiden Speichersystemen.
Ein Konzept, das wichtig ist beim Adressieren von Datenverlust und Wiedergewinnung bzw. Neustart nach dem Verlust, ist die Idee des "Quittierens" einer Transaktion. Eine Transaktion ist "quittiert", wenn einige Sicherheit besteht, daß alle Wirkungen der Transaktion fest im Dauerspeicher sind. Wenn sich ein Absturz ereignet bevor eine Transaktion quittiert, sind die für die Wiedergewinnung erforderlichen Schritte verschieden von denen, die für die Wiedergewinnung erforderlich sind, wenn sich ein Absturz ereignet, nachdem eine Transaktion quittiert. Wiedergewinnung ist das Verfahren des Vornehmens von Korrekturen an einer Datenbank, die dem gesamten System ermöglichen, an einem bekannten und gewünschten Punkt neu zu starten.
Die Art der Wiedergewinnung, die benötigt wird, hängt natürlich von der Ursache für den Datenverlust ab. Wenn ein Computersystem abstürzt, muß die Wiedergewinnung die Wiederherstellung des Dauerspeichers des Computersystems, z.B. Platten, in einen Zustand ermöglichen, der mit dem übereinstimmt, der mit dem durch die letzten quittierten Transaktionen erzeugten vereinbar ist. Wenn der Dauerspeicher abstürzt (Speichermedienausfall genannt), muß die Wiedergewinnung die auf der Platte gespeicherten Daten wiederherstellen.
Viele Wege zur Wiedergewinnung von Datenbanksystemen beinhalten den Gebrauch von Logbüchern. Logbücher oder Protokolle sind lediglich Auflistungen von nach der Zeit geordneten Aktionen, die, wenigstens im Fall von Datenbanksystemen, anzeigen, welche Anderungen an der Datenbank vorgenommen und in welcher Reihenfolge diese Anderungen durchgeführt wurden. Die Logbücher ermöglichen folglich einem Computersystem, die Datenbank in einen bekannten und gewünschten Zustand zu versetzen, der dann dazu benutzt werden kann, Anderungen nochmals vorzunehmen (Redo) oder rückgängig zu machen (Undo).
Logbücher sind jedoch in Systemkonfigurationen, in denen mehrere Computersysteme, "Netzwerkknoten" genannt, auf eine Sammlung von Gemeinschaftsplatten zugreifen, schwierig zu verwalten. Diese Art der Konfiguration wird "Cluster" oder "Gemeinschaftsplatten"-System genannt. Ein System, das allen Netzwerkknoten in einem solchen System ermöglicht auf sämtliche Daten zuzugreifen, wird "Datenverbund"-System genannt.
Ein Datenverbund-System führt "Datenversand" aus, durch den die Datenblöcke selbst von der Platte zum anfordernden Computer gesendet werden. Im Gegensatz dazu versendet ein Funktionsversand-System, besser bekannt als "partitioniertes" System, eine Sammlung von Operationen zur Partitionierung der Daten an den Computer, der als "Server" bestimmt ist. Der Server führt dann die Operationen aus und sendet die Ergebnisse zurück zum Anforderer.
In partitionierten Systemen, ebenso wie in Einfachknotenoder zentralisierten Systemen, kann jeder Datenteil im Lokalspeicher höchstens eines Netzwerkknotens liegen. Ferner müssen sowohl partitionierte Systeme als auch zentralisierte Systeme nur in einem einzelnen Logbuch Aktionen aufzeichnen.
Genauso wichtig kann Datenwiedergewinnung allein gestützt auf den Inhalt eines einzigen Logbuchs vor sich gehen.
Verteilte Datenversand-Systeme sind auf der anderen Seite dezentralisiert, so können die gleichen Daten in den Lokalspeichern mehrerer Netzwerkknoten liegen und von diesen Netzwerkknoten aktualisiert werden. Dies führt zu mehreren Netzwerkknoten-Protokollieraktionen für die gleichen Daten. Zur Vermeidung des Problems mehrerer Logbücher, die Aktionen für die gleichen Daten enthalten, kann ein Datenverbund-System erfordern, daß die Logbuchaufzeichnungen für die Daten zu einem einzelnen Logbuch zurückgesendet werden, das für die Aufzeichnung von Wiedergewinnungsinformation für die Daten verantwortlich ist. Eine solche "Fern - Protokollierung verlangt jedoch zusätzliche System-Ressourcen, da außer den Ein-/Ausgabe-Schreibvorgängen für das Logbuch zusätzliche Mitteilungen benötigt werden, die die Protokollaufzeichnungen enthalten. Außerdem kann die Verzögerung durch das Warten auf eine Quittierung vom protokollierenden Computer beträchtlich sein. Das verlängert nicht nur die Reaktionszeit, sondern kann auch die Fähigkeit verringern, mehreren Benutzern den Mehrfachzugriff auf die gleiche Datenbank zu ermöglichen.
Eine andere Alternative besteht darin, die Benutzung eines gemeinsamen Logbuchs durch gegenseitiges Abwechseln beim Schreiben in dieses Logbuch zu synchronisieren. Das ist zu teuer, da es zusätzliche Mitteilungen für die Koordination erfordert.
Es ist wichtig diese Schwierigkeiten anzugehen, da Datenverbund-Systeme häufig partitionierten Systemen vorzuziehen sind. Datenverbund-Systeme sind beispielsweise wichtig für Arbeitsplatzrechner und Anwendungen der konstruktiven Entwicklung, da Datenverbund-Systeme den Arbeitsplatzrechnern ermöglichen, Daten für ausgedehnte Zeiträume in einem Cache-Speicher abzulegen, was lokale Datenverarbeitung mit hoher Leistung ermöglicht. Weiterhin sind Datenverbund-Systeme dem Wesen nach fehlertolerant und belastungsausgleichend, da eine Vielzahl von Netzwerkknoten auf die Daten gleichzeitig zugreifen, einige lokale Daten selbst verwalten und andere Daten mit anderen Hauptrechnern und Arbeitsplatzrechnern gemeinsam nutzen kann.
Der "IBM Research report RJ 6649 Januar 1989, Seiten 1-45" diskutiert allgemein Wiedergewinnungsverfahren und schlägt unter bestimmten Umständen die Möglichkeit vor, Redo- und Undo- Aufzeichnungen getrennt voneinander zu führen.
Eine Aufgabe dieser Erfindung ist daher, die Redo-Logbuch- Verwaltung durch das Entfernen von Undo-Information aus Redo- Aufzeichnungen zu erleichtern.
Eine andere Aufgabe dieser Erfindung ist es, einfachere Verwaltung von Undo-Information zu bieten, indem Undo- Information bei der Quittierung einer Transaktion verworfen wird.
Eine andere Aufgabe dieser Erfindung ist es, die Information zu minimieren, die abgespeichert werden muß um Transaktionen im Fall von Abstürzen oder Ausfällen rückgängig zu machen.

II. ZUSAMMENFASSUNG DER ERFINDUNG

Die vorliegende Erfindung vermeidet das Problem des Standes der Technik durch Sicherstellung, daß genügend Information aus Redo- und Undo-Puffern aufrechterhalten wird, so daß alle Anderungen von unquittierten Transaktionen entfernt, die Änderungen von den quittierten Transaktionen wiederhergestellt, und die Speicherung der Undo-Puffer in Undo- Logbücher minimiert werden können. Weitere Leistungsfähigkeit kann durch genaues Zählen der Aktionen in einer Transaktion erhalten werden, während die Aktionen rückgängig gemacht werden.
Die vorliegende Erfindung stellt ein Datenverarbeitungswiedergewinnungsgerät und ein Verfahren zur Datenverarbeitungswiedergewinnung gemäß den Ansprüchen 1 bzw. 5 bereit.
Die beiliegenden Zeichnungen, die in diese Beschreibung einbezogen sind und einen Teil davon bilden, stellen bevorzugte Ausführungsformen dieser Erfindung dar und erläutern, zusammen mit der beiliegenden wörtlichen Beschreibung, die Grunzüge der Erfindung.

III. KURZE BESCHREIBUNG DER ZEICHUUNGEN

Figur 1 zeigt ein Schema eines Computersystems für die Durchführung dieser Erfindung;
Figur 2 zeigt ein Schema eines Plattenteils mit Blöcken und Seiten;
Figur 3 zeigt ein Schema eines Redo-Logbuchs;
Figur 4 zeigt ein Schema eines Undo-Logbuchs;
Figur 5 zeigt ein Schema eines Archivierungs-Logbuchs;
Figur 6 zeigt ein Flußdiagramm zur Durchführung einer Redo-Operation;
Figur 7 zeigt ein Flußdiagramm zur Durchführung einer Wiedergewinnung nach einem Absturz;
Figur 8 zeigt ein Flußdiagramm zur Zusammenfügung von Archivierungs-Logbüchern;
Figur 9 zeigt ein Schema einer Tabelle schmutziger Blöcke;
Figur 10 zeigt ein Flußdiagramm zum Durchführen eines Voraus schreibe-Protokolls, um den Gebrauch eines Undo-Logbuchs zu optimieren;
Figur 11 zeigt ein Schema einer Kompensations-Logbuch- Aufzeichnung;
Figur 12 zeigt ein Schema einer Tabelle aktiver Transaktionen;
Figur 13 zeigt ein Flußdiagramm für eine Transaktionsstart-Operation;
Figur 14 zeigt ein Flußdiagramm für eine Blockaktualisierungs-Operation;
Figur 15 zeigt ein Flußdiagramm für eine Blockschreibe- Operation;
Figur 16 zeigt ein Flußdiagramm für eine Transaktionsabbruch-Operation;
Figur 17 zeigt ein Flußdiagramm für eine Transaktionsvorbereite-Operation;
Figur 18 zeigt ein Flußdiagramm für eine Transaktionsquittier-Operation.

IV. BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORMEN

In folgenden wird im Detail auf bevorzugte Ausführungsformen dieser Erfindung verwiesen, von denen Beispiele in den beiliegenden Zeichnungen dargestellt sind.

A. System-Komponenten

System 100 ist ein Beispiel eines Speichersystems, das zur Ausführung der vorliegenden Erfindung benutzt werden kann. System 100 umfaßt mehrere Netzwerkknoten 110, 120 und 130, die alle auf ein Gemeinschaftsplatten-System 140 zugreifen. Jeder der Netzwerkknoten 110, 120 und 130 enthält einen Prozessor 113, 123 bzw. 133, um die unten beschriebenen Speicher- und Wiedergewinnungs-Routinen auszuführen. Die Netzwerkknoten 110, 120 und 130 enthalten auch jeweils einen Speicher 118, 128 bzw. 138, um wenigstens zwei Funktionen bereitzustellen. Eine der Funktionen ist, als ein lokaler Speicher für den entsprechenden Prozessor zu arbeiten, und die andere Funktion ist, die Daten, die mit dem Plattensystem 140 ausgetauscht werden, zu halten. Die Speicherbereiche, die für den Datenaustausch benutzt werden, werden Cache-Speicher genannt. Cache-Speicher sind allgemein flüchtiger Systemspeicher.
Das Gemeinschaftsplatten-System 140 wird auch "Dauerspeicher" genannt. Dauerspeicher betrifft nichtflüchtigen Systemspeicher, dessen Inhalt mutmaßlich weiterbesteht, wenn ein Teil oder das gesamte System abstürzt. Traditionell umfaßt dieser Speicher magnetische Plattensysteme, Dauerspeicher könnte jedoch auch optische Platten- oder genauso Magnetband-Systeme umfassen.
Außerdem ist der Dauerspeicher, der zur Ausführung dieser Erfindung benutzt wird, nicht auf die in Figur 1 gezeigte Architektur beschränkt. Der Dauerspeicher könnte beispielsweise mehrere Platten umfassen, von denen jede an einen anderen Netzwerkknoten gekoppelt ist, wobei die Netzwerkknoten in einer Art Netzwerk miteinander verbunden sind.
Ein anderer Teil von Dauerspeicher ist ein Sicherungsband- System 150, auf das als "Archivierungsspeicher" Bezug genommen wird. Archivierungsspeicher ist ein Begriff, der allgemein eingesetzt wird, um auf den Systemspeicher zu verweisen, der für Information benutzt wird, die die Rekonstruktion des Inhalts von Dauerspeicher für den Fall erlaubt, daß die Daten im Dauerspeicher unlesbar werden. Sollte beispielsweise das Gemeinschaftsplatten-System 140 einen Speichermedienausfall haben, könnte das Bandsystem 150 dazu benutzt werden, das Plattensystem 140 zurückzuspeichern. Archivierungs speicher umfaßt häufig ein Magnetband-System, es könnte jedoch auch magnetische oder genauso optische Plattensysteme umfassen.
Im System 100 werden Daten normalerweise in Blöcken gespeichert, die die wiedergewinnbaren Objekte des Systems darstellen. Allgemein kann auf Blöcke nur eingewirkt werden, wenn sie sich im Cache-Speicher irgendeines Netzwerkknotens befinden.
Figur 2 zeigt ein Beispiel von mehreren Blöcken 210, 220 und 230 auf einem Teil einer Platte 200. Allgemein enthält ein Block eine ganzzahlige Anzahl von Seiten des Dauerspeichers. In Figur 2 enthält Block 210 beispielsweise die Seiten 212, 214, 216 und 218.

B. Logbücher

Wie oben erklärt, benutzen die meisten Datenbank-Systeme Logbücher zu Wiedergewinnungszwecken. Die Logbücher werden allgemein im Dauerspeicher gespeichert. Wenn ein Netzwerkknoten den Dauerspeicher aktualisiert, speichert der Netzwerkknoten die Logbuchaufzeichnungen, die die Aktualisierungen beschreiben, in einem Puffer im Cache-Speicher des Netzwerkknotens.
Die bevorzugte Ausführungsform der vorliegenden Erfindung stellt sich drei Arten von Logbüchern im Dauerspeicher vor, jedoch nur zwei Arten von Puffern im Cache-Speicher jedes Netzwerkknotens. Die Logbücher sind Redo-Logbücher oder RLOGs, Undo-Logbücher oder ULOGs, und Archivierungs-Logbücher oder ALOGs. Die Puffer sind die Redo-Puffer und die Undo-Puffer.
Ein Beispiel eines RLOG ist in Figur 3 gezeigt, ein Beispiel eines ULOG in Figur 4 und ein Beispiel eines ALOG in Figur 5. Die Organisation eines Redo-Puffers ist ähnlich dem RLOG, und die Organisation eines Undo-Puffers ist ähnlich dem
Eine Logbuch-Laufzahl, LSN (log sequence number), ist die Adresse oder relative Position einer Aufzeichnung in einem Logbuch. Jedes Logbuch verzeichnet LSNS zu den Aufzeichnungen in diesem Logbuch.

1. RLOG

Das RLOG 300 ist, wie in Figur 3 gezeigt, eine bevorzugte Ausführung einer sequentiellen Datei, die benutzt wird, um Information über Anderungen aufzuzeichnen, die die Wiederholung der spezifischen Operationen, die während dieser Änderungen stattfanden, ermöglicht. Im allgemeinen müssen diese Anderungen während eines Wiedergewinnungsschemas wiederholt werden, sobald ein Block in den Zustand wiederhergestellt wurde, an dem protokollierte Aktionen durchgeführt wurden.
Wie Figur 3 zeigt, enthält das RLOG 300 mehrere Aufzeichnungen 301, 302 und 310, die jeweils mehrere Attribute beinhalten. Das TYPE-Attribut 320 kennzeichnet die Art der entsprechenden RLOG-Aufzeichnung. Beispiele der unterschiedlichen Arten von RLOG-Aufzeichnungen sind Redo- Aufzeichnungen, Kompensations-Logbuch-Aufzeichnungen und quittierungsbezogene Aufzeichnungen. Diese Aufzeichnungen sind unten beschrieben.
Das TID-Attribut 325 ist ein eindeutiger Kennzeichner für die mit der aktuellen Aufzeichnung zusammenhängende Transaktion. Dieses Attribut wird dazu benutzt, die der gegenwärtigen RLOG- Aufzeichnung entsprechende Aufzeichnung im ULOG finden zu helfen.
Das BSI-Attribut 330 ist ein "Vorzustands-Kennzeichner". Dieser Kennzeichner ist in größerem Detail unten beschrieben. Kurz gesagt, zeigt das BSI den Wert eines Zustands- Kennzeichners für die Version des Blockes vor seiner Modifikation durch die entsprechende Transaktion an.
Das BID-Attribut 335 kennzeichnet den Block, der durch die Aktualisierung entsprechend der RLOG- Aufzeichnung modifiziert ist.
Das REDO_DATA-Attribut 340 beschreibt die Art der entsprechenden Aktion und stellt genügend Information dafür bereit, daß die Aktion noch einmal durchgeführt werden kann.
Der Begriff "Aktualisierung" wird in dieser Beschreibung weit und austauschbar mit dem Begriff "Aktion" benutzt. Aktionen umfassen in strengem Sinn nicht nur Datensatz-Aktualisierungen, sondern auch Datensatz-Einfügungen und -Löschungen genauso wie Blockzuweisungen und -freigaben.
Das LSN-Attribut 345 kennzeichnet eindeutig die aktuelle Aufzeichnung im RLOG 300. Wie unten im Detail erläutert wird, wird das LSN-Attribut 345 in der bevorzugten Ausführung benutzt, um die Redo-Suche und die Fixpunktroutine des RLOG zu kontrollieren. Das LSN 345 wird in der bevorzugten Ausführungsform weder in RLOG-Aufzeichnungen noch in Blöcken gespeichert. Es ist stattdessen eine der Position der Aufzeichnung im RLOG anhaftende Eigenschaft.
Ein Ziel dieser Erfindung ist es, jedem Netzwerkknoten zu ermöglichen, seine Wiedergewinnung so unabhängig wie möglich von den anderen Netzwerkknoten zu erledigen. Dafür ist mit jedem Netzwerkknoten ein separates RLOG verbunden. Die Verbindung eines RLOG mit einem Netzwerkknoten in der bevorzugten Ausführungsform erfordert den Gebrauch eines jeweils verschiedenartigen RLOG für jeden Netzwerkknoten. Alternativ können sich die Netzwerkknoten RLOGs teilen oder jeder Netzwerkknoten kann mehrere RLOGs haben. Wenn ein RLOG jedoch einem Netzwerkknoten eigen ist, wird keine Synchronisation einschließlich Mitteilungen benötigt, um den Gebrauch des RLOG mit anderen RLOGs und Netzwerkknoten zu koordinieren.

2. ULOG

In Figur 4 ist ULOG 400 eine bevorzugte Ausführung einer sequentiellen Datei, die zur Aufzeichnung von Information benutzt wird, die es ermöglicht, daß Operationen an Blöcken korrekt rückgängig gemacht werden können. Das ULOG 400 wird benutzt, um Blöcke in Zustände wiederherzustellen, die existierten als eine Transaktion begann.
Anders als RLOGs sind jedes ULOG und jeder Undo-Puffer mit einer verschiedenartigen Transaktion verbunden. Daher verschwinden ULOGs und ihre entsprechenden Puffer, wenn die
Transaktionen quittieren, und neue ULOGs treten auf, wenn neue Transaktionen beginnen. Es gibt auch andere Möglichkeiten.
ULOG 400 enthält mehrere Aufzeichnungen 401, 402 und 410, die jeweils zwei Felder enthalten. Ein BID-Feld 420 kennzeichnet den durch die Transaktion modifizierten Block, die mit dieser Aufzeichnung protokolliert ist. Ein UNDO_DATA-Feld 430 beschreibt die Art der Aktualisierung und stellt genügend Information bereit, damit die Aktualisierung rückgängig gemacht werden kann.
Das RLSN-Feld 440 kennzeichnet die RLOG-Aufzeichnung, die die gleiche Aktion beschreibt, für die diese Aktion die Rückgängigmachung darstellt. Dieses Attribut sorgt für die Fähigkeit, jedes ULOG eindeutig zu kennzeichnen.

3. ALOG

In Figur 5 ist ALOG 500 eine bevorzugte Ausführung einer sequentiellen Datei, die benutzt wird, um Redo-Logbuch- Aufzeichnungen für eine ausreichende Zeitdauer zu speichern, um für Speichermedien-Wiedergewinnung zu sorgen, so, wie wenn das Gemeinschaftsplatten-System 140 in Figur 1 ausfällt. Die RLOG- Puffer sind die Informationsquelle, aus der ALOG 500 erzeugt wird, und daher hat das ALOG 500 dieselben Attribute wie das RLOG 300.
ALOGs werden vorzugsweise aus den gekürzten Teilen entsprechender RLOGs gebildet. Die gekürzten Teile sind Teile, die nicht länger gebraucht werden, um die Dauerspeicher- Versionen von Blöcken auf aktuelle Versionen zu bringen. Die Aufzeichnungen in den gekürzten Teilen der RLOGs werden jedoch noch benötigt, sollte die Dauerspeicher-Version eines Blocks unbrauchbar werden und aus der Version des Blockes in Archivierungsspeicher wiederhergestellt werden müssen.
Ähnlich dem RLOG 300 enthält das ALOG 500 mehrere Aufzeichnungen 501, 502 und 503. Die Attribute TYPE 520, TID 525, BSI 530, BID 535 und REDO_DATA 540 haben dieselben Funktionen wie die gleichnamigen Attribute im RLOG 300. Das LSN 545 kennzeichnet, wie das LSN 345 für das RLOG 300, die ALOG- Aufzeichnung.

C. Zustands-Kennzeichner (und Vorausschreibe-Logbuch- Protokoll)

In logbuch-gestützten Systemen wird eine Logbuch- Aufzeichnung nur auf einen Block angewendet, wenn der aufgezeichnete Zustand des Blockes für die durch die Logbuch- Aufzeichnung vorgesehene Aktualisierung geeignet ist. Daher ist eine ausreichende Bedingung für eine korrekte Wiedervornahme (Redo), eine protokollierte Transaktion auf einen Block anzuwenden, wenn der Block in demselben Zustand ist als er war, als die ursprüngliche Aktion durchgeführt wurde. Wenn die ursprüngliche Aktion korrekt war, wird auch die wiederholte Aktion korrekt sein.
Es ist schwerfällig und unpraktisch, den gesamten Inhalt eines Blockzustandes in einem Logbuch zu speichern. Demgemäß wird ein Proxy-Wert oder -Kennzeichner für den Blockzustand geschaffen. Der Kennzeichner, der in der bevorzugten Ausführungsform benutzt wird, ist ein Zustands-Kennzeichner oder SI (state identifier). Der SI hat für jeden Block einen eindeutigen Wert. Dieser Wert kennzeichnet den Zustand des Blockes zu irgendeiner bestimmten Zeit, so wie entweder vor oder nach der Durchführung irgendeiner Operation an dem Block.
Der SI ist viel kleiner als der komplette Zustand und kann anstelle des kompletten Zustandes billig benutzt werden, solange der komplette Zustand, wenn notwendig, wiederhergestellt werden kann. Ein SI wird durch die Speicherung eines bestimmten Wertes, "Zustandsdefinitions- Kennzeichner" oder DSI (defining state identifier) genannt, im Block "definiert". Der DSI gibt dem Zustand des Blockes an, in dem er enthalten ist.
Die Wiederherstellung eines Zustandes kann durch Zugriff auf den gesamten im Dauerspeicher gespeicherten Block während der Wiedergewinnung und Kenntnisnahme von dem DSI dieses Blockes erreicht werden. Dieser Blockzustand wird dann, wie im Detail unten erläutert, durch Anwendung der protokollierten Aktionen, soweit geeignet, aktualisiert.
Eine ähnliche Technik wird unten für Speichermedien- Wiedergewinnung unter Benutzung des ALOG beschrieben. Zu wissen, ob eine Logbuch-Aufzeichnung auf einen Block anwendbar ist, bedeutet in der Lage zu sein, aus der Logbuch-Aufzeichnung zu bestimmen, auf welchen Zustand sich die protokollierte Aktion bezieht. Gemäß der vorliegenden Erfindung wird der DSI eines Blockes dazu benutzt, zu bestimmen, wann mit der Anwendung von Logbuch-Aufzeichnungen auf diesen Block begonnen wird.
In einem zentralisierten oder partitionierten System wird die physikalische Reihenfolge von Aufzeichnungen in einem einzelnen Logbuch zum Ordnen der wiedervorzunehmenden Aktionen verwendet. Das heißt, wenn die Aktion B an einem Block unmittelbar auf die Aktion A an dem Block folgt, dann ist die Aktion B auf den Blockzustand anwendbar, der durch die Aktion A geschaffen wurde. So wird, wenn die Aktion A wiederholt wurde, die nächste auf den Block anzuwendende Logbuch-Aufzeichnung die Aktion B sein.
Einzellogbuch-Systeme, wie zentralisierte oder partitionierte Systeme, benutzen häufig LSNs als SIs, um Blockzustände zu kennzeichnen. Das LSN, das als der DSI für einen Block dient, kennzeichnet die letzte Aufzeichnung in Logbuchreihenfolge, deren Wirkung ihren Niederschlag im Block gefunden hat. In derartigen Systemen kann das LSN einer Logbuch-Aufzeichnung die Rolle eines "Nachzustands- Kennzeichners" oder ASI (after state identifier) spielen, der den Zustand des Blockes nach der protokollierten Aktion kennzeichnet. Das steht im Gegensatz zu einem BSI (before state identifier, Vorzustands-Kennzeichner), der in der vorliegenden Erfindung in einer Logbuch-Aufzeichnung wie unten beschrieben benutzt wird.
Um den DSI zu aktualisieren und für die nächste Operation vorzubereiten, ist es auch notwendig, den ASI für einen Block nach der Anwendung der Logbuch-Aufzeichnung bestimmen zu können. Es ist von Nutzen, den ASI von der Logbuch- Aufzeichnung, wie vom BSI, ableiten zu können, so muß der ASI nicht in Logbuch-Aufzeichnungen gespeichert werden, obwohl der ASI tatsächlich gespeichert werden kann. Die Ableitung muß jedoch eine sein, die sowohl während der Wiedergewinnung als auch während des Normalbetriebs verwendet werden kann. Vorzugsweise sind die SIs in einer bekannten Reihenfolge, so wie die monoton ansteigende Menge von ganzen Zahlen beginnend mit Null. In dieser Technik ist der ASI immer um eins größer als der BSI.
Beim Zurückspeichern des aktualisierten Blocks in den Dauerspeicher, wie das Gemeinschaftsplatten-System 140, wird ein Vorausschreibe-Logbuch- (WAL, Write-Ahead-Log) Protokoll benutzt. Das WAL-Protokoll verlangt, daß die Redo- und Undo- Puffer vor den Blöcken in die Logbücher des Gemeinschaftsplatten-Systems 140 geschrieben werden. Das stellt sicher, daß die zur Wiederholung oder Rückgängigmachung der Aktion notwendige Information fest gespeichert ist bevor eine Anderung der dauerhaften Kopie der Daten erfolgt.
Wenn dem WAL-Protokoll nicht gefolgt wird, und ein Block müßte vor der Logbuch-Aufzeichnung für die letzte Aktualisierung für den Block in den Dauerspeicher geschrieben werden, könnte unter bestimmten Bedingungen keine Wiedergewinnung erfolgen. Zum Beispiel kann eine Aktualisierung an einem Netzwerkknoten bewirken, daß ein Block, der unquittierte Aktualisierungen enthält, in den Dauerspeicher geschrieben wird. Wenn die letzte Aktualisierung für diesen Block nicht in das RLOG des Netzwekknotens gepeichert wurde, und eine weitere Transaktion an einem zweiten Netzwerkknoten aktualisiert den Block und quittiert, wird der DSI des Blockes erhöht. Im Moment des Quittierens für diese zweite Transaktion werden die protokollierten Aktionen für diese anderen Transaktionen in das RLOG für den zweiten Netzwerkknoten gezwungen. Da die zweite Aktualisierung jedoch durch einen anderen Netzwerkknoten erzeugt wurde, stellt das Schreiben der Logbuch-Aufzeichnungen für die zweite Transaktion nicht sicher, daß die Logbuch-Aufzeichnung für die unquittierte Transaktion an dem ursprünglichen Netzwerkknoten geschrieben ist.
Wenn der ursprüngliche Netzwerkknoten abstürzt und die Logbuch-Aufzeichnung für die unquittierte Transaktion niemals in das RLOG geschrieben wird, wird eine Lücke in der ASI-BSI- Reihenfolge für den Block erzeugt. Sollte der Block im Dauerspeicher jemals unbrauchbar werden, beispielsweise aufgrund eines Plattenausfalls, wurde Wiedergewinnung scheitern, da die ALOG-Zusammenfügung, wie unten erläutert, eine bekannte und lückenlose Reihenfolge von SIs erfordert.
Folglich ist das WAL-Protokoll eine notwendige Bedingung für eine ununterbrochene Reihenfolge protokollierter Aktionen. Es ist ebenso eine ausreichende Bedingung hinsichtlich der Blockaktualisierungen. Wenn ein Block sich vom Cache-Speicher eines Netzwerkknotens zu einem anderen bewegt, erzwingt das WAL-Protokoll, daß die RLOG-Aufzeichnungen für alle früheren Aktualisierungen der Blöcke durch die quittierende Transaktion geändert werden. "Erzwingen" bedeutet Sicherstellen, daß die Aufzeichnungen im Cache-Speicher oder Puffer eines Netzwerkknotens fest im Dauerspeicher abgespeichert werden.
Durch das Schreiben in den Dauerspeicher erzwingt das WAL- Protokoll das Schreiben aller Aufzeichnungen in das RLOG des ursprünglichen Netzwerkknotens bis zu der Logbuch-Aufzeichnung für die letzte Aktualisierung des gegenwärtigen Blockes.

D. Neue Blockzuweisung

Wenn ein Block freigegeben wurde, wie während normaler Plattenspeicher-Verwaltungsroutinen, und wird später wieder für weiteren Gebrauch zugewiesen, sollte sein DSI nicht auf Null gesetzt werden, da diese Aktivität zu mehrdeutigen Zustands- Kennzeichnern führt. Wenn der DSI auf Null gesetzt werden würde, könnten mehrere auf einen Block anwendbare Logbuch- Aufzeichnungen auftauchen, da sie den gleichen SI haben wurden. Es wurde zusätzliche Information benötigt werden, um die korrekte Logbuch-Aufzeichnung zu bestimmen. Daher muß die DSI- Numerierung, die bei der vorhergehenden Zuweisung verwendet wurde, ununterbrochen bei der neuen Zuweisung erhalten werden. Vorzugsweise entspricht der BSI für einen neu zugewiesenen Block dem ASI des Blockes bei der Freigabe.
Ein einfacher Weg zur Erreichung einer ununterbrochenen SI-Numerierung liegt darin, einen DSI als Ergebnis der Freigabe-Operation im Block zu speichern. Wenn der Block wieder zugewiesen wird, wird er gelesen, möglicherweise vom Dauerspeicher, und die normale DSI-Erhöhung wird fortgesetzt. Dies behandelt Zuweisung und Freigabe gerade wie Aktualisierungs-Operationen. Ein Problem bei dieser Lösung ist die Notwendigkeit, neu wieder zugewiesene Blöcke vor ihrer Benutzung zu lesen. Um jedoch die Speicherplatzverwaltung mit einem Minimum an Ein-/Ausgabe-Tätigkeit leistungsfähig zu gestalten, wäre es wünschenswert, die "Strafe des Lesens vor Zuweisung" zu vermeiden.
Die vorliegende Erfindung gewinnt an Leistungsfähigkeit, indem sie den DSI für alle nichtzugewiesenen Blöcke nicht schreibt. Für Blöcke, die nicht zuvor zugewiesen wurden, ist der anfängliche DSI immer auf Null gesetzt. Nur der DSI für Blöcke, deren Zuweisung aufgehoben wurde, wird gespeichert. Diese DSIs werden unter Verwendung der Aufzeichnungen gespeichert, die bereits durch die Systemverwaltung für freien Speicherplatz im Dauerspeicher gehalten werden. Üblicherweise wird eine derartige Systemverwaltungsinformation in einer Sammlung von Speicherplatzverwaltungsblöcken aufgezeichnet.
Indem der anfängliche SI für jeden Block, dessen Zuweisung aufgehoben wird, mit dieser Speicherplatzverwaltungsinformation gespeichert wird, müssen die anfänglichen SIs nicht in den Blöcken gespeichert werden, so daß die Strafe des Lesens vor der Zuweisung beseitigt wird. Bei der Wiederzuweisung wird der BSI für die "Zuweisungs"-Operation der anfängliche SI dieses vorher "freien" Blocks.
Natürlich müssen, um dieses Verfahren korrekt funktionieren zu lassen, Blöcke mit Speicherplatzverwaltungsinformation in regelmäßigen Zeitabständen in den Dauerspeicher geschrieben werden, und einem Netzwerkknoten darf nicht ermöglicht werden, Blöcke, die durch einen anderen Netzwerkknoten freigegeben wurden, wieder zuzuweisen, bevor ihm die Existenz der freigegebenen Blöcke über diese Systemverwaltung bekannt gemacht wurde. Folglich verursacht die Aufrechterhaltung der anfänglichen SIs für freigegebene Blöcke kein zusätzliches Lesen oder Schreiben der Systemverwaltungs information über freien Speicherplatz.
Obwohl das Hinzufügen von SI-Information für freie Blöcke die in diesen System benotigte Menge an Speicherplatzverwaltungsinformation erhöht, gibt es zwei Gründe dafür, warum die Leistungsfähigkeit des Systems nicht zu sehr darunter leiden sollte. Erstens ist der größte Teil des freien Speicherpiatzes als "niemals zuvor zugewiesen" gekennzeichnet und hat demzufolge bereits einen anfänglichen SI von Null. Zweitens ist der vorher benutzte freie Speicherplatz in den meisten Datenbank-Systemen gering, da Datenbanken üblicherweise anwachsen. Da die anfänglichen SIs nur für die wieder zugewiesenen Blöcke einzeln gespeichert werden, sollte der zusätzliche Speicherplatz für die SIs gering sein.
Alternativ könnten die niemals vorher zugewiesenen Blöcke von den wieder zugewiesenen Blöcken unterschieden werden. Der SI für die wieder zugewiesenen Blöcke könnte dann aus dem Dauerspeicher gelesen werden, wenn diese Blöcke zugewiesen werden. Dies wurde jedoch eine Strafe des Lesens vor Zuweisung schaffen, obwohl die Strafe aus den oben diskutierten Gründen leicht wäre.

E. Wiedergewinnung

1. Block-Versionen

Um zu verstehen wie die Logbücher bei der Wiedergewinnung benutzt werden können, ist es notwendig, die unterschiedlichen Vesionen der Blöcke zu verstehen, die nach einem Absturz verfügbar sein können. Diese Versionen können charakterisiert werden in Form von wievielen der protokollierten Aktualisierungen in wievielen Logbüchern notwendig sind, um die verfügbare Version aktuell zu machen. Dies hat offensichtlichen Einfluß hinsichtlich der Frage, wie ausgedehnt oder örtlich beschränkt die Wiedergewinnungsaktivität sein wird.
Für Zwecke der Wiedergewinnung gibt es drei Arten von Blöcken. Eine Version eines Blockes ist "aktuell", wenn alle Aktualisierungen, die an dem Block vorgenommen wurden, ihren Niederschlag in der Version gefunden haben. Ein Block, der nach einen Ausfall eine aktuelle Version aufweist, benötigt keine Redo-Wiedergewinnung. Wenn man jedoch mit unvorhersehbaren Systemausfällen zu tun hat, kann man nicht sicherstellen, daß alle Blöcke aktuell sind, ohne immer den Cache-Speicher in den Dauerspeicher zu schreiben ("writing-thru"), jedesmal wenn eine Aktualisierung auftritt. Das ist teuer und wird selten gemacht.
Eine Version eines Blockes ist "ein-Logbuch", wenn lediglich das Logbuch eines Netzwerkknotens Aktualisierungen hat, die noch nicht auf den Block angewendet wurden. Wenn ein Ausfall auftritt, muß maximal ein Netzwerkknoten in die Wiedergewinnung eingebunden werden. Dies ist wunschenswert, da es die potentiell teure Koordination während der Wiedergewinnung, genauso wie zusätzliche Ausführungskosten vermeidet.
Eine Version eines Blockes ist "N-Logbuch", wenn mehr als ein Logbuch eines Netzwerkknotens Aktualisierungen haben kann, die noch nicht auf ihn angewendet wurden. Wiedergewinnung ist allgemein schwieriger für N-Logbuch-Blöcke als für ein-Logbuch- Blöcke, aber es ist unpraktisch, wenn Speichermedienwiedergewinnung bereitgestellt wird, um sicherzustellen, daß Blöcke immer in der ein-Logbuch-Version vorliegen, da dies jedesmal das Schreiben eines Blockes in den Archivierungsspeicher umfassen wurde, wenn der Block Netzwerkknoten wechselt.

2. Redo-Wiedergewinnung

Ohne darauf zu achten werden zum Zeitpunkt eines Systemabsturzes (im Gegensatz zu einem Speichermedienausfall) einige Blöcke vom N-Logbuch-Typ sein. Die bevorzugte Ausführungsform dieser Erfindung garantiert jedoch, daß alle Blöcke für die Wiedergewinnung vom Systemabsturz ein-Logbuch- Blöcke sein werden. Das ist vorteilhaft, da N-Logbuch-Blöcke für ihre Wiedergewinnung eine komplexe Koordination zwischen den Netzwerkknoten erfordern können. Obwohl eine solche Koordination möglich ist, da die Aktualisierungen ursprünglich während dem normalen Systembetrieb unter Verwendung einer verteilten Nebenläufigkeitskontrolle geordnet wurden, erfordert eine solche verteilte Nebenläufigkeitskontrolle eine Organisation, die während der Wiedergewinnung vermieden werden sollte.
Es kann sichergestellt werden, daß alle Blöcke in bezug auf Redo-Wiedergewinnung vom ein-Logbuch-Typ sind, indem gefordert wird, daß "schmutzige" Blöcke in den Dauerspeicher geschrieben werden, bevor sie von einem Cache-Speicher zu einem anderen verschoben werden. Ein schmutziger Block ist einer, dessen Version im Cache-Speicher aktualisiert wurde, seit der Block aus dem Dauerspeicher gelesen wurde.
Wenn dieser Regel gefolgt wird, erhält ein anfordernder Netzwerkknoten immer einen sauberen Block, wenn der Block in den Cache-Speicher des neuen Netzwerkknotens eintritt. Weiterhin müssen während der Wiedergewinnung lediglich die Aufzeichnungen im Logbuch des letzten Netzwerkknotens, der den Block änderte, auf den Block angewendet werden. Alle anderen Aktionen anderer Netzwerkknoten wurden bereits im Zustand des Blockes im Dauerspeicher eingefangen. Demgemäß werden alle Blöcke für Redo-Wiedergewinnung vom ein-Logbuch-Typ sein, so daß Redo-Wiedergewinnung keine verteilte Nebenläufigkeitskontrolle erfordert.
Dieser Technik zu folgen heißt nicht, daß niemals mehrere Logbücher Aufzeichnungen für einen Block enthalten. Diese Technik stellt lediglich sicher, daß nur die Aufzeichnungen eines Netzwerkknotens auf die Version des Blockes im Dauerspeicher anwendbar sind.
Weiterhin kann es, obwohl ein-Logbuch Redo-Wiedergewinnung für Systemabstürze angenommen wird, notwendig sein, daß zur Durchführung von Speichermedienwiedergewinnung Redo-Aktionen in mehreren Logbüchern angewendet werden müssen, um das Schreiben jedes Blockes in den Archivierungsspeicher, jedesmal wenn sich der Block zwischen den Cache-Speichern bewegt, zu vermeiden. Daher ist es unter bestimmten Bedingungen immer noch notwendig, die protokollierten Aktionen über alle Logbücher anzufordern, um Wiedergewinnung für N-Logbuch-Blöcke zu gewährleisten. Dies kann jedoch aufgrund der sequentiellen SIs erreicht werden.
Figur 6 zeigt ein Flußdiagramm 600 der grundlegenden Schritte für eine Redo-Operation unter Verwendung des RLOG und der oben beschriebenen SIs. Die durch das Flußdiagramm 600 dargestellte Redo-Operation würde von einem einzelnen Netzwerkknoten unter Verwendung einer einzelnen RLOG- Aufzeichnung, die auf einen einzelnen Block angewendet wird, durchgeführt.
Zuerst würde die durch die Logbuch-Aufzeichnung gekennzeichnete aktuellste Version des Blockes aus dem Dauerspeicher zurückgewonnen werden (Schritt 610). Wenn der in diesem zurückgewonnenen Block gespeicherte DSI mit dem in der Logbuch-Aufzeichnung gespeicherten BSI übereinstimmt (Schritt 620), dann wird die in der Logbuch-Aufzeichnung angezeigte Aktion auf den Block angewendet und der DSI erhöht, um den neuen Zustand des Blockes wiederzugeben (Schritt 630). Andernfalls wird diese Aktualisierung nicht auf den Block angewendet.
Die mit Bezug auf Figur 6 beschriebene Redo-Operation ist möglich, da die BSIs und ASIs zum Zeitpunkt der Wiedergewinnung bestimmt werden können. Folglich kann man für jedes Logbuch bestimmen, welche Logbuch-Aufzeichnungen nochmals vorgenommen werden müssen, und diese Bestimmung kann unabhängig von den Inhalten anderer Logbücher sein. Der einzige Vergleich, der zwischen Block-DSIs und Logbuch-Aufzeichnungs-BSIs gemacht werden muß, ist ein Gleichheitsvergleich.
Die mit Bezug auf Figur 6 beschriebene Redo-Operation kann zur Wiedergewinnung aus Systemabstürzen eingesetzt werden. Ein Beispiel für ein Verfahren der Absturz-Wiedergewinnung ist durch das Flußdiagramm 700 in Figur 7 gezeigt. Dieses Absturz- Wiedergewinnungsverfahren kann ein einzelner Netzwerkknoten unabhängig von anderen Netzwerkknoten ausführen.
Der erste Schritt für den Netzwerkknoten wäre, die erste RLOG-Aufzeichnung zu lesen, die durch den neuesten Fixpunkt angezeigt wird (Schritt 710). Der Fixpunkt zeigt, wie unten beschrieben, den Punkt im RLOG an, der die der ältesten Aktualisierung entsprechende Aufzeichnung enthält, die angewendet werden muß.
Die in Figur 6 dargestellte Redo-Operation wird dann durchgeführt um zu sehen, ob die in dieser Logbuch-Aufzeichnung spezifizierte Aktion auf den in dieser Logbuch-Aufzeichnung gekennzeichneten Block anzuwenden ist (Schritt 720).
Wenn nach der Durchführung der Redo-Operation keine weiteren Aufzeichnungen vorhanden sind (Schritt 730), ist die Absturz-Wiedergewinnung vollständig. Andernfalls wird die nächste Aufzeichnung aus dem RLOG gewonnen (Schritt 740) und die in Figur 6 gezeigte Redo-Operation (Schritt 720) wird wiederholt.
Wenn der mit einer Logbuch-Aufzeichnung verbundene SI ein monoton ansteigender ASI ist, umfaßt der Test, ob eine Logbuch- Aufzeichnung auf einen Block in irgendeinem Zustand anwendbar ist, ob dieser ASI der erste ist, der um eins größer als der DSI des Blockes ist. Das reicht jedoch nur für ein-Logbuch- Wiedergewinnung aus, da in diesem Fall nur ein Logbuch Aufzeichnungen mit ASIs haben wird, die größer als der DSI im Block sind.
In der bevorzugten Ausführungsform dieser Erfindung umfaßt jedoch jede Logbuch-Äufzeichnung die genaue Kennzeichnung des Blockzustandes vor der Durchführung einer protokollierten Altion. Wie oben erläutert ist dies der "Vorzustands- Kennzeichner" oder BSI.

3. Vielfach-Logbuch-Redo für Speichermedienwiedergewinnung

Speichermedienwiedergewinnung hat viele mit der Absturz- Wiedergewinnung übereinstimmende Charakteristiken. So muß beispielsweise eine fest gespeicherte Version vorliegen, gegenüber der die Logbuch-Aufzeichnungen angewendet werden.
Es gibt auch wichtige Unterschiede. Erstens ist die feste Version des Blockes, gegenüber der die ALOG-Aufzeichnungen angewendet werden, die zuletzt in den Archivierungsspeicher eingegebene Version.
Speichermedienwiedergewinnung ist vom N-Logbuch-Typ, da sie die Wiederherstellung von Blöcken aus dem Archivierungsspeicher umfaßt, und, wie oben erläutert, die Blöcke nicht jedesmal in den Archivierungsspeicher geschrieben werden, wenn sie sich zwischen Cache-Speichern bewegen. Daher kann die Technik, Blöcke in den Speicher zu schreiben, um N- Logbuch-Wiedergewinnung für Systemabstürze zu vermeiden, nicht für Speichermedienwiedergewinnung eingesetzt werden.
Die Verwaltung von Speichermedienwiedergewinnung ist ohne Zusammenfügung der ALOGs schwierig. Wenn die ALOGs nicht zusammengefügt werden, dann umfaßt die Wiedergewinnung ständiges Suchen nach anwendbarem Logbuch-Aufzeichnungen. Im Zusammenfügen von ALOGs besteht ein beträchtlicher Vorteil im Gebrauch von BSIs.
Figur 8 zeigt ein Verfahren 800 für N-Logbuch- Speichermedienwiedergewinnung, das die Zusammenlegung der mehreren ALOGs einschließt. Die Zusammenlegung basiert nicht auf einem vollständigen Ordnen unter allen Logbuch- Aufzeichnungen, sondern auf einem teilweisen Ordnen, das sich aus dem Ordnen unter Logbuch-Aufzeichnungen für denselben Block ergibt. Manchmal wird es mehrere ALOGs mit Aufzeichnungen geben, deren Aktionen auf ihre entsprechenden Blöcke angewendet werden können. Wie aus der Beschreibung zum Verfahren 800 offensichtlich ist, ist es unwesentlich, welche dieser Aktionen während der Speichermedienwiedergewinnung zuerst angewendet wird.
Es ist schneller und effizienter, zu ermöglichen, daß die mehreren ALOGs zusammengelegt und auf die Sicherungsdatenbank im Archivierungsspeicher in einem einzigen Schritt angewendet werden. Das kann gemacht werden, wenn die SIs richtig geordnet sind. Dies ist der Grund, weshalb die SIs, wie oben erläutert, in einer bekannten Reihenfolge geordnet sind, und die bevorzugte Ausführungsform dieser Erfindung verwendet SIs, die monoton ansteigen.
Beginnend mit irgendeinem ALOG wird auf die erste Logbuch- Aufzeichnung zugegriffen (Schritt 810). Aus dieser Aufzeichnung werden dann der Block-ID und BSI herausgeholt (Schritt 820). Als nächstes wird der durch dem Block-ID gekennzeichnete Block geholt (Schritt 830).
Sobald der gekennzeichnete Block geholt ist, wird sein DSI gelesen und mit dem BSI der ALOG-Aufzeichnung verglichen (Schritt 840). Wenn der BSI der ALOG-Aufzeichnung kleiner ist als der DSI des Blockes, wird die Aufzeichnung nicht beachtet, da die protokollierte Aktion bereits im Block enthalten ist, und Wiedervornahme (Redo) ist nicht erforderlich.
Wenn der BSI der ALOG-Aufzeichnung gleich dem DSI des Blockes ist, dann wird die protokollierte Aktion durch Anwendung dieser Aktion auf dem Block wiederholt (Schritt 850). Der Grund hierfür ist, daß die Gleichheit der SIs bedeutet, daß die protokollierte Aktion auf die aktuelle Version des Blockes anwendbar ist.
Der DSI des Blockes wird dann erhöht (Schritt 860). Das spiegelt die Tatsache wider, daß die Anwendung der protokollierten Aktion eine neue (spätere) Version des Blockes erzeugt hat.
Wenn der BSI der ALOG-Aufzeichnung größer ist als der DSI des Blockes, dann ist nicht der richtige Zeitpunkt, die der Logbuch-Aufzeichnung entsprechenden Aktionen anzuwenden, und es ist stattdessen der richtige Zeitpunkt, die in anderen ALOGs aufgezeichneten Aktionen anzuwenden. Folglich muß das Lesen dieses ALOG innehalten und das Lesen eines anderen ALOG wird begonnen (Schritt 870).
Wenn der andere ALOG vorher innegehalten wurde (Schritt 880), dann wird die Kontrolle auf Schritt 820 übertragen, um den Block-ID und den BSI der Logbuch-Aufzeichnung, der aktuell war als dieses Logbuch innegehalten wurde, herauszuholen. Wenn das Logbuch nicht vorher innegehalten wurde, dann macht die Kontrolle weiter als ob dieses das erste ALOG wäre.
Nach all diesen Schritten, oder wenn das andere ALOG niemals vorher innegehalten wurde, wird eine Feststellung darüber getroffen, ob irgendwelche ALOG-Aufzeichnungen übrig sind (Schritt 890). Wenn dies so ist, wird die nächste Aufzeichnung geholt (Schritt 810). Andernfalls wird das Verfahren 800 beendet.
Wenn ein ALOG innegehalten wird, muß es wenigstens ein anderes ALOG geben, das Aufzeichnungen für dem Block enthält, der dem aktuellen vorausgeht. Ein innegehaltenes ALOG mit einer wartenden Logbuch-Aufzeichnung wird einfach als Eingabestrom angesehen, dessen erster Punkt (in einer geordneten Reihenfolge) später vergleicht als die Punkte in dem anderen Eingabeströmen (d.h. die anderen ALOGs). Das Verfahren fährt unter Verwendung der anderen ALOGs fort.
Die aktuelle Aufzeichnung des innegehaltenen ALOG muß auf den Block zu irgendeinem zukünftigen Zeitpunkt angewendet werden können, da der BSI ohne dazwischenliegende Aktionen in anderen ALOGs nicht größer sein wurde als der DSI des Blockes. Wenn das auftritt, wird das Innehalten des ALOGs beendet.
Nicht alle ALOGs werden gleichzeitig innegehalten, da die Aktionen ursprünglich in einer Ordnung durchgeführt wurden, die mit dem SI-Ordnen für die Blöcke übereinstimmt. Demzufolge ist ein Zusammenlegen der ALOGs immer möglich.

4. Redo Verwaltung

a. Bestimmung des sicheren Punktes

Mit der vorliegenden Erfindung können viele Fixpunkttechniken benutzt werden, um die Redo-Wiedergewinnung noch effizienter zu machen. Beispielsweise kann eine Tabelle schmutziger Blöcke erzeugt werden, um mit jedem schmutzigen Block Wiedergewinnungs -Verwaltungs information zu verknüpfen. Diese Information liefert zwei wichtige Funktionen bei der Verwaltung des RLOG und somit des ALOG. Erstens wird die Wiedergewinnungs-Verwaltungsinformation beim Bestimmen eines "sicheren Punktes" verwendet, der RLOG-Suche und -Kürzung regelt. Zweitens kann die Information dazu benutzt werden, das WAL-Protokoll für das RLOG genauso wie für potentielle Undo- Logbücher durchzusetzen.
Die Bestimmung des sicheren Punktes ist wichtig, um zu bestimmen, wie viel des RLOG durchsucht werden muß, um Redo- Wiedergewinnung durchführen zu können. Der Startpunkt im RLOG für diese Redo-Suche wird "sicherer Punkt" genannt. Der sichere Punkt ist in doppeltem Sinn "sicher". Erstens kann die Redo- Wiedergewinnung sicher Aufzeichnungen außer acht lassen, die dem sicheren Punkt vorangehen, da diese Aufzeichnungen bereits alle in dem Versionen von Blöcken im Dauerspeicher enthalten sind. Zweitens können die "außer acht gelassenen" Aufzeichnungen aus dem RLOG gekürzt werden, da sie nicht länger benötigt werden.
Dieses zweite Merkmal trifft für kombinierte Undo/Redo- Logbücher nicht zu. Beispielsweise könnte im Falle einer langen Transaktion, die Undo-Aufzeichnungen erzeugte, die Kürzung vor dem Fixpunkt nicht möglich sein, da die Aktionen in dem Undo- Aufzeichnungen den Aktionen in dem Redo-Aufzeichnungen, die in dem Dauerspeicher geschrieben wurden, vorausgehen können. Dies würde sich mit der Kürzung überschneiden.
Die Tabelle schmutziger Blöcke 900 ist in Figur 9 gezeigt.
Vorzugsweise wird die aktuelle Kopie der Tabelle schmutziger Blöcke 900 in flüchtigem Speicher gehalten und in gleichmäßigen Zeitabständen als Teil des Fixpunkt-Verfahrens im RLOG in dem Dauerspeicher gespeichert. Die Eingaben oder Einträge 910, 911 und 912 der Tabelle schmutziger Blöcke umfassen ein Wiedergewinnungs-LSN-Feld 920 und ein Block-ID-Feld 930. Die Werte im Wiedergewinnuns-LSN-Feld 920 kennzeichnen die früheste RLOG-Aufzeichnung, deren Aktion nicht in der Version des Blockes im Dauerspeicher eingeschlossen ist. Daher entspricht der Wert des LSN-Feldes 920 der ersten RLOG- Aufzeichnung, die nochmals vorgenommen werden müßte.
Der Wert im Block-ID-Feld 930 kennzeichnet dem der Wiedergewinnungs-LSN entsprechenden Block. Folglich verknüpft die Tabelle schmutziger Blöcke 900 mit jedem schmutzigen Block das LSN der RLOG-Aufzeichnung, der dem Block schmutzig machte.
Ein anderer Eintrag in der Tabelle schmutziger Blöcke 900 ist der LastSN-Eintrag 950. Der Wert dieses Eintrags entspricht, für jeden Block, dem LSNS der RLOG- und ULOG- Aufzeichnungen, die die letzte Aktualisierung des Blockes beschreiben. LSNS werden eher benutzt als DSIs, da es erforderlich ist, Positionen in Logbüchern zu bestimmen.
Der LastLSN 950 umfaßt dem RLastLSN 955 (für das RLOG) und eine Liste von ULastLSNs 958 (einen für jedes der ULOGs), die anzeigen, wie viel von dem RLOG bzw. dem ULOGs modifiziert werden muß, um das WAL-Protokoll durchzusetzen, wenn der Block in dem Dauerspeicher geschrieben wird. Durchsetzen des WAL- Protokolls bedeutet demzufolge, daß alle Aktionen, die in einem Block im Dauerspeicher enthalten sind, sowohl RLOG- als auch ULOG-Aufzeichnungen fest gespeichert haben.
Der RLastLSN 955 und der ULastLSN 958 sind nicht in Fixpunkt (unten beschrieben)eingeschlossen, da ihre Rolle lediglich darin besteht, das WAL-Protokoll für das RLOG und ULOG durchzusetzen. Daher werden diese Einträge in der bevorzugten Ausführungsform getrennt vom Wiedergewinnungs-LSN gehalten, um ihr Speichern mit der Fixpunktinformation zu vermeiden.
Das früheste LSN für alle Blöcke im Cache-Speicher eines Netzwerkknotens ist der sichere Punkt für die Redo-Suche im lokalen RLOG. Die Redo-Wiedergewinnung wird begonnen, indem das lokale RLOG vom sicheren Punkt vorwärts gelesen und die Aktionen in nachfolgenden Aufzeichnungen wiederholt werden. Alle Blöcke, die Wiedervornahme benötigen, treffen während dieser Suche auf alle Aktionen, die wiederholt werden müssen.
Wie oben erläutert ermöglicht es die ein-Logbuch-Annahme, jedes RLOG isoliert zu verwalten. Ein Netzwerkknotern muß sich nur mit seinem eigenen RLOG befassen, folglich werden die Aktionen eines Netzwerkknotens niemals die Ursache dafür sein, daß ein Block im Cache-Speicher irgendeines anderen Netzwerkknotens schmutzig ist. Daher reicht es aus, ein mit jedem Block verknüpftes einfaches Wiedergewinnungs-LSN (eines, das nicht das RLOG nennt) zu halten, wobei verstanden wird, daß das Wiedergewinnungs-LSN eine Aufzeichnung im lokalen RLOG kennzeichnet.

b. Fixpunktroutine

Der Zweck einer Fixpunktroutine ist es sicherzustellen, daß die Bestimmung des sicheren Punktes, wie oben beschrieben, Systemabstürze überleben kann. Eine Fixpunktroutine kann mit einer Strategie zur Verwaltung von Blöcken kombiniert werden, die dem sicheren Punkt erlaubt, sich zu bewegen und dem Teil des Logbuch-Bedarfs für das Redo zu schrumpfen. Es gibt viele verschiedene Techniken für Fixpunktroutinen. Eine ist unten beschrieben, sollte jedoch nicht als eine notwendige Technik betrachtet werden.
Die bevorzugte Technik für die Ausführung dieser Erfindung ist eine Form einer "unscharfen" RLOG-Fixpunktroutine. Sie wird "unscharf" bezeichnet, da die Fixpunktroutine ohne Rücksicht darauf durchgeführt werden kann, ob eine Transaktion oder eine Operation abgeschlossen ist.
Die Wiedergewinnung einer Version der Tabelle schmutziger Blöcke 900 aus der Fixpunktinformation ermöglicht eine Bestimmung darüber, wo die Redo-Suche begonnen werden muß. Nur Blöcke in der Tabelle schmutziger Blöcke 900 müssen einer Wiedervornahme unterzogen werden, da nur diese Blöcke Aktionen haben, die nicht in dem Dauerspeicher gespeichert wurden. Wie oben erklärt, zeigt die Tabelle schmutziger Blöcke 900 die früheste protokollierte Transaktion an, die eine Wiedervornahme erfordern könnte.
Systemabsturz-Wiedergewinnung mittels des RLOG und Speichermedien-Wiedergewinnung mittels des ALOG werden tvpischerweise unterschiedliche sichere Punkte aufweisen und entsprechend gekürzt sein. Insbesondere kann ein gekürzter Teil eines RLOG noch für Speichermedien-Wiedergewinnung benötigt werden. Wenn dies der Fall ist, wird der gekürzte Teil ein Teil des ALOG.
Die ALOG-Kürzung benutzt RLOG-Fixpunkte. Ein RLOG-Fixpunkt bestimmt einen sicheren Punkt, der die Kürzung des RLOG ab dem Zeitpunkt des Fixpunktes erlaubt. Das liegt daran, daß alle Versionen der Daten im Dauerspeicher neuer sind als dieser sichere Punkt, ansonsten würde der Punkt nicht sicher sein.
Um ein ALOG zu kürzen werden Blöcke in Dauerspeichern zunächst in dem Archivierungsspeicher gesichert. Wenn das abgeschlossen ist, wird eine Archivierungs-Fixpunkt- Aufzeichnung an eine einvernehmliche Position, z.B. im Archivierungsspeicher, geschrieben, um die RLOG-Fixpunkte zu kennzeichnen, die aktuell waren, als die Bestimmung des Archivierungs-Fixpunktes begann.
Ein ALOG kann an dem sicheren Punkt gekürzt werden, der durch dem RLOG-Fixpunkt gekennzeichnet ist, der in dem Archivierungs-Fixpunkt für Speichermedien-Wiedergewinnung benannt ist. Alle Dauerspeicher-Blöcke werden in dem Archivierungsspeicher geschrieben, nachdem dieser RLOG-Fixpunkt gemacht wurde, und spiegeln daher all die Änderungen, die vor diesem sicheren Punkt des Fixpunktes gemacht wurden, wider. Während der Blocksicherung knnen mehrere zusätzliche RLOG- Fixpunkte genommen werden. Diese beeinflussen nicht die ALOG- Kürzung, da es keine Sicherheit dafür gibt, daß die beteiligten Logbuch-Aufzeichnungen alle in die Zustände der Blöcke im Archivierungsspeicher Eingang gefunden haben. Aktionen, die nicht wiederholt werden müssen, die jedoch in einem ALOG übrigbleiben, werden als nicht anwendbar erkannt und während dem Speichermedien-Wiedergewinnungsverfahren außer acht gelassen.
Fixpunkte werden in das RLOG geschrieben. Um den letzten ins RLOG geschriebenen Fixpunkt zu finden, wird seine Position in dem Dauerspeicher des entsprechenden Netzwerkknotens in einen Bereich mit globaler Information für dem Netzwerkknoten geschrieben. Die neueste Fixpunkt-Information ist typischerweise die erste Information, auf die während der Wiedergewinnung zugegriffen wird. Alternativ kann man das Ende des RLOG nach dem letzten Fixpunkt absuchen.
Fixpunkte bieten einen Haupvorteil eines reinen RLOG, der darin besteht, daß das System die ausdrückliche Kontrolle über die Größe des Redo-Logbuchs und daher über die für die Redo- Wiedergewinnung benötigte Zeit hat. Wenn das RLOG mit dem ULOG kombiniert werden würde, könnte ein sicherer Punkt aus den oben erläuterten Grund nicht zur Logbuch-Kürzung benutzt werden.
Außerdem erlaubt die Entfernung von Undo-Information aus dem RLOG dem System, die Logbuch-Kürzung durch Schreiben von Blöcken in dem Dauerspeicher zu kontrollieren. RLOG-Kürzung erfordert niemals dem Abbruch langer Transaktionen. Dies trifft nicht zu, wenn Logbücher gekürzt werden, die Undo-Information enthalten.
Das System übt Kontrolle über das RLOG aus, indem es Blöcke an ihre Positionen im Dauerspeicher zurückschreibt. In der Tat wird dieses Schreiben von Blöcken manchmal als Teil der Fixpunktroutine betrachtet. Auch Blöcke, die Wiedergewinnungs- LSNs haben, die älter sind, z.B. weiter zurück im RLOG, können in dem Dauerspeicher geschrieben werden. Das bewegt dem sicheren Punkt für das RLOG näher ans Ende des Logbuchs. Logbuch-Aufzeichnungen, deren Operationen in dem neu geschriebenen Block eingeflossen sind, werden nicht länger für die Redo-Wiedergewinnung benötigt und können daher gekürzt werden.
Speichermedien-Wiedergewinnung folgt dem gleichen grundlegenden Paradigma wie Systemabsturz-Wiedergewinnung. Versionen von Blöcken werden im Archivierungsspeicher fest aufgezeichnet. Wie oben erläutert, wird jedes ALOG aus dem gekürzten Teil eines der RLOGs gebildet. Das ALOG selbst kann in regelmäßigen Zeitabständen gekürzt werden, basierend darauf, welche Versionen von Blöcken im Archivierungsspeicher sind.
Nur mit einen in einem Block gespeicherten DSI, und nicht einem LSN, ist es nicht möglich zu wissen, welches Logbuch das letzte war, das für die Aktualisierung des Archivierungsspeicher-Blocks verantwortlich war, noch wo diese Aufzeichnung sich im RLOG befindet. Folglich ist die Information in dem Blöcken ungenügend, um den richtigen Punkt für die Kürzung der ALOGs oder RLOGs zu bestimmen. Die Tabelle schmutziger Blöcke kann jedoch als ein Leitfaden bein Kürzen des RLOG benutzt werden. Und ein sicherer RLOG-Punkt kann benutzt werden, um einen sicheren ALOG-Punkt zu bilden.

F. ULOG-Operationen

1. ULOG-Verwaltung
Außer dem Vorteilen, die das Trennen der RLOGs von dem ULOGs für die RLOG-Operation hat, gibt es auch Vorteile, die eine solche Trennung für die ULOG-Operation hat. Beispielsweise kann ein transaktions-spezifisches ULOG verworfen werden sobald eine Transaktion quittiert. Daher ist Speicherplatzverwaltung für ULOGs einfach und Undo-Information verbleibt nicht lange im Dauerspeicher.
Außerdem kann häufig, wie unten erläutert, das dauerhafte Schreiben von Undo-Aufzeichnungen in das Logbuch vermieden werden. Eine Undo-Aufzeichnung muß nur geschrieben werden, wenn ein Block, der unquittierte Daten enthält, in dem Dauerspeicher geschrieben wird.
Ein Nachteil getrennter ULOGs und RLOGs bei einem Redo- Logbuch liegt darin, daß zwei Logbücher modifiziert werden müssen, um dem WAL-Protokoll zu genügen, wenn ein Block mit unquittierten Daten in dem Dauerspeicher geschrieben wird. Allgemein sollte jedoch das Schreiben von unquittierten Daten in dem Dauerspeicher ausreichend selten auftreten, so daß die Trennung von Logbüchern einen Nettonutzen liefert, selbst in der Leistung.
Für N-Logbuch-Undo können mehrere Netzwerkknoten gleichzeitig unquittierte Daten in einem Block haben. Ein Systemabsturz würde erfordern, daß diese Transaktionen alle rückgängig gemacht werden, was beispielsweise eine Sperrung während der Undo-Wiedergewinnung erforderlich machen kann, um die Blockzugriffe zu koordinieren.
Um sicherzustellen, daß alle Blöcke hinsichtlich der Undo- Wiedergewinnung vom ein-Logbuch-Typ sind, wird es niemals gestattet, daß ein Block, der unquittierte Daten von einem Netzwerkknoten enthält, von einem zweiten Netzwerkknoten aktualisiert wird. Dies kann durch eine Sperrgranularität erreicht werden, die nicht kleiner ist als ein Block. Ein anfordernder Netzwerkknoten wird dann einen Block erhalten, in dem niemals ein Undo-Verfahren durch einen anderen Netzwerkknoten erforderlich ist. Daher wurde beispielsweise, wenn eine Transaktion von einem anderen Netzwerkknoten einen Block aktualisiert hatte und dann abbricht, die Wirkung dieser Transaktion bereits rückgängig gemacht.
Wenn auch ein-Logbuch-Undo die Komplexität verringert, ist die Auswirkung des N-Logbuch-Undo zur Zeit der Wiedergewinnung auf die System-Leistungsfähigkeit viel geringer als die für N- Logbuch-Redo. Das liegt daran, daß nur die kleine Gruppe von Transaktionen, die zum Zeitpunkt des System-absturzes unquittiert waren, rückgängig gemacht werden müssen. Und eine Sperrgranularität, die nicht kleiner als ein Block ist, kann die Nebenläufigkeit beträchtlich verringern.
Die Technik der vorliegenden Erfindung wird gewöhnlich die Notwendigkeit vermeiden, wegen einer kurzen Transaktion in das ULOG zu schreiben. Dies liegt daran, weil selten ein Cache- Speicherschlitz, der einen Block mit unquittierten Daten von irgendeiner besonderen kurzen Transaktion enthält, gebraucht wird. Die Gründe für solche Seltenheit liegen darin, daß die meisten kurzen Transaktionen quittieren oder abbrechen sollten, bevor ihre Cache-Speicherschlitze benötigt werden.
Sollte ein Cache-Speicherschlitz, der erhascht wurde, einen Block mit unquittierten Daten enthalten, verlangt das WAL-Protokoll das Schreiben von Undo-Aufzeichnungen in alle geeigneten ULOGs. Das WAL-Protokoll wird für das ULOG mit dem erzwungenen Schreiben jedes ULOG durch die Aufzeichnungen, die durch die ULastLSN im Eintrag für dem Block in der Tabelle schmutziger Blöcke gekennzeichnet sind, durchgesetzt. Wie oben erläutert, kennzeichnen die ULastLSNS die Undo-Aufzeichnungen für die letzte Aktualisierung des Blockes in jedem ULOG.
Mit dem WAL-Protokoll ist die Information, die zum Speichern der Zustände von Blöcken ohne Aktualisierungen einer Transaktion benötigt wird, immer dauerhaft im ULOG einer Transaktion gespeichert, bevor die Dauerspeicherversion des Blockes mit dem neuen Zustand überschrieben wird. Daher ist der Zustand der Blöcke ohne Aktualisierungen einer Transaktion immer dauerhaft vor der Transaktionsquittierung. Diese Information ist entweder: (i) in der Blockversion im Dauerspeicher, (ii) "Redo-wiederherstellbar" aus der Version im Dauerspeicher unter Verwendung der RLOG-Information aus vorhergehenden Transaktionen, oder (iii) aus einer Version, die durch (i) oder (ii) produziert wurde, Undo-wiederherstellbar unter Verwendung der Undo-Information, die entweder im ULOG durch das WAL-Protokoll für diese Transaktion protokolliert ist, oder während der Redo-Wiedergewinnung erzeugt wird.
Für die Blöcke im Dauerspeicher, die noch in einem früheren Zustand sind, ist es möglich, RLOG-Aufzeichnungen ohne entsprechende ULOG-Aufzeichnungen zu haben. Dies ist dort üblich, wo es "optionales" Undo-Protokollieren gibt. Es ist auch möglich, ULOG-Aufzeichnungen ohne entsprechende RLOG- Aufzeichnungen für solche Blöcke zu haben. In diesem Fall können die ULOG-Aufzeichnungen außer acht gelassen werden.
Daher müssen nicht alle Aktionen, die nach der Redo- Wiedergewinnung rückgängig gemacht werden müssen, im ULOG gefunden werden. Sollte das System abstürzen, müssen die fehlenden Undo-Aufzeichnungen aus dem Redo-Aufzeichnungen und dem früheren Blockzuständen erzeugt werden. Solange eine Aktion nur von dem Blockzustand und dem Wertparametern der protokollierten Aktion abhängt, wird die Erzeugung von Undo- Aufzeichnungen möglich sein, da alle Information, die verfügbar war, als die Aktion ursprünglich durchgeführt wurde, an diesem Punkt verfügbar ist.
Aktionen enden aus zwei Gründen im ULOG: entweder zwingt das WAL-Protokoll eine Puffer-Aufzeichnung in das ULOG, weil der Block in dem Dauerspeicher geschrieben wurde, oder das Schreiben des ULOG zur WAL-Durchsetzung führt zu einem Schreiben vorangehender ULOG-Aufzeichnungen und, in einigen Fällen, folgender ULOG-Aufzeichnungen, die sich im Undo-Puffer befinden.
Für diese Aktionen ist es nicht notwendig, Undo- Aufzeichnungen während der Wiedergewinnung zu erzeugen, da diese Aufzeichnungen mit Sicherheit in einem ULOG sind. Das ist wichtig, da es nicht möglich sein könnte, die ULOG-Aufzeichnung für die Redo-protokollierte Aktion zu konstruieren, da die Version des Blockes im Dauerspeicher einen Zustand hat der nach der Aktion kommt. Glücklicherweise sind es genau diese Blöcke, für die ULOG-Aufzeichnungen bereits existieren.
Während des Redo wurden die fehlenden Undo-Aufzeichnungen erzeugt. Mit dem Ende des Redo würde die Vereinigung aus erzeugten Undo-Aufzeichnungen und Undo-Aufzeichnungen in den ULOGs in der Lage sein, alle unquittierten Transaktionen 4 zurückzurollen.

2. ULOG-Optimierung

Mit der vorliegenden Erfindung kann der Gebrauch des ULOG optimiert werden, indem sichergestellt wird, daß der Inhalt eines Undo-Logbuch-Puffers nur in ein ULOG geschrieben wird, wenn es notwendig ist. Im allgemeinen muß der Undo-Puffer nur in einem ULOG gespeichert werden, wenn ein Block, der unquittierte Daten von einer aktuellen Transaktion enthält, in dem Dauerspeicher geschrieben wird. Wenn die Transaktion quittiert wurde, besteht keine Notwendigkeit, die Aktualisierungen in der Transaktion rückgängig zu machen, und der Undo-Puffer kann daher verworfen werden.
Figur 10 zeigt ein Flußdiagramm 1000 eines Verfahrens zum Ausführen dieser ULOG-Optimierung unter Verwendung des WAL- Protokolls. Es geht davon aus, daß eine Version des Blockes in dem Dauerspeicher geschrieben werden muß.
Wenn der zu schreibende Block unquittierte Daten enthält (Schritt 1010), dann muß der Redo-Puffer in dem RLOG in Dauerspeicher geschrieben werden, und alle Undo-Puffer werden in ULOGs im Dauerspeicher geschrieben (Schritt 1020).
Nach dem Schreiben der Redo-Puffer in das RLOG und der Undo-Puffer in die ULOGs (Schritt 1020), oder falls die Blöcke keine unquittierten Daten enthielten (Schritt 1010), wird der Block in dem Dauerspeicher geschrieben (Schritt 1030). Dies stimmt mit dem WAL-Protokoll überein.
Folglich werden die Undo-Puffer nur geschrieben, wenn unquittierte Daten zu speichern sind. Jedesmal wenn eine Transaktion quittiert, kann der entsprechende Undo-Logbuch- Puffer verworfen werden, da er nie jemals in dem Dauerspeicher geschrieben werden muß. Weiterhin kann das ULOG selbst für die Transaktion verworfen werden, da ein Rückgängigmachen (Undo) jetzt nie erforderlich ist.
Eine quittierte Transaktion wird durch das Aufzeichnen aller Redo-Aufzeichnungen für die Transaktion im RLOG im Dauerspeicher dauerhaft gemacht. Der aktualisierte Block kann zu irgendeinem späteren Zeitpunkt in dem Dauerspeicher geschrieben werden. Selbst wenn es einen Absturz gäbe bevor der aktualisierte Block geschrieben wurde, könnte das RLOG wiedererlangt werden, um den Zustand des Blockes wiederherzustellen, das System weiß, daß eine Transaktion quittiert ist, indem es eine Quittier-Aufzeichnung im RLOG speichert.

3. Die Transaktion bricht ab

Ein ULOG kann folglich verworfen werden, wenn eine Transaktion quittiert, da die Rückgängigmachung der Wirkungen einer Transaktion nicht länger erforderlich ist. Für einen Transaktionsabbruch ist die Situation etwas anders. Bevor die ULOG-Aufzeichnungen für eine Transaktion verworfen werden können, ist es notwendig sicherzustellen, daß alle Blöcke, die durch eine abbrechende Transaktion geändert wurden, nicht nur ihre Anderungen rückgängig gemacht erhalten, sondern auch, daß die sich daraus ergebenden rückgängig gemachten Blockzustände irgendwo anders als in einem ULOG dauerhaft gespeichert werden. Entweder müssen die Blöcke selbst in ihrem rückgängig gemachten Zustand in dem Dauerspeicher geschrieben werden ("Zwang"- Abbruch genannt), oder die Undo-Transaktionen müssen geschrieben und in das RLOG gezwungen werden ("Nicht-Zwang"- Abbruch genannt). Ahnlich dem Quittieren von Transaktionen beseitigt das Protokollieren von Aktionen im RLOG in diesem Fall das Erfordernis, Blöcke in dem Dauerspeicher zu zwingen.

a. Nicht-Zwang Abbruch

Ein Nicht-Zwang Abbruch kann realisiert werden, indem die Undo-Operationen als zusätzliche Aktionen der abbrechenden Transaktion behandelt werden, die die Wirkung der vorangehenden Aktualisierungen umkehren. Solche "kompensierenden" Aktionen werden in RLOG als "Kompensations-Logbuch-Aufzeichnungen" (CLRs, compensation log records) protokolliert. Kompensations-Logbuch-Aufzeichnungen sind effektiv Undo- Aufzeichnungen, die in das RLOG geschoben wurden. Zusätzliche Information ist jedoch erforderlich, um diese Aufzeichnungen von anderen RLOG-Aufzeichnungen zu unterscheiden. Züsätzlich wird ein SI benötigt, um den CLR korrekt in bezug auf andere protokollierte zu wiederholende Transaktionen einzuordnen.
Figur 11 zeigt einen CLR 1100 mit mehreren Attributen. Das TYPE-Attribut 1110 kennzeichnet diese Logbuch-Aufzeichnung als eine Kompensations-Logbuch-Aufzeichnung.
Das TID-Attribut 1120 ist ein eindeutiger Kennzeichner für die Transaktion. Es hilft beim Auffinden der diesem RLOG-CLR entsprechenden ULOG-Aufzeichnung.
Das BSI-Attribut 1130 ist der Vorzustands-Kennzeichner, wie oben beschrieben. In diesem Zusammenhang kennzeichnet das BSI-Attribut 1130 dem Blockzustand zu dem Zeitpunkt, zu dem der CLR angewendet wird.
Das BID-Attribut 1140 kennzeichnet dem Block, der durch die mit dieser Aufzeichnung protokollierte Aktion modifiziert wurde.
Das UNDO_DATA-Attribut 1150 beschreibt das Wesen der rückgängig zu machenden Aktion und bietet genügend Information dafür, daß die Aktion rückgängig gemacht werden kann, nachdem ihre verknüpfte ursprüngliche Aktion in dem Blockzustand eingebracht wurde. Der Wert für das UNDO_DATA-Attribut 1150 kommt von der entsprechenden Undo-Aufzeichnung, die entweder in einem ULOG oder in einem Undo-Puffer gespeichert ist.
Das RLSN-Attribut 1160 ist die RLOG-Aufzeichnung, die die gleiche Aktion beschreibt, für die diese Aktion das Undo ist. Dieses Attribut kommt vom RLSN-Attribut 440 der ULOG- Aufzeichnung.
Das LSN 1170, das nicht ausdrücklich gespeichert werden muß, da es durch seine Position im RLOG identifiziert werden kann, kennzeichnet diesen CLR eindeutig im RLOG. Das LSN wird benutzt, um die Redo-Suche und Fixpunktroutine im RLOG zu kontrollieren.
Wie bei der Transaktionsquittierung sollten, wenn eine Transaktion abbricht, alle Redo-Aufzeichnungen, die die Aktionen der Transaktion beschreiben, in das RLOG geschrieben werden. Für die abgebrochene Transaktion schließt dies die Undo-Aktionen in dem CLRs mit ein. Für eine Quittierung wird das RLOG gezwungen sicherzustellen, daß alle Redo- Aufzeichnungen für die Transaktion stabil gespeichert sind; Für einen Abbruch ist dies nicht streng notwendig. Die benötigte Information ist noch im ULOG vorhanden. Jedoch kann das ULOG nicht verworfen werden bis die CLRs für die abbrechende Transaktion dauerhaft in das RLOG geschrieben wurden. Die CLRs im RLOG ersetzen dann die ULOG-Aufzeichnungen.
Eine wünschenswerte Eigenschaft des Nicht-Zwang Weges ist, daß für Speichermedienwiedergewinnung nur die Redo-Phase benötigt wird. Aktualisierungen werden in der Reihenfolge angewendet, daß sie während der ALOG-Zusammenlegung verarbeitet werden. Es wird keine getrennte Undo-Phase während der Verarbeitung des ALOG benötigt, da jedes benötigte Undo durch Anwendung von CLRs erreicht wird.
Eine zweite Tabelle, Tabelle aktiver Transaktionen genannt, zeichnet die Information auf, die benötigt wird, um Undo-Operationen zu bewirken. Wie die Tabelle schmutziger Blöcke 900 wird die Tabelle aktiver Transaktionen zu einem Teil der Fixpunkt-Information im RLOG, so daß ihre Information bewahrt wird, wenn das System abstürzt.
Die Tabelle aktiver Transaktionen zeigt Transaktionen, deren Rückgängigmachung erforderlich sein könnte, dem Zustand des Undolredo-Protokollierens und dem Undo-Fortgang an. Es muß genügend Information in der Tabelle aktiver Transaktionen verschlüsselt sein, um Wiedergewinnung von allen Systemabstürzen sicherzustellen, einschließlich derer, die während der Wiedergewinnung selbst auftreten. Es kann auch einige Information, die die Wiedergewinnungsleistung verbessert, eingeschlossen sein.
Figur 12 zeigt ein Beispiel einer Tabelle aktiver Transaktionen 1200. Die Tabelle 1200 umfaßt die Aufzeichnungen 1201, 1202 und 1207. Jeder der Aufzeichnungen umfaßt mehrere Attribute.
Das TID-Attribut 1210 ist ein eindeutiger Kennzeichner für die Transaktion. Er ist der gleiche wie der Transaktions- Kennzeichner, der für RLOG-Aufzeichnungen benutzt wird.
Das STATE-Attribut 1220 zeigt an, ob eine aktive Transaktion als Teil einer Zweiphasen-Quittierung "vorbereitet" wird. Eine Zweiphasen-Quittierung wird benutzt, wenn mehrere Netzwerkknoten an einer Transaktion teilnehmen. Um eine solche Transaktion zu quittieren, müssen alle Netzwerkknoten zuerst die Transaktion vorbereiten (Phase 1), bevor sie sie quittieren können (Phase 2). Die Vorbereitung wird durchgeführt, um teilweise Quittierungen zu vermeiden, die auftreten würden, wenn ein Netzwerkknoten quittiert, ein anderer jedoch abbricht. Eine vorbereitete Transaktion muß in der Tabelle aktiver Transaktionen 1200 behalten werden, da es notwendig sein könnte, daß sie zurückgerollt werden muß. Anders als eine nicht-vorbereitete Transaktion sollte eine vorbereitete Transaktion nicht automatisch abgebrochen werden.
Das ULOGloc-Attribut 1230 zeigt die Position des transaktionsspezifischen ULOG an. Dieses Attribut muß nur dann vorhanden sein, sollte es keinen andereren Weg geben, um das ULOG zu finden. Beispielsweise könnte das TID 1210 einen Ersatzweg zum Auffinden des ULOG für die Transaktion bieten.
Das HIGH-Attribut 1240 zeigt das RLOG-LSN der Aktion an, die die letzte Aktion mit einer Undo-Aufzeichnung ist, die für diese Transaktion ins ULOG geschrieben wurde. Diese ULOG- Aufzeichnung enthält ein RLOG-LSN in RLSN, so daß RLOG- Aufzeichnungen, die dem RLSN folgen, nach einem Systemabsturz während des Redo erzeugt werden müssen, um bereit zu sein, die Transaktion zurückzurollen, sollte sie nicht quittiert worden sein.
Das NEXT-Attribut 1250 zeigt das RLOG-LSN der nächsten Aktion in der Transaktion an, die rückgängig gemacht werden muß. Für Transaktionen, die nicht zurückgerollt werden, ist das NEXT-Attribut 1250 die Aufzeichnungsnummer für die letzte Aktion, die von der Transaktion durchgeführt wurde. Obwohl einige Systeme CLRs während der Wiedergewinnung rückgängig machen, werden sie in der bevorzugten Ausführungsform nicht rückgängig gemacht. Stattdessen werden CLRs gekennzeichnet (mittels des TYPE-Attributs), so können sie während der Wiedergewinnung identifiziert werden.
Wegen der sequentiellen Natur des ULOG wird, wenn eine Undo-Aufzeichnung in ein ULOG gezwungen wird, auch sichergestellt, daß alle vorangehenden Undo-Aufzeichnungen dauerhaft sind. RLOG-Aufzeichnungen werden in der gleichen Reihenfolge wie ULOG-Aufzeichnungen geschrieben. Daher, wenn eine RLOG-Aufzeichnung gefunden wird, der kein Redo benötigt, beispielsweise weil seine Auswirkung bereits in der Blockversion im Dauerspeicher ist, dann haben alle vorangehenden RLOG-Aufzeichnungen Undo-Aufzeichnungen im ULOG. Das trat auf, da das ULOG modifiziert wurde als der Block geschrieben wurde, daher wurden alle früheren ULOG- Aufzeichnungen zur gleichen Zeit geschrieben. Wenn Undo- Aufzeichnungen während des Redo für diese Transaktion erzeugt wurden, können sie verworfen werden, da alle solchen früheren Aufzeichnungen bereits im ULOG vorhanden sein müssen.
Das RLOG-LSN der letzten RLOG-Aufzeichnung, für das eine ULOG-Aufzeichnung geschrieben wurde, ist im HIGH-Attribut 1240 (Figur 12) des Eintrags der Tabelle aktiver Transaktionen für die Transaktion gespeichert. RLOG-Aufzeichnungen, die dieser angezeigten Redo-Logbuch-Aufzeichnung vorangehen, erzeugen keine Undo-Aufzeichnungen während des Redo, da sie alle bereits ULOG-Aufzeichnungen haben. Für RLOG-Aufzeichnungen, die dem durch HIGH angezeigten folgen, könnte es notwendig sein, Undo- Aufzeichnungen zu erzeugen.
Die Erzeugung von Undo-Aufzeichnungen kann auch vermieden werden, wenn die Zahl der Undo-Aufzeichnungen, die für jede Transaktion bereits angewendet wurde, sorgfältig überwacht wird. Daher ist die Undo-"Hochwasser-Marke" im NEXT-Attribut 1250 der Tabelle aktiver Transaktionen 1200 verschlüsselt. Das NEXT-Attribut 1250 enthält die Aufzeichnungsnummer der nächsten Undo-Aufzeichnung, die auf die Transaktion angewendet werden muß.
Während normalem Betrieb ist das NEXT-Attribut 1250 immer die Aufzeichnungsnummer für die neueste Transaktion einer Transaktion. Der Wert im NEXT-Attribut 1250 wird erhöht, wenn diese Aktionen protokolliert werden. Während der Undo- Wiedergewinnung wird der Wert im NEXT-Attribut 1250 erniedrigt, nachdem jede Undo-Aktion angewendet ist und ihr CLR protokolliert ist, wobei ihre Vorgänger-Undo-Aufzeichnung als nächste Undo-Aktion benannt wird. Sollte während des Zurückrollens ein Systemabsturz auftreten, müssen Undo- Aufzeichnungen mit höheren Aufzeichnungsnummern als die vom NEXT-Attribut 1250 angezeigte nicht wiederangewendet werden, und müssen daher während des Redo nicht wieder erzeugt werden.
Das Endergebnis ist, daß während des Redo Undo- Aufzeichnungen für die RLOG-Aufzeichnungen erzeugt werden, deren Aufzeichnungsnummern zwischen die Werte für das HIGH Attribut 1240 und das NEXT-Attribut 1250 fallen. Jedesmal wenn der Wert des HIGH-Attributs 1240 größer oder gleich dem Wert des NEXT-Attributs 1250 ist, müssen überhaupt keine Undo- Aufzeichnungen erzeugt werden.

b. Zwang-Abbruch

Beim "Zwang"-Abbruch werden keine CLRs geschrieben. Stattdessen werden, wenn die Blöcke rückgängig gemacht werden, die Blöcke selbst in dem Dauerspeicher gezwungen. Bei dieser Art des Abbruchs besteht die Notwendigkeit, stabil die Kenntnis zu bewahren, daß ein Block das Ergebnis der Anwendung einer Undo-Aufzeichnung, ebenso wie die Reihenfolge, in der die Undo- Operationen durchgeführt wurden, beinhaltet, ohne einen CLR dafür zu schreiben.
Das Ziel ist es, N-Logbuch-Undo zu unterstützen, bei dem mehrere Netzwerkknoten als Folge eines Systemabsturzes Transaktionen in einem einzelnen Block rückgängig machen können. Daher muß der Fortgang von Undo-Operationen, die von jedem Netzwerkknoten durchgeführt werden, fest aufgezeichnet werden. Das ist das, was CLRs im Nicht-Zwang-Fall erreichen. Ohne CLRs wird eine andere Technik benötigt.
Eine Alternative besteht darin, die benötigte Information in dem Block zu schreiben, der in dem Dauerspeicher geht. Obwohl ein CLR eine vollständige Beschreibung der Undo-Aktion enthält, wird nicht alles von dieser Beschreibung benötigt. Was im Zwang-Abbruchs-Fall gemacht werden muß ist, die Ergebnisse der Undo-Transaktionen und, welche davon rückgängig gemacht wurden, aufzuzeichnen.

G. Normale Operationen

Während des Normalbetriebs haben Transaktionsstart-, Blockaktualisierungs-, Blockschreibe-, Transaktionsabbruch-, Transaktionsvorbereite- und Transaktionsquittier-Operationen einen Einfluß auf dem Wiedergewinnungsbedarf. Daher müssen während des Normalbetriebs Schritte hinsichtlich des Protokollierens eingeleitet werden, um sicherzustellen, daß Wiedergewinnung möglich ist.
Figur 13 enthält ein Verfahren 1300 für Transaktionsstart- Operationen. Zuerst muß eine START_TRANSACTION-Aufzeichnung in das RLOG geschrieben werden (Schritt 1310). Danach wird die Transaktion in die Tabelle aktiver Transaktionen 1200 im "aktiven" Zustand eingetragen (Schritt 1320). Dann werden das ULOG für die Transaktion und ihre Identität im ULOGloc 1230 aufgezeichnet (Schritt 1330). Zuletzt werden die HIGH- 1240 und NEXT- 1250 Werte auf Null gesetzt (Schritt 1340).
Figur 14 zeigt ein Verfahren 1400 für eine Blockaktualisierungs-Operation. Zuerst wird die erforderliche Nebenläufigkeitskontrolle durchgeführt, um dem Block für Aktualisierung zu sperren (Schritt 1410). Auf dem Block wird dann vom Dauerspeicher zugegriffen, wenn er sich nicht bereits im Cache-Speicher befindet (Schritt 1420). Die angezeigte Transaktion wird dann mit der Version des Blockes im Cache- Speicher durchgeführt (Schritt 1430). Als nächstes wird der DSI des Blockes mit dem ASI für die Aktion aktualisiert (Schritt 1440). Dann werden sowohl RLOG- als auch ULOG-Aufzeichnungen für die Aktualisierung konstruiert und in ihre passenden Puffer gelegt (Schritt 1450). Die Lastlsns 950 (Figur 9) werden geeignet aktualisiert (Schritt 1460). Dann wird der NEXT- 1250 Wert auf das ULOG-LSN der Undo-Aufzeichnung für diese Aktion gesetzt (Schritt 1470).
Wenn der Block sauber war (Schritt 1475), wird er schmutzig gemacht (Schritt 1480). Er wird dann in die Tabelle schmutziger Blöcke 900 (Figur 9) gegeben, wobei das Wiedergewinnungs-LSN 920 auf dem LSN für seine RLOG- Aufzeichnung gesetzt wird (Schritt 1485).
Figur 15 enthält ein Flußdiagramm 1500 für eine Blockschreibe-Operation, wenn der Block unquittierte Daten enthält. Zuerst wird das WAL-Protokoll durchgesetzt (Schritt 1510). Besonders vor dem Schreiben des Blockes in dem Dauerspeicher werden alle Undo-Puffer bis hinauf zu dem entsprechenden LastULSN 958 (Figur 9) für dem Block geschrieben, und der RLOG-Puffer wird bis hinauf zum LastRLSN 955 (Figur 9) geschrieben. Für jede Transaktion, die in dem LastULSNs für dem Block gekennzeichnet ist, wird HIGH gesetzt für diese Transaktionen auf die RLOG-LSN-Werte in dem RLSN- Attributen der Undo-Aufzeichnungen, die durch die LastULSN- Attribute aus der Tabelle schmutziger Blöcke gekennzeichnet sind. Jeder LastULSN muß sowohl eine Transaktion mittels einem TID als auch ein ULOG-LSN kennzeichnen. Für diese Logbücher besteht Zeit, wenn nicht geschrieben werden muß, da diese Aufzeichnungen bereits geschrieben wurden.
Der Block wird dann aus der Tabelle schmutziger Blöcke 900 entfernt (Schritt 1520), und der Block wird in dem Dauerspeicher geschrieben (Schritt 1530). Dann kann eine Blockschreibe-Aufzeichnung in das PLOG geschrieben werden, um anzuzeigen, daß der Block in dem Dauerspeicher geschrieben wurde, aber das ist optional. Diese Blockschreibe-Aufzeichnung muß nicht erzwungen werden.
Figur 16 enthält ein Flußdiagramm 1600 für eine Transaktionsabbruch-Operation. Zuerst wird die Undo- Aufzeichnung, die durch dem Wert im NEXT-Feld 1250 angezeigt wird, lokalisiert (Schritt 1610). Dann wird die erforderliche Nebenläufigkeitskontrolle mit dem Blöcken durchgeführt, die genauso eingebunden sind, als ob sie mit normalen Aktualisierungen bearbeitet würden (Schritt 1620).
Als nächstes wird die aktuelle Undo-Logbuch-Aufzeichnung auf ihren bestimmten Block angewendet (Schritt 1630), und ein CLR für die Undo-Aktion wird im RLOG geschrieben (Schritt 1640). Dann wird der Wert des NEXT-Feldes 1250 erniedrigt, um auf die nächste Undo-Logbuch-Aufzeichnung hinzuweisen, die als die "aktuelle" Undo-Aufzeichnung angewendet werden muß (Schritt 1640).
Wenn irgendwelche Undo-Logbuch-Aufzeichnungen für die Transaktion übrig bleiben (Schritt 1660), wird die Kontrolle an Schritt 1610 zurückgegeben. Andernfalls wird eine ABORT- Aufzeichnung in das RLOG gesetzt (Schritt 1670). Das RLOG wird dann bis hinauf zur ABORT-Aufzeichnung im Dauerspeicher gespeichert (Schritt 1680). Das ULOG wird dann verworfen (Schritt 1690). Zuletzt wird die Transaktion aus der Tabelle aktiver Transaktionen 1200 (Figur 12) entfernt (Schritt 1695).
Figur 17 zeigt ein Flußdiagramm 1700 für eine Transaktionsvorbereite-Operation. Zuerst wird eine Vorbereite- Logbuch-Aufzeichnung für die Transaktion in das RLOG geschrieben (Schritt 1710). Danach wird das RLOG bis hinauf zu dieser Vorbereite-Logbuch-Aufzeichnung modifiziert (Schritt 1720). Zuletzt wird der Zustand der Transaktion, die "vorbereitet" wird, in der Tabelle aktiver Transaktionen 1200 geändert (Schritt 1730).
Figur 18 zeigt ein Flußdiagramm 1800 für eine Transaktionsquittier-Operation. Zuerst wird eine Quittier- Logbuch-Aufzeichnung für die Transaktion in das RLOG geschrieben (Schritt 1810). Als nächstes wird das RLOG bis hinauf zu dieser Aufzeichnung modifiziert (Schritt 1820). Dann wird das ULOG verworfen (Schritt 1830). Zuletzt wird die Transaktion aus der Tabelle aktiver Transaktionen 1200 entfernt (Schritt 1880).

H. Systemabsturz -Wiedergewinnungsverfahren

In der vorangehenden Diskussion wurden unterschiedliche Aspekte von Logbüchern, Zustandskennzeichnern und Wiedergewinnung diskutiert. Sie können zu einem wirkungsvollen Wiedergewinnungsschema in unterschiedlichen Verfahren kombiniert werden. Das bevorzugte Verfahren wird unten beschrieben.

1. Analysierungsphase

Eine Analysierungsphase ist nicht streng notwendig. Ohne eine Analysierungsphase kann jedoch einige unnötige Arbeit während der anderen Wiedergewinnungsphasen verrichtet werden.
Der Zweck der Analysierungsphase ist es, dem Systemzustand, wie er im letzten Fixpunkt gespeichert ist, auf dem Zustand der Datenbank zum Zeitpunkt des Systemabsturzes zu bringen. Um dies zu tun, wird die Information im letzten vollständigen Fixpunkt im RLOG gelesen und benutzt, um die Werte für die Tabelle schmutziger Blöcke 900 (Figur 9) und die Tabelle aktiver Transaktionen 1200 (Figur 12) zu initialisieren. Dann werden RLOG-Aufzeichnungen, die diesem letzten Fixpunkt folgen, gelesen. Die Analysierungsphase simuliert die protokollierten Aktionen in ihrer Wirkung auf die beiden Tabellen.
Hinsichtlich der bestimmten Aufzeichnungen werden Starttransaktions-Aufzeichnungen genauso behandelt wie eine Starttransaktions-Operation bezüglich der Tabelle aktiver Transaktionen. Aktualisierungs-Logbuch-Aufzeichnungen werden genauso behandelt wie eine Blockaktualisierung hinsichtlich der Tabelle schmutziger Blöcke 900 und der Tabelle aktiver Transaktionen 1200, aber die Aktualisierung wird nicht angewendet. Kompensations-Logbuch-Aufzeichnungen werden genauso behandelt wie eine Blockaktualisierung hinsichtlich der Tabelle schmutziger Blöcke 900 und der Tabelle aktiver Transaktionen 1200, außer daß der Wert des NEXT-Attributes 1250 erniedrigt und die Aktualisierung nicht angewendet wird.
Für Blockschreibe-Aufzeichnungen wird der Block aus der Tabelle schmutziger Blocke 900 entfernt. Für Abbruchtransaktions-Aufzeichnungen wird die Transaktion aus der Tabelle aktiver Transaktionen 1200 gelöscht. Für Vorbereitetransaktions-Aufzeichnungen wird der Zustand der Transaktion in der Tabelle aktiver Transaktionen 1200 auf "vorbereitet" gesetzt. Fur Quittiertransaktions-Aufzeichnungen wird die Transaktion aus der Tabelle aktiver Transaktionen 1200 gelöscht.
Um das HIGH-Attribut 1240 für die Transaktionen in der Tabelle aktiver Transaktionen 1200 wiederherzustellen, muß auf das ULOG zugegriffen werden, um das RLSN-Attribut der letzten in das ULOG geschriebenen Aufzeichnung zu finden. Dieses LSN wird zum Wert für das HIGH-Attribut 1240. Alternativ kann der Wert für das HIGH-Attribut 1240 aus dem Fixpunkt benutzt oder aktualisiert werden. Dieses RLOG-LSN kann benutzt werden, um die Erzeugung von Undo-Aufzeichnungen für Aktionen zu vermeiden, die bereits im ULOG für eine Transaktion aufgezeichnet sind. Nur für RLOG-Aufzeichnungen für eine Transaktion, die diesem Wert folgt, muß Undo-Information erzeugt werden.
Das NEXT-Attribut 1250 ist dann entweder (1) das RLOG-LSN der letzten Aktion, deren Logbuch-Aufzeichnung in das RLOG für die Transaktion geschrieben ist, falls diese Logbuch- Aufzeichnung für eine Aktualisierung ist, oder (2) das RLSN- Attribut des letzten für die Transaktion geschriebenen CLR. Folglich kann das NEXT-Attribut 1250 während des Analysierungsschrittes des RLOG wiederhergestellt werden. Das NEXT-Attribut 1250 kennzeichnet mittels des RLSN-Wertes in den ULOG-Aufzeichnungen die nächste Undo-Auf zeichnung, die ausgeführt werden muß. Es kann ebenso dazu benutzt werden, die Erzeugung von Undo-Aufzeichnungen für Aktionen zu vermeiden, die bereits dadurch kompensiert wurden, daß CLRs geschrieben wurden, um sie rückgängig zu machen. Folglich muß für Redo- Aufzeichnungen für eine Transaktion mit RLOG-LSNS, die größer sind als das NEXT-Attribut 1250 für die Transaktion in der Tabelle aktiver Transaktionen 1200, keine Information erzeugt werden, da das Undo gemacht wird, wenn die vorhandenen CLRs während der Redo-Phase der Wiedergewinnung angewendet werden.

2. Die Redo-Phase

In der Redo-Phase werden alle Blöcke, die in der rekonstruierten Tabelle schmutziger Blöcke 900 als schmutzig angezeigt werden, in dem Cache-Speicher gelesen. Dieses Lesen kann im ganzen erfolgen, überschnitten mit dem Durchsuchen des RLOG.
Einige Blöcke können von mehreren Netzwerkknoten gelesen werden, um zu bestimmen, ob sie in dem lokalen Redo mit eingeschlossen werden müssen, aber nur einer der Netzwerkknoten wird tatsächlich dem Redo für einen Block ausführen. Das kann jedoch beinahe vollständig vermieden werden, indem Blockschreibe-Aufzeichnungen in das RLOG geschrieben werden. Da Blockschreibe-Aufzeichnungen nicht gezwungen werden müssen, wird ein Block gelegentlich vom Dauerspeicher gelesen werden, wenn dies nicht notwendig ist. Die Strafe für ein solches Lesen ist jedoch gering.
Im Dauerspeicher ist eine ein-Logbuch-Version jedes Blockes vorhanden, so kann nur ein Netzwerkknoten Aufzeichnungen in seinem Logbuch haben, die einen BSI haben, der gleich dem DSI des Blockes ist. Dieser Netzwerkknoten ist derjenige, der das Redo-Verfahren unabhängig mit dem Block durchführen wird. Daher kann Redo parallel durch verschiedene Netzwerkknoten des Systems durchgeführt werden, jeder mit seinem eigenen RLOG. Hier wird keine Nebenläufigkeitskontrolle benötigt.
Die Redo-Phase rekonstruiert dem Zustand des Cache- Speichers des Netzwerkknotens, indem auf die schmutzigen Blöcke zugegriffen wird, die Redo benötigen, und die Änderungen wie in dem RLOG-Aufzeichnungen angezeigt abgelegt werden. Der sich daraus ergebende Cache-Speicher enthält die schmutzigen Blöcke in ihren Zuständen wie zum Zeitpunkt des Absturzes. Blöcke, die Gegenstand des Redo waren, wurden gesperrt. Die sich daraus ergebende Tabelle schmutziger Blöcke 900 und die Tabelle aktiver Transaktionen 1200 werden ähnlich rekonstruiert. Blöcke, die Gegenstand des Redo waren, wurden gesperrt.
Nur für Redo-Aufzeichnungen für schmutzige Blöcke, wie in der Tabelle schmutziger Blöcke 900 nach der Analysierungsphase angezeigt, kann eine Wiedervornahme notwendig sein. Die Redo- Suche des RLOG beginnt an dem frühesten Wiedergewinnungs-LSN 920, das in der Tabelle schmutziger Blöcke 900 aufgezeichnet ist. Das ist der sichere Punkt für das Redo. Daher wird sichergestellt, daß alle Aktualisierungen für jeden Block, seit er in dem Dauerspeicher geschrieben wurde, in die Redo-Suche eingeschlossen sind.
Wie oben erläutert gibt es nur zwei Fälle, die auftreten können, wenn versucht wird, eine RLOG-Aufzeichnung auf ihren entsprechenden Block anzuwenden. Wenn der BSI der RLOG- Aufzeichnung nicht gleich dem DSI des Blockes ist, kann die protokollierte Aktion außer acht gelassen werden. Wenn stattdessen der BSI der RLOG-Aufzeichnung gleich dem DSI des Blockes ist, wird die geeignete Redo-Aktivität ausgeführt.
Das Redo-Phasen-Verfahren schließt das Wiederholen der Vergangenheit ein. Alle Aktualisierungs-RLOG-Aufzeichnungen werden, beginnend mit der RLOG-Aufzeichnung, die durch ein Wiedergewinnungs-LSN des Blockes angezeigt wird, angewendet, selbst diejenigen, die zu Transaktionen gehören, die nachfolgend rückgangig gemacht werden müssen. Das Prinzip hier ist, daß es für eine Aktion, die rückgängig gemacht werden muß, erforderlich ist, auf dem Block in genau dem Zustand angewendet zu werden, auf dem die ursprüngliche Aktion angewendet wurde.
Bei der Anwendung einer RLOG-Aufzeichnung auf einen Block wird der DSI des Blockes auf dem ASI für die wiederholte Aktion aktualisiert. Der Netzwerkknoten verlangt eine geeignete Sperre des Blockes, wenn eine RLOG-Aktion angewendet wird. Das Redo muß nicht warten bis die Sperre gewährt wird, da kein anderer Netzwerkknoten eine Sperre verlangen wird. Die verlangte Sperre muß jedoch vor dem Beginn des Undo gewährt sein. Das ist der Weg auf dem Nebenläufigkeitskontrolle für die Undo-Phase initialisiert wird.
Wenn eine normale im RLOG protokollierte Aktualisierung ein Redo benötigt, kann es sein, daß eine ULOG-Aufzeichnung für sie erzeugt werden muß. Alle RLOG-Redo-Aufzeichnungen für eine Transaktion mit LSNS zwischen dem HIGH- und dem NEXT-Werten werden für sie erzeugte Undo-Information haben. Diese Information beinhaltet vorzugsweise ULOG-Aufzeichnungen mit RLSN-Attributen, die diese Aufzeichnungen kennzeichnen.
Wenn eine Aktion nicht wiederholt werden muß, werden frühere Undo-Aufzeichnungen, die unpassend erzeugt worden sein können, verworfen, da das ULOG mittels des WAL-Protokolls bis hinauf zur ULOG-Aufzeichnung für diese Aktion in dem Dauerspeicher geschrieben wurde. Das HIGH-Atribut 1240 kann zu diesem Zeitpunkt mit dem RLOG-LSN dieser Aufzeichnung aktualisiert werden, was, sollte ein Fixpunkt genommen werden, die redundante Undo-Aufzeichnungs-Erzeugung während der nachfolgenden Wiedergewinnung reduzieren wird, sollte der aktuelle Wiedergewinnungsprozeß scheitern.
Für jede Transaktion werden erzeugte Undo-Aufzeichnungen im ULOG-Puffer der Transaktion gespeichert. Diese Undo- Aufzeichnungen zuzüglich denen in ihrem ULOG und ihren CLRs stellen sicher, daß eine aktive Transaktion zurückgerollt werden kann. Daher werden am Ende der Redo-Phase alle notwendigen Undo-Logbuch-Aufzeichnungen vorhanden sein.

3. Die Undo-Phase

Undo-Wiedergewinnung ist vom N-Logbuch-Typ. Daher erfordert die Undo-Wiedergewinnungsphase Nebenläufigkeitskontrolle in der gleichen Weise wie sie während des Transaktions-Zurückrollens benötigt wird. Für mehrere Netzwerkknoten kann es erforderlich sein, Anderungen an demselben Block rückgängig zu machen. Normale Datenbank- Aktivität kann jedoch fortfahren sobald die Undo-Phase beginnt, gerade so wie normale Aktivität gleichzeitig mit einem Transaktionsabbruch weitergehen kann. Das ganze geeignete Sperren ist am richtigen Platz dies zu ermöglichen. Dies wird sichergestellt, indem die Undo-Phase nicht begonnen wird bis alle Netzwerkknoten ihre Redo-Phase abgeschlossen haben. Daher werden alle Sperren, die von irgendeinem Netzwerkknoten während des Redo verlangt werden, vor dem Beginn des Undo von dem passenden Netzwerkknoten gehalten.
Zuerst werden alle aktiven Transaktionen (aber keine vorbereiteten Transaktionen) in der Tabelle aktiver Transaktionen 1200 zurückgerollt. Die Undo-Bearbeitung geht, mit einer Ausnahme, genauso weiter wie beim Zurückrollen ausdrücklich abgebrochener Transaktionen. Einige Undo- Aufzeichnungen könnten sowohl in einem Undo-Puffer, wo sie während des Redo wiedererzeugt wurden, als auch in einem ULOG im Dauerspeicher vorhanden sein. Diese doppelten Undo- Aufzeichnungen können ermittelt und außer acht gelassen werden. Dies kann in eine Routine zum Erhalten der nächsten Undo- Aufzeichnung eingeschlossen werden, so daß der Rest des Codes um Transaktionen rückgängig zu machen, die zur Zeit des Absturzes aktiv waren, praktisch identisch sein kann zu dem Code, der benötigt wird, um eine Transaktion rückgängig zu machen, wenn das System normal funktioniert. Redundante ULOG- Aufzeichnungen unter diesen Quellen können entfernt werden, da alle Undo-Aufzeichnungen durch das LSN der RLOG-Aufzeichnung gekennzeichnet sind, auf die sie anwendbar sind.

V. Schlußfolgerung

Die Verwendung getrennter RLOGs und ULOGs ermöglicht die Optimierung einer protokollierenden Operation, indem sichergestellt wird, daß die Undo-Information nur in einem ULOG gespeichert wird, wenn dies absolut notwendig ist. Die Prüfung dafür, wann diese Notwendigkeit besteht, ist, ob alle Information, die für Anderungen benötigt wird, die in unquittierten Transaktionen eingeschlossen sind, gespeichert wurde oder wiederhergestellt werden kann.
Eine weitere Optimierung kann erreicht werden, indem die Anderungen, die während der Wiedergewinnung gemacht wurden, genau gezählt werden.
Es ist für Fachleute offensichtlich, daß Anderungen und Variationen gemacht werden können ohne vom Rahmen dieser Erfindung, wie sie in dem beiliegenden Patentansprüchen definiert ist, abzuweichen. Beispielsweise kann die in Figur 1 gezeigte Architektur anders sein, und die Anzahl der jedem Netzwerkknoten zugewiesenen Undo- und Redo-Logbücher kann variieren.

Claims

1. Datenverarbeitungswiedergewinnungsgerät mit:

einem Redo-Puffer, der einen Satz von Redo-Aufzeichnungen enthält, wobei der Redo-Puffer Information für quittierte und unquittierte Transaktionen umfaßt,

einem Undo-Puffer, der einen Satz von Undo-Aufzeichnungen enthält, wobei der Undo-Puffer Information nur für eine unquittierte Transaktion enthält und die Undo-Aufzeichnungen in dem Undo-Puffer getrennt von dem Redo-Aufzeichnungen in dem Redo-Puffer angesammelt sind, und

einer Logbuch-Managementroutine zum Starten einer unquittierten Transaktion, zum Aufzeichnen von Redo- Aufzeichnungen entsprechend der unquittierten Transaktion in dem Redo-Puffer, zum Aufzeichnen von Undo- Aufzeichnungen der unquittierten Transaktion in dem Undo-Puffer zum Quittieren der Transaktion, zum Speichern der Redo-Aufzeichnungen entsprechend der quit tierten Transaktion von dem Redo-Puffer zu einem Dauerspeicher und zum getrennten Löschen der Undo-Aufzeichnungen entsprechend der quittierten Transaktion von dem Undo-Puffer, während die Redo-Aufzeichnungen in dem Redo-Puffer zurückgehalten sind.

2. Datenverarbeitungswiedergewinnungsgerät nach Anspruch 1, weiterhin mit einer aktiven Transaktionstabelle, die in einem Speicher gespeichert ist und Eingaben entsprechend Transaktionen enthält, die nicht quittiert wurden.

3. Datenverarbeitungswiedergewinnungsgerät nach Anspruch 2, weiterhin mit einer Einrichtung, um aus der aktiven Transaktionstabelle eine Eingabe entsprechend einer ersten Transaktion zu entfernen, nachdem die erste Transaktion quittiert ist.

4. Datenverarbeitungswiedergewinnungsgerät nach Anspruch 2, weiterhin mit einer Einrichtung zum Speichern der Inhalte des Undo-Puffers in dem Dauerspeicher vor einem Speichern von Änderungen von entsprechenden unquittierten Transaktionen.

5. Verfahren zur Datenverarbeitungswiedergewinnung mit dem folgenden Schritten:

Vorsehen eines Redo-Puffers, der einen Satz von Redo-Aufzeichnungen enthält, wobei der Redo-Puffer Information für quittierte und unquittierte Transaktionen umfaßt,

Vorsehen eines Undo-Puffers, der einen Satz von Undo-Aufzeichnungen enthält, wobei der Undo-Puffer Information lediglich für eine unquittierte Transaktion umfaßt und die Undo-Aufzeichnungen in dem Undo- Puffer getrennt von dem Redo-Aufzeichnungen in dem Redo-Puffer angesammelt sind,

Starten einer unquittierten Transaktion,

Aufzeichnen von Redo-Aufzeichnungen entsprechend der unquittierten Transaktion in dem Redo-Puffer, Aufzeichnen von Undo-Aufzeichnungen für die unquittierte Transaktion in dem Undo-Puffer,

Quittieren der Transaktion,

Speichern der Redo-Aufzeichnungen entsprechend der quittierten Transaktion von dem Redo-Puffer zu einem Dauerspeicher und

getrenntes Löschen der Undo-Aufzeichnungen entsprechend der quittierten Transaktion von dem Undo- Puffer, während die Redo-Aufzeichnungen in dem Redo- Puffer zurückgehalten sind.

6. Verfahren nach Anspruch 5, weiterhin umfassend dem Schritt des Vorsehens einer aktiven Transaktionstabelle, die in einem Speicher gespeichert ist, und Eingaben entsprechend Transaktionen enthält, die nicht quittiert wurden.

7. Verfahren nach Anspruch 6, weiterhin mit dem Schritt des Entfernens einer Eingabe entsprechend einer ersten Transaktion aus der aktiven Transaktionstabelle, nachdem die erste Transaktion quittiert ist.