Datenbanken Online Lexikon TH Köln, Campus Gummersbach
Aktuelle Änderungen - Suchen:

FlockDB

Steckbrief

Webadresse: https://github.com/twitter/flockdb
Kategorie: Graphdatenbank
API: Java, Ruby via Thrift
Geschrieben in: Scala, Ruby und Java
Replikation: realisiert durch Gizzard
Skalierung: Sharding (horizontale Skalierung) & Replication durch Gizzard
Lizenz: Opensource (Apache Licence Version 2)
Entwickelt f�r: Twitter � zur Speicherung der sozialen Verbindungen zwischen den Usern
Zugriffsm�glichkeiten: Ruby client



Entstehung / Historie

Im Jahre 2010 ver�ffentliche Twitter unter dem Namen FlockDB eine eigene NoSQL Datenbank, die als typische Graphendatenbank gilt. Diese Datenbank hat den Zweck die sozialen Verbindungen zwischen den Usern abzubilden. Es wird also die Frage beantwortet, welcher User wem folgt. Die Tweets, also die Nachrichten, die bei Twitter gepostet werden, haben mit dieser Datenbank nichts zu tun. F�r diesen Zweck wird die NoSQL Datenbank Cassandra eingesetzt.
Bei dem f�r FlockDB konzipierten Einsatz ist hohe Performance die wichtigste Eigenschaft. FlockDB ist daf�r ausgelegt bis zu 20.000 Schreibvorg�nge und bis zu 100.000 Lesezugriffe pro Sekunde abzuwickeln. Der Fokus f�r den Einsatz von FlockDB liegt auf einstufigen Graphen. F�r Taversierungen des Graphen und den Aufbau von Baumstrukturen ist FlockDB nicht geeignet. Vielmehr steht die Verwaltung von gro�en Adjazenzmatrizen und schnelle Schreib- und Lesevorg�nge im Vordergrund.

Datenmodell

Das Datenmodell von FlockDB ist fest definiert und l�sst sich nicht anpassen. Es werden Graphen in Form von Kanten gespeichert, die mit folgenden Attributen belegt sind:

AttributDatentyp
source_idInteger (64 bit)
destination_idInteger (64 bit)
positionInteger (64 bit)
stateInteger (64 bit)

Der Prim�rschl�ssel ist eine Kombination aus source_id, state und position.

Das Feld �source_id� stellt die ID des Users dar, der als Quelle der Kante dient. Bei Twitter erh�lt jeder User eine eindeutige ID, die im Datentyp Integer mit 64 Bit L�nge gespeichert wird.
Die �destination_id� bildet die eindeutige Identifikationsnummer des Users ab, dem der User (source_id) folgt.
�position� ist ein Datenfeld, dass ausschlie�lich zur Sortierung der Follower dient. Es wird ein Timestamp gespeichert, mit dem der Zeitpunkt des �Folgens� festgehalten wird. �ber dieses Feld wird absteigend sortiert, sodass eine Liste der Follower erstellt werden kann, wobei die neusten Follower oben angezeigt werden. Diese Liste wird standardm��ig dargestellt, wenn man sich seine eigenen Follower bei Twitter anzeigen l�sst.
In dem Attribut �state� wird der Status der Beziehung, also der Kante des Graphen festgehalten.
Hier werden drei Auspr�gungen unterschieden:

normal: Beide User sind aktiv und die Followerbeziehung besteht unangefochten.

removed: Trennt man als Nutzer die Verbindung zu einem Follower wird diese nicht direkt in der Persistenzschicht der Datenbank gel�scht. Die Kante wird mit dem Status �removed� markiert, aber noch nicht endg�ltig gel�scht.

archived: Wird ein Account (von dem User selbst, oder von Twitter) gel�scht, werden alle zugeh�rigen Kanten mit dem Status �archived� markiert. Abh�ngig von einem in den Terms of Service von Twitter definierten Zeitraum hat der User die M�glichkeit seinen Account wiederherzustellen. Solange m�ssen alle Kanten gespeichert bleiben.

