Infrastructure P2P pour la Réplication et la Réconciliation des Données

Réplication Synchrone et Asynchrone

   Dans les systèmes de bases de données répartis, l’accès aux données se fait via des transactions. Une transaction, prend un état d’une base de données, effectue une ou des actions et génère un autre état de la base. Ces actions sont essentiellement des opérations de lecture ou d’écriture de données suivies par une validation (commit). Si une transaction ne se termine pas avec succès, on dit qu’elle échoue. Une transaction qui met à jour une donnée doit être propagée à tous les sites qui contiennent des répliques de cette donnée afin de garder ses répliques cohérentes. Nous distinguons deux techniques de réplication de mise à jour: réplication synchrone et réplication asynchrone. Dans ce qui suit, nous discutons ces deux techniques. La réplication synchrone (eager) : c’est un mode de distribution dans lequel toutes les sous-opérations locales effectuées suite à une mise à jour globale sont accomplies pour le compte de la même transaction. Cette technique est très utile lorsque les mises à jour effectuées sur un site doivent être prises en compte immédiatement dans les autres sites, comme le montre la Figure 3. L’avantage incontestable de la mise à jour synchrone est de fournir la dernière version des données (cohérence mutuelle) quelle que soit la copie accédée. Cela demande néanmoins, une gestion des transactions multisite coûteuse en ressources et des algorithmes de contrôle de concurrence complexes. Pour cette raison, la mise à jour asynchrone est le plus souvent préférée. La réplication asynchrone (lazy) : dans cette approche, les mises à jour sont propagées après la fin de la transaction (après le commit). En effet, la première transaction valide (commits) le plus tôt possible, et ensuite les mises à jour sont propagées à l’ensemble des répliques, comme le montre la Figure 4. Les solutions de réplication asynchrone peuvent être classées comme optimiste ou non-optimiste [PD02] selon leurs hypothèses concernant les mises à jour conflictuelles. En général, la réplication asynchrone optimisme repose sur l’hypothèse optimiste que les mises à jour des conflits se produisent que rarement, voire pas du tout. Les mises à jour sont donc propagées à l’arrière-plan, et les conflits sont réconciliés après avoir eu lieu. En revanche, la réplication asynchrone non-optimiste suppose que les mises à jour conflictuelles sont susceptibles de se produire et met en œuvre des mécanismes de propagation qui empêchent les mises à jour conflictuelles.

Transformée Opérationnelle (OT)

   Le modèle des transformées opérationnelles (OT) [MOSM+03, Ophd05] a été développé par la communauté des éditeurs collaboratifs synchrones. La préservation de l’intention est au centre de la définition du modèle de cohérence de cette approche. L’architecture générale du modèle des transformées opérationnelle distingue deux composants :
• Un algorithme d’intégration. Il est responsable de la réception, de la diffusion et de l’exécution des opérations. Si nécessaire, il fait appel aux fonctions de transformation. Cet algorithme est indépendant du type des données manipulées (chaîne de caractères, document XML, système de fichiers).
• Un ensemble de fonctions de transformation. Ces fonctions ont la charge de « fusionner » les mises à jour en sérialisant deux opérations concurrentes. Ces fonctions sont spécifiques à un type de données particulier. Le modèle OT considère n sites. Chaque site possède une copie des objets partagés. Quand un objet est modifié sur un site, l’opération correspondante est exécutée immédiatement sur ce site, puis diffusée aux autres sites pour y être également exécutée. Autrement dit, une opération est traitée en quatre étapes:
• Génération sur un site.
• Diffusion aux autres sites.
• Réception par les autres sites.
• Exécution sur ces autres sites.
Lorsqu’une opération est reçue, son contexte d’exécution peut être différent de celui dans lequel elle a été générée. Dans ce cas, l’intégration de cette opération sur les autres sites peut conduire à des incohérences entre les différentes copies. Dans OT, les opérations reçues doivent être transformées par rapport aux opérations locales concurrentes avant d’être exécutées. Cette transformation est effectuée en utilisant des fonctions de transformation. L’algorithme d’intégration est défini comme correct s’il assure la Causalité, la Convergence et la préservation des Intentions (CCI) [SCF97, SZJY97, SE98] :
• Respect de la causalité : Pour certaines opérations, il existe une relation de précédence causale qui doit être maintenue. On dit que l’opération op1 précède l’opération op2 (noté op1 -> op2) si et seulement si op2 a été générée et exécutée sur une réplique après l’exécution de op1 sur cette même réplique. Puisque op2 a été générée après op1, elle tient compte implicitement de ces effets. Le respect de la causalité garantit que pour les opérations pour lesquelles il existe une relation de causalité, celles-ci seront exécutées dans le même ordre sur toutes les répliques.
• Préservation de l’intention : Deux opérations op1 et op2 qui ne sont pas liées par une relation de précédence sont concurrentes. De ce fait, ces deux opérations peuvent être exécutées sur les différentes répliques dans un ordre quelconque. Cependant, si on exécute l’opération op1 avant l’opération op2 alors il faudra lors de l’exécution d’op2 tenir compte des effets d’op1 de façon à respecter les effets d’op2.
• Convergence des répliques : Lorsque tous les sites ont exécuté les mêmes opérations, les répliques doivent être identiques. Cependant, le fait de respecter les relations de causalité entre les opérations et de préserver les effets des opérations ne suffit pas pour garantir la convergence des répliques. La Figure 6, montre un exemple de scénario où les deux critères sont respectés sans les copies convergent.

