DE3784190T2

DE3784190T2 - Eintragung eines datenbasisindex in das journal zur verbesserten rueckstellung.

Info

Publication number: DE3784190T2
Application number: DE8787107665T
Authority: DE
Inventors: Dennis Steven Delorme; Mark Larry Holm; Wilson Douglas Lee; Peter Bernard Passe; Gary Ross Ricard; Timms, Jr; Larry William Youngren
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1986-06-13
Filing date: 1987-05-26
Publication date: 1993-08-19
Anticipated expiration: 2007-05-27
Also published as: US4819156A; EP0249090A2; EP0249090B1; DE3784190D1; JPS62297950A; EP0249090A3

Description

Die Erfindung bezieht sich auf die Fehlerbehebung in Computer- Systemen und im besonderen auf die Synchronisation von Datenbankindizes mit den Datenräumen, die sie abdecken.
Datenbanken können aus Datenräumen gebildet werden, die Datenraumeintragungen oder -aufzeichnungen und Datenbankindizes umfassen, die geordnete Listen der Datenraumeintragungen liefern, die auf Ordnungswerten beruhen, die in den Datenraumeintragungen enthalten sind. Wenn an den Eintragungen in einem Datenraum oder in mehreren Datenräumen Veränderungen vorgenommen werden, dann kann sich die Notwendigkeit ergeben, daß die Datenbankindizes über den Datenraum aktualisiert werden, damit die Indizes in Bezug auf die Datenräume, die sie abdecken, synchron bleiben. Beim IBM-System/38 werden die Veränderungen am Datenbankindex/ an den Datenbankindizes zuerst durchgeführt, dann folgen die Veränderungen am Datenraum. Diese Reihenfolge der Veränderungen ist gewählt worden, damit allen beliebigen Bedingungen Rechnung getragen wird, die die Aktualisierung der Datenbankindizes zur Oberfläche verhindern könnten, ehe ein Datenraum verändert wird. Der Versuch, einen doppelten Ordnungswert in einen eindeutigen Index einzusetzen, ist eine solche Bedingung.
Wenn ein System nicht normal beendet wird, dann können die Datenräume und die dazugehörigen Datenbankindizes nicht synchronisiert werden. Einige Arbeitsvorgänge können dazu geführt haben, daß der Datenbankindex/die Datenbankindizes aktualisiert werden sollen, aber zu dem Zeitpunkt, an dem das System beendet wird, sind die dazugehörigen Datenraumeintragungen nicht aktualisiert worden. Um die Angelegenheit noch weiter zu erschweren, soll in einer virtuellen Speicherumgebung mit Seitenaustausch die Seitenaustauschroutine die geänderten Seiten entweder für den Datenraum oder für den/die dazugehörigen Datenbankindex /-indizes nicht in einen nichtflüchtigen Speicher eingeschrieben haben, oder sie soll zum Zeitpunkt des Ausfalls nur einige der veränderten Seiten entweder für den Datenraum oder für den/die Datenbankindex/-indizes in den nichtflüchtigen Speicher eingeschrieben haben. Wenn nur einige, aber nicht alle geänderten Seiten für einen Datenbankindex vor Eintritt der abnormalen Beendigung in den nichtflüchtigen Speicher eingeschrieben wurden, dann kann die logische Struktur des Indexes, der nach der Beendigung aus dem nichtflüchtigen Speicher noch verfügbar ist, derart uneinheitlich sein, daß sie sogar die Verwendung des Indexes als Ausgangspunkt für eine Vorwärtswiederherstellung (unter Verwendung eines Protokolls der Veränderungen der Datenraumeintragungen) ausschließt.
Die Journalführung bei Arbeitsvorgängen, die eine Veränderung in einer Datenbank verursachen, ist bekannter Stand der Technik. Die US-Patentschrift Nr. 4,507,751 beschreibt eine Rechneranordnung und -methode zur Führung eines Eintragungsprotokolls. Die Rechneranordnung umfaßt einen flüchtigen Speicher zur Speicherung eines Protokollpuffers und einen nichtflüchtigen Speicher für die Speicherung eines Eintragungsprotokolls. Für die Einspeicherung einer Vielzahl von kurzen Datenblöcken in einem Vorwärtsschreibdatensatz werden nichtflüchtige Speichermittel zur Verfügung gestellt. Die Inhalte des Protokollspeichers werden entsprechend einer vor der Füllung des Protokollspeichers liegenden Prozeßzeitspanne in den Vorwärtsschreibdatensatz eingeschrieben. Die Inhalte der Protokollspeicher werden entsprechend der Ablage der Protokollspeicher in das Eintragungsprotokoll eingeschrieben. Die erneute Durchführung oder das Rückgängigmachen von Datenbankveränderungen wird mit Bezug auf den Vorwärtsschreibdatensatz nur in dem Falle realisiert, wenn ein Systemfehler zum Verlust der noch nicht im Eintragungsprotokoll eingeschriebenen Protokollpufferdaten führt; anderenfalls werden Datenbankveränderungen mit Bezug auf den Protokollpuffer oder das Eintragungsprotokoll erneut realisiert oder rückgängig gemacht.
Bei Haerder, "Principles of Transaction-Oriented Recovery" (Prinzipien einer dialogorientierten Wiederherstellung), Computing Surveys, Bd. 15, Nr. 4 vom Dezember 1983, Verhofstad, "Recovery Techniques for Database Systems" (Technologien der Wiederherstellung für Datenbanksysteme), Computing Surveys, Bd. 10, Nr. 2 vom Juni 1978 und Gray, "The Recovery Manager of the System R Database Manager" (Der Wiederherstellungsmanager des Datenbankmanagers System R), Computing Surveys, Bd. 13, Nr. 2 vom Juni 1981 wird ebenfalls die Eintragung von Arbeitsvorgängen beschrieben, die zu einer Veränderung in einer Datenbank führen.
Alle diese Quellenangaben befassen sich jedoch nicht mit der wirksamen Wiederherstellung von Datenbankindizes, die sich auf Datenräume beziehen.
Die Führung von Eintragungen für Dialogvorgänge mit einer Datenbank funktioniert sehr wohl für die Wiederherstellung des Datenraumes, weil es dabei nur notwendig ist, das Abbild jeder Datenraumeintragung vor und nach jeder Veränderung in das Journal aufzunehmen. Jede Eintragung im Datenraum wird an einer festen Position innerhalb des Datenraumes lokalisiert, damit werden einige wenige Seiten geändert, wenn eine Datenraumeintragung aktualisiert wird.
Die Europäische Patentschrift EP-A-0118 861 beschreibt ein Textverarbeitungssystem, bei dem ein Textstrom zum Wiederaufruf und zur Edierung in einer Direktzugriffsspeicher-Einrichtung (DASD) gespeichert wird. Der Textstrom wird in ein Dokument eingeordnet, das in der DASD als Datensatz gespeichert wird. Der Datensatz besteht aus einem Index-Teil und einem Teil, der die Textaufzeichnungen enthält. Der Index-Teil ist in Knoten unterteilt, von denen der primäre Knoten auch Wurzelknoten genannt wird. Die zusätzliche Aufzeichnung von kritischen Indexknoten schützt diejenigen Indexknoten, deren Verlust für den Systembediener einen bedeutenden Datenverlust ergeben würde.
Die Eintragung von Veränderungen an den Datenbankindizes, die sich auf einen Datenraum beziehen, ist komplexer, da eine Veränderung an einer einzelnen Eintragung in einem Index in Abhängigkeit von der für den Index verwendeten Datenstruktur Veränderungen in vielen logischen Seiten in dem Index erforderlich machen kann. Viele häufig angewandte Indexstrukturen, wie etwa binäre Basiszahlenbäume und B-Bäume, haben die Eigenschaft, daß eine Veränderung an einer einzelnen Eintragung Veränderungen erforderlich machen kann, die über viele logische Seiten des Index verteilt sein können. Eine Lösungsmethode für die Eintragung aller Veränderungen an einem Datenbankindex kann es erforderlich machen, daß so viele Seiten für jede Veränderung einer Datenraumeintragung aufgezeichnet werden müßten, daß diese Technologie aufgrund der sehr großen Speicheranforderungen für das Journal nicht benutzt werden kann oder daß die Betriebskosten der erforderlichen Eintragungsaktivitäten ein Hinderungsgrund wären.
Die einfachste Methode für die Wiederherstellung von Datenbankindizes nach einer Störung, bei der der Zustand der Indizes ungewiß geblieben ist, besteht darin, jede Eintragung in jedem Datenraum, der von jedem Datenbankindex abgedeckt wird, zu lesen und den gesamten Index aus den Datenraumeintragungen wieder aufzubauen. Dieses Verfahren kann aufgrund der erforderlichen Anzahl der Eingabe-/Ausgabevorgänge des Hilfsspeichers und der Indexvorgänge außerordentlich zeitaufwendig sein. In einigen Fällen ist die für die Wiederherstellung der Datenbankindizes für einen oder mehrere große Datenräume notwendige Zeit in der Größenordnung von Tagen zu messen.
Der grundlegende Gegenstand der vorliegenden Erfindung besteht darin, eine Methode für die Eintragung von Indizes gemäß dem Anspruch 1 zur Verfügung zu stellen.
Eine schnelle Wiederherstellung eines Datenbankindex wird dadurch realisiert, daß die unveränderten Indexseiten (einmal) vor der erstmaligen Veränderung der Seiten eingetragen werden und daß auch die Dialogvorgänge eingetragen werden, die aus geänderten und nicht geänderten Abbildern von Datenraumeintragungen für alle vom Index abgedeckten Datenräume bestehen.
Zur Wiederherstellung des Datenbankindex wird der Index zuerst in seinem ursprünglichen Zustand wiederhergestellt, indem man das Abbild der unveränderten Seiten aus dem Journal auf den Index kopiert. Der Index wird dann dadurch aktualisiert, daß die Indexveränderungen neu bearbeitet werden, die mit allen eingetragenen Veränderungen für Eintragungen im Datenraum/in den Datenräumen, die von dem Index abgedeckt werden, verbunden sind. Das unveränderte Abbild jeder Datenraumeintragung ist dafür notwendig, daß die dazugehörige Eintragung in dem ursprünglichen Datenbankindex ermittelt werden kann. Das Abbild der veränderten Datenraumeintragung wird dazu benutzt, die aktualisierte Indexeintragungsinformation zu liefern und ebenso den Datenraum dadurch wiederherzustellen, daß die geänderte Eintragung aus dem Journal auf den Datenraum kopiert wird (für alle veränderten Datenraumeintragungen, die vor der Beendigung nicht in einen nichtflüchtigen Speicher eingeschrieben werden konnten). Nach dem Abschluß dieser Vorgänge sind sowohl der Datenbankindex wie auch der Datenraum auf dem aktuellen Stand, und der Datenbankindex ist mit dem Datenraum/den Datenräumen, die er abdeckt, synchron.
im Anspruch 2 wird eine Eintragungseinrichtung belegt, die die mit Anspruch 1 belegte Methode ausführt.
Fig. 1 ist ein Blockschaltbild der im Hauptspeicher dafür benutzten Bereiche, die Eintragung von logischen Dateien gemäß der vorliegenden Erfindung zu realisieren.
Fig. 2 ist ein allgemeines Flußdiagramm der für die Erzeugung eines Klons der logischen Datei erforderlichen Schritte.
Fig. 3 bis 5 stellen Seiten eines Indexes dar, die zur Beschreibung der Eintragungsfunktionen von Fig. 1 und Fig. 2 benutzt werden.
Fig. 6a bis f sind ein allgemeines Flußdiagramm der Indexeintragung der Fig. 1.
Fig. 7a bis d sind ein Flußdiagramm für die Wiederherstellung von Indizes und Datenräumen.
Fig. 8 ist ein Diagramm der aufeinanderfolgenden Zustände eines mehrfachen Ringpuffers zur Speicherung von unberührten Seitenabbildungen aus den eingetragenen logischen Dateien.
Fig. 9 ist ein Flußdiagramm für die Ablage von unberührten Indexabbildungen in dem Ringpuffer.
In der bevorzugten Ausführung der vorliegenden Erfindung umfassen die Datenbankindizes Indizes von binären Basiszahlenbäumen, die über Datenräume definiert sind. Die Eintragung von unveränderten Indexseiten ist für andere Ausführungen von Datenbankindizes, wie etwa für B-Bäume, ebenso vorteilhaft. Es wird ein Vorwärtsschreibjournal benutzt, um alle Veränderungen an einem Datenraum widerzuspiegeln, ehe die Datenraumeintragungen auch wirklich verändert werden. Es wird nicht zugelassen, daß veränderte Indexseiten in den Hilfsspeicher eingeschrieben werden, ehe nicht ihre entsprechenden unveränderten Seitenabbildungen in ein Journal in dem Hilfsspeicher eingeschrieben worden sind. So enthält das Journal am Hilfsspeicher immer Informationen, die mit den aktuellsten Veränderungen an den darin eingetragenen Datenbankindizes und Datenräumen korrespondieren, und zwar bevor die Indizes und die Datenräume am Hilfsspeicher verändert werden.
In einer weiteren bevorzugten Ausführung werden die unveränderten Datenbankindexseiten in einen Puffer im Hauptspeicher kopiert, ehe sie in das Journal am Hilfsspeicher eingetragen werden. Der Puffer im Hauptspeicher muß nicht zwangsläufig in den Hilfsspeicher eingeschrieben werden, ehe nicht alle unveränderten Datenbankindexseiten und die veränderten und unveränderten Datenraumeintragungsänderungen dem Puffer hinzugefügt worden sind. Die Möglichkeit der Sammlung der Journalinformationen in einem Puffer des Hauptspeichers setzt die Anzahl der Eingabe/Ausgabevorgänge herab, die zum Einschreiben der Information in den Hilfsspeicher notwendig sind, wodurch die Leistungsfähigkeit verbessert wird. Weil diese Verfahrensweise es zuläßt, daß die Datenbankindexseiten im Hauptspeicher verändert werden, ehe die unveränderten Indexseiten in das Journal im Hilfsspeicher eingeschrieben werden, muß man einen Sicherungsmechanismus vorsehen, damit der Schreibvorgang/die Schreibvorgänge für das Journal vollständig abgeschlossen sind, ehe der Schreibvorgang/die Schreibvorgänge für den Datenbankindex/die Datenbankindizes begonnen werden.
Bei der Vorzugsvariante befinden sich die Datenbankindizes, die Datenräume und die Eintragungen auf Seiten in einer virtuellen Speicherumgebung. Wenn eine Seite aus einem virtuellen Speicher im Hauptspeicher festgehalten wird, dann läßt es der Speicherverwaltungsmechanismus des Systems nicht zu, die Seite in den Hilfsspeicher einzuschreiben oder die Hauptspeicherkachel einer unterschiedlichen virtuellen Seite neu zuzuordnen. Die Schreibvorgänge in den Hilfsspeicher werden in eine Reihenfolge gebracht, indem beliebige Seiten in einem Datenbankindex von genau dem Zeitpunkt an, ehe die Seite zum ersten Mal (im Hauptspeicher) geändert wird bis nach dem Einschreiben des unveränderten Seitenabbildes in das Journal am Hilfsspeicher festgehalten werden. Es sind auch andere Mechanismen möglich, um die Aktualisierung der Journaleintragungen vor dem Datenbankindex im Hilfsspeicher sicherzustellen, und solche Mechanismen gehören zum Umfang der vorliegenden Erfindung.
Ein Eintragungssynchronpunkt ist eine Markierung oder ein Zeiger, der mit einem speziellen eingetragenen Datenbankindex oder Datenraum verbunden ist und der die älteste Eintragung in das Journal identifiziert, die zur Wiederherstellung des damit verbundenen eingetragenen Objektes nach einer abnormalen Beendigung notwendig ist. Jeder eingetragene Datenbankindex und Datenraum hat seinen eigenen Synchronpunkt. Der Synchronpunkt kann als die Position innerhalb des Journals angesehen werden, die der letzten (jüngsten) Zeit entspricht, zu der der eingetragene Datenbankindex oder Datenraum auf dem Hilfsspeicher mit einem vollständig zuverlässigen und folgerichtigen Zustand bekannt war. Der Synchronpunkt für ein eingetragenes Objekt wird mit Bezug auf eine unterschiedliche Journaleintragung immer dann aktualisiert, wenn alle davon abhängigen Veränderungen für das Objekt (Datenbankindex oder Datenraum) zwangsläufig vom Hauptspeicher in den Hilfsspeicher eingeschrieben werden.
Die Wiederherstellung eines eingetragenen Datenbankindex nach einer abnormalen Beendigung vertraut auf die Fähigkeit, den Index zu einem ziemlich vollständigen folgerichtigen Zustand zurückzuführen und dann die Veränderung neu abzuarbeiten und den Index damit hinsichtlich der von ihm abgedeckten Datenräume wieder zu aktualisieren. Da der Eintragungssynchronpunkt für einen Datenbankindex einen Punkt identifiziert, an dem der Index in einem folgerichtigen Zustand ist, muß der Wiederherstellungsprozeß den Zustand eines Index zu dem Zeitpunkt wiederherstellen, wenn der damit verbundene Eintragungssynchronpunkt das letzte Mal aktualisiert wurde. Das Journal muß wenigstens die unveränderten Abbildungen jeder Seite des Datenbankindex enthalten, die entsprechend einer Änderung in einem der Datenräume, die der Index abdeckt, geändert wurde, damit der Index zu seinem Zustand am letzten Synchronpunkt zurückgeführt werden kann.
Bei der Vorzugsvariante werden nur die Abbilder der ungeänderten Seiten des Datenbankindex im Journal gesichert. Wenn einmal das Abbild einer ungeänderten Seite in einem Datenbankindex dem Journal hinzugefügt worden ist, dann sind für diese Seite keine zusätzlichen Journaleintragungen erforderlich, bis die nächste Aktualisierung des Synchronpunktes abgelaufen ist, dabei ist es gleichgültig, wie viele Male eine einzelne Seite aktualisiert wird. Daher besteht keine Notwendigkeit, wenn an den gleichen Seiten des Datenbankindex mehrfache Veränderungen zwischen den Synchronpunktaktualisierungen aufgetreten sind, den Inhalt der Indexseiten, die umfassende und redundante Veränderungen enthalten können, zu erfassen und zu sichern. Es sind auch andere Technologien möglich, wie etwa die Sicherung jedes Abbildes jeder Datenbankindexseite vor jeder Veränderung. Die Vorzugsvariante reduziert die Anzahl der Eingabe-/Ausgabevorgänge des Hilfsspeichers und den erforderlichen Hilfsspeicherraum, wenn mehrfache Veränderungen an der/den gleichen Seite/Seiten des Datenbankindex zwischen den Aktualisierungen des Synchronpunktes vorgenommen worden sind.
Es ist ein Mechanismus erforderlich, der die seit dem letzten Synchronpunkt unverändert gebliebenen Seiten aufzeichnet und der auch aufzeichnet, welche Seiten ihre unveränderten Abbilder bereits eingetragen bekommen haben, ehe sie verändert worden sind. In der bevorzugten Ausführung ist mit dem Datenbankindex eine Bitabbildung verbunden, die der Bestimmung der Seiten dient, die seit der letzten Aktualisierung des Synchronpunktes eingetragen und verändert worden sind. Jedes Bit in der Abbildung stellt eine einzelne logische Seite in dem Index dar, und es gibt jeweils eine getrennte Bitabbildung für jeden eingetragenen Datenbankindex. Alle Bits in der Darstellung für einen eingetragenen Index werden gelöscht (auf Null gesetzt), wenn der Synchronpunkt des Index aktualisiert wird. Das unveränderte Abbild einer Datenbankindexseite, die seit der letzten Aktualisierung des Synchronpunktes nicht verändert worden ist, wird als ein "unberührtes" Seitenabbild bezeichnet. Bevor eine Seite in dem Index geändert wird, wird das entsprechende Bit daraufhin geprüft, ob die Seite noch eine unberührte Seite ist. Wenn das Bit rückgestellt worden ist (auf Null), dann wird das unberührte Abbild der Seite dem Journal hinzugefügt, wenn das Bit gesetzt worden ist (auf Eins), dann wird die Seite im Hauptspeicher festgehalten, und dann wird die Seite geändert. Wenn das Bit schon gesetzt ist (auf Eins), wenn eine Seite geändert werden muß, dann wird die Seite gerade aktualisiert (ohne sie in den Hauptspeicher einzutragen oder dort festzuhalten). Zur Unterscheidung zwischen unberührten Seiten und Indexseiten, die seit dem letzten Synchronpunkt geändert worden sind, sind auch andere Methoden möglich.
In einer anderen bevorzugten Ausführung wird eine Liste aller der Seiten des Datenbankindex, die gerade festgehalten werden, aktualisiert, damit man jederzeit, wenn eine Indexseite festgehalten wird (bevor sie im Hauptspeicher aktualisiert wird), eine Eintragung hinzufügen kann. Nachdem dem Journal unveränderte und veränderte Abbildungen der dazugehörigen Datenraumeintragung zugefügt worden sind und die Eintragungen zwangsläufig in den Hilfsspeicher eingeschrieben worden sind, werden alle Seiten in der Liste freigegeben (wodurch die Seiten mit Hilfe der Führungsmittel des Systemspeichers in den Hilfsspeicher eingeschrieben werden können), und alle Eintragungen werden aus der Liste der festgehaltenen Seiten entfernt.
Der Eintragungssynchronpunkt für einen Datenbankindex wird gelegentlich aktualisiert, damit die Anzahl der Journaleintragungen begrenzt wird, die zur Wiederherstellung nach einer abnormalen Beendigung benutzt werden müssen. Je mehr Journaleintragungen zwischen den Aktualisierungen der Synchronpunkte für die Datenbankindizes zugelassen werden, desto mehr Journaleintragungen müßten nach einer abnormalen Beendigung aus dem Hilfsspeicher gelesen und bearbeitet werden und desto länger würde die Wiederherstellung dauern. In der bevorzugten Ausführung ist ein Parameter vorgesehen, mit dem der Nutzer der Datenbank steuern kann, wie häufig die Synchronpunkte für Datenbankindizes zu aktualisieren sind.
Bei der Wiederherstellung von Datenbankindizes und Datenräumen werden die geeigneten Journaleintragungen, die nach den Synchronpunkten für jedes Objekt erscheinen, auf die Indizes und die Datenräume angewandt. Die Synchronpunkte für Indizes müssen nicht die gleichen wie für Datenräume sein. Dies ist insofern günstig, weil das System dadurch in die Lage versetzt wird, das gleichzeitige Einschreiben aller veränderten Seiten für die Datenbankenindizes und die Datenräume, die sie abdecken, zu vermeiden. Die für das Einschreiben mehrfacher Objekte in den Hilfsspeicher erforderlichen Eingabe-/Ausgabevorgänge könnten für den Rest des Systems gravierende Leistungseinbußen nach sich ziehen. Es müssen nicht alle Objekte innerhalb eines Satzes von Datenbankindizes und die Datenräume, die sie abdecken, übereinstimmend synchronisiert (eingeschrieben im Hilfsspeicher) sein, damit man ein beliebiges Objekt synchronisiert.
Zur Wiederherstellung eines Datenraumes oder -indexes werden die Eintragungen im Journal (erzeugt im Dialog mit der durch Eintragungen zu belegenden Datenbank) seit dem letzten Synchronpunkt bei jedem Objekt auf den entsprechenden Datenraum oder -index angewandt. Der erste Schritt besteht in der Anwendung aller eingetragenen unberührten Abbilder auf den Datenbankindex, damit der Index in den folgerichtigen Zustand zurückkehrt, der am letzten Synchronpunkt existierte. Der nächste Schritt besteht in der Anwendung aller eingetragenen Veränderungen auf den Datenraum/die Datenräume und in der Aufzeichnung der Indexveränderungen, die erforderlich sein werden, um den Datenbankindex/ die Datenbankindizes auf den aktuellen Stand zu bringen. Der letzte Schritt besteht darin, die aufgezeichneten Veränderungen auf den Index anzuwenden, wodurch der Index von seinem Zustand am letzten Synchronpunkt zu dem Zustand aktualisiert wird, der der letzten (neuesten) Eintragung in das Journal entspricht.
In der bevorzugten Ausführung laufen die ersten beiden Schritte in einem einzigen Durchlauf ab, der die Journaleintragungen liest und verarbeitet. Der Index wird nicht bis zur Verarbeitung aller eingetragenen unberührten Seitenabbilder in seinem Zustand beim letzten Synchronpunkt neu gespeichert, sondern das System kann mit Hilfe der Aufzeichnungstechnologie die Bezugnahme auf den Index so verzögern, daß die Eintragungen aktualisiert, entfernt oder verändert werden können, bis er vollständig mit seinem Zustand beim letzten Synchronpunkt neu gespeichert worden ist.
Wenn bei einem gegebenen Dialog eine große Anzahl von Seiten in einem Index geändert werden soll, dann wird von dem Index ein Klon oder Duplikat auf dem Hilfsspeicher erzeugt, damit das Journal nicht zu voll wird. In dem Journal wird eine Eintragung hinzugefügt, und der Synchronpunkt für den Index wird aktualisiert, wenn der Klon erzeugt worden ist. In diesem Falle ist es nicht notwendig, den ursprünglichen Datenbankindex in den Hilfsspeicher einzuschreiben, wenn der Synchronpunkt aktualisiert wird. Anstelle dessen wird der Klon in den Hilfsspeicher eingeschrieben. Wenn eine abnormale Beendigung erfolgt, dann wird der Klon zur neuen Speicherung des Index in seinem Zustand am letzten Synchronpunkt verwendet. Die Wiederherstellung erfolgt dann in der gleichen Art wie oben beschrieben, nachdem der Indexzustand am letzten Synchronpunkt aus dem Klon neu gespeichert worden ist. Der Klon wird zerstört, wenn der Dialog beendet ist.
Ein Beispiel für einen Vorgang, der von einem Klonen profitieren würde, ist dann gegeben, wenn die gesamten Eintragungen in einen Datenraum physikalisch reorganisiert (neu geordnet) werden müssen. Dieser Vorgang erfordert es, daß jeder Ordnungsbegriff in dem Datenbankindex verändert werden muß, damit er den neuen Standort jeder Aufzeichnung widerspiegelt. Durch das Klonen steht eine Methode zum Erfassen der unberührten Abbilder vor der Neuorganisation zur Verfügung, ohne daß jede Veränderung bei ihrem Auftreten eingetragen wird.
Ein Eintragungsmechanismus für einen Datenbankindex ist bei 10 in Fig. 1 ganz allgemein dargestellt. Der Mechanismus 10 umfaßt einen Hauptspeicherbereich 12 zur Speicherung von Datenseiten. In der bevorzugten Ausführung umfassen die Datenseiten 512-Byte- Datenseiten, die in den flüchtigen Hauptspeicher 12 hinein und aus diesem wieder heraus mit Hilfe eines Prozessors 14 übertragen werden, der eine Seitenaustauschroutine nach bekanntem Stand der Technik umfaßt. Die Seiten werden in den nichtflüchtigen Hilfsspeichereinheiten 16, 18, 20 und 22 gespeichert, die gewöhnlich Diskettenlaufwerkseinrichtungen sind.
Die im Hauptspeicher 12 und auf den Diskettenlaufwerken 16 bis 22 befindlichen Daten umfassen eine Vielzahl von Datenbanken, die aus einer Kombination von Datenräumen und logischen Dateien bestehen. Die logischen Dateien, die in der bevorzugten Ausführung als Indizes realisiert sind, liefern unterschiedliche Ansichten der Datenräume. Die Datenräume und die logischen Dateien werden beide auch als Objekte angesehen. Die Datenraumseiten, die sich im Hauptspeicher 12 befinden, werden bei 24 dargestellt. Obwohl sie bildlich in einem Block dargestellt sind, befinden sie sich physikalisch auf mehreren Seiten des Hauptspeichers 12. Gleicherweise umfassen die durch Block 26 dargestellten Indexseiten mehrere Seiten des Hauptspeichers.
Die Indexseiten 26 enthalten Ordnungsbegriffe, die sich auf Daten in den Datenraumseiten 24 beziehen. In der bevorzugten Ausführung sind die Ordnungsbegriffe in Form eines binären Basiszahlenbaumes organisiert. Einige Beispiele für die Ordnungsbegriffe werden nachstehend erläutert. Weitere Informationen über Ordnungsbegriffe und binäre Basiszahlenbäume finden sich bei Howard und Borgendale, "System/38 Machine Indexing Support" (Maschinelle Indexierhilfe beim System /38), IBM System/38 Technical Developments, 1978, (IBM Form G580-0237). Eine Seitenadressierung ist zwischen den Datenraumsseiten 24 und den Indexseiten 26 über einen Adressierungsblock 28 für Ordnungsbegriffe vorgesehen, der die für die Umformung von Daten aus einem Verzeichnis in dem Datenraum in einen entsprechenden Ordnungsbegriff in dem Index notwendige Information enthält.
In einem Eintragungspuffer 30 werden Kopien von Änderungen gepuffert, die an den Datenraumseiten durchgeführt werden sollen. Vor der Durchführung der Änderungen an den Datenraumseiten werden die eingetragenen Änderungen im Puffer in einen Hilfsspeicher 16 bis 22 überschrieben. Dies ist allgemein bekannt als Vorwärtsschreibjournal.
Immer dann, wenn ein eingetragener Datenraum forciert wird (zwangsweise in seiner Gesamtheit in den Hilfsspeicher eingeschrieben werden soll), dann wird in der Eintragung für diesen Datenraum ein Synchronpunkt markiert. Ein Synchronpunkt ist ein Kennzeichen, das einen Zeitpunkt darstellt, bei dem alle früher geänderten Seiten des mit Einträgen belegten Objektes aus dem flüchtigen Hauptspeicher in einen nichtflüchtigen Hilfsspeicher eingeschrieben worden sind.
Jedesmal, wenn ein neuer Synchronpunkt eingerichtet wird, kann der Mechanismus für das Wiederherstellungsverfahren die Bearbeitungszeit begrenzen, indem er alle früher eingetragenen Ablagen hinsichtlich des synchronisierten Objektes vernachlässigt. Folglich stellt dieser Mechanismus sicher, daß im Falle eines Systemabbruchs die jüngsten Eintragungen in die Datenraumseiten wiederhergestellt werden können, indem man nur die eingetragenen Abbilder benutzt, die nach dem Synchronpunkt aufgezeichnet worden sind.
Zusätzlich zur Eintragung der Veränderungen an den Datenraumseiten wird vor der Veränderung der Indexseiten eine Kopie der zu ändernden Indexseiten eingetragen. Die zu ändernden Seiten werden wie folgt identifiziert. Jeder Indexiervorgang, der einen Index verändert (entweder eine Ergänzung oder eine Löschung) liefert einen Ordnungsbegriff, der eingefügt oder gelöscht werden soll. Dieser Ordnungsbegriff wird zur Suche nach dem Index benutzt, damit der Änderungspunkt im Index gefunden wird. Damit werden nach einer ersten Indexsuche die Seite/Seiten ermittelt, die sich als Folge einer Datenraumänderung ändert/ändern. Die Eintragung der Veränderungen wird begleitet von der Einsendung des Seitenabbildes in das Journal, falls es ein unberührtes Abbild ist.
Die Tatsache, daß eine Indexseite eingetragen worden ist, wird in einem Bitabbild 32 angezeigt, das eine getrennte Unterscheidungs-Bitposition für jede Indexseite enthält. Falls an der Indexseite mehrere Veränderungen durchgeführt werden sollen, ehe für die Indexseite der Synchronpunkt eintritt, wird die entsprechende Bitposition in dem Bitabbild 32 geprüft. Wenn das Bit gesetzt ist, dann werden die Indexveränderungen durchgeführt, ohne daß die Indexseite wieder eingetragen wird.
Veränderte Indexseiten, die seit dem letzten Synchronpunkt noch nicht eingetragen worden sind, werden in einer Liste für festgehaltene Seiten 34 festgehalten und belegt. Die Seite wird festgehalten, ehe die unberührte Indexseite an den Eintragungspuffer 30 übermittelt wird. Das Vorhandensein dieses Festhaltemechanismus verhindert es, daß die Seite durch normale Seiteneinteilungsfunktionen für virtuelle Speicher herausgeschrieben wird. Nachdem die Seite an den Eintragungspuffer 30 übermittelt worden ist, werden die Veränderungen an den Indexseiten durchgeführt.
Die Veränderungen an den Datenräumen werden am Eintragungspuffer 30 widergespiegelt und werden dann synchron über eine Speicherführungsfunktion in den Hilfsspeicher eingeschrieben. Die unberührten Indexseiten werden ebenfalls zur gleichen Zeit überschrieben. Bei den Veränderungen an den Datenräumen werden sie huckepack zum Hilfsspeicher mitgenommen. Auf diese Weise werden die beiden Arten von Eintragungsablagen in einem einzigen Byte- Paket gebündelt, und somit gibt es keine zusätzlichen Eingabe/Ausgabevorgänge für die Eintragung des Index neben denjenigen, die für die Eintragung des Datenraumes allein erforderlich sind.
Die Festhaltemechanismen für die nunmehr geänderten unberührten Indexseiten (die Liste 34 für die festgehaltenen Seiten wird zur Identifikation dieser Seiten benutzt) werden über eine Abfrage an die Speicherverwaltung entriegelt. Dadurch ist es für die geänderten Abbilder der Indexseiten wieder möglich, wieder an den normalen Seiteneinteilungsvorgängen teilzunehmen. Die Seiten werden auch aus der Liste 34 der festgehaltenen Seiten entfernt. Die Veränderungen an den Datenräumen werden ebenfalls nachfolgend zu dem synchronen Einschreiben in den Eintragungspuffer vorgenommen. Die obige Reihenfolge ist für die Tatsache wichtig, daß damit sichergestellt wird, daß zu einem beliebigen Zeitpunkt eines Systemabsturzes mit Verlust des Hauptspeicherinhaltes die Datenräume und Indizes allein aus den in den Eintragungen vorhandenen Abbildern rekonstruiert werden können.
Einzutragende Objekte werden periodisch synchronisiert. Ein Auswahlmechanismus forciert das Objekt mit dem ältesten (frühesten) Synchronpunkt nach jeweils n Journaleintragungen in den Hilfs- Speicher. Dabei ist n ein Wert, der so gewählt wird, daß er ein Gleichgewicht zwischen der Wiederherstellungszeit und der Systemleistungsfähigkeit im Hinblick auf den Synchronpunktmechanismus herstellt. Er wird als Wiederherstellungskonstante bezeichnet. Die Synchronisierung des ältesten Objektes dient dazu, die Länge der Wiederherstellungszeit zu begrenzen, indem damit sichergestellt wird, daß während einer Wiederherstellung (nach einem Maschinenausfall) die Eintragungen nicht weiter zurückbearbeitet werden müssen als für die letzten n Eintragungen, die im Journal verbleiben. Die Wiederherstellungskonstante sichert ab, daß es kein Objekt gibt, das einen Synchronpunkt mit mehr als n Eintragungen vom Ende der Eintragungen an hat.
Die obige Beschreibung der Erfindungsvariante wird in Fig. 6 dargestellt.
Im Falle von Datenbankbearbeitungen, die massenhafte Datenveränderungen erforderlich machen (solche, die wahrscheinlich die überwiegende Mehrheit der Seiten in dem Index beeinflussen sollen), ist es nicht wünschenswert, jede von den Manipulationen betroffene Indexseite einzutragen, weil eine solche Verfahrensweise die Quote für die Herstellung von Eintragungsablagen dramatisch erhöhen würde. Vorgänge dieser Art erfordern die Änderung praktisch jeder Seite in einem beliebigen Index, der die Datenbasis überlagert, und würden folglich die Eintragung aller dieser unberührten Seiten erforderlich machen. Wenn die betroffenen Indizes groß sind, dann könnte die Eintragung demzufolge schnell außerordentlich groß werden. Statt dessen werden alle eingetragenen Indizes, die von dem Vorgang betroffen werden, vor Beginn des Vorganges vollständig wiederholt (geklont), und in dem Journal wird eine einzelne Eintragung vorgenommen, die einen Zeiger zu dem Klon enthält.
Das tatsächliche Klonverfahren umfaßt die folgenden in Fig. 2 gezeigten Schritte. Bei 210 wird das Datenbanknetzwerk stillgelegt; es werden Belegungen vorgenommen (Anzeigen, die die Benutzung durch einen anderen Vorgang verhindern), damit jegliche Indexänderungen verhindert werden, so daß man für den Klonvorgang eine folgerichtige Ansicht des Index und der darunterliegenden Datenbankseiten erhält. Da ein Klon insgesamt von dem vollständigen Index gemacht werden soll (wobei alle unberührten Seiten inbegriffen sind), besteht nicht länger die Notwendigkeit der nachfolgenden Eintragung der durch eine Indexänderung betroffenen unberührten Seiten. Wie bei 212 zu sehen ist, wird der Index zur Kennzeichnung markiert, daß seine unberührten Seiten nicht mehr eingetragen werden müssen. Die Kennzeichnung erfolgt in ähnlicher Weise wie nach der in Fig. 1 durch das Bit-Abbild 32 zur Verfügung gestellten Funktion.
Bei 214 wird der Klon des Datenbankindex erzeugt und in den Hilfsspeicher forciert. Der Diagrammblock 216 ordnet in der Eintragung einen Synchronpunkt an und erzeugt eine Journaleintragung zur Identifikation des Klons. Der Diagrammblock 218 löst jegliche Belegungen auf, die bei Diagrammblock 210 vorgenommen worden sind, und läßt nun wieder Veränderungen an dem Index zu.
Wenn eine Wiederherstellung tatsächlich notwendig wird, dann ersetzt der Indexklon, der aus den Eintragungen bezogen worden ist, den ursprünglichen Index. Die Wiederherstellung erfolgt dann genauso wie für Logiken mit eingetragenen unberührten Seiten; jegliche Ordnungsbegriffsänderungen bei Datenbanken werden in einem Protokoll angeordnet und auf den Index aufgebracht.
Bei einem Maschinenausfall identifiziert der Synchronpunkt für einen Datenraum den Ausgangspunkt für die Wiederherstellung. Bei Datenräumen werden alle nach dem letzten Prüfungspunkt (Synchronpunkt) eingetragenen DANACH-Abbilder auf die Datei aufgebracht. Bevor die Datenraumindizes (DSI) wiederhergestellt werden, wird für den Index ein Bereich, der Protokoll genannt wird, geschaffen. Alle während des Wiederherstellungsvorganges hinzugefügten oder entfernten Ordnungsbegriffe werden in diesem Protokoll abgelegt, ehe sie den binären Basiszahlenbaum direkt aktualisieren. Wenn einmal die Wiederherstellung abgeschlossen ist, dann werden diese protokollierten Veränderungen auf die Baumstruktur des Index angewandt. Dieser Protokollierungsmechanismus, der von einer direkten Änderung des binären Basiszahlenbaumes Abstand nimmt, ermöglicht einen Wiederanlauf der Wiederherstellung, das heißt, er toleriert auch einen Maschinenausfall während der Wiederherstellung selbst.
Bei Datenraumindizes werden drei Arten von Journaleintragungen auf den binären Basiszahlenbaum angewandt. Alle unterhalb des Synchronpunktes des Indexes befindlichen Eintragungen werden daraufhin geprüft, ob sie Davor-Abbilder für eine Datenraumeintragung (DSE), Danach-Abbilder für eine DSE oder Abbilder von unberührten Indexseiten sind. Unberührte Indexseiten-Abbilder, die in dem Journal angetroffen werden, werden jedoch direkt auf den Baum angewandt, ehe sie auf den Protokollbereich angewandt werden. Ordnungsbegriffe, die aus allen Davor-Abbildern konstruiert worden sind, werden als solche identifiziert, die eventuell aus dem Baum zu entfernen sind. Diese Ordnungsbegriffe werden jedoch, ehe sie direkt auf den Baum angewandt werden, in dem Protokollierungsbereich abgelegt. Gleichermaßen werden aus den Danach-Abbildern der DSE abgeleitete Ordnungsbegriffe genauso protokolliert und aufgelistet, damit sie eventuell in den Baum eingefügt werden können.
Wenn ein Danach-Abbild einer DSE in dem Journal angetroffen wird und diese Journaleintragung neueren Datums ist als der Synchronpunkt des Datenraumes, was durch den Vergleich der Reihenfolgenummer der anzuwendenden Journaleintragung mit dem Synchronpunkt des Datenraumes bestimmbar ist, dann wird die Journaleintragung direkt auf den Datenraum angewendet.
Wenn es beliebige eingetragene Indizes über den Datenraum gibt und die Datenraumeintragung gleich oder größer ist als der Synchronpunkt eines beliebigen dieser Indizes, dann wird das geeignete Abbild des Ordnungsbegriffes für den Index dadurch protokolliert, daß ein Abbild des Ordnungsbegriffes in einen getrennten Spezialbehälter im Hauptspeicher, der zu dem Index gehört, abgelegt wird. Dieser Behälter, der als Protokollbereich bezeichnet wird, dient als Sammelpunkt für die anstehenden Änderungen des Ordnungsbegriffes.
Wenn die Journaleintragung das Abbild einer unberührten Indexseite ist, dann wird es direkt auf den binären Basiszahlenbaum angewendet. In jeder dieser Journaleintragungen ist die Information zur Identifikation derjenigen Seite enthalten, die aus dem binären Baum betroffen ist. Bei einer Kloneintragung in dem Journal besteht die Wiederherstellung aus dem Ersatz des vollständigen binären Basiszahlenbaumes durch seinen Klon.
Da Veränderungen der Ordnungsbegriffe dann, wenn sie aufgefunden werden, in dem Protokollbereich gesichert werden, ist nur ein Durchlauf durch das Journal notwendig. Der Index wird zurückgerollt, und die zu seiner Synchronisierung mit seinem Datenraum erforderliche Information über die Ordnungsbegriffsänderung erhält man durch einen einzigen Blick auf das Journal. Dieser einzige Durchlaufvorgang spart bei den Wiederherstellungsabläufen Zeit.
Fig. 7a bis d stellt die obige Beschreibung der Wiederherstellung von Indizes und Datenräumen dar.
An diesem Punkt bleibt nur noch ein Wiederherstellungsschritt übrig. Damit der Index mit seinen Datenräumen aktualisiert wird, müssen die Änderungen des Ordnungsbegriffes, die mit dem Index protokolliert wurden, auf den Baum angewendet werden. Während dieser Phase nimmt eine Datenbankfunktion die protokollierten Veränderungen des Ordnungsbegriffes und setzt sie in den wiederhergestellten Index ein. Dies ist als "Einklinken" des Index bekannt. Wenn der Index einmal eingeklinkt worden ist, dann befindet er sich wieder in perfekter Synchronisation zu den Inhalten der zugeordneten Datenräume.
In Fig. 3 bis 5 ist ein einfaches Beispiel von ausgewählten Seiten aus einem Index dargestellt. Durch Kreise dargestellte Entscheidungsknoten definieren die Richtung (d. h. nach rechts oder nach links), in der die Suche ablaufen soll. Jeder Entscheidungsknoten enthält Verknüpfungsinformationen nach vorwärts und nach rückwärts. Sie enthalten auch Informationen, die die Art des Knotens definieren, und identifizieren ein Vergleichsbit, das in dem gewünschten Ordnungsbegriff daraufhin geprüft wird, welche Suchrichtung es angibt (z. B. wenn das Bit Null ist, dann läuft die Suche nach links ab; wenn das Bit Eins ist, dann läuft die Suche nach rechts ab). Seitenzeiger, die durch Dreiecke dargestellt werden, enthalten einen Zeiger auf die nächste Seite innerhalb des Suchpfades. Wenn ein Seitenzeiger angetroffen wird und die Seite, die er anspricht, nicht im schnellen Zugriffsspeicher oder im Hauptspeicher enthalten ist, dann muß die Bezugsseite aus dem Hilfsspeicher in den Hauptspeicher zurückgebracht (zurückgewonnen) werden. Abgeschlossene Textbausteine, die durch Rechtecke dargestellt werden, enthalten den restlichen Teil einer Eintragung oder eines Ordnungsbegriffes, die im Index gespeichert sind. Beliebige zwei Elemente werden jeweils als Gruppe definiert, wie etwa zwei Knoten oder ein Knoten und ein Seitenzeiger oder ein abgeschlossener Text und ein Knoten, um nur einige wenige Möglichkeiten zu benennen. Eine bei 110 angezeigte Seite 1 und eine bei 112 in Fig. 3 angezeigte Seite 2 sind Indexseiten und enthalten Eintragungen, die einer Datenraumaufzeichnung mit der folgenden Definition entsprechen:
Tier : Geräusch/Feld 1 : Feld 2
Der Datenraum wird als Datenraum Nummer 1 bezeichnet, und er hat vier Eintragungen:
Ordnungsnummer Feld 1 Feld 2
1 Kuh muhen
2 Sperling tschilpen
3 Pferd wiehern
4 Katze miauen
wobei die Ordnungsnummer der relativen Position der Datenraumeintragung im Datenraum entspricht. Die Bezugsadresse ist definiert durch die Datenraumnummer und die Ordnungsnummer, die der interessierenden Eintragung in dem Datenraum zugeordnet wurde. Die Aufzeichnung tschilpen hat eine Bezugsadresse von 1,2 entsprechend der Datenraumnummer beziehungsweise der Ordnungsnummer. Feld 2 ist das Schlüsselfeld.
Die Aufzeichnung miauen hat eine Bezugsadresse von 1,4; muhen 1,1 und wiehern 1,3. In Fig. 3 auf der Seite 1 wird der Indexschlüssel, der der zweiten Datenraumeintragung entspricht, bei der Gruppe 114 mit seiner eincodierten Bezugsadresse am Ende der Indexeintragung angezeigt. Miauen befindet sich bei der Gruppe 116 auf der Seite 1. Die Gruppe 116 hat auch einen Seitenzeiger 118, der auf die Seite 2 bei 112 hinweist.
Die Aufzeichnungen muhen und wiehern befinden sich beide an einem Knoten 120 auf der Seite 2.
Wenn die Eintragung des Datenraumes 1 gerade begonnen hat, ehe die Aufzeichnungen 3 und 4 in den Datenraum eingesetzt worden sind, dann würde das Journal die folgenden Eintragungen für die Aufzeichnungen 3 und 4 enthalten.

