Problématiques liées au partage de données dans les MANets

Réplication

Dans le cadre d’un système distribué, un site est susceptible d’accéder à des données stockées sur un site distant. Comme nous l’avons dit plus haut, nous définissons la disponibilité d’une donnée comme la capacité pour un terminal d’accéder à cette donnée en un temps borné. La réplication de données vise à augmenter la disponibilité en créant plusieurs copies (répliques), placées sur différents sites. La création de répliques a un impact sur le trafic réseau : – créer une réplique permet de ne pas avoir à transmettre la donnée à chaque lecture. – cependant, si cette donnée est modifiable, la création d’une réplique engendre un trafic nécessaire pour maintenir la cohérence entre les différentes copies de la donnée. Par ailleurs, une réplique utilise de l’espace-mémoire. Selon les caractéristiques du système, tel le coût de l’envoi d’un message, ou l’espace-mémoire disponible, on cherche donc à atteindre un juste milieu entre trafic engendré d’une part et rapidité d’accès et tolérance aux fautes d’autre part. Dans un système sujet aux pannes, on utilise aussi la réplication de données pour prévenir la disparition des données. La réplication est donc utilisée dans la plupart des types de systèmes distribués (mémoire partagée distribuée, cache, système de fichiers distribué, base de données) afin d’en améliorer les performances et d’en augmenter la tolérance aux fautes. L’espace de stockage des sites peut être limité. Il est donc nécessaire de répliquer en priorité les données utiles sur le site. Par ailleurs, quand on cherche à répliquer une donnée, mais que le cache est plein, un algorithme de remplacement détermine quelle réplique éliminer si cela nécessaire. 

 Schéma de réplication

Un schéma de réplication décrit sur quels critères une donnée doit être répliquée. Les schémas classiques sont les suivants : – Copie fixe : il n’existe qu’une seule copie de la donnée dans tout le réseau. Elle est placée sur un terminal déterminé. Cette politique permet d’éviter le surcoût nécessaire pour maintenir les différentes répliques cohérentes. Cependant, elle n’améliore en rien l’accessibilité ou la tolérance aux pannes. Cette technique est utilisée dans les systèmes de fichiers réseaux, ou les bases de données. – Migration : il n’existe qu’une copie de la donnée dans le réseau. Quand un terminal doit accéder à la copie, il en fait la demande. Quand un terminal transmet la donnée, il détruit sa copie. – Réplication totale (mirroring) : les données sont répliquées sur tous les terminaux. Cette technique est coûteuse en espace-mémoire, et si les données sont modifiables, coûteuse en messages. Cependant, une donnée ne peut pas disparaître et est disponible immédiatement pour chaque terminal. Elle est utilisée dans certains systèmes de gestion de base de données comme SQL Server ou Oracle – Réplication à la demande : une réplique d’une donnée est créée sur un terminal la première fois que celui ci tente d’y accéder. Dans les systèmes filaires, c’est la politique la plus couramment utilisée. Il existe d’autres techniques de réplication à la demande partielle prenant en compte des paramètres plus complexes. La réplication peut, par exemple, être basée sur les fréquences d’accès : un terminal réplique une donnée s’il l’utilise fréquemment. Le terminal peut aussi prendre en compte le comportement de ses voisins dans sa décision de répliquer. Il existe aussi des schémas de réplication proactifs utilisant des informations sémantiques sur les données et sur l’utilisateur [8] [28]. Elles visent à répliquer la donnée avant que l’utilisateur n’y accède en prédisant ses accès futurs. Par ailleurs, dans les MANets, le problème de réplication est souvent abordé de manière collaborative : un groupe de terminaux proches décide collaborativement des données qui seront répliquées, afin de maximiser la diversité des données dans le groupe.

Remplacement de cache

