9. Cloud -Datenspeicherung und MapReduce -Parallelisierungdbs.uni-leipzig.de/file/mrdbs-ws0910-kap9.pdf · ± Spam -(UNHQQXQJ« Ausnutzung ... MR -Job Submission MR -Layer über HDFS

WS09/10, © Prof. Dr. E. Rahm

9. Cloud-Datenspeicherung und

MapReduce-Parallelisierung

Einführung Cloud Data Management

Verteilte Datenhaltung– Dateisysteme (GFS)– Hbase (Google Big Table)– Amazon Dynamo

MapReduce– Idee– Open Source-Realisierung – Hadoop

MapReduce vs. Parallele DBS

MapReduce - Erweiterungen

– Hive

– HadoopDB

9-1


Cloud Computing“Cloud computing is using the internet to access someone else's software running on someone else's hardware in someone else's data center”

- Lewis Cunningham

Externe Bereitstellung von IT-Infrastrukturen sowie Applikations-Hosting über das Internet (bzw. Intranet)

– Public Cloud vs. Private Clouds

Charakteristika:

– Illusion unendlicher, „on demand“ verfügbarer Ressourcen

– Virtualisierung: gemeinsame Nutzung v. Ressourcen durch viele Nutzer

– „Elastizität“ - schnelle Belegung/Freigabe von Ressourcen nach Bedarf

(„Hinzuschalten“ weiterer Rechner)

– Abrechnung nach Verbrauch (CPU Zyklen, Speicherplatz,

Übertragungsvolumen)

9-2


Cloud Computing (2) Vorteile Cloud User

– Kein Einrichten/Betreiben eigener Rechenzentren

– Keine langfristige Ressourcenplanung

– Keine hohen Vorabinvestitionen - pay per use

– Verspricht wesentliche Kosteneinsparungen (u.a. für Startups)

Vorteile Cloud Provider

– Aufteilung verfügbarer Ressourcen auf mehrere Kunden

– Große Rechenzentren (50.000 Server) haben im Vrgl. zu mittelgroßen

(1000 Server) nur 1/5 - 1/7 der Kosten

– Standortvorteile - Elektrizitätspreise, Löhne, Steuern

– Green Computing- Bessere Auslastung der Clouds im gegenüber lokalen Rechenzentren

9-3


Cloud Computing - Einteilung

9-4

IaaS

Infrastructure as a Service

PaaS

Platform as a Service

SaaS

Software as a Service


Cloud-Einsatzbeispiele

Amazon EC2 (Electronic Compute Cloud)

– „Mieten“ einer Menge virtueller Maschinen

– Verwendung für Anwendungen beliebiger Art

„Online-Speicher“ Amazon S3

– Speichern und Lesen von Daten über Webservice von überall zu jeder

Zeit

– Schnell, billig, hochverfügbar, hochskalierbar

9-5


Cloud-Einsatzbeispiele 2

Google App Engine

– Plattform zum Entwickeln und Vorhalten von Webanwendungen

– Python, Java etc.

Cloud-basierte Office-Anwendungen (realisiert als Web-Dienste)

– Google Mail, Docs, Google Calendar, ...

– Keine lokale Software und Datenhaltung

– Universeller Zugang mittels Browser/

Thin Client

9-6


Cloud Data Management

Cloud-Anwendungen erfordern Datenhaltung / Austausch von Daten in der Cloud

Effiziente und persistente Verwaltung großer Datenmengen die Speicherkapazität eines Rechners übersteigen (mehrere TB-PB)

Möglichkeiten:

– Verteiltes Filesystem (Google File System, Hadoop DFS)

– Cloud-Datenbanken

- statt RDBMS oft Key-Value Stores (Bigtable/Hbase, Dynamo, Cassandra, CouchDB, …)

Map/Reduce-Paradigma zur Parallelisierung

Unterstützung für parallele Datenauswertungen / Data Mining

– OLAP - multidim. Aggregation großer Datenmengen

– ACID nicht erforderlich

9-7


Google File System1 (GFS)

Proprietäres, verteiltes Linux-basiertes Dateisystem

– Hochskalierend: tausende Festplatten, mehrere 100TB

– Open Source-Alternative - Hadoop Distributed File System

Netzknoten: „billige“ Standardhardware (kein RAID)

– Hardwarefehler- und ausfälle sind Regelfall

– Gewährleistung von Datensicherheit

optimiert für Streaming Access

– File-Änderungen durch Anhängen: write once - read many times

– Verteiltes, sequentielles Lesen (blockweise)

Hoher Durchsatz statt geringer Latenz1 S.Ghemawat, H. Gobioff, S. T. Leung. The Google File System. SOSP 2003

9-8


Google File System

Physische Datenpartitionierung in Chunks (Default: 64 MB)

– Verteilung über mehrere Chunkserver (und Replizierung jedes Chunks)

Master-Server (Metadaten)

– Mapping: Datei->Chunk->Node

– Replikat-Management: Default 3 Chunk-Kopien (in 2 Racks)

– Anfragebearbeitung, Zugriffsverwaltung

Architektur

9-9


HBase1

Verteilte Datenspeicherung nach Vorbild von Google Bigtable2

– Spaltenorientierter Key-Value-Store

– Multi-Dimensional

– Versioniert

– Hochverfügbar

– High-Performance

Ziele

– Milliarden von Zeilen, Millionen von Spalten, Tausende von Versionen

– Real-time read/write random access

– Große Datenmengen (mehrere PB)

– Lineare Skalierbarkeit mit Anzahl Nodes

1 http://hadoop.apache.org/hbase/2 Fay Chang, Jeffrey Dean, Sanjay Ghemawat et al. Bigtable: A Distributed Storage System for Structured Data. OSDI‟06

9-10


Hbase: Einsatzfälle Web-Tabelle

– Tabelle mit gecrawlten Webseiten mit ihren Attributen/Inhalten

– Key: Webseiten-URL

– Millionen/Milliarden Seiten

Random-Zugriff durch Crawler zum Einfügen neuer/geänderter Webseiten

Batch-Auswertungen zum Aufbau eines Suchmaschinenindex

Random-Zugriff in Realzeit für Suchmaschinennutzer, um Cache-Version von Webseiten zu erhalten

9-11


Datenmodell Hbase / Bigtable Verteilte, mehrdimensionale, sortierte Abbildung

(row:string, column:string, time:int64) string

– Spalten- und Zeilenschlüssel

– Zeitstempel

– Daten bestehen aus beliebigen Zeichenketten / Bytestrings

Zeilen

– (nur) Lese- und Schreiboperationen auf eine Zeile sind atomar

– Speicherung der Daten in lexikographischer Reihenfolge der

Zeilenschlüssel

[CDG+08]

9-12


Datenmodell Hbase/Bigtable (2) Spaltenfamilien (column families)

- Können n verwandte Spalten (ähnliche Inhalte) umfassen- Spaltenschlüssel = Spaltenfamilie:Kennzeichen

- Benachbarte Speicherung von Spalten einer Familie

- innerhalb Familie: flexible Erweiterbarkeit um neue Spalten

Zeitstempel

– mehrere Versionen pro Zelle

– festgelegte Versionszahl: automatisches Löschen älterer Daten

[CDG+08]

9-13


Konzeptionelle Sicht (alternativ)

Physische Speicherung (Hstore)

Datenmodell

Row Key Time Stamp Column

Contents

Column Family Anchor

“com.cnn.www” T9 Anchor:cnnsi.com CNN

T8 Anchor:my.look.ca CNN.COM

T6 “<html>.. “

T5 “<html>.. “

Row Key Time Stamp Contents

com.cnn.www T6 “<html>..”

T5 “<html>..”

Row Key Time Stamp Anchor

com.cnn.www T9 Anchor:cnnsi.com CNN

T5 Anchor:my.look.ca CNN.COM

9-14


HBase Hohe Schemaflexibilität über Spaltenfamilien

– Optionale Verwendung von Spalten pro Satz

– Pro Spaltenfamilie können zur Laufzeit beliebig viele Spalten hinzugefügt

werden

Bsp:

9-15

create ‘test’, {NAME=>‘fam1’, VERSIONS=>2}put ‘test’, ‘row1’, ‘fam1:col7’, ‘value1’put ‘test’, ‘row2’, ‘fam1:col8’, ‘value2’put ‘test’, ‘row2’, ‘fam1:col8’, ‘value3’

scan‘test’ ROW COLUMN+CELLrow1 column=fam1:col7, timestamp=123, value=value1row2 column=fam1:col8, timestamp=125, value=value2row2 column=fam1:col8, timestamp=127, value=value3


HBase Regions (Tablets in Bigtable)

– Horizontale Partitionierung von Tabellen in Regions

– mehrere Region-Server zur Aufnahme der Regions Lastbalancierung

– Region-Split in 2 gleich große Regions, wenn max. Größe (z.B. 128 MB)

erreicht

Architektur

– Datenspeicherung in Region-Server

– Master

- weist Regions Region-Servern zu

- Recovery für Region-Server

RegionServer

RegionServer

RegionServer

Master Server

HStore HStore Region

9-16


HBase

9-17

region {

-ROOT-

.META.

user table 1

user table n

Zweistufige Katalogverwaltung: Tabellen ROOT, META

– META verwaltet Liste aller (user table) Regions

– ROOT: 1 Region mit Liste der META-Regions

Eintrag enthält 1st Row Key, Location, Status, …– Tabellen sind sortiert nach Start-Row-Key

Adressraum (Eintragsgröße 1 KB, Regiongröße 128 MB):


Hbase vs. RDBMS Hbase-Eigenschaften

– Verteilte Punkt- und Scan-Anfragen für Reads/Writes

– Built-In-Replikation

– Skalierbarkeit

– Batch-Verarbeitung (Source/Sink für MapReduce)

– Denormalisierte Daten / breite, spärlich besetzte Tabellen

– kostengünstig

– keine Query-Engine / kein SQL

– Transaktionen und Sekundär-Indexe (extern) möglich, jedoch schlechte

Performance

RDBMS

– deklarative Anfragen mit SQL (Joins, Group By, Order By …)

– automatische Parallelisierbarkeit auf verschiedenen PDBS-Architekturen

– Sekundär-Indexe

– Referenzielle Integrität

– ACID-Transaktionen, …9-18


Amazon Dynamo Verteilter, skalierbarer Key-Value-Speicher

– v.a. für kleine Datensätze (z.B. 1 MB/Key), z.B. Warenkörbe

– hochverfügbar

“Eventually consistent data store”

– Schreibzugriffe sollen immer möglich sein

– reduzierte Konsistenzzusicherungen zugunsten Verfügbarkeit

Performance SLA (Service Level Agreement)

– “response within 300ms for 99.9% of requests for peak client load of 500

requests per second”

P2P-artige Verteilung

– keine Master-Knoten

– alle Knoten haben selbe Funktionalität

9-19


Amazon Dynamo Knoten bilden logischen Ring

– Position entspricht zufälligem Punkt im Wertebereich einer Hashfunktion

Knoten speichert Daten, deren Key-Hashwert zwischen Vorgänger und ihm liegt

jedes Datum über N Knoten repliziert

– Präferenzliste: Liste der Knoten, die zur Datenspeicherung für einen Key

zuständig

9-20


Amazon Dynamo Key-Value-Store-Interface

– Put (key, context, object)

- Context enthält u. a. Versionsnummer des Objektes (aus vorheriger Leseoperation)

- Lokales Schreiben des Objektes, Erhöhen der Versionsnummer

- asynchrone Aktualisierung der Replikate -> Konsistenzprobleme

– Get (key)

- Kann mehrere Versionen eines Objektes zurückliefern: Liste von (object, context)-Paaren

Primary-Key-Zugriff; keine komplexen Queries – Anfrage kann an beliebigen Knoten des Ringes gesendet werden

– Weiterleitung der Anfrage an einen Knoten der Präferenzliste dieses Keys

Anwendungen sehen Versionierung

9-21


Amazon Dynamo Verwendung von Read/Write-Quoren

– R/W minimale Anzahl der N Replikat-Knoten, die für erfolgreiche Read/Write Operation übereinstimmen müssen

– Anwendung kann (N,R,W) an Bedürfnisse an bzgl. Performanz, Verfügbarkeit und Dauerhaftigkeit einstellen

– üblich ist (3,2,2)

Sloppy Quorum– strenge Konsistenz erfordert R + W > N, W > R/2 hohe Zugriffszeiten

– W=1 Schreiben möglich, solange mindestens ein Knoten arbeitet

– Nutzergesteuerte Konfliktbehandlung für abweichende Versionen

9-22


Amazon Dynamo

Verwenden von “Vector Clocks” um Abhängigkeiten zwischen verschiedenen Versionen eines Objektes darzustellen

– Versionsnummer/zähler pro Replikat-Knoten

z.B. D ([Sx, 1] für Objekt D, Speicherknoten Sx, Version 1

– Vector Clock : Liste von (node,counter)-Paaren zur Anzeige welche

Objektversionen bekannt sind

Beispiel zur Entwicklung von Objektversionen

9-23


Amazon Dynamo mit Vector Clocks feststellbar, ob 2

Objektversionen aufeinander aufbauen oder nicht

– Counter der 1. Vector Clock ≤ alle

Counter der 2. Vector Clock 1.Version

ist Vorfahr, kann gelöscht werden

– sonst Konflikt

Leseoperation liefert im Konfliktfall alle bekannten Versionen inkl. Vector Clocks

– darauf folgendes Update führt

verschiedene Versionen wieder

zusammen

Anwendung kann Konfliktlösung bestimmen– z.B. Mischen verschiedener Warenkorbversionen

9-24

Quelle: G. DeCandia, D. Hastorun, M. Jampani et al.

Dynamo: Amazon‟sHighly Available Key-value Store. SOSP‟07


MapReduce

Framework zur automatischen Parallelisierung von Auswertungen auf großen Datenmengen (Google-Ansatz1)

Nutzung v.a. zur Verarbeitung riesiger Mengen teilstrukturierter Daten in einem verteilten Dateisystem

– Konstruktion Suchmaschinenindex

– Clusterung von News-Artikeln

– Spam-Erkennung …

Ausnutzung vorhandener Datenpartitionierung (GFS, Bigtable)

Verwenden zweier Funktionen Map und Reduce

Map: Verarbeitung von Key-Value-Paaren, Generierung und

dynamische Partitionierung von Zwischenergebnissen (abgeleitete Key-

Value-Paare)

Reduce: Mischen aller Zwischenergebnisse mit demselben Key;

Datenreduktion; Generierung von Key-Value Paaren als Endergebnis

1 Jeffrey Dean,Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. OSDI'04

9-25


MapReducemap: (k1,v1) list(k2,v2)

reduce: (k2,list(v2)) list(k3,v3)

Bsp.

– Bestimmen der höchsten aufgezeichneten Temperatur pro Jahr in großer

Menge von ASCII-Files mit Wetterdaten

– 0043011990999991950051512004...9999999N9+00221+99999999999...

9-26

Adaptiert von: Hadoop The Definitive Guide, 2009, Tom White, O„Reilly

k1 vom Typ Long(File-Offset)

v1 vom Typ String(Zeile selbst)

pro (k1,v1)-Paar wirdEin (k2,v2)-Paar erzeugt(1-elementige Liste)

Sortieren der(k2,v2)-Paare undgruppieren nach k2

Zusammenfassung (Maximum)Aller v2 zu einem k2(1-elementige Liste)


MapReduce Parallele Ausführung der Map- und Reduce- Funktionen

– Lokale Speicherung des partitionierten Map-Outputs

– Reducer holen sich ihren Input ab

9-27

Quelle: http://www.jiahenglu.net/course/advancedDataManagement/

Output der Mapper mitselbem Key wird vom

selben Reducer bearbeitet

Reducer mischen sortierten Map-Output

und übergeben (k2,list(v2))an Reduce-Funktion R

Output d. Mappersortiert und par-

titioniert nach Key


Hadoop Googles MapReduce 2004 veröffentlicht

– Proprietär, nicht verfügbar

Hadoop ist Open Source Alternative

Inspiriert von Googles MR/GFS

Apache Top-Level-Projekt

Unterprojekte: HDFS, MapReduce, HBase, Pig, Hive et al.

Unix-ähnliche OS (Shell Skripte, passwortloses SSH)

Java 6

Große Community

Fertige Distributionen zur Ausführung in Amazon EC2

Sieger des Terabyte Sort Benchmark 2008 & 2009

100 TB Integer in 173 Minuten mit 3452 nodes (2 Quadcore Xeons, 8 GB

Memory, 4 SATA)

9-28


Hadoop

9-29

list(v2)

k1 v1

k2

v2

k3

v3

Bsp.:SELECT line, COUNT(*) FROM file WHERE line LIKE 'pattern' GROUP BY line


Hadoop

9-30

MR-Job Submission

MR- Layer über HDFS

2 Arten von Knoten

Jobtracker - Koordinator

Tasktracker - Ausführung der Map

und Reduce-Funktionen (Tasks)

Jeder Tasktracker hat feste Anzahl an Slots für Map- und Reduce Tasks

Abhängig von #Cores und Hauptspeicher

Tasktracker sind gleichzeitig Chunkserverdes HDFS

Jobtracker weist Tasks an Tasktracker mitfreien Slots zu

Berücksichtigung der Datenlokalität

Quelle: Hadoop The Definitive Guide,

2009, Tom White, O„Reilly


Hadoop Fehlschlag eines Task

– Abbruch/Timeout: Tasktracker meldet failed

– Task wird an anderen Tasktracker vergeben

– Nach vier Fehlschlägen wird Job als failed markiert

Crash Tasktracker

– Abbruch/Timeout: Entfernen aus Tasktracker Pool

– Jobtracker weist diesem Tasktracker keine neuen Tasks mehr zu

– Fertige Map-Tasks laufender Jobs werden neu vergeben- Ergebnisse d. Map-Tasks (im lok. FS des Tasktrackers) nicht erreichbar

- Neustarten aller laufenden Tasks

Tasktracker Slowdown - ausstehende Tasks mehrfach vergeben

Jobtracker - Single Point of Failure

9-31


MapReduce vs. Parallele DBS

9-32

M/R SN-RDBMS

Datengröße TB-PB

Struktur Statisches Schema

Partitionierung Horizontal

Anfrage Deklarativ (SQL)

Zugriff Punkt/Bereich via Indexes

Updates Read and write many times

Scheduling Compile-time

Verarbeitung Effizienter Zugriff auf Attribute

möglich (Storage Manager)

Datenfluss Push - Pipelining von Tupeln

zwischen Operatoren

Fehlertoleranz Query-Restart (z. T. Operator-Restart)

Skalierbarkeit Linear (existierende Setups)

Umgebung Homogen (High-End-Hardware)

Kosten Sehr teuer


MapReduce vs. Parallele DBS Vorteile MapReduce

– Skalierbarkeit/Fehlertoleranz

– Konfigurationsaufwand

– Kosten

– Kein initialer Ladevorgang

Vorteile SN-DBS

– Deklarative Anfragesprache

– Anfragen werden um Größenordnungen schneller beantwortet

– (Zzt.) Arbeit auf komprimierten Daten

– Random Access

Typische Anwendungsfälle MapReduce

– ETL

– Data-Mining, Data-Clustering

– Analyse semistrukturierter Daten (Web-Logs, …)

– Einmal-Analysen eines Datenbestandes

9-33


Hive1

Data Warehouse-Infrastruktur, setzt auf Hadoop auf

Entwickelt für Facebook

– 4TB komprimierte Daten pro Tag

– 135TB komprimierte Daten werden pro Tag analysiert

– 7500 MapReduce/HiveJobs jeden Tag

MapReduce Programmierung Low-Level

– Programme schwer zu warten, kaum Reuse

– Barriere für Nicht-Experten

– Fehlende Ausdrucksmächtigkeit- Hoher Zeitaufwand, um simple Count/Avg-Anfragen in MapReduce zu realisieren

Ziel - Erweiterung der Anfragemöglichkeiten an Hadoop

1 http://hadoop.apache.org/hive/

9-34


Hive What is Hive

– Verwaltung und Analayse strukturierter Daten mit Hilfe Hadoop

– Anfragen mit HiveQL, Ausführung mit MapReduce

– Datenhaltung im HDFS, Metadaten für Abbildung auf Tabellen

– Skalierbarkeit und Fehlertoleranz

– Erweiterbarkeit (UDTF, UDAF)

What Hive is NOT1

– Hive does not and cannot promise low latencies on queries

– The paradigm here is strictly of submitting jobs and being notified when

the jobs are completed as opposed to real-time queries

– Hive queries response times for even the smallest jobs can be of the order

of several minutes

1 http://wiki.apache.org/hadoop/Hive

9-35


Hive HiveQL - SQL-ähnliche Anfragesprache

– σ, π, Equi-⋈, Union, Sub-Queries, Group By, Aggregatfunktionen

– Übersetzung d. Anfragen in MapReduce Jobs

– Ausführung in Hadoop Cluster

– MapReduce Skripte können Bestandteil von Queries sein

Architektur

9-36

– Thrift - Cross-language Service

– Metastore - Tabellen, Spalten/Typ,

Location, Partitionen,

(De)Serialisierungs-informationen, …

– Compiler - Anfrageoptimierung und

Übersetzung des HiveQL-Statements in

DAG von MapReduce Jobs

– Executor - Ausführung der MR-Jobs

entsprechend DAGQuelle: Ashish Thusoo, Joydeep Sen Sarma, Namit Jain et. Al.

Hive - A Warehousing Solution Over a Map-Reduce Framework. VLDB‟09


Hive Tabellen1

– Kann auf exist. Daten im HDFS verweisen

– Tabelle hat korrespond. HDFS-Verzeichnis- /wh/pvs

– Definition von Spalten, anhand denen Daten partitioniert werden- /wh/pvs/ds=20090801/ctry=US- /wh/pvs/ds=20090801/ctry=CA

– Bucketing- Aufteilen der Dateien eines Verzeichnisses anhand Hash-Wert einer Spalte

(Datenparallelität)- /wh/pvs/ds=20090801/ctry=US/part-00000 … - /wh/pvs/ds=20090801/ctry=US/part-00020

Laden von Daten in Tabellen1

– status_updates(user_id int, status string, ds string)

– LOAD DATA LOCAL INPATH ‘/logs/status_updates’ INTO TABLE status_updates PARTITION (ds=’2009-03-20’)

1 http://www.slideshare.net/ragho/hive-user-meeting-august-2009-facebook

9-37

CREATE EXTERNAL TABLE pvs(userid int, pageid int, ds string, stry string)

PARTITIONED ON(ds string, ctry string)STORED AS textfileLOCATION ‘/path/to/existing/file’


Hive Anfrageübersetzung

SELECT * FROM status_updates WHERE status LIKE ‘michael jackson’

Anfrageoptimierung

– Verwerfen nicht benötigter Spalten- Berücksichtigung von. (Outer-)Join- und Selektionsattributen

– Frühes Anwenden von Selektionsprädikaten

– Verwerfen nicht benötigter Partitionen

9-38

Quelle: http://www.slideshare.net/ragho/hive-user-meeting-august-2009-facebook


HiveSELECT COUNT(*) FROM status_updates WHERE ds=‘2009-08-01’

9-39

Updates/Nutzer

Alle Updates

ZwischenspeichernDes Map-Outputs


Hive Join

INSERT INTO TABLE pv_users

SELECT pv.pageid, u.age

FROM page_view pv JOIN user u ON (pv.userid = u.userid)

9-40

key value

111 <1,1>

111 <1,2>

222 <1,1>

pageid userid time

1 111 9:08:01

2 111 9:08:13

1 222 9:08:14

userid age gender

111 25 female

222 32 male

page_view

user

key value

111 <2,25>

222 <2,32>

Map

key value

111 <1,1>

111 <1,2>

111 <2,25>

key value

222 <1,1>

222 <2,32>

Shuffle

SortReduce

pageid age

1 25

2 25

pageid age

1 32

pv_users

Unterscheidung, aus welcherTabelle Key-Value-Paar stammt



Hive Map-Join

– Kleinere Tabelle (benutzerdef.) wird von Mappern in Hash-Tabelle

gehalten

– Keine Reducer notwendig

– N-Wege-Map-Join wenn n-1 Tabellen von Mapper gespeichert werden

können

9-41

pageid userid time

1 111 9:08:01

2 111 9:08:13

1 222 9:08:14

userid age gender

111 25 female

222 32 male

page_view

user

key value

111 <1,2>

222 <1>

Hash table

Map

pageid age

1 25

2 25

1 32

pv_users

Besuchte Seiteneines Users



Hive Group By

INSERT INTO TABLE pageid_age_sum

SELECT pageid, age, count(*)

FROM pv_users

GROUP BY pageid, age

9-42

pageid age

1 25

1 25

pageid age

1 25

2 32

pv_users

Map

key value

<1,25> 2

key value

<1,25> 1

<2,32> 1

Shuffle

Sort

key value

<1,25> 2

<1,25> 1

key value

<2,32> 1

Reduce

pageid age count

1 25 3

pageid age count

2 32 1

pageid_age_sum



HadoopDB1

9-43

M/R (SN-)RDBMS

Struktur Un-/semistrukturierte Daten Strukturierte relationale Daten

Anfrage Map/Reduce Programme

(„etwas SQL“ mit Hive)

SQL

Abfrage-

ausführung

Materialisierung der Ergebnisse

zwischen Map- und Reduce-Phase

Pipelining von Ergebnissen

zwischen Operatoren

Quelle: http://db.cs.yale.edu/hadoopdb/HadoopDB_CLUE.pdf

1 Azza Abouzeid, Kamil Bajda-Pawlikowski, Daniel J. Abadi at al. An Architectural

Hybrid of MapReduce and DBMS Technologies for Analytical Workloads. VLDB„09.


HadoopDB Idee

– Viele unabhängige Single-Node DBS (PostgreSQL/MySQL)

– Hadoop als Koordinator und Kommunikations-Layer

– Anfragen mit MapReduce parallelisiert

– Großteil der Arbeit wird in DBS-Nodes verrichtet

Kombination Fehlertolleranz Hadoop und Performance paralleler DBS

9-44

WS09/10, © Prof. Dr. E. Rahm 9-45

Architektur

– DB-Connector- Hadoop InputFormat-Implementierung

- “Datenbanken für Hadoop wie HDFS-

Blöcke”

– Catalog- Metadaten über DB (Location, Driver, …)

- Metadaten über gehaltene Daten (Par-

titionierung, Replikation, …)

– Data Loader- Partitionierung der Daten während

des Ladens

– SQL to MapReduce to SQL Planner- Erweitert Hive

- Hive ist regelbasiert– keine kostenbasierten Anfrageoptimierung wie DBS

- Anpassung der Hive Ausführungspläne– Erstellen von Single-Node-Queries (Optimierung durch DBS)– Kombination mit MapReduce

HadoopDB

Quelle: http://db.cs.yale.edu/hadoopdb/HadoopDB_CLUE.pdf


HadoopDBSELECT YEAR(salesDate), SUM(revenue)

FROM sales GROUP BY YEAR(salesDate)

9-46

Quelle: Azza Abouzeid, Kamil Bajda-Pawlikowski, Daniel J. Abadi at al. An Architectural

Hybrid of MapReduce and DBMS Technologies for Analytical Workloads. VLDB„09.Hive

SMS SMS (sales partitioniert

nach YEAR)


Zusammenfassung Cloud Computing - Illusion unendlicher, „on demand“

verfügbarer Ressourcen

Verteilte Dateisysteme, z.B. Google FileSystem

– replizierte Speicherung großer Datenmengen

verteilte Speicherung semistrukturierter Daten: Key-Value-Stores

– Beispiele: Google Bigtable/Hbase, Dynamo

– Replikation, Lastbalancierung, sehr einfache Operationen

MapReduce - automatische Parallelisierung von Auswertungen auf großen Datenmengen

Hive - Erweiterung von MapReduce um SQL-ähnliche Anfragemöglichkeiten

HadoopDB – versucht Vorteile von MapReduce und parallelen DBS zu kombinieren

9-47


Literatur The Google File System, Sanjay Ghemawat, Howard Gobioff, Shun T.

Leung, SOSP‟03

MapReduce: Simplified Data Processing on Large Clusters, Jeffrey Dean and Sanjay Ghemawat, OSDI‟04

Bigtable: A Distributed Storage System for Structured Data, Fay Chang, Jeffrey Dean, Sanjay Ghemawat et al., OSDI‟06

Dynamo: Amazon‟s Highly Available Key-value Store, G. DeCandia, D. Hastorun, M. Jampani et al., SOSP‟07

http://hadoop.apache.org

Hadoop The Definitive Guide, 2009, Tom White, O„Reilly

Hive - A Warehousing Solution Over a Map-Reduce Framework, Ashish Thusoo, Joydeep Sen Sarma, Namit Jain et. al., VLDB‟09

http://www.slideshare.net/ragho/hive-user-meeting-august-2009-facebook

HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads, Azza Abouzeid, Kamil Bajda-Pawlikowski, Daniel J. Abadi et al., VLDB‟09

9-48


Vorschau SS2010 Datenbanksysteme 2

Relationales Datenbankpraktikum (IBM DB2)

Data Warehouse-Praktikum

Bio-Datenbanken

Lehrveranstaltungen können auch in Module im WS10/11 eingebracht werden

9-49


MRDBS-Klausur Donnerstag, 11.2.2008, 15:00 Uhr, HS 3

Klausurdauer: 60 Minuten

Anmeldung: OLAT (Anmeldeschluss 31.01.2010)

Stoff: Kap. 1 - 8

Vorbereitung

– Buch Mehrrechner-DBS

– VL-Skript und -mitschriften

– LOTS

9-50

Documents

9. Cloud -Datenspeicherung und MapReduce -Parallelisierungdbs.uni-leipzig.de/file/mrdbs-ws0910-kap9.pdf · ± Spam -(UNHQQXQJ« Ausnutzung ... MR -Job Submission MR -Layer über HDFS