Zum Inhalt springen

Aktualisierungen durch Copy-on-Write

Einführung

"Copy on Write" ist eine Technik, die in einer Vielzahl von Anwendungen im Computer verwendet wird. RDM verwendet diese Technik in einigen Bereichen. Bevor wir uns mit RDM befassen, werfen wir einen Blick auf den allgemeinen Fall.

 

Die Hauptidee hinter Copy-on-Write besteht darin, Inhalte zu kopieren und dann die Kopie zu ändern, anstatt das Original zu ändern, wenn in den Speicher, eine Datei oder ein Blockgerät geschrieben wird. Daher stammt der Begriff Copy-on-Write. Einige Anwendungen sind Copy-on-Write in der funktionalen Programmierung in Kombination mit „Referenzzählung“. Unter Unix wird Copy-on-Write verwendet, um den virtuellen Speicher bei der Implementierung des Fork-Systemaufrufs mit Unterstützung der Hardware gemeinsam zu nutzen. Das Btrfs-Dateisystem unter Linux verwendet Copy-on-Write, um eine effiziente Transaktionsverarbeitung und Snapshot-Isolation zu ermöglichen. Diese Technik wird auch von Hypervisoren und Implementierungen virtueller Maschinen für eine effiziente Speicherverwaltung verwendet.

 

In RDM verwenden wir diese Technik für verschachtelte Transaktionen. Dieser Artikel konzentriert sich jedoch auf das in RDM 15.0 implementierte Datenbankdateiformat. Schauen wir uns zunächst die vorherigen Versionen von RDM an.


Frühere Versionen von RDM

RDMe 12.0 und älter (”RDMe”) verwendete ein Transaktionsprotokoll. Dies bedeutete, dass Daten normalerweise zweimal geschrieben wurden - zuerst in das Transaktionsprotokoll und dann in die eigentlichen Datenbankdateien. RDMe speicherte auch Elemente mit fester Länge, und in einigen Fällen mussten zusätzliche Inhalte an anderer Stelle separat gespeichert werden. Dieses Design führte zu Platzverschwendung, einem zusätzlichen Aufwand, wenn der Inhalt aufgeteilt werden musste, und war im Allgemeinen nicht sehr flexibel. Aufgrund der Datensätze mit fester Länge war es auch nicht sinnvoll, die Daten zu komprimieren.

 

Um diese Probleme zu beheben, implementierte RDM 14.0 Datensätze mit variabler Größe und Aktualisierungen mithilfe von "Copy on Write". Die Datenbankdateien wurden in sogenannte "Pack-Dateien" aufgeteilt. Eine Aktualisierung des Pakets wurde immer mit "Kopieren beim Schreiben" durchgeführt. RDM 14.0 hat jedoch keine vollständige rekursive "Kopie beim Schreiben" durchgeführt. Stattdessen stützte es sich auf einen Schlüsselwertspeicher (ID-Index), wenn Inhalte von einem Ort im Paket an einen anderen Ort verschoben wurden.

 

Dieses Design hatte seine eigenen Probleme. Der ID-Index verfolgte nicht genutzten Speicherplatz. Diese Nachverfolgung und die Datenstrukturen, die zur effizienten Nutzung des nicht genutzten Speicherplatzes erforderlich sind, erwiesen sich als recht teuer. Es verhinderte auch die Wiederverwendung von Speicherplatz in Kombination mit Massenschreiben. Die E / A-Leistung war ebenfalls alles andere als optimal, da Daten in Seiten geschrieben wurden, wenn nur ein Bruchteil der Seite aktualisiert wurde. 

 

Für diesen Entwurf wurde auch ein Transaktionsprotokoll für den ID-Index benötigt, das in das Paket für RDM 14.1 integriert wurde. Das Leeren des ID-Index war ebenfalls relativ teuer, was zu einem möglicherweise langsamen Öffnen und Schließen der Datenbank führte. Diese Probleme machten dieses Design für Anwendungen wie die ungeeignet REST-APIDies setzt voraus, dass die Datenbank für jede einzelne Anforderung geöffnet und geschlossen wird.

 

RDM 14.2 verfolgte einen etwas anderen Ansatz als RDM 14.1. Im folgenden Abschnitt werden wir hauptsächlich das 15.0-Design diskutieren, das viele Merkmale mit dem 14.2-Design sowie einige Merkmale mit dem 14.1-Design teilt.


RDM 15.0

Zwei Prinzipien

RDM 15.0 basiert auf zwei Prinzipien.

 

Das erste Prinzip, auf das wir uns verlassen, ist das vollständig rekursive "Copy on Write". Dies bedeutet, dass die in RDM 15.0 verwendete persistente Datenstruktur ein Baum (oder ein Baum von Bäumen, abhängig von der Abstraktionsebene) ohne Verwendung eines ID-Index ist. Es werden zwei Baumstrukturen verwendet: B-Bäume und R-Bäume. Die Datenbank verfügt über einen Baum für jeden im Schema definierten Schlüssel, es werden jedoch auch andere Bäume benötigt. Die Details hierzu gehen über den Rahmen dieses Artikels hinaus. Zum Abschluss dieser Diskussion erwähnen wir, dass es zum Zusammenbinden all dieser Bäume auch einen Hauptbaum gibt, der Verweise auf die Wurzelknoten der anderen Bäume enthält.

 

