NoSQL Datenbanken. Wide Column Stores

NoSQL Datenbanken-Wide Column Stores

Bakkalaureatsarbeit SS2011

Mario Götzner Alpen-Adria Universität Klagenfurt Klagenfurt, Österreich

Abstract -In den letzten Jahren konnte man eine Veränderung in der Datenbankwelt ausmachen. Denn seit dem Web 2.0 Zeitalter werden die Systeme mit neuen Anforderungen konfrontiert. Bestehende relationale Datenbanken können diese Anforderungen nur bedingt erfüllen. Alte Denkansätze wurden wiederentdeckt und mit Optimierungsverfahren ausgestattet. Dadurch entstand eine neue Generation von NoSQL Systemen (Not Only SQL), die es ermöglichen, die ungeheuren Datenmengen, die bei Social Networks und Co. anfallen, effizient zu verarbeiten. In diesem Artikel werden Wide Column Stores, eine Unterkategorie der NoSQL Systeme, behandelt.

Keywords: NoSQL, Datenbanken, Bigtable, Wide Column Stores, BASE, Map/Reduce Framework, CAP, spaltenorientierte Datenorganisation, DSM, Paxos, Bloomfilter

I. EINLEITUNG

Das Kernziel der neueren NoSQL Bewegung besteht darin, Web-Scale-Datenbanken, also Datenbanken für die ungeheuren Datenmengen des Web 2.0 Zeitalters im Tera- bzw. Petabyte Bereich, zu entwickeln. Wenn solch große Datenmengen verarbeitet werden müssen, ist es von Vorteil wenn die Datenbank im Vornhinein auf Skalierung ausgerichtet ist. Eine weitere Anforderung bezieht sich auf die Verfügbarkeit der Daten in einem verteilten System. Es muss gewährleistet werden, dass bei Teilausfällen von einigen Knoten, das System als Ganzes noch lauffähig bleibt. [1] Das zweite Kapitel des Artikels soll eine Einordnung und Kategorisierung der unterschiedlichen Datenbankmodelle ermöglichen. In der dritten Sektion werden die grundlegenden Eigenschaften des Datenmodells von spaltenorientierten Datenbanken, die die Grundlage von Wide Column Stores bilden, behandelt. Im vierten Kapitel wird Google’s Bigtable, ein bestehendes Wide Column Store System analysiert. Im Speziellen werden das Datenmodell, die Infrastruktur und die Implementierung von Bigtable behandelt. Eingebettet in dieses Kapitel ist auch ein Performancevergleich zwischen verteilten Datenbanken. Im letzten Kapitel werden die Kernaussagen des Artikels zusammengefasst und offene Problemstellungen bzw. zukünftige Entwicklungen behandelt.

II. NOSQL DATENBANKEN

Obwohl die Idee einer nicht relationalen Datenbank schon seit den 70er Jahren existiert, fällt es aufgrund der Heterogenität der Systeme schwer, eine einheitliche Definition zu finden. Laut NoSQL Archiv gehört eine Datenbank zu den NoSQL Vertretern, wenn es einige der unten genannten Punkte erfüllt:

- Das zugrundeliegende Datenmodell ist nicht relational
- Die Systeme sind von Anbeginn auf eine verteilte und horizontale Skalierbarkeit ausgerichtet
- Das NoSQL System ist Open Source
- Schemafreiheit oder schwächere Schemarestriktionen
- Aufgrund der verteilten Architektur unterstützt das System eine einfache Datenreplikation
- Die Bereitstellung einer einfachen Programmierschnittstelle
- Dem System liegt meistens auch ein anderes Konsistenzmodell zugrunde (BASE statt ACID)[20]

Es zeigte sich bald die Erkenntnis, dass es immer schwerer wurde, herkömmliche relationale Datenbanken mit normaler commodity-Hardware zu skalieren. Mit dem ersten Punkt der Definition ist gemeint, dass das relationale Datenmodell nicht immer das perfekte Datenmodell sein muss. Punkt zwei beschreibt die Verteilung der Datenbank und ihre Ausrichtung auf Skalierbarkeit. Unter horizontaler Skalierbarkeit versteht man das Einfügen (bzw. Löschen) von Knoten in einem Netzwerk. Diese Knoten werden dynamisch eingebunden um einen Teil der Datenlast tragen zu können. Bei der vertikalen Skalierung werden die Rechner aufgerüstet, damit sie leistungsfähiger sind. Die Forderung nach Punkt drei, kommt von der Erkenntnis, dass in der Industrie zu oft zu viel Geld für Datenbanksysteme ausgegeben worden ist, die aber dennoch nicht ideal passen. Dieser Punkt wird zwar heiß diskutiert, ist aber nicht als eine strikte Forderung anzusehen. So wird die Open Source Bewegung als eine Art Protest betrachtet, mit der

