Grundlagen: Google® Bigtable

Grundlagen: Google® Bigtable

Google wurde 1998 gegründet und nutzt seit 2005 Bigtable für eine steigende Zahl an Diensten, wie die Indizierung von Web-Seiten für die Google Websuche über Google Earth bis hin zu Google Finance. Mit der Platzierung der Google-App-Einginge (GAE) als PaaS-Leistung am Markt stellte Google einen durch API (Application Programming Interface) gekapselten Zugang zu Bigtable bereit.

Google erschuf auf Basis vorhandener OpenSource-Technologien und unter dem Paradigma der Shared nothing Architektur eine eigene proprietäre verteilte Datenbank, die sich an vorangegangenen, vergleichbaren Datenbanken, wie IBM’s DB2 Parallel Edition & Oracles Real Applicationcluster database, orientierte.

Google-Bigtable hat sowohl Eigenschaften spaltenorientierter als objektorientierter Datenbanken. Intern werden die Daten als unabhängige, verteilte, persistente, mehrdimensionale, geordnete Karte angesehen („A Bigtable is a sparse, distributed, persistent multi-dimensional sorted map.“). Durch die GQL wird dem Entwickler ein spaltenorientierter Zugang bereitgestellt. Über die von der  Appengine bereitgestellten Klassen „Model und Expando“, wird hingegen eine objektorientierte Sicht zugänglich gemacht.

Zusammenhang zwischen Bigtable, Datastore, HRD / Master/Slave

Aus Applikationssicht ist Google Datastore das System, welches die Datenbank repräsentiert. Durch die Datastore-API ist der Zugriff auf die Megastore-Library möglich, welche Operationen auf dem verteilten System für strukturierte Daten, der Bigtable, ermöglicht. Bigtable setzt auf das Googlefilesystem (GFS) den Chubby Lockservice sowie weitere Programme auf. Der Replikationsserver verwaltet und synchronisiert die Datenmanipulationen über die verschiedenen Replikationen der Bigtable.

Chubby ist als Service in der Google-Infrastruktur die zentrale Anlaufstelle für Server, die ihren Verbund koordinieren müssen. So hält Chubby die Metadaten des Verbundes und entscheidet, wer in diesem als Master fungiert. Da die Chubby-Knoten sehr lose gekoppelt sind und jederzeit mit Fehlern und Ausfällen gerechnet wird, ist dieser Service optimiert auf Verlässlichkeit und weniger auf Performance.

Darstellung und Speicherung von Entitäten

Aus der Applikationssicht gibt es zwei Sichten in der die in Bigtable gespeicherten Daten repräsentiert werden. Zum einen besteht die Möglichkeit Klassen mit vordefinierten Attributen zu verwenden, die die Vorzüge aus der objektorientierten Programmierung, wie Vererbung bietet. Andererseits besteht die Möglichkeit freibleibende leere Objekte zu erzeugen und diese mit zur Laufzeit frei wählbaren Attributen und Werten zu füllen. Jedes Objekt bzw. jeder Eintrag stellt eine Instanz einer Entitätsklasse dar. Die Standarddatentypen: String, Text, Int, Float, Boolean sowie Null werden unterstützt. Zusätzlich sind noch Datentypen, wie geographischer Punkt, E-Mailadresse, Post-Adresse etc. zu erwähnen. Des Weiteren steht ein Datentyp zur Referenzierung auf andere Entitäten zur Verfügung. Außerdem ist es möglich jedem Attributsschlüssel mehrere Werte zuzuweisen, so dass ein Attribut eine Liste von Werten darstellen kann (auch von unterschiedlichen Datentypen).

Abbildung 3: Datenmodellierung mit Vererbung in Python