Das zweite Prinzip, auf das wir uns verlassen, besteht darin, immer an das Ende der letzten Packdatei anzuhängen.

Daher werden Packdateien niemals in der Mitte aktualisiert. Dies bedeutet, dass teure Updates in der Mitte, in denen nur ein kleiner Teil einer Seite aktualisiert wird, vermieden werden und auch kein freier Speicherplatz verwaltet werden muss. Auf Speicherplatz, auf den nicht mehr verwiesen wird, wird einfach nicht zugegriffen.


Anhängen und Schreiben von Änderungen "Bottom Up"

Aus diesen beiden Prinzipien ergeben sich einige Implikationen. Eine Implikation, die natürlich folgt, ist, dass alle Aktualisierungen durchgeführt werden müssen, indem sie an das Ende des Pakets angehängt werden. RDM schreibt eine Transaktion fest, indem zuerst neue und aktualisierte Elemente geschrieben werden, die keine direkten oder indirekten Verweise auf andere aktualisierte Elemente haben, gefolgt von Baumknoten, die auf sie verweisen, ihren übergeordneten Baumknoten, ihren Großelternbaumknoten usw. bis zum Stammknoten von Der Haupt-B-Baum wurde geschrieben.

 

Dieses Design bedeutet, dass zusätzliche Knoten geschrieben werden müssen, obwohl ansonsten keine Änderungen an ihnen vorgenommen wurden. Dies ist normalerweise kein Problem bei großen Transaktionen, bei denen es wahrscheinlicher ist, dass mehrere Aktualisierungen auf demselben B-Tree-Knoten erfolgen. Andererseits kann der zusätzliche Aufwand für kleine Transaktionen mit nur wenigen Änderungen erheblich sein. Die beste Leistung kann für Anwendungsfälle erwartet werden, die Zeitreihen oder umfassen runde Tische.


Schnappschuss

Mit rekursivem "Copy on Write" Schnappschüsse kann sehr effizient implementiert werden. Wenn ein Snapshot angefordert wird, kann der aktuelle Stammknoten des Haupt-B-Baums vom Client verwendet werden, der den Snapshot anfordert, und seine Ansicht der Daten wird von dem abgeleitet, was von diesem Knoten aus erreicht werden kann. Der einzige Unterschied zwischen einem Snapshot und einem Lesevorgang mit Lesesperren besteht darin, dass ein Client, der eine Lesesperre anfordert, Aktualisierungen der Tabellen blockiert, für die die Lesesperren angefordert werden, während ein Snapshot dies nicht tut. Für den Snapshot sind keine weiteren zusätzlichen teuren internen Datenstrukturen erforderlich. Der Client, der den Snapshot anfordert, kann Anforderungen für Inhalte vom Transactional File Server (TFS) einfach genau so verarbeiten, wie es bei einem normalen Lesevorgang mit Sperren der Fall wäre. Es erhält einen Haupt-B-Tree-Stammknoten und fordert basierend auf den darin enthaltenen Referenzen andere Knoten vom TFS an.

 

Daher eignet sich das Pack-Dateiformat mit Copy-on-Write gut für Snapshots. Wenn ein Snapshot angefordert wird, können alte Daten im Paket referenziert werden. Vom Standpunkt der Implementierung von Packdateien aus müssen wir nur sicherstellen, dass Packdateien, deren Daten für einen Snapshot sichtbar sind, nicht gelöscht werden.


Haltbarkeit

Da Daten nur an das Ende der letzten Packdatei angehängt werden, deren Dateiformat sorgfältig entworfen wurde, kann die Haltbarkeit in den meisten Fällen einfach durch Synchronisieren der letzten Packdatei erreicht werden. Dies hat einige Leistungsvorteile im Vergleich zu anderen Datenbanken, die mehrere Dateien synchronisieren müssen, einschließlich der älteren Versionen von RDM. 

 

Es stellt sich heraus, dass die meisten Synchronisierungen weggelassen werden können, wenn keine Haltbarkeit erforderlich ist. Ein Systemabsturz kann in diesem Fall zu Datenverlust führen. Da wir jedoch nur an eine Datei anhängen, sollten alle Daten, auf die von diesem Stammknoten verwiesen wird, gültig sein, wenn ein Haupt-B-Tree-Stammknoten gefunden wird. Dies setzt eine Dateisystemimplementierung voraus, die keine Blöcke in der Mitte einer Datei verliert, wenn nur an diese Datei angehängt wird. Es gibt eine Vorsichtsmaßnahme, die RDM treffen muss, damit dies funktioniert: Jedes Mal, wenn eine neue Packdatei angefordert wird, muss die vorherige Packdatei synchronisiert werden (und unter Linux und Unix müssen wir auch das Verzeichnis synchronisieren). Dies stellt sicher, dass kein Verweis von einer Packdatei auf eine vorherige Packdatei verloren geht.

 