Journal:

Eintragungs-Nummer

1
.
.
.
16 Typ der Datenraumeintragung, Datenraumadresse und Ordnungsnummer 3 "Pferd wiehern"
17 Typ der Datenraumeintragung, Datenraumadresse und Ordnungsnummer 4
"Katze miauen"
Der Synchronpunkt für Datenraum 1 ist die Journaleintragungs- Nummer 16.
Als Beispiel für eine Indexeintragung wird die Eintragung des Datenraumindex begonnen, nachdem die Datenraumeintragungs-Nummer 4 in den Datenraum eingesetzt worden ist. Da es noch keine Eintragungen für den Datenraumindex gibt, ist sein Synchronpunkt Null. Dies bedeutet, daß der Index mit dem Journal synchron ist.
In den Datenraum sollen zwei Datenraumeintragungen eingesetzt werden:
Eintragung 5: Ente quaken
Eintragung 6: Hund bellen
Die Indexseite 2 wird durch die Datenraumeintragung "Ente quaken" geändert werden, wie es in Fig. 4 für die erste Eintragung dargestellt ist. Fig. 4 ist folgerichtig mit Fig. 3 numeriert. Die Seite wird zuerst eingetragen und festgehalten, da das dieser Seite entsprechende Bit in dem Bit-Abbild gleich Null ist. Das Journal enthält nun:
16 *das gleiche wie vorher*
17 *das gleiche wie vorher*
18 Typ der Indexeintragung, Adresse des Datenraumindex, Information über das/die interne(n) Anfangsetikett(en) des Index
19 Typ der Indexeintragung, Adresse des Datenraumindex, Bezugsadresse der Indexseite Seite 2 Daten Fig. 3 112 (unberührte Seite)
Der Synchronpunkt für den Datenraumindex ist nun die Eintragungs-Nummer 18. Die Bit-Abbildung für die Indexseite 2, die gerade eingetragen wurde, wird nun aktualisiert. Die Bit-Darstellung wird dann: 010000 . . . 0. Es ist anzumerken, daß die erste Bit-Position des Abbildes mit der ersten Seite des Index 110 korrespondiert. Die zweite Bit-Position stimmt mit der zweiten Seite des Index 112 überein. Die Indexseite 2 wird auf die Liste für die festgehaltenen Seiten für den Datenraumindex gesetzt. Die Liste für die festgehaltenen Seiten besteht aus einem Bereich, der zur Adressierung der gerade festgehaltenen Seiten benutzt wird.
Der Datenraumindex wird dann geändert. Es ist anzumerken, daß eine neue Gruppe 122 (Fig. 4) geschaffen wird, die sowohl die Aufzeichnungen quaken wie wiehern enthält. Die Gruppe 120 enthält nun einen Knoten, der auf den Knoten 122 zeigt. Wenn einmal alle Indexveränderungen abgeschlossen worden sind, dann wird die Datenraumveränderung als Journaleintragungs-Nummer 20 eingetragen. Das Journal enthält nun die folgenden Eintragungen:
16 *das gleiche wie vorher*
17 *das gleiche wie vorher*
----- Journalforcierungspunkt
(Synchronpunkt für den Datenraumindex)
18 *das gleiche wie vorher*
19 *das gleiche wie vorher*
20 Typ der Datenraumeintragung, Datenraumadresse, Ordnungs- Nummer 5 "Ente quaken"
Alle Journaleintragungen nach dem auf die Eintragung Nummer 17 folgenden Forcierungspunkt werden in den Hilfsspeicher eingeschrieben, wenn die Eintragung Nummer 20 vorgenommen worden ist. Die Festhaltemechanismen werden aus allen Seiten entfernt, auf die in der Liste der festgehaltenen Seiten des Datenraumindex Bezug genommen wurde, da nun bekannt ist, daß die den festgehaltenen Seiten entsprechenden Journaleintragungen zwangsläufig in den Hilfsspeicher gebracht worden sind. Bei diesem Beispiel wird der Festhaltemechanismus auf der Seite 2 (Fig. 4 112) des Index entfernt.
Die Veränderungen an dem Datenraum werden dann durchgeführt. Der Datenraum enthält nun:
Ordnungsnummer Feld 1 Feld 2
1 Kuh muhen
2 Sperling tschilpen
3 Pferd wiehern
4 Katze miauen
5 Ente quaken
Wenn die Datenraumeintragung "Hund bellen" in den Datenraum eingesetzt wird, dann betrifft der Ordnungsbegriff "bellen" die Seite 1 (Fig. 3 110) in dem Datenraumindex. Seite 1 wird eingetragen und festgehalten. Das Journal enthält nun:
16 *das gleiche wie vorher*
17 *das gleiche wie vorher*
18 *das gleiche wie vorher*
19 *das gleiche wie vorher*
20 *das gleiche wie vorher*
21 Typ der Indexeintragung, Adresse des Datenraumindex, Bezugsadresse der Indexseite, Seite 1 Daten Fig. 3 110 (unberührtes Seitenabbild)
Das Bitabbild wird dann zum Lesen von 1100000... 0 aktualisiert.
Die Seite 1 wird auf die Liste für die festgehaltenen Seiten für den Datenraumindex gesetzt. Der Datenraumindex wird wie in Fig. 5 110 dargestellt geändert, wobei die Numerierung übereinstimmend mit Fig. 3 ist. Der Knoten 114 enthält nun keinen Text, statt dessen weist er auf Knoten 124 hin, der nun die beiden Ordnungsbegriffe bellen und tschilpen enthält.
Die Datenraumänderung wird eingetragen, so daß das Journal nun folgendes enthält:
16 *das gleiche wie vorher*
17 *das gleiche wie vorher*
18 *das gleiche wie vorher*
19 *das gleiche wie vorher*
20 *das gleiche wie vorher*
21 *das gleiche wie vorher*
22 Typ der Datenraumeintragung, Adresse des Datenraumes, Ordnungsnummer 6 "Hund bellen"
Der Journalforcierungspunkt befindet sich gerade vor der Eintragungs-Nummer 21, daher werden die Eintragungen 21 und 22 nun in den Hilfsspeicher eingeschrieben, wenn die Eintragung 22 vorgenommen wird. Der Festhaltemechanismus wird dann aus der Seite 1 entfernt, und der Datenraum enthält nun:
Ordnungsnummer Feld 1 Feld 2
1 Kuh muhen
2 Sperling tschilpen
3 Pferd wiehern
4 Katze miauen
5 Ente quaken
6 Hund bellen
Nun soll die Eintragung "Vögel zwitschern" vorgenommen werden. Obgleich Seite 2 des Index verändert werden wird, ist ihr entsprechendes Bit im Bitabbild gesetzt, so daß für sie nichts eingetragen oder festgehalten werden muß. Das Bitabbild muß nicht aktualisiert werden, da das Bit schon gesetzt ist. Da die Seite nicht festgehalten wurde, wird auch nichts in die Liste der festgehaltenen Seiten aufgenommen. Der Datenraumindex wird verändert, und die Datenraumveränderung wird eingetragen. Das Journal enthält nun:
16 *das gleiche wie vorher*
. .
. .
.
22 .
23 Typ der Datenraumeintragung, Adresse des Datenraumes, Ordnungsnummer 7 "Vögel zwitschern"
Die Journaleintragung 23 wird in den Hilfsspeicher eingeschrieben. Es müssen keine Festhaltemechanismen entfernt werden, und der Datenraum wird dann geändert. Der Datenraum enthält nun:
Ordnungsnummer Feld 1 Feld 2
1 Kuh muhen
2 Sperling tschilpen
3 Pferd wiehern
4 Katze miauen
5 Ente quaken
6. Hund bellen
7 Vögel zwitschern
Eine Alternative zu dem beschriebenen Festhaltemechanismus besteht in der Verwendung eines geordneten Eingabe-/Ausgabeschemas. Das Festhalten dient zur Sicherstellung, daß die geänderte Indexseite nicht vor dem Journal-Abbild des unberührten Seitenabbildes auf der Magnetplatte eingeschrieben wird. Alternativ dazu kann auch eine Speicherführungsfunktion dazu benutzt werden, um eine Reihenfolge der Seitenschreibvorgänge festzulegen. In diesem Falle würden zuerst das Journalabbild und dann die geänderte Indexseite eingeschrieben werden.

