Verwenden Sie eine RandomAccessFile, um eine Datenbank auf niedriger Ebene zu erstellen

Als ich auf der JavaWorld -Website nach Ideen für Schritt für Schritt dieses Monats suchte , stieß ich nur auf wenige Artikel über den Dateizugriff auf niedriger Ebene. Obwohl High-Level-APIs wie JDBC uns die Flexibilität und Leistung bieten, die in großen Unternehmensanwendungen erforderlich sind, erfordern viele kleinere Anwendungen eine einfachere und elegantere Lösung.

In diesem Artikel erstellen wir eine Erweiterung der RandomAccessFileKlasse, mit der wir Datensätze speichern und abrufen können. Diese "Datensatzdatei" entspricht einer dauerhaften Hashtabelle, mit der verschlüsselte Objekte gespeichert und aus dem Dateispeicher abgerufen werden können.

Eine Einführung in Dateien und Datensätze

Bevor wir kopfüber in das Beispiel springen, beginnen wir mit einem grundlegenden Hintergrund. Wir werden zunächst einige Begriffe definieren, die sich auf Dateien und Datensätze beziehen, und dann kurz auf die Klassen- java.io.RandomAccessFileund Plattformabhängigkeit eingehen.

Terminologie

Die folgenden Definitionen beziehen sich eher auf unser Beispiel als auf die herkömmliche Datenbankterminologie.

Datensatz - Eine Sammlung verwandter Daten, die in einer Datei gespeichert sind. Ein Datensatz enthält normalerweise mehrere Felder, von denen jedes eine benannte und eingegebene Information ist.

Schlüssel - Eine Kennung für einen Datensatz. Schlüssel sind normalerweise eindeutig.

Datei - Eine sequentielle Sammlung von Daten, die in einem stabilen Speicher wie einer Festplatte gespeichert sind.

Nicht sequenzieller Dateizugriff - Ermöglicht das Lesen von Daten von beliebigen Stellen in der Datei.

Dateizeiger - Eine Zahl, die die Position des nächsten Datenbytes enthält, das aus einer Datei gelesen werden soll.

Datensatzzeiger - Ein Datensatzzeiger ist ein Dateizeiger, der auf die Stelle zeigt, an der ein bestimmter Datensatz beginnt.

Index - Ein sekundäres Mittel für den Zugriff auf Datensätze in einer Datei. Das heißt, es ordnet Schlüssel Aufzeichnungszeigern zu.

Heap - Eine sequentielle Datei mit ungeordneten Datensätzen und Datensätzen variabler Größe. Ein Heap erfordert eine externe Indizierung, um sinnvoll auf die Datensätze zugreifen zu können.

Persistenz - Bezieht sich auf das Speichern eines Objekts oder einer Aufzeichnung für einen bestimmten Zeitraum. Diese Zeitspanne ist in der Regel länger als die Spannweite eines Prozesses, also Objekte werden in der Regel beharren in Dateien oder Datenbanken.

Übersicht über die Klasse java.io.RandomAccessFile

Klasse RandomAccessFileist Javas Methode, um nicht sequentiellen Zugriff auf Dateien zu ermöglichen. Mit dieser Klasse können wir mithilfe der seek()Methode zu einem bestimmten Speicherort in der Datei springen . Sobald der Dateizeiger positioniert worden ist , können die Daten aus und in die Datei geschrieben gelesen werden die Verwendung DataInputund DataOutputSchnittstellen. Diese Schnittstellen ermöglichen es uns, Daten plattformunabhängig zu lesen und zu schreiben. Mit anderen praktischen Methoden RandomAccessFilekönnen wir die Länge der Datei überprüfen und einstellen.

Plattformabhängige Überlegungen

Moderne Datenbanken sind für die Speicherung auf Festplatten angewiesen. Daten auf einem Festplattenlaufwerk werden in Blöcken gespeichert , die auf Spuren und Oberflächen verteilt sind. Die Suchzeit und die Rotationsverzögerung der Festplatte bestimmen, wie Daten am effizientesten gespeichert und abgerufen werden können. Ein typisches Datenbankverwaltungssystem stützt sich eng auf die Attribute der Festplatte, um die Leistung zu optimieren. Leider (oder glücklicherweise, abhängig von Ihrem Interesse an Low-Level-Datei-E / A!) Sind diese Parameter bei Verwendung einer High-Level-Datei-API wie z java.io. In Anbetracht dieser Tatsache werden in unserem Beispiel die Optimierungen außer Acht gelassen, die die Kenntnis der Parameter der Festplatte liefern könnte.

