Neo4j – die High-Performance-Graphendatenbank

Peter Neubauer

Neo4j ist eine voll ACID-transaktionale Datenbank in Java (die .jar-Datei is ca. 500 KB groß), die alle Datenstrukturen als Netzwerke auf dem Dateisystem in einem optimierten Format speichert. Der Neo4j-Kernel ist ein sehr schneller Graphenmotor mit allen Eigenschaften, die man von einer RDBMS erwarten würde – ACID, 2PC-Transaktionen, XA-Unterstützung und so weiter. Neo4j ist im 24/7 Produktionseinsatz seit 2003 und liegt zurzeit in der frischen Version 1.0 vor. High Availability mittels Online-Backup und Master Slave Replication sind auch demnächst testfertig. Neo4j kann sowohl als selbständiger Server als auch als Embedded-Server konfiguriert werden.

Der Entwickler arbeitet direkt auf dem Graphenmodell mit einem Java-API, das die flexible Struktur exponiert, oder kann die Anbindungen an andere Programmiersprachen anwenden, so wie JavaScalaJRubyPythonClojure und unterschiedliche REST-Wrapper. Typische Charakteristiken für Neo4j sind Folgende:

Aber auch bei den „klassischen“ RDBMS-Anwendungen findet man häufig Graphen in Verzeichnisstrukturen mit freier Tiefe, Produktkonfigurationen, Sortimenten, Medienmetadaten. Semantic Trading, Fraud Detection in der finanziellen Industrie und anderen wieder.

Neo4j hat eine Menge von optionalen Komponenten, um z. B. über ein Metamodell mehr Struktur in den Graphen zu bringen, einen SAIL-kompatiblen RDF TripleStore zu implementieren oder gebräuchliche Algorithmen zu unterstützen.

In Fällen, in denen man Neo4j als einen separaten Server betreiben möchte, stehen sowohl JRuby– als auch Java-basierte REST-komponenten zur Verfügung. Das bietet sich bei z. B. Architekturen wie dem bisherigen LAMP-Modell an und eignet sich außerdem gut für HTTP-Memcached und Apache-basierte Caching-Komponenten.

High Performance?

Bei Benchmarks ist es sehr schwer, allgemeingültige Performanceaussagen zu treffen, da gerade bei der Hardware sehr viel von der jeweiligen Konfiguration, Lese- und Schreibgeschwindigkeit usw. abhängt. Neo4j hantiert ohne Probleme Graphen von mehreren Milliarden Knoten, Kanten und Eigenschaften. Es ist normal, mit Neo4j Leseleistungen von über 2000 Kantenschritten pro Millisekunde (also ca. 2 Millionen Schritte pro Sekunde) mit warmen Caches zu erreichen. Bei den untenstehenden Beispielen ist Neo4j bei einem Netzwerk von 1000 Personen und dem Freunde-meiner-Freunde-Problem schon 1000 Mal schneller als MySQL, der Unterschied steigt exponentiell mit der Größe des Graphen.

Der Vorteil ist hier, dass die Traversierung entlang der Kanten in Neo4j mit konstanter Geschwindigkeit unabhängig von der Größe des Graphen erfolgt. Es werden also keine Einbußen wegen größerer Setoperationen wie in den RDBMS-Joins gemacht. Neo4j lädt lazy, sodass Knoten und Relationen erst eingelesen werden, wenn man sie wirklich im ResultSet abfragt, was die Performance bei großen und tiefen (z. B. 1000 Kanten tief) Traversierungen optimiert.

Schreibgeschwindigkeiten hängen vor allem vom Seek-Speed des Dateisystems ab. SSD-Disks und ext3 sind eine gute Kombination und geben mit vollem ACID unter Leselast von 100 000 Operationen pro Sekunde.

[ header = Seite 2: Skalierbarkeit ]

Skalierbarkeit: Ein Beispiel – die Matrix
Der Graph