Wir haben auch einen unsicheren Modus implementiert, in dem wir Packdateien überhaupt nicht synchronisieren. Dieser Modus sollte nur verwendet werden, wenn der Verlust von Daten in der Datenbank kein Problem darstellt oder garantiert werden kann, dass das Betriebssystem nicht heruntergefahren wird oder abstürzt, ohne Dateien zu synchronisieren. Es ist in Ordnung, dass die Datenbank abstürzt, da sich der geschriebene Inhalt im Dateisystem-Cache befindet. Beachten Sie, dass dies bei einigen eingebetteten Systemen, bei denen das Dateisystem im Benutzerbereich implementiert ist, möglicherweise nicht der Fall ist.

 

Für die Wiederherstellung wurde das Pack-Dateiformat so gestaltet, dass die Pack-Datei sowohl vorwärts als auch rückwärts gelesen werden kann. Für jedes 64 KB gibt es spezielle Wiederherstellungsinformationen, mit denen die Datei vorwärts und rückwärts gescannt werden kann, ohne dass die gesamte Datei von Anfang an gelesen werden muss. Diese Eigenschaft ist wichtig für eine effiziente und zuverlässige Wiederherstellung. Die Wiederherstellung schreibt nichts in das Paket, sondern findet den letzten Haupt-B-Tree-Stammknoten und überprüft das Ende des Pakets. Wenn festgestellt wird, dass sich eine Datenbank in einem bestimmten unvollständigen Zustand befindet, wird eine neue Packdatei erstellt. Dies bedeutet einfach, dass bei Abstürzen möglicherweise Inhalte in den Packdateien verbleiben, auf die der Haupt-B-Tree-Stammknoten nicht direkt oder indirekt verweist.

 

Das Pack-Dateiformat ermöglicht das parallele Aktivieren mehrerer Aktualisierungstransaktionen. Wenn sie jedoch festgeschrieben werden, wechselt das Anhängen an die Pack-Datei zwischen den derzeit festgeschriebenen Transaktionen. Eine kleine Transaktion kann möglicherweise alle ihre Daten in einem Block anhängen, während größere Transaktionen abwechselnd ihre Daten schreiben müssen. Der Haupt-B-Baum muss ausschließlich geschrieben werden, und jedes Mal müssen Änderungen von anderen Aktualisierungstransaktionen oder dem Vakuumer (ein Garbage Collector, den wir später behandeln) in die Änderungen für die jeweilige Transaktion integriert werden.


Laufzeit-Caching

Das alte Design mit dem ID-Index sowie Implementierungen, die auf Elementen fester Größe basieren, erforderten Daten für eine bestimmte Tabelle, die sich im Laufzeitcache befand, um jedes Mal gelöscht zu werden, wenn ein anderer Client Aktualisierungen an derselben Tabelle vornahm. Mit dem RDM 15.0-Design müssen keine Daten gelöscht werden. Der Laufzeitcache sucht Daten immer anhand der Packadresse und findet daher garantiert die richtigen Daten, wenn sie zwischengespeichert werden. Dies bedeutet, dass Daten möglicherweise länger im Laufzeitcache verbleiben können, was möglicherweise die Leistung erhöht.


Parallelität und direktes Lesen und Schreiben

Das alte Design mit dem ID-Index erlaubte es nicht, Operationen parallel auszuführen. Das RDM 15.0-Design, das Copy-on-Write verwendet, ermöglicht die parallele Ausführung der meisten Vorgänge von verschiedenen Clients. Das Dateiformat ermöglicht sogar die parallele Ausführung der meisten Dateivorgänge von verschiedenen Prozessen auf derselben Maschine, die direkt in die Pack-Dateien lesen und schreiben, ohne mit dem TFS zu kommunizieren. Dieser Ansatz führt zu einer höheren Leistung.


Staubsaugen

Während das RDM 15.0-Design viele Vorteile hat, wie oben beschrieben, hat es einen Hauptnachteil. Da wir nur an das Ende des Pakets anhängen, wird es dadurch auf unbestimmte Zeit wachsen. Um dieses Problem zu beheben, führen wir einen Speicherbereinigungsprozess aus, der als "Staubsaugen" bezeichnet wird. Das Staubsaugen wird in a separater Artikel.


Fazit

Wir haben festgestellt, dass das Dateiformat für RDM 15.0 flexibel ist und sich gut für Snapshot-Isolation, Parallelität, geringen Speicherbedarf und schnelle Wiederherstellung eignet. Wir empfehlen Ihnen, weiterzulesen Snapshot-Isolation und Staubsaugen. Genießen! 

 

von Sverre Hvammen Johansen und Daigoro Toyama