DE69126067T2

DE69126067T2 - Verfahren und Gerät zur Verwaltung von Zustandsidentifizierern zur effizienten Wiederherstellung

Info

Publication number: DE69126067T2
Application number: DE69126067T
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-10-02
Anticipated expiration: 2011-06-12
Also published as: EP0465019A3; EP0465019A2; DE69126067D1; KR940005826B1; US5485608A; EP0465019B1; KR920001374A

Description

I. ALLGEMEINER STAND DER TECHNIK

Die Anmeldung bezieht sich auf das US-Patent 5 524 205, das dem EP-Patent 465 018 entspricht und den Titel "Methods and Apparatus for Optimizing Undo Log Usage" hat, das am 29. Juni 1990 von dem Mitgliedern dieser Anmeldung eingereicht wurde.
Die vorliegende Erfindung bezieht sich allgemein auf das Gebiet einer Wiederherstellung bzw. Erholung (engl. recovery) nach Abstürzen in Systemen mit gemeinsam genutzten Platten und insbesondere auf die Verwendung von Protokollen bei einer derartigen Wiederherstellung.
Alle Computersysteme können Daten verlieren, falls der Computer abstürzt. Einige Systeme wie Datenbanksysteme sind für möglichen Datenverlust wegen einer Systemstörung oder eines Absturzes besonders anfällig, weil diese Systeme große Datenmengen zwischen Platten und einem Prozessorspeicher hin und her übertragen.
Der übliche Grund für Datenverlust ist eine unvollständige Datenübertragung von einem flüchtigen Speichersystem (z.B. einem Prozessorspeicher) zu einem Permanent- bzw. Persistent-Speichersystem (z.B. einer Platte). Oft tritt die unvollständige Übertragung auf, weil eine Transaktion zu der Zeit stattfindet, in der ein Absturz auftritt. Eine Transaktion umfaßt allgemein die Übertragung einer Reihe von Aufzeichnungen (oder Änderungen) zwischen den beiden Speichersystemen.
Ein Konzept, das beim Adressieren eines Datenverlustes und einer Erholung von diesem Verlust wichtig ist, ist die Idee eines "Ausführens bzw. Festschreibens" (engl. committing) einer Transaktion. Eine Transaktion wird "festgeschrieben", wenn es eine gewisse Garantie gibt, daß alle Effekte der Transaktion in dem Persistent-Speicher stabil sind. Falls ein Absturz auftritt, bevor eine Transaktion festschreibt, sind die für eine Wiederherstellung notwendigen Schritte von denjenigen verschieden, die für eine Wiederherstellung notwendig sind, falls ein Absturz auftritt, nachdem eine Transaktion festschreibt. Eine Wiederherstellung ist der Prozeß, bei dem Korrekturen an einer Datenbank vorgenommen werden, die dem kompletten System gestatten, an einem bekannten und gewünschten Punkt wiederanzulaufen.
Der benötigte Wiederherstellungstyp hängt natürlich vom Grund für den Datenverlust ab. Falls ein Computersystem abstürzt, muß die Wiederherstellung die Wiedereinsetzung des Persistent-Speichers, z.B. von Platten, des Computersystems in einen Zustand freigeben, der mit dem durch die letzten festgeschriebenen Transaktionen erzeugten vereinbar ist. Falls der Persistent-Speicher abstürzt (eine Datenträger- bzw. Medienstörung genannt), muß die Wiederherstellung die auf die Platte gespeicherten Daten wieder erzeugen.
Viele Ansätze zum Erholen bzw. Wiederherstellen von Datenbanksystemen beinhalten die Verwendung von Protokollen. Protokolle sind nur Listen zeitlich geordneter Aktionen, die zumindest im Fall von Datenbanksystemen angeben, welche Änderungen an der Datenbank vorgenommen wurden und in welcher Reihenfolge diese Änderungen vorgenommen wurden. Die Protokolle gestatten somit einem Computersystem, die Datenbank in einen bekannten und gewünschten Zustand zu versetzen, der dann genutzt werden kann, um Änderungen zu wiederholen (engl. redo) oder rückgängig zu machen bzw. aufzuheben (engl. undo).
Protokolle sind jedoch in Systemkonfigurationen schwierig zu verwalten, bei denen eine Anzahl Computersysteme, "Knoten" genannt, auf eine Kollektion gemeinsam genutzter Platten zugreift. Dieser Konfigurationstyp wird ein "Cluster" oder ein System mit "gemeinsam genutzten Platten" genannt. Ein System, das alle Knoten in einem solchen System erlaubt, auf alle Daten zuzugreifen, wird ein System mit "gemeinsamer Datenbenutzung" genannt.
Ein System mit gemeinsamer Datenbenutzung führt einen "Datenversand" aus, durch den die Datenblöcke selbst von der Platte zum anfordernden Computer geschickt werden. Im Gegensatz dazu versendet ein Funktions-Versandsystem, das als ein "partitioniertes" System besser bekannt ist, eine Kollektion von Operationen an den als den "Server" bezeichneten Computer für eine Partitionierung der Daten. Der Server führt dann die Operationen aus und versendet die Ergebnisse zurück zum Anforderer.
In partitionierten Systemen, wie in Einzelknoten- oder zentralisierten Systemen, kann jeder Datenteil im lokalen Speicher von höchstens einem Knoten liegen. Ferner erfordern sowohl partitionierte Systeme als auch zentralisierte Systeme nur Aufzeichnungsaktionen auf einem einzigen Protokoll. Ebenso wichtig ist, daß eine Datenwiederherstellung allein auf den Inhalten eines Protokolls basierend fortschreitet.
Verteilte Daten versendende Systeme sind andererseits dezentralisiert, so daß die gleichen Daten in den lokalen Speichern mehrerer Knoten liegen und von diesen Knoten fortgeschrieben werden können. Dies hat Protokollieraktionen mehrerer Knoten für die gleichen Daten zur Folge.
Um das Problem mehrerer Protokolle zu vermeiden, die Aktionen für die gleichen Daten enthalten, kann ein System mit gemeinsamer Datenbenutzung erfordern, daß die Protokollaufzeichnungen für die Daten zu einem einzigen Protokoll zurück versandt werden, das für ein Aufzeichnen einer Wiederherstellungsinformation für die Daten verantwortlich ist. Ein solches "Fern"-Protokollieren erfordert jedoch zusätzliche Systemressourcen, weil zusätzliche, die Protokollaufzeichnungen enthaltende Nachrichten zusätzlich zu den I/O-Schreibdaten für das Protokoll benötigt werden. Ferner kann die mit einem Warten auf eine Bestätigung vom protokollierenden Computer verbundene Verzögerung beträchtlich sein. Dies wird nicht nur die Ansprechzeit erhöhen, es kann die Fähigkeit verringern zu gestatten, daß mehrere Benutzer einen gleichzeitigen Zugriff auf die gleiche Datenbank haben.
Eine andere Alternative besteht darin, die Verwendung eines gemeinsamen Protokolls zu synchronisieren, indem ein Schreiben in dieses Protokoll abwechselt. Dies ist zu aufwendig, weil es zusätzliche Nachrichten für die Koordinierung mit sich bringt.
Es ist wichtig, die Schwierigkeiten anzugehen, weil Systeme mit gemeinsamer Datenbenutzung gegenüber partitionierten Systemen oft vorzuziehen sind. Zum Beispiel sind Systeme mit gemeinsamer Datenbenutzung für Workstations und Anwendungen für technische Entwürfe wichtig, weil Systeme mit gemeinsamer Datenbenutzung gestatten, daß die Workstations für ausgedehnte Zeitspannen Daten speichern, was eine lokale Verarbeitung der Daten mit hoher Leistung gestattet. Außerdem sind Systeme mit gemeinsamer Datenbenutzung ihrer Natur nach störungstolerant und lastausgleichend, weil eine Vielzahl von Knoten auf die Daten gleichzeitig zugreifen kann, einige lokale Daten selbst verwalten und andere Daten mit anderen Host-Computern und Workstations gemeinsam nutzen kann.
IBM Technical Disclosure Bulletin Bd. 26, Nr. 2, "Database integrity at emergency restart in data sharing" beschreibt ein Verfahren für eine Vielzahl von Computern, die eine gemeinsame Datenbank gemeinsam benutzen, unter Verwendung einer Steuerintervall-Fortschreibung-Sequenznummer (CUSN), die in jeder Fortschreibung-Protokollaufzeichnung und in jedem in die Datenbank geschriebenen Block aufgezeichnet ist. Die CUSN wird bei jeder Fortschreibung des Steuerintervalls automatisch um Eins erhöht bzw. inkrementiert und wird bei einem Notfall-Wiederanlauf verwendet, um zu folgern, daß eine Verriegelung durch ein versagendes System gehalten wurde, falls die CUSN auf der Datenbank um 1 geringer als die CUSN auf dem System-Journal ist.
Es ist daher eine Aufgabe dieser Erfindung, ein Verfahren zum Protokollieren in einer Datenversandumgebung zu schaffen, das eine effiziente Wiederherstellung und Protokollverwaltung unterstützt.
Eine weitere Aufgabe dieser Erfindung besteht darin, eine effiziente Wiederherstellung zu liefern, wobei Techniken von Zustandsidentifizierern verwendet werden, welche eine einfache Wiederherstellung nach einem Systemabsturz und auch eine Wiederherstellung nach einer Medienstörung fördern.
Eine weitere Aufgabe dieser Erfindung besteht darin, private Protokolle für jeden Knoten zu liefern, um das Senden von Protokolliernachrichten oder eine Synchronisierung zur Nutzung eines gemeinsamen Protokolls zu vermeiden.

II. ZUSAMMENFASSUNG DER ERFINDUNG

Die vorliegende Erfindung überwindet die Probleme des Standes der Technik und erreicht die oben aufgeführten Ziele durch Verwenden von Zustandsidentifizierern als Vertreter (engl. proxies) für die gesamten Zustände von Abschnitten eines Persistent-Speichers. Der Zustandsidentifizierer nimmt vorzugsweise Werte in einer bekannten Sequenz an; am wichtigsten ist aber, daß der Zustandsidentifizierer für einen Abschnitt eines Persistent-Speichers (z.B. einen Block auf einer Platte) aus einer in einem Protokoll aufgezeichneten Information bestimmt werden kann, welche Information den Zustandsidentifizierer für den Persistent- Speicherabschnitt enthält, bevor er geändert wurde.
Jedes Protokoll kann für eine Wiederherstellung unabhängig von den anderen Protokollen verwendet werden, indem auf jeden der Abschnitte im Speicher nur die Aktionen von demjenigen Protokoll angewandt werden, die den gleichen Zustandsidentifiziererwert haben, wie er in der jüngsten Version dieses Abschnitts gespeichert ist. Verschiedene Protokolle können ferner leicht für eine Medien- Wiederherstellung gemischt werden, indem der Zustandsidentifizierer verwendet wird, um das Protokoll zu finden, das den nächsten Satz Aktionen aufweisen sollte, die für den Abschnitt auf dem Persistent-Speicher verwendet werden.
In einem Datenverarbeitungssystem, das nichtflüchtige Speichermedien enthält, die in mehrere Abschnitte eingeteilt und für zumindest einen ersten Knoten zugänglich sind, und Protokolle enthält mit Information bezüglich der an Abschnitten der Speichermedien vorgenommenen Fortschreibungen, umfaßt ein Verfahren zum Verwalten der Fortschreibungen gemäß dieser Erfindung mehrere Schritte. Sie umfassen: Erhalten bzw. Gewinnen des Besitzes bzw. einer Steuerung eines gewählten Abschnitts; Aussieben bzw. Extrahieren eines Zustandsidentifizierers, der dem gewählten Abschnitt zugeordnet ist; Vornehmen von Fortschreibungen in den gewählten Abschnitt; Aufzeichnen, in einen Teil des dem einen Knoten zugeordneten Protokolls, des extrahierten Zustandsidentifizierers und einer Information über die Fortschreibungen, die in dem gewählten Abschnitt vorgenommen wurden; Zuordnen des fortgeschriebenen gewählten Abschnitts einem neuen Zustandsidentifizierer mit einem Wert, der aus dem Protokollteil bestimmt werden kann; und Freigeben einer Steuerung des gewählten Abschnitts. In einem Datenverarbeitungssystem, das Speichermedien enthält, die in mehrere Abschnitte eingeteilt und mehreren Knoten zugänglich sind, worin jeder der Abschnitte einen Abschnittszustandsidentifizierer enthält, der einen jüngsten Satz in diesem Abschnitt vorgenommener Fortschreibungen eindeutig identifiziert, und worin ein gewählter Knoten einem Protokoll mit Aufzeichnungen zugeordnet ist, wobei jede der Aufzeichnungen eine Information enthält, die einen der Abschnitte identifiziert, einen Satz in dem entsprechenden Abschnitt durch den gewählten Knoten vorgenommener Fortschreibungen beschreibt und einen protokollierten Zustandsidentifizierer aufführt, der den entsprechenden Satz Fortschreibungen identifiziert, umfaßt gemäß einem anderen Aspekt dieser Erfindung ein Verfahren zum Rekonstruieren bzw. Wiederherstellen der Speichermedien in einen gewünschten Zustand mehrere Schritte. Sie umfassen: Wiedergewinnen einer der Aufzeichnungen im Protokoll; Zugreifen auf den einen der Abschnitte, der in der wiedergewonnenen Aufzeichnung identifiziert ist; Finden des Abschnittszustandsidentifizierers im Zugriffsabschnitt; und Verwenden des Satzes Fortschreibungen, die in der wiedergewonnenen Protokollaufzeichnung beschrieben sind, falls der gefundene Zustandsidentifizierer des Abschnitts der gleiche wie der protokollierte Zustandsidentifizierer für die wiedergewonnene Protokollaufzeichnung ist.
Die beiliegenden Zeichnungen, die hierin enthalten sind und einen Teil dieser Beschreibung bilden, veranschaulichen bevorzugte Implementierungen dieser Erfindung und erläutern zusammen mit der beiliegenden Textbeschreibung die Grundlagen der Erfindung.

III. KURZE BESCHREIBUNG DER ZEICHNUNGEN

Figur 1 ist ein Diagramm eines Computersystems zum Implementieren dieser Erfindung;
Figur 2 ist ein Diagramm eines Teils einer Platte, das Blöcke und Seiten zeigt;
Figur 3 ist ein Diagramm eines Redo- bzw. Wiederhol- Protokolls;
Figur 4 ist ein Diagramm eines Aufhebung-Protokolls;
Figur 5 ist ein Diagramm eines Archiv-Protokolls;
Figur 6 ist ein Flußdiagramm zum Ausführen einer Wiederhol-Operation;
Figur 7 ist ein Flußdiagramm zum Durchführen einer Wiederherstellung nach einem Absturz;
Figur 8 ist ein Flußdiagramm zum Mischen von Archiv- Protokollen;
Figur 9 ist ein Diagramm einer Tabelle Unsaubere Blökke;
Figur 10 ist ein Flußdiagramm zum Implementieren eines Vorausschreib-Protokolls, um eine Verwendung des Aufhebung- Protokolls zu optimieren;
Figur 11 ist ein Diagramm einer Kompensation- Protokollaufzeichnung;
Figur 12 ist ein Diagramm einer Tabelle Aktive Transaktionen;
Figur 13 ist ein Flußdiagramm für eine Transaktion- Start-Operation;
Figur 14 ist ein Flußdiagramm für eine Block-Fortschreibung-Operation;
Figur 15 ist ein Flußdiagramm für eine Block-Schreib- Operation;
Figur 16 ist ein Flußdiagramm für eine Transaktion- Abbruch-Operation;
Figur 17 ist ein Flußdiagramm für eine Transaktion-Vorbereitung-Operation; und
Figur 18 ist ein Flußdiagramm für eine Transaktion- Festschreibung-Operation.

IV. BESCHREIBUNG DER BEVORZUGTEN IMPLEMENTIERUNGEN

Nun wird ausführlich auf bevorzugte Implementierungen dieser Erfindung Bezug genommen, von denen Beispiele in den beiliegenden Zeichnungen veranschaulicht sind.

A. Systemkomponenten

