Neo4j – Eine Graphendatenbank – Veränderte Anforderungen

View Github Repository Open presentation in a new window

markuslamm

See all presentation from markuslamm

Neo4j – Eine Graphendatenbank – Veränderte Anforderungen

0 0

neo4j-presentation

On Github markuslamm / neo4j-presentation

Neo4j

Eine Graphendatenbank

Markus Lamm | s786697 | Beuth Hochschule für Technik Berlin

Veränderte Anforderungen

  • exponentiell steigend anfallenden Datenmengen
  • Twitter: 7 Terrabyte Daten täglich
  • Facebook: 25 Terrabyte Log-Daten täglich
  • weltweit gepeicherte digitale Daten 2011: 1800 Exabyte(10 ^18)
Quelle: Marktforschungsunternehmen IDC, Java Magazin 04.12
  • immer stärker werdende Vernetzung der Daten, hypertext, rss, blogs, wikis, social networks
  • Website als Graph aus Dokumenten und Links
  • Auflösung von Strukturen der Daten durch user generated content(videos, fotos, Dokumente), semi-strukturiert

NoSQL

  • "Not only SQL"
  • keine eindeutige Definition
  • nicht-relationale Datenspeicher

NoSQL-Typen

Key-Value-Store

(BerkeleyDB, Redis)
  • einfachste NoSQL-Technologie
  • konkurrierender Zugriff auf großes Datenvolumen
  • Caching als typischer Use-Case
  • Daten werden in großen Hash-Tabellen gespeichert, Zugriff über Schlüssel
  • kaum komplexe Datenstrukturen möglich
  • jedoch leichte Verteilung der Daten

Column-Family-Store

(BigTable, Cassandra, Amazon SimpleDB, HBase)
  • basieren auf Tabellen
  • mehrere Attribute pro Zeile
  • Attributname und -wert bilden Schlüssel-Wert-Paar - Spalte, Column
  • kein festgelegtes Schema, Anzahl der Spalten variabel
  • keine Joins, leichte Verteilung
  • leading technologies - Google’s BigTable and Cassandra, originally by Facebook

Document-Store (CouchDB, MongoDB)

  • Speicherung in Form von semi-strukturierten Dokumenten(JSON, XML)
  • schlechtere Performance und Skalierbarkeit
  • ??

Graph Database (Neo4j)

  • basiert auf den mathematischen Konzept der Graphen-Theorie
  • Daten werden in Form Graphen gespeichert
  • optimiert für Traversierung von Graphen
  • besteht aus Knoten und Kanten, optional Properties
  • "Property-Graph"

Knoten (Node, Vertex)

  • bilden die grundlegenden Einheiten eines Graphen
  • mit einer eindeutigen, fortlaufenden ID versehen
  • Eigenschaften, einfache Schlüssel/Werte-Paare
  • kein vorgegebenes Schema d.h. die verwendeten Schlüssel können sich von Knoten zu Knoten unterscheiden
  • Flexibilisierung im Vergleich zu relationalen Datenbanken, wo eigene Tabelle für jeden Knotentyp

Kanten (Relationship, Edge)

  • benannt, fortlaufenden ID
  • Start-Node und End-Node zwingend
  • gerichtet, X Fan von Y != Y Fan von X
  • Properties durch Schlüssel/Werte-Paare
  • Relationships sind Bestandteil der Daten, nicht teil eines fixen Schemas

Pfade (Paths)

  • Aneinandereihung mehrerer Knoten anhand von Kanten
  • Ergebnis von Suchanfragen an die Datenbank

Indices

  • Knoten und Kanten können jeweils anhand ihrer Eigenschaft indiziert werden
  • Ergebnis von Suchanfragen an die Datenbank, "Index-Lookup"
  • Lucene

Anwendungsgebiete

  • Social networks
  • Semantic Web
  • (Local) Recommendations
  • Geo-Processing
  • Network and Data Center Management
  • Routing (shortest path)
  • Search-Engines(Page-Rank)
  • Fraud-Detection

Cypher Query Language

  • deklarative Abfragesprache für Graphen, in Scala implementiert
  • (einfachste) Abfragen bestehen aus START, MATCH und RETURN
  • START: Ausgangspunkt ist einzelner oder Menge von Knoten oder Beziehungen, Referenzierung durch ID oder Index-Lookup
  • MATCH: beschreibt Traversierung des Graphen, stellt einen oder mehrere Pfade des Graphen dar
  • RETURN: welche Informationen werden aus dem gefundenen Muster zurückgegeben
  • Filterung mit WHERE, Sortierung mit SORT, etc...

Beispiele

