Entwicklung eines skalierbaren und verteilten Datenbanksystems (eBook)

Geleitwort 6
Zusammenfassung 8
Inhaltsverzeichnis 9
Abbildungsverzeichnis 15
Tabellenverzeichnis 18
Abkürzungsverzeichnis 20
1. Einleitung 22
1.1. Ziele dieser Arbeit 23
1.2. Aufbau dieser Arbeit 24
2. Grundlagen 27
2.1. Verteilte Datenbankmanagementsysteme 27
2.1.1. Architekturmodelle von VDBMS 28
2.1.2. Fragmentierung und Allokation 29
2.2. Konsistenz 30
2.2.1. Datenzentrierte Konsistenmodelle 32
2.2.2. Clientzentrierte Konsistenmodelle 33
2.3. Fehlerarten 34
2.4. Hashing 34
2.4.1. Hashtabellen 35
2.4.2. Distributed Hashtables 35
2.5. Das CAP-Theorem 36
2.6. NoSQL-Datenbanken 38
2.6.1. Key Value Stores 39
2.7. Cassandra 41
2.7.1. DataStax, Inc. 42
2.7.2. Grundlagen der Cassandra Query Language 42
2.7.3. Zusammengesetzte Primärschlüssel 46
2.7.4. Sekundärindizes 46
2.7.5. Virtuelle Knoten 49
2.7.6. Token-Bereiche 49
2.8. Stromverarbeitung 50
2.9. Speedup und Scaleup 52
2.9.1. Speedup 52
2.9.2. Scaleup 53
2.10. SECONDO 53
2.10.1. Second-Order Signature 54
2.10.2. Architektur von SECONDO 56
2.10.3. Fortschrittschätzung 56
2.11. MapReduce 58
2.11.1. Hadoop 60
2.12. Parallel SECONDO 61
2.12.1. Ausführungspläne in Parallel SECONDO 61
2.13. Verwandte Arbeiten 61
3. Datenströme 66
3.1. Aufzeichnungs- und Analysekomponente 66
3.2. Aufzeichnung eines Datenstroms 67
3.3. Erweiterung der ImEx-Algebra 68
3.3.1. Operator csvimport 68
3.4. Loadbalancer 71
3.4.1. Scheduling 72
3.4.2. Umgang mit Ausfällen 75
3.4.3. Anwendung 77
3.5. Lastgenerator 79
4. Kopplung von SECONDO mit Cassandra 82
4.1. Cassandra-Algebra 82
4.1.1. Operator cspread 84
4.1.2. Operator ccollect 86
4.1.3. Operator ccollectlocal 87
4.1.4. Operator ccollectrange 87
4.1.5. Operator ccollectquery 88
4.1.6. Operator clist 89
4.1.7. Operator cdelete 89
4.1.8. Operator cquerylist 91
4.1.9. Operator cqueryexecute 92
4.1.10. Operator cqueryreset 93
4.1.11. Operator cquerywait 93
4.1.12. Operator sleep 96
4.1.13. Operator statistics 96
4.2. Implementation der Cassandra-Algebra 98
4.2.1. Export von SECONDO-Tupeln 98
4.2.2. Partitionierung von Tupeln 99
4.2.3. Adressierung von Tupeln 99
4.2.4. Ablage von SECONDO-Relationen in Cassandra 100
4.2.5. Bestimmung der lokalen Token-Bereiche 101
4.2.6. Loadbalancing des cpp-Treibers 102
4.2.7. Parallelisierung von CQL-Abfragen 105
4.2.8. Connection Pool 106
4.2.9. Bekannte Probleme 106
5. Verteilte Abfrageauswertung 109
5.1. Grundlagen 109
5.1.1. Partitionierung von Daten 110
5.1.2. Verteilter Join – Ein erster Ansatz 111
5.2. Distributed SECONDO 112
5.2.1. Management-System 114
5.2.2. QueryExecutor – Verteilung von Abfragen 115
5.2.3. Platzhalter in Abfragen 116
5.2.4. Beispielumgebung 122
5.2.5. Systemtabellen von Distributed SECONDO 122
5.2.6. Management von Distributed SECONDO 125
5.2.7. Robuste Partitionierung des logischen Ringes 128
5.2.8. Robuste Partitionierung –Beispiele 134
5.2.9. Atomares Einbringen von Tupeln 138
5.2.10. Robustes Lesen von Relationen 141
5.2.11. Verteilter Join – Die robuste Variante 143
6. Fallstudien 145
6.1. Verarbeiten von Positionsdaten 145
6.1.1. Problemstellung 145
6.1.2. Lösungsmöglichkeit 146
6.1.3. Analyse der Koordinaten 149
6.2. Analyse des Logfiles eines Webservers 152
6.2.1. Problemstellung 152
6.2.2. Lösungsmöglichkeit 153
6.3. Partition based spatial merge join 157
6.3.1. Problemstellung 158
6.3.2. Lösungsmöglichkeit 159
6.4. Zusammenfassung 162
7. Experimente 163
7.1. Umgebung 163
7.1.1. Grundlegendes zu den Experimenten 163
7.1.2. Hardware des Clusters 164
7.1.3. Software des Clusters 166
7.1.4. Zusätzlich installierte Software 167
7.2. Verarbeitung von Datenströmen 168
7.2.1. Durchsatz des Operators csvimport 168
7.3. Datenstromverarbeitung auf homogenen Systemen 172
7.3.1. Durchführung 173
7.3.2. Ergebnis 175
7.3.3. Zusammenfassung 176
7.4. Datenstromverarbeitung auf heterogenen Systemen 178
7.4.1. Durchführung 179
7.4.2. Ergebnis 180
7.4.3. Einfluss der Größe des Bestätigungsfensters 182
7.4.4. Zusammenfassung 186
7.5. Cassandra als Datenspeicher 187
7.5.1. Anzahl der Cassandra-Knoten 187
7.5.2. Konsistenz beim Schreiben 190
7.5.3. Lokalität in Cassandra 191
7.5.4. Größe der Tupel 196
7.5.5. Anzahl der Tupel 197
7.6. Distributed SECONDO 199
7.6.1. Ausführen von verteilten Abfragen 199
7.6.2. Token-Ranges und die Laufzeit von verteilten Abfragen 203
7.6.3. Verteilter Join 204
7.6.4. Ein verzögerter Join mit erhöhter Laufzeit 206
7.6.5. Zeit für den Im- und Export von Tupeln 214
7.6.6. Verteilter spatial Join 214
7.6.7. Verteilter spatial Join ohne Rückschreiben der Ergebnisse 220
7.6.8. Fortschrittschätzung 226
7.6.9. Fazit 228
8. Zusammenfassung und Ausblick 229
8.1. Erweiterungen 229
8.1.1. Anzahl der Distributed SECONDO-Knoten 230
8.1.2. Automatische Skalierung 230
8.1.3. Prepared Statements in SECONDO 231
8.1.4. Laden von einzelnen Token 232
8.1.5. Umstellung auf einen neuen Cassandra-Treiber 232
8.2. Ausblick 233
Anhang A. Veränderungen am DataStax cpp-driver 235
Anhang B. Verwendete Bibliotheken 238
Anhang C. Im Cluster eingesetzte Festplatten 240
Anhang D. UML-Diagramme 243
D.1. CSV-Parser 243
D.2. Loadbalancer 244
Anhang E. Codeblöcke 245
E.1. Zu Kapitel 5 gehörende Codeblöcke 245
E.2. Zu Kapitel 6 gehörende Codeblöcke 247
E.3. Zu Kapitel 7 gehörende Codeblöcke 250
Anhang F. Übersicht über Cassandra 257
F.1. Einleitung 257
F.1.1. Geschichte 258
F.1.2. Grundlagen 258
F.1.3. Einsatzbereiche 259
F.2. Cassandra 260
F.2.1. Datenmodell 260
F.2.2. Architektur von Cassandra 263
F.2.3. Lesen und Schreiben von Daten 269
F.2.4. Sicherheit 275
F.2.5. Performance 276
F.3. Erweiterungen von Cassandra 277
F.3.1. CQL– Cassandra Query Language 278
F.3.2. Integration von Hadoop 279
F.4. Fazit 280
Anhang G. Scripte 281
Anhang H. Quellcode 299
Listingverzeichnis 300
Literaturverzeichnis 302