Die Graphdatenbank Neo4j modelliert graphbasierte Probleme auf natürliche Weise ohne kostspielige Transformation in das relationelle Modell traditioneller Datenbanken.
Softwareprobleme wie der "Social Graph" von Facebook, in dem Freunde und deren Bekanntschaften mit einander in Verbindung stehen, oder die "Follower"-Struktur von Twitter sträuben sich hartnäckig, wenn es darum geht, ihre Daten persistent in traditionelle Datenbanken zu packen. Verfolgt man einen Pfad, der sich auf einem Whiteboard sehr einfach mit Kringeln und Pfeilen darstellen lässt in einem relationellen Modell, mündet dies schnell in performancefressenden JOIN-Anweisungen, die unmöglich den Anforderungen einer schnell antwortenden Webseite entsprechen.
Die Graphdatenbank Neo4j (http://neo4j.org) schickt sich deshalb an,
Graphmodelle nativ zu speichern und trumpft mit sagenhaften
Performancegewinnen auf, falls man es mit der Komplexität der Queries
nicht übertreibt. Das generische Speichermodell besteht aus Nodes
(Knoten) mit Relationships (Kanten). Beide dürfen Attribute führen,
so könnte zum Beispiel ein Node, der eine Person repräsentiert, ein
name-Feld zum Speichern des Namens enthalten oder eine Beziehung
is_friends_with deren Gütegrad (best_friend, casual_friend).
Die in der Datenbank liegenden Daten nimmt der Query-Processor von
Neo4j in einer SQL-ähnlichen Sprache namens "Cypher" entgegen und
liefert auch reihenweise Ergebnisse, die Cypher ebenfalls ähnlich wie SQL
filtert und aufbereitet (sortieren, gruppieren, etc.).
Nach der Installation des unter der GPL lizensierten Neo4j-Community-Servers
(auch eine kostenpflichtige Enterprise-Version wird angeboten) lauscht dieser
auf Port 7474 auf Kommandos, die entweder über REST eingehen oder den
neueren simplen JSON-Prozessor nutzen. Programmieren lässt sich ein Client
in mehreren Dutzend Sprachen, unter anderem auch mit dem CPAN-Modul
REST::Neo4p. Dem auf neo4j.org angebotenen
Debian-Paket liegt ebenfalls eine praktische Kommandoshell
namens neo4j-sh bei, die ähnlich wie der MySQL-Client zum
Absetzen von Anweisungen dient, um neue Daten in das Modell einzufügen
und gespeicherte Informationen über Cypher-Queries zu extrahieren.
Cypher gibt sich, ähnlich wie SQL, deklarativ, der User bestimmt also, welche Ergebnisse er sucht, macht aber keine prozeduralen Angaben darüber, wie diese genau zu finden sind. MATCH-Anweisungen bestimmen, welche Daten interessieren (zum Beispiel "finde all Daten" oder "finde alle Relationen vom Typ "is_friends_with"). WHERE-Klauseln reduzieren anschließend die Anzahl der Treffer, zum Beispiel könnten den anfragenden User nur Personen interessieren, die älter als 18 Jahre sind. Und schließlich modeln später einsetzende Aufbereitungsschritte die Daten um, sortieren, oder fassen zusammen. Aber auch weitere MATCH-Anweisungen auf die Ergebnisliste und sogar zwischendurch einsetzende Aktionen zum Erzeugen neuer Daten sind erlaubt.
Zur Illustration einiger praktischer Abfragen soll der Graph eines Home-Netzwerks in Abbildung 1 dienen. Netzwerke mit ihren Knoten und Verbindungskanten stellen tatsächlich ein beliebtes Aufgabenfeld für Neo4j dar, denn um festzustellen, ob ein Router über andere Knoten problemlos das offene Internet erreicht, muss die Datenbank einen offenen Pfad von A nach B über N oft trickreich verbundene Knoten finden, was auf relationalen Systemen eine Performance-Implosion verursacht, aber sich auf Graphdatenbanken oft in den Griff bekommen lässt.
| |
| Abbildung 1: Die Komponenten eines Home-Networks werden zur Analyse in eine Graphdatenbank eingefüttert. |
Um nun zum Beispiel den Router mit dem Namen "internal" aus Abbildung 1 in die Datenbank einzufügen und ihm die LAN IP 192.168.2.1 zuzuweisen, genügt folgendes Kommando in der neo4j Shell:
neo4j-sh (?)$ CREATE (router {name:"internal", lan_ip:"192.168.2.1"});
Um die Relation gateway zwischen dem Router "internal" und seinem
Gateway, einem weiteren neu erzeugten Knoten namens "merger"
anzulegen, sucht ein Cypher-Query beide Knoten wieder heraus und
definiert mit der Cypher-eigenen ASCII-Art-Syntax die Verbindung:
neo4j-sh (?)$ MATCH (a), (b)
> WHERE a.name = "windows" and b.name = "merger"
> CREATE (a)-[r:gateway]->(b);
Die MATCH-Operation sucht zwei Knoten, denen sie die Alias-Namen a und
b zuweist. Da sonst kein gesuchtes Pattern in der MATCH-Klausel steht,
trifft dies auf alle in der Datenbank liegenden Knoten zu. Die nachfolgende
WHERE-Klausel schränkt die Treffer aber auf zwei exakt benannte Knoten
ein und die CREATE-Anweisung malt mit "-[...]->" einen benamten
Pfeil zwischen die gefundenen Knoten und kreiert somit eine Relation
vom Typ "gateway".
Nun wäre es äußerst mühsam, die Daten eines größeren Netzwerks von
Hand einzutippen. Deswegen definiert die Datei routers.yml
in Listing 1 die Eckdaten aller im Netzwerk installierten Router
im lesbaren YAML-Format. Die Verknüpfung der Router untereinander
als Graph ergibt sich später implizit aus der Verbindung der Gateway-Adresse
des einen mit der LAN-IP des nächsten Routers als Beziehung.
01 -
02 name: modem
03 hardware_vendor: Actiontec
04 lan_ip: 192.168.20.1
05 -
06 name: merger
07 hardware_vendor: Netgear
08 hardware_model: WNR3000
09 lan_ip: 192.168.10.1
10 gateway: 192.168.20.1
11 -
12 name: internal
13 hardware_vendor: Linksys
14 hardware_model: WRT54GS
15 lan_ip: 192.168.2.1
16 gateway: 192.168.10.1
17 -
18 name: guest
19 hardware_vendor: Linksys
20 hardware_model: WRT54GL
21 wireless: 1
22 lan_ip: 192.168.1.1
23 gateway: 192.168.10.1
Das Skript in Listing 1 schnappt sich die YAML-Records aller
Router aus der Datei routers.yml iteriert ab Zeile 28 über
die Liste und pumpt
sie mittels des CPAN-Moduls REST::Neo4p als Nodes in die Datenbank.
Dabei sichert sie alle Referenzen auf erzeugte Node-Objekte im
Hash %lans unter deren LAN IP als Schlüssel.
Die Gateway-IPs hingegen speichert
das Skript im Array @gateways zusammen mit den Routern, die diese
Gateway-IPs nutzen. Später, ab Zeile 46, nudelt dann eine for-Schleife
über @gateways, sucht über den %lans-Hash das Zielobjekt heraus
und definiert mit der Methode relate_to() jeweils eine Relation
gateway vom Start- zum Zielrouter in der Datenbank.
01 #!/usr/bin/perl -w
02 use strict;
03 use FindBin qw( $Bin );
04 use REST::Neo4p;
05 use YAML qw( LoadFile );
06 use Log::Log4perl qw( :easy );
07
08 Log::Log4perl->easy_init();
09
10 my %lans = ();
11 my @gateways = ();
12
13 REST::Neo4p->connect(
14 'http://127.0.0.1:7474' ) or die;
15
16 # Delete all data
17 my $query = REST::Neo4p::Query->new('
18 MATCH (n)
19 OPTIONAL MATCH (n)-[r]-()
20 DELETE n,r');
21 $query->execute;
22
23 my $index = REST::Neo4p::Index->new(
24 "node", "router_index" );
25
26 my $yaml = LoadFile( "$Bin/routers.yml" );
27
28 for my $router ( @$yaml ) {
29
30 DEBUG "Adding router ",
31 "$router->{ name }/$router->{ lan_ip }";
32
33 my $node =
34 REST::Neo4p::Node->new( $router );
35 $index->add_entry( $node,
36 { name => $router->{ name } } );
37
38 if( exists $router->{ gateway } ) {
39 push @gateways,
40 [ $node, $router->{ gateway } ];
41 }
42
43 $lans{ $router->{ lan_ip } } = $node;
44 }
45
46 for my $gateway ( @gateways ) {
47 my( $node, $gateway_ip ) = @$gateway;
48
49 if( !exists $lans{ $gateway_ip } ) {
50 die "Gateway $gateway_ip not defined";
51 }
52
53 DEBUG "Adding ",
54 $node->get_property("name"),
55 " -[:gateway]-> ",
56 $lans{ $gateway_ip }->
57 get_property("name");
58
59 $node->relate_to(
60 $lans{ $gateway_ip }, "gateway" );
61 }
Kaum ist das Skript fertig, offenbart ein Blick auf das auf Port
7474 bereitgestellte Browser-Interface, dass die Daten ordnungsgemäß
in Neo4j liegen (Abbildungen 2 und 3).
Mit einem Query wie MATCH (n) RETURN n, der einfach alle
bislang gespeicherten Knoten zurückliefert,
zeigt der Datenbankbrowser
im Graph-Modus die Knoten als numerierte Kringel und deren Relationships
als beschriftete Pfeile, die von Knoten zu Knoten zeigen.
Ein Klick auf einen Knoten zeigt dessen Attribute
in einem hochkommenden Dialogfenster an. Im Textmodus kommen wie
in Abbildung 3 gezeigten Kästen mit den Attributwerten der Knoten hoch.
Damit das Skript bei Änderungen in den YAML-Daten die Netzwerkstruktur in der Datenbank ohne Fehler auffrischt, löscht Listing 3 zu Beginn alle bislang definierten Knoten und Kanten im Graph. Dies ist gar nicht so einfach, denn Neo4j weigert sich, Knoten zu löschen, an denen noch Beziehungen kleben, um das Datenmodell intakt zu halten. Der Cypher-Query zum Ausputzen der Datenbank heißt deshalb
MATCH (n)
OPTIONAL MATCH (n)-[r]-()
DELETE n,r
und passt auf alle Knoten n, und von ihnen eventuell ausgehende
Beziehungen zu einem anderen (hier anonymen) Knoten. Die
DELETE-Anweisung am Schluss löscht alle zu einem Knoten
gehörenden Einträge, inklusive der ausgehenden Kanten.
 |
| Abbildung 2: Im Grafikmodus zeichnet der Neo4j-Browser ein Diagramm mit den Nodes und deren Relationships. |
 |
| Abbildung 3: Der Neo4j-Browser stellt auf Port 7474 Cypher-Abfragen grafisch dar. |
Um nun alle in der Datenbank gespeicherten Router mit der Neo4j-Shell
anzuzeigen, dient der Query in Abbildung 4. Stünde statt der
RETURN-Klausel mit drei interessierenden Attributwerten
(n.name, n.hardware_vendor, ...)
dort einfach RETURN n, enthielte das Query-Ergebnis alle definierten
Attribute, was die Lesbarkeit erschweren würde. So lassen sich mit
RETURN nicht interessierende Werte ausblenden.
 |
| Abbildung 4: Dieser Query sucht alle verzeichneten Geräte. |
Die Vorteile einer Graphdatenbank liegen aber nicht in niederen
Diensten wie dem Hervorholen
von Nodes, sondern im performanten
Verfolgen von Verbindungen zwischen den Knoten. So ist es recht
einfach, herauszufinden, welche Netzverbindungen bestehen.
Der Query in Abbildung 5 sucht mit
MATCH (n) nach allen Routern im Netz.
Die mit -[r:gateway*]-> angehängte Relationsbeschreibung passt auf
eine oder mehrere Relationen vom Typ "gateway", das abschließende (m)
in der Beschreibung steht für den Knoten am Ende der Kette. Da der
Cypher-Query die Ergebnisse mit einem vorangestellten p= in der Variablen
p ablegt, würde ein nachfolgendes RETURN p alle Routingpfade mit
allen durchlaufenen Routern samt deren Attribute ausgeben. Das wäre
ein wahrer Datenwust und so reduziert die RETURN-Anweisung die Ausgabe
auf den Router-Namen am Anfang der Route und sammelt mit collect(m.name)
die Namen durchlaufener Router ein.
Die Ausgabe in Abbildung 5 hat deswegen 2 Spalten, in der ersten steht
der gefundene Start-Router, in der zweiten eine Liste mit den
Namen durchlaufener Router auf dem Weg ins offene Internet.
In einem riesigen Netzwerk läuft ein Query mit beliebig langen Relationsketten oft zu langsam, ihn auf 2 oder 3 Stufen zu begrenzen kann enorm Zeit sparen. Auch wenn die Datenbank nicht ewig nach einem passenden Startpunkt für einen Pfad suchen muss, gehen ihr Abfragen schneller von der Hand. Steht der Startknoten für die Suche etwa schon fest, lässt er sich mit einer Direktive wie etwa
START n=node:router_index(name='guest')
vor dem MATCH-Kommando verankern. Voraussetzung dafür ist, dass
der Startrouter unter dem angegebenen Schlüssel ("name") vorher
in einem Neo4j-Index abgelegt wurde. Listing 2 hat genau dies
in Zeile 36 mit der Methode add_entry() erledigt. Für einfachere
Anwendungen steht in Neo4j auch eine "autoindex"-Option auf Serverebene
bereit, mit der sich festlegen lässt, welche Attribute er
automatisch indiziert.
 |
| Abbildung 5: Alle möglichen Pfade im Graphen über "gateway"-Relationen zeigt dieser Query. |
In Abbildung 6 findet der Query zunächst alle drahtlosen Router, die das Attribut "wireless" auf "1" gesetzt haben. Im Beispielnetzwerk gibt es nur einen einzigen, in einer komplexeren Installation kämen alle vorhandenen und deren Routine-Pfade zum Internet zutage. Mit diesen Informationen ließen sich zum Beispiel periodisch automatisch Sicherheits-Checks durchführen, um zu verhindern, dass ein Netzwerkpaket durch einen Konfigurationsfehler von einem drahtlosen Netzwerk in ein geschütztes, internes Netzwerk gelangen kann.
 |
| Abbildung 6: Vom einzigen Wireless-Router führt nur eine Verbindung zum Modem, die nicht über das interne Netzwerk läuft. |
Das Suchmuster der MATCH-Anweisung darf auch komplexer verankert sein.
Der Query in Abbildung 7 sucht im gesamten Netzwerk
nach einem beliebigen Router n, der von zwei Seiten als Gateway
verwendet wird. Hierzu schreibt der User den Query mit drei
Router-Variablen, wie im Beispiel m, n und o, mit einer
Relation von links nach rechts zwischen den ersten beiden Routern und
einer weiteren Relation von rechts nach links zwischen dem Router am
Ende und dem in der Mitte. ASCII-Att macht's möglich.
Neo4j versucht, eine solche Konstellation zu
finden und gibt das Ergebnis aus: Der Router "merger" entspricht den
Anforderungen. Die zwei Treffer entsprechen demselben Pfad in
unterschiedlichen Richtungen.
 |
| Abbildung 7: Gesucht sind zwei Knoten im Graph, die Pakete zum gleichen Gateway weiterleiten. |
Welche Geräte im Netz leiten Pakete ins Internet weiter? Listing 3
setzt einen Cypher-Query in Perl ab und verankert das Match-Pattern
am Ende mit dem zum DSL-Modem gehörenden Router. Das CPAN-Modul
REST::Neo4p::Query setzt den Query ab, und nimmt die per JSON vom Server
eintrudelnden Ergebnisse mit der Methode fetch() als Pfade
entgegen. Letztere bestehen aus zwei Listen, eine mit Knoten und eine
mit den dazwischenliegenden Kanten. Die Methoden
nodes() und relationships() kramen sie aus den Pfad-Objekten hervor.
Der For-Schleife am Ende bleib nur noch, die Namen der Geräte per
get_property() zu extrahieren und die Pfade mit Pfeilen auszugeben:
merger->modem
internal->merger->modem
guest->merger->modem
01 #!/usr/bin/perl -w
02 use strict;
03 use REST::Neo4p;
04
05 REST::Neo4p->connect(
06 "http://127.0.0.1:7474" ) or die;
07
08 my $query_string =
09 "START n=node:router_index(name='guest')
10 MATCH p =
11 (n)-[r:gateway*]->({name:'modem'})
12 RETURN p";
13
14 my $query = REST::Neo4p::Query->new(
15 $query_string );
16 $query->execute( ) or die $!;
17
18 while( my $row = $query->fetch() ) {
19 my $path = $row->[0];
20 my @nodes = $path->nodes();
21 my @rels = $path->relationships();
22
23 for my $node ( @nodes ) {
24 print $node->get_property( "name" );
25 if( @rels ) {
26 my $rel = shift @rels;
27 print "->";
28 }
29 }
30 print "\n";
31 }
Wie in Abbildung 8 gezeigt, erfolgt die Installation des Neo4j-Servers
unter Ubuntu und anderen Debian-Derivaten mit Hilfe des Debian-Repo-Servers
auf neo4j.org. Nach der Installation startet sich der Dämon selbständig,
was der Aufruf von curl http://localhost:7474 bestätigt, der den
Server-Status im JSON-Format zurückgibt. Wer einen Browser auf den
URL hindirigiert, bekommt das weiter oben erwähnte Web-Interface zu
sehen und kann mit Tutorials spielen oder testweise eigene Daten einfüttern.
Zum Redaktionsschluss war auf Ubuntu 12.04 Neo4j Version 2.0.1 aktuell.
 |
| Abbildung 8: Der Paketmanager apt-get installiert den neo4j-Server auf Ubuntu. |
Wer den neo4j-Server in einer VM oder auf einem anderen Host laufen hat, und von anderer Stelle darauf zugreifen möchte, muss in der Konfigurationsdatei
/etc/neo4j/neo4j-server.properties
die Zeile
org.neo4j.server.webserver.address=0.0.0.0
auskommentieren, sonst lässt der Webserver keine Abfragen zu, die nicht vom "localhost" kommen.
Als weiterführende Literatur stehen neben den Manualseiten auf der Neo4j-Webseite http://www.neo4j.org zwei Bücher zur Verfügung: Zum einen das brandneue Kindle-Buch von Neo4j-Contributor Michael Hunger [2], das eine Wirbelwindtour durch die Cypher-Syntax bietet, einige praktische Neo4j-Beispiel vorstellt, aber außer dem angehängten Cypher-Cheat-Sheet kein Referenzwerk ist, sondern nur hie und da an der Oberfläche kratzt. Das ein Jahr alte O'Reilly-Buch "Graph Databases" [3] widmet sich trotz des umfassend klingenden Titels praktisch nur Neo4j und stellt eine Vielzahl von echten Neo4j-Anwendungen im Detail vor. Auch ihm fehlt die sorgfältig entwickelte Struktur eines Lehrbuchs, das Standardwerk zu diesem recht jungen Thema steht wohl noch aus, der Manning-Verlag hat schon "Neo4j in Action" angekündigt.
Listings zu diesem Artikel: ftp://www.linux-magazin.de/pub/listings/magazin/2014/06/Perl
"Neo4j 2.0 - Eine Graphdatenbank für alle", Michael Hunger, schnell + kompakt, 2014.
"Graph Databases", Ian Robinson, Jim Webber, Emil Eifrem, O'Reilly 2013
 |
Michael Schilliarbeitet als Software-Engineer bei Yahoo in Sunnyvale, Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen der Skriptsprache Perl. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |