Eine Studie zur Anwendung schemaloser Datenbanken in der seismologischen Forschung
Aus Winfwiki
| Hochschule und Studienort: | FOM - Hochschule für Ökonomie und Management Berlin |
| Fallstudie I | Im Rahmen des 2. Semesters zum Bachelor of Science im Studienfach Wirtschaftsinformatik |
| Titel der Arbeit: | Eine Studie zur Anwendung schemaloser Datenbanken in der seismologischen Forschung |
| Betreuer: | Professor Dr. Ralf Hötling |
| Namen der Autoren: | |
| Benjamin Bruse | |
| Stephan Fonfara | |
| Oliver Haase | |
| Guido Hagemann |
1 Abkürzungsverzeichnis
| Abkürzung | Bedeutung |
|---|---|
| AD | analog / digital |
| API | application programming interface |
| BW | BayernNetz |
| CAP | Consistency-Availability-Partition tolerence |
| cURL | Client for URLs |
| DBMS | Database Management System |
| DCL | Data Control Language |
| DDL | Data Definition Language |
| DMC | Data Management Center |
| DML | Data Manipulation Language |
| DSL | Digital Subscriber Line |
| EIDA | European Integrated Data Archive |
| FC | Fibre Channel |
| FDSN | International Federation of Digital Seismograph Networks |
| GEOFON | GeoForschungsNetz |
| GFZ | GeoForschungsZentrum |
| GMT | Greenwich Meantime |
| GR | German Regional Seismic Network |
| GSN | Global Seismographic Network |
| GUID | Global Unique Identifier |
| HTTP | Hypertext Transfer Protocol |
| IGGCAS | Institute of Geology and Geophysics, Chinese Academy of Sciences |
| IRIS | Incorporated Research Institutions for Seismology |
| ISDN | Integrated Services Digital Network |
| JDBC | Java Database Connector |
| JSON | JavaScript Object Notation |
| MPLS | Multi Protocol Label Switching |
| MS | Microsoft |
| NAS | Network Attached Storage |
| NFS | Network File System (oder Service) |
| NIC | Network Interface Card (oder Controller) |
| NoSQL | Not only SQL |
| ODBC | Object Database Connector |
| ODBMS | Objektdatenbankmanagementsystem |
| ODMG | Object Database Management Group |
| OID | Object ID |
| OQL | Object Query Language |
| ORFEUS | Observatories and Research Facilities for European Seismology |
| PC | Personal Computer |
| PHP | Hypertext Preprocessor |
| RAM | Random-Access-Memory |
| RDBMS | Relational Database Management System |
| ReNaSS | Réseau National de Surveillance Seismique |
| REST | Representational State Transfer |
| RPC | Remote Procedure Call |
| SAS | Seriel Attached SCSI |
| SCSI | Small Computer System Interface |
| SQL | Structured Query Language |
| SX | Saxon Seismic Network |
| UCS | Unicode Transformation Format |
| URL | Uniform Resource Locator |
| URI | Uniform Resource Identifier |
| USV | unterbrechungsfreie Stromversorgung |
| UTF-8 | 8-bit UCS Transformation Format |
| VEBSN | Virtual European Broadband Seismic Network |
| WAN | Wide Area Network |
| XML | Extensible Markup Language |
2 Tabellenverzeichnis
| Tabellennr. | Tabelle |
|---|---|
| 01 | Entscheidungskriterien |
| 02 | Konsistentes Hashing |
3 Abbildungsverzeichnis
| Abb.-Nr. | Abbildung |
|---|---|
| 01 | ORFEUS Stationen |
| 02 | Seismograph |
| 03 | Raumrichtungen der Seismographenstation |
| 04 | Seismogramm |
| 05 | CAP-Theorem |
| 06 | CouchDB |
| 07 | Cassandra |
| 08 | Redis |
| 09 | Die sechs JSON Basistypen |
| 10 | Notationsvorschrift eines JSON Object |
| 11 | Notationsvorschrift eines JSON Array |
| 12 | Ein Beispiel eines B-Trees |
4 Einleitung
18. April 1906, ca. 05:12 Uhr
Zahlreiche Besucher der Oper des Tenors Enrico Caruso, der am Vorabend seine Vorstellung gab, ziehen noch unbeschwert durch die Straßen. Sie lachen, singen und feiern ausgelassen. Sogar Tiere lassen sich anscheinend von der guten Laune anstecken und schließen sich kurioserweise mit ihren Lauten den Straßengängern an...
Dann bricht die Erdkruste auf einer Länge von 1.280 km entlang einer von Norden nach Süden verlaufenden Nahtzone.
Drei Tage später sind mehr als 3.000 Menschen tot und hunderttausende obdachlos. Ca. 28.000 Gebäude sind zerstört und ein Sachschaden von 400-500 Millionen US-Dollar ist entstanden, bei heutiger Wertung ca. 10 Milliarden US-Dollar.
Die Rede ist hier von einem der bekanntesten Erdbeben der Weltgeschichte und von einer der schlimmsten Naturkatastrophe in der Geschichte der USA -
dem San-Fransisco-Erdbeben.
4.1 Aktualität
Aber auch im 21. Jahrhundert bleibt die Menschheit nicht unberührt von Erdbeben und ihren Folgen.
Am 26. Dezember 2004 um 07:58 Uhr (Ortszeit West-Indonesien und Thailand) bricht das Sumatra-Andamanen-Beben aus. Der infolge des Bebens ausgelöste Tsunami erreicht in mehreren Flutwellen die Küstenregionen Südasiens und sogar Ostafrikas. Allein in Thailand gab es offiziell 5.395 Opfer, spätere Opferzahlen wurden nicht mehr hinzugezählt.
Weniger dramatisch waren hingegen die recht kleinen Erdbeben in Island seit Ostern 2009, die Vorboten des Vulkanausbruchs am 20. März 2010 sein sollten. Vom 3. bis 5. März wurden rund um den Eyjafjallajökull rund 3.000 Erdbeben gemessen.
4.2 Motivation
Das San-Fransico-Erdbeben maß auf der Richterskala eine Magnitude von 8,3; das Epizentrum lag ca. 3 km von der Stadt entfernt im Meer. Die Erdbeben rund um den Eyjafjallajökull maßen lediglich Magnituden zwischen eins und zwei und waren nur selten spürbar. Mit einer Magnitude von 9,1 und Epizentrum 85 km vor der Küste Nordwest-Sumatras ist das Sumatra-Andamanen-Beben zwar nicht das stärkste jemals gemesse Erdbeben (22. Mai 1960 Chile Magnitude von 9,5), reiht sich jedoch trotzdem in die "Top 10" ein.
Magnituden? Epizentren? Die Fragen, die sich hier in den Vordergrund drängen, sind: Wie werden diese Daten erhoben bzw. gemessen und viel wichtiger, wie werden sie gespeichert und ausgewertet? Internationale Organisationen beschäftigen sich mit Speicherung und Auswertung seismologischer Daten. Besonders hervorgetan hat sich hier IRIS-Incorporated Research Institutions for Seismology. Alle durch seismolgische Stationen gesammelten Daten werden in einer Oracle Datenbank gespeichert, dem so genannten DMC-Data Management Center, und können durch diverse Tools ausgewertet werden. Besondere Aufmerksamkeit erlangte hier wiederum das "IRIS SeismiQuery", durch das ein Anwender durch einfache SQL-Abfragen Ergebnistabellen erhalten kann.
Seit Ende der 80er Jahre wird vermehrt nach Alternativen zu relationalen Datenbanken gesucht, z.B. objektorientierten Datenbanken. Seit 2009 kommen verstärkt NoSQL-Datenbanken zum Einsatz, besonders bei sozialen Netzwerken wie StudiVZ oder Facebook. Auch Google und Amazon nutzen NoSQL. Diese Alternative scheint bewusst auf einige Vorteile moderner relationaler Datenbankensysteme zu verzichten - zu Gunsten der Performance.
Macht die "NoSQL-Bewegung" bei der Speicherung und Auswertung seismologischer Daten halt? Oder überwiegen die Vorteile einer objektorientierten Datenbank? Fest steht, dass relationale Datenbanken vielen nicht mehr ausreichen, da esProbleme mit der Verarbeitung von großen Datenmengen gibt.
5 Analyse des Ist-Zustandes
5.1 Ausgangslage
Um seismologische Daten zu erheben und auszuwerten, existieren zahlreiche nationale und internationale Organisationen von unterschiedlicher Größe. Messdaten werden selbstständig erhoben und den jeweils anderen Organisationen zur Verfügung gestellt.
5.1.1 GEOFON
GEOFON (GeoForschungsNetz) ist ein Programm des GFZ (GeoForschungsZentrum) in Potsdam. Es besteht aus einem weltweiten Netz von Seismographenstationen, welche ihre Messdaten unter anderem an das GFZ Seismological Data Archive senden. Das GFZ Seismological Data Archive dient sowohl als Archiv, als auch als Backup-Zentrum für die gemessenen GEOFON-Daten. Als Mitglied des VEBSN (Virtual European Broadband Seismic Network) dient das GFZ zusätzlich als Hauptknoten für das EIDA (European Integrated Data Archive) im Rahmen der Organisation ORFEUS (Observatories and Research Facilities for European Seismology-Sternwarten und Forschungseinrichtungen für europäische Seismologie).
5.1.2 ORFEUS
ORFEUS wurde im Jahr 1987 als gemeinnützige Organisation mit dem Ziel, die digitale Seismologie im europäischen Raum zu koordinieren und zu fördern, gegründet. ORFEUS empfängt seismolgische Daten von ca. 400 Seismographenstationen aus Europa. In Deutschland befinden sich 53 Stationen, davon 32 des GEOFON-Netzwerkes. Sämtliche Daten werden im europäischen Datenarchiv (EIDA) gesammelt, gesichert und ausgewertet. ORFEUS ist Mitglied des FDSN (International Federation of Digital Seismograph Networks), EIDA dient als regionales FDSN-Archiv.
ORFEUS betreibt 400 Stationen in Europa.
In Deutschland existieren 53 Stationen (Stand: 27.06.2010):
- GE - GEOFON - 32 Stationen
- GR - German Regional Seismic Network (Erlangen) - 16 Stationen
- BW - BayernNetz (München) - 3 Stationen
- SX - Saxon Seismic Network (Leipzig) - 2 Stationen
5.1.3 FDSN
Die globale Organisation FDSN-International Federation of Digital Seismograph Networks (Internationale Föderation von digitalen Seismographen-Netzwerken) besteht aus Gruppen, die für die Installation und Wartung von Seismographen innerhalb ihrer geografischen Grenzen oder global verantwortlich sind. Voraussetzung für die Mitgliedschaft ist das Bedienen von mindestens einer Breitbandstation, die Mitgliedschaft ist generell für jede Organisation offen, die diese Voraussetzung erfüllt. Mitglieder des FDSN stellen ihre Daten frei und offen zur Verfügung. Dies bedeutet eine Förderung der Erdwissenschaft, im Speziellen die Studie seismischer Tätigkeiten - regional und global.
Die Mitgliedschaft des FDSN ist global und kostenfrei. Das FDSN wird nicht durch ein Land oder eine bestimmte Gruppe dominiert. Während die Mehrheit der Mitglieder innerhalb ihrer nationalen Grenzen operiert, operieren einige Mitglieder auch außerhalb ihrer Grenzen.
Die durch die Stationen der FDSN-Mitglieder erzeugten Daten werden im IRIS Data Management Center gespeichert und verwaltet.
Liste von ausgewählten FDSN-Mitgliedern:
- Europa = ORFEUS (Observatories and Research Facilities for European Seismology)
- Frankreich = ReNaSS (Réseau National de Surveillance Seismique)
- Deutschland = GEOFON, GeoForschungsZentrum Potsdam (GFZ)
- USA = GSN (Global Seismographic Network), IRIS
- China = IGGCAS (Institute of Geology and Geophysics, Chinese Academy of Sciences)
- Island = Iceland National Network
5.2 Problemskizzierung und Zielidentifikation
Die bei seismologischen Messungen anfallenden Daten müssen gespeichert, gesammelt und analysiert werden.
Bisher nutzen seismologische Forschungszentren klassische relationale Datenbanken, um diese Aufgabe zu bewältigen. Im Rahmen dieser Fallstudie wird der Frage nachgegangen, ob relationale Datenbanken die optimale Wahl für das im Verlauf dargestellte Anforderungsprofil sind und welche möglichen Alternativen sinnhaft erscheinen.
Die Datenmengen werden im Gigybyte oder Terrabytebereich liegen und die Speicherkapazitäten müssen darauf ausgelegt sein. Die Daten werden aus verschiedenen Quellen bereitgestellt und das System wird an verschiedenen geographischen Standorten betrieben. Es muss daher als verteiltes System funktionieren.
Eine zentrale Auswertung der Daten und die Bereitstellung der Ergebnisse über eine Webseite ist bereitzustellen.
Es ist grundsätzlich anzumerken, dass die Fallstudie aus dem Blickwinkel der Backend Datenbank erarbeitet wird. Das bedeutet, dass alle technischen und fachlichen Anforderungen nur in so weit betrachtet werden, wie sie eine Relevanz zur Datenbanknutzung haben.
6 Exkurs: Funktionsweise eines Seismographen
6.1 Allgemeine Funktionsweise
Ein Seismograph zeichnet Bodenbewegungen auf, die durch Erdbeben verursacht werden. Das Abbild der aufgezeichneten Bodenbewegungen nennt man Seismogramm. Voraussetzung hierfür ist die Simulation eines "Archimedischen Punktes" (Punkt in absoluter Ruhe) durch ein Pendel, dessen Aufhängung an dem sich bewegenden Boden befestigt ist.
6.2 Funktionsweise moderner Seismographen
Moderne Seimographen arbeiten mit einer kontaktfreien Registrierung auf elektromagnetischem Weg, dies geschieht unter Ausnutzung des Dynamo-Prinzips. Durch die Anbringung einer Spule an der Pendelstange, die in einen Magneten eintaucht, entsteht Induktion, die induzierte Spannung ist proportional zur Geschwindigkeit des Pendels. Das entstehende Seismogramm beinhaltet auf der x-Achse die Zeit t in Sekunden s, auf der y-Achse die Bodenschwingung, bzw. die Amplitude des Pendels, gefiltert und verstärkt in V oder mV (Spannung).
Spätere Berechnungen und Bestimmungen, z.B. Herdentfernung, werden mit Hilfe des Seismogramms durchgeführt.
Eine vollständige Seismographenstation erfasst in allen drei Raumrichtungen (NS, OW und Up-Down durch UD-Seismograph).
7 Anforderungsprofil
7.1 Fachlich
Die fachliche Zielstellung ist die Bereitstellung von seismographischen Daten für die wissenschaftliche Forschung und Arbeit. Das Ziel dieses Systems ist kein Frühwarnsystem, wie es beispielsweise von Japan schon im produktiven Einsatz betrieben wird. Echtzeitsysteme und -auswertungen werden in dieser Fallstudie nicht betrachtet.
Es existieren drei fachliche Ebenen:
- die lokale Ebene der Datenerfassung
- die regionale Ebene der Datenanalyse und
- die globale Ebene der Datenarchivierung
Für diese drei Ebenen werden im Folgenden die fachlichen Anforderungen dargestellt.
7.1.1 Lokale Ebene der Datenerfassung
Seismolgische Daten (festlegbare oder messbar):
- Name der Station
- Name des Ortes (Ortscode - drei Buchstaben)
- Region
- Elevation (Höhe über dem Meerespiegel)
- Messdaten des Seismographen pro Sekunde
- Zeit
- Bei allen Stationen wird GMT (Greenwich Meantime) genutzt.
- Geographische Breite (Breitengrad / Latitude)
- Dezimalgrad, z.B. Berlin: 52.52341°N(orth), 13.41140°E
- Geographische Länge (Längengrad / Longitude)
- Dezimalgrad, z.B. Jamaika: 18.10958°N, -77.2975°E(ast)
Beispiel für eine Station: Code: FUR Latitude: 48.16550 Longitude: 11.27633 Elevation: 565.0 Name: Furstenfeldbruck Region: Bayern,Germany
7.1.2 Regionale Ebene der Datenanalyse
Ableiten weiterer Daten aus der Funktionsweise eines Seismographen:
In der regionalen Ebene werden die Daten der lokalen Stationen erfasst und ausgewertet. Errechnet werden Herdentfernung, Herdzeit, Magnitude und die Lokalisation des Herdes. Die Daten einer Region können nach definierten Suchanfragen analysiert bzw. zusammengefasst werden und sind per Website zugänglich.
- Herdentfernung
Die Berechnung erfolgt aus der Differenz der Zeitspanne zwischen Primärwelle und Sekundärwelle mit Hilfe eines empirischen Laufzeit-Diagramms, in Kilometer oder Winkelgrad.
- Herdzeit
Berechnung ebenfalls mit Hilfe des Laufzeit-Diagramms, Differenz der Ankunft der P(rimär)-Welle und Laufzeit der P-Welle.
- Magnitude
Die Magnitude bezeichnet die Stärke des Erdbebens. Der Wert liegt auf der Richter-Skala (benannt nach Charles Richter) und ist logarithmisch, das bedeutet z.B., dass 7 10-mal stärker als 6 ist. Die Bestimmung erfolgt mit Hilfe der Oberflächenwelle mit der größten Amplitude - Ms (s=surface).
- Lokalisation des Herdes (Epizentrum)
Das Epizentrum wird mit Hilfe des Seismogramms ermittelt und wird mit geographischer Länge und Breite gekennzeichnet.
- Daten der Messstationen 24/7
Die regionalen Datacenter erhalten rund um die Uhr Daten aus der lokalen Ebene - 24 Stunden am Tag, 7 Tage die Woche.
7.1.3 Globale Ebene der Datenaggregation und -speicherung
In der globalen Ebene werden die Daten der regionalen Ebene für die Langzeitarchivierung gespeichert. Die Daten stehen hier zur Analyse zur Verfügung und sind per Webzugriff abrufbar.
7.2 IT-Anforderungen, abgeleitet aus den fachlichen Anforderungen
7.2.1 Lokale Ebene
Am Tag fallen mindestens 346MB bzw. 10GB pro Monat an Daten pro Station an.
Berechnungsgrundlage: 4kb/s x 60 sek x 60 min x 24 stunden = 346MB = 10GB/monat (86400 Sekunden/Revisions ID)
- Daten
- Name der Station
- Organisation, der die Station angehört
- GUID
- Latitude
- Longitude
- Elevation
- Zeit
- Datum
- Magnitude
- Herdentfernung
- Herdzeit
Es muss eine Möglichkeit der Speicherung der Messdaten geben. Es wird daher eine Datenbank verwendet.
Um die Daten eines Tages zuverlässig und störungsfrei identifizieren zu können und Inkonsistenzen zu vermeiden, muss ein GUID (Global Unique Identifier) verwendet werden. Es wird ein Verfahren zur GUID-Erstellung entwickelt, dass jeden dieser Schlüssel unverwechselbar gestaltet.
Um Datenverluste durch Stromausfall zu überbrücken und um mögliche Schäden an Hard- und Software durch unkontrolliertes Herunterfahren des Messknotens zu vermeiden, wird in allen Messstationen durchgängig mit USV (unterbrechungsfreie Stromversorgung) gearbeitet.
Zusätzlich wird ein AD-Wandler benötigt, der die Messströme des Seismographen in digital verarbeitbare Daten transferiert. Dieser ist in den Seismographen integriert.
Um die Messdaten aus der Messstation, also der Ebene der lokalen Datenerhebung in die regionalen Datacenter der Datenanalyse zu transferieren, wird ein Netzwerk benötigt.
7.2.2 Regionale Ebene
Aus den (aus der lokalen Ebene) erhaltenen Daten werden in der regionalen Ebene die Herdzeit, Herdentfernung und die Magnitude ermittelt.
Die Daten werden in den regionalen Knoten gesammelt, die sich untereinander mittels Replikation synchronisieren.
Für die Analyse der Daten in einem regionalen Datacenter ist es nicht notwendig, dass alle Daten aller andereren regionalen Datacenter vorliegen. Daraus folgt, dass die Konsistenz der Daten nicht oberste Prämisse ist und zeitlich verzögert erfolgen kann.
Wiederum wichtig ist, dass bei Ausfällen der Synchronisation die einzelnen Datacenter autonom weiterarbeiten können. Dies wird mit dem Terminus "Partition tolerence" umschrieben.
7.2.3 Globale Ebene
Alle Daten der regionalen Zentren werden letztendlich in ein globales Datacenter übertragen. Das Ziel der zentralen Datenhaltung im globalen Datacenter ist die Archivierung und die Möglichkeit der zentralen Auswertung für wissenschaftliche Studien.
Auch hier ist die Konsistenz der Daten nicht oberstes Ziel, von daher gibt es nie eine vollständige Konsistenz aller Daten. Alle Daten werden nach einem Quartal in eine Archivdatenbank ausgelagert und aus Redundanz- und Partitionierungsgründen über ein Server Cluster zur Verfügung gestellt. Auch hier kann auf die Daten via Webbrowser zugegriffen werden.
7.3 Wirtschaftliche Anforderungen
Die wirtschaflichen Anforderungen werden im Rahmen dieser Fallstudie nicht betrachtet.
8 Lösungsdiskussion
8.1 Vergleich der Datenbank-Paradigmen
In dieser Fallstudie werden drei verschiedene Arten von Datenbanken beschrieben und verglichen. Anhand von Vor- und Nachteilen der Datenbanktypen wird die richtige Datenbank herausgefiltert, mit der das Projekt realisiert werden kann.
8.1.1 Darstellung Datenbank Paradigmen
- Relationale Datenbanken (SQL)
Relationale Datenbanken wurden erstmals 1970 von Edgar F. Codd vorgeschlagen.
Die Daten werden dabei in Form von zweidimensionalen Tabellen verwaltet, welche über Primär- und Fremdschlüssel miteinander verknüpft werden.
Ein Großteil der eingesetzten Datenbanken sind relationale Datenbanken.
Als Abkürzung wird RDBMS genutzt (Relational Database Management System).
SQL (Structured Query Language) ist die am häufigsten anzutreffende und und in großen Teilen standardisierte Abfragesprache. Teilweise standardisiert deshalb, da jeder Hersteller noch eigene Eigenheiten mit in die Sprache einbaut. Beispiele hierfür sind z.B. T-SQL (Transact SQL) bei MS SQL oder SQLPLUS bei Oracle.
Im allgemeinen Sprachgebrauch ist auch oft von SQL-Datenbanken die Rede, obwohl SQL lediglich die Abfragesprache ist.
SQL-Abfragen lassen sich in drei Bereiche unterteilen:
- (DML) Data Manipulation Language --> Befehle zur Datenmanipulation (Ändern, Einfügen, Löschen)
- (DDL) Data Definition Language --> Befehle zur Definition des Datenbankschemas
- (DCL) Data Control Language --> Befehle für die Rechteverwaltung und Transaktionskontrolle.
Zur Modellierung von RDBMS wird meist das Entity-Relationship-Modell oder ähnliche Varianten verwendet. Genutzt wird dies, um das konzeptionelle Schema zu designen. Es ist somit der erste Schritt, das Schema zu erstellen.
Das Vorgehen zur Nutzung relationaler Datenbanken wurde 1970 vom Edgar F. Codd in den sogenannten 12 Regeln codifiziert:
- Regel 1: Darstellung von Informationen
Alle Informationen in einer relationalen Datenbank (einschließlich Namen von Tabellen und Spalten) sind explizit als Werte in Tabellen darzustellen.
- Regel 2: Zugriff auf Daten
Jeder Wert einer relationalen Datenbank muss durch eine Kombination von Tabellenname, Primärschlüssel und Spaltenname auffindbar sein.
- Regel 3: Systematische Behandlung von Nullwerten
Das DBMS behandelt Nullwerte durchgängig gleich als unbekannte oder fehlende Daten und unterscheidet diese von Standardwerten.
- Regel 4: Struktur einer Datenbank
Die Datenbank und ihre Inhalte werden in einem sogenannten Systemkatalog auf derselben logischen Ebene wie die Daten selbst - also in Tabellen - beschrieben. Demzufolge lässt sich der Katalog mit Hilfe der Datenbanksprache abfragen.
- Regel 5: Abfragesprache
Zu einem relationalen System gehört mindestens eine Abfragesprache mit einem vollständigen Befehlssatz für Datendefinition, Manipulation, Integritätsregeln, Autorisierung und Transaktionen.
- Regel 6: Aktualisieren von Sichten
Alle Sichten, die theoretisch aktualisiert werden können, lassen sich auch vom System aktualisieren.
- Regel 7: Abfragen und Bearbeiten ganzer Tabellen
Das DBMS unterstützt nicht nur Abfragen, sondern auch die Operationen für Einfügen, Aktualisieren und Löschen in Form ganzer Tabellen.
- Regel 8: Physikalische Datenunabhängigkeit
Der logische Zugriff auf die Daten durch Anwendungen und Ad-Hoc-Programme muss unabhängig von den physikalischen Zugriffsmethoden oder den Speicherstrukturen der Daten sein.
- Regel 9: Logische Datenunabhängigkeit
Änderungen der Tabellenstrukturen dürfen keinen Einfluss auf die Logik der Anwendungen und Ad-Hoc-Programme haben.
- Regel 10: Unabhängigkeit der Integrität
Integritätsregeln müssen sich in der Datenbanksprache definieren lassen. Die Regeln müssen im Systemkatalog gespeichert werden. Es darf nicht möglich sein, die Regeln zu umgehen.
- Regel 11: Verteilungsunabhängigkeit
Der logische Zugriff auf die Daten durch Anwendungen und Ad-Hoc-Programme darf sich beim Übergang von einer nicht-verteilten zu einer verteilten Datenbank nicht ändern.
- Regel 12: Kein Unterlaufen der Abfragesprache
Integritätsregeln, die über die Datenbanksprache definiert sind, dürfen sich nicht mit Hilfe von Low-Level-Sprachen umgehen lassen.
Zusätzlich hat Codd noch die Regel 0 definiert, wonach jeder Zugriff nur durch relationale Fähigkeiten stattfinden darf.
- Objektorientierte Datenbanken
Objektdatenbanken wurden Ende der 80er Jahre entwickelt und gehören daher zu den neuen Datenbankkonzepten. Bis heute sind sie auf dem Datenbankmarkt nicht sehr weit verbreitet. Die Objektdatenbanken sind sehr stark an die relationalen Datenbanken angelehnt.
In objektorientierten Datenbanken werden Daten als Objekte gespeichert. Zur Verwaltung der Datenbank wird ODBMS (Objektdatenbankmanagementsystem) verwendet. Um Abfragen auf die Datenbank zu machen, wurde eine einheitliche Sprache OQL beschlossen, welche stark an SQL angelehnt ist. OQL wurde von der Object Database Management Group (ODMG) ins Leben gerufen. Die ODMG ist ein Verbund von Herstellern objektorientierter Datenbanksysteme.
In der Objektdatenbank werden keine künstlichen Schlüssel verwendet. Es werden sogenannte OIDs verwendet, mit denen man auf die Objekte zugreifen kann, die vollautomatisch vom System vergeben werden. Zu den Vorteilen der Datenbank gehört, dass objektorientierte Programme direkt mit der Datenbank kommunizieren können und keine komplizierten Abfragen mittels Joins notwendig sind, um Daten mehrerer Tabellen zu erhalten.
Die problematisch erscheinenden Punkte sind die geringere Verbreitung des Datenbanksystems, keine Vorbereitung für Schnittstellen bzw. Tools wie JDBC/ODBC und Performanceprobleme, verursacht durch Zugriffspfade zu Objekten über mehrere Pfade.
Am einfachen Beispiel illustriert (Suche alle Messstationen, die nicht zugleich auch Regionalzentrum sind):
SELECT messstation.name
FROM messstaton in StationTUM
WHERE not (messstation.name in SELECT regionalzentrum.name FROM regionalzentrum in TAs)
- NoSQL
Mit der Bezeichnung "NoSQL" ist nicht "kein SQL" gemeint, sondern "Not only SQL". Die aktuellen NoSQL Datenbanken verzichten auf ein vordifiniertes Datenbankschema, was die Flexibilität ihrer Nutzungsmöglichkeiten erhöht. Vertreter von NoSQL-Datenbanken sind auf hohe Verteilbarkeit ausgelegt, so dass die Daten leicht in einem Cluster vorgehalten werden können. Die NoSQL-Datenbanken sind speziell für Web2.0-Applikationen und viele gleichzeitige Zugriffe entwickelt worden.
Anhand des CAP-Theorems und den Anforderungen, Availability und Partition tolerence werden die drei Datenbanktypen verglichen, um die passende Datenbank zu finden. Klärung
Availability: Die Daten müssen auf jeder Ebene verarbeitet und gespeichert werden können.
Partition tolerence: Die Datenverarbeitung muss bei Ausfall einer Ebene gewährleistet sein.
- Relationale Datenbanken
+ Skalierbarkeit durch Replikation
+ hohe Datenmengen
- Replikation (Master/Slave Problem)
- Leistungsprobleme bei datenintensiven Applikationen
- Abfragen werden immer neu abgefragt
- schlechte Anbindung an das Web
- Objektorientierte Datenbanken
+ gute Anbindung an das Web
- wenig verbreitet
- wenig Tools und Schnittstellen
- doppelte Datenhaltung
- Leistungsprobleme durch Zugriffspfade
- Skalierbarkeit nur möglich mit zusätzlicher Software
- Abfragen werden immer neu abgefragt
- NoSQL
+ Skalierbarkeit durch mitgelieferten Proxy
+ Speicherung der Abfragen
+ hohe Datenmengen
+ viele gleichzeitige Zugriffe
+ gute Anbindung an das Web
8.1.2 Der zentrale Anforderungshebel
CAP Theorem Das CAP Theorem besagt, dass in verteilten Systemen nur zwei von drei Zielen gleichzeitig erreicht werden können.
- Consistency (Konsistenz) - Alle Knoten sehen zur selben Zeit die selben Daten
Consistency beschreibt, wie ein Datenbanksystem nach einer Operation in einen konsistenten Zustand gebracht wird. In verteilten Datenbanksystemen bedeutet dies, dass sobald ein Schreibzugriff durchgeführt wird, alle Anderen lesenden Zugriff erhalten. Ein verteiltes Datenbanksystem hat entweder eine stark konsistente oder eine Form der schwachen Konsistenz.
Das bekannteste Beispiel starker Konsistenz in Datenbanken ist ACID (Atomicity Consistency Isolation Durability), welches in den meisten relationalen Datenbanken (SQL) verwendet wird. Auf der anderen Seite steht BASE (Basically Available Soft-State Eventual consistency). Diese Methode kommt in NoSQL-Datenbanken im Einsatz. Schwach konsistente Systeme replizieren ihre Daten über Datenreplikationsmechanismen. Die neueste Version befindet sich auf einem Knoten im Cluster, allerdings befinden sich zur gleichen Zeit die älteren Versionen noch auf den anderen Knoten des Cluster bis zu einem gegebenen Zeitpunkt alle Daten wieder über alle Knoten konsistent sind.
- Availability (Verfügbarkeit) - Knotenausfälle hindern nicht andere Knoten daran, weiter zu funktionieren
Die Verfügbarkeit eine Systems ist definiert als die Fähigkeit eines Systems, trotz Ausfall einer seiner Komponenten mit einer hohen Wahrscheinlichkeit einen ununterbrochenen Betrieb zu gewährleisten. Bei Auftreten eines Fehlers bei einem Knoten muss das System fehlertolerant sein und ein Ausfall eines Knotens darf nicht zum Ausfall des ganzem Systems führen.
- Partition tolerence (Partitions Toleranz) - Das System arbeitet trotz willkürlicher Verluste von Nachrichten weiter
Eine Datenbank kann über mehrere Server an verschiedenen Standorten verteilt sein. Bei physikalischer Trennung der Datenbank funktionieren die Subsysteme autonom weiter. Nach der Wiederherstellung der System-Integrität, wird die Daten-Konsistenz automatisch wiederherstellt.
Ein Beispiel aus der Praxis für CAP-Theorem:
- Im November 2006 veröffentlichte Google ein Papier mit dem Namen BigTable. Ein verteiltes Speichersystem für strukturierte Daten beschreibt eine verteilte, spaltenorientierte Datenbank, welche das Google-Filesystem benutzt.
- Im Oktober 2007 veröffentlichte Amazon ein Papier mit dem Namen Dynamo. Hierin wird Amazons hochverfügbarer Shop als weltweit verteilte Datenbank beschrieben.
Was diese zwei zu einem guten Beispiel macht ist, dass sie moderne Designs und Implementierungen der verteilten gemeinsam genutzten Datensysteme mit zwei verschiedenen Philosophien bezüglich CAP umsetzen. BigTable ist ein CA-System, es ist stark konsistent und hochverfügbar, kann aber unter Netzwerk-Partitionierung nicht verfügbar sein. BigTable hat des Weiteren keine Replikation auf Datenbankebene. Die Replikation erfolgt unterhalb von GFS (Google File System). Dynamo ist ein AP-System, es ist hochgradig verfügbar, auch unter Netzwerk-Partitionen und ist dadurch immer irgendwann konsistent.
Das Backend der NoSQL-Datenbank für die Speicherung der seimsologischen Daten erfordert ein verteiltes Datenbanksystem (lokale Ebene repliziert Richtung regionaler Ebene, die wiederum Richtung globaler Ebene repliziert).
Eine hohe Verfügbarkeit der Datenbankknoten ist Grundvoraussetzung für das Funktionieren des Gesamtsystems. Die lokalen Datenbanken der Messstationen erhalten kontinuierlich Daten der seismologischen Stationen und müssen daher rund um die Uhr zur Verfügung stehen, um Datenverluste zu vermeiden.
Die Nichterreichbarkeit einzelner Knoten darf das Gesamtsystem nicht beeinträchtigen. Ein Szenario hierfür ist z.B. der Ausfall des Netzwerkes zwischen einzelnen regionalen Datacenter, der dazu führt, dass ein Datacenter isoliert ist. In diesem Fall kann das isolierte Datacenter mit den bereits vorhandenen Daten weiter arbeiten, während die restlichen Datacenter weiterhin Daten replizieren und verarbeiten können. Die Synchronisation wird automatisch wieder aufgenommen, sobald das Netzwerk wieder verfügbar ist.
Aufgrund dieser Anforderungen wird ein verteiltes Datenbanksystem gesucht, das eine hohe Verfügbarkeit und eine hohe Partitionstoleranz aufweist. Eine starke Konsistenz ist nicht erforderlich, da zur Verarbeitung in den regionalen Datacentern primär die Daten der eigenen Messstationen wichtig sind und diese nur eine Teilmenge aller Messdaten zu jedem Zeitpunkt darstellen.
8.1.3 Ergebnis der Betrachtung
Durch Betrachtung des CAP-Theorems schließen sich die relationale und objektorientierten Datenbanken aus, wenn die Anforderung Skalierbarkeit, Verarbeitung hoher Datenmengen und gleichzeitige Zugriffe dazu genommen werden.
| Entscheidungskriterien/Datenbanksysteme | relationale Datenbank | objektorientierte Datenbank | NoSQL |
| Consistency | ja | ja | ja, überwiegend schwach |
| Availability | ja | nein | ja |
| Partition tolerence | nein | ja | ja |
| Skalierbarkeit | ja, durch Replikation | nein, nur mit zusätzlicher Software | ja, durch Proxies |
| Verarbeitung hoher Datenmengen | ja | ja | ja, Proxies erhöhen die Speicherkapazität |
| gleichzeitige schreibende Zugriffe | nein, nur bei kleinen Transaktionen | nein, durch Zugriffspfade | ja, auf Web 2.0 ausgelegt |
T01 Entscheidungskriterien
8.2 NoSQL Datenbanken
Unter dem Oberbegriff "NoSQL"-Datenbanken ist eine Vielzahl von Datenbanksystemen zusammengefasst, die sich vor allem durch ihre unterschiedliche Funktionsweise unterscheiden, bzw. dem Konzept, an dem sich das Datenbanksystem orientiert. Allen gemeinsam ist, dass kein festes Schema konzipiert werden muss, die gespeicherten Daten sind nicht formal strukturiert. Drei Funktionsweisen bzw. Konzepte mit Beispielen sollen im Anschluss näher erläutert werden.
8.2.1 Dokumentorientierte Datenbanken
CouchDB
Dokumentenorientierte Datenbanken speichern beliebig lange "Texte" mit unstrukturierten Informationen. Auf Basis der Dokumenteinhalte ist eine Suche möglich. Die Besonderheit hier ist, dass die abgespeicherten Dokumente nicht alle die gleichen Felder enthalten müssen. Ein bekannter Vertreter der dokumentenorientierten Datenbanken ist "CouchDB". CouchDB funktioniert nach dem oben genannten Verfahren. Views (Abfragen) erzeugen einen Index und können eine (Map)Reduce-Funktion enthalten. Die Views werden selbst ebenfalls als Dokumente in der Datenbank abgelegt, welches wiederum eine Reaktivierung und Aktualisierung ermöglicht und die Serverlast reduziert. CouchDB ist weiterhin ein verteiltes Datenbanksystem mit einem effizienten Replikationsmechanismus, der auch mit Systemen funktioniert, die nicht immer online sind (CAP). Der englische Radio-und Fernsehsender BBC benutzt z.B. CouchDB als interne Datenablage. Die Programmierschnittstelle (API-application programming interface), die von CouchDB genutzt wird, ist "REST".
Ein weiteres Beispiel für dokumentenorientierte Datenbanken ist "MongoDB".
8.2.2 Spaltenorientierte Datenbanken
Cassandra
Im Gegensatz zu herkömmlichen SQL-Datenbanken, orientieren sich spaltenorientierte Datenbanken nicht an den Zeilen, sondern - wie der Name schon vermuten lässt - an den Spalten. Ein Datensatz ist somit keine Zeile, sondern eine Spalte in der Datenbank. Dieses Konzept ermöglicht eine schnellere Analyse der Daten.So funktionier z.B. einZusammenrechnen von Verkaufszahlen pro Mitarbeiter wesentlich schneller bei geringerer Serverlast im Vergleich zu relationalen SQL-Datenbanken. Das anfänglich für Facebook entwickelte "Cassandra" ist ein hybrides Datenbanksystem, das spaltenorientiert arbeitet und das Key-Value-Prinzip nutzt. Von Apache weiterentwickelt zu einer dezentralisierten und letztendlich konsistenten (eventuel consistency CAP) verteilten Datenbank, wird Cassandra mittlerweile bei weiteren sozialen Netzwerken wie z.B. Twitter eingesetzt. Die von Cassandra genutzte API ist "many Thrift". Ein weiteres Besipiel für eine spaltenorientierte Datenbank ist "Hadoop".
8.2.3 Key Value basierte Datenbanken
Redis
In Key Value Datenbanken verweist ein bestimmter Schlüssel auf einen Wert, der eine einfache Zeichenkette sein kann. Key Value-Datenbanken teilen sich in In-Memory-Versionen und in On-Disk-Versionen. Die In-Memory-Variante sorgt für eine hohe Performance, da sie die Daten im (RAM-)Speicher behält. Die On-Disk-Variante speichert direkt auf die Festplatte. "Redis" ist eine Beispiel für die On-Disk-Variante. Zusätzlich zu Strings, kann Redis auch Listen, Sets und sortierte Sets speichern. Redis hält die Daten solange im Speicher vor, bis bestimmte Bedingungen für das Speichern auf die Festplatte erfüllt sind. Die Besonderheit bei Redis ist, dass mehrere APIs für viele Programmiersprachen existieren, z.B. PHP oder Java. Ein anderes Beispiel für Key Value Datenbanken ist "Amazon Simple DB".
8.3 Auswahl eines NoSQL-Datenbanksystems
Die beschriebenen NoSQL-Datenbanken verfolgen unterschiedliche konzeptionelle Ansätze. Es ist mit allen drei Konzepten grundsätzlich möglich die definierten fachlichen Anforderungen umzusetzen.
8.3.1 Redis vs. Cassandra vs. CouchDB
Eine hohe Performance und Skalierbarkeit ist charakteristisch für alle drei Vertreter der unterschiedlichen NoSQL-Datenbanksysteme. Es werden unterschiedliche technologische Ansätze für Speicherung, Bearbeitung und Präsentation der Daten verwendet, die trotz ihrer Diversität effektiv im Rahmen dieser Fallstudie eingesetzt werden können.
Die Replikationsmöglichkeiten und -techniken geben bei genauer Betrachtung der IT-Anforderungen den Ausschlag. Die Möglichkeit einer asynchronen Replikation der seismolgischen Daten über drei Ebenen ist das K.O.-Kriterium.
Redis
- Master-Slave-Replikation
Cassandra
- symmeterische Replikation, Point to Point
CouchDB
- asymmetrische Replikation, Master-Master
8.3.2 Ergebnis der Betrachtung
Von den drei betrachteten NoSQL-Datenbanksystemen ist einzig CouchDB in der Lage durch Verwendung der Master-Master-Replikation, Datenbestände von einer Ebene in die nächst höhere Ebene in asymetrischem Verfahren zu replizieren.
Redis, sowie Cassandra, sind konzeptionell in der Lage in einer Ebene zu replizieren, die ebenenübergreifende Replikation per Push-Verfahren ist nicht implementiert.
Die für diesen Einsatzzweck vorteilhaften Eigenschaften von CouchDB werden hier stichpunktartig aufgeführt und es wird an geeigneten Stellen in der Umsetzungsbeschreibung detaillierter auf sie eingegangen.
- verteiltes System
- 8 Trugschlüsse verteilter Systeme
- Local Data ist King - Latency Verringerung
- eventual consistency --> CouchDB setzt Availability vor absoluter Konsistenz (RDBMS machen das anders herum)
- Architektur ist für Replikation entworfen
- Eindeutige IDs für Dokument (UUID mit 128 Bit)
- Revisionsverwaltung (32Bit- Revisions Id)
- Fehlertolerant
- Akzeptiert mehrere Realitäten → Lokale Konsistenz
- Multi-Version Concurrency Control (MVCC)
- Statt überschreiben → Neues Dokument (neue Blöcke auf der Festplatte)**Lesezugriff trotzdem möglich (alte Version)
- Von Last unabhängig
- Revisionsverwaltung
- sehr hohe Performance
- Views aktualisieren nur geänderte und neue Daten - Rest bleibt gleich
- Views werden auch als B-Trees gespeichert
- Lookups by key, or key range, are extremely efficient operations with a B-tree,described in big O notation as O(log N) and O(log N + K), respectively
- daher Performance gelich hoch - egal wie viele Datensätze
- kann große Datenmengen verarbeiten
- einfache Replikation mit Checkpoints, die bei abgebrochener Replikation nur noch den Rest übertragen
- Continous Replication: automatische Synchronisierung von DBs zu optimalem Zeitpunkt, wenn Verbindung vorhanden.
- Integration von Lucene Suchmaschine für Volltextsuche http://github.com/rnewson/couchdb-lucene
9 Umsetzung
9.1 Darstellung von CouchDB
Vor der Darstellung der Umsetzung der Ebenen, die durch die Fach- und IT-Anforderungen definiert wurden, erfolgt im Folgenden eine Darstellung der in CouchDB verwendeten Technologien und Ansätze.
9.1.1 RESTful Services - REST HTTP API
REST ist ein Akronym für Representational State Transfer und wurde im Jahre 2000 von Roy Fielding im Rahmen einer Dissertation eingeführt. REST beschreibt eine Softwarearchitektur für verteilte Informationssysteme, die mit Hilfe von Hypertext Transfer Protokoll und Uniform Resource Identifier beschrieben wird.
REST wird als einfache Schnittstelle zur Kommunikation mit einer CouchDB-Instanz verwendet.
Jede Ressource, wie eine Datenbank oder Datenbankdokument, ist durch einen definierten URI adressierbar und kann mit Hilfe von vier einfachen Webservices auf Basis von HTTP angesprochen werden.
Vier Webservices von CouchDB
- GET: Daten von DB abfragen
- PUT: Daten aktualisieren oder neu in DB schreiben
- DELETE: Daten in DB löschen
- COPY: kopiert Dokumente in DB
Client/Server Architektur
Ein Vorteil der Nutzung von RESTful services oder REST HTTP API zur Datenmanipulation ist dadurch gegeben, dass keine speziellen Client zur Kommunikation notwendig ist. Jedes System, das in der Lage ist, HTTP Request zu verarbeiten, ist ebenfalls in der Lage mit einer CouchDB per REST HTTP API zu kommunizieren.
Zur Veranschaulichung der vier CouchDB Webservices werden im folgenden Video Daten in einer CouchDB mit dem Kommandozeilenprogramm cURL, welches ohne Browserzugriff HTTP Requests verschicken kann, verarbeitet.
9.1.2 JSON
Javascript Objekt Notation ist ein offenes, textbasiertes Datenaustauschformat, das gut für Menschen und Maschinen lesbar ist.
JSON ist im Prinzp eine Sammlung von Schlüssel/Wert-Paaren in einem Objekt, welche nach definierten Regeln erstellt werden.
Es existieren 6 Basistypen in JSON
- String - wird in "" angegeben
- Number - Int und floatingPoint
- Boolean (true und false)
- Null
- Object
- Array
Arrays und Objekte können wiederum neben den anderen Basistypen auch wieder Objekte und Arrays enthalten, so dass verschachtelte Informationsstrukturen in nahezu beliebiger Tiefe möglich sind.
Notation: {
key1:value1, key2:value2, array: [wert1,wert2,wert3], }
ein Beispiel:
{
funktion : "Student",
matrikelnr : 123456789,
belegteKurse : {
12345 : "prozedurale Programmiertechniken",
23456 : "objektorientiertes Programmieren",
34567 : "wissehnschaftliches Arbeiten"
},
emails : [student@uni.de, privat@hoster.de]
}
Die Vorteile von JSON:
- JSON ist ein offener Standard, dessen Spezifikationen für Jeden offen liegen.
- Internatinalisierung per UTF-8 ist standardmäßig implementiert, so dass Characterencodierungsprobleme nicht auftreten.
- JSON hat einen reduzierten Overhead im Vergleich zu XML durch simplere Syntax
- einfaches Mapping von XML oder existierenden DBs auf JSON
9.1.3 JSON Response verarbeiten mit JQuery
JQuery ist eine JavaScript Bibliothek, die häufig in sogenannten Web 2.0 Applikationen Anwendung findet. JQuery ist in der Lage JSON codierte Daten aufzunehmen und in beliebige andere Datenformate wie z.B. XML auszugeben. Der umgekehrte Weg der Umwandlung von z.B. XML zu JSON ist ebenfalls möglich.
Der Einsatz von JQuery ermöglicht hier also die Umwandlung von Dateiformaten zur Verarbeitung in einer CouchDB (Codierung zu JSON) oder die Ausgabe der Datenbankobjekte in einem anderen Format.
Der detaillierte Ablauf ist unter http://api.jquery.com/jQuery.getJSON/ beschrieben, daher wird an dieser Stelle nur auf die JQuery API verwiesen.
9.1.4 B-Tree
Ein B-Tree oder B-Baum ist in der Informatik eine Daten- oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B-Baum ist ein immer vollständig balancierter Baum, der Daten sortiert nach Schlüsseln speichert. B-Bäume wachsen – und schrumpfen – anders als die meisten Suchbäume von den Blättern hin zur Wurzel.
Sie sind besonders für die Aufbewahrung von großen Datenmengen auf sekundären Speichern (z.B. Festplatten) optimiert, weil sie im Vergleich zu normalen Bäumen weniger I/O Operationen bei der Suche benötigen. B-Bäume sind typische Vertreter der Vielwegbäume.
Jeder B-Baum-Knoten enthält n Schlüssel (keys), welche in einem Array angeordnet sind. Die Anzahl n hängt normalerweise von der Blockgröße des sekundären Speichers ab. Jeder Schlüssel beinhaltet neben der eigentlichen Information bzw. dem Verweis auf die Information noch einen Zeiger auf den nachfolgenden B-Baum-Knoten. Außerdem existiert pro B-Baum-Knoten noch ein separater Zeiger p0 auf einen nachfolgenden B-Baum Knoten. Da hier ein Suchbaum vorliegt, muss eine Ordnung herschen. Die Ordnung ist ähnlich dem binären Suchbaum. Der p0-Zeiger verweist auf die kleineren Schlüssel und die Zeiger der Schlüssel verweisen auf die größeren Elemente, in der Art, dass gilt: Alle nachfolgenden Schlüssel eines Schlüssels i sind größer als i aber kleiner als der rechte Schlüsselbruder i+1.
Ein B-Baum wächst immer von unten nach oben.
Einfügen
Beim Einfügen wird zuerst nach einem passenden Platz gesucht (siehe Suchkriterium). Ist der passende B-Baum-Knoten für den Schlüssel gefunden, so wird der Schlüssel in das Schlüsselfeld des Knotens so eingefügt, dass alle Schlüssel aufsteigend sortiert sind. Falls dabei noch ein Platz frei ist, so wird der Schlüssel eingefügt. Sonst muss der Knoten geteilt werden. Dabei wird das mittlere Element entnommen, die linke Hälfte bleibt im Knoten, die rechte Hälfte bekommt einen neuen Knoten. Das entnommene Element wird beim rekursiven Aufstieg dann in den Vaterknoten eingefügt, welcher sich auch wieder teilen kann. Bestehende Verzweigungen werden mitbeachtet. Das, was am mittleren Schlüssel hängt, wird p0-Unterbaum vom neu entstandenen, rechten Knoten. Da die rechte Hälfte immer größer als der mittlere Schlüssel ist, wird sie Nachfolger von ihm.
Video zu Einfügeoperationen in B-Bäumen: http://www.youtube.com/v/XjbZnqvvtXE
Löschen
Das Löschen eines Schlüssels läuft ähnlich, d.h. es wird zuerst der Schlüssel gesucht. Wenn er gefunden ist, dann wird unterscheiden, ob der Schlüssel auf einem äußeren Knoten (Blatt) oder einem inneren Knoten liegt. Im ersteren Fall wird der Schlüssel aus seinem Array gelöscht. Beim zweiten Fall wird es schwieriger: Der Schlüssel darf nicht einfach gelöscht werden, weil an ihm andere Knoten hängen. Es wird daher wie folgt verfahren, dass der zu ersetzende Schlüssel gelöscht und durch den nächstkleineren Schlüssel (also den rechtesten Schlüssel des "nächstlinken" Unterbaumes) ersetzt wird. Die Verzeigerung und die Suchordnung bleiben erhalten. Das 50% Füllungskriterium ist noch zu beachten. Es besagt, dass jeder B-Baum-Knoten außer die Wurzel immer mit minimal n/2 Schlüsseln besetzt sein muss. Diese Forderung besteht, weil durch sie ein schnelles Suchverhalten und damit an eine geringe Baumhöhe realisiert wird. Es muss daher überprüft werden, ob in dem Knoten, in dem ein Schlüssel gelöscht wurde, nicht eine Underflow Situation (50% Füllkriterium ist unterschritten) eingetreten ist. Wenn doch, so wird geprüft, ob nicht die Nachbarknoten einen Schlüssel "übrig" haben. Zuerst wird der rechte Bruder und danach der linke Bruder abgefragt. Die Reihenfolge ist erst rechts dann links, weil es einfacher und schneller ist, an ein Array hinten etwas anzuhängen, als die erste Stelle neu zu besetzen. Falls noch ein Schlüssel übrig sein sollte, so wird dieser eingefügt. Sind aber beide wegen Rationalisierungsmaßnahmen schon minimal besetzt, so kann nur noch der Vaterknoten weiterhelfen. Der Schlüssel des Vaterknotens wird verwendet, der auf den Underflow-Knoten zeigt. Gleichzeitig wird der rechte (wenn nicht vorhanden der linke) Bruder konsolidiert. Die Lücke im Vaterknoten wird durch eventuell vorhandene rechtere Schlüssel aufgefüllt. Natürlich wird auch die Verzeigerung neu angepasst.
Es kann passieren, dass auch der Vaterknoten zu einem Underflow-Knoten wird. In diesem Fall wird rekursive Programmierung angewandt. Falls die alte Wurzel nach einer Löschoperation keine Schlüssel mehr enthält, so wird sie gelöscht. Der p0-Unterbaum wird in diesem Falle neue Wurzel.
Eigenschaften von B-Bäumen
Ein B-Baum der Ordnung m ist ein Baum mit folgenden Eigenschaften:
- Jeder Knoten enthält zwischen m und 2m Elementen (außer der Wurzel, die weniger als m Elemente enthalten kann).
- Jeder Knoten ist entweder ein Blattknoten oder er hat k + 1 Nachfolger, wobei k die Anzahl der Elemente im Knoten ist.
- Alle Blattknoten liegen auf der gleichen Stufe.
Einsatz von B-Bäumen in CouchDB
CouchDb ist eine "Append-Only" Datenbank, was bedeutet, dass Änderungen an Datensätzen nicht durch Überschreiben vorhandener Daten erfolgt, sondern durch Zuweisung einer neuen Revisionsnummer und Anhängen der geänderten Daten an das Datenbankdokument.
Löschen von Datenobjekten erfolgt ausschließlich bei "Kompaktierung" der Datenbank. Bei Anweisung von CoucDB eine Datenbank zu kompaktieren werden alle Revisionen aller Datenbankdokumente bis auf die Aktuelleste gelöscht. Diese Funktion wird eingesetzt um die Größe von Datenbanken zu verkleinern.
9.1.5 Map/Reduce Verfahren
Einfache Verarbeitung von Daten auf großen Clustern
- Framework eingeführt von Google Inc. im Februar 2003
- Begriff Map und Reduce kommt aus der funktionalen Programmierung (imperative Programmierung)
- MapReduce ist in C++, Erlang, Java, Python realisiert
- MapReduce Runtime parallelisiert die Computing Power über große Cluster
- fängt Serverfehler ab
- wird genutzt für Auswertungen und Analysen von sehr großen Datenmengen
- Google hat in den letzten vier Jahren 10.000 MapReduce jobs implementiert und verarbeitet jeden Tag mehr als 20 Petabytes
1. Die MapReduce Bibliothek im Client Programm splittet die Input Files in M Teile und 16-64MB (optionaler Parameter wie groß) und kopiert dann Kopien dieser Programme auf Maschinen im Cluster
2. Eine der Kopien ist der Master. Der Rest sind Worker Processe welche vom Master kontrolliert werden. Es gibt M map Jobs und R Reduce Jobs. Der Master sucht inaktive Worker Prozesse und weist diesen einen Map oder Reduce Task zu.
3. Ein Worker welchem ein Map Job zugewiesen wurde, liest den Inhalt des Inputs und analysiert die key/value paare und weißt jedes Paar der definierten Map Funktion zu. Die Zwischengespeicherten key/value Paare werden im Speicher zwischengespeichert
4. Regelmäßig werden nun die zwischengespeicherten Paare auf die lokale Platte geschrieben und mit der Partition Funktion in R Regionen geschreiben. Die Lokation der zwischengespeicherten Paare auf der Festplatte werden dann an den Master zurückgegeben, welcher dann die Lokationen an den Reduce Worker weiter gibt.
5. Nun wird der Reduce Worker über eine RPC (Remote Procedure Call) informiert, um die gespeierten Informationen der Map Worker von der Festplatte zu lesen. Wenn der Reduce Worker nun alle Daten seiner Partition gelesen hat, sortiert dieser alle gleichen keys und groupiert diese. Anschließend wirde eine Sortierung notwendig, da normalerweise viele Keys der Map Funktion zum gleichen Reduce Taks gehören. Wenn die Menge der zwischengespeicherten Daten zu groß ist, wird ein externe Sortierung genutzt.
6. Der Reduce Workter wiederholt diesen Vorgang für die zwischengespeicherten Daten und für jeden einmaligen Key und übergibt den Key mit den Values and die User Reduce Funktion. Der Output wird dann an das File dieser Reduce Partition angehangen.
Beispiel:
map(String key, String value): // key: document name // value: document contents for each word w in value: EmitIntermediate(w, “1”);
reduce(String key, Iterator values): // key: a word // values: a list of counts int result = 0; for each v in values: result += ParseInt(v); Emit(AsString(result));
- Ein View besteht aus Map und (optional) Reduce Funktionen (JavaScript)
- Anwendung auf alle Dokumente
- View stellt Query Endpunkt dar
- Code in View Ersetzt SQL Abfrage
- Abfrage Parameter (wie WHERE ...)
- All / Key / Range
- Oder: Direktzugriff über Dokument Id
9.1.6 Replikation
- sehr stabil und einfach zu implementieren
- Arbeitet mit einer Sequenznummer, welche bei jeder Änderung hochgezählt wird. Die macht die Replikation sehr effizient und robust.
- Continous Replication (_changes API)
- implementiert in Futon
Die Replikation wird durch das Senden eines POST-requests an die _replicate URL mit einem JSON Objekt getriggert. Im Body ist source und target implementiert.
Dieser Aufruf schickt Dokumente von der lokalen Datenbank zur remote Datenbank (fom.de/testdb):
POST /_replicate HTTP/1.1
{"source":"testdb","target":"http://fom.de/testdb"}
Falls die CouchDB mit user/password gesichert ist, muss dies in der URL angegeben werden:
POST /_replicate HTTP/1.1
{"source":"http://fom.de/testdb","target":"http://admin:password@127.0.0.1:5984/testdb"}
Remote Local --> Remote source = push replication
Remote source --> Local target = pull replication (effizienter und resistenter gegen Fehler besonders bei großen Dokumenten mit großen Attachments)
Die Datenbank auf dem der POST /_replicate HTTP request absetzt wurden, gilt immer als lokal und muss somit ohne http:// angegeben werden. Dieses Beispiel zeigt die unidirektionale Replikation. Für eine bidirektionale Replikation müssen bei beiden Aufrufen einfach source und target getauscht werden.
Für die Continous Replikation muss das Wort "continuous":true als Parameter zum JSON Aufruf angegeben werden:
POST /_replicate HTTP/1.1
{"source":"http://fom.de/testdb","target":"http://admin:password@127.0.0.1:5984/testdb", "continuous":true}
Zum canceln eines Replikations Tasks muss das Wort "cancel": true als Parameter zum JSON Aufruf angegeben werden:
POST /_replicate HTTP/1.1
{"source":"http://fom.de/testdb","target":"http://admin:password@127.0.0.1:5984/testdb", "continuous":true, "cancel":true}
9.2 Lokale Ebene
Hardware/Infrastruktur:
- als Basis wird eine Hardware Appliance benötigt
- Raid Platten / redundander Flash Speicher (möglichst keine beweglichen Teilchen)
- eine kleine mobile CPU und 2GB RAM
- ein A/D Wandler der die analogen Signale des Seismographen in digitale umwandelt und über ein Interface and die CouchDB transferiert
- eine USV bei Ausfall des Stromnetzes
Software/Daten:
- ubuntu 10.04
- CouchDB
- cURL
- 350MB Daten pro Tag
Die lokale Ebene umfasst mehrere Stationen mit jeweils drei Seismographen (bzw. Seismometer, grapho „schreiben“, metréo „messen“) für die Messung Nord-West, Ost-West und oben-unten. Drei Seismographen sind notwendig, um später auf der regionalen Ebene die Herdlokalisaton zu bestimmen. Die Anzahl der Stationen ist abhängig von der Anzahl an Erdbeben, die in der jeweiligen Region vorkommen bzw. vorkamen. Zum Bsp.: Das seismographische Netz in Bayern besteht aus zehn Stationen. Die einzelnen Stationen müssen bestimmte Voraussetzungen erfüllen bzw. bestimmte Komponenten erhalten. Notwendig ist ein PC mit einem Linux-Betriebssystem (hier: ubuntu 10.04), auf dem "CouchDB" installiert ist mit einer ISDN/DSL-Verbindung, um die lokale Datenbank auf die regionale Ebene zu replizieren. Die Festplattenkapazität des PCs hängt von der Dauer der gewünschten lokalen Verfügbarkeit der Daten ab. Eine ausreichend große Festplattenkapazität ist unbedingt notwendig, wenn in der Region mit zeitweisen Unterbrechungen des Netzwerkes zu rechnen ist. Es muss mindestens die Zeit überbrückt werden, bis die Netzwerkverbindung wieder hergestellt ist und die Datenbank vollständig auf die regionale Ebene repliziert ist. Weiterhin wird ein A/D-Wandler benötigt, der die analogen Stromsignale (mV) des Seismographen in digitale Signale umwandelt und sekündlich an den PC sendet, damit sie in der "CouchDB" gespeichert werden. Eine USV ist zu emfehlen, besonders in erdbebengefährdeten Gebieten, um zeitweisen Stromausfall überbrücken zu können. Ein "CouchDB"-Dokument beinhaltet folgende Daten: die GUID (Global Unigue Identifier), die Revision (Version des Dokuments), den Namen der Station, die Region, die Organisation, die Longitude der Station, die Latitude der Station, die Elevation der Station und die jeweiligen mV-Angaben pro Sekunde für jeden einzelnen der drei Seismographen pro Station. Die GUID darf niemals den selben Bezeichner haben, sie kann von "CouchDB" generiert werden. Da die automatische Generierung zu Lasten der Performance der Datenbank geht, setzt sich hier die GUID aus der Longitude, der Latitude und dem jeweiligen Datum im Format yyyymmdd zusammen, um eine eindeutige Identifizierung der Dokumente zu gewährleisten.
Ein komplettes "CouchDB"-Dokument für einen Tag wird demnach wie folgt in der Datenbank dargestellt:
GUID: long+lat+yyyymmdd
_rev (Revision wird automatisch erstellt und verwaltet)
Name der Station
Region
Organisation
Long
Lat
Elevation
Seismograph NS {
00:00:00 : 1,2345
00:00:01 : 9,8765
…
23:59:59 : 6,5748
}
Seismograph OW {
00:00:00 : 1,2345
00:00:01 : 9,8765
…
23:59:59 : 6,5748
}
Seismograph Oben/Unten {
00:00:00 : 1,2345
00:00:01 : 9,8765
…
23:59:59 : 6,5748
}
Der Name der Station, Region und die Organisation werden innerhalb der Datenbank als Zeichenkette (String?) gespeichert, Longitude, Latitude und digitale mv_Signale als float mit vier Nachkommastallen. Die Elevation ist ein flaot mit zwei Nachkommastellen (200,05 m ?).
Ein von CouchDB erzeugter Datensatz pro Station (3 Seismographen) hat eine Größe von 4 KByte. Da sekündlich die mV-Signale gemessen werden, muss dieser Wert mit 60 multiplizert werden (pro Minute), daraus ergibt sich eine Größe von 240 KByte, mal 60 (pro Stunde) 14.400 KByte und mal 24 (pro Tag) 345600 KByte, also rund 350 MByte. Mit dieser Information lässt sich die benötigte Festplattenkapazität bestimmen. Ist es gewünscht oder notwendig lokale Daten eine Woche speichern zu können, ergibt sich eine Festplattengröße von 2.380 MByte, ungefähr 2,5 GByte.
Um die ständige Replikation mit der regionalen Ebene zu ermöglichen, wird die Funktion "Continuous Replication" genutzt. Hinter der "Continuous Replication"-Funktion steckt ein komplexer Algorithmus, der dafür sorgt, dass jedes neu hinzugefügte Dokument in der Quelldatenbank (lokale Ebene) automatisch mit der Zieldatenbank (regionale Ebene) repliziert. Der passende Befehl sieht wie folgt aus:
> curl -X POST http://xxx.x.x.x:1234/_replicate \ -d '{"source":"db-lokal", "target":"db-regional", "continuous":true}'
Sind die Dokumente mit der regionalen Datenbak repliziert, erfolgt die Auswertung der mV-Signale, wodurch Magnitude, Herdentfernung und Herdlokalisation bestimmt werden können.
9.3 Regionale Ebene
Hardware/Infrastruktur
- ein Cluster aus mehreren Servern
- Multicore Prozessoresn
- 32GB RAM (MAP/Reduce findet im RAM statt)
- NFS Zugriff durch eigene NICs (getrennt vom public Netz)
- NAS eines renomierten Herstellers mit ca. 5TB Speicherkapazität
- Backup auf Storage Ebene (Snapshots)
- Gigabit Netzwerk-Infrastruktur
- Redundante MPLS/GBit Ethernet Netzanbindung zwischen den regionalen Zentralen
Software/Daten
- ubuntu 10.04
- CouchDB
- cURL
- redundante Proxies (CouchDB Lounge)
- 19GB Daten pro Tag für RAW Daten (53 Stationen in Deutschland)
- Berechnungsgrundlage: 350MB pro Tag für 53 Stationen
- 19GB Daten pro Tag für berechnete Daten (Herdentfernung, Herdzeit, Magnitude)
- Berechnungsgrundlage: 350MB pro Tag für 53 Stationen
- xGB/Tag für Views
- Kann im Rahmen der Fallstudie nicht theoretisch errechnet werden. Die reale Datenmenge ist abhängig von den wissenschaftlichen Fragestellungen.
In der regionalen Ebene werden die Daten der 53 lokalen Stationen repliziert und können dadurch ausgewertet und analysiert werden. Beim Datenaufkommen handelt es sich um ca. 1.1TB/Monat welche 3 Monate vorgehalten werden. Da die Verfügbarkeit und Performance der Systeme eine weitaus größere Rolle spielt, wird auf der regionalen Ebene Server-Hardware in einem CouchDB Cluster eingesetzt (4 x Server jeweils mit jeweils 2 x 4/8 Core Prozessoren) und einem Shared Storage System welches per NAS Protokoll (Network Attached Storage) mit den Servern verbunden wird. Es handelt sich dabei um ein Storage System mit schnellen SAS/FC Disks in einem Raid Verbund. Das NAS wird mit 2x1Gbit Netzwerkarten angebunden, welche speziell für Storage genutzt werden. Auch hier wird das Linux Betriebssystem ubuntu 10.04 eingesetzt. Als Bandbreite steht eine 10 Mbit Verbindung zur Verfügung.
Die Daten der lokalen Stationen werden in die gleiche Datenbank repliziert, da es nur dadurch möglich wird Views über alle Stationen zu erstellen. Der große Vorteil bei CouchDB ist, dass Views direkt in der Datenbank gespeichert werden und bei neuen Daten nur upgedated wird. Ein View wird alle fünf Minuten erstellt, um so einen möglichst genauen Status über die Situation zu geben. Die Views können dann über den Webbrowser abgerufen werden.
9.4 Globale Ebene
Hardware/Infrastruktur
- ein Cluster aus mehreren Servern
- Multicore Prozessoren
- 32GB RAM (MAP/Reduce findet im RAM statt)
- NFS Zugriff durch eigene NICs (getrennt vom public Netz)
- redundantes Datacenter
- Backup auf Storage Ebene (Snapshots)
- NAS eines renomierten Herstellers mit ca. 30TB Speicherkapazität (für 3 Monate auf Online Storage)
- Archivierungsystem eines renomierten Herstellers (Daten älter 3 Monate auf günstigeren sekundär Storage)
- Gigabit Netzwerk Infrastruktur
- redundante MPLS/GBit WAN Netzanbindung
Software/Daten
- ubuntu 10.04
- CouchDB
- cURL
- redundante Proxies (CouchDB Lounge)
- ca. 280GB/Tag
In der globalen Ebene werden die Daten regionalen Datacenter repliziert und können dadurch zentral ausgewertet und analysiert werden. Das Datenaufkommen beläuft sich auf ca. 280GB/Tag und somit auf 8.4TB/Monat. Da die Verfügbarkeit und Performance der Systeme gerade in Bezug auf die Auswertungen eine weitaus größere Rolle spielt, wird wie auf der regionalen Ebene Server-Hardware in einem CouchDB Cluster und einem Shared Storage System, welches per NAS-Protokoll (Network Attached Storage) mit den Servern verbunden wird, eingesetzt. Es handelt sich dabei um ein Storage System mit schnellen SAS/FC Disks in einem Raid Verbund. Das NAS wird mit GBit Technology angebunden, welches speziell für Storage genutzt werden. Auch hier wird das Linux Betriebssystem ubuntu 10.04 eingesetzt. Als Bandbreite steht eine redundante MPLS bzw. GBit WAN Infrastructur zur Verfügung. Die Daten werden in dieser Datenbank 3 Monate vorgehalten und anschließend in eine Archivdatenbank, welche sich auf günstigem Sekundärstorage befindet, transferiert.
Da es in der globalen Ebene nicht auf eine aktuelle Datenbasis ankommt, wird hier nur jeden Tag ein View erstellt.
Konsistentes Hashing bei Lounge Proxy Einsatz
Der Zugriff auf den CouchDB Cluster wird mit dem Proxy Lounge durchgeführt. Das Storage-Modell von CouchDB nutzt einzigartige Dokument-IDs (unique IDs) zum Speichern von Dokumenten, wodurch eine Partitionierung der Daten durch den Hashwert dieser Dokument-IDs möglich wird.
CouchDB erstellt einen Hashwert aus Hexwerten und mapped diesen auf die Dokument-ID. In dem unten beschriebenen Beispiel sind vier Server und die jeweils aufgeteilten IDs aufgeführt. Jedes Dokument mit dem Start-Hashwert 0,1,2,3 wird also auf den Server1 verwiesen, wo wiederum Hashwerte im Bereich c,d,e,f auf Server4 verwiesen werden. Für den Benutzer ist dieses Verhalten völlig transparent.
| Server | Dokument ID |
|---|---|
| Server1 | 0,1,2,3 |
| Server2 | 4,5,6,7 |
| Server3 | 8,9,a,b |
| Server4 | c,d,e,f |
T02: Konsistentes Hashing für CouchDB Lounge
Durch diese Technologie wird eine verteilte Datenhaltung erst möglich.
10 Fazit
- Reflexion - wurde die Zielstellung erreicht?
Das Ziel, seismolgische Messdaten in einer schemalosen Datenbank zu speichern und auszuwerten, wurde erreicht. Die Fallstudie ergibt nach ausführlicher Recherche die NoSQL-Datenbank CouchDB als geeignetsten Vertreter der schemalosen Datenbanken.
- Kritik - welche Probleme gibt es?
Aufgrund des frühen Auschlusses relationaler Datenbanksysteme durch das CAP-Theorem, konnte der Vergleich von "Stored Procedures", also das Abspeichern von Abfragen und Anweisungen innerhalb einer Prozedur, mit den "Views" der ausgewählten NoSQL-Datenbank "CouchDB" nicht realisiert werden. Des Weiteren sind Views einer SQL-Datenbank und Views einer NoSQL-Datenbank nicht vergleichbar. Von einem Laufzeitvergleich wird daher abgesehen.
Aufgrund des noch recht frühen Entwicklungsstadiums von CouchDB (Versionsstand 0.11), ist eine komplexe Benutzerrechteverwaltung noch nicht implementiert. Zur Zeit der Fallstudie gab es nur Datenbankbenutzer mit uneingeschränkten Administrationsrechten. Aus diesem Grund konnte die Rechteverwaltung auch nicht mit anderen Datenbankparadigmen bzw. Datenbankmanagementsystemen verglichen werden. Sicherungs- und Kontrollmechanismen müssen daher über andere Infrastrukturelle Komponenten gewährleistet werden. Wie diese Mechanismen im Detail aussehen können und wie sie optimal implementiert werden sollten, ist nicht Gegenstand dieser Fallstudie.
- Weiterführung - was kann basierend auf dem Artikel vertiefend betrachtet werden
Eine mögliche Weiterführung auf Grundlage dieser Fallstudie, bietet sich bei allen "Systemen" an, die globale und verteilte Daten speichern und auswerten müssen. Denkbar im wissenschaftlichen Bereich sind z.B. die Erhebung und Analyse von Wasserproben oder die Messung von Emission in der Ökologie.
Abschließend muss gesagt werden, dass schemalose Datenbanken kein Allheilmittel für alle Datenbankanwendungen sind. Sie sind kein Komplettersatz für relationale Datenbanksysteme. Die Sinnhaftigkeit des Einsatzes muss für jede Anwendung individuell geprüft werden. In Szenarien, in denen hohe Performance, parallele Verarbeitung und große Datenmengen gegeben sind, ist der Einsatz einer schemalosen NoSQL Datenbank zu empfehlen.
