Seminar Verteilte Informationssysteme LH* A Scalable, Distributed Data Structure

Seminar Verteilte InformationssystemeSeminar Verteilte InformationssystemeSeminar Verteilte InformationssystemeSeminar Verteilte Informationssysteme

LH*

A Scalable, Distributed Data Structure


Motivation

• Kontext:Kontext:

- - mehrere Clients teilen sich das File Fmehrere Clients teilen sich das File F

- F ist auf mehreren Seiten gespeichert- F ist auf mehreren Seiten gespeichert

• Forderungen an die Datenstruktur:Forderungen an die Datenstruktur:+ Expansion erst nach Auslastung bestehender server+ Expansion erst nach Auslastung bestehender server

+ Adressberechnung nicht über master site+ Adressberechnung nicht über master site

+ kein atomares Update bei Filezugriffen und + kein atomares Update bei Filezugriffen und

Elementaroperationen für verschiedene Clients Elementaroperationen für verschiedene Clients

Skalierbare, verteilte Datenstrukturmit dem zugehörigen Algorithmus LH*


Lineares Hashing

• Hashfktn hHashfktn hii( C) ( C) C mod N* 2C mod N* 2ii

• Expansion des Files durch Bucket-SplitingExpansion des Files durch Bucket-Spliting

• Zuordnung der Splits durch Zeiger Zuordnung der Splits durch Zeiger nn

• Adressierung mit folgendem AlgorithmusAdressierung mit folgendem Algorithmus

a a h hii (C) (C)

if a < n then a if a < n then a h hi+1i+1( C)( C)

• SplitkontrolleSplitkontrolle

• File-Verkleinerung durch Verschmelzen File-Verkleinerung durch Verschmelzen


• Buckets auf verschiedenen ServernBuckets auf verschiedenen Servern

• Bucket-Level i´ im Kopf gespeichertBucket-Level i´ im Kopf gespeichert

• LH*-File expandiert wie LH-FileLH*-File expandiert wie LH-File

• 3 Prinzipien der Adress-Berechnung3 Prinzipien der Adress-Berechnung

Überblick LH*


Prinzipien der Adressberechnung

1. Client-Adress-Berechnung1. Client-Adress-Berechnung• lokale Parameter n´ und i´lokale Parameter n´ und i´• Manipulation der Parameter nur durch clientManipulation der Parameter nur durch client

2.Prinzip2.Prinzip• Adresskalkulation durch jeden Server Adresskalkulation durch jeden Server • SchlüsselweiterleitungSchlüsselweiterleitung

3. Prinzip3. Prinzip• Sicht-Berichtigungsmeldung (IAM) bei FehladressierungSicht-Berichtigungsmeldung (IAM) bei Fehladressierung• client erhält die Möglichkeit seine Parameter zu client erhält die Möglichkeit seine Parameter zu

korrigierenkorrigieren


Client 1n` = 5i`= 6

Client 2n` = 0i`= 2

Client mn` = 31i`= 9

Server 000

10

Server 001

10

Server 080

9

Server 512

10

Server 583

10

Server 591

10

n = 80

Prinzip von LH *


Client-Adress-Berechnunga´ sei die Resultatadressea´ sei die Resultatadressea´ a´ h hi i (C)(C)

if a´ < n´ then a´if a´ < n´ then a´ h hi+1i+1( C)( C)

j = 5 j = 4 j = 5

0 6 7 15 16 22

j = 4 j = 3 j = 4

0 3 7 10

7

j = 4 j = 3 j = 4

0 3 7 10

7

j = 5 j = 4 j = 5

0 5 16 20

20

j = 4

0 15

15

j = 4 j = 3 j = 4

0 3 7 10

15

j = 4 j = 3 j = 4

0 4 7 11

20

n = 7, i = 4

n` = 3, i` = 3 n` = 3, i` = 3

n` = 3, i` = 3

n` = 4, i` = 3 n` = 5, i` = 4

n` = 0, i` = 4


Server-Adress-Kalkulation

a´ a´ h hjj (C); (C);

if a´ if a´ a then a´´ a then a´´ h hj-1j-1( C)( C)

if a´ > a and a´´ < a´ then a´if a´ > a and a´´ < a´ then a´ a´´ a´´

