Systèmes Peer to Peer

Les systèmes Peer to Peer sont aujourd'hui largement connus. Étudions comment les plus répandus sont construits. Cet article entre dans le cadre de la spécialisation Coursera sur le Cloud Computing.

On distingue deux types de systèmes Peer to Peer :

  • Les systèmes non structurés très répandus tels que Napster ou Gnutella
  • Les systèmes structurés développés en milieu universitaire comme Chord ou Kelips

P2P

Systèmes non structurés

Napster

Napster est un outil développé en 1999 pour partager de la musique. Au sein de Napster, on distingue deux types de nœuds :

  • Les clients reliés directement aux serveurs, qui stockent les fichiers et en transmettent la liste aux serveurs. Ce sont aussi eux qui initient les recherches.
  • Les serveurs interconnectés, qui contiennent la liste de tous les fichiers disponibles ainsi que leurs emplacements.

Lorsqu'une recherche est initiée :

  1. Le client envoie une requête aux serveurs
  2. Les serveurs cherchent les clients canditats
  3. Les serveurs envoient leurs réponses
  4. Le client initiateur de la requête ping les candidats pour déterminer le meilleur hôte
  5. Le téléchargement s'effectue.

Pour rejoindre le système, une requête DNS permet de connaître la liste des serveurs et de s'y connecter.

Ce type de système souffre de plusieurs problèmes :

  • C'est un système centralisé : source de congestion, single point of failure.
  • Pas de sécurité, tout est échangé en plain text
  • La loi a tranché de la responsabilité indirecte en ce qui concerne la violation de copyright

Gnutella

Il s'agit ici du premier réel système Peer to Peer.

Chaque client agit aussi comme serveur (peer). Aucun serveur centralisé n'existe dans le système.

Chaque peer est connecté à un certain nombre d'autres peers voisins. Ils forment ensemble un graph de superposition (overlay graph). Chaque nœud stocke :

  • Les fichiers qu'il partage
  • Un ensemble de pointeurs vers les autres peers

5 types de messages transitent à travers le réseau

  • Les requêtes (query)
  • Les réponses (query hit)
  • Des pings pour vérifier la présence d'autres peers
  • Des pongs en réponse aux pings, ils contiennent l'adresse d'autres pings
  • Les push qui servent au transfert de fichiers

Chaque message est étiqueté d'un TTL afin d'éviter qu'ils aient une durée de vie infinie : un nœud décrémente le TTL des messages qu'il reçoit et ne le transmet que lorsque son TTL est supérieur à 0.

Afin de garder un graphe à jour, les nœuds changent périodiquement de voisins.

On distingue plusieurs problèmes dans ce type de systèmes :

  • 50% du trafic est occupé à des échanges de pings et pongs. Pour y remédier on effectue un multiplexage des messages et on cache les résultats.
  • Certaines requêtes sont faites souvent, ce à quoi on peut remédier à l'aide de caches.
  • Le trafic est réduit sur certains hôtes. En utilise alors des serveurs qui servent de proxy. C'est la solution de Fasttrack aussi.
  • Beaucoup de peers sont des free loaders, c'est à dire qu'ils ne font que du téléchargement.
  • On assiste aussi à une inondation du trafic. On peut contourner ce soucis via un routage plus intelligent (et structurer les réseaux Peer to Peer) à l'aide le Chord.

Fasttrack

Même algorithme que Gnutella si ce n'est que certains nœuds sont élus supernodes en se basant sur leur réputation. Un supernode stock, la liste des sous-ensembles <nom de fichier, peer> de ses voisins. Ainsi, il n'a pas besoin d'envoyer de requête pour effectuer une recherche.

L'élection se fait sur la réputation du nœud, à savoir son uptime, ce qu'il envoie, …

Un peer normal effectue ses recherches en contactant un supernode voisin.

BitTorrent

Chaque fichier est découpé en blocs est est associé à un tracker qui contiens les peers qui servent les blocs du fichier. Lorsqu'un peer veut un fichier, il récupère le tracker correspondant puis contacte les peers qu'il contient afin de récupérer le fichier.

