InfiniteGraph

InfiniteGraph ist eine sehr junge NoSQL Graphendatenbank, welche auf der Infrastruktur der Objektdatenbank Objectivity/DB aufbaut. InfiniteGraph und Objectivity/DB werden von der Firma Objectivity Inc. gepflegt, welche die Object Management Group (OMG) und Object Data Management Group (ODMG) mitgegründet hat. Folgende Mechanismen werden bereits von Objectivity/DB umgesetzt.

  1. Jedes Objekt in der Datenbank hat eine eindeutige Identität
  2. Objekte können durch Kanten verbunden werden. Hierbei sind auch mehrfach Kanten und bidirektionale Kanten erlaubt.
  3. Die Datenbank kann SQL Anfragen beantworten
  4. Die Datenbank kennt ein Iterator Konzept, welches im Großen und Ganzen einer Graph Traversierung entspricht
  5. Es wird ein synchrones und quorum-basiertes Verfahren zur Replikation genutzt, auf welches im Kapitel Replikation in InfiniteGraph näher eingegangen wird.

InfiniteGraph nutzt diese Vorentwicklungen. Somit konnte sehr schnell eine graphenorientierte Programmierschnittstelle angeboten werden. Im nachfolgenden wird im allgemeinen das Produkt InfiniteGraph beschrieben. Da dieses jedoch nicht ohne den "Unterbau" Objectivity/DB auskommt, werden auch einige Konzepte dieser Datenbank, die für die Nutzung von InfiniteGraph relevant oder von Vorteil sind, beschrieben.


Inhalt

Steckbrief
Datenmodell
Architektur
Replikation
Transaktionen
Indizierung
Kommunikation
Bewertung
Quellen



Steckbrief

Webadressehttp://www.infinitegraph.com
KategorieVerteilte Graphdatenbank
DatenmodellProperty Graph
SchemaJava Klassen
Query-MethodeTraverser API, PQL
APIJava
PersistenzObjectivity/DB
TransaktionenACID, lokal und verteilt
Replikation/SkalierungObjectivity/DB, derzeit keine Graphpartitionierung
LizenenKommerziell, Demoversion mit bis zu 1000000 Knoten

Datenmodell

Das Datenmodell von InfiniteGraph entspricht einem Property-Graphen. Knoten und Kanten werden durch objektorientierte Klassen definiert. Diese erben von Basisklassen aus der API Schnittstelle. Die Basisklassen definieren ein statisches Grundschema welches z.B. eine eindeutige Identität implementiert. Durch Attribute der Klassen können weitere Properties erzeugt werden. Momentan gibt es keinen Schemamanager der die Verbindung zwischen Knoten und Kanten überprüft. In InfiniteGraph besitzen Kanten eine Gewichtung. Dies sorgt für eine reduzierte Betrachtung von Kanten bei Analyseverfahren. Da bei vielen Analyseverfahren ein hoher Prozentsatz der betrachteten Kanten irrelevant ist, ist dies eine sinnvolle Technik. Zur Indizierung von Properties nutzt InfiniteGraph sowohl eigene Indextypen aber auch Alternativen wie die Indizies vom Open Source Projekt Lucene. Knoten können ebenfalls Namen gegeben werden, was einen schnelleren Zugriff erlaubt.

Architektur


Abbildung 1: Architektur von InfiniteGraph[1]

Die genaue Verbindung der Dateien, die im nachfolgenden einzeln beschrieben werden, kann Abbildung 1 entnommen werden.

  • Konfigurationsdatei

Beim Erstellen einer Datenbank wird eine vorher angelegte Konfigurationsdatei genutzt. Die Konfigurationsdatei ist eine Propertiedatei (.properties) welche Informationen zum Erstellen der Datenbank enthält. Dazu zählt die eindeutige ID der Datenbank sowie die Spezifikation der StorageUnits. Auch andere Konfigurationen, wie z.B. das Abschalten der MROW Funktionalität können hier definiert werden.

  • Bootdatei

Beim Erstellen einer Datenbank wird automatisch eine Bootdatei erzeugt (.boot). Diese wird unter dem Pfad erzeugt, der im 'BootFilePath' der Konfigurationsdatei angegeben wurde. Dabei handelt es sich um eine Textdatei, die Informationen zum Öffnen einer Datenbank enthält. Weitere Informationen aus der Konfigurationsdatei, wie der zu verwendende Lockserver oder der Name bzw. die Identifikation der Datenbank, werden ebenfalls in die Bootdatei kopiert.
Die Bootdatei enthält den Pfad zur Systemdatenbankdatei.

  • Systemdatenbankdatei