System 100 ist ein Beispiel eines Speichersystems, das verwendet werden kann, um die vorliegende Erfindung zu implementieren. Das System 100 umfaßt mehrere Knoten 110, 120 und 130, die alle auf ein System 140 mit gemeinsam genutzten Platten zugreifen. Jeder der Knoten 110, 120 und 130 enthält einen Prozessor 113, 123 bzw. 133, um die unten beschriebenen Speicher- und Fehlerbehebungs- bzw. Wiederherstellungsroutinen auszuführen. Die Knoten 110, 120 und 130 enthalten auch jeweils einen Speicher 118, 128 bzw. 138, um zumindest zwei Funktionen bereitzustellen. Eine der Funktionen besteht darin, als lokaler Speicher für den entsprechenden Prozessor zu wirken, und die andere Funktion besteht darin, die Daten zu halten, die mit dem Plattensystem 140 ausgetauscht werden. Die Teile des Speichers, die für einen Datenaustausch verwendet werden, werden Cache-Speicher bzw. Caches genannt. Caches sind im allgemeinen flüchtige Systemspeicher.
Das System 140 mit gemeinsam genutzten Platten wird auch "Persistent-Speicher" genannt. Permanent- bzw. Persistent-Speicher bezieht sich auf einen nichtflüchtigen Systemspeicher, von dem man annimmt, daß dessen Inhalte weiterbestehen, wenn ein Teil des Systems oder das ganze System abstürzt. Dieser Speicher umfaßt traditionell Magnetplattensysteme, aber Persistent-Speicher könnten auch ebenso gut optische Plattensysteme oder Magnetbandsysteme enthalten.
Außerdem ist der Persistent-Speicher, der verwendet wird, um diese Erfindung zu implementieren, nicht auf die in Figur 1 dargestellte Architektur begrenzt. Zum Beispiel könnte der Persistent-Speicher mehrere Platten enthalten, die jeweils mit einem verschiedenen Knoten gekoppelt sind, wobei die Knoten in einer gewissen Netzwerkart verbunden sind.
Ein anderer Teil des Persistent-Speichers ist ein Sicherungsband-System 150, auf das als "Archivspeicher" verwiesen wird. Archivspeicher ist ein Ausdruck, der im allgemeinen verwendet wird, um auf den Systemspeicher zu verweisen, der für Information genutzt wird, die eine Rekonstruktion der Inhalte des Persistent-Speichers gestattet, sollten die Daten im Persistent-Speicher unlesbar werden. Sollte beispielsweise das System 140 mit gemeinsam genutzten Platten eine Medienstörung aufweisen, könnte das Bandsystem 150 verwendet werden, um das Plattensystem 140 wiederherzustellen bzw. zu rekonstruieren. Der Archivspeicher umfaßt häufig ein Magnetbandsystem; er könnte aber auch genauso gut magnetische oder optische Plattensysteme enthalten.
Daten im System 100 werden gewöhnlich in Blöcken gespeichert, die die wiedererlangbaren Objekte des Systems sind. Im allgemeinen kann mit Blöcken nur gearbeitet werden, wenn sie im Cache irgendeines Knotens sind.
Figur 2 zeigt ein Beispiel mehrerer Blöcke 210, 220 und 230 auf einem Teil einer Platte 200. Im allgemeinen enthält ein Block eine ganze Zahl von Seiten des Persistent-Speichers. Der Block 210 in Figur 2 enthält beispielsweise Seiten 212, 214, 216 und 218.

B. Protokolle

Wie oben erläutert wurde, verwenden die meisten Datenbanksysteme zu Wiederherstellungszwecken Protokolle. Die Protokolle sind im allgemeinen im Persistent-Speicher gespeichert. Wenn ein Knoten den Persistent-Speicher fortschreibt, speichert der Knoten die die Fortschreibungen beschreibenden Protokollaufzeichnungen in einen Puffer im Cache des Knotens.
Die bevorzugte Implementierung der vorliegenden Erfindung sieht drei Typen von Protokollen im Persistent-Speicher vor, aber nur zwei Typen Puffer in jedem Cache des Knotens. Die Protokolle sind Wiederhol-Protokolle oder RLOGs, Aufhebung-Protokolle oder ULOGs und Archiv-Protokolle oder ALOGs. Die Puffer sind die Wiederhol-Puffer und die Aufhebungspuffer.
Ein Beispiel eines RLOG ist in Figur 3 dargestellt, ein Beispiel eines ULOG ist in Figur 4 dargestellt, und ein Beispiel eines ALOG ist in Figur 5 dargestellt. Die Organisation eines Wiederhol-Puffers ist dem RLOG ähnlich, und die Organisation eines Aufhebungspuffers ist dem ULOG ähnlich.
Eine Protokoll-Sequenznummer LSN ist die Adresse oder relative Position einer Aufzeichnung in einem Protokoll. Jedes Protokoll bildet LSNs auf die Aufzeichnungen in diesem Protokoll ab.

1. RLOG

Wie in Figur 3 dargestellt ist, ist RLOG 300 eine bevorzugte Implementierung einer sequentiellen Datei, die verwendet wird, um Information über Änderungen aufzuzeichnen, die die speziellen Operationen zulassen werden, welche während der zu wiederholenden Änderungen stattfinden. Im allgemeinen werden diese Operationen während eines Wiederherstellungsschemas wiederholt werden müssen, wenn ein Block einmal in den Zustand rekonstruiert worden ist, in dem protokollierte Aktionen durchgeführt wurden.
Wie Figur 3 zeigt, enthält RLOG 300 mehrere Aufzeichnungen 301, 302 und 310, die jeweils mehrere Attribute enthalten. Ein TYPE-Attribut 320 identifiziert den Typ der entsprechenden RLOG-Aufzeichnung. Beispiele der verschiedenen Typen von RLOG-Aufzeichnungen sind Wiederhol-Aufzeichnungen, Kompensation-Protokollaufzeichnungen und auf Festschreibungen bezogene Aufzeichnungen. Diese Aufzeichnungen sind unten beschrieben.
Ein TID-Attribut 325 ist ein eindeutiger Identifizierer für die der aktuellen Aufzeichnung zugeordnete Transaktion. Dieses Attribut wird verwendet, um dabei zu helfen, die Aufzeichnung im der vorliegenden RLOG-Aufzeichnung entsprechenden ULOG zu finden.
Ein BSI-Attribut 330 ist ein "Vor-Zustand-Identifizierer" (engl. before state identifier). Dieser Identifizierer ist unten ausführlicher beschrieben. Kurz gesagt gibt der BSI den Wert eines Zustandsidentifizierers für die Version des Blocks vor dessen Modifikation durch die entsprechende Transaktion an.
Ein BID-Attribut 335 identifiziert den Block, der durch die der RLOG-Aufzeichnung entsprechenden Fortschreibung modifiziert wurde.
Ein REDO_DATA-Attribut 340 beschreibt die Natur der entsprechenden Aktion und liefert genug Information für die zu wiederholende Aktion. Der Ausdruck "Fortschreibung" wird in dieser Beschreibung allgemein und austauschbar mit dem Ausdruck "Aktion" verwendet. Aktionen im strengen Sinne schließen nicht nur Aufzeichnungsfortschreibungen, sondern Aufzeichnungseinfügungen und -löschungen ebenso wie Blockzuweisungen und -freigaben ein.
Ein LSN-Attribut 345 identifiziert eindeutig die aktuelle Aufzeichnung auf dem RLOG 300. Wie unten ausführlich erläutert wird, wird das LSN-Attribut 345 in der bevorzugten Implementierung verwendet, um das Wiederhol-Scannen und das Aufzeichnen von Prüfpunktdaten des RLOG zu steuern. LSN 345 wird in weder RLOG-Aufzeichnungen noch in Blöcken in der bevorzugten Implementierung gespeichert. Statt dessen ergibt sie sich inhärent aus der Position der Aufzeichnung im RLOG.
Ein Ziel dieser Erfindung besteht darin, jedem Knoten zu erlauben, seine Wiederherstellung so unabhängig wie möglich von den anderen Knoten zu verwalten. Dazu ist jedem Knoten ein separates RLOG zugeordnet. Die Zuordnung eines RLOG zu einem Knoten in der bevorzugten Implementierung bringt die Verwendung eines verschiedenen RLOG für jeden Knoten mit sich. Alternativ dazu können die Knoten RLOGs gemeinsam nutzen, oder jeder Knoten kann mehrere RLOGs aufweisen. Falls für einen Knoten ein RLOG privat ist, wird jedoch keine Synchronisierung bezüglich Nachrichten benötigt, um die Nutzung des RLOG mit anderen RLOGs und Knoten zu koordinieren.

2. ULOG

In Figur 4 ist ULOG 400 eine bevorzugte Implementierung einer sequentiellen Datei, die verwendet wird, um eine Information aufzuzeichnen, die gestattet, daß Operationen an Blöcken korrekt rückgängig gemacht bzw. aufgehoben werden. ULOG 400 wird verwendet, um Blöcke in Zuständen zu rekonstruieren, die existierten, als eine Transaktion begann.
Im Gegensatz zu RLOGs ist jedes ULOG und jeder Aufhebungspuffer einer verschiedenen Transaktion zugeordnet. Somit verschwinden ULOGs und ihre entsprechenden Puffer, während Transaktionen festschreiben, und neue ULOGs erscheinen, während neue Transaktionen beginnen. Es gibt andere Möglichkeiten.
ULOG 400 enthält mehrere Aufzeichnungen 401, 402 und 410, die jeweils zwei Felder enthalten. Ein BID-Feld 420 identifiziert den Block, der durch die mit dieser Aufzeichnung protokollierten Transaktion modifiziert wird. Ein UNDO_DATA-Feld 430 beschreibt die Natur der Fortschreibung und liefert genug Information für die aufzuhebende Fortschreibung.
RLSN 440 ist die LSN auf dem RLOG der Wiederhol-Aufzeichnung, welche diese Protokollaufzeichnung aufhebt. Das RLSN-Feld 440 identifiziert somit die RLOG-Aufzeichnung, die die gleiche Aktion beschreibt, für die diese ULOG- Aufzeichnung eine Aufhebung vornehmen kann. Dieses Attribut läßt die Fähigkeit zu, jedes Aufhebung-Protokoll eindeutig zu identifizieren.

3. ALOG

In Figur 5 ist ALOG 500 eine bevorzugte Implementierung einer sequentiellen Datei, die verwendet wird, um Wiederhol-Protokollaufzeichnungen für eine ausreichende Dauer zu speichern, um eine Medien-Wiederherstellung zu liefern, wie z.B. wenn das System 140 mit gemeinsam genutzten Platten in Figur 1 versagt. Die RLOG-Puffer sind die Quelle einer Information, woraus ALOG 500 erzeugt wird, und somit hat ALOG 500 die gleichen Attribute wie RLOG 300.
ALOGs werden vorzugsweise aus den abgeschnittenen Teilen entsprechender RLOGs gebildet. Die abgeschnittenen Teile sind Teile, die nicht länger benötigt werden, um die Versionen des Persistent-Speichers von Blöcken bis zu aktuellen Versionen zu bringen. Die Aufzeichnungen in den abgeschnittenen Teilen der RLOGs werden jedoch noch benötigt, sollte die Persistent-Speicherversion eines Blocks nicht verfügbar werden und aus der Version des Blocks auf dem Archivspeicher wiederhergestellt werden müssen.
Ähnlich RLOG 300 enthält ALOG 500 mehrere Aufzeichnungen 501, 502 und 510. Die Attribute TYPE 520, TID 525, BSI 530, BID 535 und REDO-DATA 540 haben die gleichen Funktionen wie die gleichnamigen Attribute im RLOG 300. LSN 545 identifiziert wie LSN 345 für RLOG 300 die ALOG-Aufzeichnung.

C. Zustandsidentifizierer (und Vorausschreib-Log-Protokoll)

In protokollbasierten Systemen wird eine Protokollaufzeichnung für einen Block nur verwendet, wenn der aufgezeichnete Zustand des Blocks für die durch die Protokollaufzeichnung bezeichnete Fortschreibung geeignet ist. Somit ist eine ausreichende Bedingung für eine korrekte Wiederholung, eine protokollierte Transaktion auf einen Block anzuwenden, wenn der Block im gleichen Zustand ist, wie er war, als die ursprüngliche Aktion durchgeführt wurde. Falls die ursprüngliche Aktion korrekt war, wird die Wiederhol-Aktion ebenfalls korrekt sein.
Es ist kompliziert und unpraktisch, die ganzen Inhalte eines Blockzustands auf einem Protokoll zu speichern. Daher wird ein Vertreter-Wert oder Identifizierer für den Blockzustand erzeugt. Der Identifizierer, der in der bevorzugten Implementierung verwendet wird, ist ein Zustandsidentifizierer oder SI. Der SI hat für jeden Block einen eindeutigen Wert. Dieser Wert identifiziert den Zustand des Blocks zu einer bestimmten Zeit, wie z.B. entweder vor oder nach der Durchführung einer Operation auf dem Block.
Der SI ist viel kleiner als der komplette Zustand und kann anstelle des kompletten Zustands ohne besonderen Aufwand bzw. billig gespeichert werden, solange der komplette Zustand, wenn nötig, wieder erzeugt bzw. wiederhergestellt werden kann. Ein SI wird "definiert", indem ein bestimmter Wert, genannt der "definierende Zustandsidentifizierer" oder DSI, im Block gespeichert wird. Der DSI bezeichnet den Zustand des Blocks, in dem er enthalten ist.
Eine Neuerzeugung bzw. Wiederherstellung des Zustands kann durch Zugreifen auf den ganzen, im Persistent-Speicher gespeicherten Block während einer Wiederherstellung und Notieren bzw. Bezeichnen des DSI dieses Blocks erreicht werden. Dieser Blockzustand wird dann, wie unten ausführlich erklärt wird, auf den neuesten Stand gebracht, indem protokollierte Aktionen wie geeignet verwendet werden.
Ein ähnliches Verfahren ist unten für eine Medien- Wiederherstellung unter Verwendung des ALOG beschrieben. Eine Kenntnis darüber, ob eine Protokollaufzeichnung auf einen Block Anwendung findet, schließt die Fähigkeit ein, aus der Protokollaufzeichnung zu bestimmen, auf welchen Zustand die protokollierte Aktion Anwendung findet. Gemäß der vorliegenden Erfindung wird ein DSI eines Blocks verwendet, um zu bestimmen, wann eine Anwendung von Protokollaufzeichnungen auf diesen Block beginnen soll.
In einem zentralisierten oder partitionierten System wird das physikalische nacheinander Anordnen bzw. Sequenzbilden von Aufzeichnungen auf einem einzigen Protokoll genutzt, um die zu wiederholenden Aktionen zu ordnen. Das heißt, falls eine Aktion B auf einem Block einer Aktion A auf dem Block unmittelbar folgt, findet dann die Aktion B auf den durch die Aktion A erzeugten Blockzustand Anwendung. Falls somit die Aktion A wiederholt worden ist, wird die nächste auf den Block anzuwendende Protokollaufzeichnung die Aktion B sein.
Einzelne Protokollsysteme, wie z.B. zentralisierte oder partitionierte Systeme, verwenden häufig LSNs als SIs, um Blockzustände zu identifizieren. Die LSN, die als der DSI für einen Block dient, identifiziert die letzte Aufzeichnung in einer Protokollsequenz, um ihre Wirkung im Block widerspiegeln zu lassen. In solchen Systemen kann die LSN einer Protokollaufzeichnung die Rolle eines "Nach-Zustand- Identifizierers" oder ASI (engl. after state identifier) spielen, der den Zustand des Blocks nach der protokollierten Aktion identifiziert. Dies steht im Gegensatz zu einem BSI (Vor-Zustand-Identifizierer), der in der vorliegenden Erfindung in einer Protokollaufzeichnung wie unten beschrieben verwendet wird.
Um den DSI zu aktualisieren bzw. fortzuschreiben und für die nächste Operation vorzubereiten, ist es auch notwendig, den ASI für einen Block nach Verwendung der Protokollaufzeichnung bestimmen zu können. Es ist nützlich, in der Lage zu sein, den ASI aus der Protokollaufzeichnung abzuleiten, wie z.B. aus dem BSI, so daß der ASI nicht in Protokollaufzeichnungen gespeichert sein muß, obwohl der ASI tatsächlich gespeichert sein kann. Die Ableitung muß jedoch eine sein, die während einer Wiederherstellung und auch während einer normalen Operation verwendet werden kann. Die SIs liegen vorzugsweise in einer bekannten Sequenz vor, wie z.B. dem monoton zunehmenden, mit Null beginnenden Satz ganzer Zahlen. In diesem Verfahren ist der ASI immer größer als der BSI.
Wenn man den fortgeschriebenen Block in den Persistent- Speicher zurückspeichert, wie z.B. das System 140 mit gemeinsam genutzten Platten, wird ein Vorausschreib-Log(WAL)- Protokoll verwendet. Das WAL-Protokoll verlangt, daß die Wiederhol- und Aufhebungspuffer in die Protokolle im System 140 mit gemeinsam genutzten Platten vor den Blöcken geschrieben werden. Dies stellt sicher, daß die Information, die notwendig ist, um die Aktion zu wiederholen oder aufzuheben, stabil gespeichert ist, bevor die Persistentkopie der Daten geändert wird.
Falls man dem WAL-Protokoll nicht folgt und ein Block vor der Protokollaufzeichnung für die letzte Fortschreibung für den Block in den Persistent-Speicher geschrieben werden sollte, könnte die Wiederherstellung unter bestimmten Bedingungen nicht stattfinden. Zum Beispiel kann eine Fortschreibung bei einem Knoten bewirken, daß ein nicht festgeschriebene Fortschreibungen enthaltender Block in den Persistent-Speicher geschrieben wird. Falls die letzte Fortschreibung in diesen Block nicht in das RLOG des Knotens gespeichert worden ist und eine andere Transaktion auf einem zweiten Knoten den Block weiter fortschreibt und festschreibt, wird der DSI für den Block inkrementiert. In dem Moment einer Festschreibung für diese zweite Transaktion werden die protokollierten Aktionen für diese anderen Transaktionen in das RLOG für den zweiten Knoten gezwungen. Weil die zweite Fortschreibung durch einen verschiedenen Knoten erzeugt wurde, stellt jedoch das Schreiben der Protokollaufzeichnungen für die zweite Transaktion nicht sicher, daß die Protokollaufzeichnung für die nicht festgeschriebene Transaktion auf dem ursprünglichen Knoten geschrieben wird.
Falls der ursprüngliche Knoten abstürzt und die Protokollaufzeichnung für die nicht festgeschriebene Transaktion nie in das RLOG geschrieben wird, wird in der ASI-BSI-Folge für den Block eine Lücke erzeugt. Sollte der Block im Persistent-Speicher jemals nicht verfügbar werden, z.B. wegen eines Plattenfehlers, würde eine Wiederherstellung scheitern, weil die ALOG-Mischung, wie unten erläutert wird, eine bekannte und lückenlose Folge bzw. Sequenz von SIs verlangt.
Somit ist das WAL-Protokoll eine notwendige Bedingung für eine ununterbrochene Sequenz protokollierter Aktionen. Es ist auch eine hinreichende Bedingung hinsichtlich Blockfortschreibungen. Wenn sich ein Block von einem Cache eines Knotens zu einem anderen verschiebt, zwingt das WAL- Protokoll die RLOG-Aufzeichnungen für alle früheren Fortschreibungen in die Blöcke, die durch die festschreibende Transaktion geändert werden sollen. "Zwingen bzw. Erzwingen" bedeutet, daß sichergestellt wird, daß die Aufzeichnungen in einem Cache oder Puffer eines Knotens im Persistent-Speicher stabil gespeichert werden.
Durch Schreiben in den Persistent-Speicher erzwingt das WAL-Protokoll das Schreiben aller Aufzeichnungen in das RLOG des ursprünglichen Knotens bis zur Protokollaufzeichnung für die letzte Fortschreibung in den aktuellen Block.

