27
1 8 Replikation und Caching 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

Embed Size (px)

Citation preview

Page 1: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

1

8 Replikation und Caching8 Replikation und Caching

8.1 Anforderungen und Verfahren

8.2 Replikation im Web und in verteilten DBS

7 Event Notification / Aktive Datenbanken

Page 2: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.2

Die Situation im NetzDie Situation im Netz

Diverse (Anwendungs-) Protokolle für verteilte Verarbeitung / Verteilung NNTP:

Sender initiiert, viele Teilnehmer, wenige Nutzer/Nachricht, Replikation ist Standard ( News-Server)

SMTP Sender adressiert Empfänger explizit

HTTP 1:1, vom Empfänger initiiert, hot spots (flash crowds)

Page 3: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.3

BegriffeBegriffe

Caching und Replikation Ziel: Performanz und Verfügbarkeit erhöhen Unterschied?

Replikation Alle Objekte (des Originalbestandes) werden in dem/n

Replikat(en) vorgehalten kein vergeblicher Zugriff (außer wenn Objekt nicht mehr existiert) - static

Meist nicht transparent für Klienten

Cache Wörtlich: "verstecken": meist transparent für Klienten

Objekte migrieren zwischen verschiedenen Speichern (unterschiedlicher Zugriffszeit| räumlicher Entfernung)

"Cache miss": gesuchtes Objekt befindet sich nicht im "nächsten" Cachespeicher - dynamic

Page 4: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.4

Beispiele (Web) Beispiele (Web)

Cache Proxy Cache

ursprünglich Schutzfunktion

Klientenseitig Serverseitig: "reverse cache"

firewallserver

Klienten

Kooperation

Allgemeine Cache-Architektur

ReplikationSpiegel-Server (statische Replikation)Server-Farmen mit identischem Inhalt

Page 5: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.5

Pros und ConsPros und Cons

Vorteile Latenzverringerung (Latenz: wesentlich Signallaufzeit)

Dokumente aus Cache / Replikat 'in der Nähe' Weniger Datenverkehr, weniger Stau

Bandbreite einsparen (langfristig nicht bedeutsam?) Entlastung des Servers Verfügbarkeit (auch bei Netzausfall / Partitionierung)

Nachteile Einzelner Proxy: Engpass " : Ausfall legt System lahm ("single point fo failure") Zusatzkosten ( $ und Zeit, falls "cache miss") Cache Konsistenz: wie garantiert man Klienten

aktuellen Zustand?

Page 6: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.6

Cache EffektivitätCache Effektivität

Cache Hit-Rate (hit rate, analog: miss rate)

h = Anzahl im Cache gefundener Objekte/ Anzahl Zugriffe(typisch: deutlich unter 50 %)

Immer mehr dynamische Inhalte Hit-Rate sinkt

Programme, nicht Daten "cachable" Personalisierte Inhalte mit gleichem Effekt

Effekte spürbar, aber bisher nicht gut verstanden

Bandbreite spielt mittelfristig untergeordnete Rolle Zugriffszeit und Verfügbarkeit verbessern

Tendenziell Replikation

Page 7: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.7

Technik: Adressierung (Replikation) Technik: Adressierung (Replikation)

Standard: HTTP-Request..... <-> Client Multiplexing

Domain Name Service (providerseitig) liefert mehr als eine IP-Adresse

DNS (clientseitig) wählt eine aus Nachteil: Replikate müssen relativ stabil sein, sonst

häufig nicht-lokale DNS - Abfragen Java-Applet, das IP-Auswahl übernimmtNachteil: eine zusätzliche Interaktion

IP-Multiplex Router verteilt Requests

an Server und vermitteltResponse an Client

Router(single point of failure!)

Page 8: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.8

Technik: Adressierung (Replikation)Technik: Adressierung (Replikation) DNS Indirection

Domain name server erhält von einem web Server für einen host domain name mehrere Ips, eine wird ausgewählt (traffic, query Ursprung,...) [Cisco Distributed Director]