L’espace de stockage d’un terminal étant limité, il arrive que pour répliquer localement une donnée, il soit nécessaire d’éliminer une réplique existante. Les algorithmes de remplacement visent à déterminer quelles sont les données à éliminer. Les algorithmes utilisés sont, pour certains, identiques à ceux proposés pour la gestion de caches physiques, comme décrit dans [99]. Ils sont donc simples à mettre en œuvre et nécessitent peu de calcul. Tous ces algorithmes ne sont pas nécessairement adaptés aux caches logiciels distribués. Dans les systèmes distribués, les algorithmes issus de la gestion de cache-mémoire principalement utilisés sont : – LRU (least recently used) : on élimine la donnée qui n’a pas été utilisée depuis le plus longtemps. – LFU (least frequently used) : on élimine la donnée la moins fréquemment utilisée. Cependant, d’autres critères sont pris en compte dans des caches logiciels distribués : 39 – la difficulté d’accès à une donnée : on préfère ne pas éliminer une donnée difficile à obtenir, si, par exemple la réplique, la plus proche est éloignée. – la taille : quand on élimine une donnée de petite taille, il est probable qu’il faille éliminer rapidement une autre donnée, alors que quand on élimine une donnée de taille importante, on libère plus d’espace. Dans un système de réplication collaboratif où la création d’une réplique prend en compte l’intérêt non pas du seul utilisateur, mais du groupe, le remplacement de cache doit lui aussi être collaboratif. Nous avons vu sur quels critères une donnée pouvait être mise en cache, ou éliminée du cache. Il est maintenant nécessaire de définir dans quelle mesure les différentes répliques sont maintenues identiques. C’est le problème de la cohérence qui est examiné dans la partie suivante. 

Cohérence

Dans le cadre d’un système de partage de données distribué, on réplique les données afin d’améliorer leur disponibilité. Il est alors nécessaire de maintenir cohérentes les différentes copies d’une donnée. Un modèle de cohérence de mémoire définit quelles sont les garanties sur l’ordre des accès aux données qu’un programmeur obtient du système. Il est à noter que les anglophones distinguent les termes consistency et coherency : Consistency décrit l’état de l’intégralité de la mémoire. Coherency décrit l’état d’une unité de granularité de la mémoire. Cette distinction n’est pas faite en français. On notera aussi que de nombreux travaux ne différencient pas réplication et cohérence. Dans [32], par exemple, Gray parle de Lazy Replication et Eager Replication pour distinguer deux modes de mises à jour des données distribuées. Dans les systèmes ne faisant pas cette distinction, les données sont généralement totalement répliquées ou répliquées à la demande. Nous allons voir ici les différents modèles de cohérence existant dans la littérature [75]. Nous verrons ensuite quels problèmes posent ces modèles, et les algorithmes proposés pour les résoudre. 

Modèles

Il existe plusieurs types de modèles de cohérence, pour la plupart décrits dans [75]. Nous allons d’abord voir des modèles de cohérence (consistency) définis pour des mémoires partagées distribuées. Nous verrons ensuite les modèles de cohérence (coherency), définis pour des systèmes à plus gros grain. Dans un modèle de cohérence sans synchronisation, la mémoire est maintenue cohérente par le système sans intervention du programmeur. Dans un modèle de cohérence avec synchronisation, les opérations de synchronisation des vues de l’espace partagé sont explicitement appelées par le programmeur.

Modèles sans synchronisation

Il existe différents modèles de cohérence sans synchronisation qui définissent un ordre valide sur les événements dans un système. 40 3. Problématiques liées au partage de données dans les MANets Dans un modèle de cohérence atomique, ou cohérence stricte, tous les processeurs voient les événements dans leur ordre d’apparition. Les événements sont donc strictement ordonnés selon l’ordre temporel. Dans un modèle de cohérence séquentielle, tous les processeurs voient les événements dans le même ordre [72]. Les événements sont strictement ordonnés, mais pas nécessairement selon l’ordre temporel. L’ordre d’exécution sur un processeur donné est respecté. Dans un modèle de cohérence causale, tous les processeurs voient les événements causalement liés dans le même ordre [73]. Les événements indépendants peuvent être vus dans des ordres différents par deux processeurs. Les événements sont donc ordonnés selon un ordre causal partiel. Dans un modèle de cohérence processeur (appelé aussi PRAM ou FIFO), tous les événements générés par un processeur sont vus dans le même ordre par tous les processeurs. Dans un modèle de cohérence ∆, on garantit que si une donnée est modifiée à l’instant t, tous les processeurs verront cette modification à l’instant t + ∆. Dans un modèle de cohérence à terme, on garantit uniquement que les opérations d’écriture seront à terme propagées à tous les processeurs. Hormis la cohérence à terme et ∆, les autres modèles de cohérence demandent la mise en œuvre par le système d’une synchronisation lourde qui n’est pas visible par l’utilisateur mais peuvent offrir plus que ce qui est requis par l’utilisateur. Des modèles avec une synchronisation explicitée par le développeur, qui ne devraient donc utiliser que le nombre minimum de points de synchronisation nécessaires, ont donc été proposés.