Wie schon vorher gesagt, stellen soziale Netzwerke nur einen Bruchteil der Anwendungsfälle von Graphen dar, sind aber sehr leicht verständlich. Um die Grundfunktionalität zu demonstrieren, wird nachstehend ein kleiner Graph aus dem Film Matrix erstellt, visualisiert mit dem Eclipse-RCP-basierten Neoclipse für Neo4j:

Abbildung 1

Der Graph ist mit dem Referenzknoten (meist der Knoten mit der ID 0) verbunden, um ohne Probleme von einem bekannten Startpunkt wieder in das Netzwerk zu finden. Das ist nicht notwendig, erweist sich aber in der Praxis als anwendbar.

Die Java-Implementierung sieht ungefähr folgendermaßen aus: Wir öffnen oder erstellen eine neue Neo4j-Datenbank im Verzeichnis „target/neo“:

EmbeddedGraphDatabase neodb = new 
EmbeddedGraphDatabase("target/neo");

Relationstypen können dynamisch erstellt oder mittels einer Java Enum vordefiniert werden:

RelationshipType KNOWS = DynamicRelationshipType.withName("KNOWS");

oder

enum Relationships implements RelationshipType { KNOWS, INLOVE, HAS_CODED, MATRIX }

Dann können wir zwei Knoten schaffen, jedem eine name-Eigenschaft geben und diese mit einer KNOWS-Relation verbinden:

enum Relationships implements RelationshipType { KNOWS, INLOVE, HAS_CODED, MATRIX }
Node neo = neodb.createNode();
node.setProperty("name", "Neo");
Node morpheus = neodb.createNode();
morpheus.setProperty("name", "Morpheus");
neo.createRelationshipTo(morpheus, KNOWS);

Wie schon gesagt, hat Neo4j volle Transaktionssemantik, sodass wir auch Rollback etc bekommen. Operationen werden also in einer Transaktion gekapselt:

Transaction tx = neodb.beginTx();
try {
Node neo = neodb.createNode();
...
tx.success();
} catch (Exception e) {
tx.failure();
} finally {
tx.finish();
}

Der gesamte Code zur Erstellung des Nodespace sieht folgendermaßen aus:

graphdb = new EmbeddedGraphDatabase("target/neo4j");
index = new LuceneIndexService(graphdb);
Transaction tx = graphdb.beginTx();
try {
Node root = graphdb.getReferenceNode();
// wir verbinden Neo mit dem Root-Knoten, um einen Eingang in den
// graphen zu haben.Nicht notwendig, aber praktisch.
neo = createAndConnectNode("Neo", root, MATRIX);
Node morpheus = createAndConnectNode("Morpheus", neo, KNOWS);
Node cypher = createAndConnectNode("Cypher", morpheus, KNOWS);
Node trinity = createAndConnectNode("Trinity", morpheus, KNOWS);
Node agentSmith = createAndConnectNode("Agent Smith", cypher, KNOWS);
architect = createAndConnectNode("The Architect", agentSmith, HAS_CODED);
//Trinity liebt Neo. Er weiss es aber erst nicht.
trinity.createRelationshipTo(neo, LOVES);
tx.success();
} catch (Exception e) {
tx.failure();
} finally {
tx.finish();
}

Zum Erstellen der Knoten und Kanten dient folgende Funktion:

private Node createAndConnectNode(String name, Node otherNode,
RelationshipType relationshipType) {
Node node = graphdb.createNode();
node.setProperty("name", name);
node.createRelationshipTo(otherNode, relationshipType);
index.index(node, "name", name);
return node;
} 

[ header = Seite 3: Wer sind Neos Freunde? ]

Wer sind Neos Freunde?

Neo4j’s API hat einige schnelle Java-Collection-orientierte Methoden, um einfache Fragen schnell beantworten zu können. Hier reicht ein Blick auf die Relationen von Neo, um diese Frage zu beantworten:

tx = neodb.beginTx();
for (Relationship rel : neo.getRelationships(KNOWS)) {
Node friend = rel.getOtherNode(neo);
System.out.println(friend.getProperty("name"));
}
tx.success();
tx.finish();