PropositionProposition

Der Algorithmus findet die Adresse für jeden Der Algorithmus findet die Adresse für jeden Schlüssel C, der mit (A1´) gesendet wurde. C Schlüssel C, der mit (A1´) gesendet wurde. C wird höchstens zweifach weitergeleitet.wird höchstens zweifach weitergeleitet.


PropositionBeweisBeweis

Bucket a erhält C vom Client. Bucket a erhält C vom Client. Falls a = a´ = hFalls a = a´ = hjj (C) gibt es keine Weiterleitung. Sonst betrachte a´´ = (C) gibt es keine Weiterleitung. Sonst betrachte a´´ =

hhj-1j-1 (C) dann gilt (1) n (C) dann gilt (1) n a a 2 2ii oder (2) a < n oder a oder (2) a < n oder a 2 2ii. Für den . Für den

Fall (1) haben wir j = i Fall (1) haben wir j = i Es kann vorkommen, daß a´´ Es kann vorkommen, daß a´´ a, dann findet Weiterleitung zu a´´ a, dann findet Weiterleitung zu a´´

statt.statt.Für a´´Für a´´ a haben wir i´< j-1, a´´ > a, das Level j(a´´) ist j = i und a haben wir i´< j-1, a´´ > a, das Level j(a´´) ist j = i und a´´= h a´´= h j(a´´)-1j(a´´)-1(C).(C).

Dann gilt entweder a´´ = a´ = hDann gilt entweder a´´ = a´ = hii( C) oder a´´= a.( C) oder a´´= a.

Im ersten Fall ist a´´ die Adresse für C, andernfalls Weiterleitung zu a´. Im ersten Fall ist a´´ die Adresse für C, andernfalls Weiterleitung zu a´. Dann j(a´) = i und a´ ist die Adresse von C. Man hat im Fall (1) zwei Dann j(a´) = i und a´ ist die Adresse von C. Man hat im Fall (1) zwei Weiterleitungen.Weiterleitungen.

Betrachte nun (2):Betrachte nun (2):j = i + 1 und a´´ = a , Gilt a´´ > a wird C zu Bucket a´´ weitergeleitet. j = i + 1 und a´´ = a , Gilt a´´ > a wird C zu Bucket a´´ weitergeleitet.

Dann hat man j(a´´) = i Dann hat man j(a´´) = i oder j(a´´) = i + 1. Im letzteren Fall hoder j(a´´) = i + 1. Im letzteren Fall hj(a´´) j(a´´) = a´´ und somit ist a´´ Adresse = a´´ und somit ist a´´ Adresse

für C, sonst a´´ = hfür C, sonst a´´ = hj(a´´)-1j(a´´)-1( C). ( C).

Es kann nun gelten a´ = a´´ , a ´ Es kann nun gelten a´ = a´´ , a ´ 2 2ii, dann j(a´) = i + 1 und a´ Adresse , dann j(a´) = i + 1 und a´ Adresse für C. Auch im Fall (2) gibt es zwei Weiterleitungen.für C. Auch im Fall (2) gibt es zwei Weiterleitungen.


Client-Image-Adjustment

Infolge von Adressierungsfehlern kommt es zur IAM vom Infolge von Adressierungsfehlern kommt es zur IAM vom Server, der das Level j des Buckets beinhaltet, an das C Server, der das Level j des Buckets beinhaltet, an das C gesandt wurde.gesandt wurde.

Korrektur von n´ und i´ durch:Korrektur von n´ und i´ durch:i´ j-1, n´ a+1if n´ 2i´ then n´ 0 i´ i+1; A3


Splitting

• Unkontrolliertes SplittingUnkontrolliertes SplittingSplitkoordinator erhält Meldung über Kollision, meldet Splitkoordinator erhält Meldung über Kollision, meldet die zu splittende Seite zurück und setztdie zu splittende Seite zurück und setztnn n+1if n 2i then n 0, i i+1 A4

• Kontrolliertes SplittingKontrolliertes Splitting-Kollisionsmeldung beinhaltet Anzahl der -Kollisionsmeldung beinhaltet Anzahl der

BucketobjekteBucketobjekte-Überschreitung der Belegungsobergrenze führt zum -Überschreitung der Belegungsobergrenze führt zum Split Split