Ringförmiger Puffer für Indexelastizität

Eine weitere Ausführung der vorliegenden Erfindung benutzt einen ringförmigen Protokollpufferbereich für unberührte Indexseiten anstelle ihrer Ablage in dem Journal, das für die Ablage der Abbilder der Datenraumeintragungen benutzt wird. Der Algorithmus schreibt vor, daß die Datenraumveränderungen eingetragen werden, daß aber die unberührten Indexseiten in einen ringförmigen Puffer getrennt von dem Journal eingeschrieben werden, das mit dem Datenraum verbunden ist. Diese Einrichtung eines ringförmigen Puffers vermindert den Bedarf an Hilfsspeicherkapazität, der für die Unterbringung der unberührten Indexseiten erforderlich ist, und verhindert es, daß das Journal durch die vielen unberührten Indexseiten aufgebläht wird.
Bei 810 in Fig. 8 wird ein ringförmiger Puffer zur Unterbringung von unberührten Indexseiten definiert, und mit Hilfe von zwei Zeigern wird auf ihn hingewiesen, mit START, der bei 812 angezeigt wird, und mit AVAIL, der bei 814 angezeigt wird, wobei diese im Puffer den zuerst zu benutzenden Bereich beziehungsweise den nächsten verfügbaren Bereich identifizieren. Es wird auch ein Bitabbild definiert, das jede unberührte Seite in der Indexdatei identifiziert, die schon in dem ringförmigen Speicher abgelegt worden ist. Da die unberührten Seiten des Index in den ringförmigen Speicher 810 eingeschrieben werden, muß eine unberührte Seite, wenn sie einmal im Puffer ist, nicht wieder dort abgelegt werden, außer wenn der Index vollständig in den Hilfsspeicher überschrieben wird und in dem Journal ein neuer Synchronpunkt angezeigt wird. Für jeden Index gibt es ein unterschiedliches Bitabbild, so daß der ringförmige Puffer zur Ablage von unberührten Seiten aus mehreren Indizes in einem System benutzt werden kann.
Wenn die Datenräume geändert werden, dann können Änderungen in beliebigen Indizes für diese Datenräume ausgelöst werden. Wenn einmal die zu modifizierenden Indexseiten bestimmt worden sind, dann wird das Bitabbild für den Index daraufhin geprüft, ob die unberührten Abbilder beliebiger Seiten schon in dem ringförmigen Puffer abgelegt worden sind. Falls die unberührte Seite schon abgelegt worden ist, ist keine weitere Aktion erforderlich, und diese Indexseite wird modifiziert. Wenn die unberührte Seite nicht abgelegt worden ist, dann wird sie in dem ringförmigen Puffer abgelegt, und ein nicht synchronisierter Einschreibvorgang (Seite im Hilfsspeicher eingeschrieben) wird an der neuen Ablage veranlaßt. Die unberührte Seite in dem Index wird dann festgehalten und modifiziert. Der Festhaltemechanismus verbleibt auf der modifizierten Indexseite, bis die Ablage der unberührten Seite in dem ringförmigen Puffer in den Hilfsspeicher eingeschrieben worden ist. Diese Reihenfolge muß eingehalten werden, damit bei der Wiederherstellung die notwendige Information zum Ersatz der modifizierten Indexseite durch die ursprüngliche unberührte Seite zur Verfügung steht. Wenn der Puffer in den Hilfsspeicher eingeschrieben worden ist, dann wird die tatsächliche Indexseite losgelassen, und sie kann wieder an den normalen Seiteneinteilungsvorgängen teilnehmen.
Die Verwaltung des ringförmigen Puffers ist der Schlüssel zum Journalalgorithmus für den ringförmigen Puffer. Zur Erläuterung wird ein Beispiel dargestellt, bei dem Änderungen in zwei Indizes gleichzeitig vorkommen.
Anfänglich ist der Puffer leer, aber ihm ist eine implementierungsabhängige Größe schon zugeordnet. START bei 812 und AVAIL bei 814 verweisen beide das erste Byte in den zugewiesenen Raum.
Eine Veränderung einer Datenraumeintragung bewirkt, daß Seite 1 des Index Nr. 1 bei 815 geändert werden soll (wie in Fig. 8 gezeigt). Die Darstellung des ringförmigen Puffers nach der Veränderung ist bei 816 zu sehen. START bleibt bei 818 weiterhin am Anfang des Puffers angeordnet, aber AVAIL 820 bewegt sich vorwärts in den Puffer hinein, wenn die unberührte Indexseite in dem Puffer abgelegt wird. Der für die Seite neu verwendete Pufferraum wird nun asynchron in den Hilfsspeicher eingeschrieben, die geänderte Indexseite wird festgehalten, und die aktuellen Veränderungen werden durchgeführt. Das entsprechende Bit aus der Bitabbildung wird gesetzt und zeigt an, daß die unberührte Seite dieser Indexseite im Puffer ist.
Die obige Verfahrensweise wird für die Seiten 2 und 7 des Index Nr. 1 und die Seiten 5 und 15 des Index Nr. 2 wiederholt. Bis zu der Zeit, da die Seite 7 des Index Nr. 1 in dem Puffer eingeschrieben wird, sind die asynchronen Schreibvorgänge der Seiten 1 und 2 des Index Nr. 1 abgeschlossen. Die Seiten 1 und 2 in dem Index Nr. 1 werden nun im Hauptspeicher losgelassen. Nachdem die Seiten 2, 7, 5 und 15 in dem Puffer untergebracht worden sind, verweist AVAIL bei 820 in der dritten Darstellung des Puffers (822) nun auf den Anfang des Puffers, da das Ende des anfangs zugeordneten Pufferraumes erreicht ist und ein Rücksprung zum Anfang des Puffers erfolgt. Dieser Rücksprung ist kennzeichnend für den ringförmigen Aufbau dieses Puffers.
Wenn beliebige weitere Veränderungen an jedem Index auftreten, dann muß in dem ringförmigen Speicher Raum für die Unterbringung der unberührten Abbilder vorhanden sein. Wenn der gesamte Raum belegt worden ist, dann muß ein Bereich freigemacht werden, ehe beliebige weitere Veränderungen durchgeführt werden können. Um dies zu bewerkstelligen, wird der Index, dessen Seiten die nächsten im Puffer sind, in den Hilfsspeicher eingeschrieben. Dadurch werden alle Seiten frei, die zu diesem Index gehören, da sie für die Wiederherstellung nicht mehr erforderlich sind, und dadurch wird der START-Zeiger bei 828 veranlaßt (in der vierten Darstellung des Puffers 830), zu dem nächsten benutzten Bereich fortzuschreiten.
Es sollte angemerkt werden, daß die Größe des Puffers so gewählt werden muß, daß die Forcierungen der Indizes nicht sehr oft erfolgen. Wenn jedoch der Puffer zu groß ist, dann kann die Wiederherstellungszeit unvertretbar werden, da viele unberührte Seiten auf den Index aufgebracht werden müssen. Es ist ein Kompromiß zwischen diesen beiden Faktoren notwendig, bei dem sowohl die Anzahl der Schreibvorgänge in den Hilfsspeicher als auch die Wiederherstellungszeit akzeptabel sind. Dem Anwender wird eine Option für die Wahl der Puffergröße angeboten.
Wenn eine Wiederherstellung erforderlich wird, dann werden die Indizes in ihrem unberührten Zustand neu gespeichert, indem der Ringpuffer beginnend bei START und bei AVAIL endend gelesen wird, und dabei werden die Indexseiten durch ihre unberührten Abbilder, wie sie in dem ringförmigen Puffer existieren, ersetzt. Wenn dies abgeschlossen ist, dann stellt sich der Index so dar, wie er vor seiner letzten Forcierung war. Dann wird das Journal geprüft, und die Veränderungen an den Datenräumen werden durchgeführt, wobei die Änderungen auf die entsprechenden Indizes mit aufgebracht werden. Da sich die Indizes in ihrem unberührten Zustand befinden, können die Veränderungen an ihnen direkt vorgenommen werden. Wenn das Journal aufgebracht worden ist, dann ist das Datenbanknetzwerk ohne weitere Verfahrensweisen für eine Benutzung bereit.
Fig. 9 stellt die grundsätzliche Verfahrensweise dar, die zur Ablage der unberührten Abbilder in dem ringförmigen Puffer benutzt wird.
Wenn auch die Erfindung im Hinblick auf eine einzelne Variante mit einigen wenigen Abwandlungen beschrieben worden ist, so ist es jedoch allen Fachleuten klar, daß die vorliegende Erfindung nicht auf diese Varianten und Abwandlungen begrenzt ist. Die Erfindung bezieht sich auf die Journalführung von logischen Dateien, nicht nur von Indizes. Es gibt eine Vielzahl von unterschiedlichen Speicherführungsmechanismen, die im Austausch benutzt werden könnten, ohne daß vom geistigen Umfang der vorliegenden Erfindung abgewichen wird, wie er beschrieben und durch Ansprüche belegt ist.