D. Neue Blockzuordnung

Wenn ein Block freigegeben worden ist, wie z.B. während Routinen für eine normale Plattenspeicherverwaltung, und später für eine weitere Verwendung erneut zugeordnet wird, sollte dessen DSI nicht auf Null gesetzt sein, weil diese Tätigkeit nicht-eindeutige Zustandsidentifizierer zur Folge hat. Falls der DSI auf Null gesetzt wäre, könnte es den Anschein haben, daß mehrere Protokollaufzeichnungen auf einen Block Anwendung finden, weil sie den gleichen SI hätten. Eine zusätzliche Information wäre notwendig, um die korrekte Protokollaufzeichnung zu bestimmen. Somit muß die in der vorherigen Zuordnung verwendete DSI-Numerierung ununterbrochen in der neuen Zuordnung bewahrt bzw. gesichert werden. Der BSI für einen neu zugeordneten Block ist vorzugsweise der ASI des Blocks, als er freigegeben wurde.
Ein einfacher Weg, eine ununterbrochene SI-Numerierung zu erreichen, besteht darin, einen DSI in dem Block als Ergebnis einer Freigabeoperation zu speichern. Wenn der Block erneut zugeordnet wird, wird er gelesen, vielleicht vom Persistent-Speicher, und die normale DSI-Inkrementierung wird fortgeführt. Dies behandelt eine Zuordnung und Freigabe genau wie Fortschreibungsoperationen. Ein Problem mit dieser Lösung ist die Notwendigkeit, neu zugeordnete Blöcke zu lesen, bevor sie verwendet werden. Um eine Platzverwaltung mit einem Minimum an I/O-Tätigkeit effizient zu machen, wäre es jedoch wünschenswert, den "Nachteil eines Lesens vor einer Zuordnung" zu vermeiden.
Die vorliegende Erfindung gewinnt Effizienz, indem der DSI nicht für alle nicht zugeordneten Blöcke geschrieben wird. Für nicht vorher zugeordnete Blöcke ist der anfängliche DSI immer auf Null gesetzt. Nur der DSI für Blöcke, die freigegeben worden sind, wird gespeichert. Diese DSIs werden unter Verwendung der Aufzeichnungen gespeichert, die schon durch das System zur Buchhaltung des freien Raums im Persistent-Speicher gehalten werden. Gewöhnlich wird eine solche Buchhaltungsinformation in einer Kollektion von Platzverwaltungsblöcken aufgezeichnet.
Durch Speichern des anfänglichen SI für jeden freigegebenen Block mit dieser Platzverwaltungsinformation müssen die anfänglichen SIs nicht in den Blöcken gespeichert werden, wobei somit der Nachteil eines Lesens vor einer Zuordnung eliminiert ist. Bei einer Neuzuordnung wird der BSI für die "Zuordnungs"-Operation der anfängliche SI dieses früheren "freien" Blocks.
Um diese Prozedur korrekt arbeiten zu lassen, müssen natürlich die eine Platzverwaltungsinformation enthaltenden Blöcke periodisch in den Persistent-Speicher geschrieben werden, und einem Knoten darf nicht erlaubt werden, durch einen anderen Knoten freigegebene Blöcke neu zuzuordnen, bis ihm über diese Buchhaltung die Existenz freigegebener Blöcke bekanntgegeben ist. Somit verursacht ein Beibehalten anfänglicher SIs für freigegebene Blöcke kein zusätzliches Lesen oder Schreiben der Buchhaltungsinformation für freien Platz.
Obwohl eine Hinzufügung einer SI-Information für freie Blöcke den Umfang an Platzverwaltungsinformation erhöht, die in diesem System benötigt wird, gibt es zwei Gründe, warum die Systemeffizienz darunter nicht zu sehr leiden sollte. Erstens ist der meiste freie Platz als "nie zuvor zugeordnet" gekennzeichnet und hat somit schon einen anfänglichen SI von Null. Zweitens ist der vorher verwendete freie Platz in den meisten Datenbanken gering, weil Datenbanken gewöhnlich wachsen. Weil die anfänglichen SIs einzeln nur für die neu zugeordneten Blöcke gespeichert werden, sollte der vergrößerte Speicher für SIs klein sein.
Alternativ dazu könnten die nie zuvor zugeordneten Blöcke von neu zugeordneten unterschieden werden. Der SI für die neu zugeordneten Blöcke könnte dann vom Persistent- Speicher gelesen werden, wenn diese Blöcke zugeordnet werden. Dies würde den Nachteil eines Lesens vor einer Zuordnung herbeiführen, obgleich jedoch der Nachteil aus den oben diskutierten Gründen gering wäre.

E. Wiederherstellung

1. Blockversionen

Um zu verstehen, wie die Protokolle bei einer Wiederherstellung verwendet werden können, ist es notwendig, die verschiedenen Versionen von Blöcken zu verstehen, die nach einem Absturz verfügbar sein können. Diese Versionen können unter dem Aspekt gekennzeichnet sein, wie viele der protokollierten Fortschreibungen auf wie vielen Protokollen benötigt werden, um die verfügbare Version aktuell zu machen. Dies hat einen offensichtlichen Einfluß hinsichtlich der Frage, wie ausgedehnt oder lokalisiert eine Wiederherstellungstätigkeit sein wird.
Zu Wiederherstellungszwecken gibt es drei Arten von Blöcken. Eine Version eines Blocks ist "aktuell", falls alle Fortschreibungen, die auf dem Block durchgeführt worden sind, in der Version widergespiegelt werden. Ein Block mit einer aktuellen Version nach einer Störung benötigt keine Wiederhol-Wiederherstellung. Wenn man mit nicht vorhersagbaren Systemstörungen zu tun hat, kann man jedoch nicht sicherstellen, daß alle Blöcke aktuell sind, ohne immer den Cache in den Persistent-Speicher "durchzuschreiben", wann immer ein Fortschreiben stattfindet. Dies ist aufwendig und wird selten gemacht.
Eine Version eines Blocks ist "1-Protokoll-artig" (engl. one-log), falls nur ein Protokoll eines Knotens Fortschreibungen aufweist, die noch nicht für den Block verwendet worden sind. Wenn eine Störung auftritt, muß höchstens ein Knoten an der Wiederherstellung beteiligt sein. Dies ist wünschenswert, weil es eine möglicherweise aufwendige Koordinierung während der Wiederherstellung und auch zusätzliche Implementierungskosten vermeidet.
Eine Version eines Blocks ist "N-Protokoll-artig", falls mehr als ein Protokoll eines Knotens Fortschreibungen aufweisen kann, die darauf noch nicht angewendet worden sind. Eine Wiederherstellung ist im allgemeinen für N- Protokoll-Blöcke schwieriger als für 1-Protokoll-Blöcke, ist aber unpraktisch, wenn eine Medien-Wiederherstellung vorgesehen ist, um sicherzustellen, daß Blöcke immer 1- Protokoll-artig sind, weil dies das Schreiben eines Blocks mit sich bringen würde, um einen Speicher jedesmal zu erreichen, wenn der Block Knoten ändert.

2. Wiederhol-Wiederherstellung

Ohne Pflege werden einige Blöcke zum Zeitpunkt eines Systemabsturzes (im Gegensatz zu einer Medienstörung) N- Protokoll-artig sein. Die bevorzugte Implementierung dieser Erfindung garantiert jedoch, daß alle Blöcke 1-Protokoll- Blöcke für eine Wiederherstellung nach einem Systemabsturz sein werden. Dies ist vorteilhaft, weil N-Protokoll-Blöcke eine komplexe Koordinierung zwischen Knoten für deren Wiederherstellung erfordern können. Obwohl eine solche Koordinierung möglich ist, weil die Fortschreibungen während eines normalen Systembetriebs unter Verwendung einer verteilten Parallelbetriebsteuerung ursprünglich nacheinander eingeordnet wurden, verlangt eine solche Parallelbetriebsteuerung einen Aufwand, der während einer Wiederherstellung vermieden werden sollte.
Es kann garantiert werden, daß alle Blöcke bezüglich einer Wiederhol-Wiederherstellung 1-Protokoll-artig sind, indem man fordert, daß "unsaubere" Blöcke (engl. dirty blocks) in den Persistent-Speicher geschrieben werden, bevor sie von einem Cache zu einem anderen verschoben werden. Ein unsauberer Block ist einer, dessen Version im Cache fortgeschrieben worden ist, seit der Block vom Persistent- Speicher gelesen wurde.
Falls diese Regel befolgt wird, erhält ein anfordernder Knoten immer einen sauberen Block, wenn der Block in den Cache eines neuen Knotens gelangt. Während einer Wiederherstellung müssen außerdem nur die Aufzeichnungen auf dem Protokoll des letzten Knotens, um den Block zu ändern, auf den Block angewandt werden. Alle anderen Aktionen anderer Knoten sind im Zustand des Blocks im Persistent-Speicher schon erfaßt worden. Somit werden alle Blöcke für eine Redo- bzw. Wiederhol-Wiederherstellung 1-Protokoll-artig sein, so daß eine Wiederhol-Wiederherstellung keine verteilte Parallelbetriebsteuerung erfordern wird.
Ein Befolgen dieses Verfahrens bedeutet nicht, daß nie mehrere Protokolle Aufzeichnungen für einen Block enthalten werden. Dieses Verfahren stellt nur sicher, daß allein Aufzeichnungen eines Knotens für die Version des Blocks im Persistent-Speicher verwendbar sind.
Obwohl eine 1-Protokoll-Wiederhol-Wiederherstellung für Systemabstürze angenommen wird, kann es außerdem notwendig sein, um eine Datenträger- bzw. Medien-Wiederherstellung durchzuführen, Wiederhol-Aktionen auf mehreren Protokollen zu verwenden, um ein Schreiben jedes Blocks in einen Archivspeicher jedesmal, wenn sich der Block zwischen Caches verschiebt, zu vermeiden. Daher ist es unter bestimmten Umständen noch notwendig, die protokollierten Aktionen über alle Protokolle zu ordnen, um eine Wiederherstellung für N- Protokoll-Blöcke zu liefern. Dies kann jedoch aufgrund der sequentiellen SIs erreicht werden.
Figur 6 zeigt ein Flußdiagramm 600 der Grundschritte für eine Wiederhol-Operation unter Verwendung des RLOG und der SIs, die oben beschrieben wurden. Die durch das Flußdiagramm 600 repräsentierte Wiederhol-Operation würde von einem einzigen Knoten unter Verwendung einer einzigen RLOG- Aufzeichnung ausgeführt werden, die auf einen einzigen Block angewandt wird.
Zuerst würde man die jüngste Version des durch die Protokollaufzeichnung identifizierten Blocks vom Persistent- Speicher wiedergewinnen (Schritt 610). Falls der in diesem wiedergewonnenen Block gespeicherte DSI gleich dem in der Protokollaufzeichnung gespeicherten BSI ist (Schritt 620), wird dann die in der Protokollaufzeichnung angegebene Aktion auf den Block angewandt, und der DSI wird inkrementiert, um den neuen Zustand des Blocks widerzuspiegeln (Schritt 630). Andernfalls wird diese Fortschreibung nicht auf den Block angewandt.
Die bezüglich Figur 6 beschriebene Wiederhol-Operation ist möglich, weil die BSIs und ASIs zur Zeit einer Wiederherstellung bestimmt werden können. Folglich kann man für jedes Protokoll bestimmen, welche Protokollaufzeichnungen wiederholt werden müssen, und diese Bestimmung kann von den Inhalten anderer Protokolle unabhängig sein. Der einzige Vergleich, der zwischen Block-DSIs und Protokollaufzeichnung-BSIs vorgenommen werden muß, ist der einer Gleichheit.
Die bezüglich Figur 6 beschriebene Wiederhol-Operation kann beim Wiederherstellen nach Systemabstürzen verwendet werden. Ein Beispiel einer Prozedur einer Wiederherstellung nach einem Absturz ist durch das Flußdiagramm 700 in Figur 7 dargestellt. Diese Prozedur für eine Wiederherstellung nach einem Absturz kann ein einziger Knoten unabhängig von anderen Knoten ausführen.
Der erste Schritt bestünde für den Knoten darin, die durch den jüngsten Prüfpunkt angegebene erste RLOG-Aufzeichnung zu lesen (Schritt 710). Der Prüfpunkt gibt, wie unten beschrieben ist, den Punkt bzw. die Stelle im RLOG an, die die Aufzeichnung enthält, die der ältesten Fortschreibung entspricht, die angewandt werden muß.
Die in Figur 6 dargestellte Wiederhol-Operation wird dann ausgeführt, um zu sehen, ob die in dieser Protokollaufzeichnung festgelegte Aktion auf den in dieser Protokollaufzeichnung identifizierten Block anzuwenden ist (Schritt 720).
Falls nach Ausführen der Wiederhol-Operation keine weiteren Aufzeichnungen vorliegen (Schritt 730), ist die Wiederherstellung nach einem Absturz komplett. Andernfalls wird die nächste Aufzeichnung vom RLOG wiedergewonnen (Schritt 740), und die in Figur 6 gezeigte Wiederhol- Operation (Schritt 720) wird wiederholt.
Falls der einer Protokollaufzeichnung zugeordnete SI ein monoton zunehmender ASI ist, besteht der Test, ob eine Protokollaufzeichnung auf einen Block in einem gewissen Zustand Anwendung findet, darin, ob dieser ASI der erste ist, der größer als der DSI des Blocks ist. Dies ist jedoch nur für eine 1-Protokoll-Wiederherstellung ausreichend, weil in diesem Fall nur ein Protokoll Aufzeichnungen mit ASIs aufweisen wird, die größer als der DSI im Block sind.
In der bevorzugten Implementierung dieser Erfindung enthält jedoch jede Protokollaufzeichnung die genaue Identität des Protokollzustands, bevor eine protokollierte Aktion durchgeführt wird. Wie oben erklärt wurde, ist dies der "Vor-Zustand-Identifizierer" oder BSI.