Hintergrundidee, neue Geschäftsmodelle zu etablieren. Punkt vier ist daraus zu begründen, dass Web 2.0 Portale und Projekte deutlich agiler sein müssen als beispielsweise Bankanwendungen. Der Kern der Sache ist der, dass Schemaerweiterungen in relationalen Datenbankanwendungen eher selten problemlos verlaufen, und das darüber liegende Portal für Stunden außer Gefecht setzen können. Die Idee von NoSQL dagegen ist jene, einen Teil der Verantwortung im Umgang mit dem Schema auf die Anwendung zu übertragen. Dieses Ziel wird durch die Versionierung der Daten verfolgt. So kann die Anwendung von Anfang an erweiterte Daten (z.B. ein Feld mehr) schreiben und ein Hintergrundprozess konvertiert die Daten und legt sie als neue Version ab. Der fünfte Punkt ergibt sich als logische Konsequenz des verteilten Designs der NoSQL Anwendungen, da die Daten bei Einbindung eines neuen Knotens auf diesen verteilt werden. Es ist nicht zu widerlegen, dass SQL einer der reifsten Standards der Datenbankwelt ist, insbesondere bei einem sauberen relationalen Modell. Doch werden Tabellen und Spalten oft unüberlegt in ein bestehendes, gut ausgebautes Datenmodell angefügt. Dadurch kann die Anwendung Performance einbüßen. NoSQL Entwickler versuchen neue Wege zu gehen, und Abfragen nicht mehr derart join-intensiv (Operationen bei denen Relationen miteinander verknüpft werden) zu gestalten, wie es bisher der Fall war. Viele Programmierschnittstellen von NoSQL Systemen sind daher tatsächlich einfacher als SQL, bieten aber manchmal auch weniger mächtige Abfragemöglichkeiten an. Nicht selten müssen Anwender dadurch komplexere Aufgaben als Map/Reduce (siehe Kapitel IV.G.2) Abfragen formulieren. Der letzte Punkt betrifft das Konsistenzmodell von NoSQL Systemen. Nicht alle heutigen Websysteme benötigen die strikten Konsistenz- und Transaktionsanforderungen die von relationalen Systemen zur Verfügung gestellt werden. Das typische Beispiel sind Social Web Portale, die in der Regel keine besonders kritischen Daten halten. In diesen Systemen können die Daten auch einmal für ein kurzes Zeitfenster inkonsistent sein. Solche Systeme benötigen daher keine ACID (Atomicity, Consistency, Isolation, Durability) Garantien, denn in der Regel reichen BASE (Basically Available, Soft State, Eventually Consistent) Anforderungen aus. Es gibt durchaus NoSQL Systeme die ACID oder beide Modelle wahlweise zur Verfügung stellen. [1]

A. Einordnung in die Datenbankwelt

Die meisten Datenbanken können in zwei Lager aufgeteilt werden. Auf der einen Seite stehen die relationalen Datenbanken(MySQL, Oracle, Sybase), die vor allem in den 90er Jahren großen Aufschwung erlebten. Auf der anderen Seite stehen die NoSQL Datenbanken. Dieses Lager kann wiederum in zwei Gruppen unterteilt werden. Die Core- NoSQL und die nachgelagerten Soft-NoSQL Datenbanken. Die Kerngruppe lässt sich nach den zugrundeliegenden Datenmodellen in vier Subkategorien differenzieren. Die Key/Value Stores, Document Stores, Graphdatenbanken und die Wide Column Stores. Die nachgelagerte Gruppe unterscheidet sich von den Kernsystemen insofern, dass sie zwar keine relationale Lösung repräsentieren, aber auch nicht den ursprünglichen NoSQL Datenmodellen entsprechen. Zu dieser Gruppe gehören unter anderem Objekt- und XML Datenbanken. [1]