Die Systemdatenbankdatei (.fdb) wird ebenfalls automatisch erzeugt. Standardmäßig im selben Pfad wie die Bootdatei.
Die Systemdatenbankdatei enthält eine Liste aller individuellen Datenbankdateien und aller autonomen Partitionen falls mehr als eine existiert.
Wenn das erste Objekt eines definierten Typs in der Datenbank gespeichert wird, wird das zugehörige Schema erzeugt und in der Systemdatenbank gespeichert.

  • Individuelle Datenbankdateien

Es werden auch die individuellen Datenbankdateien erzeugt (.DB). Auf diese wird im Kapitel über StorageUnits näher eingegangen. Kurz zusammengefasst, existieren für die verschiedenen Typen, Knoten, Kanten und Connectoren, einzelne Datenbankdateien. Beim Speichern eines Objekts eines bestimmten Typs wird dieses in der zugehörigen Datenbankdatei gespeichert bzw. in deren Containern.

  • Journaldateien

Wenn eine Applikation Änderungen an der Datenbank vornimmt werden Journal Dateien (.JNL) angelegt. Diese werden genutzt, um beim Abbruch bzw. Fehlschlag einer Transaktion, den letzten konsitenten Datenbankzustand wieder herzustellen.


  • Storage Unit

Abbildung 3: Eine StorageUnit[1]

Abbildung 2: Eine StorageUnit und ihre Container[1]

Wenn eine Applikation Knoten oder Kanten in die Datenbank einfügt, werden diese in Datenbankdateien gespeichert. Eine StorageUnit ist eine Kombination aus Speicherort und Spezifikation, die Richtlinien über das Zuweisen von Daten enthält. Jede StorageUnit speichert Daten in drei verschiedenen Datenbankdateien (siehe Abbildung 3). Eine InfiniteGraph Datenbank kann auch mehrere StorageUnits nutzen. Ist dies der Fall werden die Datenbankdateien fortlaufend nummeriert. Jede Datenbankdatei besitzt eine Nummer an Containern. Container sind die technische Umsetzung der Speicherung von Daten (siehe Abbildung 2). Ihre initiale Größe, wird durch die StorageUnit Spezifikation bestimmt und ergibt sich aus dem minimal zulässigen Wert. Es werden auch maximal zulässige Werte angegeben. Ebenso kann die initiale Menge von Containern spezifiziert werden. Die Spezifikation einer StorageUnit wird dann immer für alle drei Datenbankdateien angewendet. Durch diese Spezifikation ist eine gezielte Auslagerung der Daten im Netzwerk möglich.


  • Lockserver

Ein Lockserver ist dafür zuständig, den Datenbankzugriff durch Locks auf Daten zu steuern um die Daten konsistent zu halten. Dadurch werden anfragenden Transaktionen Locks vergeben und entzogen. Dafür wird immer der Container gelockt, der die angefragten Daten enthält. Wenn ein zweiter Lock auf einen bereits gelockten Container angefragt wird, kann dieser nur dann erteilt werden, wenn die beiden Locks kompatibel sind. Dies ist z.B. der Fall, wenn es sich beim ersten Lock um einen Lock mit Leserechten handelt, und beim zweiten Lock ebenfalls. Auch die Kombination Lesen und Schreiben ist erlaubt.
Während einer Transaktion ist es möglich 'stale data' ,also veraltete Daten, zu erhalten, da InfiniteGraph MROW erlaubt. MROW steht für Multiple Readers, One Writer. Diese Eigenschaft kann manuell deaktiviert werden. Dies führt jedoch zu Performance Nachteilen.

Replikation


Abbildung 4: Der Aufbau einer autonomen Partition[4]