Le passage à l’échelle

   L’absence de coordination globale entre les pairs se répercute directement sur le passage à l’échelle des applications P2P. Les architectures P2P se présentent actuellement comme une solution viable pour permettre le passage à l’échelle de ses applications. Par exemple, les applications P2P de partage de fichiers comptent un très grand nombre de participants et fonctionnent sans problème. D’après une étude menée en 2001 [SGG02], OceanStore [KBCC+ 00] qui est une application P2P de stockage de fichiers, permet de gérer 1010 utilisateurs stockant au total plus de 1014 fichiers.

Insertion, départ et maintenance

   L’insertion d’un nouveau nœud dans une communauté se fait par la simple recherche de son suivant dans l’anneau. C’est ensuite le processus de maintenance qui, exécuté régulièrement, va prendre en charge le maintien de la cohérence des tables de routage des pairs concernés par l’arrivée du nouvel élément. En effet, à intervalles réguliers chaque nœud vérifie la validité des informations détenues dans sa table de routage à savoir: son suivant et les fingers. La vérification de son suivant s’effectue en lui demandant son précédent. Si la réponse est soi-même, le suivant est correct. Si le résultat est l’identifiant d’un nœud situé entre soi et son suivant, il devient alors le nouveau suivant, et est notifié que le nœud courant est le nouveau précédent. La vérification des fingers est similaire à la construction de la table et consiste à rechercher pour chaque entrée le nœud correspondant d’identifiant suivant (n + 2i−1), avec 1 ≤ i ≤ m. La table est mise à jour si jamais un pair différent des pairs actuels est trouvé. Par le biais de ces vérifications régulières, Chord garantit le maintien de la cohérence de l’anneau.Dans le cas d’un départ de nœud, c’est le processus de maintenance qui permet la mise à jour des informations maintenues par les pairs. En outre, afin de limiter les échecs de requêtes survenant dans l’intervalle de temps situé entre la disparition d’un nœud et l’exécution de ce processus, chaque nœud maintient une liste de suivants, qui peuvent être utilisés alternativement au suivant défaillant.

Le Protocole Chord. Chord [SMKK+01]

   est un protocole de recherche P2P pour les applications Internet : pour une clé donnée, Chord y associe un pair. Chord est déployé dans plusieurs applications: tout d’abord, dans CFS (Collaborative File System) [DKKM+01] qui est un système de fichiers distribué à l’échelle de l’Internet, ensuite dans ConChord [ACMR02] qui utilise CFS afin de fournir une infrastructure distribuée pour la délivrance de certificats de sécurité et enfin dans DDNS [CMM02] qui propose une implantation P2P du DNS (Domain name Service). La DHT Chord [SMKK+ 01] repose sur une topologie en anneau et utilise donc une notion de successeurs et de prédécesseurs dont elle garde trace dans sa table de routage à m entrées. Donc tout utilisateur peut contacter directement m nœuds du réseau pour transmettre ses requêtes. Une fonction de hachage régulière génère un identifiant pour chaque pair à partir de son adresse IP. Ensuite, chaque pair est placé dans l’anneau de manière à ordonner les identifiants par ordre croissant. Ainsi, chaque pair d’identifiant n est responsable de l’intervalle de clés [precedent(n), n].

Table des matières

