Suche
Einführung

Graphendatenbanken, NoSQL und Neo4j

Peter Neubauer

Von den unterschiedlichen Datenmodellen ist seit den 80er Jahren das relationale Modell mit den zugehörigen relationalen Datenbanken die absolut vorherrschende Strömung mit Vertretern wie OracleMySQL undMSSQL. In letzter Zeit häufen sich jedoch die Fälle, bei denen die Verwendung von relationalen Datenbanken zu Schwierigkeiten sowohl aufgrund der Defizite und Probleme in der Datenmodellierung als auch der Skalierbarkeit über mehrere Maschinen und große Datenmengen in der Praxis führt.

Es gibt zwei Trends, die dieses Problem in letzter Zeit immer mehr ins Zentrum der Aufmerksamkeit der internationalen Entwicklergemeinde gerückt haben:

  • Die exponentielle Zunahme des Volumens der von Anwendern, Systemen und Sensoren produzierten Datenmengen und deren Konzentration auf große verteilte Systeme (Amazon, Google und andere Cloud-Systeme)
  • Die zunehmende Abhängigkeit, Komplexität und Vernetzung von Daten, beschleunigt durch das Internet, Web 2.0, soziale Netzwerke und offene und standardisierte Schnittstellen zu Daten aus verschiedensten Systemen

Die relationalen Datenbanken sind diesen Entwicklungen in zunehmendem Maß nicht mehr gewachsen. Das hat zu einer Flut von alternativen Techniken für die Lösung spezieller Datenprobleme geführt, die alternativ oder zusammen mit den bestehenden SQL-Datenbanken angewendet werden können – auch als Polyglot Persistence bekannt. Es gibt schon lange alternative Datenbanken wie die Objektdatenbanken, Hierarchische Datenbanken (z. B. LDAP) und viele andere. Jedoch sind in letzter Zeit eine eine Reihe neuer Projekte gestartet worden, die unter dem Namen „NoSQL-Datenbanken“ bekannt sind.

Im folgenden Artikel soll eine Einführung in die Funktionsweise von Graphendatenbanken und ihre Positionierung im Umfeld der NoSQL-Bewegung gegeben werden. Der zweite Teil beleuchtet dann die Neo4j-Graphendatenbank ein wenig näher.

Das NoSQL-Umfeld

NoSQL (Not Only SQL) ist eigentlich eine sehr weite Bezeichnung für eine Gruppe von Persistenzmodellen und Datenbanken, die nicht das relationale Datenmodell anwenden und nicht SQL als Abfragesprache haben.

Kurz gesagt kann man die NoSQL-Szene aufgrund ihrer unterschiedlichen Datenmodelle in vier Kategorien einteilen:

  • Key-Value-Datenbanken
  • BigTable-Implementationen
  • Dokumentendatenbanken
  • Graphendatenbanken

Bei Key-Value-Systemen wie Voldemort oder Tokyo Cabinet ist die kleinste Modellierungseinheit das Key-Value-Paar, die BigTable-Klone hantieren viele Datentupel mit variablen Attributen, bei Dokumentendatenbanken wie CouchDB und MongoDB das Dokument. Graphendatenbanken sehen alle Daten als eine große vernetzte Struktur.

Hier sollen vor allem zwei Aspekte der Einteilung von NoSQL-Datenbanken aufgegriffen werden – die Skalierbarkeit und die Komplexität.

[ header = Seite 2: Skalierbarkeit ]

1. Skalierbarkeit
CAP: ACID vs. BASE