3. Mehrfach-Protokoll-Wiederausführung zur Medien-Wiederherstellung

Eine Datenträger- bzw. Medien-Wiederherstellung weist viele gleiche Charakteristiken wie eine Wiederherstellung nach einem Absturz auf. Zum Beispiel wird eine stabil gespeicherte Version benötigt, gegen die die Protokollaufzeichnungen angewandt werden.
Es gibt auch wichtige Unterschiede. Erstens ist die stabile Version des Blocks, gegen die die ALOG-Aufzeichnungen verwendet werden, die Version, die zuletzt in den Archivspeicher eingegeben wurde.
Eine Medien-Wiederherstellung ist N-Protokoll-artig, weil sie ein Rekonstruieren von Blöcken vom Archivspeicher beinhaltet und, wie oben erklärt wurde, Blöcke nicht jedesmal in den Archivspeicher geschrieben werden, wenn sie sich zwischen Caches verschieben. Somit kann das Verfahren zum Schreiben von Blöcken in einen Speicher, um eine N-Protokoll-Wiederherstellung für Systemabstürze zu vermeiden, für eine Medien-Wiederherstellung nicht verwendet werden.
Ohne Mischen der ALOGs ist ein Verwalten einer Medien- Wiederherstellung schwierig. Falls die ALOGs nicht gemischt werden, bringt die Wiederherstellung dann eine ständige Suche nach verwendbaren Protokollaufzeichnungen mit sich. Beim Mischen von ALOGs besteht ein wesentlicher Vorteil in der Verwendung von BSIs.
Figur 8 zeigt eine Prozedur 800 für eine N-Protokoll- Medien-Wiederherstellung, die den Zusammenschluß der vielfachen ALOGs beinhaltet. Das Mischen basiert nicht auf einem Gesamtordnen zwischen allen Protokollaufzeichnungen, sondern auf einem partiellen Ordnen, das sich aus dem Ordnen zwischen Protokollaufzeichnungen für den gleichen Block ergibt. Gelegentlich wird es mehrere ALOGs geben, die Aufzeichnungen aufweisen, deren Aktionen auf ihre jeweiligen Blöcke angewendet werden können. Wie aus der Beschreibung der Prozedur 800 ersichtlich sein wird, ist es unwesentlich, welche dieser Aktionen zuerst während einer Medien- Wiederherstellung verwendet wird.
Es ist schneller und effizienter zu gestatten, daß die vielfachen ALOGs in einem einzigen Durchgang gemischt und auf die Sicherungsdatenbank im Archivspeicher angewendet werden. Dies kann getan werden, falls die SIs richtig geordnet sind. Der Grund dafür ist, wie oben erklärt wurde, daß die SIs in einer bekannten Sequenz geordnet sind und die bevorzugte Implementierung dieser Erfindung SIs verwendet, die monoton zunehmen.
Mit einem beliebigen ALOG beginnend wird auf die erste Protokollaufzeichnung zugegriffen (Schritt 810). Die Block- ID und -BSI werden dann aus dieser Aufzeichnung ausgesiebt bzw. extrahiert (Schritt 820). Als nächstes wird der durch die Block-ID identifizierte Block geholt bzw. abgerufen (Schritt 830).
Ist der identifizierte Block einmal abgerufen, wird dessen DSI gelesen und mit dem BSI der ALOG-Aufzeichnung verglichen (Schritt 840). Falls der BSI des ALOG kleiner als der DSI des Blocks ist, wird die Aufzeichnung ignoriert, weil die protokollierte Aktion schon in den Block eingearbeitet ist und eine Wiederholung nicht benötigt wird.
Falls der BSI der ALOG-Aufzeichnung gleich dem DSI des Blocks ist, wird dann die protokollierte Aktion wiederholt, indem diese Aktion auf den Block angewandt wird (Schritt 850). Dies verhält sich so, weil die Gleichheit der SIs bedeutet, daß die protokollierte Aktion auf die aktuelle Version des Blocks Anwendung findet.
Der DSI des Blocks wird dann hochgezählt bzw. inkrementiert (Schritt 860). Dies spiegelt die Tatsache wider, daß die Anwendung der protokollierten Aktion eine neue (spätere) Version des Blocks erzeugt hat.
Falls der BSI der ALOG-Aufzeichnung größer als der DSI des Blocks ist, ist es dann nicht die geeignete Zeit, die der Protokollaufzeichnung entsprechenden Aktionen anzuwenden, und es ist statt dessen die geeignete Zeit, die auf anderen ALOGs aufgezeichneten Aktionen anzuwenden. Folglich muß das Lesen dieses ALOG warten, und das Lesen eines anderen ALOG wird begonnen (Schritt 870).
Falls vorher das andere ALOG unterbrochen (engl. paused) wurde (Schritt 880), wird dann eine Steuerung auf Schritt 820 übertragen, um die Block-ID und den BSI der Protokollaufzeichnung zu extrahieren, die aktuell war, als dieses Protokoll unterbrochen wurde. Falls das Protokoll vorher nicht unterbrochen wurde, geht dann die Steuerung weiter, als ob dieses das erste ALOG wäre.
Nach all diesen Schritten oder, falls das andere ALOG niemals vorher unterbrochen wurde, wird eine Bestimmung vorgenommen, ob irgendwelche ALOG-Aufzeichnungen zurückbleiben (Schritt 890). Falls dies der Fall ist, wird die nächste Aufzeichnung geholt (Schritt 810). Andernfalls ist die Prozedur 800 beendet.
Wenn ein ALOG unterbrochen wurde, muß es zumindest ein anderes ALOG geben, das Aufzeichnungen für den Block enthält, die dem aktuellen vorausgehen. Ein unterbrochenes ALOG innerhalb einer wartenden Protokollaufzeichnung wird einfach als ein Eingangsstrom betrachtet, dessen erstes Objekt (in einer geordneten Sequenz) später als die Objekte in den anderen Eingangsströmen vergleicht (d.h. den anderen ALOGs). Eine Verarbeitung geht unter Verwendung der anderen ALOGs weiter.
Die aktuelle Aufzeichnung des unterbrochenen ALOG muß zu irgendeinem zukünftigen Zeitpunkt auf den Block angewendet werden können, weil der BSI ohne intervenierende Aktionen anderer ALOGs nicht größer als der DSI des Blocks wäre. Wenn dies geschieht, wird das unterbrochene ALOG nicht unterbrochen sein.
Nicht alle ALOGs werden gleichzeitig unterbrochen, weil die Aktionen ursprünglich in einer Reihenfolge vorgenommen wurden, die mit der SI-Ordnung für die Blöcke übereinstimmt. Somit ist immer eine Mischung der ALOGs möglich.

4. Redo- bzw. Wiederhol-Verwaltung

a. Sicherer-Punkt-Bestimmung

Viele Verfahren zum Aufzeichnen von Prüfpunktdaten (engl. checkpointing methods) können mit der vorliegenden Erfindung verwendet werden, um eine Wiederhol-Wiederherstellung noch effizienter zu machen. Zum Beispiel kann eine Tabelle Unsaubere Blöcke erzeugt werden, um jedem unsauberen Block eine Information über eine Wiederherstellungsverwaltung zuzuordnen. Diese Information liefert zwei wichtige Funktionen beim Verwalten des RLOG und daher des ALOG. Erstens wird die Information für die Wiederherstellungsverwaltung beim Bestimmen eines "sicheren Punktes" verwendet, der ein RLOG-Scannen und -Abschneiden beherrscht. Zweitens kann die Information beim Erzwingen des WAL-Protokolls für das RLOG und auch für mögliche Aufhebung-Protokolle verwendet werden.
Eine Sicherer-Punkt-Bestimmung ist wichtig, um zu bestimmen, wie viel vom RLOG gescannt werden muß, um eine Wiederhol-Wiederherstellung durchzuführen. Der Startpunkt im RLOG für dieses Wiederhol-Scannen wird der "sichere Punkt" genannt. Der sichere Punkt ist in zweierlei Hinsicht "sicher". Erstens kann die Wiederhol-Wiederherstellung sicher Aufzeichnungen ignorieren, die dem sicheren Punkt vorausgehen, weil diese Aufzeichnungen alle schon in den Versionen von Blöcken im Persistent-Speicher enthalten sind. Zweitens können die "ignorierten" Aufzeichnungen vom RLOG abgeschnitten werden, weil sie nicht länger benötigt werden.
Dieses zweite Merkmal ist für kombinierte Aufhebung/Wiederhol-Protokolle nicht wahr. Falls zum Beispiel eine lange Transaktion vorlag, die Aufhebungsaufzeichnungen erzeugte, kann ein Abschneiden vor dem Prüfpunkt nicht möglich sein, weil die Aktionen in den Aufhebungsaufzeichnungen den Aktionen in den Wiederhol-Aufzeichnungen vorausgehen können, die in den Persistent-Speicher geschrieben worden sind. Dies würde ein Abschneiden beeinträchtigen.
Die Tabelle Unsaubere Blöcke 900 ist in Figur 9 dargestellt. Die aktuelle Kopie der Tabelle Unsaubere Blöcke 900 wird vorzugsweise in einem flüchtigen Speicher gehalten und wird in einen Persistent-Speicher im RLOG als Teil des Prüfpunktdaten aufzeichnenden Prozesses periodisch gespeichert. Die Einträge 910, 911 und 912 der Tabelle Unsaubere Blöcke umfassen ein Wiederherstellung-LSN-Feld 920 und ein Block-ID-Feld 930.
Die Werte im Wiederherstellung-LSN-Feld 920 identifizieren die früheste RLOG-Aufzeichnung, deren Aktion in der Version des Blocks im Persistent-Speicher nicht enthalten ist. Somit ist der Wert des LSN-Feldes 920 die erste RLOG- Aufzeichnung, die wiederholt werden müßte.
Der Wert im Block-ID-Feld 930 identifiziert den der Wiederherstellung-LSN entsprechenden Block. Die Tabelle Unsaubere Blöcke 900 ordnet somit jedem unsauberen Block die LSN der RLOG-Aufzeichnung zu, die den Block unsauber machte. Ein anderer Eintrag in die Tabelle Unsaubere Blöcke 900 ist der Letzte-LSN-Eintrag 950. Der Wert für diesen Eintrag sind für jeden Block die LSNs der RLOG- und ULOG-Aufzeichnungen, die das letzte Fortschreiben in den Block beschreiben. LSNs werden eher als DSIs verwendet, weil es notwendig ist, Stellen in Protokollen zu bestimmen.
Die Letzte-LSN 950 enthält eine R-Letzte-LSN 955 (für das RLOG) und eine Liste von U-Letzte-LSNs 958 (eine für jedes der ULOGs), welche jeweils angeben, wie viel von dem RLOG und den ULOGs erzwungen werden muß, wenn der Block in den Persistent-Speicher geschrieben wird, um das WAL- Protokoll zu erzwingen. Erzwingen des WAL-Protokolls bedeutet somit, daß alle in einen Block auf dem Persistent- Speicher eingebauten Aktionen sowohl stabil gespeicherte RLOG- als auch ULOG-Aufzeichnungen aufweisen.
Eine R-Letzte-LSN 955 und eine U-Letzte-LSN 958 sind im (unten beschriebenen) Prüfpunkt nicht enthalten, weil ihre Rolle allein darin besteht, das WAL-Protokoll für das RLOG und ULOG zu erzwingen. In der bevorzugten Implementierung werden daher diese Einträge von der Wiederherstellung-LSN getrennt gehalten, um zu vermeiden, daß sie mit der Prüfpunktinformation gespeichert werden.
Die früheste LSN für alle Blöcke in einem Cache eines Knotens ist der sichere Punkt für das Wiederhol-Scannen im lokalen RLOG. Eine Wiederhol-Wiederherstellung wird durch Lesen des lokalen RLOG von dem sicheren Punkt aus vorwärts und Wiederholen der Aktionen in nachfolgenden Aufzeichnungen begonnen. Alle eine Wiederausführung benötigenden Blökke weisen alle zu wiederholenden Aktionen auf, auf die man während dieses Scannens traf.
Wie oben erläutert wurde, macht es die 1-Protokoll- Annahme möglich, jedes RLOG isoliert zu verwalten. Ein Knoten muß nur mit seinem eigenen RLOG umgehen, und folglich werden Aktionen eines Knotens niemals der Grund dafür sein, daß ein Block in einem Cache irgendeines anderen Knotens unsauber wird. Es ist daher ausreichend, eine einfache, jedem Block zugeordnete Wiederherstellung-LSN (eine, die das RLOG nicht nennt) zu haben, wobei es sich versteht, daß die Wiederherstellung-LSN eine Aufzeichnung im lokalen RLOG identifiziert.

b. Aufzeichnen von Prüfpunktdaten

