Globals sind Datenspeicher-Merge, Bäume. Teil 1

Echte Datenbank-Merge, Globals, sind schon lange bekannt, aber bisher können nur wenige sie effektiv nutzen oder besitzen dieses Superwerkzeug überhaupt nicht.

Wenn Sie Globals für die Aufgaben verwenden, bei denen sie wirklich gut sind, können Sie herausragende Ergebnisse erzielen. Entweder in der Leistung oder in der Vereinfachung der Lösung der Aufgabe (1, 2).

Globals sind eine spezielle Methode zur Speicherung und Verarbeitung von Daten, ganz anders als Tabellen in SQL. Sie erschienen 1966 in der Sprache M(UMPS) (evolutionäre Entwicklung - Caché ObjectScript, auch bekannt als COS) in medizinischen Datenbanken und werden bis heute dort aktiv verwendet, haben sich aber auch in andere Bereiche verbreitet, in denen Zuverlässigkeit und hohe Leistung gefordert sind: Finanzen, Trading usw.

Globals in modernen DBMS unterstützen Transaktionen, Protokollierung, Replikation, Partitionierung. Das heißt, auf ihnen können moderne, zuverlässige, verteilte und schnelle Systeme aufgebaut werden.

Globals schränken Sie nicht auf die Grenzen des relationalen Modells ein. Sie geben Freiraum für die Entwicklung von Datenstrukturen, die auf spezifische Aufgaben optimiert sind. Für viele Anwendungen kann die sinnvolle Nutzung von Globals wirklich eine geheime Waffe sein, die eine Leistung bietet, von der Entwickler relationaler Anwendungen nur träumen können.

Globals als Methode zur Datenspeicherung können in vielen modernen Programmiersprachen verwendet werden, sowohl in Hoch- als auch in Niedrigsprachen. Daher werde ich mich in diesem Artikel genau auf Globals konzentrieren und nicht auf die Sprache, aus der sie einst hervorgingen.

2. Wie Globals funktionieren

Lassen Sie uns zunächst verstehen, wie Globals funktionieren und wo ihre Stärken liegen. Globals können aus verschiedenen Perspektiven betrachtet werden. In diesem Teil des Artikels werden wir sie als Bäume betrachten. Oder als hierarchische Datenspeicher.

Einfach ausgedrückt ist ein Global ein persistentes Array. Ein Array, das automatisch auf der Festplatte gespeichert wird.
Es ist schwer, sich etwas Einfacheres zur Speicherung von Daten vorzustellen. Im Code (in den Sprachen COS/M) unterscheidet es sich nur durch das Symbol ^ vor dem Namen.

Um Daten im Globalen zu speichern, muss man keine SQL-Abfragesprache lernen; die Befehle zu ihrer Handhabung sind sehr einfach. Man kann sie in einer Stunde lernen.

Lass uns mit dem einfachsten Beispiel beginnen. Ein einstufiger Baum mit 2 Ästen. Die Beispiele sind in COS geschrieben.

Set ^a("+7926X") = "John Sidorov"
Set ^a("+7916Y") = "Sergey Smith"

Beim Einfügen von Informationen in das Globale (Befehl Set) passieren automatisch 3 Dinge:

1. Speichern der Daten auf der Festplatte.
2. Indizierung. Das, was in der Klammer steht, fungiert als Schlüssel (in der englischen Literatur – „subscript“), und rechts vom Gleichheitszeichen steht der Wert („node value“).
3. Sortierung. Die Daten werden nach dem Schlüssel sortiert. Bei einer Traversierung des Arrays wird das erste Element "Sergey Smith" und das zweite "John Sidorov" sein. Beim Abrufen der Benutzerliste aus dem Globalen benötigt die Datenbank keine Zeit für die Sortierung. Außerdem kann man eine sortierte Liste abgerufen werden, beginnend mit jedem Schlüssel, selbst mit nicht existierenden (die Ausgabe beginnt mit dem ersten tatsächlichen Schlüssel, der nach dem nicht existierenden kommt).

All diese Operationen geschehen unglaublich schnell. An meinem Heimcomputer erreichte ich Werte von bis zu 750.000 Einfügungen/Sekunde in einem einzigen Prozess. Auf Mehrkernprozessoren können die Werte sogar erreichen Zehntausende Millionen Einfügungen/Sekunde.

Natürlich sagt die Geschwindigkeit des Einfügens alleine wenig aus. Man kann zum Beispiel sehr schnell Informationen in Textdateien schreiben – so soll es angeblich bei der Verarbeitung von Visa funktionieren. Aber im Fall der Globals erhalten wir ein strukturiertes, indiziertes Speicherformat, mit dem man anschließend einfach und schnell arbeiten kann.

• Die größte Stärke der Globals ist die Geschwindigkeit des Einfügens neuer Knoten.
• Die Daten im Globalen sind immer indiziert. Ihre Traversierung sowohl auf einer Ebene als auch in die Tiefe des Baumes erfolgt immer schnell.

Lass uns dem Globalen noch einige Zweige der zweiten und dritten Ebene hinzufügen.

Set ^a("+7926X", "city") = "Moskau"
Set ^a("+7926X", "city", "street") = "Req Square"
Set ^a("+7926X", "age") = 25
Set ^a("+7916Y", "city") = "London"
Set ^a("+7916Y", "city", "street") = "Baker Street"
Set ^a("+7916Y", "age") = 36

Es ist offensichtlich, dass auf der Basis von Globals mehrstufige Bäume aufgebaut werden können. Der Zugriff auf jeden Knoten erfolgt nahezu augenblicklich aufgrund der automatischen Indizierung beim Einfügen. Und auf jeder Ebene des Baumes sind alle Äste nach dem Schlüssel sortiert.