Um die referenzielle Integrität der Daten zu gewährleisten, sind die allermeisten klassischen Datenbanken transaktionsbasiert. Das gewährleistet die Konsistenz der Daten in allen Situationen der Datenhaltung. Die transaktionalen Charakteristiken sind auch unter dem Namen ACID (Atomicity, Consistency, Isolation, Durability) bekannt. Da ACID Datenkonsistenz voraussetzt, wird jedoch die Skalierung dieser Systeme ein Problem. Es kommt zu einem Konflikt der unterschiedlichen Zugänglichkeitsaspekte in verteilten Systemen, der nicht vollständig zu lösen ist – bekannt alsCAP-Theorem:

  • Strong Consistency: Alle Klienten sehen die gleichen Daten, auch bei Datenänderungen, z. B durch das Two-Phase-Commit-Protokoll (XA-Transaktionen), siehe ACID
  • High Availability: Alle Klienten können immer wenigstens eine Kopie der Daten finden, auch wenn ein Teil der Maschinen aussetzt
  • Partition-Tolerance: Das Gesamtsystem behält seine Eigenschaften, auch wenn es auf mehrere Maschinen verteilt wird.

Das CAP-Theorem sagt, dass man nur zwei der drei Skalierungsaspekte gleichzeitig erreichen kann.

Abbildung 1

Um mit CAP in großen verteilten Systemen arbeiten zu können, hat man die unterschiedlichen CAP-Merkmale unter die Lupe genommen.

Viele NoSQL-Datenbanken haben vor allem Consistency gelockert, um hohe Erreichbarkeit und Partionierung (AP) liefern zu können. Herausgekommen sind so genannte BASE-Systeme (Basically Available, Soft-state, Eventually consistent), die keine Transaktionen im klassischen Sinn haben und Einschränkungen im Datenmodell einführen, um bessere Partitionierungsmechanismen zu ermöglichen. Eine tiefere Erklärung von CAP, ACID und BASE gibt es in dieser Einführung.

2. Komplexität

Ein Protein Homology Network, Courtesy of Alex Adai: Institute for Cellular and Molecular Biology – University of Texas

Durch die zunehmende Vernetzung von sowohl Systemen als auch Daten kommt es zu mehr und mehr dichten Datenmengen, die nicht mehr einfach skaliert und aufgeteilt werden können, wie auch Todd Hoff bemerkt. Mehr Visualisierungen von komplexen Datenmengen gibt es bei Visual Complexity.

Das relationale Modell

Bevor man die RDBMS als nicht mehr zeitgemäß abtut, sollten wir nicht vergessen, dass einer der Gründe für den Erfolg der relationalen Datenbanksysteme darauf beruht, das man mit demrelationalen Datenmodell nach E.F. Codd im Prinzip alle Datenstrukturen ohne größeren Informationsverlust oder redundante Datenmengen abbilden kann – durch Normalisierung. Nachdem diese Modellierung erfolgt ist, können die Daten beliebig über SQL eingefügt und abgefragt werden und über unterschiedliche RDBMS-Implementierungen auf verschiedene Anwendungsgebiete optimiert gelagert werden (für z. B. OLTP, OLAP, Webanwendungen oder Reporting).

Soweit die Theorie, jedoch stoßen die RDBMS-Datenbanken in der Praxis schnell an die oben genannten CAP-Probleme und Grenzen hinsichtlich der performanten Abfrage über viele Joins, Skalierbarkeit, Evolution des Schemas, nicht einheitlich strukturierter Daten, Abbildung von Baumstrukturen, Hierarchien und Netzwerken u. v. a.

Auch stimmt dieses Modell oft nicht mit den heutigen Softwareentwicklungsparadigmen der Objektorientierung mit den dynamischen Typen von Skriptsprachen überein, auch bekannt als Object-relational Impedance Mismatch. Hier kommen ORM-Schichten wie Hibernate für Java mit mäßigem Erfolg zum Einsatz. Sie vereinfachen zwar die Entwicklung, liefern aber meist nicht optimale Performance. Besonders schwach strukturierte Daten werden oft als große Tabellen mit vielen Spalten mit meist leeren Inhalten (Sparse Tables) modelliert und haben schlechte Performance. In der Anwendung gibt es auch häufig Probleme mit der Segmentierung der Daten (Fetch Groups) für Teilobjektnetze.

[ header = Seite 3: Der Graph als Alternative zur relationalen Normalisierung ]

Der Graph als Alternative zur relationalen Normalisierung