Jedes einmal gespeicherte Objekt hat neben seiner nicht änderbaren ID einen Typ, der durch die Klasse, die dieses Objekt erzeugt und gespeichert hat bestimmt wird. Anhand dieses Typs werden die gespeicherten Objekte für Zugriffe gruppiert, so dass z.B. Abfragen zum Typ „Auto“ keine Elemente des Typs „Person“ liefern. Zur internen Repräsentation werden die Daten nach Einträgen mit Attributen zerlegt und in der Bigtable gespeichert. Diese besteht aus Tupeln dessen Deskriptoren Zeilenname, Spaltenname und Zeitstempel einem Wert zugewiesen werden, siehe Abbildung 4. Jeder gespeicherte Datentyp wird in eine String-Repräsentation serialisiert.  Besteht der Wert aus einer Liste von Werten, wird für jedes Element ein eigenes Tupel von der Bigtable gespeichert. Bei Änderungen von Einträgen werden die alten Werte in der Bigtable nicht überschrieben, sondern es werden neue Tupel mit neuerem Zeitstempel eingefügt. Um die Größe der Datenbank zu begrenzen werden durch Hintergrunddienste in freikonfigurierbaren, periodischen Intervallen obsolete Tupel nach vorgegebenen Kriterien gelöscht.

Abbildung 4 Speicherung der Daten in Bigtable am Beispiel: Webseitencaching, Zeilenname ist die umgekehrte URL, Content-Spalte besitzt mehrere Versionen, t6 ist die aktuelle, Anchors werden einer beliebigen Anzahl von Spalten gespeichert.

Quelle: F. Chang, R. E. Gruber und weitere Authoren, Bigtable: A Distributed Storage System for Structured Data, Abschnitt 4.3

Abfragen und Indizes

Abfragen in der GAE werden über sog. Query-Objekte an die Bigtable übermittelt. Dazu wird ein Queryobjekt unter Angabe der zu verwendenden Klasse erzeugt. Anschließend können diesem die gewünschten Restriktionen, Filter und Sortierungsangaben hinzugefügt werden. Diese stellen eine Teilmenge im Vergleich zu anderen (relationalen) Datenbanksystemen dar. Insbesondere kann sich IN nicht auf Subqueries beziehen, sondern nur auf der Abfrage im Vorhinein übergebene Listen.

Aufgrund der Auslegung für große Datenmengen kann Bigtable nur im Voraus bekannte Abfragen durchführen, da sie nicht einzelne Datensätze scannt, sondern in Frage kommende Datensätze aus sog. Indizes extrahiert. Die Indizes sind sortierte Listen von Dokumenten, die nur eine echte Teilmenge von Schlüsseln enthalten.

Abbildung 5: Index des Level-Attributs der Spieler-Entität, absteigend sortiert

Wie die Abbildung zeigt, werden für jeden Schlüssel eines Dokuments automatisch zwei sog. Elementarindizes angelegt, die jeweils einmal in auf- und absteigender Reihenfolge sortiert sind. Anhand dieser können einfache Abfragen, wie z.B. „Gib mir alle Spieler die einen Level zwischen 12 und 10 haben“ ausgeführt werden. Bigtable sucht dabei den ersten in Frage kommenden Eintrag, sowie den ersten danach nicht mehr in Frage kommenden Eintrag und gibt alle dazwischenliegenden Einträge aus. Aufgrund dieses Verfahrens reichen die Elementarindizes nicht für alle Anfragen aus. Die Frage nach „Alle Spieler mit Level zwischen 10 und 13 und der Charakterklasse Magier“ lässt sich weder mit dem Elementarindex für Level noch dem Elementarindex für charclass beantworten. Hierfür ist ein zusätzlicher Index nötig, der die beiden Attribute verbindet und entsprechend sortiert ist.

Abbildung 6: Index des Level- und des Charackterklassen-Attributs der Spieler-Entität, aufsteigend sortiert nach Klasse und dann nach Level

Der Index aus Abbildung 6 enthält die Attribute Charackterklasse und Level und ist zuerst nach Charackterklasse und innerhalb dieser nach level sortiert. Somit kann die Bigtable zunächst zum ersten Eintrag mit Charackterklasse=Magier springen und von dort weiter springen, bis zum ersten Eintrag in dem auch das Level-Attribut die Bedingungen erfüllt. So wird auch der letzte in Frage kommende Eintrag gefunden und die Einträge dazwischen ausgegeben. Dieses Verfahren garantiert, dass alle Suchanfragen an die Datenbank in nahezu konstanter Zeit (O₍₁₎)beantwortet werden können. 

