Premières études sur la gestion de la volatilité dans Pastis Fabio Picconi

1

Premières études sur la gestion

de la volatilité dans Pastis

Fabio Picconi

Réunion GDS – 19/11/2004

2

1. Systèmes pair-à-pair Réseaux structurés : Pastry, PAST

2. Pastis Rappel Mises à jour

3. Problème de la volatilité KBR : routage cohérent DHT : accès aux blocs Pastis : modèles de cohérence

Plan de l’exposé

3

Systèmes pair-à-pair

4

Systèmes pair-à-pair

Tier 0

Tier 1

Tier 2

KBR : Pastry

DHT : PAST

Syst. de fichiers réparti Pastis

Couches pair-à-pair

Application

5

Pastry

04F2

5230

834BC52A

8909

8BB2

3A79

8954

8957AC78

895D

E25A

04F2

3A79

5230

834B8909

8954

8957

8BB2

AC78

C52A

E25A

k = 8958

k = 8959

route(m,8959)

root ofkey 8959

Address space

895D

6

PAST

Interface

void put( Key k, Block b );

Block b = get( Key k );

7

PAST

04F2

5230

834BC52A

8909

8BB2

3A79

8954

8957AC78

895D

E25A

04F2

3A79

5230

834B8909

8954

8957

8BB2

AC78

C52A

E25A

k = 8958

k = 8959

put(8959,block)

root ofkey 8959 block

Address space

replica

895D

replica

8

Pastis

9

Pastis

Caractéristiques Simplicité Complètement décentralisé Passant à l’échelle

10

Pastis

Structure similaire à l’UFS (Unix File System) inodes stockés dans des User Certificate Blocks (UCB, modifiables) données stockées dans Content-Hash Blocks (CHB, immuables)

metadata@CHB1@CHB2…

@CHBi@CHBii@CHBiii

UCB1

directory inode

file1 @UCB2file2 @UCB3file3 ……

CHB1

directory contents

metadata@CHB3……

………

UCB2

file inode

…

CHB3

file contents

@CHBx@CHBy@CHBz--- empty ---

CHBi

indirect block

file4 @UCBjfile5 @UCBkfile6 ……

CHBx

directory contents

11

Pastis – mises à jour

metadata@CHB1@CHB2…

@CHBi@CHBii@CHBiii

UCB1

directory inode

file1 @UCB2file2 @UCB3file3 ……

CHB1

directory contentsmetadata@CHB3……

………

UCB2

file inode

foo

CHB3

file contents

insérer les nouvelles données (CHBs) réinsérer l’inode (UCB) qui pointe vers les nouveaux CHBs

12

Pastis – mises à jour

insérer les nouvelles données (CHBs) réinsérer l’inode (UCB) qui pointe vers les nouveaux CHBs

metadata@CHB1@CHB2…

@CHBi@CHBii@CHBiii

directory inode

CHB1

directory contentsmetadata@CHB3……

………

file inode

foo

CHB3

file contents

foo bar

CHB4

new file contents

Insert new CHB into the DHT

UCB1 UCB2

file1 @UCB2file2 @UCB3file3 ……

13

Pastis – mises à jour

insérer les nouvelles données (CHBs) réinsérer l’inode (UCB) qui pointe vers les nouveaux CHBs

metadata@CHB1@CHB2…

@CHBi@CHBii@CHBiii

directory inode

CHB1

directory contentsmetadata@CHB4……

………

file inode

foo

CHB3

file contents

foo bar

CHB4

new file contents

Update file inode to point to new CHB

file1 @UCB2file2 @UCB3file3 ……

UCB1 UCB2

14

Pastis – mises à jour

insérer les nouvelles données (CHBs) réinsérer l’inode (UCB) qui pointe vers les nouveaux CHBs

metadata@CHB1@CHB2…

@CHBi@CHBii@CHBiii

directory inode

CHB1

directory contentsmetadata@CHB4……

………

file inode

foo

CHB3

file contents

foo bar

CHB4

new file contents

Reinsert inode UCB into the DHT

file1 @UCB2file2 @UCB3file3 ……

UCB1 UCB2

15

Volatilité dans les systèmes pair-à-pair

16

Problématique

Réseaux structurés Routage efficace [O(log N)] Routage correcte : le message est délivré à la racine de la clef Il faut maintenir des tables de routage correctes

Resistance à la volatilité : Résilience statique Mesures de temps de session sur des réseaux existants Comportement des prototypes existants en présence d’une forte

volatilité Effets sur les couches DHT et Pastis

17

Volatilité

Résilience statiqueCapacité d’un algorithme de routage pair-à-pair de délivrer un message à sa destination après défaillance d’un ensemble de nœuds

Gummadi et al. (2003) :

18

Mesures de temps de session Effectuées sur des réseaux existants Méthodes actives (crawling, probing) et passives (tracing) Résultats très différents

Volatilité

19

Comportement des prototypes existants Injection de fautes selon un processus de Poisson Mesures : pourcentage de lookups cohérents, latence du lookup

Rhea et al. (2004) :

Volatilité

20

Volatilité

Effets d’un routage défaillantKBR Messages délivrés à de fausses racines

(un nœud croit, à tort, être la racine leafsets incorrects)

DHT Vision incohérente, voir partitionnement du replica set Mises à jour effectuées sur des répliques différentes Données existantes non retrouvées (répliques flottantes)

Pastis Non respect du modèle de cohérence

21

Volatilité – Effets sur le KBR

04F2

3A79

5230

834B8909

8954

8957

8BB2

AC78

C52A

E25A

k = 8959

Address space

895D

root seen by node 5230

root seen by node 3A79

k = 8959

22

Volatilité – Effets sur la DHT

04F2

3A79

5230

834B8909

8954

8957

8BB2

AC78

C52A

E25A

k = 8959

Address space

895D

répliques

23

Volatilité – Effets sur la DHT

04F2

3A79

5230

834B8909

8954

8957

8BB2

AC78

C52A

E25A

k = 8959

Address space

895D

répliques déconnectées

24

Volatilité – Effets sur la DHT

04F2

3A79

5230

834B8909

8954

8957

8BB2

AC78

C52A

E25A

k = 8959

Address space

895D

répliques reconnectées

25

Volatilité

Premiers systèmes adressant la volatilité au niveau KBR : Bamboo (Berkeley, basé sur Pastry)

• Maintenance périodique au lieu de réactive

MSPastry (Microsoft, évolution de Pastry)• Heartbeats, active probing• Propagation des leaf sets correctes

Difficultés Comportement prototypes difficile à analyser par seule simulation Absence de preuve des algorithmes Modèle de communication peu clair DHT : protocole de réplication (répliques flottantes)

26

Volatilité

Directions Peut-on caractériser le comportement défaillant des couches KBR et

DHT en présence d’une forte volatilité ? Peut-on les fiabiliser ?

• Détection de routage défaillant• Déviation maximale par rapport à la vraie racine

Disposant d’un KBR non fiable, peut-on construire au-dessus une DHT fiable ?

• Protocole de réplication (niveau DHT)• Quorum dynamiques ?

Peut-on envisager de fiabiliser la couche tier 2 (Pastis) à partir d’une DHT et KBR non fiables ?

27

Questions ?