Verteilte Algorithmen und Datenstrukturen

Kapitel 4: Caching

Christian Scheideler

Institut für Informatik

Universität Paderborn

Caching vs Hashing

Strategien, um Engpässe zu vermeiden:• Hashing: Vermeidung von Engpässen

durch Streuung• Caching: Vermeidung von Engpässen

durch Lokalität

Formales Ziel: halte Congestion für ein gegebenes Zugriffsmuster so niedrig wie möglich.

Hashing im Netzwerk

Beispiel: k×k-Gitter G=(V,E) mit uniformen Kantenkapazitäten und Speicherkapazitäten für die n=k2 Knoten.

• h:U→V: zufällige Hashfunktion für den Datenraum U.• f:V→U: beliebiges Zugriffsproblem (Knoten v greift auf Datum f(v) zu)

mit f(v1)≠f(v2) für alle v1,v2∈V.

• f definiert Routingproblem P mit Quell-Ziel-Paaren (v,h(f(v)))• Wegen Wahl von h ist Pr[(v,w)∈P] = 1/n für alle v und w• Mit x-y-Routing ist dann die erwartete Congestion O( n ).

Caching im Netzwerk

Beispiel: k×k-Gitter G=(V,E) mit uniformen Kantenkapazitäten und Speicherkapazitäten für die n=k2 Knoten.

• f:V→U: beliebiges Zugriffproblem mit f(v1)≠f(v2) für alle v1,v2∈V.

• Platziere einfach Datum f(v) in v für alle v∈V.

Problem: Zugriffsmuster mag nicht im vornherein bekannt sein!

Caching-Modell• G=(V,E,c): beliebiges Netzwerk• U: Datenraum• Zugriffe: read (lese ein Datum) und write (aktualisiere/speichere ein

Datum)• Bei write ist Zugriff auf ein bestehendes Datum notwendig, falls

vorhanden (z.B. Teilupdate).• Wir beschränken uns auf Datenzugriffe ohne Konflikte (d.h. wir haben

eine eindeutige Ordnung auf den read und write Zugriffen – wie das geht, betrachten wir später).

• Caching Strategie ist konsistent: read Anfrage gibt Ergebnis der letzten write Anfrage auf Datum zurück

• Caching Strategien können Daten in Knoten anlegen, löschen und von Knoten v nach w (über einen Pfad) migrieren.

• Jedes Datum kann eine oder mehrere Kopien im Netzwerk besitzen. Keine Kodierungsstrategien erlaubt.

Caching-Modell• Anfangs hat jedes Datum genau eine Kopie im Netzwerk.• Jede Botschaft und jede Bewegung einer Kopie über eine Kante e erhöht

dessen Congestion (Kosten) um 1/c(e)

Ziel: halte die Congestion so niedrig wie möglich.

Instanzen:• Sei s beliebige Folge von read und write Anfragen.• Wir interessieren uns für Caching-Algorithmen, die s nicht im vornherein

kennen (d.h. wir betrachten online Algorithmen).• Ce

A(s): Congestion in Kante e bei Verwendung von Cachingalgorithmus A

• CA(s) = maxe CeA(s): Congestion von Algorithmus A

• COPT(s) = minA CA(s): bestmögliche Congestion• Algo A ist c-kompetitiv: es gibt Konstante d, so dass für alle s:

CA(s) ≤ cCOPT(s) + d

Caching in Bäumen

T=(V,E): ungerichteter Baum mit c(e)=1 für alle Kanten e

Caching in Bäumen

Caching-Strategie für T:• v führt read(x) aus: v sendet Anfrage zum nächsten

Knoten u in T, der eine Kopie von x hat. Knoten u sendet eine Kopie von x zurück nach v. Jeder Knoten, der von der Kopie besucht wird, speichert eine Kopie von x.

v

ux

x

x

x

x

Caching in Bäumen

Caching-Strategie für T:• v führt write(x) aus: v sendet Anfrage zum nächsten Knoten u in T,

der eine Kopie von x hat. Knoten u initiiert daraufhin die Löschung aller Kopien von x, speichert die neue Kopie von x und sendet eine Kopie von x zurück nach v. Jeder Knoten, der von der Kopie besucht wird, speichert eine Kopie von x.

v

ux

x

x

x

x

x

Caching in Bäumen

