Replikation & Konsistenz II

Question 1

Was sind die Faktoren für die Platzierung der Replikatserver ?

Answer 1

minimiere Abstände Server ⟷ Clients

Abstand: Latenz, Bandbreite

Question 2

Wie geht der Greedy - Algorithmus vor um den optimalen Ort für die Platzierung der Replikatserver zu bestimmen ?

Answer 2

Bestimmt Abstand der Clients von den Standorten, stellt Solange Server an Standorte mit dem geringsten Durchschnittsabstand bis alle Server verteilt sind.

Question 3

Wie geht der Autonome-Systeme-Ansatz vor um den optimalen Ort für die Platzierung der Replikatserver zu bestimmen ?

Answer 3

Berücksichtigt Topologie des Internets.

Platziert 1. Server in größtem AS, auf Router mit den meisten Verknüpfungen, 2. Server in zweitgrößtem AS, …

Question 4

Was ist ein Autonomes System im Bezug auf den Autonome-Systeme-Ansatz ?

Answer 4

Internet besteht aus sog. Autonomen Systemen (AS), d.h. Netze, die
• dasselbe IP-Routing-Protokoll verwenden
• von einer Organisation verwaltet werden.

Question 5

Wie geht der HotZone-Ansatz vor um den optimalen Ort für die Platzierung der Replikatserver zu bestimmen ?

Answer 5

Teil Netz in Zellen auf,

sucht Client-Cluster, d.h. Zellen mit vielen Clients und platziert Replikatserver in K größten Clustern

Question 6

Welcher Algorithmus ist am besten für dynamische Platzierung bei Flash Crowds geeignet ?

Answer 6

HotZone-Ansatz, da Laufzeit nur O(N ⋅ max(log(N), k))

Question 7

Welche Arten von Replikaten gibt es ?

Answer 7

• Permanente Replikate
• Server-initiierte Replikate
• Client-initiierte Replikate

Question 8

Was sind Permanente Replikate ?

Answer 8

Grundlegende Menge von Replikaten, die meist beim Design eines Datenspeichers schon angelegt werden

Question 9

Welche Varianten von permanenten Replikaten existieren ?

Answer 9

• transparent repliziert (Client merkt nichts von der Replikation)
• Mirroring (Client sucht bewusst ein Replikat aus)

Question 10

Was sind Server-initiierte Replikate ?

Answer 10

Kurzfristig initiierte Replikate die bei hohem Bedarf eines Datums erstellt werden (meist in der Netzregion, in der der Bedarf auftritt )

Question 11

Was ist die Voraussetzung dafür, Permanente Replikate mit Server-initiierten Replikaten zu ersetzen ?

Answer 11

Server-initiierte Replikate können permanente Replikas ersetzen, wenn garantiert ist, dass
jedes Datum immer von mindestens einem Server vorrätig gehalten wird

Question 12

Was passiert mit den Daten bei einem Client-Initiierten Replikat ?

Answer 12

Daten werden meist für begrenzte Zeit in einem vom Client verwalteten Chache gespeichert

Question 13

Was ist der einzige Zweck von Client-Initiierten Replikaten ?

Answer 13

Verbesserung der Datenzugriffszeiten

Question 14

Was bedeutet es, wenn Updates an den Daten mittels Push propagiert werden ?

Answer 14

Server Schickt Updates nach einer Änderung an alle Clientcaches

Question 15

Wann nutzen wir das Updaten per Push ?

Answer 15

• Wir benötigen einen hohen grad an Konsistenz

- viele Lese- vs. wenig Schreiboperationen

Question 16

Was bedeutet es, wenn Updates an den Daten mittels Pull propagiert werden ?

Answer 16

Server bzw. Clients fragen nach Updates für die Daten

Question 17

Wann nutzen wir das Updaten per Pull ?

Answer 17

gut bei wenig Lese- vs. viele Schreiboperationen oder wenn

geringe Kohärenz erforderlich

Question 18

Was bedeutet es, wenn Updates an den Daten mittels Leases propagiert werden ?

Answer 18

Hybrid aus Push und Pull, bei der während der Laufzeit eines Leases Daten an den jeweiligen Client per Push übertragen werden. Hat ein Client keine Lease, muss er über Pulls nach Updates fragen.

Question 19

Was wird benötigt um die verschiedenen Konsitenzmodelle zu implementieren ?

Answer 19

Protokolle, mit deren Hilfe sich die

verschiedenen Replika-Server abstimmen

Question 20

Worin werden die Konsistenzprotokolle unterteilt ?