B. Kategorien der Kernsysteme

1) Key/Value Stores

Key/Value Datenbanken gehören zu den ältesten Datenbanken. Das einfache Datenmodell, bestehend aus Schlüssel und Wert ermöglicht eine schnelle und effiziente Datenverwaltung. Des Weiteren zeichnet sich dieses Schema durch eine einfache Skalierung aus, was im Gegensatz zu relationalen oder join- intensiven Daten und Anwendungen sehr kompliziert werden kann. Jedoch birgt dieses Modell auch Nachteile. Da die gespeicherten Daten schemafrei sind, lässt die Abfragemächtigkeit zu wünschen übrig. Komplexe Abfragen können oft nicht selbst implementiert werden, stattdessen muss man sich auf die Mächtigkeit der API verlassen. Dennoch gehört diese Kategorie zu den am schnellsten wachsenden NoSQL Systemen. Wichtige Vertreter dieser Gruppe sind Redis, Voldemort und Amazon’s SimpleDB. [1][10]

2) Document Stores

Bei Document Stores handelt es sich nicht um Dokumentdatenbanken, sondern um strukturierte Datensammlungen wie JSON, YAML oder RDF Dokumente. Eine Datei wird zusammen mit ihrer ID abgelegt. Wobei die Datenbank nur festlegt, auf welches Format die ID verweist. Document Stores verfolgen die Idee, die Schemaverantwortung von der Datenbank auf die Anwendung zu übertragen. Dies kann für manche Anwendungen erhebliche Nachteile haben, wenn beispielsweise die referenzielle Integrität gewährleistet werden muss. Aber gerade bei Web 2.0 Applikationen bringt diese Eigenschaft erhebliche Vorteile. So kann sich die Anwendung selbständig um Schemaerweiterungen oder Schemainkompatibilitäten kümmern. Abfragen werden in Document Stores effizienter verarbeitet als in Key/Value Systemen. Zu den bekanntesten Mitgliedern dieser Gruppe gehören CouchDB und MongoDB. [1][10]

3) Graphdatenbanken

Diese Systeme verwalten Graph- oder Baumstrukturen, in denen die Elemente über Kanten verknüpft sind. Da es eine Vielzahl von Graphen gibt, gibt es auch verschiedenste Graphdatenbanken. Die größte Bedeutung haben derzeit die nativen Datenbanken, welche Property Graphen abbilden. In dieser Struktur kann man die Knoten und Kanten des Graphen mit Eigenschaften und Gewichtungen versehen. Ein großer Vorteil dieser Systeme ist, dass die Relationen über Kanten sehr viel schneller traversiert werden können, als in relationalen Systemen. Ein wichtiges Anwendungsfeld in welchem Graphdatenbanken verstärkt zum Einsatz kommen, sind die Location Based Services (LBS). Bei diesen Services werden Webinformationen mit geographischen Daten verknüpft. Aber auch in anderen Bereichen kann diese Gruppe sehr sinnvoll eingesetzt werden. Ein Nachteil dieser Variante ist jedoch, dass das Clustering bei Graphdatenbanken mitunter sehr komplex werden kann. Wichtige Vertreter dieser Gruppe sind Neo4J, Infogrid und SonesDB. [1][10]

4) Wide Column Stores

Die abschließende Kategorie, die das eigentliche Thema dieser Arbeit ist, bilden die Wide Column Stores, auch Column- Family Systeme genannt. Die Datenstruktur ähnelt einer Excel Tabelle, mit dem Unterschied, dass beliebige Schlüssel auf beliebig viele Key/Value Paare – sogenannte Columns – abgebildet werden können. Diese Systeme sind speziell auf die Speicherung und die Verarbeitung sehr großer Datenmengen, die auf mehrere Rechner verteilt sind, ausgerichtet. Ein Nachteil dieser Gruppe ist jedoch, dass das Einfügen von Daten unter manchen Umständen sehr aufwändig sein kann. Zu den leistungsfähigsten Datenbanken dieser Kategorie zählen C- Store, MonetDB und FluidDB. Im Laufe dieser Arbeit wird Google’s Bigtable als Vertreter der Column-Family Systeme genauer analysiert. [1][10]

C. Theoretische Konzepte