Belegungs-Kontroll-Strategie für LH*

• ..Bucket s sendet Kollisionsmeldung zu SC, die x beinhaltet

• ..SC setzt d = x / b und eventuell d d 2 falls s < n oder s 2i

• ..SC berechnet den Belegungsfaktor ´ (2i d ) / (2i + n)

• Für ´ > t veranlaßt SC das Bucket zu einem Split

A5


Allokation neuer Seiten

Bucketadressen a sind logische Adressen, die den aktuellen Bucketadressen a sind logische Adressen, die den aktuellen Adressen zugeordnet werden müssen.Adressen zugeordnet werden müssen.

Zwei Basismöglichkeiten:Zwei Basismöglichkeiten:

• Menge der Seiten in statischer TabelleMenge der Seiten in statischer Tabelled.h. s = T(a) oder mit Randomisierung S(a) = T(h(F+a))d.h. s = T(a) oder mit Randomisierung S(a) = T(h(F+a))

• Menge der Seiten für jedes File in dynamischer TabelleMenge der Seiten für jedes File in dynamischer Tabelle


Parallele Anfragen

Hauptvorteil von LH* gegenüber LHHauptvorteil von LH* gegenüber LHZwei BasismöglichkeitenZwei Basismöglichkeiten::• Ausbringen einer NachrichtAusbringen einer Nachricht

- Broadcast (multicast) Meldungen auf die Seiten- Broadcast (multicast) Meldungen auf die Seiten

• Sendung einer Sammlung von Point-to-point Messages zu Sendung einer Sammlung von Point-to-point Messages zu dem Zielbucketdem ZielbucketBearbeitung und Weiterleitung mit folg. AlgorithmusBearbeitung und Weiterleitung mit folg. Algorithmus

while j´ < j do:j´ j´ + 1forward (Q, j´) to Bucket a + 2j´-1 A6endwhile.


Paralleler-Sichtanpassungsalgorithmus

j´ sei nun das maximale j.a´ sei die maximale Bucketadresse, so daß a < 2j´-1

a´´´ sei die maximale Adresse mit a´´´ 2j´-1,

1. i´ j´-12. if both a´ and a´´´ then n´ max (a´ + 1, a´´´ +1 - 2i´)

else if a´ then n´ a´ + 1else if a´´´ then n´ a´´´ + 1 - 2i´

3. if n´ 2i´ then n´ 0; i´ i´ + 1 A7


Performance von LH*Basismaß für die Zugriffsperformance: Anzahl der MeldungenBasismaß für die Zugriffsperformance: Anzahl der Meldungen

• Aufwand fürAufwand für Zufallssuche Zufallssuche:: 2 Meldungen2 Meldungenmit master directorymit master directory :: 3 Meldungen3 Meldungenworst case:worst case: 4 Meldungen4 Meldungen

• Aufwand für Aufwand für EinfügeoperationEinfügeoperation::best case:best case: 1 Meldung1 Meldungworst case:worst case: 3 Meldungen3 Meldungenaverage case:average case: 2 Meldungen2 Meldungen

• Parallele OperationenParallele Operationen::Broadcast: Broadcast: mit Tabelle:mit Tabelle: 1 Meldung1 Meldung

mit SC:mit SC: 2 Meldungen in 2 Runden2 Meldungen in 2 Runden

ppm: ppm: M+1 Meldung in 2 Runden M+1 Meldung in 2 Runden oder M Meldungen in 1 bis i-i´+2 Rundenoder M Meldungen in 1 bis i-i´+2 Runden


Varianten von LH*

• LH* ohne KoordinatorLH* ohne Koordinator-Wert des Splitzeigers wird als „Token“ weitergeleitet-Wert des Splitzeigers wird als „Token“ weitergeleitet-kaskadierende Splits-kaskadierende Splits

• Konkurrierende SplitsKonkurrierende Splits-- Parallele Splits mit Hilfe eines zweiten ZeigersParallele Splits mit Hilfe eines zweiten Zeigers-- PresplittingPresplitting


Simulationsresultate


Performance von LH*


Performance von LH*


Performance von LH*


Performance von LH*

Documents

Seminar Verteilte Informationssysteme LH* A Scalable, Distributed Data Structure