Wie man sieht, kann die Information sowohl im Schlüssel als auch im Wert gespeichert werden. Die gesamte Länge des Schlüssels (Summe der Längen aller Indizes) kann bis zu 511 Byte, und die Werte 3,6 MB für Caché. Die Anzahl der Ebenen im Baum (Anzahl der Dimensionen) – 31.

Ein weiterer interessanter Punkt. Es ist möglich, einen Baum zu erstellen, ohne Werte für die Knoten der oberen Ebenen festzulegen.

Set ^b("a", "b", "c", "d") = 1
Set ^b("a", "b", "c", "e") = 2
Set ^b("a", "b", "f", "g") = 3

Leere Kreise sind Knoten, denen kein Wert zugewiesen ist.

Um Globals besser zu verstehen, vergleichen wir sie mit anderen Bäumen: mit Gartenbäumen und mit den Bäumen von Dateisystemen.

Vergleichen wir die Bäume in Globals mit den uns am vertrautesten hierarchischen Strukturen: mit normalen Bäumen, die in Gärten und Feldern wachsen, sowie mit Dateisystemen.

Wie wir bei Gartenbäumen sehen, befinden sich die Blätter und Früchte nur an den Enden der Äste.
In Dateisystemen wird die Information nur an den Enden der Äste gespeichert, die die vollständigen Dateinamen sind.

Hier ist die Datenstruktur eines Globals.

Unterschiede:

1. Innere Knoten: Informationen in Globals können in jedem Knoten gespeichert werden, nicht nur an den Enden der Äste.
2. Äußere Knoten: In Globals müssen an den Enden der Äste Werte definiert sein, in FS-Bäumen und Gartenbäumen hingegen nicht.

In Bezug auf einige innere Knoten kann man sagen, dass die Struktur eines Globals eine Übermenge der Struktur von Namensbäumen in Dateisystemen und Gartenbäumen ist. Das heißt, sie ist flexibler.

Im Allgemeinen stellt ein Global dar einen geordneten Baum mit der Möglichkeit, Daten in jedem Knoten zu speichern..

Um die Funktionsweise von Globals besser zu verstehen, stellen wir uns vor, was wäre, wenn die Ersteller von Dateisystemen einen Ansatz ähnlich dem der Globals zur Speicherung von Informationen verwendet hätten?

1. Beim Löschen einer einzelnen Datei im Verzeichnis würde automatisch das Verzeichnis sowie alle übergeordneten Verzeichnisse gelöscht werden, die nur dieses kürzlich gelöschte Verzeichnis enthalten.
2. Die Notwendigkeit für Verzeichnisse wäre entfallen. Es wären einfach Dateien mit Unterdateien und Dateien ohne Unterdateien vorhanden. Im Vergleich zu einem normalen Baum würde jeder Ast zu einer Frucht werden.

   
   

3. Sowas wie die Datei README.txt wäre möglicherweise entfallen. Alles, was man über den Inhalt eines Verzeichnisses sagen müsste, könnte in die Datei des Verzeichnisses selbst geschrieben werden. Im Pfadraum wäre der Dateiname nicht von dem Verzeichnisnamen zu unterscheiden, daher könnte man sich mit nur Dateien begnügen.
4. Die Geschwindigkeit beim Löschen von Verzeichnissen mit verschachtelten Unterverzeichnissen und Dateien würde erheblich steigen. In der Vergangenheit gab es viele Artikel über die lange und schwierige Aufgabe, Millionen kleiner Dateien zu löschen.1, 2). Allerdings würden ein Pseudo-Dateisystem auf Globalen Sekunden oder deren Bruchteile benötigen. Als ich das Entfernen von Teilbäumen auf meinem Heimcomputer testete, wurden in einer Sekunde 96-341 Millionen Knoten aus einem zweistufigen Baum auf einer HDD (nicht SSD) gelöscht. Dabei geht es um das Entfernen eines Teils des Baums und nicht einfach um die gesamte Datei mit den Globalen.

Das Entfernen von Teilbäumen ist eine weitere Stärke von Globalen. Dafür ist keine Rekursion erforderlich. Dies geschieht unglaublich schnell.

In unserem Baum könnte dies mit dem Befehl Kill.

Kill ^a("+7926X")

Um besser zu verstehen, welche Aktionen uns mit den Globalen zur Verfügung stehen, gebe ich eine kurze Tabelle an.

Hauptbefehle und Funktionen zur Arbeit mit Globalen in COS

Set
Setzen von Zweigen bis zum Knoten (wenn sie noch nicht definiert sind) und den Wert des Knotens

Merge
Kopieren eines Teilbaums

Kill
Löschen eines Teilbaums

ZKill
Löschen des Wertes eines bestimmten Knotens. Der Teilbaum, der aus dem Knoten hervorgeht, bleibt unberührt

$Query
Vollständige Durchquerung des Baumes mit Vertiefung

$Order
Durchqueren der Äste eines bestimmten Knotens

$Data
Überprüfen, ob der Knoten definiert ist

$Increment
Atomares Inkrementieren des Wertes eines Knotens. Um Lese- und Schreibvorgänge zu vermeiden, für ACID. In letzter Zeit wird empfohlen, zu wechseln zu $Sequence

Vielen Dank für Ihre Aufmerksamkeit, wir sind bereit, Ihre Fragen zu beantworten.

Haftungsausschluss: Dieser Artikel und meine Kommentare dazu sind meine persönliche Meinung und stehen nicht im Zusammenhang mit der offiziellen Position der InterSystems Corporation.

Fortsetzung Globals – Schätze zur Datenspeicherung. Bäume. Teil 2. Sie erfahren, welche Datentypen auf Globalen dargestellt werden können und bei welchen Aufgaben sie den größten Gewinn bringen.

Quelle: habr.com