Dem entsprechend gibt es Morpheus als einzigen Freund. Die eigentliche Kraft von Neo4j kommt jedoch mit der Anwendung des Traverser API zum tragen, das sehr viel komplexere Wegbeschreibungen und Filter zulässt. Das API besteht aus einem Traverser, der einen StopEvaluator nach dem Ende des Weges und einen ReturnableEvaluator nach der Relevanz des aktuellen Knotens für das Ergebnis befragt. Außerdem kann man die zu berücksichtigenden Relationen und deren Richtung angeben. Der Traverser implementiert die Iterable API und lädt die Knoten ggf. erst, wenn auf sie in der der for{…}-Schleife zugegriffen wird (lazy). Es werden einige einfache Standardimplementierungen mitgeliefert, wie man hier sieht:

tx = neodb.beginTx();
Traverser friends = neo.traverse(Order.BREADTH_FIRST,
StopEvaluator.DEPTH_ONE,
ReturnableEvaluator.ALL_BUT_START_NODE, KNOWS, Direction.BOTH);
for (Node friend : friends) {
System.out.println(friend.getProperty("name"));
}
tx.success();
tx.finish();

Wir wollen also zuerst alle Knoten einer Tiefe durchsehen, bevor wir weitere Kanten entlanglaufen (Order.BREADTH_FIRST), nach einem Schritt (StopEvaluator.DEPTH_ONE) stehenbleiben und alle Knoten außer dem Startknoten Neo (ReturnableEvaluator.ALL_BUT_START_NODE) zurückgeben. Außerdem sind Kanten mit dem Typen KNOWS in beiden Richtungen (Direction.BOTH) erlaubt. Dieser Traverser gibt uns Neos Freund Morpheus aus.

Wen kennen Neos Freunde?

Wenn wir wissen wollen, wen die Freunde von Neo kennen, also die Freunde von Neos Freunden, gehen wir entlang der KNOWS-Kanten zwei Schritte ausgehend von Morpheus und finden Trinity on Cypher. Programmatisch ausgedrückt lassen wir den Traverser durch einen geeigneten StopEvaluator nur zwei Schritte tief gehen:

StopEvaluator twoSteps = new StopEvaluator() {
@Override
public boolean isStopNode(TraversalPosition position) {
return position.depth() == 2;
}
};

Das Gleiche passiert durch einen eigenen ReturnableEvaluator, der nur Knoten, die in der Tiefe 2 gefunden wurden, im resultierenden Iterator zulässt:

ReturnableEvaluator nodesAtDepthTwo = new ReturnableEvaluator() {
@Override
public boolean isReturnableNode(TraversalPosition position) {
return position.depth() == 2;
}
};

Somit können wir nun Neos Freundeskreis erweitern:

tx = neodb.beginTx();
Traverser friendsOfFriends = neo.traverse(Order.BREADTH_FIRST,
twoSteps, nodesAtDepthTwo, KNOWS, Direction.BOTH);
for (Node friend : friendsOfFriends) {
System.out.println(friend.getProperty("name"));
}
tx.success();
tx.finish();

Was uns Cypher und Trinity als Ergebnis liefert.

[ header = Seite 4: Wer liebt wen? ]

Wer liebt wen?

Eine weitere interessante Frage ist, ob es in diesem Netzwerk irgendjemanden gibt, der verliebt ist, ohne bei Neo anzufangen. Diesmal wollen wir den gesamten Graphen vom Architekten her aufrollen (wir müssen natürlich seine NodeID haben, aber dazu später) und herausfinden, ob irgendein Knoten eine ausgehende LOVE-Relation hat. Ein kleiner ReturnableEvaluator ist hier angebracht:

ReturnableEvaluator findLove = new ReturnableEvaluator() {
@Override
public boolean isReturnableNode(TraversalPosition position) {
return position.currentNode().hasRelationship(LOVES, Direction.OUTGOING);
}
};

Wir brauchen alle Relationstypen im gesamten Graphen, damit wir wirklich alle Kanten mitnehmen:

tx = neodb.beginTx();
List<Object> types = new ArrayList<Object>();
// alle relationship types aus dem gesamten Graph, in beiden Richtungen berücksichtigen
for(RelationshipType type : neodb.getRelationshipTypes()) {
types.add(type);
types.add(Direction.BOTH);
}
//nun aber an die Arbeit!
Traverser inLove = architect.traverse(Order.BREADTH_FIRST,
StopEvaluator.END_OF_GRAPH, findLove, types.toArray());
for (Node lover : inLove) {
System.out.println(lover.getProperty("name"));
}
tx.success();
tx.finish();

Dies gibt uns Trinity als einzigen Knoten zurück, da wir nur nach ausgehenden LOVE-Relationen suchen.

Volltextsuche im Graphen

Während Graphoperationen die Spezialität von Neo4j sind, braucht man oft auch andere Methoden, um z. B. eine Volltextsuche über den ganzen Graphen gut abwickeln zu können. Neo4j greift hier auf externe Indexsysteme zurück, um nicht das Rad neu zu erfinden. Für die oft verwendeten Fälle der Volltextsuche bündelt Neo4j hier Lucene und Solr als Komponenten, womit man beliebige Eigenschaften im Graphen in der gleichen Transaktion ändern und indizieren (und bei Problemen zurückrollen) kann.

In unserem Beispiel könnten wir also die name-Eigenschaft mit folgendem Code indexieren:

GraphDatabaseService graphDb = // eine GraphDatabaseService Instanz
IndexService index = new LuceneIndexService( graphDb );


// Knoten mit "name"-Eigenschaft erzeugen und indizieren
Node neo = graphDb.createNode();
neo.setProperty( "name", "Neo" );
index.index( neo, "name", neo.getProperty( "name" ) );

// Knoten mit Namen "Neo" ermitteln
Node node = index.getSingleNode( "name", "Neo" );

Das ist ein Beispiel für einen externen Index. Es bieten sich aber eine Vielzahl von Indexmethoden an, die direkt im Graphen die Wege für spezielle Anwendungen verkürzen, so etwa eineTimeline mit B-Tree, RTrees und QuadTrees für zweidimensionale Indexe (sehr gewöhnlich im GIS-Bereich) und andere. Teilweise hat es sich auch bewährt, direkt an den Root-Knoten weitere Kategorisierungsknoten (Schnellzugriff) zu hängen, womit man wichtige Startknoten direkt verknüpft.

[ header = Seite 5: Java ist langweilig. Geht es auch kürzer? ]

Java ist langweilig. Geht es auch kürzer?

Neo4j hat viele Sprachanbindungen, die das Arbeiten mit Graphen von unterschiedlichen Programmiersprachen erleichtern. Erwähnt seien hier die sehr guten Neo4j-JRuby-Anbindungen, mit denen der Code für das Beispielnetz um einiges schrumpft.

In der Shell installieren wir also das neo4j-gem mit gem install neo4j. Der Ruby-Code sieht dann folgendermaßen aus:

require "rubygems"
require "neo4j"

class Person
include Neo4j::NodeMixin
# Symbole für Knoten Eigenschaften
property :name

# Beziehungs-Typen
has_n :friends

# Lucene index für die angegebenen Eigenschaften
index :name
end

neo = Person.new {|n| n.name = 'Neo' }
morpheus = Person.new {|n| n.name = 'Morpheus' }
trinity = Person.new {|n| n.name = 'Trinity' }
cypher = Person.new {|n| n.name = 'Cypher' }
smith = Person.new {|n| n.name = 'Agent Smith' }
architect = Person.new {|n| n.name = 'Architect' }

cypher.friends << morpheus
cypher.friends << smith
neo.friends << morpheus
morpheus.friends << trinity
trinity.rels.outgoing(:loves) << neo

architect.rels.outgoing(:has_coded) << smith

#Neos Freunde finden
neo.friends.each { |n| puts n }

#Neos Freunde von Freunden
neo.friends.depth(2).each { |n| puts n }

#Ist jemand verliebt?
architect.traverse.both(:friends, :has_coded, :loves).depth(:all).filter do
outgoing(:loves).to_a.size > 0
end.each do |n|
puts 'In love: ' + n.name
end
Eine Abfragesprache – Gremlin