Claims

1. Verfahren zum Eintragen von Indizes, die zu einem Datenraum eines Computersystems führen, das Daten in Seiten aus einem bzw. in einen Hauptspeicher und aus einem bzw. in einen Hilfsspeicher überträgt, wobei das Verfahren dadurch gekennzeichnet ist, daß es die folgenden Schritte aufweist:

a. Bestimmen welche Indexseiten eine Änderung erfordern, in Abhängigkeit von angeforderten Änderungen im Datenraum;

b. Festhalten solcher Indexseiten, um zu verhindern, daß sie in den Hilfsspeicher geschrieben werden;

c. Eintragen ungeänderter Seiten von Indizes, welche Änderungen aufweisen, die das Ergebnis der im Datenraum durchzuführenden Änderungen sind, so daß die Indizes an einem gewünschten Punkt der Einträge mit dem Datenraum synchronisiert sind;

d. Ändern dieser Indizes;

e. Eintragen der Änderungen an dem Datenraum vor dem Ändern des Datenraums;

f. Schreiben der Einträge in den Hilfsspeicher;

g. Loslassen der Indexseiten, so daß sie in den Hilfsspeicher fließen können und

h. Ändern des Datenraums.

2. Eintragungsvorrichtung zum Ausführen des Verfahrens nach Anspruch 1 in einem Computersystem, welches das Übertragen von Seiten zwischen einem Hauptspeicher (12) und einem Hilfsspeicher (16, 18, 26, 20, 22) benützt und nichtflüchtige Speichermittel (30) zum Speichern von Einträgeinformation aufweist, wobei das Computersystem Datenräume (24) und Indizes (26) besitzt, die zu diesen Datenräumen führen, und die Vorrichtung zum Eintragen dadurch gekennzeichnet ist, daß sie folgendes aufweist:

