Zusammenfassung. Analysen auf NoSQL-Datenbanken sind oft langdauernd und die Ergebnisse fur den Benutzer hau g schwer verstandlich. Wir prasentieren eine Moglichkeit, Datenmengen aus Wide-Column Stores mittels der Transformationssprache NotaQL zu transformieren sowie zu aggregieren und die Ergebnisse in Form von Diagrammen dem Benutzer darzustellen. Dabei kommen Sampling-Techniken zum Einsatz, um die Berechnung auf Kosten der Genauigkeit zu beschleunigen. Das von uns verwendete iterative Samplingverfahren sorgt fur eine kontinuierliche Verbesserung der Berechnungsgenauigkeit und bietet zudem Moglichkeiten zur Genauigkeitsabschatzung, die in Form von Kon denzintervallen in den Diagrammen dargestellt werden kann.
genannt und haben gemeinsam, dass jeder Eintrag uber eine eindeutige ID
identi ziert wird. Uber diese ID erfolgt auch die Partitionierung; ein
impliziter Index darauf erlaubt e ziente Lese- und Schreibzugri e. Da viele
NoSQLDatenbanksysteme keine komplexen Anfragen erlauben, werden oft
Datentransformationen mittels MapReduce oder hoheren Sprachen wie Pig [
Diese Arbeit beschaftigt sich mit der Visualisierung von Daten, die im
WideColumn Store HBase [
Im folgenden Kapitel stellen wir Sampling-Ansatze vor und erlautern, wie sich mit statistischen Methoden Abschatzungen uber die Genauigkeit machen lassen. Weiterhin prasentieren wir die Sprache NotaQL, mit der Transformationen auf der HBase-Datenbank ausgefuhrt werden konnen. In Kapitel 3 stellen wir ein Visualisierungswerkzeug vor, welches mittels Sampling-Methoden NotaQLTransformationen durchfuhrt und in Form von Diagrammen visualisiert. Dort wird erlautert, wie mithilfe von Whiskers die Berechnungsgenauigkeit im Diagramm dargestellt werden kann und wie ein iterativer Transformationsprozess diese Genauigkeit kontinuierlich steigern lasst. Kapitel 4 beinhaltet Ergebnisse von Experimenten, die die Performanz des iterativen Samplingprozesses analysieren. Nach einer Vorstellung verwandter Arbeiten in Kapitel 5 folgt eine Zusammenfassung in Kapitel 6. 2
Dieses Kapitel beinhaltet die mathematischen und technischen Grundlagen zur Ausfuhrung von Sampling-basierten Tabellentransformationen, die fur die Visualisierung genutzt werden. Wide-Column Stores bieten eine simple API, um komplette Tabellen zu scannen und bestimmte Zeilen anhand ihrer ID (rowid ) abzurufen. Wegen des exiblen Datenmodells kann keine Aussage uber die Spaltennamen einer Tabelle gemacht werden. Aus diesen Grunden kommt im Rahmen dieser Arbeit kein SQL zum Einsatz, sondern die Transformationssprache NotaQL.
In Tabelle 1 wird der zeitliche Verlauf von Spritpreisen gespeichert. Die Tabelle besteht aus zwei sogenannten Spaltenfamilien, die beim Erstellen der Tabelle de niert werden. Die erste Spaltenfamilie "Spritpreise\ zeigt die Spritsorten, die eine Tankstelle anbietet, sowie deren Preise. Die zweite Spaltenfamilie "Informationen\ hingegen listet den Tankstellennamen sowie die Stra e auf. row id Spritpreise Informationen
2014-11-07 12:32:00 1,319 1,489 FillItUp Rue de Gaulle
2014-11-07 21:30:00 1,409 FillItUp Rotweg
2014-11-08 04:30:00 1,409 1,509 FillItUp Rue de Gaulle
2014-11-08 05:30:00 1,389 FillItUp Rotweg
2.1
In [
Folgendes ist ein NotaQL-Skript, welches angewandt auf Tabelle 1 zur Berechnung des Durchschnittspreises fur die einzelnen Spritsorten der Tankstellenkette "FillItUp\ dient:
IN-FILTER: Informationen:Tankstelle = 'FillItUp', OUT. r <- IN.Spritpreise: c,
OUT.aggr:AVGPreis <- AVG(IN.Spritpreise: v);
Das Skript ist wie folgt zu verstehen: Die erste Zeile fuhrt eine ZeilensSeplaekltteinernuanmgendu"rTchan.kEstselwlee\rddeenr SnpuarltZeeniflaemnilmieit"IdnefmormWateirotne"nF\illaIutUsgpe\wainhltd.eImn der zweiten Zeile wird beschrieben, dass die Spaltennamen der Spaltenfamilie "Spritpreise\ (IN.Spritpreise:_c) die neuen row-ids (OUT._r) sind. Es wird also fur jeden distinkten Spaltennamen in dieser Spaltenfamilie eine Zeile in der Ausgabetabelle erzeugt. Die dritte Zeile beschreibt nun die Anwendung der Aggregatfunktion AVG auf die Werte der Spaltenfamilie "Spritpreise\ (AVG(IN.Spritpreise:_v)); also eine Ermittlung des Durchschnittspreises je Snoarmtee.nD"AieVseGr PWreeirst\ w( OirUdT.daagngnr:inAVdGePrrSepiasl)teanbfgaemleiglite. D"aagsgEr\rguenbtneirs ddeemrTSrpaanlstfeonr-mation ist in Tabelle 2 zu sehen.
row id
aggr
2.2
Durch die Verwendung von Sampling lassen sich Datentransformationen auf
Kosten der Berechnungsgenauigkeit um einen beliebigen Faktor beschleunigen.
Sampling wird verwendet, um eine Stichprobe, also eine Teilmenge, aus einer
Grundgesamtheit zu ziehen und anhand dieser Statistiken, wie Ergebnisse von
Aggregatfunktionen, der Grundgesamtheit abzuschatzen. Je reprasentativer
eine solche Teilmenge ist, also je mehr ihr prozentualer Aufbau dem der
Grundgesamtheit gleicht, desto genauere Hochrechnungen und Schatzungen erlaubt
sie. Es existieren verschiedene Techniken zum Ziehen von Stichproben [
Diese Technik kann mit und ohne Zurucklegen der Elemente durchgefuhrt werden. Wir betrachten letzteres, da durch das Vermeiden von Duplikaten in der Stichprobe im Allgemeinen eine hohere Genauigkeit erreicht wird. Jedes Element der Datenmenge hat die gleiche Wahrscheinlichkeit p%, um in die Stichprobe aufgenommen zu werden. Laut dem Gesetz der gro en Zahlen betragt der Stichprobenumfang n somit N p=100, wobei N dem Umfang der Datenmenge entspricht. Die Vorteile dieser Technik liegen in der einfachen Umsetzbarkeit, und dass keine weitere Informationen, wie die Hau gkeitsverteilung des Merkmals, uber die Datenmenge vorliegen mussen. Au erdem ist diese Technik unbiased, das hei t, dass kein Element bei der Auswahl bevorzugt wird, was zu einer Verzerrung der Hau gkeitsverteilung in der Stichprobe fuhren konnte.
Iteratives Sampling Der Samplingprozess besteht aus mehreren Iterationen
von einfachen Zufallsstichproben. Es emp ehlt sich eine kleine Startgro e zu
wahlen, um bereits nach kurzer Zeit Ergebnisse zu sehen. Die iterative Ausfuhrung
mit immer gro er werdender Stichprobengro e sorgt nicht nur fur die
kontinuierliche Verbesserung der Berechnungsgenauigkeit, sondern liefert auch die
notwendigen Informationen, um ebendiese Genauigkeit mathematisch berechnen zu
konnen. Der Prozess kann abgebrochen werden, wenn fur den Nutzer eine
ausreichende Genauigkeit erzielt wurde. Alternativ ist der Prozess dann beendet,
sobald die Stichprobengro e 100% der Grundmenge betragt. In [
Hochrechnung Bei der Verwendung der Aggregatfunktionen SUM und COUNT ist das Ergebnis einer Berechnung nicht direkt aussagekraftig fur die Grundgesamtheit, wenn die Berechnung nur eine Teilmenge betrachtet hatte. Das Ergebnis muss somit zuerst mit dem Faktor 100=p hochgerechnet werden, wobei p der Samplingwahrscheinlichkeit entspricht.
Kon denzintervalle Durch die Verwendung von Sampling und beim
Hochrechnen der Ergebnisse von Aggregatfunktionen ergibt sich eine gewissen
Berechnungsungenauigkeit. Um diese Ungenauigkeit auszudrucken, werden
ci%Kon denzintervalle verwendet. Dabei gilt, dass je gro er ci% ist, desto gro er
ist auch das Intervall. Beispielsweise wird Tabelle 1 als Stichprobe betrachtet und
anhand dieser Daten der Durchschnittspreis fur Diesel geschatzt. Dieser
Durchschnittswert, genannt Stichprobenmittel x, ist in Tabelle 2 gelistet. Die
Berechnung eines 50%-Kon denzintervalles liefert nun das Intervall [
Fur die Berechnung der Intervalle wird neben dem Stichprobenmittel x auch die Varianz der Stichprobe, genannt Stichprobenvarianz s2n, benotigt. Dieser Wert ist ein Ma fur die Streuung der Daten in der Stichprobe.
x = 1 Xn xi n
i=1 Mittelwert:
Varianz:
Dabei entspricht n dem Stichprobenumfang und xi dem i-ten Element in der Stichprobe. Die Stichprobenvarianz weist weiterhin eine systematische, nichtzufallige Abweichung auf. Das Ausma dieser Abweichung wird Bias oder Verzerrung genannt. Zur Korrektur wird der Faktor n=(n 1) verwendet. Dieser Faktor wird als Bessel-Korrektur bezeichnet. Daraus berechnet sich dann die korrigierte Stichprobenvarianz s2.
s2 = n (2)
Die Quadratwurzel aus der korrigierten Stichprobenvarianz liefert die Stichprobenstandardabweichung . Diese ist ein Ma fur die Streuung der Daten um das Stichprobenmittel.
n 1 s2n s2n = n1 Xn xi2 i=1 x2 (1) (3) = ps2
Die Berechnung der Kon denzintervalle erfolgt nun nach der
ChebyshevFormel [
Aktuell gilt die Formel 4 nur fur die Aggregatfunktion AVG. Eine Erweiterung dieser fur die Aggregatfunktion SUM ist moglich durch die Multiplikation der Grenzen mit der Anzahl N an Datensatzen in der Grundgesamtheit. N kann bei Verwendung der einfachen Zufallsstichprobe aus der Stichprobengro e n und der Sampling-Wahrscheinlichkeit p hergeleitet werden.
Die Chebyshev-Formel gilt als eine konservative Abschatzung, da sie meist Intervallgrenzen berechnet, die nicht nur das gewunschten Kon denzniveau abdecken, sondern auch uberschreiten. Es wird also meist ein zu gro es Intervall berechnet. Jedoch kann es auch zu einer Unterschreitung des Niveaus kommen, wenn die geschatzte Standardabweichung stark von der wirklichen abweicht und diese daruber hinaus noch sehr gro ist. Der Vorteil dieser Formel ist die einfache Berechenbarkeit und die Anwendbarkeit auf jede beliebige Werteverteilung, solange das Stichprobenmittel sowie die Stichprobenvarianz berechenbar sind. 3
Das Ziel dieser Arbeit ist die Visualisierung von Daten aus einem Wide-Column Store, welche mit Hilfe von NotaQL-Skripten zuerst transformiert wurden. Der entsprechende Work ow wird in Abbildung 1 dargestellt. Gestrichelte Linien zeigen dabei Prozesse an, die nur im Zusammenhang mit einem iterativen Samplingprozess ausgefuhrt werden.
Zuerst erfolgt eine einfache
Zufallsstichprobe mit der eingestellten
SamplingWahrscheinlichkeit aus der
Eingabetabelle. Die HBase API stellt hierfur die
Klasse RandomRowFilter bereit. Die
Daten werden anschlie end gema der
gegebenen NotaQL-Vorschrift transformiert
[
Die Aggregatfunktionen AVG, COUNT, SUM, MAX, MIN werden in zwei Gruppen aufgeteilt. Gruppe eins besteht aus den beiden Funktionen MAX und MIN, deren Resultat ein bestimmtes Element der zu aggregierenden Werte darstellt. Die zweite Gruppe besteht aus den Funktionen AVG, COUNT, SUM, auf deren Resultat alle Werte einen direkten Ein uss haben.
MAX und MIN Die Funktionen der ersten Gruppe berechnen im Gegensatz zur zweiten Gruppe keinen Wert, sondern suchen den gro ten beziehungsweise kleinsten Wert aus einer Datenmenge heraus. Der gesuchte Wert ist also auf jeden Fall ein Bestandteil der Datenmenge. Werden diese Funktionen nun anhand einer Stichprobe ausgewertet, so kann man uber den gefunden Wert nur sagen, dass der wahre Wert nicht kleiner (im Falle von MAX) oder gro er (im Falle von MIN) ist. Weitere Aussagen anhand der Standardabweichung oder anderen Werten sind meist nicht aussagekraftig, da diese Funktionen die Ausreiser einer Verteilung als Ziel haben. Verringert sich jedoch ein mit der MAX-Funktion berechnetes Ergebnis in Iteration i + 1 gegenuber der vorherigen Iteration i, wird die vorherige Schatzung beibehalten, um eine Verschlechterung der Schatzwerte zu verhindern.
AVG, COUNT und SUM Die Funktionen der zweiten Gruppe berechnen anhand einer Datenmenge eine Statistik. Im vorherigen Kapitel wurden die Kondenzintervalle bereits erklart und gezeigt, wie diese fur die Aggregatfunktionen AVG und SUM berechnet werden konnen. Um auch Kon denzintervalle fur die Aggregatfunktion COUNT angeben zu konnen, wird die Berechnung dieser Intervalle mit dem iterativen Samplingprozess verbunden. Zur Berechnung der Kon denzintervalle verwaltet der Uncertainity-Computer fur jede Output-Zelle die Anzahl der gespeicherten Werte sowie deren Summe und Quadratsumme. Daraus konnen bei Bedarf in konstanter Zeit die Kon denzintervalle mit der Chebyshev-Formel (Gleichung 4) berechnet werden. Es werden somit mindestens zwei Werte, entsprechend mindestens zwei Samplingschritte, zur Berechnung benotigt, da sonst die Varianz 0 ist und somit kein Intervall berechnet werden kann. Dieses Berechnungsverfahren wird fur alle Aggregatfunktionen dieser Gruppe verwendet. 3.2
Diagramme wie Linien- oder Balkendiagramme dienen zur adaquaten
Darstellung gro er Datenmengen und bieten gro en Modi kationsspielraum. So lassen
sich Ungenauigkeiten von Daten, also Kon denzintervalle, mit Hilfe von
Whiskers (Abbildung 2) oder Deviation Areas (Abbildung 3) darstellen. Erstere
nutzen dafur einen kleinen vertikalen Balken und letztere heben das Kon
denzintervall farblich vom Hintergrund und anderen Linien ab. Wahrend Whiskers
auf beiden Diagrammtypen angewandt werden konnen, sind die Devation
Areas nur fur Liniendiagramme sinnvoll, da sie eine Interpretation des
Zwischenraums erlauben. Zur Umsetzung der Diagramme haben wir die Java Bibliothek
JFreeChart 1 verwendet und erweitert [
4
In diesem Kapitel demonstrieren wir anhand von Experimenten zum einen die Genauigkeit, die sich durch die Verwendung von iterativen Samplingtechniken erreichen lasst. Zum anderen analysieren wir die Performanz dieses Prozesses und vergleichen die Laufzeiten mit der einer vollstandigen Berechnung. Dazu betrachten wir zuerst anhand eines Tests mit Startsamplinggro e 1%, die pro Iteration um 1% steigt, den Verlauf der Kon denzintervallgrenzen und im darau olgenden Test wird die Verwendung verschiedener Startsamplinggro en mit entsprechender Erhohung pro Iteration evaluiert.
Wie in Abbildung 4 zu sehen ist, wachst mit steigendem Iterationsdurchlauf, also auch steigender Sampling-Wahrscheinlichkeit, die Berechnungsgenauigkeit der verwendeten Aggregatfunktion. Dadurch sinkt nicht nur im Mittel die Abweichung zwischen berechnetem und wahrem Wert, sondern auch die berechnete Standardabweichung, wodurch die Chebyshev-Formel anwendbar ist. Der berechnete Wert konvergiert also gegen den wahren Wert und somit konvergieren auch die Intervallgrenzen gegen den wahren Wert. Die Abbildung stellt einen iterativen Samplingprozess mit Startwahrscheinlichkeit 1% auf der Tabelle 1 dar. Die verwendete Transformationsvorschrift sorgt fur die Berechnung des Durchschnittspreises fur Diesel uber den kompletten Zeitraum und alle Tankstellen: OUT._r <- 'Diesel', OUT.Preis <- AVG(IN.Diesel). Die grune und die gelbe Linie stellen den Werteverlauf der oberen bzw. unteren Grenze des 95%-Kon denzintervalls dar. Die blaue Linie markiert den tatsachlichen Durchschnittspreis und die rote Linie den Verlauf der berechneten Durchschnittspreise. Au allig ist, dass manche berechneten Werte au erhalb des Kon denzintervalls liegen. So zum Beispiel der Wert, der mit einer Sampling-Wahrscheinlichkeit von 1 http://www.jfree.org/jfreechart/index.html
(rot), des 95%-Kon denzintervalls (grun, gelb) und des wahren Wertes (blau) nach
30% entstanden ist. Die Abweichung dieses Wertes zur Ideallinie ist, im Vergleich zu seinen Vor- und Nachgangern, wesentlich gro er. Dies lasst sich dadurch erklaren, dass die Stichprobe die Verteilung der Datenmenge ungenauer dargestellt hat. Es wurden also prozentual wesentlich mehr unterdurchschnittliche Werte in die Stichprobe eingelesen, als wirklich in der Datenmenge vorhanden sind. Es ist also eine zufallige Verzerrung aufgetreten. Obwohl der berechnete Wert au erhalb des Kon denzintervalls liegt, enthalt dieses in jedem Iterationsschritt dennoch den wahren Wert. Weiterhin ist zu erkennen, dass fur den ersten Iterationsschritt und fur das komplette Auslesen der Datenmenge, wie bereits erwahnt, kein Kon denzintervall berechnet wurde.
Fur das nachste Experiment wurde die folgende Transformationsvorschrift verwendet: OUT._r <- IN._c, OUT.avg <- AVG(IN._v); Diese fuhrt fur jeden Spaltennamen eine Durchschnittswertberechnung aus.
Eine HBase-Tabelle wurde von einem Daten- 100% generator mit zehn Million Zeilen gefullt, von 80% denen jede drei Spalten mit Zufallszahlenwerten im Intervall [0; 1500] haben. Zudem wurden wei- reu60% tere Testtabellen generiert und dabei die Anzahl aD40% der Zeilen und Spalten variiert. Alle Tests wur- 20% den auf einem Zweikern-Prozessor (je 2,1 GHz) sowie 3,9 GB RAM durchgefuhrt. Als Wide- 0% 0% 50% 100% Column Store wurde eine HBase Standalone Da- Samplinggröße tenbank (Version 0.98.7) verwendet.
Abbildung 5 zeigt die Abhangigkeit der Berechnungsdauer von der Samplinggro e. Es fallt Abb. 5. Berechnungsdauer relativ zur vollstandigen Berechnung (blaue Linie). Zum Vergleich die Optimallinie (orange). auf, dass bereits eine 1% Samplingberechnung zehn Prozent der Dauer im Vergleich zur vollstandigen Berechnung benotigt. Mit zunehmender Samplinggro e nahert sich der Zusammenhang nahezu der Optimallinie.
Im Folgenden wird der iterative Samplingprozess auf der gleichen Tabelle (10 Mio. Zeilen, 3 Spalten) genauer untersucht. Dazu wurden auf dieser Tabelle vier iterative Samplingprozesse mit den Startwahrscheinlichkeiten 1%, 5%, 10% und 20%, mit entsprechender prozentualen Erhohung pro weiterem Iterationsschritt, durchgefuhrt (siehe Abbildung 6). Zum Vergleich wurde eine vollstandige Transformation ohne die Verwendung von Sampling ausgefuhrt. Diese dauerte knapp zehn Minuten und ist als rote Linie in Abbildung 6 eingezeichnet. Ein iterativer Samplingprozess besitzt gegenuber der Verarbeitung ohne Sampling einen zeitlichen Vorteil, solange seine kumulierte Dauer geringer ist als die Dauer fur die komplette Verarbeitung. Die Verwendung der Startwahrscheinlichkeit 1% liefert zwar am schnellsten die ersten Ergebnisse, jedoch sind diese recht ungenau und liefern somit nur eine grobe Approximation. Nach acht Schritten hat der Sampling-Prozess seinen Zeitvorteil verloren und nur 8% der Datenmenge im letzten Schritt verarbeitet. Mit steigender Startwahrscheinlichkeit erhoht sich die Dauer bis zum ersten Ergebnis, dafur steigt aber auch die maximal mogliche Anzahl an ausgelesenen Daten. So ist mit einer Startwahrscheinlichkeit von 20% die Ausfuhrung von bis zu zwei Iterationsschritten sinnvoll und somit werden 40% der Datenmenge im zweiten Schritt ausgelesen. Wie in Abbildung 4 zu sehen ist, ist die Berechnungsgenauigkeit bereits bei einer Samplinggro e von 10 bis 15% fur viele Anwendungen ausreichend. Diese Gro e ist nach zwei bis drei Iterationen zu je 5% erreicht, was in der Halfte der Zeit gegenuber einer vollstandigen Berechnung ausgefuhrt werden kann. Die direkte Wahl einer gro eren Samplinggro e wurde zwar die gleichen Ergebnisse bereits nach kurzerer Zeit und nur einer Iteration liefern. Dafur kann dem Benutzer allerdings keine Information uber die Berechnungsgenauigkeit mittels Whiskers und Deviation Areas gegeben werden.
Die Wahl der Startwahrscheinlichkeit hangt somit von der gewunschten Berechnungsdauer fur das erste Ergebnis und der Approximationsgenauigkeit ab. Dabei bezieht sich die Approximationsgenauigkeit auf die maximale SamplingWahrscheinlichkeit und etwaige berechnete Kon denzintervalle. 5
Sowohl Datenvisualisierungen als auch Sampling-Verfahren kommen oft zum
Einsatz, wenn es um die Analyse gro er Datenmengen geht. In [
EARL [
5% 10% Startsamplinggröße und Erhöhungswert 20%
Iteration 1 Iteration 2 Iteration 3 Iteration 4 Iteration 5 Iteration 6 Iteration 7 Iteration 8 Iteration 9
zu machen. EARL fuhrt dabei Transformationen kontinuierlich durch. Unser Ansatz dagegen ist iterativ, was den Vorteil hat, dass auch ohne Bootstrapping eine Genauigkeitschatzung moglich ist, namlich uber die Varianz der Ergebnisse verschiedener Iterationen. Beim Bootstrapping wird eine Stichprobe in Unterstichproben zerlegt, sodass die die aggregierten Resultate auf diesen kleineren Mengen basieren.
In [
Wir haben gezeigt, dass bei der Ausfuhrung von Tabellentransformationen Sampling-Techniken dazu beitragen konnen, fruh erste Ergebnisse zu sehen. Eine Visualisierungssystem ist in der Lage, HBase-Tabellen als Linien-, Balken- oder Kreisdiagramm darzustellen sowie weitere Iterationen auf vergro erten Stichproben im Hintergrund weiterlaufen zu lassen. Die Ergebnisse mehrerer Iterationen konnen fur die Genauigkeitsberechnung verwendet werden, die mittels Whisters und Deviation Areas in die dargestellten Diagramme eingezeichnet werden konnen. Dadurch erhalt der Benutzer nicht nur nach kurzer Zeit erste Ergebnisse einer Berechnung, sondern auch eine Information uber deren Genauigkeit und die Moglichkeit, eine Berechnung vorzeitig abzubrechen, wenn die gewunschte Genauigkeit erreicht ist. Wir haben mittels Experimenten gezeigt, dass dieses Vorgehen deutlich schneller ist als eine vollstandige Berechnung, und dass die Ungenauigkeit bereits bei geringen Stichprobengro en so minimal ist, dass die Diagramme, die dem Benutzer gezeigt werden, im Wesentlichen so aussehen, als wurden sie auf der kompletten Datenbasis basieren.
Literatur