Der Zweck des Aufzeichnens von Prüfpunktdaten ist sicherzustellen, daß die Bestimmung des sicheren Punktes, wie oben beschrieben, Systemabstürze überleben kann. Ein Aufzeichnen von Prüfpunktdaten kann mit einer Strategie zum Verwalten von Blöcken kombiniert werden, die gestattet, daß sich der sichere Punkt bewegt bzw. verschiebt und den Teil des Protokolls schrumpfen läßt, der ein Wiederholen benötigen wird. Es gibt viele verschiedene Verfahren zum Aufzeichnen von Prüfpunktdaten. Eines wird unten beschrieben, sollte aber nicht als ein gefordertes Verfahren betrachtet werden.
Das bevorzugte Verfahren zum Implementieren dieser Erfindung ist eine Form eines "unscharfen" Aufzeichnens von RLOG-Prüfpunktdaten. Es wird "unscharf" genannt, weil das Aufzeichnen von Prüfpunktdaten ohne Bedeutung dafür bzw. unabhängig davon durchgeführt werden kann, ob eine Transaktion oder eine Operation abgeschlossen ist.
Eine Wiederherstellung einer Version der Tabelle Unsaubere Blöcke 900 aus der Prüfpunktdaten aufzeichnenden Information gestattet eine Bestimmung, wo das Wiederhol- Scannen begonnen werden soll. Nur Blöcke in der Tabelle Unsaubere Blöcke 900 müssen wiederholt werden, weil nur diese Blöcke Aktionen aufweisen, die nicht in den Persistent- Speicher gespeichert worden sind. Wie oben erläutert wurde, gibt die Tabelle Unsaubere Blöcke 900 die früheste protokollierte Aktion an, die ein Wiederholen verlangen könnte.
Eine Wiederherstellung nach einem Systemabsturz über das RLOG und eine Medien-Wiederherstellung über das ALOG werden typischerweise verschiedene sichere Punkte haben und werden entsprechend abgeschnitten sein. Insbesondere kann ein abgeschnittener Teil eines RLOG weiterhin für eine Medien-Wiederherstellung erforderlich sein. Falls dies der Fall ist, wird der abgeschnittene Teil Teil des ALOG.
Ein ALOG-Abschneiden nutzt RLOG-Prüfpunkte. Ein RLOG- Prüfpunkt bestimmt einen sicheren Punkt, der das Abschneiden des RLOG von der Zeit des Prüfpunkts an gestattet. Dies ist so, weil alle Versionen der Daten im Persistent-Speicher jüngeren Datums als dieser sichere Punkt sind oder sonst der Punkt nicht sicher wäre.
Um ein ALOG abzuschneiden, werden Blöcke auf Persistent-Speichern zuerst in den Archivspeicher gesichert. Wenn dies abgeschlossen ist, wird die Archiv-Prüfpunktaufzeichnung in eine übereingekommene Stelle, z.B. im Archivspeicher, geschrieben, um die RLOG-Prüfpunkte zu identifizieren, die aktuell waren, als eine Bestimmung des Archiv- Prüfpunktes begann.
Ein ALOG kann bei dem sicheren Punkt abgeschnitten werden, der durch den RLOG-Prüfpunkt identifiziert wird, der im Archiv-Prüfpunkt für Medien-Wiederherstellung genannt ist. Alle Persistent-Speicherblöcke werden in den Archivspeicher geschrieben, nachdem dieser RLOG-Prüfpunkt ausgeführt wurde, und spiegeln daher alle vor diesem sicheren Punkt des Prüfpunkts vorgenommenen Änderungen wider. Während einer Blocksicherung können mehrere zusätzliche RLOG- Prüfpunkte genommen werden. Diese beeinflussen nicht ein ALOG-Abschneiden, weil es keine Garantie gibt, daß die involvierten Protokollaufzeichnungen alle in die Zustände von Blöcken im Archivspeicher eingebaut worden sind. Aktionen, die nicht wiederholt werden müssen, die aber auf einem ALOG zurückgelassen werden, werden als nicht verwendbar festgestellt und werden während des Prozesses einer Medien- Wiederherstellung ignoriert.
Prüfpunkte werden in das RLOG geschrieben. Um den letzten, in das RLOG geschriebenen Prüfpunkt zu finden, wird dessen Stelle in den Persistent-Speicher des entsprechenden Knotens in einem Bereich einer Globalinformation für den Knoten geschrieben. Die Information über den jüngsten Prüfpunkt ist typischerweise die erste Information, auf die während einer Wiederherstellung zugegriffen wird. Alternativ kann man das Ende des RLOG für den letzten Prüfpunkt suchen.
Prüfpunkte liefern einen bedeutenden Vorteil eines reinen RLOG, was bedeutet, daß das System explizite Kontrolle über die Größe des Wiederhol-Protokolls und daher die Zeit hat, die für eine Wiederhol-Wiederherstellung erforderlich ist. Falls man das RLOG mit dem ULOG kombinieren würde, könnte ein sicherer Punkt für ein Protokollabschneiden aus dem oben erläuterten Grund nicht verwendet werden.
Außerdem erlaubt das Eliminieren einer Aufhebungsinformation aus dem RLOG, daß das System ein Protokollabschneiden durch Schreiben von Blöcken in den Persistent-Speicher steuert. Ein RLOG-Abschneiden verlangt niemals den Abbruch langer Transaktionen. Dies ist nicht wahr, wenn Abschneide- Protokolle eine Aufhebungsinformation enthalten.
Das System übt über das RLOG eine Steuerung aus, indem Blöcke in ihre Stellen im Persistent-Speicher zurückgeschrieben werden. Tatsächlich betrachtet man dieses Schreiben von Blöcken manchmal als Teil des Prüfpunkts. Blöcke können auch in den Persistent-Speicher geschrieben werden, die Wiederherstellung-LSNs aufweisen, die älter sind, d.h. im RLOG weiter zurückliegen. Dies bewegt bzw. verschiebt den sicheren Punkt für das RLOG näher zum Ende des Protokolls. Protokollaufzeichnungen, deren Operationen im neu geschriebenen Block enthalten sind, werden für eine Wiederhol-Wiederherstellung nicht länger benötigt und können daher abgeschnitten werden.
Eine Medien-Wiederherstellung folgt dem gleichen Grundparadigma wie eine Wiederherstellung nach einem Systemabsturz. Versionen von Blöcken werden im Archivspeicher stabil aufgezeichnet. Wie oben erläutert wurde, wird jedes ALOG aus dem abgeschnittenen Teil eines der RLOGs gebildet. Das ALOG selbst kann periodisch abgeschnitten werden basierend darauf, welche Versionen von Blöcken im Archivspeicher sind.
Mit nur einem in einem Block gespeicherten DSI und ohne eine LSN ist es nicht möglich zu wissen, welches Protokoll zuletzt für ein Fortschreiben des Archivspeicherblocks verantwortlich war, noch wo diese Aufzeichnung im RLOG ist. Somit ist die Information in den Blöcken unzureichend, um den richtigen Punkt zu bestimmen, um die ALOGs oder RLOGs abzuschneiden. Die Tabelle Unsaubere Blöcke kann jedoch als ein Anhaltspunkt beim Abschneiden des RLOG verwendet werden. Ein sicherer Punkt eines RLOG kann auch verwendet werden, um einen sicheren Punkt eines ALOG einzurichten.

F. ULOG-Ooerationen

1. ULOG-Verwaltung

Zusätzlich den Vorteilen, die ein Trennen von RLOGs von ULOGs für eine RLOG-Operation hat, gibt es auch Vorteile, die eine solche Trennung für eine ULOG-Operation hat. Zum Beispiel kann ein transaktionsspezifisches ULOG gelöscht werden, wenn eine Transaktion einmal festschreibt. Daher ist eine Platzverwaltung für ULOGs einfach, und eine Aufhebungsinformation bleibt nicht lange im Persistent-Speicher.
Außerdem kann, wie unten erklärt wird, ein ständiges Schreiben von Aufhebungsaufzeichnungen in das Protokoll häufig vermieden werden. Eine Aufhebungsaufzeichnung muß nur geschrieben werden, wenn ein nicht festgeschriebene bzw. ungebundene Daten (engl. uncommitted data) enthaltender Block in den Persistent-Speicher geschrieben ist.
Ein Nachteil getrennter ULOGs und RLOGs für ein Wiederhol-Protokoll besteht darin, daß zwei Protokolle erzwungen werden müssen, wenn ein Block mit nicht festgeschriebenen Daten im Persistent-Speicher geschrieben wird, um das WAL- Protokoll zu erfüllen. Im allgemeinen sollte jedoch ein Schreiben von Blöcken mit nicht festgeschriebenen Daten in den Persistent-Speicher ausreichend selten sein, so daß die Trennung von Protokollen sogar in der Leistung einen Nettogewinn liefert.
Für eine N-Protokoll-Aufhebung können mehrere Knoten gleichzeitig nicht festgeschriebene Daten in einem Block aufweisen. Ein Systemabsturz würde verlangen, daß diese Transaktionen alle aufgehoben werden müssen, was beispielsweise ein Verriegeln während einer Aufhebung-Wiederherstellung auf Koordinatenblockzugriffe erfordern kann.
Um sicherzustellen, daß alle Blöcke bezüglich der Aufhebung-Wiederherstellung 1-Protokoll-artig sein werden, wird nie erlaubt sein, daß ein nicht festgeschriebene Daten von einem Knoten enthaltener Block durch einen zweiten Knoten fortgeschrieben wird. Dies kann durch eine Verriegelungskörnung erreicht werden, die nicht kleiner als ein Block ist. Ein anfordernder Knoten wird dann einen Block empfangen, in dem keine Aufhebungsverarbeitung durch einen anderen Knoten je erlaubt ist. Daher ist, falls z.B. eine Transaktion von einem anderen Knoten einen Block fortgeschrieben hat und dann abbricht, die Wirkung dieser Transaktion schon aufgehoben worden.
Obwohl eine 1-Protokoll-Aufhebung die Kompliziertheit verringert, ist der Einfluß auf die Systemleistung der N- Protokoll-Aufhebung zur Wiederherstellungszeit geringer als für eine N-Protokoll-Wiederausführung. Dies verhält sich so, weil nur der kleine Satz von Transaktionen, die zu der Zeit des Systemabsturzes nicht festgeschrieben waren, ein Aufheben benötigt. Läßt man die Verriegelungskörnung nicht kleiner als einen Block sein, kann dies im wesentlichen den Parallelbetrieb bzw. die Gleichzeitigkeit verringern.
Die Technik der vorliegenden Erfindung vermeidet gewöhnlich die Notwendigkeit, das ULOG für eine kurze Transaktion zu schreiben. Dies verhält sich so, weil es selten der Fall sein wird, daß ein einen Block mit nicht festgeschriebenen Daten von irgendeiner speziellen kurzen Transaktion enthaltender Cache-Schlitz benötigt wird. Die Gründe für eine solche Seltenheit liegen darin, daß die meisten kurzen Transaktionen festschreiben oder abbrechen sollten, bevor ihre Cache-Schlitze benötigt werden.
Sollte ein zu entziehender (engl. to be stolen) Cache- Schlitz einen Block mit nicht festgeschriebenen Daten enthalten, verlangt das WAL-Protokoll das Schreiben von Aufhebungsaufzeichnungen in alle geeigneten ULOGs. Das WAL- Protokoll wird für das ULOG durch erzwungenes Schreiben jedes ULOG durch die Aufzeichnungen erzwungen, die durch U- Letzte-LSN im Eintrag der Tabelle Unsaubere Blöcke für den Block identifiziert sind. Wie oben erläutert wurde, identifizieren U-Letzte-LSNs die Aufhebungsaufzeichnungen für die letzte Fortschreibung in den Block in jedem ULOG.
Mit dem WAL-Protokoll wird die Information, die benötigt wird, um die Zustände von Blöcken ohne Fortschreibungen einer Transaktion zu speichern, immer dauerhaft in ein ULOG einer Transaktion vor dem Überschreiben der Persistent-Speicherversion des Blocks mit dem neuen Zustand gespeichert. Der Zustand der Blöcke ohne die Fortschreibungen einer Transaktion ist daher vor einer Transaktion-Festschreibung immer langlebig bzw. dauerhaft. Diese Information ist entweder: (i) in der Blockversion im Persistent- Speicher, (ii) "wiedererlangbare Wiederholung" von der Version im Persistent-Speicher unter Verwendung der RLOG- Information von vorhergehenden Transaktionen oder (iii) eine wiedererlangbare Aufhebung von einer Version, die durch (i) oder (ii) unter Verwendung der Aufhebungsinformation erzeugt wird, die entweder auf dem ULOG durch das WAL- Protokoll für diese Transaktion protokolliert oder während einer Wiederhol-Wiederherstellung erzeugt wird.
Für die Blöcke auf dem Persistent-Speicher, die noch in einem früheren Zustand sind, ist es möglich, RLOG-Aufzeichnungen ohne entsprechende ULOG-Aufzeichnungen zu haben. Dies ist üblich, wo es eine "wahlfreie" Aufhebung-Protokollierung 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 ignoriert werden.
Somit müssen alle Aktionen, die nach einer Wiederhol- Wiederherstellung aufgehoben werden müssen, nicht im ULOG gefunden werden. Sollte das System abstürzen, müssen die fehlenden Aufhebungsaufzeichnungen aus den Wiederhol-Aufzeichnungen und früheren Zuständen von Blöcken erzeugt werden. Solange eine Aktion nur von dem Blockzustand und den Werteparametern der protokollierten Aktion abhängt, wird die Erzeugung von Aufhebungsaufzeichnungen möglich sein, weil alle Information, die verfügbar war, als die Aktion ursprünglich durchgeführt wurde, an dieser Stelle verfügbar ist.
Aktionen schließen am ULOG aus zwei Gründen ab: entweder erzwingt das WAL-Protokoll eine Pufferaufzeichnung in das ULOG, weil der Block in den Persistent-Speicher geschrieben wurde, oder das Schreiben des ULOG für eine WAL- Erzwingung hat das Schreiben vorhergehender ULOG- Aufzeichnungen und in einigen Fällen nachfolgender ULOG- Aufzeichnungen zur Folge, die im Aufhebungspuffer sind.
Für diese Aktionen ist es nicht notwendig, Aufhebungsaufzeichnungen während einer Wiederherstellung zu erzeugen, weil garantiert wird, daß diese Aufzeichnungen auf einem ULOG sind. Dies ist wichtig, weil es nicht möglich sein könnte, die ULOG-Aufzeichnung für die für eine Wiederholung protokollierte Transaktion zu konstruieren, weil die Version des Blocks im Persistent-Speicher einen Zustand hat, der nach der Aktion kommt. Glücklicherweise sind es exakt diese Blöcke, für die ULOG-Aufzeichnungen schon existieren.
Während einer Wiederholung würden die fehlenden Aufhebungsaufzeichnungen erzeugt werden. Bis zum Ende einer Wiederholung wäre die Vereinigung erzeugter Aufhebungsaufzeichnungen und Aufhebungsaufzeichnungen auf den ULOGs imstande, alle nicht festgeschriebenen Transaktionen zurückzurollen.

2. ULOG-Optimierung

Mit der vorliegenden Erfindung kann die Verwendung des ULOG optimiert werden, indem man sich davon überzeugt, daß die Inhalte eines Aufhebung-Protokoll-Puffers in ein ULOG nur wenn notwendig geschrieben werden. Im allgemeinen muß der Aufhebungspuffer nur in ein ULOG gespeichert werden, wenn ein nicht festgeschriebene Daten von einer aktuellen Transaktion enthaltender Block in den Persistent-Speicher geschrieben wird. Falls die Transaktion festgeschrieben worden ist, besteht keine Notwendigkeit, die Fortschreibungen in der Transaktion aufzuheben, und somit kann der Aufhebungspuffer gelöscht werden.
Figur 10 zeigt ein Flußdiagramm 1000 einer Prozedur zum Implementieren dieser ULOG-Optimierung unter Verwendung des WAL-Protokolls. Man nimmt an, daß eine Version des Blocks in den Persistent-Speicher geschrieben werden soll.
Falls der zu schreibende Block nicht festgeschriebene Daten enthält (Schritt 1010), muß dann der Wiederhol-Puffer in das RLOG im Persistent-Speicher geschrieben werden, und jegliche Aufhebungspuffer werden in ULOGs im Persistent- Speicher geschrieben (Schritt 1020).
Nach dem Schreiben der Wiederhol-Puffer in das RLOG und der Aufhebungspuffer in die ULOGs (Schritt 1020) oder falls die Blöcke keine festgeschriebenen Daten enthielten (Schritt 1010), wird der Block in den Persistent-Speicher geschrieben (Schritt 1030). Dies stimmt mit dem WAL-Protokoll überein.
Somit werden die Aufhebungspuffer nur geschrieben, falls zu speichernde, nicht festgeschriebene Daten existieren. Jedesmal wenn eine Transaktion festschreibt, kann der entsprechende Aufhebung-Protokoll-Puffer gelöscht werden, weil er nie in den Persistent-Speicher geschrieben werden muß. Ferner kann das ULOG selbst für die Transaktion gelöscht werden, weil eine Aufhebung nun nie erforderlich ist.
Eine festgeschriebene Transaktion wird durch das Aufzeichnen aller Wiederhol-Aufzeichnungen für die Transaktion im RLOG im Persistent-Speicher dauerhaft gemacht. Der fortgeschriebene Block kann zu irgendeiner späteren Zeit in den Persistent-Speicher geschrieben werden. Selbst wenn ein Absturz auftreten würde, bevor der fortgeschriebene Block geschrieben wäre, könnte das RLOG wiedergewonnen werden, um den Zustand des Blocks wiederherzustellen bzw. zu rekonstruieren, und das System weiß, daß eine Transaktion festgeschrieben bzw. ausgeführt ist, indem eine Festschreibung- Aufzeichnung in das RLOG gespeichert wird.

3. Transaktionsabbrüche