Datenreplikation wird in InfiniteGraph durch Objectivity/DRO (Data Replication Option) erreicht. Dieses Feature ist Teil der Grundlage von InfiniteGraph, Objectivity/DB. Objectivity/DRO nutzt mehrere Datenbankimages um synchrone Replikation zu gewährleisten.
Synchrone Replikation bedeutet, dass bei einem Update auf einem Datenbankimage alle anderen existierenden Images ebenfalls aktualisiert werden. Vorteil dieses Mechanismus ist die ständige Konsistenz der Daten. Nachteil dieses Mechanismus ist die Fehleranfälligkeit durch Ausfall eines Servers der ein Datenbankimage enthält. In diesem Fall kann die synchrone Replikation nicht durchgeführt werden.
Objectivity/DRO modifiziert den beschriebenen Mechanismus um ein Verfahren, welches eine Mindestzahl an erreichbaren Datenbankimages benötigt, die zusammen einen konsistenten Datenbankzustand repräsentieren können. Dazu werden die Datenbankimages in autonome Partitionen abgelegt. Autonome Partitionen sind unabhängig von Netzwerk- oder Systemfehlern anderer Partitionen und besitzen einen eigenen Lockserver. Jede autonome Partition besitzt eine komplette Architektur (siehe Abbildung 4). In der Systemdatenbankdatei sind Referenzen zu allen anderen autonomen Partitionen hinterlegt.
Stellt eine Transaktion eine Anfrage an einen Lockserver werden alle anderen Lockserver kontaktiert. Antwortet eine Mehrzahl, wird der Transaktion der Zugriff auf die Daten gewährt. Die Transaktion wird dann auf allen erreichbaren Datenbankimages synchron durchgeführt. In dieser Zeit können keinen anderen Transaktionen auf die Container zugreifen um Konsistenz der Daten zu gewährleisten. Eine Mehrzahl an Datenbankimages bwz. an autonomen Partitionen wird als Quorum bezeichnet.
Datenimages, die nach einiger Zeit wieder erreichbar sind, werden in Objectivity/DRO automatisch mit dem aktuellen Status synchronisiert. Dieser wird durch die Mehrzahl der Datenbankimages repräsentiert. Standardmäßig ist dieses Verfahren für READ und WRITE Transaktionen aktiviert. Für READ Transaktionen kann es aber vom Anwendungsentwickler deaktiviert werden.
Objectivity/FTO (Fault Tolerant Option), das hier nicht näher beschrieben werden soll, bietet ein administratives Tool um autonome Partitionen zu erzeugen und ist bei jeder InfiniteGraph Installation verfügbar.


Transaktionen

Um in InfiniteGraph mit der Datenbank zu kommunizieren, sind Transaktionen notwendig. Transaktionen sind bereits Teil von Objectivity/DB. Durch die Verwendung von Transaktionen werden ACID Eigenschaften erreicht. Beim Durchführen einer Transaktion, wird der Container, der die relevanten Daten enthält, vom Lockserver für andere unzulässige Transaktionen gesperrt. Erst nach dem Commit einer Transaktion werden die Daten bzw. der Container wieder frei gegeben. Der nachfolgende Code demonstriert die einfache Umsetzung von Transaktionen durch die InfiniteGraph Java API.
Transaction tx = myGraph.beginTransaction(AccessMode.READ_WRITE);
  //Mache etwas in der Transaktion
tx.commit()

Indizierung

InfiniteGraph unterstützt drei verschiedene Index-Implementierungen.

  • Graph Index
Dies ist der Basismechanismus zum indizieren von Objekten in InfiniteGraph. Hierbei werden alle Objekte eines angegebenen Typs automatisch in den Index eingepflegt. Dafür müssen ein Name, eine Klasse sowie ein oder mehrere Attribute angegeben werden. Indizierbare Typen sind short, int, long, float, double und String von Knoten oder Kanten. Das nachfolgende Beispiel erzeugt einen Index mit dem Namen 'myGraphIndexName' für das Attribut bzw. die Property 'name' des Knoten 'Person'. Es wird ebenfalls dargestellt, wie ein solcher Index geladen werden kann.
IndexManager.<Person>createGraphIndex("myGraphIndexName", Person.class.getName(), "name");
personGraphIndex = IndexManager.getGraphIndex(Person.class.getName(), "name");
  • Generic Index

Beim Generic Index hat der Entwickler die volle Kontrolle darüber, welche Objekte in den Index aufgenommen werden sollen. Dazu muss er nach der Erzeugung des Index alle Objekte eines Typs explizit hinzufügen. Dabei lassen sich Logiken einbauen.

Das nachfolgende Beispiel zeigt, wie nur Knoten vom Typ Person und dem Namen "John" in den Index aufgenommen werden.
//Erzeugen eines generischen Index
IndexManager.<Person>createGenericIndex("myGenericIndex", Person.class.getName(), "name");

//Laden des generischen Index
GenericIndex<Person> myGenericIndex IndexManager.getGenericIndexByName("myGenericIndex");

