| 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 |
