ANALYSE UND KONZEPTION VON TUPLE SPACES IM HINBLICK AUF SKALI

ERBARKEIT

Philipp Obreiter

Telecooperation Office (TecO)Universitaet Karlsruhe

Betreuer: Guntram Gräf, Martin Gaedke

ZieleSkalierbarer Tuple Space

– ohne zusätzliche Beschränkungen– minimale Zahl zusätzlicher Informationen

Vorgehen:• Formalisierung/Klassifikation von Tupeln• Analyse bisheriger Indexverfahren• Herleitung eines neuen Indexverfahrens• Konzeption der Architektur/Implementierung eines

skalierbaren Tuple Spaces

Fieldhierarchie (F,matchF)

“Hello“ “World“1234 5678

int string

F

Tupelhierarchie (,match)

(int,F)

(int,(int,int))

(F, string)

(int,string) (F,“Hello“)

(int,“Hello“)

(1234,string)

(1234,(56,78))

(5678,“Hello“)

Taxonomie von Schemata

• Freiheitsgrade:(A) Klassenhierarchie

(B) Instanzhierarchie

(C) Semantische Tupel

(D) Verschachtelte Tupel

(E) Tupelhierarchie

• Schema ABCDE schränkt Freiheitsgrade ein

Linda Schema: 23111 A

EB

C D

0

0

0

0 0

1

11

1

2

2 31

TSpaces/JavaSpaces Schema: 00110 A

EB

C D

0

0

0

0 0

1

11

1

2

2 31

Verteilungsmodell• Menge von p Servern {1,...,p}

• Verteilung (W,R) für Tupel t– schreibt auf W(t) {1,...,p}

– liest von R(t) {1,...,p}

Korrektheitsbedingung

match(t1,t2) W(t2) R(t1)

1 2 3 4 5 6

R W

abstrakteDarstellung

Konzeption einer Verteilung

Abstrakte Darstellung

– entkoppelt Abstraktionsvorgang und Anpassung an p

– ist effiziente Datenstruktur

t W(t) t

direkt indirekt

R(t)

W(t)

R(t)

Hashindizierung (I)

(printer,F,F)

P1

(F)

(scanner,F,F)(F,1200dpi,F)

(printer,1200dpi,F) (scanner,1200dpi,F)

P2P3

P4

(F,1200dpi,x.x.x.x)

P5

S4

S5S3

S2S1

{1}

{5}

{6}

{8} {3} {8}{5}{12}

{2}{7}

{1,...,p}

{1,...,p}

{1,...,p}

{1,...,p}{1,...,p}{1,...,p}

{1,...,p}

Hashindizierung (II)

(printer,F,F)

P1

(F)

(scanner,F,F)(F,1200dpi,F)

(printer,1200dpi,F) (scanner,1200dpi,F)

P2P3

P4

(F,1200dpi,x.x.x.x)

P5

S4

S5S3

S2S1

{3}

{3}

{3}

{3} {3} {7}{7}{7}

{7}{7}

{3}

{1,...,p}

{7}

{1,...,p}{1,...,p}{1,...,p}

{1,...,p}

Indizierung durch Hyperquader• Fields:

– hierarchische Struktur Intervalle statt Punkte

– Korrektheit: matchF(f1,f2) F(f2) F(f1)

• Tupel:– Tupel komplex mehrdimensionaler Index

– induziert Trafo auf Hyperquader

• Verteilung:– Aufteilung des Hyperraums in Tupeldomänen 1,... p

– (,) zulässig mit (t) := {q | q(t) }

disjunkte/vollständigeTupeldomänen

1

3

2

-1 0 1 2 3 4 5

1

2

3

4

5

x1

x2

T3T2

T4

T5

T6

T14 5

überlappende/unvollständigeTupeldomänen

-1 0 1 2 3 4 5

1

2

3

4

5

x1

x2

T3T2

T4

T5

T6

T1

3

1 2

ClientClient

AgentAgent

Komponenten der Architektur

F

TupleSpaceServer

TupleSpaceServer

TupleSpaceServer

TupleSpaceServer

-Server -ServerAgenten-server

Agent

Client (t)t (t)

F-Server

Fieldhierarchie nicht a priori bekannt

Aufgaben des F-Server:

• Bereitstellen der Klassendefinitionen• Adaptive Trafo von Fields auf Intervalle

– für 12 automatisierbar durch relative Intervalle

? Garbage collection von Indexbereichen

-Server und Tuple Space Server

• Tupeldomänen müssen adaptiv sein

• Überlauf eines TS Servers:– Teil der Tupel auf freien TS Server verschieben– Einblenden der neuen Tupeldomänen

• Unterlauf eines TS Servers:– lokale Vereinigung (mit Buddy)– Delegation oder Sperren

• Extended k-d tree als Tupeldomänenbaum

Cache-Validation der Agenten

F-Server:

– Lesecache, also stets gültig

-Server:– Unterbäume tragen Sequenznummern– Cacheeintrag invalidiert, wenn mit veralterter

Sequenznummer auf TS Server zugegriffen Extended k-d tree garantiert Korrektheit

SATUS

• Implementierung eines skalierbaren Tuple Spaces

• Management Schnittstelle

• Erweiterung auf 4-tier Architektur

• Eingebaute Standardfields

• Validiert hinsichtlich:– Effizienz der Verteilung– Effizienz der Tupeldomänenadaption

Adaption der Tupeldomänen

0 50 100

.5

Response time

n150 200 250 300 350 400

1

1.5

2.5

2

Fazit?Vorgehen:• Formalisierung/Klassifikation von Tupeln• Analyse bisheriger Indexverfahren• Herleitung eines neuen Indexverfahrens• Konzeption der Architektur/Implementierung eines

skalierbaren Tuple Spaces

Skalierbarer Tuple Space?– ohne zusätzliche Beschränkungen?– minimale Zahl zusätzlicher Informationen?

Fragen?

Verschachtelte Tupel

• Field selber komplex, daher Indizierung nicht direkt anwendbar

• Bei beschränkter Schachtelungstiefe unnesten

• Aufteilung in mehrere Tupel (Atomizität?)

• Aufnahme komplexer Klassen in die Fieldhierarchie

Skalierbarkeit

Fünf Dimensionen:

• Größe der Tupel

• Zahl der Tupel im Tuple Space

• Zahl der eingesetzten Tuple Spaces

• Durchsatz des Tuple Spaces

• Zahl der Clients

Fieldhierarchie

x modulo y fraction

F

1/2 2/4

6/9 4/6

x modulo 5x modulo 3

0 12

0 1

23

4

Tupeldomänenbaum

x2 = 0

2x1 = 2

x2 = 3 x1 = 4

4 5 3 2

Adaptive Trafo

i11[0,0]

f1

[0,100][0,30][30,100]

i12[10,20]

z=0.3

[0,0] [0.1,0.2]

f2

[30,44][30,44][44,44]

z=1size=0.2

i21[30,37]

i22[38,42]

[0,0.5] [0.6,0.9]

f3

[45,100][45,45][45,100] z=0

size=0.8f4

[45,100][45,78][78,100]

z=0.6size=1

Effizienz der Verteilung

0 50 100

.2

Rate

n150 200 250 300 350 400 450 500

.4

.6

1

.8pruning

rate

overhead