//Iteration über alle Knoten vom Typ Person
Iterable<Vertex> vertexItr = myGraphDB.getVertices(Person.class.getName());
  try{
    for (Vertex vertex : vertexItr){
      Person returnedVertex = (Person) vertex;

      //Wenn der Name der Person 'John' ist wird das Objekt dem Index hinzugefügt
      if(returnedVertex.getName().equals("John"))
        myGenericIndex.put(returnedVertex);
    }
  }
  catch(IndexException ndxe){
   //Something TODO here
  }       
  • Lucine Index

InfiniteGraph unterstützt Apache Lucene™ Volltext Indizierung und Suchunterstützung mit der LuceneIndex Klasse. Durch diese Implementierung eines Index, wird jedes indizierte Attribut in Text umgewandelt. Weiter wird hier auf diese Art der Indizierung nicht eingegangen, da ebenfalls eine genauere Erklärung des Apache Lucene™ Projekts notwendig wäre.

Kommunikation

Die Kommunikation mit der Datenbank erfolgt immer über die Java API, die von InfinteGraph zur Verfügung gestellt wird.

  • CRUD

CRUD steht für Create Read Update Delete und beschreibt die Basisoperationen zur Manipulation von Daten.
Nachdem eine Datenbank erstellt und geöffnet ist, können Knoten und Kanten hinzugefügt werden. Dazu werden Instanzen von Klassen gebildet, die definierte Basistypen und damit auch Basisfunktionalitäten erben.
Diese sind

  1. BaseVertex für Knoten und
  2. BaseEdge für Kanten
Ausgehend für die Beschreibung aller Operationen ist die Klasse Person, die einen Knoten abbildet und im folgenden Code Ausschnitt dargestellt ist. Das Objekt 'myGraph' steht für die bereits geöffnete Datenbank. Die Implementierung von Transaktionen wird hier nicht mit dargestellt.
public class Person extends BaseVertex
{
    private String name;

    public Employee(String name){
        setName(name);    
    }

    private void setName(String name){
        markModified();
        this.name = name;
    }

    public String getName(){
        fetch();
        return this.name;
    }
}
  • Create
Um einen Knoten vom Typ Person in der Datenbank zu speichern, muss dieser zuerst erzeugt werden.
Person person = new Person("markus");
Danach kann das Objekt 'person' innerhalb einer Transaktion der Datenbank hinzugefügt werden.
myGraph.addVertex(person);
  • Read

Um einen Knoten wieder aus der Datenbank zu laden, verwendet man entweder dessen Index oder einen einfachen Graph Traverse. Beide Möglichkeiten werden in den nachfolgenden Kapiteln beschrieben.

  • Update

Zum Ändern eines Datensatzes, muss dieser zuerst aus der Datenbank geladen werden. Danach können seine Attribute wie bei normalen Java Objekten über die Getter und Setter Methoden verändert werden. Wichtig hierbei ist, dass diese Methoden markModified() bzw. fetch() aufrufen, da der geladene Datensatz nur eine leere Hülle ist. markModified() signalisiert der Datenbank, dass Änderungen am Objekt vorgenommen wurden. fetch() signalisiert der Datenbank, dass die Daten des Attributes Lazy nachgeladen werden sollen.

  • Delete
Um einen Eintrag aus einer Datenbank zu löschen, muss dieser entweder zuerst geladen worden sein oder seine ID muss bekannt sein. Daraufhin stehen folgende Methoden zur Verfügung.
myGraph.removeVertex(person);
myGraph.removeVertexById(id);
  • Predicate Query Language

Abbildung 5: Beispiel einer 'Operator Expression' in PQL[2]

Die Predicate Query Language (PQL) ist Teil der Objectivity/DB und damit auch für InfiniteGraph verfügbar. Da es sich um eine Query Language handelt, werden nur Abfragen von Daten unterstützt. Manipulation oder das Erzeugen von Daten ist nicht möglich. PQL besitzt eine Menge von Operatoren die zusammen mit Operanden eine 'Operator Expression' bilden. 'Attribute Expressions' verweisen dabei auf Attribute bereits persistierter Objekte während 'Literal Expressions' Konstanten sind, die mit den Werten der Attribute verglichen werden (siehe Abbildung 5). Eine beispielhafte Abfrage in Java unter Verwendung eines Index kann folgendermaßen aussehen.
IndexIterable<Person> indexItr = personGraphIndex.query(new PredicateQuery("name='John' && age < 100")); Hierbei werden Personen aus der Datenbank geladen, deren Name „John“ ist und die jünger als 100 Jahre sind. Die Verwendung von 'Operator Expressions' ähnelt stark der Syntax von SQL. Die Verwendung von Regular Expressions ist ebenfalls möglich.

  • Traversierung