Abbildung 2: Gremlin

Zurzeit gibt es keine standardisierten Graphanfragesprachen, die alle Bereiche und Projekte in diesem Bereich abdecken. Jedoch gibt es im RDF- Bereich SPARQL, eine an SQL angelehnte Abfragesprache, die sich vor allem auf die Beschreibung von Beispielteilgraphen konzentriert, um dann passende Mengen von Statements herauszufiltern. Es gibt aber eine ganze Menge von Graphen die nicht RDF-kompatibel sind und eigene, nicht standardisierte Strukturen benutzen, wie z.B. unser Matrix-Graph und andere domänenspezifische Datenmengen. Andere Initiativen setzen auf JSON-basierte Varianten, wie zum Beispiel MQL, die Anfragesprache für Freebase. All diese Sprachen funktionieren nur auf ihren eigenen Datenmengen und bieten keinen oder sehr wenig Unterstützung für die wirklich interessanten Graphalgorithmen und heuristischen Analysemethoden, die für heutige große Graphen erforderlich sind.

Für die komplexeren und interessanteren Fragen, die direkt auf einem Netzwerk aufsetzen (ohne und mit RDF), ist zurzeit die XPath-orientierte Graphenprogrammiersprache Gremlin in der Entwicklung. Über die Schaffung eines generellen Graphenmodells, das alle Features der bestehenden Modelle und Theorien vereinigt, wurde eine Plattform geschaffen, um darunter unterschiedliche Datenmodellierungen einzuhängen. Zurzeit gibt es schon einige von diesen Implementierungen. Sie reichen vom einfachen in-memory TinkerGraph, über die RDF-SAIL-Schnittstelle für AllegroGraphSesame und das ThinkerPop LinkedData SAIL (ursprünglich von Josh Shinavier für die Ripple-Programmiersparche) bis hin zu Neo4j.

Gremlins Syntax basiert auf XPath, um auch tiefe Wegbeschreibungen durch den Graphen gut ausdrücken zu können. Viele einfache Fälle sehen damit im Prinzip wie normales XPath aus.

Für das verwendete Matrix-Beispiel könnte eine Gremlin-Sitzung ungefähr so aussehen (nachdem Gremlin installiert und gremlin.sh gestartet wurde):

peterneubauer$ ~/code/gremlin/gremlin.sh

,,,/
(o o)
-----oOOo-(_)-oOOo-----
gremlin> #öffne einen Neo4j Graphen als default ($_g)
gremlin> $_g := neo4j:open('tmp/matrix')
==>neo4jgraph[tmp/matrix]
gremlin> #Die Knoten mit Eigenschaften
gremlin> $neo := g:add-v(g:map('name','Neo'))
==>v[1]
gremlin> $morpheus := g:add-v(g:map('name','Morpheus'))
==>v[2]
gremlin> $trinity := g:add-v(g:map('name','Trinity'))
==>v[3]
gremlin> $cypher := g:add-v(g:map('name','Cypher'))
==>v[4]
gremlin> $smith := g:add-v(g:map('name','Agent Smith'))
==>v[5]
gremlin> $architect := g:add-v(g:map('name','The Architect'))
==>v[6]
gremlin> #Die Kanten
gremlin> g:list($cypher,$neo,$trinity)[g:add-e($morpheus,'KNOWS',.)]
==>v[4]
==>v[1]
==>v[3]
gremlin> g:add-e($cypher,'KNOWS',$smith)
==>e[3][4-KNOWS->5]
gremlin> g:add-e($trinity,'LOVES',$neo)
==>e[4][3-LOVES->1]
gremlin> g:add-e($architect,'HAS_CODED',$smith)
==>e[5][6-HAS_CODED->5]
gremlin> #Setze Neo als Startknoten ($_) über eine Volltextsuche
gremlin> $_ := g:key('name','Neo')
==>v[1]
gremlin> #ist das auch Neo?
gremlin> ./@name
==>Neo
gremlin> #Wie sehen die Kanten aus?
gremlin> ./bothE
==>e[0][1-KNOWS->2]
==>e[4][3-LOVES->1]
gremlin> #Nimm nur die KNOWS-Kanten
gremlin> ./bothE[@label='KNOWS']
==>e[0][1-KNOWS->2]
gremlin> #Die Namen von Neo's Freunden
gremlin> ./bothE[@label='KNOWS']/inV/@name
==>Morpheus
gremlin>
gremlin> #Die Freunde der Freunde, 2 Schritte
gremlin> repeat 2
$_ := ./outE[@label='KNOWS']/inV
end
==>v[4]
==>v[3]
gremlin> #Und deren Namen?
gremlin> ./@name
==>Cypher
==>Trinity
gremlin> #Alle Knoten im Graphen mit einer ausgehenden LOVES Kante
gremlin> $_g/V/outE[@label='LOVES']/../@name
==>Trinity 