Entwerfen des RecordsFile-Beispiels

Jetzt sind wir bereit, unser Beispiel zu entwerfen. Zunächst werde ich einige Entwurfsanforderungen und -ziele festlegen, Probleme beim gleichzeitigen Zugriff lösen und das Dateiformat auf niedriger Ebene angeben. Bevor wir mit der Implementierung fortfahren, werden wir uns auch die Hauptaufzeichnungsoperationen und ihre entsprechenden Algorithmen ansehen.

Anforderungen und Ziele

Unser Hauptziel in diesem Beispiel ist die Verwendung von a RandomAccessFile, um eine Möglichkeit zum Speichern und Abrufen von Datensatzdaten bereitzustellen. Wir werden Stringjedem Datensatz einen Typschlüssel zuordnen, um ihn eindeutig zu identifizieren. Die Schlüssel sind auf eine maximale Länge begrenzt, obwohl die Aufzeichnungsdaten nicht begrenzt sind. Für die Zwecke dieses Beispiels bestehen unsere Datensätze nur aus einem Feld - einem "Blob" von Binärdaten. Der Dateicode versucht nicht, die Datensatzdaten in irgendeiner Weise zu interpretieren.

Als zweites Entwurfsziel müssen die Anzahl der von unserer Datei unterstützten Datensätze zum Zeitpunkt der Erstellung nicht festgelegt werden. Wir werden zulassen, dass die Datei wächst und schrumpft, wenn Datensätze eingefügt und entfernt werden. Da unsere Index- und Datensatzdaten in derselben Datei gespeichert werden, führt diese Einschränkung dazu, dass wir zusätzliche Logik hinzufügen, um den Indexbereich durch Reorganisation von Datensätzen dynamisch zu vergrößern.

Der Zugriff auf Daten in einer Datei ist um Größenordnungen langsamer als der Zugriff auf Daten im Speicher. Dies bedeutet, dass die Anzahl der Dateizugriffe, die die Datenbank ausführt, der bestimmende Leistungsfaktor ist. Wir werden verlangen, dass unsere Hauptdatenbankoperationen nicht von der Anzahl der Datensätze in der Datei abhängen. Mit anderen Worten, sie haben eine konstante Ordnungszeit in Bezug auf Dateizugriffe.

Als letzte Anforderung gehen wir davon aus, dass unser Index klein genug ist, um in den Speicher geladen zu werden. Dies erleichtert unserer Implementierung die Erfüllung der Anforderungen, die die Zugriffszeit vorschreiben. Wir werden den Index in a spiegeln Hashtable, der eine sofortige Suche nach Datensatz-Headern ermöglicht.

Codekorrektur

Der Code für diesen Artikel weist einen Fehler auf, der in vielen möglichen Fällen eine NullPointerException auslöst. In der abstrakten Klasse BaseRecordsFile gibt es eine Routine namens insureIndexSpace (int). Der Code soll vorhandene Datensätze an das Ende der Datei verschieben, wenn der Indexbereich erweitert werden muss. Nachdem die Kapazität des "ersten" Datensatzes auf seine tatsächliche Größe zurückgesetzt wurde, wird sie an das Ende verschoben. Der dataStartPtr wird dann so eingestellt, dass er auf den zweiten Datensatz in der Datei zeigt. Wenn im ersten Datensatz freier Speicherplatz vorhanden war, zeigt der neue dataStartPtr leider nicht auf einen gültigen Datensatz, da er eher um die Länge des ersten Datensatzes als um seine Kapazität erhöht wurde. Die geänderte Java-Quelle für BaseRecordsFile finden Sie unter Ressourcen.

von Ron Walkup

Senior-Software-Entwickler

bioMerieux, Inc.

Synchronisation und gleichzeitiger Dateizugriff