Transaktionen

Um die Integrität von Daten zu gewährleisten, unterstützt auch die Bigtable Transaktionen. Aufgrund der Fokussierung auf sehr große Projekte, wird aber nicht mit dem in RDBS üblichen Sperrverfahren, sondern mit einem sog. „optimistic concurrency control“ – Verfahren gearbeitet.  Bigtable ermöglicht durchgehende und konsistente Lesezugriffe, auch während an den zu lesenden Objekten Veränderungen vorgenommen werden. Dadurch, dass Bigtable Veränderungen an Einträge als neue Versionen eines Eintrags mit jüngerem Zeitstempel speichert, besteht für Lesezugriffe die Möglichkeit eine konsistente Sicht auf die Daten anhand des Zeitstempels des ersten Lesezugriffs zu erlangen.

Abbildung 7:  Beispiel: Umgang mit Transaktionen und Entitygroups

Quelle: Eigene Darstellung

Die Bigtable führt Buch über den Zeitpunkt des Beginns einer jeden Transaktion, sowie dem Zeitpunkt der letzten Änderung. Liest ein Client innerhalb einer Transaktion Daten aus der Bigtable, erhält dieser ausschließlich Einträge mit einem Zeitstempel „kleiner gleich“ dem Zeitpunkt des Beginns der Transaktion.
Somit ist sichergestellt, dass die Sicht auf die Daten konsistent bleibt, auch wenn in der Zwischenzeit Daten geändert werden.

Werden nun innerhalb der Transaktion Daten geändert, werden diese Änderungen gesammelt und mit Ende der Transaktion als atomische Operationen angewendet, sofern die Daten seit Beginn der Transaktion nicht verändert wurden. Falls dies geschehen ist, werden die Änderungen vollständig verworfen und der Client über den Fehlschlag seiner Transaktion informiert.

Um trotzdem mehrere Transaktionen gleichzeitig zu ermöglichen, werden die Einträge in der Bigtable zu sog. Entitygroups zusammengefasst. Die Entitygroups bilden Bereiche von zusammenhängenden Einträgen. Einträge werden beim Einfügen in die Bigtable zu genau einem frei wählbaren Bereich zugeordnet, der jedoch nachträglich nicht mehr verändert werden kann. Verschiedene Bereiche können parallel von Transaktionen verändert werden, jedoch kann sich eine Transaktion nur auf Daten eines Bereichs beziehen.

Skalierung und Replikationsmechanismen

Für die Bigtable sind zurzeit zwei Replikationsmechanismen verfügbar. Einerseits die Master/Slave Replikation, bei der ein Datacenter als Master ausgewählt wird, und sämtliche Schreibzugriffe über dieses Center abgewickelt werden. Hierbei werden die Änderungen asynchron auf andere Datacenter repliziert.  Andererseits wird der High Replication Datastore angeboten, der mittels des sog. Paxos-Algorithmus die Schreibanfragen auf verschiedene Datacenter verteilt und diese dann synchron auf andere Datacenter repliziert. Bigtable besitzt eigene Algorithmen, die eine automatische Lastanpassung (Skalierung) durchführen, daher ist kein manueller Eingriff notwendig. Die Rechenzentren von Google sind für eine automatische Kapazitätsanpassung an variierende Lasten konzipiert.

Quellen

• Chang: Bigtable: A Distributed Storage System for Structured Data 
• Mike Burrows, Google Inc. The Chubby lock service for loosely-coupled distributed systems
• http://www.google.de/intl/de/about/corporate/company/index.html
• http://code.google.com/intl/de-DE/appengine/docs/python/datastore/overview.html
• Sanderson: Programming Google Appengine 2009