Ein ULOG kann folglich gelöscht werden, wenn eine Transaktion festschreibt, weil ein Rückgängigmachen bzw. Aufheben der Effekte einer Transaktion nicht länger erforderlich ist. Für einen Transaktionsabbruch ist die Situation etwas verschieden. Bevor die ULOG-Aufzeichnungen für eine Transaktion gelöscht werden können, ist es notwendig sicherzustellen, daß alle durch eine abbrechende Transaktion geänderten Blöcke nicht nur ihre Änderungen aufheben liessen, sondern auch daß die resultierenden aufgehobenen Blockzustände dauerhaft irgendwo anders als in einem ULOG gespeichert sind. Entweder müssen die Blöcke selbst in ihrem aufgehobenen Zustand in den Persistent-Speicher ("ERZWUNGENER"-Abbruch genannt) geschrieben sein, oder die Aufhebungstransaktionen müssen in das RLOG geschrieben und gezwungen sein ("KEIN-ERZWUNGENER"-Abbruch genannt). Ähnlich festschreibenden Transaktionen vermeidet ein Protokollieren von Aktionen auf dem RLOG die Notwendigkeit, in diesem Fall Blöcke in den Persistent-Speicher zu zwingen.

a. KEIN-ERZWUNGENER-Abbruch

Ein KEIN-ERZWUNGENER-Abbruch kann realisiert werden, indem die Aufhebungsoperationen als zusätzliche Aktionen der abbrechenden Transaktion behandelt werden, welche den Effekt der vorherigen Fortschreibungen umkehren. Solche "kompensierenden" Aktionen sind auf dem RLOG als "Kompensation-Protokollaufzeichnungen" (CLRs) protokolliert.
Kompensation-Protokollaufzeichnungen sind tatsächlich Aufhebungsaufzeichnungen, die in das RLOG verschoben wurden. Eine zusätzliche Information ist jedoch erforderlich, um diese Aufzeichnungen von anderen RLOG-Aufzeichnungen zu unterscheiden. Außerdem wird ein SI benötigt, um die CLR korrekt bezüglich anderer zu wiederholender protokollierter Transaktionen korrekt hintereinander anzuordnen.
Figur 11 zeigt eine CLR 1100 mit mehreren Attributen. Ein TYPE-Attribut 1110 identifiziert diese Protokollaufzeichnung als eine Kompensation-Protokollaufzeichnung.
Ein TID-Attribut 1120 ist ein eindeutiger Identifizierer für die Transaktion. Er hilft beim Finden der dieser RLOG-CLR entsprechenden ULOG-Aufzeichnung.
Ein BSI-Attribut 1130 ist der Vor-Zustand-Identifizierer, wie oben beschrieben wurde. In diesem Zusammenhang identifiziert das BSI-Attribut 1130 den Blockzustand zu der Zeit, in der die CLR verwendet wird.
Ein BID-Attribut 1140 identifiziert den Block, der durch die mit dieser Aufzeichnung protokollierten Aktion modifiziert wurde.
Ein UNDO_DATA-Attribut 1150 beschreibt die Natur der rückgängig zu machenden bzw. aufzuhebenden Aktion und liefert genug Information für die aufzuhebende Aktion, nachdem ihre zugeordnete ursprüngliche Aktion in den Blockzustand eingebaut worden ist. Der Wert für das UNDO_DATA-Attribut 1150 kommt von der entsprechenden Aufhebungsaufzeichnung, die entweder in einem ULOG oder in einem Aufhebungspuffer gespeichert ist.
Ein RLSN-Attribut 1160 ist die RLOG-Aufzeichnung auf dem RLOG, die die gleiche Aktion beschreibt, für die diese CLR die Aufhebung ist. Dieses Attribut kommt vom RLSN- Attribut der ULOG.
LSN 1170, das nicht explizit gespeichert werden muß, weil es durch seine Stelle im RLOG identifiziert werden kann, identifiziert diese CLR eindeutig auf dem RLOG. Die LSN wird verwendet, um das Wiederhol-Scannen und Aufzeichnen von Prüfpunktdaten des RLOG zu steuern.
Wie bei einer Transaktionsfestschreibung sollten, wenn eine Transaktion abbricht, alle Wiederhol-Aufzeichnungen, die die Aktionen der Transaktion beschreiben, in das RLOG geschrieben werden. Für die abgebrochene Transaktion schließt dies die Aufhebungsaktionen in den CLRs ein. Für eine Festschreibung wird das RLOG gezwungen sicherzustellen, daß alle Wiederhol-Aufzeichnungen für die Transaktion stabil gespeichert sind. Für einen Abbruch ist dies nicht strikt notwendig. Die benötigte Information existiert noch auf dem ULOG. Das ULOG kann jedoch nicht gelöscht werden, bis CLRs für die abbrechende Transaktion dauerhaft in das RLOG geschrieben worden sind. Die CLRs auf dem RLOG dienen dann als Ersatz für die ULOG-Aufzeichnungen.
Eine wünschenswerte Eigenschaft des KEIN-ZWANG-Ansatzes ist, daß für eine Medien-Wiederherstellung nur die Wiederhol-Phase benötigt wird. Fortschreibungen werden in der Reihenfolge verwendet, in der sie während des ALOG-Mischens verarbeitet werden. Während der Verarbeitung des ALOG ist keine separate Aufhebung-Phase erforderlich, weil jegliche erforderliche Aufhebung durch Verwenden von CLRs geliefert wird.
Eine zweite Tabelle, die Tabelle Aktive Transaktionen genannt, zeichnet die Information auf, die benötigt wird, um Aufhebungsoperationen auszuführen. Wie die Tabelle Unsaubere Blöcke 900 wird die Tabelle Aktive Transaktionen Teil der Prüfpunktinformation auf dem RLOG, so daß ihre Information gesichert ist, falls das System abstürzt.
Die Tabelle Aktive Transaktionen gibt Transaktionen, die vielleicht aufgehoben werden müssen, den Zustand der Aufhebung/Wiederhol-Protokollierung und den Aufhebungsfortschritt an. In der Tabelle Aktive Transaktionen muß genug Information codiert sein, um eine Wiederherstellung nach allen Systemabstürzen sicherzustellen, einschließlich derjenigen, die während einer Wiederherstellung selbst auftreten. Eine gewisse Information, die die Wiederherstellungsleistung verbessert, kann ebenfalls enthalten sein.
Figur 12 zeigt ein Beispiel einer Tabelle Aktive Transaktionen 1200. Die Tabelle 1200 enthält Aufzeichnungen 1201, 1202 und 1207. Jede der Aufzeichnungen enthält mehrere Attribute.
Ein TID-Attribut 1210 ist ein eindeutiger Identifizierer für die Transaktion. Er ist der gleiche wie der für RLOG-Aufzeichnungen verwendete Transaktionsidentifizierer.
Ein STATE-Attribut 1220 gibt an, ob eine aktive Transaktion als Teil einer Zweiphasen-Festschreibung "vorbereitet" ist. Eine Zweiphasen-Festschreibung wird verwendet, wenn mehrere Knoten an einer Transaktion beteiligt sind. Um solch eine Transaktion festzuschreiben, müssen zuerst alle Knoten die Transaktion vorbereiten (Phase 1), bevor sie sie ausführen bzw. festschreiben können (Phase 2). Die Vorbereitung wird vorgenommen, um partielle Festschreibungen zu vermeiden, die auftreten würden, falls ein Knoten festschreibt, ein anderer aber abbricht. Eine vorbereitete Transaktion muß in der Tabelle Aktive Transaktionen 1200 festgehalten werden, weil sie möglicherweise zurückgerollt werden muß. Im Gegensatz zu einer nicht vorbereiteten Transaktion sollte eine vorbereitete Transaktion nicht automatisch abgebrochen werden.
Ein ULOG-loc-Attribut 1230 gibt die Stelle (engl. location) des transaktionsspezifischen ULOG an. Dieses Attribut muß nur vorhanden sein, sollte kein anderer Weg existieren, um das ULOG zu finden. Zum Beispiel könnte das TID 1210 einen Ersatzweg zum Finden des ULOG für die Transaktion bereitstellen.
Ein HIGH-Attribut 1240 gibt die RLOG-LSN der Aktion an, welche die letzte Aktion mit einer in das ULOG für diese Transaktion geschriebenen Aufhebungsaufzeichnung ist. Diese ULOG-Aufzeichnung enthält ein RLOG-LSN im RLSN, so daß RLOG-Aufzeichnungen, die RLSN folgen, während einer Wiederholung nach einem Systemabsturz erzeugt werden müssen, um bereit zu sein, die Transaktion zurückzurollen, sollte sie nicht festgeschrieben worden sein.
Ein NEXT-Attribut 1250 gibt das RLOG-LSN der nächsten Aktion in der Transaktion an, die aufgehoben werden muß. Für Transaktionen, die nicht gerade zurückgerollt werden, ist das NEXT-Attribut 1250 gleich dem LSN der letzten RLOG- Aufzeichnung für eine Transaktion.
Obwohl einige Systeme CLRs während einer Wiederherstellung rückgängig machen bzw. aufheben, werden sie in der bevorzugten Ausführungsform nicht aufgehoben. Statt dessen werden CLRs [über das TYPE-Attribut] gekennzeichnet, so daß sie während einer Wiederherstellung identifiziert werden können.
Wenn eine Aufhebungsaufzeichnung in ein ULOG gezwungen wird, wird wegen der sequentiellen Natur des ULOG garantiert, daß alle vorhergehenden Aufhebungsaufzeichnungen dauerhaft sind. RLOG-Aufzeichnungen werden in der gleichen Reihenfolge wie die ULOG-Aufzeichnungen geschrieben. Falls man eine RLOG-Aufzeichnung findet, die keine Wiederholung verlangt, weil beispielsweise ihr Effekt schon in der Version des Blocks auf dem Persistent-Speicher ist, weisen daher alle vorhergehenden RLOG-Aufzeichnungen dann Aufhebungsaufzeichnungen im ULOG auf. Dies trat auf, weil das ULOG erzwungen wurde, als der Block geschrieben wurde, und daher wurden alle früheren ULOG-Aufzeichnungen zur gleichen Zeit geschrieben. Falls Aufhebungsaufzeichnungen während einer Wiederholung für diese Transaktion erzeugt worden sind, können sie gelöscht werden, weil alle derartigen früheren Aufzeichnungen schon im ULOG existieren.
Die RLOG-LSN der letzten RLOG-Aufzeichnung, für die eine ULOG-Aufzeichnung geschrieben wurde, ist im HIGH-Attribut 1240 (Figur 12) der Eintragung der Tabelle Aktive Transaktionen für die Transaktion gespeichert. RLOG-Aufzeichnungen, die dieser angezeigten Wiederhol-Protokollaufzeichnung vorangehen, erzeugen keine Aufhebungsaufzeichnungen während einer Wiederholung, weil sie alle schon ULOG-Aufzeichnungen aufweisen. RLOG-Aufzeichnungen, die der durch HIGH bezeichneten folgen, können erfordern, daß Aufhebungsaufzeichnungen erzeugt werden.
Die Erzeugung einer Aufhebungsaufzeichnung kann auch vermieden werden, falls die Anzahl Aufhebungsaufzeichnungen, die schon für jede Transaktion verwendet worden sind, sorgfältig überwacht wird. Daher ist die Aufhebung "hohe Zuordnungsmarke" (engl. high water mark) im NEXT-Attribut 1250 der Tabelle Aktive Transaktionen 1200 codiert. Das NEXT-Attribut 1250 enthält die Aufzeichnungsnummer der nächsten Aufhebungsaufzeichnung, die für die Transaktion verwendet werden soll.
Während einer normalen Verarbeitung ist das NEXT-Attribut 1250 immer die Aufzeichnungsnummer für die jüngste Transaktion der Transaktionen. Der Wert im NEXT-Attribut 1250 wird inkrementiert, während diese Aktionen protokolliert werden. Während einer Aufhebung-Wiederherstellung wird der Wert im NEXT-Attribut 1250 dekrementiert, nachdem jede Aufhebungsaktion verwendet und ihre CLR protokolliert ist, wobei ihre Vorgänger-Aufhebungsaufzeichnung als die nächste Aufhebungsaktion benannt wird. Sollte während eines Zurückrollens ein Systemabsturz stattfinden, müssen Aufhebungsaufzeichnungen mit höheren Aufzeichnungsnummern als der durch das NEXT-Attribut 1250 angegebenen nicht wiederverwendet werden und müssen daher nicht wieder während einer Wiederholung erzeugt werden.
Das Endergebnis ist, daß während einer Wiederholung Aufhebungsaufzeichnungen für die RLOG-Aufzeichnungen erzeugt werden, deren Aufzeichnungsnummern zwischen die Werte für das HIGH-Attribut 1240 und das NEXT-Attribut 1250 fallen. Wann immer der Wert des HIGH-Attributs 1240 größer oder gleich dem Wert des NEXT-Attributs 1250 ist, müssen überhaupt keine Aufhebungsaufzeichnungen erzeugt werden.

b. Erzwungener Abbruch

Beim "ERZWUNGENEN"-Abbruch werden CLRs nicht geschrieben. Wenn Blöcke aufgehoben werden, werden statt dessen die Blöcke selbst in den Persistent-Speicher gezwungen. Bei diesem Abbruchtyp ist es notwendig, eine Kenntnis darüber stabil festzuhalten, daß ein Block das Ergebnis einer Verwendung einer Aufhebungsaufzeichnung und auch die Sequenz enthält, in der die Aufhebungsoperationen durchgeführt wurden, ohne eine CLR für sie zu schreiben.
Ein Ziel besteht darin, eine N-Protokoll-Aufhebung zu unterstützen, bei der mehrere Knoten Transaktionen auf einem einzigen Block als Folge eines Systemabsturzes aufheben können. Der Fortschritt von Aufhebungsoperationen, die von jedem Knoten ausgeführt werden, muß daher stabil aufgezeichnet werden. Dies ist es, was CLRs in dem Fall NICHT- ERZWUNGEN leisten. Ohne CLRs wird eine gewisse andere Technik benötigt.
Eine Alternative besteht darin, die benötigte Information in den Block zu schreiben, der zum Persistent-Speicher geht. Obwohl eine CLR eine komplette Beschreibung der Aufhebungsaktion enthält, wird nicht die ganze Beschreibung benötigt. Im Fall ERZWUNGENER-Abbruch ist es erforderlich, die Ergebnisse der Aufhebungstransaktionen aufzuzeichnen und welche von ihnen aufgehoben worden sind.

G. Normale Operationen