Im Gegensatz zu "Client based" trifft Server die Entscheidung: besser

Grundätzlicher Nachteil: DNS-Software ist unter der Prämisse einer stabilen IP – hostname Verbindung geschrieben worden.

dynamisch sich ändernden Replikatadressen: schlecht

HTTP Redirection Klient bekommt vom Server neue Adresse Schwergewichtig: HTTP-roundtrip

IPv6 Anycast Eine IP für mehrere Hosts möglich

Auswahl nach Entfernung, Last (Pakete/Zeit) gemäß Routing table

Page 9: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.9

Replikation und Replikation und KonsistenzKonsistenz

Performanz?

Verfügbarkeit?update

update

update

Konsistenz bei Netz- partitionierung?

Konsistenz bei Ausfall eines Knotens?

update

update

update

Inkonsistenz Sperren aller Kopien während eines updates ? Annahme:

updates erlaubt

Page 10: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.10

RandbedingungenRandbedingungen

Wenn keine Updates .... Beliebige Replikation Zusätzliche Resourcen fast ohne Kosten

Speicher Prozessor

Anwendungen Stabile Datensammlungen

— GenDB für bekannte Arten ("Drosophila")— Bibliographische DB ("Jahres-CD")— Material- / Stoffsammlungen— Fahrpläne (?) — ......

Updatefrequenz ist wichtiger Entwurfsparameter für Replikation!

Page 11: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.11

ExtremeExtreme Updates nur auf "Masterkopie" (primary copy) Replikate können altern

Inserts / deletes, update

Beispiele: Informationsverbreitung (information dissimination) Telefonbuch (CD!)

viele Webserver Literaturdatenbanken Fachdatenbanken (Chemie,...)

Refresh-Kriterien?

- Anzahl inaktueller Objekte? - Maximale Abweichung? (Bsp.: Aktienkurs)

Refresh-Verfahren?

- vollständiger Update / Ergänzung

- nachvollziehen der Änderungen

Wie zu bestimmt man die?Einfach: DNS

Asynchron / lazy

Page 12: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.12

ExtremeExtreme

update

update

update

Ein logisch konsistenter Gesamtzustand

zu jedem Zeitpunkt: x = xr für alle Replikate xr von x Alle Replikate gleichberechtigt

Updates von Replikaten (fast) wie verteilte Transaktion -> Two-Phase-Commit – Protokoll

Nachteil: Performanzverbesserung nur wenn Lese/Schreib-Verhältnis groß, favorisiert Leser

Synchron / eager und transaktional

Page 13: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.13

Distributed TransactionsDistributed Transactions

The Two phase Commit protocol

After prepare phase: participants ready to commit or to abort; they still hold locks

If one of the participants does not reply or is not able to commit for some reason, the global transaction has to be aborted.

Problem: if coordinator is unavailable after the prepare phase, resources may be locked for a long time

Request_to_prepare

Prepared

commit

done

1. Coordinator asks for preparing commit of a transaction

2. If (all participants answer 'prepared')

3. Coordinator asks for commit

else asks for abort

4. Participants send 'done'

Uncertain

period

Page 14: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.14

Distributed TransactionsDistributed Transactions

Problems No problem ... if all systems work reliable Obvious inconsistencies, if one participant commits,

another crashes:

x := x+2x := x-2

Coordinator: COMMIT

P1 commits

P2 crashes, undo??Introduces global inconsistency

P1 P2

AssumptionsEach resource manager has a transactional recovery system(log operations, commit, rollback) There is exactly one commit coordinator, which issues commit for a transaction exactly onceA transaction has stopped processing at each site before commit isissued

Page 15: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.15

ReplikationsmodelleReplikationsmodelle

Wo sind Updates erlaubt? Update anywhere (group replication)

Aufwendig—Jedes Replikat muss dieselbe Arbeit leisten—Aufwendig, Konsistenz zu erhalten