Lemma 4.1: Für jedes Datum x und jeden Zeitpunkt t formen die Knoten mit Kopien von x eine ZHK.

Beweis: durch Induktion über Zugriffe auf x in Folge s

Strategie zum Finden der nächsten Kopie von x: • Knoten v besitzt x: einfach.• Alle anderen Knoten v, dessen

Teilbaum die ZHK von x enthält, merken sich einen Hinweis auf das Kind, über das die ZHK erreichbar ist.

• Die restlichen Knoten merken sich nichts für x.

x

Caching in Bäumen

Summe aller Hinweise für Datum x:

Tiefe D: maximal D Hinweise, also durch-schnittliche Hinweislast gering.

x

Caching in Bäumen

Kürzester Weg zu Datum x:

• kein Hinweis im Knoten: gehe hoch• Hinweis im Knoten: folge diesem

x

Caching in Bäumen

Theorem 4.2: Die Caching-Strategie ist 3-kompetitiv.

Beweis:• Es reicht zu zeigen: Caching-Strategie ist 3-kompetitiv für jedes

Datum x.• Betrachte festes Datum x.• Sei e=(a,b) feste Kante im Baum.• Entfernung von e teilt Baum in

Teilbäume Ta und Tb auf.

• Wir betrachten drei Fälle:– [A]: Alle Kopien von x in Ta.

– [B]: Alle Kopien von x in Tb.

– [AB]: Ta und Tb enthalten Kopien von x. (Lemma 4.1: a und b halten Kopien von x.)

b

a

Ta

Tb

Caching in Bäumen

Beweis (Fortsetzung):• Betrachte beliebige Folge s an read und write Anfragen und sei ct die

Konfiguration ([A], [B] oder [AB]) nach Bearbeitung der t-ten Anfrage in s.• Dann hat c0,c1,c2,... die Form

...[?]+[AB]+[?]+[AB]+[?]+[AB]+...

wobei [?] ein Platzhalter für [A] oder [B] ist und [X]+ eine Folge von X-en der Länge ≥1 ist.

• O.b.d.A. Betrachte eine Folge der Form [A]+[AB]+.(Anfangs gibt es nur eine Kopie von x, d.h. wir starten entweder mit [A] oder [B]. Im Fall [A]+ oder [B]+ ist die Congestion von e gleich 0, d.h. Konfigurationsfolgen dieser Form am Ende können wir vernachlässigen.)

• We betrachten die online und optimale Congestion von e für diese Folge.

Caching in Bäumen

Beweis (Fortsetzung):• Für die online Kosten von [A]+[AB]+ gilt:

Teilphase Anfragetyp vorige Konf. online Cong.

[A]+ startet mit write von Ta

(*)[AB] 1

gefolgt von Anfragen aus Ta

[A] 0

[AB]+ startet mit Anfrage aus Tb (**)

[A] 2

gefolgt von read An-fragen aus Ta oder Tb

[AB] 0

Caching in Bäumen

Beweis (Fortsetzung):• Was ist optimale Congestion für [A]+[AB]+?• Angenommen, Congestion 0 wäre möglich.• (*): dann darf OPT keine Kopien in Tb haben,

oder alle Kopien in Tb wären veraltet.

• (**): kann dann aber nicht in Tb bedient werden, also muss Anfrage oder Kopie über e wandern.

• Online Congestion is also höchstens 3 während die optimale Congestion mindestens 1 sind.

Caching in Bäumen

Bemerkungen:• Caching-Strategie auch 3-kompetitiv für

Bäume mit beliebigen Kantenkapazitäten.• Gilt auch für Bäume mit gerichteten (d.h.

bidirektionalen Kanten).

Was ist mit anderen Graphen?

Caching im Gitter

Betrachte beliebiges n×n-Gitter M, für das n eine Zweierpotenz ist. (Verfahren kann aber auch für andere Werte eingesetzt werden.)

Caching im Gitter

Rekursive Partitionierung in Teilgitter:

Dekompositionsbaum T(M)

8 8

8 8 8 8

6 10 6 10 6 10 6 10

Caching im Gitter

Rekursive Partitionierung in Teilgitter:

c(e)=# Kanten raus ausTeilgitter von Kind in e

8 8

8 8 8 8

6 10 6 10 6 10 6 10

Caching im Gitter

Datenspeicherung:• Für jedes Datum x: Baum Tx(M), der eine Kopie von