Abbildung 6: Traversierung eines Graphen in InfinityGraph[3]

InfiniteGraph unterstützt sowohl eine Breitensuche als auch eine Tiefensuche. Diese Suche kann von jedem Knoten im Graphen gestartet werden. Die Tiefen- bzw. Breitensuche kann durch den Entwickler manipuliert werden. Dazu können sowohl 'Path-' als auch 'Result Qualifier' implementiert werden. Ein 'Path Qualifier' entscheidet bei jedem Knoten ob der Weg weiter verfolgt wird oder nicht. Der 'Result Qualifier' entscheidet ob Pfade relevant für das Ergebnis sind. Dazu können, wie beim 'Path Qualifier', benutzerdefinierte Regeln implementiert werden. Um Ergebnisse zu verwerten müssen 'Result Handler' implementiert werden, die Pfade verwerten die als qualifiziert gelten. Abbildung 6 illustriert den detaillierten Ablauf eine Traversierung in InfiniteGraph. Im nachfolgenden wird ein Code Beispiel dargestellt welches durch eine individuelle Implementierung eines 'Result Handlers' die Knoten der durchlaufenden Pfade ausgibt. 'root' ist dabei der Startknoten für die Traversierung durch eine Tiefensuche.



PrintPathResultsHandler resultPrinter = 
  new PrintPathResultsHandler();

//Es wird ein Navigator erzeugt, der eine Tiefensuche durchführt
//und jeden Pfad bis zum Ende verfolgt.
//Dabei wird jeder Knoten dem ResultHandler übergeben
Navigator myNavigator = root.navigate
  (Guide.SIMPLE_DEPTH_FIRST, Qualifier.FOREVER,
   Qualifier.Any, resultPrinter);

myNavigator.start();
myNavigator.stop();

class PrintPathResultsHandler implements 
  NavigationResultHandler{

  @Override
  public void handleNavigatorFinished(Navigator arg0) {}

  @Override
  public void handleResultPath(Path path, Navigator arg1) {
    for(Hop h :path){
      System.out.println(h.getVertex().toString());
    }
  }


Bewertung

Im nachfolgenden werden die Vor- und Nachteile von InfiniteGraph betrachtet.
Vorteile

  1. Durch Objectivity/DB besitzt InfiniteGraph einen Unterbau, der bereits Persistenz, Replikation und Transaktionen implementiert.
  2. Eine sehr gute Unterstützung für die objektorientierte Programmiersprache Java vorhanden.
  3. InfiniteGraph bzw. Objectivity/DB hat mit seinen StorageUnits ein gutes Konzept zur Auslagerung von Daten auf entfernte Systeme.

Nachteile

  1. Sehr junges Projekt. Dies führt wahrscheinlich zu häufigen Veränderungen an der API.
  2. Keine uniqueness oder mandatory (not null) constraints für Properties an Knoten und Kanten. Dies kann allerdings durch Konzepte der objektorientierten Programmierung erreicht werden.
  3. Keine Netzwerkschnittstellen wie REST

Quellen

Allgemeine Quellen die im Text verwendet wurden

http://www.objectivity.com/pages/downloads/whitepaper/html/datareplication.html
http://wiki.infinitegraph.com/2.1/w/index.php?title=Tutorial:_Using_the_Navigator
http://wiki.infinitegraph.com/2.1/w/index.php?title=InfiniteGraph_System_Architecture
http://devnet.objectivity.com/files/docs/objy_docs/latest/java/guide/jgdObjectQualification.html#1180258
Stefan EDLICH, Achim FRIEDLAND, jens HAMPE, benjamin BRAUER, markus BRÜCKNER - NoSQL Einstieg in die Welt nichtrelationaler Web 2.0 Datenbanken - Hanser 2011

Quellen der verwendeten Grafiken [1] http://wiki.infinitegraph.com/2.1/w/index.php?title=InfiniteGraph_System_Architecture
[2]http://devnet.objectivity.com/files/docs/objy_docs/latest/java/guide/jgdObjectQualification.html#1180258
[3]http://wiki.infinitegraph.com/2.1/w/index.php?title=Tutorial:_Using_the_Navigator
[4]Objectivity/FTO and Objectivity/DRO Release 5.2

Kategorie Graphen-DB,Neue DB-Entwicklungen, NoSQL, I