Der Einfachheit halber unterstützen wir zunächst nur ein Single-Thread-Modell, bei dem die gleichzeitige Ausführung von Dateianforderungen verboten ist. Wir können dies erreichen, indem wir die öffentlichen Zugriffsmethoden der Klassen BaseRecordsFileund synchronisieren RecordsFile. Beachten Sie, dass Sie diese Einschränkung lockern können, um Unterstützung für gleichzeitige Lese- und Schreibvorgänge für nicht widersprüchliche Datensätze hinzuzufügen: Sie müssen eine Liste gesperrter Datensätze verwalten und Lese- und Schreibvorgänge für gleichzeitige Anforderungen verschachteln.

Details zum Dateiformat

Wir werden nun explizit das Format der Datensatzdatei definieren. Die Datei besteht aus drei Regionen mit jeweils einem eigenen Format.

Der Dateikopfbereich. Diese erste Region enthält die beiden wesentlichen Header, die für den Zugriff auf Datensätze in unserer Datei erforderlich sind. Der erste Header, der als Datenstartzeiger bezeichnet wird long, zeigt auf den Anfang der Datensatzdaten. Dieser Wert gibt die Größe des Indexbereichs an. Der zweite Header, der als num-Datensatz-Header bezeichnet wird int, gibt die Anzahl der Datensätze in der Datenbank an. Der Header-Bereich beginnt am ersten Byte der Datei und erstreckt sich über FILE_HEADERS_REGION_LENGTHBytes. Wir verwenden readLong()und readInt()die Header zu lesen, und writeLong()und writeInt()die Header zu schreiben.

Der Indexbereich. Jeder Eintrag im Index besteht aus einem Schlüssel und einem Datensatzkopf. Der Index beginnt mit dem ersten Byte nach dem Dateikopfbereich und erstreckt sich bis zum Byte vor dem Datenstartzeiger. Aus diesen Informationen können wir einen Dateizeiger auf den Anfang eines der n Einträge im Index berechnen . Einträge haben eine feste Länge - die Schlüsseldaten beginnen beim ersten Byte im Indexeintrag und erweitern die MAX_KEY_LENGTHBytes. Der entsprechende Datensatzkopf für einen bestimmten Schlüssel folgt unmittelbar nach dem Schlüssel im Index. Der Datensatzheader gibt an, wo sich die Daten befinden, wie viele Bytes der Datensatz enthalten kann und wie viele Bytes er tatsächlich enthält. Indexeinträge im Dateiindex sind in keiner bestimmten Reihenfolge und werden nicht der Reihenfolge zugeordnet, in der die Datensätze in der Datei gespeichert sind.

Datenbereich aufzeichnen. Der Datensatzdatenbereich beginnt an der durch den Datenstartzeiger angegebenen Position und erstreckt sich bis zum Ende der Datei. Datensätze werden hintereinander in der Datei positioniert, wobei zwischen den Datensätzen kein freier Speicherplatz zulässig ist. Dieser Teil der Datei besteht aus Rohdaten ohne Header- oder Schlüsselinformationen. Die Datenbankdatei endet am letzten Block des letzten Datensatzes in der Datei, sodass am Ende der Datei kein zusätzlicher Speicherplatz vorhanden ist. Die Datei wächst und schrumpft, wenn Datensätze hinzugefügt und gelöscht werden.

Die einem Datensatz zugewiesene Größe entspricht nicht immer der tatsächlichen Datenmenge, die der Datensatz enthält. Der Datensatz kann als Container betrachtet werden - er ist möglicherweise nur teilweise voll. Gültige Datensatzdaten werden am Anfang des Datensatzes positioniert.

Unterstützte Operationen und ihre Algorithmen

Das RecordsFileunterstützt die folgenden Hauptoperationen:

  • Einfügen - Fügt der Datei einen neuen Datensatz hinzu

  • Lesen - Liest einen Datensatz aus der Datei

  • Aktualisieren - Aktualisiert einen Datensatz

  • Löschen - Löscht einen Datensatz

  • Kapazität sicherstellen - Vergrößert den Indexbereich, um neue Datensätze aufzunehmen

Bevor wir den Quellcode durchgehen, gehen wir die ausgewählten Algorithmen für jede dieser Operationen durch:

Einfügen. Dieser Vorgang fügt einen neuen Datensatz in die Datei ein. Zum Einfügen haben wir:

  1. Stellen Sie sicher, dass der einzufügende Schlüssel nicht bereits in der Datei enthalten ist
  2. Stellen Sie sicher, dass der Indexbereich groß genug für den zusätzlichen Eintrag ist
  3. Suchen Sie freien Speicherplatz in der Datei, der groß genug ist, um den Datensatz aufzunehmen
  4. Schreiben Sie die Datensatzdaten in die Datei
  5. Fügen Sie den Datensatzkopf zum Index hinzu

Lesen. Diese Operation ruft einen angeforderten Datensatz basierend auf einem Schlüssel aus der Datei ab. Um einen Datensatz abzurufen, gehen wir wie folgt vor:

  1. Verwenden Sie den Index, um den angegebenen Schlüssel dem Datensatzkopf zuzuordnen
  2. Suchen Sie bis zum Anfang der Daten (mit dem Zeiger auf die im Header gespeicherten Datensatzdaten).
  3. Lesen Sie die Daten des Datensatzes aus der Datei

Aktualisieren. Dieser Vorgang aktualisiert einen vorhandenen Datensatz mit neuen Daten und ersetzt die neuen Daten durch die alten. Die Schritte für unser Update variieren je nach Größe der neuen Datensatzdaten. Wenn die neuen Daten in den vorhandenen Datensatz passen, werden wir:

  1. Schreiben Sie die Datensatzdaten in die Datei und überschreiben Sie die vorherigen Daten
  2. Aktualisieren Sie das Attribut, das die Länge der Daten im Header des Datensatzes enthält

Andernfalls, wenn die Daten für den Datensatz zu groß sind, gehen wir wie folgt vor:

  1. Führen Sie einen Löschvorgang für den vorhandenen Datensatz durch
  2. Führen Sie eine Einfügung der neuen Daten durch

Löschen. Dieser Vorgang entfernt einen Datensatz aus der Datei. Um einen Datensatz zu löschen, gehen wir wie folgt vor:

  1. Stellen Sie den dem zu entfernenden Datensatz zugewiesenen Speicherplatz wieder her, indem Sie entweder die Datei verkleinern, wenn der Datensatz der letzte in der Datei ist, oder indem Sie den Speicherplatz einem benachbarten Datensatz hinzufügen

  2. Entfernen Sie den Header des Datensatzes aus dem Index, indem Sie den zu löschenden Eintrag durch den letzten Eintrag im Index ersetzen. Dadurch wird sichergestellt, dass der Index immer voll ist und keine Leerzeichen zwischen den Einträgen vorhanden sind

Kapazität sicherstellen. Diese Operation stellt sicher, dass der Indexbereich groß genug ist, um zusätzliche Einträge aufzunehmen. In einer Schleife verschieben wir Datensätze von der Vorderseite zum Ende der Datei, bis genügend Speicherplatz vorhanden ist. Um einen Datensatz zu verschieben, gehen wir wie folgt vor:

  1. Suchen Sie den Datensatzheader des ersten Datensatzes in der Datei. Beachten Sie, dass dies der Datensatz mit Daten oben im Datensatzdatenbereich ist - nicht der Datensatz mit dem ersten Header im Index

  2. Lesen Sie die Daten des Zieldatensatzes

  3. Erweitern Sie die Datei mithilfe der setLength(long)Methode in um die Größe der Daten des ZieldatensatzesRandomAccessFile

  4. Schreiben Sie die Datensatzdaten in das Ende der Datei

  5. Aktualisieren Sie den Datenzeiger in dem Datensatz, der verschoben wurde

  6. Aktualisieren Sie den globalen Header, der auf die Daten des ersten Datensatzes verweist

Implementierungsdetails - Durchlaufen des Quellcodes

Wir sind jetzt bereit, uns die Hände schmutzig zu machen und den Code für das Beispiel durchzuarbeiten. Sie können die vollständige Quelle unter Ressourcen herunterladen.

Hinweis: Sie müssen die Java 2-Plattform (früher als JDK 1.2 bekannt) verwenden, um die Quelle zu kompilieren.

Klasse BaseRecordsFile

BaseRecordsFileist eine abstrakte Klasse und die Hauptimplementierung unseres Beispiels. Es definiert die Hauptzugriffsmethoden sowie eine Reihe von Dienstprogrammmethoden zum Bearbeiten von Datensätzen und Indexeinträgen.