FlockDB speichert jede Kante zweifach. Einmal zur Beantwortung der Frage �Wem folge ich?� und �Wer folgt mir?�. Die vorw�rts gerichteten Datens�tze mit Bezug auf die erste Frage werden nach der source_id partitioniert, w�hrend die r�ckw�rtsgerichteten (�Wer folgt mir?�) nach der destination_id partitioniert werden. Hierdurch ist gew�hrleistet, dass sich diese zusammengeh�rige Datens�tze auf einer Partition befinden und daher Abfragen besonders effizient durchgef�hrt werden k�nnen.

Architektur

Die FlockDB l�sst sich als eine Art Framework bezeichnen und setzt sich aus verschiedenen Komponenten zusammen. Eingehende Anfragen werden von der Middleware entgegengenommen. Die Middleware setzt sich aus beliebig vielen FlockDB Application Servern (Flapps) zusammen. Wesentlicher bestandteil der Flapps ist das Framework Gizzard. Neben der Kommunikation mit den Clients, welche �ber die App-Ports abgehandelt werden, stellen die Flapps einen Admin-Port f�r die Administration der Server mithilfe des Konsolentools Gizzmo zur Verf�gung. Als Schnittstelle zwischen den (Web-) Clients und den Flapps dient das Apache Thrift Framework. Die Flapps werden an einen persistenten Datenspeicher angebunden um Informationen dauerhaft zu speichern.



Gizzard

Gizzard ist ein Scala Framework zur Erstellung verteilter Datenspeicher. Gizzard nutzt die starke Integration von Java und wird in einer JVM (Java Virtuell Machine) ausgef�hrt. Ziel von Gizzard ist es mittels dem sogenannten Sharding gro�e Daten und Datenmengen auf effiziente Weise zur Verf�gung zu stellen.

Sharding
Beim Sharding werden Informationen auf mehrere Systeme verteilt um einen schnellen und effizienten Zugriff zu gew�hrleisten. Dabei bedient sich das Sharding zweier Methoden um die Daten horizontal auf den Systemen skalieren zu k�nnen, der Partitionierung und der Replikation.

GraphPartitionierung
Bei der Partitionierung werden die Informationen in kleine Einheiten, den sog. �Chunks� zerteilt und auf den verschiedenen Systemen gespeichert. Dabei ist jede dieser Informationseinheiten klein genug um in k�rzester Zeit von einem der Systeme abgerufen und manipuliert zu werden.

Replikation
Mithilfe der Replikation werden mehrere Kopien eines Datensatzes auf mehreren Systemen verteilt gespeichert. Dadurch kann jedes System mit seiner eigenen Kopie der Daten arbeiten und �u�erst effizient viele Abfragen durchf�hren. Dar�ber hinaus wird das Gesamtsystem durch die Replikation der Daten resistenter gegen�ber Fehlern.

Dabei birgt das Sharding verschiedene Schwierigkeiten. Zum einen stellt es eine Herausforderung die Daten konsistent zu halten. Dar�ber hinaus muss ein sinnvolles Schema f�r die Partitionierung der Daten ermittelt werden. Hierf�r bietet Gizzard ein Template, welches die Partitionierung der Daten verwaltet. Die Regeln f�r die Partitionierung werden dabei in einer Tabelle gespeichert, welche daf�r sorgt, dass Informationen anhand von Schl�sselbereichen auf Partitionen abgebildet werden. Die Replikation der Daten verwaltet jede Partition f�r sich selber mithilfe einer Baumstruktur.

Partitionierung bei Gizzard




Gizzard Replikationsstruktur

Innerhalb der Baumstruktur wird zwischen physischen und logischen Shards unterschieden. Eine physische Shard repr�sentiert einen Datenspeicher. Eine logische Shard hingegen bildet einen Baum von weiteren Shards ab. Wobei jeder Zweig eine logische Transformation der Daten und ein Blatt einen Datenspeicher darstellt. Dies erm�glicht, eine leichtgewichtige und konsistente Manipulation der Shards.

 

 

Gizzard unterst�tzt jeden Datenspeicher sofern dieser den Datenaustausch �ber ein Netzwerk erlaubt und idempotente sowie kommutative Schreiboperationen gew�hrleistet. Dabei spielt es keine Rolle auf welche Art und Weise der Datenspeicher die Informationen ablegt und verwaltet. Somit kann ein relationales Datenbankmanagementsystem wie MySQL gleicherma�en wie ein Redis Key-Value-Speicher oder eine Apache Lucene Search-Engine als Speicher angebunden werden. Typische Clients f�r Gizzard sind Web front-ends wie php oder Ruby on Rails Anwendungen.

