=Paper=
{{Paper
|id=None
|storemode=property
|title=Cloud-Services und effiziente Anfrageverarbeitung für Linked Open Data
|pdfUrl=https://ceur-ws.org/Vol-850/paper_betz.pdf
|volume=Vol-850
|dblpUrl=https://dblp.org/rec/conf/gvd/BetzS12
}}
==Cloud-Services und effiziente Anfrageverarbeitung für Linked Open Data==
https://ceur-ws.org/Vol-850/paper_betz.pdf
Cloud-Services und effiziente Anfrageverarbeitung für
Linked Open Data
[Work in Progress]
Heiko Betz, Kai-Uwe Sattler
Department of Computer Science and Automation
TU Ilmenau, Germany
{first.last}@tu-ilmenau.de
ABSTRACT QL [2] auf. Dies ist eine graph-basierte Anfragesprache für
Der Verbreitungsgrad von Linked Open Data hat in den RDF-Daten. Sie definiert neben der Möglichkeit Daten abzu-
letzten Jahren massiv zugenommen. Stetig erscheinen neue fragen, ähnlich dem SQL aus der Datenbankwelt, ein Trans-
Quellen, die RDF-Daten frei zur Verfügung stellen. Aktu- portprotokoll zwischen verschiedenen SPARQL-Endpoints.
ell diskutiert die Bundesregierung über ein neues Gesetz, In SPARQL selbst werden Basic Graph Patterns (BGP) für
welches zur Offenlegung von Daten der öffentlichen Hand die Abfrage von Daten verwendet, die aus einem oder meh-
verpflichtet. Durch diese Maßnahme, steigt u. a. die Menge reren Tripeln bestehen. Hierdurch ergeben sich joinintensive
an Linked Open Data sehr schnell an. Es werden neue Ver- Abfragen, die eine weitere detaillierte Betrachtung benöti-
fahren benötigt, die mit sehr vielen RDF-Daten gleichzeitig gen.
eine effiziente, skalierbare und mit Garantien versehene Ab-
frage von Daten mittels SPARQL gewährleistet. In dieser Fallunterscheidung.
Arbeit wird ein reines In-Memory Shared-Nothing-System Für die Beantwortung von (komplexen) quellenübergrei-
vorgestellt, das die genannten Anforderungen in effizienter fenden Anfragen müssen nun zwei Fälle unterschieden wer-
Weise erfüllt. Hierfür werden verschiedenste Optimierungs- den [7]:
maßnahmen ergriffen, die das Potenzial moderner Hardware
umfassend ausnutzen. 1. Verteilter Ansatz: Daten bleiben in den Quellen. An-
fragen werden von einem Koordinator entgegengenom-
men, in Subanfragen aufgesplittet, den entsprechenden
1. EINFÜHRUNG Quellen zugesandt, von diesen bearbeitet und das Re-
Die Anzahl an verfügbaren Quellen für Linked Open Data sultat vom Koordinator entgegengenommen.
(LOD) wächst stetig an1 . Unter anderem wurde vor kurzem
von der Bundesregierung die Open Data-Initiative gestartet. 2. Data Warehouse Ansatz: Daten werden von verschie-
Es sollen Daten, die durch Steuergelder finanziert wurden, denen Quellen geladen, vorverarbeitet und lokal abge-
der Öffentlichkeit frei zur Verfügung stehen2 . Insgesamt geht legt (materialisiert). Anfragen können direkt durchge-
die Anzahl an verfügbaren LOD-Quellen in diesem hochver- führt werden. Die Quellen bleiben gleichzeitig erhalten.
teilten System in die Hunderttausende bzw. Millionen über.
Es werden disjunkte bzw. teils überlappende Daten bereit- Punkt 1 besitzt mehrere potenzielle Vorteile. Durch die Ver-
gestellt, die häufig untereinander verlinkt sind, jedoch nicht teilung wird ein Single Point of Failure (SPOF) vermieden.
immer einem gemeinsamen Qualitätsstandard entsprechen. Der Koordinator muss keine Daten speichern, da sie alle
Die innere Struktur von LOD entspricht dem Ressource in den Quellen vorliegen. Er muss nur einen geringen Spei-
Description Framework [1] (RDF) Aufbau. In diesem wer- cherplatz und nur eine geringe Rechenkapazität zur Verfü-
den Daten als Tripel repräsentiert (Subjekt, Prädikat und gung stellen. Ein wichtiger Punkt, der für eine Verteilung der
Objekt). Hierauf baut wiederum die Abfragesprache SPAR- Quellen spricht, ist, dass die Daten nicht an andere Unter-
1
nehmen herausgegeben werden müssen. Es können ’Firmen-
Die LOD-Cloud, welche nur einen minimalen Ausschnitt geheimnisse’ bewahrt werden. Als Nachteile ergeben sich je-
darstellt und unter http://www4.wiwiss.fu-berlin.de/ doch einige Punkte. Die Zerlegung von Anfragen in Subque-
lodcloud/state/ zu finden ist, umfasst mittlerweile ca. 31
Milliarden Einträge. ries und alle daraus folgenden Schritte sind ein hoch komple-
2
http://heise.de/-1429179 xes Problem (Parsing, Normalisierung, eingebettete Anfra-
gen ’herausdrücken’, Vereinfachung, Datenlokalisation, Op-
timierung). Zwei weiter nicht zu unterschätzende Nachtei-
le sind die fehlenden Kontroll- und Überwachungsmechanis-
men der Quellen. Die Antwortzeit in einem solchen Szenario
ist nach oben unbeschränkt. Es ergibt sich, dass keinerlei Ga-
rantien abgegeben werden können. Weiterhin ist durch die
Verteilung das verwendete Schema dem Koordinator gänz-
lich unbekannt. Viele Quellen sind zudem nicht in der Lage,
24th GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 29.05.2012 - 01.06.2012, Lübbenau, Germany. SPARQL-Anfragen zu verarbeiten. Sie liefern nur die Quel-
Copyright is held by the author/owner(s). len über einen Webserver aus. Wären SPARQL-Anfragen
möglich, wären Analyseanfragen à la Data Warehouse-Anfragen hierbei als Framework und nicht als reine Datenablage an-
auch nur bedingt möglich. gesehen werden. Neben SPARQL-Anfragen soll es den Be-
Die zentralen Nachteile des Punktes 2 sind die (i.) benötig- nutzer im gesamten Workflow unterstützen. Unter Work-
te Zeit zum Einsammeln aller Daten, die (ii.) Durchführung flow werden die Folgenden Operationen verstanden: Einfü-
einer Vorberechnung und das Problem, dass niemals gewähr- gen/Löschen/Ändern von Tripeln sowie die Abfrage/Analy-
leistet werden kann, dass (iii.) alle Daten aktuell sind. Zu- se von Daten. Unter dem Stichpunkt Analyse fallen sämtli-
dem wird (iv.) ein SPOF, sowie ein (v.) extrem hoher Spei- che Data-Mining-Aufgaben, die in einem Data-Warehouse-
cherplatz an einer einzigen zentralen Instanz in Kauf genom- Szenario möglich sind. Ein weiteres Ziel ist die Unterstüt-
men. Ein weiterer Nachteil beider Fälle ist das (vi.) unbe- zung von SLAs. Neben dem Garantieren von maximalen
kannte Schema und die (vii.) geringe Datenqualität. Im zen- Antwortzeiten sollen auch Garantien bezüglich der Verfüg-
tralisierten Fall kann jedoch auf die letzten beiden Probleme barkeit und der Aktualität von Daten, sowie einige ande-
effizient reagiert werden, indem entsprechende Indizes ange- re mehr beachtete werden. Letztendlich soll das System als
legt und/oder verschiedenste Optimierungen durchgeführt ein Cloud-Service für LOD-Daten propagiert werden. Das
werden. Eine entsprechende Datenvorverarbeitung kann zu- Ziel hierbei ist, Kosten für den Endbenutzer einzusparen.
dem davor gestartet werden, um die Datenqualität zu ver- Er möchte nur für den von ihm selbst verursachten Aufwand
bessern. Beides wird durch die einheitliche Form der Daten bezahlen (Service on Demand). Im alternativen Fall müsste
als reine Tripel unterstützt. Der große Vorteil, der sich aus eine eigene Infrastruktur aufgebaut werden, was häufig zu
dem zentralisierten Ansatz ergibt, ist die Möglichkeit, An- viel höheren Kosten führt.
fragezeiten zu einem bestimmten Prozentsatz zu gewährleis- Diese Arbeit beschäftigt sich mit einem Teil aus dem so-
ten, da sich das gesamte System unter der Kontrolle einer eben beschriebenen Zieles. Es soll ein erster Ansatz für einen
Instanz befindet. Weiterhin kann ein Scale-Out (Erhöhung Datenspeicher für Linked Open Data aufgezeigt werden, der
der Speicherkapazität (v.), Verbesserung der Antwortzeiten) mit sehr großen Datenmengen eine effiziente Anfrageverar-
und eine Replikation (Beseitigung SPOF (iv.), Verbesserung beitung ermöglicht. Hierfür ist ein zuverlässiges Scale-Out-
der Antwortzeiten) angestrebt werden. Zur Verringerung der Verfahren notwendig, welches vorgestellt wird. Des Weiteren
Speicherkapazität (v.) können effiziente Kompressionstech- soll das gewählte Verfahren auf eine wechselnde Anfragelast
niken verwendet werden, die zugleich lese- und schreibopti- reagieren können.
miert sind, was zu einer weiteren Verringerung des benötig-
ten Speicherplatzes führt. Durch die Verwendung von push 2. STATE-OF-THE-ART
und Bulk Load-Techniken zur Datenintegration anstelle von
Für die Verarbeitung von LOD existieren bereits viele
reinen pull-Techniken kann garantiert werden, dass die abge-
verschiedene Systeme, die RDF-Daten entgegennehmen und
fragten Daten aktuell (iii.) sind. Das Einsammeln von Daten
SPARQL-Queries ausführen. Einige bekanntere System sind
ist nur zu Beginn einmal nötig, wenn eine neue Datenquelle
Virtuoso [5], MonetDB [3], Hexastore [14], Jena [15] und
erschlossen wird (i. und ii.).
RDF-3X [11]. Virtuoso ist ein weitverbreitetes relationales
Der Mechanismus des Scale-Outs und der Replikation be-
Datenbanksystem, das aus allen Kombinationen des Subjek-
dingen jedoch, dass eine Zerlegung der Anfrage durchgeführt
tes, Prädikates und Objektes Indizes erzeugt. Somit kann
werden muss. Wobei dieser eine Nachteil durch die oben ge-
sehr schnell auf Daten zugegriffen werden. MonetDB ist ein
nannten Vorteile aufgewogen wird. Insgesamt sprechen viele
OpenSource Column-Store, der eine Menge von Zwischen-
Faktoren für die Verwendung eines zentralisierten Ansatzes.
ergebnissen im Speicher hält, um neue und ähnliche An-
Garantien bezüglich den soeben erwähnten Antwortzei-
fragen schneller bearbeiten zu können. Hexastore ist eine
ten sind äußerst komplex in ihrer Umsetzung und benötigen
In-Memory-Lösung. Es erzeugt aus allen möglichen Kom-
im extremen Fall viele vorallokierte Kapazitäten, die wäh-
binationen von Tripeln Indizes, die daraufhin in einer Lis-
rend normaler Nutzung brachliegen und hohe Kosten ver-
te abgelegt werden. Für die Vermeidung von Dopplungen
ursachen. Stattdessen werden sie nur während Lastspitzen
und zur Kompression werden Strings in einem Wörterbuch
benötigt. Folglich werden aus diesem Grund häufig prozen-
abgelegt. Jena ein bekanntes OpenSource-Projekt kann ver-
tuale Werte angegeben. Es sollen beispielsweiße 99,99 % aller
schiedene Datenspeicher verwenden. Einerseits können die
Anfragen in der maximal erlaubten Zeitspanne beantwortet
Daten in einem eigenen Format abgelegt werden, anderer-
werden. Erst ein solches Vorgehen erlaubt es, dass während
seits in einer relationalen Datenbank. Auch Jena verwendet
einer Lastspitze neue Kapazitäten hinzugenommen werden
ein Wörterbuch zur Kompression. RDF-3X verwendet auch
können (automatisierter Scale-Out). Das Ziel hierbei ist, zu-
mehrere Indizes, um alle möglichen Kombinationen abzu-
künftige Anfragen wieder innerhalb der gesetzten Antwort-
speichern und legt diese in B+-Bäumen ab. Zudem enthält
zeit beantworten zu können. Am Ende der Lastspitze wer-
es eine ausgeklügelte Anfrageoptimierung, die speziell auf
den die zusätzlich allokierten Ressourcen wieder freigege-
die Besonderheiten von RDF abgestimmt ist.
ben. Letztendlich werden hierdurch Kosten für den Betrei-
Werden alle vorgestellten Systeme genauer betrachtet, stellt
ber des Services eingespart. Wichtig zu erwähnen ist, dass
man fest, dass diese einige Nachteile besitzen. Entweder sind
die Garantie bezüglich der Antwortzeit nicht für jede belie-
diese auf bestimmte Operationen (lesen, ändern) und/oder
bige SPARQL-Anfrage garantiert werden kann. Stattdessen
Domänen getrimmt und/oder sind nicht skalierbar im Sinne
soll dies nur für gewöhnliche“ Anfragen gelten.
” eines Scale-Outs und somit ungeeignet für sehr große Da-
tenmengen. Stattdessen setzten sie auf die Leistung einer
Projektziel. einzigen Maschine, was zu einem erheblichen Performance-
Das Ziel dieses Projektes ist es, ein hochverfügbares, - , Speicherplatz- und Verfügbarkeitsproblem werden kann.
skalierbares und -effizientes System aufzubauen, welches meh- Weiterhin unterstützt keines der erwähnten Systeme Garan-
rere hundert Milliarden bzw. mehrere Billionen Tripel von tien bezüglich Antwortzeiten. Sie setzen zudem auf einen
RDF-Daten in einer materialisierten Form vorhält. Es soll Permanentspeicher, welcher I/O-Zugriffe erfordert. Dies er-
Query geführt werden. Die Verwendung einer reinen In-Memory
Pull Lösung basiert auf der Grundlage, zukünftig Antwortzeiten
... garantieren zu können.
Linked Open Data bestehen ausschließlich aus Tripeln, die
Datenquellen wiederum aus Strings bestehen. Werden die darin abgespei-
cherten Werte genauer untersucht, stellt man fest, dass die-
Push selben Stringwerte mehrmals auftreten. Hier ist eine Kom-
pression nützlich, um Speicherplatz einzusparen. Dies fällt
Innere Aufbau umso mehr ins Gewicht, da der Data-Warehouse Ansatz an-
gestrebt wird. Die naheliegenste Technik, ist der Einsatz ei-
nes rein lokalen Wörterbuches. In einem solchen wird jeder
Figure 1: Aufbau des Systems mit mehreren un- Stringwert auf eine eindeutige ID gemappt. Hierfür ist wie-
abhängigen Knoten, die untereinander verbunden derum eine effiziente Anfrageverarbeitung von Nöten, die im
sind. Annahme einer Query und Weitergabe an ei- folgenden Abschnitt beschrieben wird.
nem beliebigen Knoten. Einspielen von neuen Da-
tenquellen durch Push und Pull.
Kombinierte Row- und Column-Store.
Ein Chunk besteht intern aus einer Kombination von Row-
und Column-Store [9]. Jede logische Zeile enthält drei Spal-
höht wiederum sehr schnell die Antwortzeit. Eine Gewäh-
ten für Subjekt, Prädikat und Objekt, wobei in einem je-
rung von Garantien wird erschwert. Einige dieser Ansätze
den Feld nur ein einzelner Integerwerte abgelegt ist. Werden
sind zudem bereits mit wenigen Milliarden Tripeln über-
nun alle einzelnen Integerwerte eines Tripels mittels Shift-
fordert (Jena). Andere verwenden alte Konzepte für neuere
Operationen disjunkt zu einem Wert vereint, ergibt sich ein
Probleme (Virtuoso), was nicht immer zu einer optimalen
Wort mit 96 Bit Breite, wenn jeweils 32 Bit für Subjekt,
Lösung beiträgt.
Prädikat und Objekt angenommen werden. Somit wird die
Bezüglich den Garantien von Antwortzeiten, beschreiben
Datenzeile aus drei logischen Spalten zu einer physischen
die Autoren in [12] und [9] ein Verfahren zur Beantwortung
Spalte vereint, die in einem theoretischen Drittel der Zeit
von Anfragen in einem konstanten Zeitintervall. Dies wird
überprüft werden kann.
durch verschiedenste Optimierungen erreicht. Unter ande-
Moderne CPUs besitzen interne SIMD3 -Register die ei-
rem wird beschrieben, wie ein Row- und Column-Store mit-
ne Breite von 256-Bit besitzen. Diese wurde mit dem neu-
einander verschmolzen wird und trotzdem eine effiziente An-
en AVX4 -Befehlsatz von Intel eingeführt. In einem solchen
frageverarbeitung ermöglicht wird.
Register werden mehrere logisch getrennte Einheiten zu ei-
ner physischen Einheit verbunden, die in einer Instruktion
3. ARCHITEKTUR gleichzeitig bearbeitet werden können. Hierfür müssen die
Die Architektur des Gesamtsystems ist in Abbildung 1 einzulesenden Daten auf eine volle 2-er Potenz ergänzt und
aufgezeigt. Sie folgt dem typischen Scale-Out-Paradigma mit die Wortgrenze bekannt sein.
verschiedenen Shared-Nothing-Systemen (Kreise in der Mit- Werden die Fakten vereint, muss zuerst das 96 Bit Wort
te), die alle gleichberechtigt sind. Anfragen können von be- auf 128 Bit, ergänzt werden. Mit Hilfe der verfügbaren 256-
liebigen Knoten entgegengenommen werden. Im nächsten Bit können nun zwei logische Datenzeilen mit jeweils 128-
Schritt wird ein Queryrewriting durchgeführt und an die ent- Bit gleichzeitig überprüft werden. Theoretisch ergibt sich
sprechenden Knoten weitergegeben. Die Empfänger nehmen eine bis zu sechsfache Performancesteigerung. Mittels der
die umgeschriebenen Anfragen entgegen, bearbeiten diese Vermeidung von Sprung- und sonstigen Befehlen, die Leer-
und senden letztendlich das Ergebnis zurück. Nachdem alle lauf produzieren, ist dieses Verfahren sehr Cache freundlich.
Einzelergebnisse eingetroffen sind werden diese mittels ver- Einmal verwendete Daten können stur linear abgearbeitet
schiedener Join-Operationen zu einem Ergebnis verknüpft. werden. Zugriffe auf dem langsamen RAM werden damit
Dieses wird letztlich an den ursprünglich anfragenden Cli- vermieden. Insgesamt wird die Struktur moderner Hardware
ent als Ergebnis zurück gesandt. Auf der rechten Seite der sehr gut ausgenutzt und eine Performancesteigerung ergibt
Grafik ist ersichtlich, dass neue Daten mittels push- oder sich.
pull-Techniken eingespielt werden können und dies während Wie oben erwähnt, muss in diesem Fall eine Ergänzung
der Laufzeit, mit Einhaltung der Antwortzeitgarantien. von 96-Bit auf 128-Bit durchgeführt werden. Es verbleiben
32 ungenützte Bit. Diese können für eine weitere Spalte ver-
3.1 Lokale Verarbeitung wendet werden. In dieser kann die Sprache bzw. der Daten-
Die lokale Verarbeitungseinheit liegt auf einem Knoten typ des (Literal)Objektes vermerkt werden [1]. Sollten ent-
und besteht aus einem Java-Programm, sowie vorwiegend sprechende Filterbedingungen auftreten, können diese direkt
aus einer C++ In-Memory-Datenhaltung und Datenabfra- mit übernommen werden, was zu einer weiteren Performan-
gemöglichkeit, die LODCache genannt wird. Dies ist eine cesteigerung beiträgt. Andererseits können die 32-Bit pro
hochperformante, reine In-Memory Lösung für LOD, die den Spalte zu gering sein und entsprechend erweitert werden. Es
L2-, wenn vorhanden L3-Cache und die RAM-Struktur mo- ist auch eine Kombination aus beiden möglich (z. B. 40 Bit
derner Hardware effizient ausnutzt. Allokierte Datenfelder, pro Spalte und 8 Bit für Sprache und Datentyp).
sogenannte Chunks, entsprechen genau der Größe des L2- Durch die Verwendung von Integerwerten, die eine feste
Caches. Dies ermöglicht es sehr effizient auf Daten zuzugrei- Bitbreite besitzen, wird auf einen expliziten und unvorher-
fen, diese zu Bearbeiten und Berechnungen auf diesen durch-
3
zuführen. Des Weiteren können Anfragen an den LODCache Single instruction, multiple data
4
gestellt, sowie Änderungen und Einfügeoperationen durch- Advanced Vector Extensions
sehbar langen Stringvergleich verzichtet. Dies erhöht weiter 0 1 2
die Performance und verbessert die Antwortzeit. A
Wie zu erkennen ist, wird auf eine Erzeugung von zusätz- 0 1 2
lichen Indixes verzichtet. Dies ergibt sich aus der Speicherre- 0 2
B
1
striktion und dem nötigen Wartungsaufwand, der während
jeder Änderung anfällt. Hierdurch können Operationen un-
AB
201
vorhersehbar lange blockiert werden. Es sind keine Garan-
tien mehr möglich. Anstelle werden wie in einem gewöhn-
lichen Column-Store alle Elemente stetig geprüft. Dies ist Figure 2: Aufbau des Baumes nach dem Einfügen
durch moderne Hardware und der ständig steigenden Paral- von ’AB’ (Rechteck), welches über den Pfad 201 er-
lelisierung problemlos möglich. Sind c Cores gegeben, muss reichbar ist.
jeder Core nur maximal d cC c
e Elemente überprüfen, wobei
cC die Anzahl der Chunks angibt.
gleichzeitig effizient durchgeführt werden kann. Dies könnte
Lokale Anfrageverarbeitung. naiv erreicht werden, indem jeder nachfolgende Mapping-
Der LODCache besitzt keinerlei Logik für die Optimie- wert einige Zahlen zu seinem Vorgänger überspringt. Treten
rung von Anfragen. Aus diesem Grund ist eine vorgelagerte nun neue Einträge auf, können diese solange eingefügt wer-
Java-Applikation vorhanden. Diese nimmt SPARQL-Anfragen den, wie freie Plätze existieren. Ein Problem dieses Ansat-
entgegen, zerlegt diese, optimiert sie (lokale Optimierung) zes ist jedoch, dass nicht bekannt ist, in welcher Reihenfolge
und überführt sie in die Sprache des LODCaches. Dieser Strings auftreten und es ist gänzlich unbekannt an welcher
führt die entsprechende Operation durch und übergibt das freien Position ein Element eingefügt werden muss/soll (in
Ergebnis dem Java-Programm mittels JNI5 , dass die ermit- der Mitte, an der ersten oder letzten freien Position?). Eine
telten Daten an den Aufrufer sendet. falsche Position bedingt eine schnellere Reorganisation. Aus
Wird eine exakt Match Anfrage mit Subjekt1 , Objekt1 diesem Grund muss ein besser geeignetes Verfahren verwen-
und einem freien Prädikat ?p an den LODCache gesandt, det werden.
werden zuerst die Integerwerte der fest definierten Strings Ein solches wird für XML-Daten in [8] beschrieben. Die
gesucht und in ein Wort mittels Shift und logischen OR- Autoren zeigen ein rekursives Verfahren, um Daten in ei-
Operationen zu einer Maske (m) ergänzt. Dies wird mit- nem Baum abzulegen und eine eindeutige ID zu generie-
tels vier CPU-Operationen durchgeführt werden (COPY, ren. Hierfür wird auf jeder Ebene jede mögliche Verzweigung
SHIFT, OR, SHIFT). Die Operationen zum Filtern der Da- durchnummeriert6 . Nun wird zwischen geraden und ungera-
ten aus einem Chunk beschränken sich daraufhin nur noch den Elementen unterschieden. Die ungeraden Elemente sind
auf ein logisches AND und einen Vergleich (CMP), je Ein- vorhanden, um darin Werte sortiert aufzunehmen (durchge-
trag und Chunk. Die genaue Berechnung ist im Folgenden zogene Linie). Im Gegensatz zu den Ungeraden, denn die-
nochmals dargestellt. Wobei e das zu überprüfende Element se spannen einen neuen Unterbaum auf (gestrichelte Linie).
ist, m die Maske und r das Ergebnis als boolescher Wert. Soll ein neuer Wert eingefügt werden, wird dieser auf der
höchsten Ebene (sortiert) hinzugefügt, die (i.) mindestens
r = (e AND m) CMP m einen freien Platz besitzt und (ii.) lexikografisch den String
korrekt einordnet. Das neue Element kann nun über die Kon-
Werden Bereichsanfragen betrachtet, muss das Mapping katenation aller traversierten Baumverzweigungen eindeutig
der Strings auf Integerwerte eindeutig und ordnungserhal- identifiziert werden und wird sinnvollerweise in einem String
tend sein, da sonst immer das Wörterbuch zu Rate gezo- überführt. In Abbildung 2 ist ein Beispiel mit den Elementen
gen werden müsste. Dies bedeutet, jeder Integerwert muss ’A’, ’B’ und dem neuen Element ’AB’ gegeben. Durch die-
mit der lexikografischen Ordnung seines gegenüberliegenden sen Ansatz ist gewährleistet, dass sich neue Elemente immer
Strings übereinstimmen. Nur so können die in [9] aufge- zwischen zwei bereits bestehenden Elementen einsortieren
führten Operationen angewandt und die Performance von lassen. Problematisch an diesem Ansatz ist jedoch, dass be-
SIMD-Befehlen ausgenutzt werden. Hierfür muss zuerst der liebig viele Unterbäume generiert werden können, der Baum
minimale und maximale Integerwert der Bereichsanfrage er- zu einer Liste entartet und somit die Pfadlänge zu einem
mittelt werden. Daraufhin werden zwei Masken erstellt und Element sehr lang werden kann. Dies widerspricht jedoch
die Daten in den Chunks mit diesen, durch verschiedene lo- der oben genannten Forderung, nach einer festen Breite für
gische Operationen, verglichen. Elemente, sowie der Verwendung eines Integerwertes. Aus
diesem Grund muss eine Modifikation dieses Ansatzes ver-
Ordnungserhaltender Baum. wendet werden.
Ein Problem tritt jedoch beim Einfügen von neuen String- Anstelle eines Strings, um den Pfad eindeutig zu identifi-
werten auf. Diese werden meist lexikografisch zwischen zwei zieren, werden nun beispielsweise 32 Bit Werte verwendet.
bereits bestehenden Elementen eingeordnet. Somit müssten Im Folgenden werden weiterhin jeweils 2 Bit pro Ebene ver-
sich in einem naiven Ansatz alle IDs aller nachfolgenden wendet. Wobei für jede neue Ebene, die neu hinzukommen-
Stringwerte ändern. Das Wörterbuch und alle bestehenden den Bits an den bereits bestehenden Bits dahinter gehan-
Chunks müssen daraufhin überprüft und ggf. abgeändert gen werden (von der größten zur kleinsten Wertigkeit). Es
werden. ergeben sich insgesamt maximal 16 Ebenen. Von den mög-
Dies ist ein sehr großes und äußerst schwerwiegendes Pro- lichen vier (2b = 22 ) Werten pro Ebene können nur drei
blem, welches sich nicht vermeiden lässt. Es kann nur ver- verwendet werden (00, 01, 10). Dies ergibt sich daraus, da
sucht werden, dass die Reorganisation möglichst selten und der Wert 11 ungerade ist. In einem solchen müsste nach der
5 6
Java Native Interface In den weiteren Ausführungen wird von 0 gestartet.
00 01 10 Eingabe von Daten einen Hashwert, der genau einem Knoten
A 00 10
im Chord-Ring zugeordnet ist. Eine einfache Datenlokalisa-
01 tionsfunktion ist hierdurch gegeben. Der Vorteil, der hieraus
00 01 10 B entsteht ist ein globaler und flüchtiger Index, der keinerlei
Wartung benötigt und auf allen n Elementen gleichermaßen
AB
zur Verfügung steht.
100001 Für die Indizierung von RDF-Tripeln werden alle einstel-
ligen Kombinationen aus Subjekt, Prädikat und Objekt er-
Figure 3: Aufbau des Baumes nach dem Einfügen zeugt (s→op, p→so, o→sp). Diese werden nun mittels h(x)
von ’AB’ (Rechteck), welches über den Pfad 100001 auf den Ring verteilt, indem das zu indizierende Element in
erreichbar ist. h(x) gegeben wird und der entsprechende Knoten bestimmt
wird. Für dasselbe Literal ergibt sich immer derselbe Hash
und somit ist immer derselbe Knoten zuständig.
oben genannten Definition ein Element ablegt werden. Je-
doch existiert nach diesem kein weiteres gerades Element, Globale Anfrageverarbeitung.
womit nach einem falsch einsortierten Element kein weite- Im ersten Schritt wird eine beliebige SPARQL-Anfrage
res lexikografisch dahinter liegendes Element eingefügt wer- einem Client an einem beliebigen Knotenelement gesandt.
den kann. Dies würde eine frühere Reorganisation erzwingen, Der Empfänger wird zum Koordinator dieser Anfrage. Nun
was zu vermeiden ist. In Abbildung 3 ist das bereits weiter zerlegt er die SPARQL-Anfrage und überprüft, ob er alle
oben gezeigte Beispiel nochmals auf diesen Sachverhalt ab- Daten lokal besitzt. Ist dies der Fall, liest er die Daten aus
gebildet. und führt die gesamte Berechnung durch. Ansonsten leitet er
die umgeschriebenen Subanfragen an die zuständigen Kno-
Bewertung. ten weiter. Hierfür wird die Hashfunktion h(x) benötigt, in
Ein großes Problem dieses Ansatzes ist jedoch die geringe dem der nicht variable Teil einer jeden WHERE-Bedingung
Auslastung. So werden höchstens 50 % der möglichen Werte eingetragen wird. Während des Rewriting-Vorganges werden
verwendet und auch nur genau dann, wenn keine zusätzli- FILTER-Statements beachtet und in die Subqueries einbe-
chen Ebenen vorhanden sind. Somit treten wiederum sehr zogen, falls dies möglich ist (globale Optimierung). Durch
schnelle Reorganisationen auf. Auf der anderen Seite kann diese Technik arbeiten mehrere Knoten parallel an derselben
eine Reorganisation sehr schnell durchgeführt werden. Sie Ausgangsquery. Als Nebeneffekt wird die Datenmenge ver-
ist auf wenige logische Operationen pro Wörterbuch- und kleinert. Nach dem Erhalt der Subqueries arbeiten die Kno-
Chunk-Eintrag beschränkt (SHIFT- und OR-Operationen). ten diese ab (lokale Anfrageverarbeitung; siehe Kapitel 3.1)
Gleichzeitig kann durch eine Reorganisation die Ebenenan- und senden das Ergebnis an den Koordinator zurück. Die-
zahl verringert und somit die Anzahl an Bits pro Ebene ver- ser führt die benötigten Joins und die restlichen FILTER-,
größert werden. Die theoretisch mögliche Auslastungsgrenze GROUP BY-, HAVING-, ORDER BY-, LIMIT-, OFFSET-
steigt automatisch an. , Projektions-, usw. Operationen durch. Zum Schluss wird
das Ergebnis an den Client gesandt.
3.2 Globale Verarbeitung
Die globale Architektur besteht aus der Zusammenfassung Bewertung.
aller lokalen Verarbeitungseinheiten zu einer globalen Ein- Ein Problem dieses Ansatzes ist die mehrfache redundante
heit. Diese sind mittels der Technik eines Chord-Ringes [13] Datenhaltung derselben Daten in maximal drei verschiede-
miteinander verbunden. Er besteht aus n unabhängigen und nen Knoten und die dafür zweimal höhere Speicherkapazi-
gleichwertigen Elementen, die in einem geschlossenen Ring tät. Dies ist jedoch nur bedingt ein Nachteil. Durch den au-
angeordnet sind. Wobei jedes Element einen Vorgänger und tomatisierten Scale-Out-Mechanismus kann ein lokales Ele-
einen Nachfolger besitzt (siehe Abbildung 1; Doppeltpfeile ment entlastet werden, indem ein neuer Knoten einen Teil-
mit durchgehender Linie). Neben diesen Verbindungen exis- bereich der Hashwerte und die darin abgebildeten Daten für
tieren noch sogenannte Finger (siehe Abbildung 1; einfacher sich beansprucht. Ein weiterer Vorteil ist die Möglichkeit
Pfeil mit gestrichelter Linie). Dies sind zusätzliche unidirek- auf sehr große Anfragelasten dynamisch reagieren zu kön-
tionale Verbindungen, die mehrere Nachfolger überspringen nen. Es können automatisch neue Knoten hinzugefügt wer-
und somit für eine schnellere Kontaktaufnahme mit einem den, die einen Teil der Anfragelast übernehmen. Die Auftei-
beliebigen Element vorhanden sind. Wären diese nicht vor- lung des Speicherplatzes und Anfragelast, wird jeweils durch
handen, müsste eine Anfrage von einem Element zum an- die konsistente Hash-Funktion h(x) garantiert [10]. Durch
deren solange weitergereicht werden, bis der Empfänger er- den beschriebenen Scale-Out, wächst die maximale Pfad-
reicht ist (O(n)). Dies wird durch die Finger auf O(log2 n) länge nur bedingt an, da diese durch O(log2 n) definiert ist
verkürzt. (was einem Vorteil entspricht). Ein weiterer Vorteil ist, dass
zu jeder WHERE-Bedingung maximal ein Knoten involviert
Fragmentierungsfunktion. ist. Es müssen keine knotenübergreifenden Daten für bspw.
Für die Umsetzung eines Scale-Outs wird eine Fragmen- Bereichsanfrage gesammelt werden. Dies ist nur zwischen
tierungs- und Allokationsfunktion benötigt. Erstere definiert verschiedenen WHERE-Bedingungen nötig, die mittels Join
wie welche Daten aufgeteilt werden, letztere auf welchen verknüpft werden.
Knoten welches Element abgelegt wird. Beide sollten mög-
lichst einfach zu berechnen sein, da sie für jede Anfrage be-
nötigt werden (Datenlokalisation). Der Chord-Ring definiert 4. ZUSAMMENFASSUNG
hier bereits eine Hashfunktion h(x). Diese erzeugt durch die In dieser Arbeit wurde ein Ansatz vorgestellt, der mehre-
re Hundert Milliarden bzw. mehrere Billionen RDF-Tripel ge SPARQL-Anfragen ermittelt, die sich in Äquivalenzklas-
Linked Open Data effizient verwalten kann. Es wurde eine sen einteilen lassen. Den einfachen SPARQL-Anfragen, den
Unterscheidung in lokaler und globaler Verarbeitung durch- Anfragen, die eine Datenmanipulation erfordern sowie den
geführt. Die lokale Verarbeitungseinheit besteht aus einem analytischen SPARQL-Anfragen.
hochoptimierten In-Memory C++-Programm zur Datenhal-
tung und -abfrage, das die Strukturen moderner Hardware 6. REFERENCES
effizient ausnutzt. Im selben Abschnitt wurde eine Möglich- [1] Rdf - semantic web standards.
keit aufgezeigt, Bereichsanfragen effizient zu verarbeiten, in- http://www.w3.org/RDF.
dem ein ordnungserhaltendes Mapping von Strings auf In- [2] Sparql query language for rdf.
tegerwerten dargestellt wurde. Dies wird durch einen ord- http://www.w3.org/TR/rdf-sparql-query.
nungserhaltenden und updatefreundlichen Baum garantiert. [3] P. A. Boncz, M. L. Kersten, and S. Manegold.
Die globale Verarbeitungseinheit besteht aus dem Zusam- Breaking the memory wall in monetdb. Commun.
menschluss mehrerer lokaler Komponenten und verwendet ACM, 51(12):77–85, 2008.
hierzu die Technik des Chord-Ringes. Jedes Element ist gleich- [4] G. DeCandia, D. Hastorun, M. Jampani,
berechtigt, es existiert somit kein zentraler Koordinator. Für G. Kakulapati, A. Lakshman, A. Pilchin,
die Verbindung untereinander existieren Finger, die eine ma- S. Sivasubramanian, P. Vosshall, and W. Vogels.
ximale Anzahl an Weiterleitungen garantieren. Zur Verar- Dynamo: Amazon’s highly available key-value store.
beitung von beliebigen SPARQL-Anfragen werden diese von SIGOPS Oper. Syst. Rev., 41(6):205–220, 2007.
einem Knoten entgegengenommen, optimiert und an den be- [5] O. Erling and I. Mikhailov. RDF support in the
treffenden Knoten gesandt. Zur Datenlokalisation wird ei- virtuoso DBMS. In S. Auer, C. Bizer, C. Müller, and
ne einfache Hashfunktion und kein global zu pflegender In- A. V. Zhdanova, editors, CSSW, volume 113 of LNI,
dex benötig. Des Weiteren ist dieses Verfahren unabhän- pages 59–68. GI, 2007.
gig gegenüber der Anzahl an Tripeln und dem benötigten
[6] FU-Berlin. Berlin sparql benchmark.
Speicherplatz, da ein automatischer Scale-Out-Mechanismus
http://www4.wiwiss.fu-
existiert.
berlin.de/bizer/berlinsparqlbenchmark.
[7] A. Harth, K. Hose, M. Karnstedt, A. Polleres, K.-U.
5. AUSBLICK Sattler, and J. Umbrich. Data summaries for
In der weiteren Forschung müssen einige Punkte näher be- on-demand queries over linked data. In WWW, pages
trachtet werden, die als Motivation zu diesem Ansatz dienen. 411–420, 2010.
Hierunter fällt die Einhaltung der garantierten Antwortzeit [8] M. P. Haustein, T. Härder, C. Mathis, and M. W.
aller Anfragen bis zu einem vorher definierten Prozentsatz. 0002. Deweyids - the key to fine-grained management
Zur Unterstützung dieser Forderung ist eine Replikation der of xml documents. JIDM, 1(1):147–160, 2010.
Daten denkbar. [9] R. Johnson, V. Raman, R. Sidle, and G. Swart.
Dies führt zum nächsten Problem, der effizienten Replika- Row-wise parallel predicate evaluation. PVLDB,
tion. Bis zu diesem Zeitpunkt werden alle Daten nur auf ei- 1(1):622–634, 2008.
nem Knoten vorgehalten. Stürzt dieser ab, sind all seine Da- [10] D. R. Karger, E. Lehman, F. T. Leighton,
ten verloren und nachfolgende Anfragen können nicht mehr R. Panigrahy, M. S. Levine, and D. Lewin. Consistent
beantwortet werden. Als Ausweg bestünde die Möglichkeit, hashing and random trees: Distributed caching
ein ähnliches Vorgehen umzusetzen, wie es in Amazons Dy- protocols for relieving hot spots on the world wide
namo [4] implementiert ist. web. In F. T. Leighton and P. W. Shor, editors,
Zur weiteren Performancesteigerung ist es notwendig den STOC, pages 654–663. ACM, 1997.
LODCache weiter zu optimieren. Es existiert zum Beispiel
[11] T. Neumann and G. Weikum. RDF-3X: A RISC-Style
die Möglichkeit auf einer SandyBridge-CPU eine Schleife di-
Engine for RDF. In VLDB, Auckland, New Zealand,
rekt im CPU eigenen Loop-Cache abzulegen. Eine Perfor-
2008.
mancesteigerung von über 100 % soll möglich sein. Jedoch
[12] V. Raman, G. Swart, L. Qiao, F. Reiss, V. Dialani,
ist die Bedingung hierfür, dass alle Instruktionen höchstens
D. Kossmann, I. Narang, and R. Sidle. Constant-time
28 µ-Operationen lang sind.
query processing. In G. Alonso, J. A. Blakeley, and
Der oben beschriebene Ansatz zum Mapping von Strings
A. L. P. Chen, editors, ICDE, pages 60–69. IEEE,
auf ordnungserhaltende Integerwerte muss weiter erforscht
2008.
werden. Es ist u. a. notwendig, die Operationen zur Reor-
ganisation effizienter anzuordnen. Eine Möglichkeit zur Er- [13] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger,
höhung der Auslastung wird außerdem angestrebt. In die- M. F. Kaashoek, F. Dabek, and H. Balakrishnan.
sem Zusammenhang soll gleichzeitig ein Verfahren entwi- Chord: a scalable peer-to-peer lookup protocol for
ckelt werden, um Updates auf bestehende Daten möglichst internet applications. IEEE/ACM Trans. Netw.,
effizient durchzuführen. 11(1):17–32, 2003.
Für die weitere Entwicklung und Evaluierung des Systems [14] C. Weiss, P. Karras, and A. Bernstein. Hexastore:
wird zukünftig ein Benchmark eingesetzt. Es wurde der Ber- Sextuple Indexing for Semantic Web Data
lin SPARQL Benchmark [6] ausgewählt. Dieser erzeugt ak- Management. In VLDB, Auckland, New Zealand,
zeptierte Resultate und ist für das Testen von beliebigen 2008.
SPARQL-Systemen entwickelt worden. Für Skalierungstests [15] K. Wilkinson, C. Sayers, H. Kuno, and D. Reynolds.
kann ein Skalierungsfaktor angepasst werden, der die Anzahl Efficient RDF storage and retrieval in Jena2. In Proc.
an automatisch erzeugten Tripeln vergrößert. First International Workshop on Semantic Web and
Die Performanz des Systems wird durch verschiedenarti- Databases, 2003.