Answer 20

In datenzentrierte Konsistenzprotokolle und clientzentierte Konsistenzprotokolle

Question 21

Welche grundlegenden Ansätze Existieren für datenzentrierte Konsistenzprotokolle ?

Answer 21

‣Urbildbasierte Protokolle (Primary-based Protocols)
• Write-Operationen gehen immer an dieselbe Kopie
• auch: Urbildsicherungsprotokolle (Primary Backup Protocols)

‣ Protokolle für replizierte Schreibvorgänge (ReplicatedWrite Protocols)
• Write-Operationen gehen an beliebige Kopien

Question 22

Welche Protokolle existieren, die Urbildbasiert sind ?

Answer 22

Wenn alle Write-Operationen immer nur an eine Kopie gehen, kann man unterscheiden, ob die Primärkopie
• immer am selben entfernten Platz bleibt
→ Remote-Write-Protokolle
• zu dem schreibenden Client verlagert wird
→ Local-Write-Protokolle

Question 23

Wie erfolgt eine Änderung bei dem Remote-Write-Protokoll ?

Answer 23

Wenn Client Datum x ändern möchte:
• lokaler Server S leitet Änderung an Urbildserver U weiter
• U macht Änderung, informiert alle Kopien
• Jede Kopie macht Änderung, sendet ACK an U
• Nachdem alle ACKs eingetroffen: U sendet ACK an S

Question 24

Was ist das Problem der Remote-Write-Protokolle ?

Answer 24

Performance, deshalb wird auch non-blocking
Update eingesetzt (aber hier wieder Problem mit Fehlertoleranz)

Question 25

Für welches Konsistenzmodell eigenet sich Remote-Write-Protokolle ?

Answer 25

Beste Umsetzung für sequentielle Konsistenz

Question 26

Was besagt das Local-Write-Protokoll ?

Answer 26

Jeder Prozess, der ein Update ausführen will, lokalisiert das Urbild und bewegt dieses an seinen eigenen Platz.

Question 27

Wieso eignet sich das Local-Write-Protokoll besonders für mobile Benutzer ?

Answer 27

Der Benutzer holt sich das Urbild, kann danach aber auch bei Verbindungsabbruch ohne Probleme mit den Daten arbeiten

Question 28

Welche Ansätze existieren für replizierendes Schreiben ?

Answer 28

• Aktive Replikation: eine Operation wird an alle Replikas weitergegeben
• Quorum-basiert: es wird abgestimmt, die Mehrheit gewinnt

Question 29

Wie erfolgt das Update bei Aktiver Replikation ?

Answer 29

Jede Replika besitzt einen Prozess, der Updates durchführt.
‣ Updates werden meist als Operation propagiert.
‣ Wichtigstes Problem: alle Updates müssen auf allen Replikas in derselben Reihenfolge ausgeführt werden
→ es wird Multicast mit totaler Ordnung benötigt (kann mittels Lamport-Uhr implementiert werden)

Question 30

Was ist der Nachteil der Aktiven Replikation ?

Answer 30

skaliert schlecht

Question 31

Was ist die Grundidee von Quorum-basierte Protokollen ?

Answer 31

Clients müssen vor Lese- oder

Schreiboperation Erlaubnis mehrerer Server einholen

Question 32

Wie funktionieren Qurom-basierte Protokolle konkret ?

Answer 32

• Angenommen, es gibt N Replikate des Datum X
• X besitzt Versionsnummer
• Schreibprozess benötigt Schreiberlaubnis von NW Servern
• NW > N/2 → verhindert Schreib/Schreib-Konflikte
• Leseprozess benötigt Leseerlaubnis von NR Servern
• NW + NR > N → garantiert, dass Quorum mindestens eine
Kopie der neuesten Version enthält

Question 33

Für welche Konsistenzarten werden Client-zentrierte Konsistenzprotokolle verwendet ?

Answer 33

• Konsistenz für monotones Lesen
• Konsistenz monotones Schreiben
• Read-Your-Writes-Konsistenz
• Writes-Follow-Reads-Konsistenz

Question 34

Was sind die Vorraussetzungen für Client-zentrierte Konsistenzprotokolle ?

Answer 34

‣Jedem Schreibvorgang W wird eine global eindeutige ID zugewiesen;
‣ Pro Client C werden zwei Reihen von Schreibvorgängen überwacht:
1. Lesevorgangsreihe: Schreibvorgänge (aller), die für Lesevorgänge von C relevant sind;
2. Schreibvorgangsreihe: Schreibvorgänge von C