Transcription
NoSQL-DatenbankenKapitel 1: EinführungDr. Anika GroßSommersemester 2017Universität Leipzighttp://dbs.uni-leipzig.de1-1
Inhaltsverzeichnis NoSQL-Datenbanken– Motivation und Definition– Kategorisierung, Eigenschaften CAP-Theorem– ACID-Eigenschaften– BASE-Ansatz1-2
Massives DatenwachstumQuelle: big-data-market/ Schätzung von IBM– Pro Tag werden 2,5 Exabytes an Daten generiert– 90% aller Daten weltweit wurden in den letzten 2 Jahren erzeugtQuelle (05 Feb 2013): 27.wss1-3
DatenproduzentenQuelle: Einführungsveranstaltung Seminar “New Trends in Big Data” WS 2013/141-4
Big Data ChallengesQuelle: ta/1-5
Parallele DBS? Anforderung: Effiziente Verarbeitung großer Datenmengen ––––in einer preiswerten, verteilten (heterogenen) Infrastrukturmit konkurrierenden Schreib- und Lesezugriffenunter Berücksichtigung von Knoten- bzw. Netzwerkausfällenfür beliebige Daten (unstrukturiert, semi-strukturiert, strukturiert) Parallele Datenbanksysteme ungeeignet .––––teure, homogene Infrastrukturgeringe Fehlertoleranz (z.B. Query-Restart)nur für strukturierte Daten (statisches Schema)begrenzte Skalierbarkeit (ca. 100 Knoten) . dafür– mächtige, einfache Anfragesprache– ACID-Eigenschaften– Datenunabhängigkeit1-6
NoSQL-Datenbanken “Not only SQL” „Nicht relationale Ansätze“ Verschiedene Anwendungen erfordern versch. Typen von Datenbanken Keine standardisierte Definition Datenbanksystem, das eines oder mehrere der folgenden Kriterien aufweist– Kein relationales Datenmodell Schemafrei oder schwache Schemarestriktionen Keine Joins / keine Normalisierung– Verteiltes, auf horizontale Skalierbarkeit ausgelegtes System “Commodity Hardware”– “Kein SQL” Zugriff mit einfacher API statt SQL– “Keine Transaktionen” Konsistenzmodell BASE statt ACID1-7
Rückblick - History ( repeats itself ) Early Database Management Systems– Flat File Data Management Systems Oft Daten zu einem Entity in einem record (meist ineffiziente Suche)Datenduplizierung / Redundanz InkonsistenzenKeine Implementierung von ZugriffsrechtenKeine Datenunabhängigkeit Änderungen in Anwendungsprogrammen– Hierarchical Data Management Systems Parent-child relationships (1:N), etwas weniger Redundanz Keine N:M Beziehungen Effizientere Suche– Network Data Management Systems Knoten und gerichtete Kanten ( N:M / mehrere parent records erlaubt), keine ZyklenSchemas zur Definition der Knotentypen und BeziehungenSchwieriges Design und VerwaltungRetrieval: Programm muss ggf. hohe Anzahl an Kanten traversieren Nachteile adressiert von relationalen DBMS1-8
Motivation NoSQL-Datenbanken Relationales Schema zu starr für viele Webanwendungen– Evolution: Änderung der Webanwendung führt meist zu Schemaänderung– Datenstruktur: Heterogene Informationsarten führen zu großen, unübersichtlichenSchemas (u.a. einfache mengenwertige Attribute z.B. Tags)– Impedance Mismatch– Anfrage: Wartbarkeit komplexer SQL-Anfragen (viele Joins) Vorteile relationaler Modellierung spielen geringere Rolle– Data Store meist nur für eine Anwendung, daher Datenunabhängigkeit kein Ziel– Effiziente SQL-Ausführung (Optimierung) durch komplexe Anfragen begrenzt Fokus: Performanz und Verfügbarkeit– begrenzte Skalierbarkeit paralleler Datenbanksysteme– geringe Fehlertoleranz (z.B. Query-Restart)1-9
NoSQL Data Stores* multi-modelKey-Value Stores (Kap.2) Kollektion von Key/Value-Paaren: 1 Wert (z.B. BLOB) je Schlüssel Zugriff über Schlüssel: get(key), put(key, value)*Document Stores (Kap.3) Speicherung semistrukturierter Daten als Dokument (z.B. JSON) Zugriff über Schlüssel oder einfache AnfragespracheWide Column Stores / Record Stores (Kap.5) Tables with records with (many) dynamic columns Zugriff über Schlüssel oder SQL-ähnliche AnfragespracheGraph Databases (Kap.6)* Repräsentation der Daten als Knoten und Kanten mit Properties Datenbankabfragen inkl. Graphalgorithmen Skalierbare Relationale Datenbanken (Kap. 5)MySQL Cluster, MegaStore, VoltDB, Clustrix, ScaleDB, ScaleBase, NimbusDB, .NoSQL – Data Stores for Big Data10
Größe vs. KomplexitätKey-ValueStoresdata sizeColumnStoresDocumentDatabasesGraphDatabases90 % of use casesdata complexity1-11
NoSQL .com/2012/02/overview2.png1-12
DB Engines Ranking �� Data Stores for Big Data13
Inhaltsverzeichnis NoSQL-Datenbanken– Definition und Motivation– Kategorisierung, Eigenschaften CAP-Theorem– ACID-Eigenschaften– BASE-Ansatz1-14
Performantes, verteiltes Datenmanagement Annahmen („Irrtümer“) der verteilten Datenverarbeitung– Das Netzwerk ist ausfallsicher, sicher und homogen– Die Latenzzeit ist gleich Null, der Datendurchsatz unendlich und die Kosten desDatentransports können mit Null angesetzt werden– Die Netzwerktopologie ist ies of Distributed Computing Verteilte Datenverarbeitung erfordert Kommunikation zwischen Knoten– u.a. Synchronisation und Replikation– Robust gegen Knotenausfälle, Nachrichtenverlust, . Trade-off: Performanz vs. Datenkonsistenz– Warten bis alle (relevanten) Knoten synchronisiert sind– Vermeidung (oder Auflösung) von Mischkonflikten1-15
CAP-Theorem [Bre00] [GL02] CAP Consistency, Availability, Partitioning ToleranceConsistency (Konsistenz)– System funktioniert entweder “voll” oder “gar nicht”( ACID-Atomarität)– Alternativ: Updates werden bei allen relevanten Knoten zurgleichen “logischen” Zeit durchgeführt, d.h. alle Knoten/Clientssehen zur selben Zeit die selben Daten ity (Verfügbarkeit)– Jede Lese/Schreib-Anfrage an einen “non-failing” Knoten wird beantwortet, d.h. alle Clientskönnen stets lesen und schreiben.– Knotenausfälle beeinflussen nicht die Verfügbarkeit “lebender” Knoten Partitioning tolerance (Partitionstoleranz)– System funktioniert bei Netzwerkpartitionierung trotz Verlust von Nachrichtenzwischen Knoten weiter– Netzwerk-Partitionierung Knoten aus einer Partition können nicht mehr mit Knoten ausanderer Partition kommunizierenTheorem: Ein verteiltes System kann maximal 2 der 3 Eigenschaften gleichzeitig erfüllen.1-16
CAP Theorem - Fälle(CA)ConsistencyMongoDBBigTableHBaseCPCP Konsistent aber nicht verfügbar beiNetzwerkpartitionierung Transaktionen werden blockiert Vermeidung möglicher Konflikte beiMerge zur Sicherstellung der KonsistenzAvailabilityAP Verfügbar aber nicht konsistent beiNetzwerkpartitionierungPartitionToleranceAP Dynamo/S3Cassandra Writes stets möglich auch wenn keine Kommunikation mitanderen Knoten möglich (z.B. Synchronisation) Notwendigkeit der Konfliktauflösung für inkonsistente Daten(verschiedene Versionen des selben Datums an verschiedenen Knoten)Kontroverse:“2 of 3” irreführend, „CA“ gibt es nicht (CAP gilt für verteilte Systemen):CAP Twelve Years Later: How the "Rules" Have ChangedKlassifikation der Systeme teilweise schwierig!Please stop calling databases CP or APNoSQL – Data Stores for Big DataSource: Misconceptions aboutthe CAP Theorem17
ACID RDBMS gewährleistet für Transaktionen ACID-Eigenschaften Atomicity– ’Alles oder Nichts’-Eigenschaft (Fehlerisolierung) Consistency– eine erfolgreiche Transaktion erhält die DB-Konsistenz(Gewährleistung der definierten Integritätsbedingungen) Isolation– alle Aktionen innerhalb einer Transaktion müssen vor parallel ablaufendenTransaktionen verborgen werden („logischer Einbenutzerbetrieb“) Durability– Überleben von Änderungen erfolgreich beendeter Transaktionen trotz beliebiger(erwarteter) Fehler garantieren (Persistenz)DBS1 VL Prof. Rahm, Uni Leipzig1-18
BASE BA - Basically Available– Partieller Ausfall einiger Teile des verteilten Systems Rest läuft weiter Ohne Replikation: Bsp. 1 von 10 Servern fällt aus 10 % der Queries schlagen fehl NoSQL DBs mit Replikation (replication level 3, 1 Knotenausfall):Queries können noch beantwortet werden S - Soft State– Daten werden letztlich mit aktuelleren Daten überschrieben– Überlappung mit E E - Eventually Consistent– DB kann in inkonsistenten Zustand kommen– Mehrere Kopien (Replika) der Daten auf versch. Servern können fürkurzen Zeitraum inkonsistent sein z.B. Nutzer aktualisiert Daten in einer Kopie, aber andere Kopie behält alten Stand– Letztendlich aktualisiert der Replikationsmechanismus der NoSQL DB alle Replika– Verschiedene Typen: casual consistency, read-your-writes consistency,monotonic read consistency, monotonic write consistency, .1-19
Konsistenzmodelle Strong Consistencyupdate(x,v2)r(x) v1r(x) v2r(x) v2r(x) v2t Eventual Consistencyupdate(x,v2)r(x) v1r(x) v2r(x) v1r(x) v1r(x) v2r(x) v1tinconsistency window1-20
Konsistenzmodelle Read-your-writes Consistencyupdate(x,v2)r(x) v1r(x) v2r(x) v1r(x) v2r(x) v1t Monotonic Read Consistencyupdate(x,v2)r(x) v1r(x) v2r(x) v1r(x) v2r(x) v2r(x) v1t1-21
ACID vs. BASE [Bre00] Aufgeben der (strengen) Konsistenz und des logischenEinbenutzerbetriebs für Verfügbarkeit und PerformanzACIDBASEKonsistenzstreng (stets aktuelle Daten proKnoten)Verfügbarkeiteingeschränkt (z.B. bei Ausfalldes Koordinatorknotens bei 2PC)Prinzip pessimistisch / konservativ Anwendung kann sich auf“Datenqualität” verlassenPrioritätTransaktionen im logischenEinbenutzerbetriebEvolutionaufwändig (Schema)1-22
Inhalt der Vorlesung Techniken zum effizienten Management großer un-/semi-strukturierterDatenmengen Verteilte Architekturen zum– Storage (Speicherung)– Retrieval/Querying (Anfrageverarbeitung) Algorithmen zur– Synchronisation (z.B. für Replikation)– Realisierung von Transaktionen1-23
Inhaltsverzeichnis (vorläufig)1.Einführung NoSQL-Datenbanken CAP-Theorem2.Key-Value Stores Dynamo/Amazon S3 Redis Microsoft Azure Storage3.Document Stores CouchDB MongoDB4.Search Engines Lucene Apache Solr ElasticSearch1-245.Record Stores & RDBMS in der Cloud BigTable/HBase, Cassandra Megastore H-Store/VoltDB Synchronisation Transaktionen6.Graphdatenmanagement Graphmodell & -algorithmen Graphdatenbanken Parallele Graph-Algorithmen
Literatur [Bre00] Brewer. Towards robust distributed systems. Proceedings of theAnnual ACM Symposium on Principles of Distributed Computing (2000)http://www.cs.berkeley.edu/ brewer/cs262b-2004/PODC-keynote.pdf [GL02] Gilbert and Lynch. Brewer's conjecture and the feasibility ofconsistent, available, partition-tolerant web services. ACM SIGACT News(2002)1-25
ElasticSearch 5. Record Stores & RDBMS in der Cloud BigTable/HBase, Cassandra Megastore H-Store/VoltDB Synchronisation Transaktionen 6. Graphdatenmanagement Graphmodell & -algorithmen Graphdatenbanken Parallele Graph-Algorithmen. 1-25 Literatur [Bre00] Brewer. Towards robust distributed systems. Proceedings of the Annual ACM Symposium on Principles of .