[ header = Seite 6: Tiefe Algorithmen + Fazit ]

Tiefe Algorithmen – Value in Relationships

Das vorstehende Beispiel ist ein sehr naives Szenario. Interessanter wird es bei Algorithmen über große Graphen. Algorithmen wie Eigenvector Centrality und Dijkstra sind hier nicht brauchbar, da sie jeden Knoten im Graphen berücksichtigen müssen. Hier kommen heuristische Konzepte wie Grammar-based Random Walkers und Spreading Activation ins Spiel (Ein guter Artikel dazu von Marko Rodriguez, dem Author von Gremlin, hier). Der Google-PageRank-Algorithmus ist eine solche Heuristik und wird in Gremlin ungefähr so modelliert (hier als Beispiel über den Graphen aller Lieder, Konzerte und Platten der Gruppe Greatful Dead, mit 2500 Schleifen und einem Energieverlust von 15 % in jeder Schleife):

Greatful Dead

$_g := tg:open()
g:load('data/graph-example-2.xml')
$m := g:map()
$_ := g:key('type', 'song')[g:rand-nat()]
repeat 2500
$_ := ./outE[@label='followed_by'][g:rand-nat()]/inV
if count($_) > 0
g:op-value('+',$m,$_[1]/@name, 1.0)
end
if g:rand-real() > 0.85 or count($_) = 0
$_ := g:key('type', 'song')[g:rand-nat()]
end
end
g:sort($m,'value',true())

Was uns die folgenden gewichteten Songs gibt:

==>DRUMS=44.0
==>PLAYING IN THE BAND=38.0
==>ME AND MY UNCLE=32.0
==>TRUCKING=31.0
==>CUMBERLAND BLUES=29.0
==>PROMISED LAND=29.0
==>THE MUSIC NEVER STOPPED=29.0
==>CASSIDY=26.0
==>DARK STAR=26.0
==>NOT FADE AWAY=26.0
==>CHINA CAT SUNFLOWER=25.0
==>JACK STRAW=25.0
==>TOUCH OF GREY=24.0
==>BEAT IT ON DOWN THE LINE=23.0
==>BERTHA=23.0

Wie man sieht, spielt Gremlin seine Stärken bei tieferen Analysen aus. Ein anderes interessantes Beispiel, bei dem die unterliegenden Daten direkt aus dem Internet als alleinige Datenquelle gezogen werden, ist ein Empfehlungsalgorithmus für Musik über LinkedData und DBPedia.

Fazit und Ausblick

Sollte dies nicht reichen, kann man natürlich immer der Domäne angepasste Sharding-Grenzen anwenden, ohne deshalb die harten Konzepte von Key Values oder Dokumenten einführen zu müssen. Ob das in einem z. B. Dokumentenmodell resultiert oder man eine „Objektdatenbank“ für seine Domäne baut, richtet sich nach dem Anwendungsfall.

Der Code für diesen Artikel liegt hier

Für das ausgezeichnete Feedback und die hilfreichen Hinweise während des Entstehens dieses Artikels möchte ich mich besonders bei Michael Hunger bedanken.

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

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.