Mittel zum Eintragen von Einträgeinformation in den Datenraum, die zu den durchzuführenden Änderungen in Datenräumen des Speichermittels führt und

Mittel zum Eintragen von Indizes, um unveränderte Seiten mit Indizes einzutragen, die von den in einem Datenraum eines Speichermittels durchzuführenden Änderungen betroffen sind, so daß das Speichermittel Information enthält, aus welcher der Datenraum und die Indizes zu einem selben Zeitpunkt wiederhergestellt werden können.

3. Eintragungsvorrichtung nach Anspruch 2, dadurch gekennzeichnet, daß die Einträgeinformation sowohl für den Datenraum als auch für die dazu führenden unveränderten Indexseiten im selben Arbeitsgang in das nichtflüchtige Speichermittel geschrieben wird.

4. Eintragungsvorrichtung nach Anspruch 2 oder 3, dadurch gekennzeichnet, daß die Einträgeinformation in das nichtflüchtige Speichermittel geschrieben wird, bevor im Hilfsspeicher sowohl im Bild des Datenraums als auch an dem Index permanente Änderungen herbeigeführt werden.

5. Eintragungsvorrichtung nach einem der Ansprüche 2 bis 4, dadurch gekennzeichnet, daß das Speichermittel im Hauptspeicher einen Bereich (34) aufweist und bei welcher Indexseiten, die im Hauptspeicher eingetragen wurden, aber noch nicht in den nichtflüchtigen Speicher geschrieben wurden, festgehalten werden, um zu verhindern, daß Änderungen an diesen in den Hilfsspeicher geschrieben werden.