Schreib-Konflikte
Schreib-Konflikte enstehen, wenn zwei Manipulaitonen, auf denselben Datensatz mit unterschiedlichen �nderungen, durchgef�hrt werden. Da Gizzard keine Garantie daf�r gibt, dass Datens�tze in ihrer zeitlichen Reihenfolge der Manipulation abgelegt werden, muss dies bei der Modellierung des Datenschemas beachtet werden. Wie bereits erl�utert, hegt Gizzard den Anspruch, dass die Daten idempotent und kummutativ gespeichert werden k�nnen.

Gizzmo
Gizzmo ist ein Kommandozeilentool, dass die Kommunikation mit den Gizzard Clustern erm�glicht. Dieses Tool ist in Ruby geschrieben und unterliegt der Apache Licence Version 2.0. Gizzmo kommuniziert direkt mit den den Gizzard Servern und dient als Administrationswerkzeug. Dadurch k�nnen diese bearbeitet, neue Shards erstellt und verwaltet werden. Mittels des Befehls
gizzmo tables
k�nnen beispielsweise alle in dem Datenspeicher verwalteten Tabellen ausgegeben werden.

Abschlie�ende Betrachtung

Vorteile

  • schnelle Zugriffszeiten
  • schnelle Schreib- und Lesezugriffe (ca. 20.000 Schreibvorg�nge/Sekunde & 100.000 Lesezugriffe/Sekunde)
  • einfaches, klar verst�ndliches Datenmodell
  • OpenSource (kostenlos)



Nachteile

  • keine Traversierung
  • sehr spezielles Anwendungsgebiet
  • aufwendige Installation / viele Abh�ngigkeiten
  • kaum Dokumentation
  • OpenSource (kein Support)



Anwendungsgebiete
Bedingt durch das sehr spezielle Anwendungsgebiet wird FlockDB ausschlie�lich bei Twitter eingesetzt. Letztendlich k�nnten einige weitere Netzwerke, wie beispielsweise Instagram, FlockDB f�r die sozialen Verbindungen einsetzen.


Installation von FlockDB

Die Installation der FlockDB erfolgt �blicherweise auf einem Linux basierten Betriebssystem. Die folgenden Installationsanweisungen beziehen sich auf das Betriebssystem Ubuntu Linux 13.04. Die folgenden Pakete werden f�r Installation der FlockDB ben�tigt:

  • Java
  • ruby
  • mysql-server
  • sbt
  • gizzmo
  • subversion
  • g++
  • make
  • automake
  • flex
  • bison
  • python-dev
  • libboost-dev
  • libevent-dev
  • pkg-config
  • libtool
  • thrift-0.5.0


Nach der Installation zuvor aufgelisteter Pakete muss das Paket flockdb von github bezogen und kompiliert werden:
$git clone https://github.com/twitter/flockdb.git
$cd flockdb
$sbt update

Das Simple Build Tool (sbt) erstellt in dem Arbeitspfad einen Ordner �dist�. Dieser enth�lt ein Script (��dist/script/src/set-env.sh�) welches zum Starten des zuvor kompilierten Java-Archivs dient. Das Script richtet die MySQL Datenbank ein und beschreibt sie mit Testdatens�tzen.

Die Installation der FlockDB gestaltet sich als komplex und aufw�ndig. Eine detailliert Vorgehensweise f�r die Installation der FlockDB auf einem Ubuntu-Betriebssystem findet sich hier
Nach den Anweisungen der oben stehenden Anleitung folgen weitere Schritte zum Einrichten des Systems in der Demo der FlockDB-Projektseite


Datenabfrage und -manipulation

Um Datenbankabfragen und -manipulationen durchf�hren zu k�nnen wird der FlockDB-Ruby-Client verwendet. Nach der Installation (gem install flockdb) l�sst sich das Tool mithilfe der �interactive Ruby Shell� auf der Konsole nutzen.