START a=node:user(name='Michael') MATCH (a) -[:KNOWS]-> (b) -[:KNOWS]-> (c), (a) -[:KNOWS]-> (c) RETURN b, c START me=node:people(name='me') MATCH me-[:knows]->friends-[:knows]-> new_friends WHERE new_friends.age > 18 RETURN new_friends START actor=node:Actors(lastname = 'Clooney') MATCH actor-[:ACTS_IN]-> movie <-[:ACTS_IN]-coactor RETURN movie.title, coactor.name START actor=node:Actors(lastname = 'Clooney') MATCH actor-[:ACTS_IN]-> movie <-[:ACTS_IN]-coactor RETURN movie.title, coactor.nameSTART user=node:Users(name = 'user1') MATCH user-[r:RATED]->movie RETURN movie ORDER BY r.stars DESC LIMIT 10 start user=node:Users(name = 'me') match user-[:FRIEND]-> friend -[r:RATED]->movie RETURN movie ORDER BY AVG(r.stars) DESC, COUNT(*) DESC LIMIT 10

Anwendungsbeispiel

ein soziales Netzwerk

in relationaler Datenbank

  • typischerweise zwei Tabellen für Daten und Relationen

direkte Freunde eines Benutzers

select distinct uf.* from t_user_friend uf where uf.user_1 = ?

Freunde von Freunden eine Benutzers

select distinct uf2.* from t_user_friend uf1 inner join t_user_friend uf2 on uf1.user_1 = uf2.user_2 where uf1.user_1 = ?

Freunde von Freunden von Freunden eine Benutzers

select distinct uf3.* from t_user_friend uf1 inner join t_user_friend uf2 on uf1.user_1 = uf2.user_2 inner join t_user_friend uf3 on uf2.user_1 = uf3.user_2 where uf1.user_1 = ?

  • JOIN-Operation pro Ebene
  • bei großen Graphenstrukturen potentielle Performance-Probleme

in Neo4j Graphdatenbank

  • speichert Daten als Nodes und Relationships
  • User als Nodes, Freundschaft als Relationship zwischen User-Nodes

direkte Freunde eines Benutzers

START me=node:Users(name = 'me' MATCH me-[:KNOWS]->friends RETURN friends

Freunde von Freunden eine Benutzers

START me=node:Users(name = 'me') MATCH me-[:KNOWS]->friend-[:KNOWS]->friend2 WHERE not(me-[:KNOWS]-friend2) RETURN DISTINCT friend2 ORDER BY friend2.name"

Freunde von Freunden von Freunden eine Benutzers

START me=node:Users(name = 'me') MATCH me-[:KNOWS]->friend-[:KNOWS]->friend2-[:KNOWS]->friend3 RETURN DISTINCT friend3 ORDER BY friend3.name

Alternativ: Graph-Traversals

  • mächtige und effiziente API zur Abfrage Graphen-basierte Daten
  • fundamentale Operation: Durchlaufe eine Menge von Nodes, folge den definierten Relationships, während die Kriterien erfüllt sind
TraversalDescription traversalDescription = Traversal.description().relationships(“IS_FRIEND_OF”,Direction.OUTGOING) .evaluator(Evaluators.atDepth(2)) .uniqueness(Uniqueness.NODE_GLOBAL); Iterable nodes = traversalDescription.traverse(nodeById).nodes();

Neu: Websites und Likes

Welcher Freund mag was?

START me=node:Users(name = 'me') MATCH me-[:KNOWS]->friends-[:LIKES]->websites RETURN websites.url, friends

Was wird am meisten von meinen Freunden gemocht?

START me=node:Users(name = 'me') MATCH me-[:KNOWS]->friends-[:LIKES]->websites RETURN websites.url, COUNT(*) ORDER BY COUNT(*) DESC

Experiment

  • Dataset 1000 User
  • jeder User durchnittlich 50 Freunde
  • t_user: 1000, t_user_friend 1000 X 50 = 50,000 records

...relational, Ebenen 2, 3, 4

  • MySQL handles queries with depths 2 and 3 quite well
  • join operations are common in the relational world, most databases engines are designed and tuned with this in mind
  • with depths 4 and 5, significant loss of performance
  • limitation of MySQL when modelling graph data – deep graphs require multiple joins

...with graph traversal

TraversalDescription traversalDescription = Traversal.description() .relationships(“IS_FRIEND_OF”,Direction.OUTGOING) .evaluator(Evaluators.atDepth(1)) .uniqueness(Uniqueness.NODE_GLOBAL); Iterable nodes = traversalDescription.traverse(nodeById).nodes();

...

  • signifikant bessere Performance
  • Traversal von Freunden bis Ebene 4 vierfach schnelleer
  • Ebene 5: 10 Millionen mal schneller!!

now

  • t_user table: 1,000,000 records
  • t_user_friend: 1,000,000 X 50 = 50,000,000 records
  • gleiche Abfragen

relational

  • performance of depth-two query has stayed the same, design of the MySQL engine to handle table joins efficiently using indexes
  • depth 3 and 4 (3 and 4 join operations): worse results
  • query for all friends on depth 5 did not finish in one hour
  • MySQL relational database is optimized for a single join queries

...Neo4j

  • performance of depth-two query has stayed the same, design of the MySQL engine to handle table joins efficiently using indexes
  • depth 3 and 4 (3 and 4 join operations): worse results
  • query for all friends on depth 5 did not finish in one hour
  • MySQL relational database is optimized for a single join queries

Clever Quote