Während einer normalen Operation haben Transaktion- Start-, Block-Fortschreibung-, Block-Schreib-, Transaktion- Abbruch-, Transaktion-Vorbereitung und Transaktion-Festschreibung-Operationen einen Einfluß auf Erfordernisse der Wiederherstellung. Während einer normalen Operation müssen daher Schritte hinsichtlich eines Protokollierens unternommen werden, um sicherzustellen, daß eine Wiederherstellung möglich ist.
Figur 13 enthält eine Prozedur 1300 für Transaktion- Start-Operationen. Zuerst muß in das RLOG eine START _-TRANSAKTION-Aufzeichnung geschrieben werden (Schritt 1310). Als nächstes wird die Transaktion in die Tabelle Aktive Transaktionen 1200 im "aktiven" Zustand eingetragen (Schritt 1320). Dann werden das ULOG für die Transaktion und ihre Identität in ULOG-loc 1230 aufgezeichnet (Schritt 1330). Schließlich werden die Werte HIGH 1240 und NEXT 1250 auf Null gesetzt (Schritt 1340).
Figur 14 zeigt eine Prozedur 1400 für eine Block- Fortschreibung-Operation. Zuerst wird die erforderliche Parallelbetriebsteuerung ausgeführt, um den Block für eine Fortschreibung zu verriegeln (Schritt 1410). Auf den Block wird dann vom Persistent-Speicher aus zugegriffen, falls er nicht schon im Cache ist (Schritt 1420). Die angegebene Transaktion wird dann an der Version des Blocks im Cache durchgeführt (Schritt 1430). Als nächstes wird der DSI des Blocks mit dem ASI für die Aktion fortgeschrieben (Schritt 1440). Sowohl RLOG- als auch ULOG-Aufzeichnungen werden dann für die Fortschreibung konstruiert und werden zu ihren geeigneten Puffern aktualisiert (Schritt 1450). Die Letzte- LSNs 950 (Figur 9) werden geeignet fortgeschrieben (Schritt 1460). Der Wert NEXT 1250 wird dann auf die ULOG-LSN der Aufhebungsaufzeichnung für diese Aktion gesetzt (Schritt 1470).
Falls der Block sauber war (Schritt 1475), wird er unsauber gemacht (Schritt 1480). Er wird dann in die Tabelle Unsaubere Blöcke 900 eingegeben, wobei die Wiederherstellung-LSN 920 auf die LSN der RLOG-Aufzeichnung für ihn gesetzt wird (Schritt 1485).
Figur 15 enthält ein Flußdiagramm 1500 für eine Block- Schreib-Operation, falls der Block nicht festgeschriebene bzw. ungebundene Daten enthält. Zuerst wird das WAL- Protokoll erzwungen (Schritt 1510). Speziell werden vor einem Schreiben des Blocks in den Persistent-Speicher alle Aufhebungspuffer bis zur entsprechenden Letzte-ULSN 958 (Figur 9) für den Block geschrieben, und der RLOG-Puffer wird bis zur Letzte-RLSN 955 geschrieben (Figur 9). Für jede in den Letzte-ULSNs für den Block identifizierte Transaktion wird HIGH für diese Transaktionen auf die RLOG-LSN- Werte in den RLSN-Attributen der Aufhebungsaufzeichnungen gesetzt, die durch die Letzte-ULSN-Attribute von der Tabelle Unsaubere Blöcke identifiziert wurden. Jede Letzte-ULSN muß sowohl eine Transaktion über ein TID als auch eine ULOG-LSN identifizieren. Für diese Protokolle gibt es Zeiten, in denen kein Schreiben vorgenommen werden muß, weil diese Aufzeichnungen schon geschrieben worden sind.
Der Block wird dann aus der Tabelle Unsaubere Blöcke 900 entfernt (Schritt 1550), und der Block wird in den Persistent-Speicher geschrieben (Schritt 1530). Eine Block- Schreib-Aufzeichnung kann dann in das RLOG geschrieben werden, um anzuzeigen, daß der Block in den Persistent-Speicher geschrieben worden ist, aber dies ist wahlfrei. Diese Block-Schreib-Aufzeichnung muß nicht erzwungen werden.
Figur 16 enthält ein Flußdiagramm 1600 für eine Transaktion-Abbruch-Operation. Zuerst wird die durch den Wert im NEXT-Feld 1250 angegebene Aufhebungsaufzeichnung lokalisiert (Schritt 1610). Die erforderliche Parallelbetriebsteuerung wird dann an den beteiligten Blöcken ausgeführt, exakt als ob sie gerade durch normale Fortschreibungen verarbeitet würden (Schritt 1620).
Als nächstes wird die aktuelle Aufhebung-Protokollaufzeichnung für ihren bezeichneten Block verwendet (Schritt 1630), und eine CLR für die Aufhebungsaktion wird in das RLOG geschrieben (Schritt 1640). Der Wert des NEXT-Feldes 1250 wird dann dekrementiert, um die nächste zu verwendende Aufhebung-Protokollaufzeichnung (Schritt 1640) als die "aktuelle" Aufhebungsaufzeichnung zu indizieren.
Falls irgendwelche Aufhebungsaufzeichnungen für die Transaktion übrig bleiben (Schritt 1660), wird die Steuerung zum Schritt 1610 zurückgeführt. Andernfalls wird auf dem RLOG eine ABBRUCH-Aufzeichnung plaziert (Schritt 1670). Das RLOG wird dann in den Persistent-Speicher bis zur ABBRUCH-Aufzeichnung gespeichert (Schritt 1680). Das ULOG wird dann gelöscht (Schritt 1690). Schließlich wird die Transaktion aus der Tabelle Aktive Transaktionen 1200 (Figur 12) entfernt (Schritt 1695).
Figur 17 zeigt ein Flußdiagramm 1700 für eine Transaktion-Vorbereitung-Operation. Zuerst wird in das RLOG eine Vorbereitung-Protokollaufzeichnung für die Transaktion geschrieben (Schritt 1710). Als nächstes wird das RLOG bis zu dieser Vorbereitung-Protokollaufzeichnung erzwungen (Schritt 1720). Schließlich wird der Zustand der gerade "vorbereiteten" Transaktion in der Tabelle Aktive Transaktionen 1200 geändert (Schritt 1730).
Figur 18 zeigt ein Flußdiagramm 1800 für eine Transaktion-Festschreibung-Operation. Zuerst wird in das RLOG eine Festschreibung-Protokollaufzeichnung für die Transaktion geschrieben (Schritt 1810). Als nächstes wird das RLOG bis zu dieser Aufzeichnung gezwungen (Schritt 1820). Das ULOG wird dann gelöscht (Schritt 1830). Schließlich wird aus der Tabelle Aktive Transaktionen 1200 die Transaktion entfernt (Schritt 1880).

H. Verarbeitung einer Wiederherstellung nach einem Systemabsturz

In der vorhergehenden Diskussion sind verschiedene Aspekte von Protokollen, Zustandsidentifizierern und einer Wiederherstellung diskutiert worden. Sie können in verschiedenen Verfahren zu einem effektiven Wiederherstellungsschema kombiniert werden. Das bevorzugte Verfahren wird unten beschrieben.

1. Analyse-Phase

Eine Analyse-Phase ist nicht streng notwendig. Ohne eine Analyse-Phase kann jedoch während der anderen Wiederherstellungsphasen eine gewisse unnötige Arbeit ausgeführt werden.
Der Zweck der Analyse-Phase ist, den Systemzustand wie im letzten Prüfpunkt gespeichert in den Zustand der Datenbank zu der Zeit zu bringen, zu der das System abstürzte. Dazu kann die Information im letzten kompletten Prüfpunkt auf dem RLOG gelesen und verwendet werden, um die Werte für die Tabelle Unsaubere Blöcke 900 (Figur 9) und die Tabelle Aktive Transaktionen 1200 (Figur 12) zu initialisieren. Diesem letzten Prüfpunkt folgende RLOG-Aufzeichnungen werden dann gelesen. Die Analyse-Phase simuliert die protokollierten Aktionen in ihren Wirkungen auf die beiden Tabellen.
Hinsichtlich der speziellen Aufzeichnungen werden die Start-Transaktion-Aufzeichnungen exakt wie eine Start- Transaktion-Operation bezüglich der Tabelle Aktive Transaktionen behandelt. Fortschreibung-Protokollaufzeichnungen werden exakt wie eine Blockfortschreibung bezüglich der Tabelle Unsaubere Blöcke 900 und der Tabelle Aktive Transaktionen 1200 behandelt, aber die Fortschreibung wird nicht verwendet. Kompensation-Protokollaufzeichnungen werden exakt wie eine Blockfortschreibung bezüglich der Tabelle Unsaubere Blöcke 900 und der Tabelle Aktive Transaktionen 1200 behandelt, außer der Wert des NEXT-Attributs 1250 wird dekrementiert, und die Fortschreibung wird nicht verwendet.
Für Block-Schreib-Aufzeichnungen wird der Block aus der Tabelle Unsaubere Blöcke 900 entfernt. Für Abbruch-Transaktion-Aufzeichnungen wird die Transaktion aus der Tabelle Aktive Transaktionen 1200 gelöscht. Für Vorbereitung-Transaktion-Aufzeichnungen wird der Zustand der Transaktion in der Tabelle Aktive Transaktionen 1200 auf "vorbereitet" gesetzt. Für Festschreibung-Transaktion-Aufzeichnungen wird die Transaktion aus der Tabelle Aktive Transaktionen 1200 gelöscht.
Um das HIGH-Attribut 1240 für die Transaktionen in der Tabelle Aktive Transaktionen 1200 wiederherzustellen bzw. zu rekonstruieren, muß auf das ULOG zugegriffen werden, um das RLSN-Attribut der letzten, in das ULOG geschriebenen Aufzeichnung zu finden. Dieses LSN wird der Wert für das HIGH-Attribut 1240. Alternativ dazu kann der Wert für das HIGH-Attribut 1240 vom Prüfpunkt verwendet oder fortgeschrieben werden. Diese RLOG-LSN kann verwendet werden, um ein Erzeugen von Aufhebungsaufzeichnungen für Aktionen zu vermeiden, die auf dem ULOG für eine Transaktion schon aufgezeichnet sind. Nur eine RLOG-Aufzeichnung fur eine Transaktion, die diesem Wert folgen, muß eine Aufhebungsinformation erzeugen lassen.
Das NEXT-Attribut 1250 ist dann entweder (1) die RLOG- LSN der letzten Aktion, deren Protokollaufzeichnung in das RLOG für die Transaktion geschrieben ist, falls diese Protokollaufzeichnung für eine Fortschreibung dient, oder (2) das RLSN-Attribut der letzten CLR, die für die Transaktion geschrieben wurde. Somit kann das NEXT-Attribut 1250 während des Analysedurchgangs des RLOG wiederhergestellt werden. Das NEXT-Attribut 1250 identifiziert über den RLSN- Wert in den ULOG-Aufzeichnungen die nächste auszuführende Aufhebungsaufzeichnung. Es kann auch verwendet werden, um eine Erzeugung von Aufhebungsaufzeichnungen für Aktionen zu vermeiden, die schon kompensiert worden sind, indem man CLRs schreiben ließ, um sie aufzuheben. Somit brauchen Wiederhol-Aufzeichnungen für eine Transaktion mit RLOG-LSNs, die größer als das NEXT-Attribut 1250 für die Transaktion in der Tabelle Aktive Transaktionen 1200 sind, keine Aufhebungsinformation aufweisen, die für sie erzeugt wurde, weil eine Aufhebung vorgenommen wird, wenn die bestehenden CLRs während der Wiederhol-Phase der Wiederherstellung verwendet werden.

2. Die Wiederhol-Phase

In der Wiederhol-Phase werden alle Blöcke, die in der rekonstruierten Tabelle Unsaubere Blöcke 900 als unsauber angegeben sind, in den Cache gelesen. Diese Lesung kann, überlappend mit dem Scannen des RLOG, auf einmal vorgenommen werden.
Einige Blöcke können durch mehrere Knoten gelesen werden, um zu bestimmen, ob sie in einer lokalen Wiederholung berücksichtigt werden müssen, aber nur einer der Knoten wird tatsächlich eine Wiederholung für einen Block ausführen. Dies kann jedoch nahezu vollständig vermieden werden, indem Block-Schreib-Aufzeichnungen in das RLOG geschrieben werden. Weil Block-Schreib-Aufzeichnungen nicht erzwungen werden müssen, wird ein Block gelegentlich vom Persistent- Speicher gelesen werden, wenn dies nicht notwendig ist. Der Nachteil eines solchen Lesens ist jedoch gering.
Im Persistent-Speicher existiert eine 1-Protokoll- Version jedes Blocks, so daß nur ein Knoten Aufzeichnungen in seinem Protokoll haben kann, die einen BSI gleich dem DSI des Blocks aufweisen. Dieser Knoten ist derjenige, der eine Wiederhol-Verarbeitung auf dem Block unabhängig durchführen wird. Eine Wiederholung kann daher durch die getrennten Knoten des Systems jeweils mit ihrem eigenen RLOG parallel ausgeführt werden. Hier wird keine Parallelbetriebsteuerung benötigt.
Die Wiederhol-Phase rekonstruiert den Zustand des Cache des Knotens durch Zugreifen auf die unsauberen Blöcke, die eine Wiederholung brauchen, und Eingeben der Änderungen, wie sie in den RLOG-Aufzeichnungen angegeben sind. Der resultierende Cache enthält die unsauberen Blöcke in ihren Zuständen vom Zeitpunkt des Absturzes an. Die Blöcke, die der Wiederholung unterzogen wurden, sind verriegelt worden. Die resultierenden Tabelle Unsaubere Blöcke 900 und Tabelle Aktive Transaktionen 1200 werden ähnlich rekonstruiert. Blöcke, die einer Wiederholung unterzogen wurden, sind verriegelt worden.
Nur Wiederhol-Aufzeichnungen für unsaubere Blöcke, wie in der Tabelle Unsaubere Blöcke 900 nach der Analyse-Phase angegeben, müssen vielleicht wiederholt werden. Das Wiederhol-Scannen des RLOG beginnt bei der frühesten Wiederherstellung-LSN 920, die in der Tabelle Unsaubere Blöcke 900 aufgezeichnet ist. Dies ist der sichere Punkt für eine Wiederholung. Daher sind alle Fortschreibungen in jeden Block, seit er in den Persistent-Speicher geschrieben wurde, dahingehend gesichert, daß sie in dem Wiederhol-Scannen enthalten sind.
Wie oben erläutert wurde, gibt es nur zwei Fälle, die auftreten können, wenn man versucht, eine RLOG-Aufzeichnung für ihren entsprechenden Block zu verwenden. Falls der BSI der RLOG-Aufzeichnung nicht gleich dem DSI des Blocks ist, kann die protokollierte Aktion ignoriert werden. Falls statt dessen der BSI der RLOG-Aufzeichnung gleich dem DSI der Blöcke ist, wird die geeignete Wiederhol-Tätigkeit ausgeführt.
Das Verfahren der Wiederhol-Phase beinhaltet ein Wiederholen der Geschichte. Alle mit der durch eine Wiederherstellung-LSN des Blocks bezeichneten RLOG-Aufzeichnung beginnenden Fortschreibung-RLOG-Aufzeichnungen werden verwendet, selbst diejenigen, die zu Transaktionen gehören, die anschließend aufgehoben werden müssen. Das Prinzip besteht hier darin, daß es notwendig ist, eine zu wiederholende Aktion auf den Block in exakt dem Zustand anzuwenden, auf den die ursprüngliche Aktion angewandt wurde.
Bei der Anwendung einer RLOG-Aufzeichnung auf einen Block wird der DSI des Blocks zum ASI für die Wiederhol- Aktion fortgeschrieben. Der Knoten fordert eine geeignete Verriegelung auf dem Block an, wenn eine RLOG-Aktion verwendet wird. Eine Wiederholung muß nicht darauf warten, daß die Verriegelung weitergegeben wird, weil kein anderer Knoten eine Verriegelung anfordern wird. Die angeforderten Verriegelungen müssen jedoch vor dem Beginn einer Aufhebung weitergegeben werden. Dies ist die Art und Weise, in der eine Parallelbetriebsteuerung für die Aufhebung-Phase initialisiert wird.
Falls eine auf dem RLOG protokollierte normale Fort- Schreibung eine Wiederholung verlangt, kann es notwendig sein, eine ULOG-Aufzeichnung für sie zu erzeugen. Alle RLOG-Wiederhol-Aufzeichnungen für eine Transaktion mit LSNs zwischen den Werten HIGH und NEXT werden eine Aufhebungsinformation aufweisen, die für diese erzeugt wurde. Diese Information enthält vorzugsweise ULOG-Aufzeichnungen mit RLSN-Attributen, die diese Aufzeichnungen identifizieren.
Falls es nicht erforderlich ist, daß eine Aktion wiederholt wird, werden frühere Aufhebungsaufzeichnungen, die ungeeignet erzeugt worden sind, gelöscht, weil das ULOG über das WAL-Protokoll in den Persistent-Speicher bis zur ULOG-Aufzeichnung für diese Aktion geschrieben worden ist. Das HIGH-Attribut 1240 kann zu dieser Zeit mit der RLOG-LSN dieser Aufzeichnung fortgeschrieben werden, die, sollte ein Prüfpunkt genommen werden, die redundante Erzeugung einer Aufhebungsaufzeichnung während einer nachfolgenden Wiederherstellung reduzieren wird, sollte der aktuelle Wiederherstellungsprozeß scheitern.
Für jede Transaktion werden erzeugte Aufhebungsaufzeichnungen im ULOG-Puffer der Transaktion gespeichert. Diese Aufhebungsaufzeichnungen plus diejenigen auf ihren ULOG und ihren CLRs stellen sicher, daß eine aktive Transaktion zurückgerollt werden kann. Am Ende der Wiederhol- Phase werden daher alle notwendigen Aufhebung-Protokollaufzeichnungen existieren.

3. Die Aufhebung-Phase

