of 32 /32
Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

Embed Size (px)

Citation preview

Page 1: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

Architecture des systèmes pair-à-pair

de gestion de données

Gabriel AntoniuProjet PARISIRISA/INRIA

Page 2: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

2DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Qu’est-ce que le pair-à-pair ?

Une architecture de système distribué : Sans contrôle centralisé Symétrie fonctionnelle des nœuds

Une architecture pour la très grande échelle

Nœud

Nœud

Nœud Nœud

Nœud

Internet

Page 3: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

3DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Le modèle pair-à-pair

Caractéristiques Haute dynamicité

– Composition et topologie du réseau Extensibilité Haute disponibilité

– Réplication

Applications Partage de données Messagerie instantanée Calcul global

Page 4: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

4DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Recherche d’un objetdans un réseau pair-à-pair

Problème : trouver une donnée à partir d’un mot-clé

Nœud

Nœud

Nœud Nœud

Nœud

Internet

?

Page 5: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

5DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Localisation centralisée : Napster

Goulot d’étranglementTaille du répertoire central : O(n)Vulnérabilité

Internet

BD

?

PublicationTransfert 3

1

2

Page 6: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

6DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Localisation par inondation : Gnutella

Coût élevé (grand nombre messages)Réponse partielle

Internet

?

3

1

2

1?

2

?

?

?

Page 7: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

7DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Localisation d’un objet

Sources des difficultés Comment obtenir des réponses

pertinentes ? Placement arbitraire des objets

Simplifier le problème Une clé unique pour chaque objet Affectation « intelligente » des

clés aux nœuds Trouver l’objet à partir de clé

Solution : table de hachage !

Internet

?

Page 8: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

8DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Localisation par hachage

Approche totalement distribuéeLocalisation exacte et efficaceEquilibrage de charge (tables de routage, trafic)Extensible

Internet

Localiser (clé)

Publier (clé, objet)

1

2

Page 9: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

9DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Défis

Minimiser le nombre de sautsMinimiser la taille des tables de routageRéagir efficacement à la dynamicité

Freenet (I. Clarke) : anonymatChord (MIT) : efficacité et simplicitéTapestry (Berkeley) : introspection et auto-maintenancePastry (Rice/MSR) : extensibilité

Page 10: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

10DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Exemple : Chord Hachage clé -> successeur

N32

N10

N100

N80

N60

Espace circulairedes ID

(m bits)

• Les clés et les nœuds ont des identifiants uniques sur m bits• Successeur : le plus petit ID(noeud) ID(clé)

K33, K40, K52

K11, K30

K5, K10

K65, K70

K100

Clé Noeud

02m-1 1

Page 11: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

11DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Localisation

N32

N10

N5

N20

N110

N99

N80

N60

N40

“Où est la clé 50?”

“La clé 50 est sur le noeud 60”

Page 12: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

12DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Tolérance aux fautes :Listes de successeurs

N32

N10

N5

N20

N110

N99

N80

N60

• Chaque nœud mémorise r successeurs• Les nœuds “morts” peuvent être ignorés

N40

10, 20, 32

20, 32, 40

32, 40, 60

40, 60, 80

60, 80, 99

80, 99, 110

99, 110, 5

110, 5, 10

5, 10, 20

Page 13: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

13DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Efficacité :Table des raccourcis

N10

½ ¼

1/8

1/161/321/64

1/128

• N mémorise raccourci[k] = Successeur(N + 2k-1)

Page 14: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

14DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Localisation en O(log N) sauts

N32

N10

N5

N20

N110

N99

N80

N60

Localiser(K19)

K19

Page 15: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

15DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Insertion d’un nœud

N36

N40

N25

1. Localiser(N36)K30K38

Page 16: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

16DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Insertion d’un nœud (2)

N36

N40

N25

2. N36 positionne son successeur

K30K38

Page 17: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

17DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Insertion d’un nœud (3)

N36

N40

N25

3. Copie des clés 26..36depuis N40 vers N36

K30K38

K30

Page 18: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

18DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Insertion d’un nœud (4)

N36

N40

N25

4. Positionner successeur(N25)

K30K38

K30

Page 19: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

19DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Localisation dans ChordRésumé

API : localisation(clé) adresse IP Chord ne stocke pas les données

Simplicité Efficacité: O(log N) sauts N est le nombre total de nœuds

Extensibilité: taille des tables O(log N)Tolérance aux fautes

Page 20: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

20DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Table de hachage distribuée

Table de hachage distribuée

get (clé) valeurput(clé, valeur)

Service de localisation

localiser(clé) Adresse IP

DHash distribue les données sur plusieurs nœuds

(DHash)

(Chord)

nœud nœud nœud….

Page 21: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

21DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Rôle de la couche de gestion des données

(DHash)

Put(clé, valeur) et get(clé) valeur Un “bloc”= une paire clé/valeur

Utilise Chord pour le stockage des blocsTolérance aux fautes : réplication des blocsEquilibrage de charge : cacher les blocsAuthentification du contenu des blocs

Page 22: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

22DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

DHash : réplication des blocs sur r successeurs

N40

N10

N5

N20

N110

N99

N80

N60

N50

Bloc17

N68

Réplicas faciles à trouver en cas de panne du successeur Hachage des IDs -> pannes indépendantes

Page 23: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

23DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Gestion des réplicas par le premier successeur

N40

N10

N5

N20

N110

N99

N80

N60

N50

Bloc17

N68

Copie de17

Page 24: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

24DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

CFS : Système de fichiers pair-à-

pair

Table de hachage distribuée

Système de fichiers en lecture seule

get(clé) valeur

nœud nœud nœud….

put(clé, valeur)

Service de localisation

localiser(clé) Adresse IP

Les fichiers ont des noms uniques CFS découpe le fichier en blocs et les stocke grâce à DHash

(DHash)

(Chord)

(CFS)

insert(fichier) lookup(fichier) fichier

Page 25: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

25DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

La couche CFS

CFS interprète les blocs DHash Blocs de données Blocs de méta-données

Racine

signature

H(I)

I

H(D)

D

H(F)

F

B1

B2

H(B1)

H(B2)

Répertoire I-nœudI-nœud

répertoire

Exemple : /D/F

… … ……

Page 26: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

26DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Combiner localisation et routage :

Pastry, Tapestry

Système de stockage de fichiers

route(msg, clé)

Service de localisation et routage

Les données sont envoyées à des IDs, non à des adresses IP Pas (forcément) de découpage en blocs

(PAST, Oceanstore)

insert(fichier) lookup(fichier) fichier

nœud nœud nœud….

(Pastry, Tapestry)

reply

Page 27: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

27DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Gestion de données modifiables :

Ivy

Table de hachage distribuée

Système de fichiers modifiables

get(clé) valeur

nœud nœud nœud….

put(clé, valeur)

Service de localisation

localiser(clé) Adresse IP

Nouveau bloc pour chaque modification sur Ivy Ecrivains multiples : un journal par utilisateur Faible nombre d’utilisateurs

(DHash)

(Chord)

(Ivy)

insert lookup read/write

Page 28: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

28DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Gestion de données modifiables :

OceanStore

Page 29: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

29DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Dissémination des fragments

Hypothèse : peu de modifications

Page 30: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

30DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Conclusion

Résultats significatifs Stratégies de localisation Extensibilité Disponibilité Gestion de la dynamicité Tolérance aux fautes Applications : stockage persistant et partage

en lecture seuleTo do list Plates-formes d’évaluation expérimentale

réaliste Prise en compte d’autres applications

– Calcul scientifique

Page 31: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

31DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Stockage pour le calcul scientifique : quelques problèmes

Partage de données modifiables Peu d’écrivains Peu de modifications Modèle de cohérence ?

Partage de données structurées Gestion de matrices distribuées

Prise en compte de la topologie réseau Hiérarchie Liens haut-débit

Sécurité, authentification

Page 32: Architecture des systèmes pair-à-pair de gestion de données Gabriel Antoniu Projet PARIS IRISA/INRIA

32DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA

Ecole DRUIDE 2004

• DistRibUtIon de Données à grande Echelle CNRS, INRIA, ARP, ACI Port aux Rocs (Bretagne) 24-28 Mai 2004