Primary (Master) copy Update nur auf einem Replikat Verfügbarkeit?

Wann werden updates auf Replikaten vollzogen? Synchron (eager) : innerhalb einer

Gesamttransaktion Asynchron (lazy): unabhängig

Page 16: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.16

Primärkopie Primärkopie

Primary Copy

Nachteil: single point of failure für updates alle Updates auf einem Server

Synchrone Änderung Vorteil: garantiert serialisierbar Nachteile synchroner Auffrischung

Zeitaufwand, (verteilte) Transaktion (mit 2PC) Verfügbarkeit

unüblich

T1

T2

TnUpdate (ggf verzögert)

Page 17: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.17

Primary copy, asynchron

Abgebrochene TA entfernen

Log stream

Syslog

Replikate

Log stream

Replikate

Log-Tabelle

Trigger ("on update") veranlassenSchreiben von speziellen update-Transaktionen in Log-Tabelle(deferred update queue in Oracle) Reihenfolge für alle Replikate einhalten, wenn TA auf Replikaten parallel ausgeführt werden!

Page 18: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.18

Wahl einer Ersatz - Primärkopie Wahl einer Ersatz - Primärkopie

Primary copy und Verfügbarkeit? Wie bestimmt man neuen Primary?

Vorab definiert (z.B. höchste Adresse der Hinterbliebenen) Korrekt? Nein!

R1 hat letzten Update x=x*5 von verstorbenem Primary erhalten, R2 noch nicht. Keine Konvergenz! (Konvergenz: Zustand jedes Replikats nimmt irgendwann gleichen Wert an)

Wahlverfahren Ein Replikat R ruft zur Wahl auf Alle senden ihre Version V (jede Änderung inkrementiert V) Derjenige mit höchstem V gewinnt R teilt allen die neue Primary Copy mit

Reicht das?? Nein, ebenfalls keine Konvergenz ...

Page 19: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.19

Wahl einer Ersatz - PrimärkopieWahl einer Ersatz - Primärkopie

Neue PC hat aktuellsten Stand, andere Kopien evtl. nicht

Lösung: Während Abstimmung schickt jedes Replikat auch Nr.

des letzten erhaltenen Log-Records. Gewinner (neuer PC) schickt entsprechende Log-

Records an Replikate

Garantiert Verfahren Serialisierbarkeit? Nein!

Wenn ursprünglicher PC TA abgeschlossen hat, die aber bisher an kein Replikat als "deferred updates" gelangt sind, ist TA verloren. Preis für Verzicht auf 2PC !

Page 20: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.20

NetzpartitionierungNetzpartitionierung

Konsistenz bei Netz- partitionierung? Lösung 1:

update in der Menge, die Primary enthält

Nachteil: wirklicher Ausfalldes Primary nicht erkennbar

Lösung 2: Mehrheitsentscheid (majority consensus) Rechner, von denen mehr als die Hälfte aller

Replikate (evtl. einschl. PC.) erreichbar sind, wählt neuenPrimary

Besser: Jedem Replikat Gewicht zuordnen, Gewichtssumme sei s, Partitionsgesamtgewicht w > ½*sentscheidet(Quorum consensus)

update

Page 21: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.21

Group ReplicationGroup Replication

Group Replication (update everywhere)Synchrone Änderung

2PC garantiert Serialisierbarkeit, aber......favorisiert Lesetransaktionen

Quorum Consensus – VerfahrenSchreibrecht, wenn Schreib-Quorum w (des

Gesamtgewichts) erfülltLeserecht, wenn Lese-Quorum r erfüllt

Bedingungen: Schreibquorum: w > ½* sLesequorum: r + w > s

Quorum vorab festgelegenz.B. r = 4, w = 5

g1=3

g2=1

g3=2g4=2

s = gi

Page 22: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.22

Group ReplicationGroup Replication

..... Majority Consensus