In diesem Kapitel soll auf die theoretischen Konzepte, auf die NoSQL Datenbanken aufbauen, eingegangen werden. Ein Unterschied zu relationalen Datenbanken besteht im gewählten Konsistenzmodell. Vor dem Web 2.0 Zeitalter war das ACID (Atomicity, Consistency, Isolation, Durability) Konsistenzmodell der „heilige Gral“ der Datenbankentwickler. Doch bei verteilten Systemen spielen vor allem die Konsistenz, Verfügbarkeit und Ausfalltoleranz eine zentrale Rolle. Man versuchte die Architektur der Datenbank stets in Hinsicht auf die Konsistenz der Daten aufzubauen. Doch mit dem Einzug der verteilten Datenbanken und anderen Web 2.0 Anwendungen stiegen die Reaktionszeiten der Systeme rapide an. Diese konnten die Entwickler nur temporär mit aufwändigen „Workarounds“ beseitigen, bis die nächste Skalierungsebene erreicht war. Im Jahr 2000 konnte Erik Brewer mit dem CAP Theorem beweisen, dass man bei verteilten Datenbanken nur zwei der drei Größen gleichzeitig erreichen kann. [1]

1) CAP Theorem

- Konsistenz(Consistency): steht im Theorem dafür, dass die Daten nach Beenden einer Transaktion einen konsistenten Zustand erreichen. Bei verteilten Systemen bedeutet dies, dass alle Replikationen eines veränderten Datensatzes aktualisiert werden müssen. Dies kann bei Systemen mit vielen Clustern die Reaktionszeit enorm erhöhen.
- Verfügbarkeit(Availability): bezeichnet die akzeptable Reaktionszeit, die von System zu System variieren kann. Wenn eine Transaktion beispielsweise im E- Commerce Bereich zu lange dauert, kann dies zu Umsatzeinbußen führen.
- Ausfalltoleranz(Partition Tolerance): in Webanwendungen stehen Ausfälle eines einzelnen Knotens an der Tagesordnung. Das Ziel ist, dass bei einem Ausfall eines Knotens nicht gleich das ganze System ausfällt, sondern weiter auf Anfragen von außen reagiert werden kann.[1]

Erik Brewer konnte mit seinem Theorem beweisen, dass in einem verteilten Datenbanksystem immer nur zwei dieser drei Größen gleichzeitig erreicht werden können. Ein kurzes Szenario soll diese Aussage verständlicher machen.

Abbildung in dieser Leseprobe nicht enthalten

Figure 1. CAP-Szenario[1]

Das Beispiel beschreibt eine einfache, aus 2 Knoten K1 und K2 bestehende verteilte Datenbank. Die Knoten stellen Replikationen derselben Daten D0 dar. Der Knoten K1 ist in diesem System nur für die Schreiboperationen auf die Daten D0 zuständig, K2 liefert alle Leseoperationen.

Abbildung in dieser Leseprobe nicht enthalten

Figure 2. CAP-Szenario: Synchronisation[1]

Nachdem D0 durch eine Schreiboperation in den Zustand D1 gewechselt ist, wird K2 durch eine Nachricht des Synchronisationsmechanismus der verteilten Datenbank aktualisiert. Eine darauf folgende Leseoperation auf K2 erhält den neuen Zustand D1.

Abbildung in dieser Leseprobe nicht enthalten

Figure 3. CAP-Szenario: Verbindungsausfall[1]

Nun kann man sich vorstellen, dass die Kommunikation zwischen K1 und K2 durch einen Ausfall der Netzwerkverbindung nicht mehr möglich ist. Dann kann nach der Schreiboperation auf K1 die Aktualisierung der Daten von D0 auf D1 nicht mehr auf K2 synchronisiert werden. Sollte das System ein Protokoll verwenden, dass erst bei vollständiger Synchronisation aller Knoten eine Transaktion abschließt, werden durch diesen Ausfall Teile der Daten auf K1 blockiert, was bei Schreiboperationen schnell zu einem Einbruch der Verfügbarkeit des Systems führt. Die Verfügbarkeit kann nur dadurch gewährleistet werden, dass man akzeptiert, dass in diesem Fall die Daten auf K1 und K2 nicht mehr konsistent sind. K1 würde seine Schreiboperation ausführen, ohne zu gewährleisten, dass auf K2 der neue Zustand D1 synchronisiert wird. [1]

[...]