Architecture des systèmes pair-à-pair
de gestion de données
Gabriel AntoniuProjet PARISIRISA/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
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
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
?
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
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
?
?
?
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
?
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
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é
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
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”
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
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)
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
15DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA
Insertion d’un nœud
N36
N40
N25
1. Localiser(N36)K30K38
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
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
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
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
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….
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
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
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
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
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
… … ……
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
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
28DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA
Gestion de données modifiables :
OceanStore
29DataGRAAL - 30/31 janvier 2003 Gabriel Antoniu, projet PARIS, IRISA/INRIA
Dissémination des fragments
Hypothèse : peu de modifications
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
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
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