Von den zu modellierenden Domänenmodellen ausgehend, gibt es zurzeit zwei vorherrschende Strukturen, um Daten ohne Informationsverluste oder Duplizierungen abzubilden: das relationale Modell sowie Graph- und Netzwerkstrukturen.

Während diese Strukturen theoretisch auch in RDBMS normalisierbar sind, hat doch das relationale Modell große Schwierigkeiten (vor allem in den in der Praxis eingesetzten RDBMS-Implementationen), rekursive Strukturen wie Dateienbäume und vernetzte Verhältnisse, wie soziale Relationen performant abzufragen. Jede Kante stellt mindestens einen Joint in der RDBMS dar, der in der Praxis eine Mengenoperation zwischen den Tupeln zweier Tabellen erfordert und somit sehr langsam ist.

Grundbegriffe für "labeled property graphs"

Es gibt bis jetzt noch kein allgemeingültiges Graphenmodell, jedoch einige Ansätze, wie das Allgemeine Graphenmodell. Im Allgemeinen werden alle Informationen in einem Graphen als

  • Knoten (auch Nodes order Vertices)
  • Kanten (auch Relationships, Edges) – mit Richtung und Typ (labeled and directed)
  • Eigenschaften (auch Properties, Labels) für sowohl Knoten als auch Kanten

abgebildet. Jeder Knoten und jede Kante kann verschiedene Attribute haben, was z. B. gut für wenig geordnete Daten wie anwendergenerierte Metadaten geeignet ist. Die Abbildung zeigt ein kleines Beispiel.

Ein kleiner Graph von Personen um TinkerPop

Die Anwendbarkeit und Relevanz der Graphentheorie ist nicht neu. Klassische Probleme wie das Travelling-Salesman-Problemgeodätische Verbindungen zwischen Punkten undZentralitätsprobleme wie PageRank, HITS und andere sind elegant lösbar durch die Anwendung von Graphalgorithmen, z. B. kürzester Pfad. Jedoch blieb die Anwendung dieser Theorien vielerorts auf die Forschung begrenzt wie etwa mit Pygr, da es in der Praxis keine produktionstauglichen Graphimplementierungen gab. In den letzten Jahren sind jedoch einige Systeme entwickelt worden, die sich für den 24/7-Einsatz eignen, z. B.

  • Neo4j – Open Source (AGPL), Java, Property-Graphenfokus
  • AllegroGraph, Closed Source, RDF-QuadStore
  • Sones – Closed Source, SOAP-Schnittstelle
  • Virtuoso – Closed Source, RDF TripleStore

Die folgende Abbildung zeigt eine grobe Klassifizierung der NoSQL-Kategorien hinsichtlich der Aspekte Skalierbarkeit und Komplexität.

Abbildung 5

Mehr zum Thema „Scaling to Size vs. Scaling to Complexity“ gibt es bei Emil Eifrems Blogeintrag zu diesem Thema.

Nun sind natürlich Graphendatenbanken nicht die alleinige Lösung für alle Probleme, genauso wenig wie RDBMS und alle anderen Persistenzlösungen. Entscheidend ist vor allem, welche Datenmengen und Datenstrukturen man modellieren will und welche Anforderungen hinsichtlich CAP stehen.

Die Hochskalierbarkeit als einzigen Masstab für die Anwendung von NoSQL-Datenbanken zu machen, ist oft weder notwendig noch wünschenswert, da z. B. Neo4j mit der heutigen Hardware ohne Probleme die Milliarden-Knotengrenze sprengt und so die gesamte Domäne in den meisten Fällen in einem Graph halten kann. Mehr zu Neo4J erfahren Sie im zweiten Teil dieser Artikelserie.

Peter Neubauer ist COO von Neo Technology. Peter ist Mitgründer einer Anzahl Java- und Graph-orientierter Open-Source-Projekte wie Neo4j, Gremlin, LinkedProcess, OPS4J, Qi4j und anderen. Peter ist unter peter@neotechnology.com erreichbar.
Geschrieben von
Peter Neubauer
Kommentare

Hinterlasse eine Antwort

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

Du kannst folgende HTML-Tags benutzen: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>