Idee: wenn Lesetransaktion aktiv, dann keine Schreib-TA,

keine konkurrierenden Schreib-TA

Verfahren: lese (schreib-) willige Transaktion sammelt so viele Stimmen, wie Quorum vorschreibt. Im Bsp. Lesetransaktion benötigt etwa a1 und a2

Weiterleiten von Änderungen an Replikate, die nicht zur Mehrheit gehören? Jedes Datum (z.B. Tabellenzeile) besitzt Versionsnr. Versionsnr. wird bei Update erhöht Beim Einsammeln von Schreib- Lesequorum mindestens ein

aktueller Wert

Page 23: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.23

Majority consensusMajority consensus

Weiterleiten von Updates r + w > s

w > ½ * s Lese-TA sieht mindestens

eine aktuelle Kopie Schreib-TA ebenso; Updates

an alle beteiligten Replikate weiterleiten

Leicht erkennbar mit g = 1für alle Replikate(Mehrheitsentscheidung)

10 10

1010

g1=3

g2=1

g3=2g4=2

11 10

1110

g1=3

g2=1

g3=2g4=2

update

Page 24: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.24

Group ReplicationGroup Replication

Asynchron Gefahr der Inkonsistenz Datum mit Zeitstempel

(oder Versionsnr.) versehen

Thomas' Write-Rule: Überschreibe nie ein Datum mit größeremZeitstempel

Implementierung z.B. in MS Access (Wingman replication) Tabellenzeile enthält:

- globale ID- Generation (zählt updates, die schon an andere gesandt wurden)- Version - Feld vector_version [replikat R, maximale Version von R erhalten]

10 10

10

10

x=x+1

x=x+ 2

Page 25: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.25

Group ReplicationGroup Replication

Zur Vermeidung von Inkonsistenz (lost update) Konflikte wegen gleicher Versionin Konflikt-Tabelle merken und ggf. manuell behandeln.

Wichtig: Anwendungscharakteristik beachten z.B. Mobilität mit klarer Partitionierung der änderbaren Daten (Bsp.: Vertreter mit seinen Aufträgen,

Kundenmenge im Allgem. disjunkt)

Produkt: Oracle Lite

Problem: Konflikthäufigkeit wächst quadratisch mit der Anzahl von beteiligten, unabhängig änderbaren Daten, wenn gleiche Zugriffswahrscheinlichkeit für alle Daten

Page 26: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.26

RückschauRückschau

Informationssysteme im Web ..unterscheiden sich in vielerlei Hinsicht von

"Debit-Credit"-Verarbeitung Kein (kaum) Schema vorhanden Antwortmenge: Relevanzsortierung statt

eindeutiger Ergebnisse "inhaltliche Relevanz" über Termhäufigkeiten

definieren Einfachstes Modell "Suche in Zeichenkette"

erfordert gute Indexstrukturen, Analogie zu Gen-DB Nichttextuelle Daten (z.B. Bilder, Töne) : Ähnlichkeit

in hochdimensionalen Räumen: wichtige Problem Mpeg-7: Standard zur systematischen Sammlung

von Metadaten

Page 27: 1 8 Replikation und Caching 8.1 Anforderungen und Verfahren 8.2 Replikation im Web und in verteilten DBS 7 Event Notification / Aktive Datenbanken

8.27

RückschauRückschau

XML: Austauschformat, bringt Struktur in wenig strukturierte Daten

Daten in XML-Format lassen sich in relationalen / oo DB ablegen und suchbar machen. Performanz beachten

Wichtiges Paradigma im Netz: "sich informieren lassen"(alerting, notification)

Setzt technisch aktive Komponenten voraus(Bsp.: aktive Datenbanken, Trigger)

Caching und Replikation: wichtige Performanz- und Verfügbarkeitstechniken im Netz

Replikation ist tricky, besonders mit Serialisierbarkeitsforderung

Weiterhin hochdynamisch Entwicklung zu erwarten