Seite 4: Graph-Abfragen auf nicht-nativen Graphdatenbanken

Inhaltsverzeichnis

Was aber passiert, wenn andere DBMS-Designs an Graphworkloads angepasst werden sollen?
Die kurze Betrachtung klassischer Datenstrukturen ist stark vereinfacht, zeigt aber deutlich, dass jede Datenstruktur für einen bestimmten Zweck ausgelegt ist und es keine Datenstruktur gibt, die universell einsetzbar ist. Beim Design eines DBMS gilt es, die Datenstrukturen so auszuwählen, dass sie sowohl Datenmodell als auch Abfrage-Workload bestmöglich unterstützen. Hierbei stehen recht unterschiedliche Strukturen für spaltenorientierte, relationale oder dokumentbasierte Systeme zur Verfügung. Das Systemdesign wird dann soweit optimiert, dass es für das gewählte Datenmodell möglichst effizient ist. Die resultierende Software ist nativ: ausgelegt auf Spalten, Dokumente oder Tabellen. Aber sie ist nicht nativ für Graphen.

Um Graph-Workloads in diesen nicht-nativen Graphdatenbanken unterstützen zu können, müssen wir sie in gewisser Weise erweitern, indem wir Graphfeatures in irgendeiner Form dem nativen Modell „aufpfropfen“. Bei den nicht-nativen Datenbanken gibt es zwei Varianten: Die eine Variante setzt eine Graph-API auf ein vorhandenes Datenbanksystem auf. Die andere Variante verwendet eine Engine mit multimodaler Semantik auf einem darunterliegenden nativen Modell.

Wir sollten das nicht als reine Implementierungsdetails beiseiteschieben. Durch die Implementierung eines DBMS ist das System für die nativen Workloads gut geeignet, für andere Workloads (die nicht-nativen Workloads) ist es jedoch völlig ungeeignet. Das lässt sich deutlich an den folgenden Beispielen aufzeigen, bei denen gängige, nicht-graphbasierte Modelle zu einer Graphdatenbank umgewandelt werden.

Aufsetzen eines Graph-API auf eine spaltenorientierte Datenbank

Gängige spaltenorientierte Datenmodelle stellen nativ ein verschachteltes Hashmap-Datenmodell zur Verfügung. Üblicherweise basiert ihre Cluster-Architektur auf einer Hash-Ring-Struktur und sind eine einfache Möglichkeit, Daten innerhalb eines Clusters zu verteilen. Sie lassen sich auch fehlertolerant implementieren.

Soll eine spaltenorientierte Datenbank benutzt werden um wie eine Graphdatenbank zu arbeiten, wird eine Graphschicht implementiert. Die hierzu verwendete Bibliothek stellt eine Graph-API und eine Abfragesprache zur Verfügung und wird durch einen Übersetzungscode auf der zugrundeliegenden Datenbank abgebildet.

Im Allgemeinen weist eine Hashmap eine gute Komplexität O(1) für Lese- und Schreibzugriffe pro atomare Einheit auf. Eine gute Hash-Funktion versucht jedoch auch, ähnliche Daten möglichst weit zu verteilen, um Konflikte zu vermeiden und Ausfallsicherheit zu erhöhen. Leider verringert sich dadurch die Lokalität.

In einem Graphen ist Lokalität entscheidend: Die Traversierungen erfolgen entlang von Beziehungen zu benachbarten Knoten. Daher ist es von großem Vorteil, wenn diese Konten eine Lokalität für einen effizienten Speicherzugriff aufweisen.

Jede Suche mit der Komplexität O(1) in einem spaltenorientierten Modell wird zu einer das Netzwerk übergreifenden Operation und somit in der Praxis technisch sehr aufwendig. Die Folge: Die Graph-Traversierungsleistung ist oft schlecht und es fallen für eine recht bescheidene Performance hohe Hardwareinvestitionen an. Selbst wenn ausgefeilte Mappings zwischen API und der zugrundeliegenden Datenbank zu einer radikalen Denormalisierung der Daten führen, um die Lokalität zu erhalten, sind ab einem bestimmten Punkt die Grenzen dieser Denormalisierung erreicht.

Neo4j kennt die Probleme aus eigener Erfahrung. Bei frühen Implementierungen (in den Jahren 2000 - 2003) war die Neo4j Graphdatenbank ein nicht-natives System, das mit einer Graph-API arbeitete, die auf einer relationalen Datenbank aufsetzte. Wenn Abfragen mit einer Traversierungsstiefe von etwa drei Ebenen oder mehr anfielen, brach die Leistung extrem ein. Das gab den Anstoß, eine wirklich native Graph-Engine zu entwickeln.

Da die zugrundeliegende Fehlertoleranz-Infrastruktur so ausgelegt ist, dass einzelne Datenwerte (Schlüssel+Wert) und keine Graphen gespeichert und abgerufen werden, kann es in solchen Systemen schon im Normalbetrieb schnell vorkommen, dass Daten inkonsistent werden. Das typische Konsistenzmodell ist für Graphen einfach nicht leistungsfähig genug.

Dokumentendatenbanken mit Graph-Abfrageoperator

Ein zweites Beispiel ist eine Dokumentendatenbank, die zu einer Graphdatenbank umgewandelt werden soll. Gängige Dokumentendatenbanken verwenden B-Bäume, um Dokumente im DBMS zu indizieren, ähnlich wie ein modernes Dateisystem. Als baumbasiertes System liegt beim Nachschlagen eines Dokuments die Komplexität O(log n) vor. Dies mag für einmalige Such- oder Schreibvorgänge in Ordnung sein, erreicht jedoch die Komplexität O(m log n), wenn Indizes verwendet werden, um das Traversieren eines Graphen von m Schritten nachzuahmen. Die Traversierungsleistung leidet bereits ab einer Tiefe von zwei oder drei Ebenen stark unter dieser Komplexität.

Einige Dokumentenspeicher verwenden einen Graph-Lookup-Operator, damit Daten auf grundlegende Weise miteinander verbunden werden können. Bei näherer Überprüfung wird jedoch klar, dass die Implementierung das Äquivalent eines Index-Lookups für jeden "Fremdschlüssel" durchführt, um Graphelemente zu verbinden und damit die schon erwähnten Kosten auftreten.

Der größte Nachteil bei der Verwendung von dokumentbasierten DBMS für andere Zwecke ist jedoch die Tatsache, dass die zugrundeliegende DBMS-Engine nichts über Beziehungen weiß (von Graphen ganz zu schweigen). Da sie für Dokumente ausgelegt wurde, kann ein Benutzer die Graphstruktur leicht beschädigen (indem er defekte Verweise hinterlässt, das Äquivalent zu "Not-Found" Links im WWW). Die Engine ist dann noch nicht einmal in der Lage, zur Aufrechterhaltung oder Überprüfung der Konsistenz einzugreifen. Im Laufe der Zeit wird der Graph auf diese Weise zu einer Insel von verwaisten und defekten Verbindungen, die seinen eigentlichen Mehrwert völlig zunichtemachen (Abb. 4).