Systèmes de partage de donnée

Systèmes de partage de donnée

Il existe des systèmes de partage de données non modifiables, comme par exemple Orion[55] ou 7DS [80]. Le problème est alors la localisation des données, et ces systèmes proposent soit des algorithmes permettant d’inonder efficacement le réseau avec une requête, soit de répliquer les solutions de localisation par le contenu (DHT) utilisés dans les réseaux pair à pair grande échelle. Dans cette section nous nous intéressons aux systèmes de partage de données modifiables pour MANets. Ces solutions se rapprochent donc plutôt des systèmes de fichiers distribués. 

adHocFS

Le système adHocFS [14] est un système de fichier distribué destiné aux réseaux mobiles ad hoc. Il a été développé à l’INRIA en 2003. Les fichiers partagés sont de type Unix. Dans adHocFS, les pairs partagent des fichiers au sein d’un groupe de sécurité(GdS). Un pair peut appartenir à plusieurs GdS, un fichier appartient à un seul GdS. A l’intérieur d’un GdS, adHocFS constitue des groupes de proximité entre les pairs capables de communiquer. Ces groupes sont utilisés dans les schémas de réplication et de cohérence. Les membres de chaque groupe élisent un leader. Ce rôle est tournant afin de ne pas surcharger un terminal en particulier. Le leader est chargé de maintenir la liste des pairs dans le groupe. A l’intérieur du groupe, les terminaux échangent leurs profils qui, pour un terminal, décrit les répliques hébergées ainsi que les capacités de stockage du terminal. 

Réplication

Les répliques de données sont de deux natures : les terminaux créent tout d’abord à la demande des répliques de travail pour leur propre besoin. S’il y a seulement une seule réplique de travail, des répliques préventives sont ensuite créées (une par donnée). Le choix des hôtes pour ces répliques est basé sur le profil des terminaux. 

Cohérence

La cohérence est hybride. A l’intérieur d’un groupe, les différentes copies sont gérées suivant un modèle de cohérence pessimiste avec un système de verrou pour obtenir un accès. Entre groupes, la cohérence est optimiste : les modifications sont journalisées afin de réconcilier automatiquement les différentes versions quand deux groupess se rejoignent. En cas de divergence, la réconciliation doit être faite manuellement par l’utilisateur. 

Haddock

Haddock FS [10] est un système de fichiers distribué pour réseau mobile ad hoc Dans Haddock FS, un terminal hébergeant une donnée est appelé gestionnaire de réplique (replica manager ). La politique de réplication n’est pas présentée, on suppose qu’elle est faite à la demande. 

Cohérence

Haddock FS propose un protocole de cohérence hybride. Au sein d’un groupe fortement connecté, HaddockFS met tout d’abord en place un protocole de cohérence pessimiste basé sur un algorithme d’exclusion mutuelle à jeton. La détection d’un groupe fortement connecté et la mise en place de l’exclusion mutuelle n’est pas décrite. Entre les groupes, la cohérence optimiste est mise en place en journalisant les modifications. Celles ci sont triées par ordre causal. Dans son journal, chaque gestionnaire de réplique stocke donc des mises à jour, ainsi que la version stable de la donnée, c’est à dire la dernière version sur laquelle il sait que tous les gestionnaires de répliques se sont accordés. Les mises à jour plus anciennes que la version stable sont appelés mise-à-jour stable (stable update), celles plus récentes sont appelées mises à jour provisoires tentative update  La réconciliation est faire entre couple de gestionnaires de réplique, dès que ceux ci sont en contact. Cette réconciliation vise à construire une liste de mises à jour totalement ordonnée suivant l’ordre causal (un ordre partiel). Quand il y a plusieurs modifications en parallèle, une seule sera donc choisie. Avec une granularité de l’ordre du fichier, c’est un choix très contraignant, puisque cela empêche la modification concurrente des fichiers, même dans des cas où un algorithme tel que diff-3[53], capable de construire la différence minimale entre deux chaînes de caractères ayant un ancêtre commun, ne détecterait pas de conflit. Pour obtenir une version stable, chaque donnée a une copie primaire, la première version à avoir été créée. C’est cette version qui décide au final en cas de conflit, et qui est autorisée à créer des versions stables. Le statut de copie primaire peut être transféré, mais crée un point de centralisation.

Stockage et mise à jour

Figure 4.2 – Stockage des chunks, extrait de [10] Haddock FS cherche à limiter l’occupation mémoire. Il faut donc réduire la taille des journaux de mises à jour stockés en mémoire, et la taille de la mise à jour elle-même échangée entre deux pairs. Pour diminuer la taille des échanges, Haddock FS utilise la fonction de hash SHA-1. Celle ci prend en entrée une chaîne de caractères et retourne une chaîne de caractères statistiquement unique, et de plus petite taille. Chaque donnée est tout d’abord découpée en morceaux, appelés chunk(morceau), comme dans 4.2. Un pair indexe ensuite les données qu’il héberge par leur valeur hachée . Quand la donnée est modifiée, un nouveau chunk est créé et inséré dans la liste de chunk existants. Au moment de la propagation des modifications, les valeurs hachées sont tout d’abord échangées afin de vérifier s’il est nécessaire de propager la modification elle-même. Pour limiter la place prise par la journalisation des modifications, Haddock FS élimine d’abord les mises à jour antérieures à la version stable de la donnée (obtenu grâce à la copie primaire), et pour lesquelles il est certain que tous les pairs ont appliqués ces mises à jour. Le choix d’éliminer des mises à jour n’ayant pas encore abouti à une version stable est laissé à l’utilisateur et dans ce cas les mises à jour les plus anciennes sont éliminées, car ce sont celles qui ont le plus de chance d’avoir déjà été propagées.