On distingue alors deux types de peers pour un fichier donné :

  • Les seeds qui contiennent l'ensemble des blocs du fichier
  • Les leechers qui ne contiennent pas encore tous les blocs. Un nœud effectuant une recherche est un leecher.

Les blocs les plus rares sont récupérés en priorité. Plusieurs optimisations existent :

  • tit for tat : les blocs sont transmis aux nœuds qui ont le meilleur taux d'échange. (Il en est de même pour les leecher et les seeds)
  • choking : le nombre de nœuds en envoi est limité. Cette liste est réévaluée périodiquement

Peer to Peer structuré

Le Peer to Peer structuré sert à concevoir des tables de hachage distribuées. On distingue plusieurs approches largement utilisés par les systèmes noSQL de type key-value.

Chord

Chaque nœud est identifié à partir d'un hash consistant pour l'ensemble des nœuds. Ce hash est tronqué à la taille n2^n est la taille maximale du réseau.

Au niveau adressage, chaque nœud (d'id k connaît :

  • l'id de son successeur
  • Une «finger table» qui contient n entrées. L'entrée i, 0\leq i<n contient l'adresse de nœud immédiatement avant (k+2^i)\mod n.

Les données sont ensuite stockées sur le nœud immédiatement après le hash de leur nom. Pour la recherche, il suffit alors de calculer le hash de la requête et de regarder dans la finger table l'emplacement du nœud immédiatement avant. On lui transmet alors la requête. Si aucun nœud ne correspond, on transmet au nœud successeur. La recherche est de l'ordre de O(n).

On distingue deux problématiques en cas de défaillances :

  • Trouver un chemin qui devait passer par un nœud défaillant : le problème est contourné lorsque chaque nœud stocke un certain nombre de successeurs j.
  • Pour trouver une donnée contenue sur le nœud défaillant. Il suffit alors de stoker une copie sur les j nœuds suivants.

Une valeur de j de 2\log(N) permet de traiter des défaillances de l'ordre de 50% du réseau.

Lorsqu'un nœud rejoint le réseau, le processus d'introduction informe le nœud de son prédécesseur et de son successeur.

  • Le prédécesseur fixe son successeur comme étant le nouveau nœud.
  • Le nouveau nœud fixe son successeur avec les informations qui lui sont transmises.

Pour maintenir une finger table à jour, il suffit que chaque nœud demande périodiquement les informations à ses voisins.

L'équivalent est nécessaire lorqu'un nœud quitte le réseau. Il est nécessaire de disposer d'un détecteur de défaillances.

Pastry

Pastry utilise la même structure et adressage que Chord mail la finger table est basée sur une table de préfixes. A chaque préfixe est associé le nœud le plus proche qui vérifie le préfixe. Par exemple, pour un nœud 01001101, la table de préfixes sera :

  • * : le premier nœud qui commence par 1
  • 0* : le premier nœud qui commence par 00
  • 0100110* : pointe vers le nœud 01001100 s'il existe.

Chaque nœud connaît ses successeur et prédécesseur.

Kelips

Enfin, ce dernier algorithme diffère en groupant les nœuds par groupe d'affinité.

Chaque nœud est identifié par un id correspondant à un hash h consistant. Il est assigné au groupe d'affinité h\mod k.

Chaque nœud a une connaissance complète des nœuds de son groupe d'affinité. Un groupe est maintenu à l'aide d'un membership de type gossip. Chaque nœud connaît aussi un correspondant dans chacun des autres groupes (celui le plus rapide d'accès).

Le stockage d'un fichier est effectué sur le nœud sur lequel il a été uploadé. Son hash et son emplacement sont assignés au groupe correspondant. Chaque nœud du groupe connaît alors l'emplacement du fichier.

Lors d'une recherche, on dispose de plusieurs possibilités pour trouver l'information :

  • Le nœud demande à son contact dans le groupe correspondant
  • Le nœud demande à un nœud de son groupe de demander à son contact
  • Le nœud demande à un contact d'un autre groupe (n'importe lequel) de contacter un nœud dans le groupe correspondant à la recherche

Post a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*