TABLE DES FIGURES
LISTE DES TABLEAUX
I INTRODUCTION
1 CONTEXTE
2 PROBLEMATIQUE
3 RESUME DES CONTRIBUTIONS
4 ORGANISATION DU DOCUMENT
II ETAT DE L’ART
1 REPLICATION DES DONNEES
1.1 Les bases de données distribuées et répliquées
1.2 Mécanismes de la réplication
1.2.1 Réplication simple-maître (single master)
1.2.2 Réplication multi-maître (multi master)
1.2.3 Réplication Synchrone et Asynchrone
2 REPLICATION DANS LES SYSTEMES DISTRIBUES
2.1 Paxos : exemple d’un protocole de consensus
2.2 Réalisation d’un consensus dans les systèmes asynchrones
3 REPLICATION OPTIMISTE ET DIVERGENCE
3.1 Réconciliation
3.1.1 CVS
3.1.2 IceCube
3.1.3 Bayou
3.1.4 Transformée Opérationnelle (OT)
3.1.5 So6
3.1.6 Google Wave
3.2 Synthèse Générale
4 LES SYSTEMES P2P
4.1 Caractéristiques
4.1.1 Le passage à l’échelle
4.1.2 La tolérance aux fautes
4.1.3 La dynamicité
4.1.4 L’auto-organisation
4.1.5 Un réseau virtuel
4.2 Types de réseaux P2P
4.2.1 Les réseaux non-structurés
4.2.2 Les réseaux structurés
4.2.3 Réseau super-pair
4.2.4 Synthèse générale
4.3 Solutions de réplication dans les réseaux P2P
4.3.1 Freenet
4.3.2 OceanStore
4.3.3 Ivy
4.3.4 P-Grid
4.3.5 WOOT
4.3.6 Logoot
4.3.7 DSR-P2P
4.3.8 Telex
4.3.9 Scalaris
4.3.10 MOT2
4.3.11 KTS
4.3.12 Synthèse générale
5 CONCLUSION
III P2P-LTR: MODELE ET ALGORITHMES
1 DEFINITION DU PROBLEME ET SOLUTION GENERALE
1.1 Définition du problème
1.2 Solution générale
2 MODELE DU P2P-LTR
2.1 Description
2.2 Opérations
2.3 Algorithmes
2.4 Cohérence à terme
2.5 Exemple
3 GESTION DU COMPORTEMENT DYNAMIQUE DES PAIRS
3.1 Arrivée et départ du Master-key
3.1.1 Arrivée d’un nouveau Master-key
3.1.2 Départ du Master-key
3.2 Tolérance aux fautes
3.2.1 Gestion de la défaillance du Master-key
3.2.2 Gestion de la défaillance simultanée du Master-key et Master-key Succ
3.3 Propriété de vivacité
4 ANALYSE DES COUTS
4.1 Complexité de la communication pour publier un patch
4.2 Complexité de la communication pour la convergence
4.3 Latence pour publier un patch
4.4 Latence pour la convergence
4.5 Synthèse
5 ANALYSE PROBABILISTE
6 COMPARAISON AVEC LES APPROCHES EXISTANTES
7 CONCLUSION
IV EVALUATION DE PERFORMANCES
1 ENVIRONNEMENT DE SIMULATION
2 RESULTATS
2.1 Passage à l’échelle
2.2 L’effet du nombre de répliques sur le temps de réponse
2.3 L’effet de la fréquence des mise à jour sur le temps de réponse
2.4 L’effet des pannes sur la continuité des estampilles
3 CONCLUSION
V MISE EN ŒUVRE ET VALIDATION
1 XWIKI: UN WIKI FONCTIONNANT SUR UN RESEAU P2P
2 ARCHITECTURE XWIKI P2P
2.1 Description des composants
2.1.1 PatchManager
2.1.2 ReconcileManager
2.1.3 P2P-LTR
2.2 Interface des composants
2.2.1 IPatchManager
2.2.2 IReconcileManager
2.2.3 IP2P-LTR
2.3 Implémentation des composants
2.3.1 Implémentation de PatchManager
2.3.2 Implémentation de ReconcileManager
2.3.3 Implémentation de P2P-LTR
3 DEPLOIEMENT
3.1 Déploiement de la DHT + P2P-LTR
3.2 Déploiement des serveurs XWiki avec PatchManager
3.3 Déploiement des composants ReconcileManager
3.4 Connexion de ReconcileManager avec un composant PatchManager
3.5 Connexion des ReconcileManager avec les composants P2P-LTR
3.6 Démarrage des composants ReconcileManager et P2P-LTR
4 CONCLUSION
VI BILAN ET PERSPECTIVES
1 CONTRIBUTIONS
1.1 P2P-LTR
1.2 XWiki: un Wiki P2P
2 TRAVAUX FUTURS
2.1 Authentification et contrôle d’accès aux ressources
2.2 Un Wiki sémantique sur un réseau P2P
2.3 Amélioration de XWiki
2.4 Le Cloud : compromis entre cohérence et disponibilité
ANNEXES
BIBLIOGRAPHY

Télécharger le rapport complet