6. Eintragungsvorrichtung nach einem der Ansprüche 2 bis 5, dadurch gekennzeichnet, daß sie weiterhin Mittel zum Wiederherstellen aufweist, die an das Speichermittel gekoppelt sind, um die nach einem Systemfehler zu einem Datenraum führenden Indizes zurückzuholen und die im Datenraum eingetragene Information dazu verwenden, um an den zurückgeholten Indizes Änderungen zu bewirken, so daß diese mit dem Datenraum synchronisiert werden.

7. Eintragungsvorrichtung nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, daß sie weiterhin aufweist:

an die Mittel zum Eintragen von Indizes gekoppeltes Detektionsmittel zum Erfassen der Indexseiten, die von den im Datenraum durchzuführenden Änderungen betroffen sind.

8. Eintragungsvorrichtung nach einem der Ansprüche 2 bis 6, dadurch gekennzeichnet, daß sie weiterhin aufweist:

an die Mittel zum Eintragen der Indizes gekoppeltes Mittel zum Klonen, um alle ungeänderten Seiten an dem Index in den Hilfsspeicher zu kopieren, wenn das Detektionsmittel feststellt, daß ein vorbestimmtes Verhältnis von Seiten an dem Index geändert werden.

9. Eintragungsvorrichtung nach Anspruch 8, dadurch gekennzeichnet, daß die Mittel zum Eintragen ein Anzeichen einträgt, daß eine Kopie eines Index angefertigt wurde, wobei diese Anzeige den Standort dieser Kopie angibt.