Eine Aufhebung-Wiederherstellung ist N-Protokoll-artig. Die Aufhebung-Wiederherstellungsphase benötigt daher eine Parallelbetriebsteuerung in der gleichen Weise, die während eines Zurückrollens einer Transaktion notwendig ist. Mehrere Knoten können notwendig sein, um Änderungen am gleichen Block aufzuheben. Eine normale Datenbanktätigkeit kann wiederaufgenommen werden, wenn einmal die Aufhebung-Phase beginnt, ebenso wie eine normale Tätigkeit gleichzeitig mit einem Transaktionsabbruch weitergehen kann. Die ganze geeignete Verriegelung ist vor Ort, um dies zu gestatten. Dies wird sichergestellt, indem die Aufhebung-Phase nicht begonnen wird, bis alle Knoten die Wiederhol-Phase abgeschlossen haben. Alle durch irgendeinen Knoten während einer Wiederholung angeforderten Verriegelungen werden dann durch den geeigneten Knoten vor dem Beginn einer Aufhebung gehalten.
Zuerst werden alle aktiven Transaktionen (aber nicht vorbereiteten Transaktionen) in der Tabelle Aktive Transaktionen 1200 zurückgerollt. Die Aufhebungsverarbeitung geht mit einer Ausnahme exakt weiter wie beim expliziten Zurückrollen abgebrochener Transaktionen. Einige Aufhebungsaufzeichnungen könnten sowohl in einem Aufhebungspuffer, wo sie während einer Wiederholung regeneriert wurden, als auch in einem ULOG im Persistent-Speicher vorhanden sein. Diese doppelten Aufhebungsaufzeichnungen können festgestellt und ignoriert werden. Dies kann in einer Routine eingeschlossen werden, um die nächste Aufhebungsaufzeichnung zu erhalten, so daß der Rest des Codes für Aufhebungstransaktionen, die zum Zeitpunkt eines Absturzes aktiv sind, mit dem Code praktisch identisch sein kann, der benötigt wird, um eine Transaktion aufzuheben, wenn das System normal arbeitet. Redundante ULOG-Aufzeichnungen unter diesen Quellen können eliminiert werden, weil alle Aufhebungsaufzeichnungen durch die LSN der RLOG-Aufzeichnung identifiziert werden, auf die sie Anwendung finden.

V. SCHLUSSFOLGERUNG

Die Verwendung von Zustandsidentifizierern mit einer bekannten Sequenz liefert die oben angegebenen Vorteile. Zum Beispiel kann eine Wiederherstellung- und Protokollverwaltung effizient gestaltet werden, weil sich jeder Knoten von Systemabstürzen unabhängig erholen kann. Eine Medien- Wiederherstellung wird ebenfalls wegen der verbesserten Mischung der Archivprotokolle in einem einzigen Durchgang vorgenommen.
Die Zuordnung privater Protokolle für jeden Knoten fördert die Unabhängigkeit der Knoten und macht eine Protokollverwaltung für eine gemeinsame Datennutzung viel einfacher.
Dem Fachmann ist klar sein, daß Modifikationen und Variationen vorgenommen werden können, ohne vom Umfang dieser Erfindung abzuweichen, wie sie durch die beigefügten Ansprüche definiert ist. Zum Beispiel kann die in Figur 1 gezeigte Architektur verschieden sein, und die Anzahl von Aufhebung- und Wiederhol-Protokollen, die jedem Knoten zugeordnet sind, kann verschieden sein.

Claims

1. Verfahren zum Verwalten von Fortschreibungen für Information, die in einem nichtflüchtigen Speichermedium (140) in einem Computersystem (100) mit mehreren Knoten (110, 120, 130) und dem nichtflüchtigen Speichermedium gespeichert ist, wobei das Verfahren die folgenden Schritte aufweist:

Gewinnen einer Steuerung eines gewählten Abschnittes der mehreren Abschnitte (210, 220, 230) des nichtflüchtigen Speichermediums (140),

Aussieben eines ersten Zustandsidentifizierers (DSI), der dem gewählten Abschnitt zugeordnet ist, wobei der erste Zustandsidentifizierer einen Wert hat, der einem Zustand des gewählten Abschnittes vor einer Modifikation entspricht,

Wählen eines gewählten Protokolles (300) aus einer Vielzahl von Protokollen, wobei die Vielzahl von Protokollen Information (301, 302 ...) bezüglich an den mehreren Abschnitten vorzunehmenden Fortschreibungen haben, wobei das gewählte Protokoll einen zugeordneten zweiten Zustandsidentifizierer (BSI) hat, der dem ersten Zustandsidentifizierer (DSI) entspricht,

Fortschreiben von Information in dem gewählten Abschnitt gemäß einer in dem gewählten Protokoll angegebenen Aktion,

Modifizieren des ersten Zustandsidentifizierers (DSI) auf einen Wert entsprechend einem Zustand (ASI) des gewählten Abschnittes nach Fortschreibung gemäß der in dem gewählten Protokoll festgelegten Aktion, und

Freigeben einer Steuerung des gewählten Abschnittes.

2. Verfahren nach Anspruch 1, bei dem der Modifizierschritt weiterhin einen Schritt des Speicherns des modifizierten ersten Zustandsidentifizierers (ASI) in dem gewählten Abschnitt umfaßt.

3. Verfahren nach Anspruch 1, bei dem der Modifizierschritt weiterhin einen Schritt des Ableitens des modifizierten ersten Zustandsidentifizierers (ASI) aus einem unmodifizierten ersten Zustandsidentifizierer (BSI) umfaßt.

4. Verfahren nach Anspruch 3, bei dem der erste Zustandsidentifizierer (DSI) einen von mehreren Werten hat, die in einer bekannten Sequenz geordnet sind, und bei dem der Schritt des Ableitens des modifizierten ersten Zustandsidentifizierers weiterhin den folgenden Schritt umfaßt:

Wählen als ein Wert für den modifizierten ersten Zustandsidentifizierer von einem Wert, der ein folgender Wert in der bekannten Sequenz nach dem Wert des unmodifizierten ersten Zustandsidentifizierers ist.

5. Verfahren nach Anspruch 4, bei dem die bekannte Sequenz ein Satz von Null und den positiven ganzen Zahlen ist, die in einer monoton ansteigenden Reihe geordnet sind, und wobei der Modifizierschritt weiterhin den folgenden Schritt umfaßt:

Inkrementieren des ersten Zustandsidentifizierers um Eins, um den modifzierten Zustandsidentifizierer zu bilden.

6. Verfahren nach Anspruch 1, bei dem der Schritt des Gewinnens einer Steuerung die folgenden Schritte umfaßt:

Setzen einer Verriegelung auf den gewählten Abschnitt, um zu verhindern, daß der gewählte Abschnitt um den wenigstens einen Knoten gelesen wird, bis die Verriegelung entfernt ist und

Lesen einer Kopie des gewählten Abschnittes in einen Datenbasis-Cache (118) in einem ersten Knoten (110).

7. Verfahren nach Anspruch 3, bei dem der Schritt des Freigebens der Steuerung des gewählten Abschnittes den folgenden Schritt umfaßt:

Entfernen der Verriegelung von dem gewählten Abschnitt.

8. Verfahren nach Anspruch 6, bei dem das nichtflüchtige Speichermedium (140) eine Magnetplatte umfaßt, die in eine Vielzahl von Blöcken organisiert ist, und bei dem der Schritt des Lesens in den Datenbasis-Cache weiterhin den folgenden Schritt umfaßt:

Lesen eines gewählten Blockes (210) in den Datenbasis- Cache (118), wobei der Schritt des Fortschreibens des gewählten Abschnittes weiterhin den folgenden Schritt umfaßt:

Fortschreiben der Kopie des Blockes in den Datenbasis- Cache, um eine fortgeschriebene Kopie des Blockes zu liefern, und wobei der Schritt des Freigebens der Steuerung des gewählten Abschnittes weiterhin den folgenden Schritt umfaßt:

Schreiben der fortgeschriebenen Kopie des Blockes zurück in die Platte (140).

9. Verfahren nach Anspruch 8, weiterhin mit dem folgenden Schritt:

Schreiben des gewählten Protokolles auf die Platte (140) bevor die fortgeschriebene Kopie zurück auf die Platte geschrieben wird.

10. Verfahren nach Anspruch 1, bei dem der erste Zustandsidentifizierer (DSI) in dem gewählten Abschnitt (330; 210) gespeichert ist, und

wobei der Schritt des Aussiebens des ersten Zustandsidentifizierers weiterhin den folgenden Schritt umfaßt:

Lesen des ersten Zustandsidentifizierers aus dem gewählten Abschnitt.

11. Verfahren nach Anspruch 10, bei dem der Schritt des Modifizierens des ersten Zustandsidentifizierers weiterhin den folgenden Schritt umfaßt:

Speichern des modifizierten ersten Zustandsidentifizierers in dem fortgeschriebenen gewählten Abschnitt.

12. Verfahren nach Anspruch 1, bei dem das Computersystem weiterhin einen zweiten Knoten umfaßt und das Verfahren den folgenden Schritt aufweist:

Bestimmen, daß der Modifizierschritt und der Freigabeschritt abgeschlossen sind, bevor der gewählte Abschnitt zu dem zweiten Knoten übertragen wird.

13. Verfahren nach Anspruch 1, bei dem der Modifizierschritt weiterhin einen Schritt des Wählens des gewählten Protokolles in einer zeitlich geordneten Sequenz umfaßt.

14. Verfahren nach Anspruch 1, bei dem das Computersystem mehrere Knoten einschließlich eines ersten Knotens umfaßt, wobei jeder der mehreren Knoten wenigstens einem der mehreren Protokolle zugeordnet ist, und

bei dem der Schritt des Modifizierens des ersten Zustandsidentifizierers weiterhin den folgenden Schritt umfaßt:

Aufzeichnen des modifizierten ersten Zustandsidentifizierers in einem Teil von einem der mehreren Protokolle, die dem ersten Knoten zugeordnet sind.

15. Computersystem mit mehreren Knoten (110, 120, 130) und einem nichtflüchtigen Speichermedium (140) zum Verwalten von Fortschreibungen für in dem nichtflüchtigen Speichermedium gespeicherte Information, wobei das Computersystem aufweist:

eine Einrichtung zum Gewinnen einer Steuerung eines gewählten Abschnittes einer Vielzahl von Abschnitten (210, 220, 230) des nichtflüchtigen Speichermediums (140),

eine Einrichtung zum Aussieben eines dem gewählten Abschnitt zugeordneten ersten Zustandsidentifizierers (DSI), wobei der erste Zustandsidentifizierer einen Wert entsprechend einem Zustand des gewählten Abschnittes vor einer Modifikation hat,

eine Einrichtung zum Wählen eines gewählten Protokolles (300) aus einer Vielzahl von Protokollen, wobei die Vielzahl von Protokollen Information (301, 302, ...) bezüglich an der Vielzahl von Abschnitten vorzunehmenden Fortschreibungen hat, wobei das gewählte Protokoll einen zugeordneten zweiten Zustandsidentifizierer (BSI) entsprechend dem ersten Zustandsidentifizierer (DSI) hat,

eine Einrichtung zum Fortschreiben von Information in dem gewählten Abschnitt gemäß einer in dem gewählten Protokoll festgelegten Aktion,

eine Einrichtung zum Modifizieren des ersten Zustandsidentifizierers (DSI) auf einen Wert entsprechend einem Zustand (ASI) des gewählten Abschnittes, nachdem gemäß der in dem gewählten Protokoll festgelegten Aktion fortgeschrieben ist, und

eine Einrichtung zum Freigeben einer Steuerung des gewählten Abschnittes.

16. Computersystem nach Anspruch 15, bei dem die Einrichtung zum Modifizieren weiterhin eine Einrichtung zum Speichern des modifizierten ersten Zustandsidentifizierers (ASI) in dem gewählten Abschnitt umfaßt.

17. Computersystem nach Anspruch 15, bei dem die Einrichtung zum Modifizieren weiterhin eine Einrichtung zum Ableiten des modifizierten ersten Zustandsidentifizierers (ASI) aus einem unmodifizierten ersten Zustandsidentifizierer (BSI) umfaßt.

18. Computersystem nach Anspruch 17, bei dem der erste Zustandsidentifizierer (DSI) eine Vielzahl von Werten hat, die in einer bekannten Sequenz geordnet sind, und wobei die Einrichtung zum Ableiten des modifizierten ersten Zustandsidentifizierers außerdem umfaßt:

eine Einrichtung zum Wählen als Wert für den modifizierten ersten Zustandsidentifizierer von einem Wert, der ein folgender Wert in der bekannten Sequenz nach dem Wert des unmodifizierten ersten Zustandsidentifizierers ist.

19. Computersystem nach Anspruch 18, bei dem die bekannte Sequenz ein Satz von Null und den positiven ganzen Zahlen ist, die in einer monoton ansteigenden Reihe geordnet sind, und wobei die Einrichtung zum Modifizieren außerdem umfaßt:

eine Einrichtung zum Inkrementieren des unmodifizierten ersten Zustandsidentifizierers um Eins, um den modifizierten Zustandsidentifizierer zu bilden.

20. Computersystem nach Anspruch 15, bei dem die Einrichtung zum Gewinnen einer Steuerung außerdem umfaßt:

eine Einrichtung zum Setzen einer Verriegelung auf den gewählten Abschnitt, um zu verhindern, daß der gewählte Abschnitt mit Ausnahme des wenigstens einen Knotens gelesen wird, bis die Verriegelung entfernt ist, und

eine Einrichtung zum Lesen einer Kopie des gewählten Abschnittes in einen Datenbasis-Cache (118) in einem ersten Knoten (110).

21. Computersystem nach Anspruch 17, bei dem die Einrichtung zum Freigeben einer Steuerung des gewählten Abschnittes außerdem umfaßt:

eine Einrichtung zum Entfernen der Verriegelung von dem gewählten Abschnitt.

22. Computersystem nach Anspruch 20, bei dem das nichtflüchtige Speichermedium (140) eine Magnetplatte umfaßt, die in mehrere Blöcke organisiert ist, und wobei die Einrichtung zum Lesen des Datenbasis-Cache außerdem umfaßt:

eine Einrichtung zum Lesen eines gewählten Blockes (210) in den Datenbasis-Cache (118), wobei die Einrichtung zum Fortschreiben des gewählten Abschnittes außerdem umfaßt:

eine Einrichtung zum Fortschreiben der Kopie des Blockes in den Datenbasis-Cache, um eine fortgeschriebene Kopie des Blockes zu liefern, und wobei die Einrichtung zum Freigeben einer Steuerung des gewählten Abschnittes außerdem aufweist:

eine Einrichtung zum Schreiben der fortgeschriebenen Kopie des Blockes zurück in die Platte (140).

23. Computersystem nach Anspruch 22, weiterhin umfassend:

eine Einrichtung zum Schreiben des gewählten Protokolles auf die Platte (140), bevor die fortgeschriebene Kopie zurück auf die Platte geschrieben wird.

24. Computersystem nach Anspruch 15, bei dem der erste Zustandsidentifizierer (DSI) in dem gewählten Abschnitt (330, 210) gespeichert ist, und

wobei die Einrichtung zum Aussieben des ersten Zustandsidentifizierers außerdem aufweist:

eine Einrichtung zum Lesen des ersten Zustandsidentifizierers aus dem gewählten Abschnitt.

25. Computersystem nach Anspruch 24, bei dem die Einrichtung zum Modifizieren des ersten Zustandsidentifizierers außerdem aufweist:

eine Einrichtung zum Speichern des modifizierten ersten Zustandsidentifizierers in dem fortgeschriebenen gewählten Abschnitt.

26. Computersystem nach Anspruch 15, bei dem das Computersystem außerdem einen zweiten Knoten umfaßt und das Computersystem-Verfahren weiterhin aufweist:

eine Einrichtung zum Bestimmen, daß die Einrichtung zum Modifizieren und die Einrichtung zum Freigeben abgeschlossen sind, bevor der gewählte Abschnitt zu dem zweiten Knoten übertragen wird.

27. Computersystem nach Anspruch 15, bei dem die Einrichtung zum Modifizieren außerdem eine Einrichtung zum Wählen des gewählten Protokolles in einer zeitlich geordneten Sequenz umfaßt.

28. Computersystem nach Anspruch 15, bei dem das Computersystem mehrere Knoten einschließlich eines ersten Knotens umfaßt, wobei jeder der mehreren Knoten wenigstens einem der mehreren Protokolle zugeordnet ist, und

wobei die Einrichtung zum Modifizieren des ersten Zustandsidentifizierers außerdem aufweist:

eine Einrichtung zum Aufzeichnen des modifizierten ersten Zustandsidentifizierers in einem Teil von einem der mehreren Protokolle, die dem ersten Knoten zugeordnet sind.