T(M) ist.• Wir betten Tx(M) in M mithilfe einer (pseudo-) zufälligen

Hashfunktion h:U×V(T(M))→V(M) ein, wobei h(x,v) ein Knoten innerhalb des Teilgitters von M sein muss, das v im Dekompositionsbaum T(M) repräsentiert.

• Wir wenden auf Tx(M) das Baumcaching an und speichern alle Kopien von x in Knoten v in Tx(M) in Knoten h(x,v) im Gitter M.

Caching im Gitter

Anschaulich:Tx(M)

x

x

8 8

8 8 8 8

6 10 6 10 6 10 6 10

Caching im Gitter

• Routing entlang Baumkante in Tx(M) wird simuliert über x-y-Routing in M

Caching im Gitter

• Hinweisschilder vom Baum werden für Gitter übernommen

Caching im Gitter

• Kein Knoten im M mit großer Hinweislast, da jeder Tx(M) anders in M eingebettet wird!

Caching im Gitter

Theorem 4.3: Die Caching-Strategie für das n×n-Gitter ist O(log n)-kompetitiv.

Beweis:• Zunächst vergleichen wir die optimale Congestion COPT(M)

erreichbar im Gitter M mit der optimalen Congestion COPT(T(M)) im Dekompositionsbaum T(M).

• Für jedes Routing von v nach w im Gitter verwenden wir dabei den eindeutigen Weg zwischen den zu v und w gehörenden Blättern in T(M).

wv

v w

M T(M)

Caching im Gitter

Lemma 4.4: COPT(T(M))≤COPT(M).

Beweis:• e={v,w}: Kante in T(M) mit Kapazität c(e)

(w ist Kind von v in T(M)).• C(e): Congestion von e durch Simulation von OPT in M.• Anzahl Botschaften über e: c(e)C(e)• Jede Botschaft über e entspricht Botschaft in M, die

entweder M(w) (das Teilgitter zu w) betreten oder verlassen muss.

• Da nur c(e) Kanten M(w) verlassen, muss es für OPT eine Kante e´ auf der Grenze zu M(w) geben mit Congestion mindestens (c(e)C(e))/c(e) = C(e).

Caching im Gitter

CT(e): Congestion von Kante e in M durch x-y-Routing in der Simulation von T(M) in M

Lemma 4.5: Für jede Kante e in M:

E[CT(e)] = O(log n COPT(T(M))).

Beweis:• e: feste Kante in M.• Cl(e): Congestion von e durch Simulation von Botschaften, die von

Ebene l nach l-1 oder umgekehrt in T(M) geschickt werden.• Wir zeigen: E[Cl(e)] = O(COPT(T(M))) für alle l

• Da es nur O(log n) Ebenen gibt, folgt das Lemma.

Lemma 4.4 und 4.5 ergeben Theorem 4.3.

Caching im Gitter

Beweis von E[Cl(e)] = O(COPT(T(M))) für alle l :• v: Knoten in Ebene l-1 von T(M), für den M(v) Kante e enthält

(kein solcher Knoten, dann Cl(e)=0)• v´: eines der beiden Kinder von v• eT={v,v´}: Kante in T(M)

• C(eT): Congestion von e für unser Caching-Schema• M(v´) ist Q(n/2l/2)×Q(n/2l/2)–Gitter• D.h. Q(C(eT) n/2l/2) Botschaften durch eT

• Datum x hat (pseudo-)zufällige Orte in M(v) und M(v´) für v und v´• Wkeit, dass x-y-Routing zur Simulation einer Botschaft entlang eT durch e geht,

ist Q(2l/2/n). (Verringerung der Varianz: zufälliger kürzester Weg statt nur x-y-Routing.)

• Die erwartete Congestion von e ist also

Q(C(eT) n/2l/2) Q(2l/2/n) = Q(C(eT))

• Also ist E[Cl(e)] = O(C(eT)) = O(COPT(T(M)) nach Theorem 4.2.

Caching im Gitter

Theorem 4.3 ist bestmöglich:

Theorem 4.6: Jede online Caching-Strategie im n×n-Gitter ist W(log n)–kompetitiv.

Hierarchische Dekomposition auf beliebige Netzwerke anwendbar (aber hier nicht behandelt).

Ausblick

Nächste Woche: Verteilter Konsens und Transaktionen