Zum Starten des interactive Ruby Shell wird der Befehl �irb� auf der Konsole abgesetzt. Anschlie�end m�ssen zun�chst die FlockDB-Client Bibliotheken mittels des Befehls
>> require �flockdb�
importiert werden.

Um auf einer FlockDB arbeiten zu k�nnen, muss dazu eine Instanz erzeugt werden, welche diese abbildet:
>> flock = Flock.new �localhost:7915�, :graphs => { :follows => 1 }
Es wird eine Instanz mit dem Namen �flock� f�r die FlockDB auf dem Server �localhost�, mit dem Port �7915� erzeugt, in der der Graph �follows� betrachtet wird.

Um eine Kante hinzuzuf�gen, wird der folgende Befehl verwendet:
>> flock.add(SOURCE_ID, :follows, DESTINATION_ID)

Beispiel:
>> flock.add(50, :follows, 60)
User 50 folgt User 60
Tabelle �forwardXYZ�
Source_id = 50
Destination_id = 60
Tabelle �backwardXYZ�
Source_id = 60
Destination_id = 50


Um eine Kante zu l�schen muss der folgende Befehl abgesetzt werden:
>> flock.remove(SOURCE_ID, :follows, DESTINATION_ID)

Beispiel:
>> flock.remove(50, :follows, 60)
User 50 folgt User 60 nicht mehr


Eine Auflistung aller �follower� f�r der User �USER-ID� kann mit dem folgenden Statement abgefragt werden:
>>flock.select(nil, :follows, USER-ID).to_a
(Wer folgt User �USER-ID�?)

Beispiel:
>> flock.select(50, :follows, nil).to_a
Ausgabe: [60]
Wem folgt User 50 -> User 60
>> flock.select(60, :follows, nil).to_a
Ausgabe: [ ]
Wem folgt User 60 -> niemand

Die Auflistung wem der User �USER-ID� folgt:
>>flock.select(USER-ID, :follows, nil).to_a
(Wem folgt User �USER-ID�?)

Dr�ber hinaus lassen sich auch Schnittmengen, Differenzen und Vereinigungen bilden. Die folgende Abfrage zeigt alle User die dem User �USER-ID-1� und dem �USER-ID-2� folgen, jedoch von User �USER-ID-1� nicht �verfolgt� werden:
>>flock.select(nil, :follows, USER-ID-1).difference(flockdb.select(USER-ID-1, :follows, nil).intersect(USER-ID-2, :follows, nil)).to_a

Nachstehende Abfrage zeigt alle User die der User �USER-ID-1� oder der User �USER-ID-2� folgen:
>>flock.select(USER-ID-1, :follows, nil).union(flock.select(USER-ID-1, :follows, nil)).to_a


Quellen

edb - FH K�ln. (11. Juli 2011). Abgerufen am 30. Mai 2013 von http://wikis.gm.fh-koeln.de/Datenbanken/GraphReplikation

edb - FH K�ln. (15. August 2012). Abgerufen am 27. Mai 2013 von http://wikis.gm.fh-koeln.de/Datenbanken/Sharding

GitHub - Twitter - Gizzmo. (2012). Abgerufen am 01. Juni 2013 von https://github.com/twitter/gizzmo/

Kallen, N., Pointer, R., Kalucki, E., & Ceaser, E. (2012). GitHub - Twitter - FlockDB. Abgerufen am 28. Mai 2013 von https://github.com/twitter/flockdb

Pointer, R. (03. Mai 2010). Twitter - Blog - Introducing FlockDB. Abgerufen am 27. Mai 2013 von https://blog.twitter.com/2010/introducing-flockdb

Pointer, R., Kallen, N., Ceaser, E., Kalucki, J., Freels, M., & Maxwell, K. (2012). GitHub - Twitter - Gizzard. Abgerufen am 01. 05 2013 von https://github.com/twitter/gizzard

Popescu, A. (17. Januar 2013). myNoSQL - A Comparison of 7 Graph Databases. Abgerufen am 02. 06 2013 von http://nosql.mypopescu.com/post/40759505554/a-comparison-of-7-graph-databases

Tiwari, S. (2011). Professional NoSQL. Wrox.