Zurück zum Zeichenbrett (Linux-Magazin, Juni 2014)

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.

Gespeichert wie geschaffen

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.

Mächtige Abfragesprache

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.

Füttern von Hand

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".

Füttern automatisch

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.

Listing 1: routers.yml

    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.

Listing 2: router-setup

    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.

Pfade im Netz

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.

Kosten sparen

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.

Zweiseitiger Anker

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

Listing 3: router-search

    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 }    

Installation

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.

Lesen bildet

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.

Infos

[1]

Listings zu diesem Artikel: ftp://www.linux-magazin.de/pub/listings/magazin/2014/06/Perl

[2]

"Neo4j 2.0 - Eine Graphdatenbank für alle", Michael Hunger, schnell + kompakt, 2014.

[3]

"Graph Databases", Ian Robinson, Jim Webber, Emil Eifrem, O'Reilly 2013

Michael Schilli

arbeitet 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.