République Algérienne Démocratique et Populaire
Ministère de l’Enseignement Superieur et de la Recherche
Scientifique
UNIVERSITÉ D’EL-OUED
FACULTÉ DES SCIENCES ET DE TECHNOLOGIE
Mémoire de fin d’étude
MASTER ACADEMIQUE
Domaine: Mathématiques et Informatique
Filière: Informatique
Spécialité: Système Distribué et Intelligence Artificiel
Présenté par: Lekhouimes Ahmed
Thème
Algorithme de réplication multimaitre pour la gestion de
cohérence dans une grappe de base de données
Soutenu le : 25 juin 2014
Devant le jury composé de:
Mr. Meklid Abdessalem MA (B) Univ. El Oued Président
Mr. Gharbi Kadour MA (B) Univ. ElOued Examinateur
Mr. Khelaifa Abdennacer MA (A) Univ. ElOued Encadreur
Année universitaire 2013 – 2014
N° d’ordre :
N° de série :
Dédicace
A mes très chers parents, en témoignage et en
gratitude de leurs dévouement et leur soutien
permanent durant toutes mes années d’études leurs
sacrifices illimités, leur réconfort moral et tous
les efforts qu’ils sont consentis pour mon éducation
pour me voir réussir un jour.
Que Dieu les garde.
A tous mes frères.
A toutes mes sœurs.
A tous mes amis.
Lekhouimes Ahmed
Remerciements
Je remercie Allah le tout puissant, qui m’a donné la force et la
patience pour l’accomplissement de ce travail.
J’dresse me vifs remerciements à mon encadreur Mr kaleifa
A.annacer qui m’a aidé tout la durée de mon travail et par
patience et les précieux conseils dont il m’a entouré.
J’adresse également mon remerciement, à tous mes
enseignants pour leurs aides inestimables. On remercie tous
qui ont participé de près ou de à élaborer ce travail.
Enfin. Pour finir et êtres sûre de j’oublier personne, je remercie
tout le monde.
Résumé
La haute performance et la haute disponibilité des bases de données ont été
traditionnellement gérées grâce aux systèmes de bases de données parallèles,
implémentés sur des multiprocesseurs fortement couplés. Le traitement parallèle
des données est alors obtenu en répliquant les données à travers les nœuds du
multiprocesseur afin de diviser les temps de traitement. Cette solution requiert
un Système de Gestion de Base de Données (SGBD) ayant un contrôle total sur
les données. Bien qu’efficace, cette solution s’avère très coûteuse en termes de
logiciels et de matériels. De nos jours, les grappes d’ordinateurs personnels (PC)
fournissent une alternative aux multiprocesseurs fortement couplés, Les grappes
sont composées d’un ensemble de serveurs (PC) interconnectés entre eux par un
réseau. Ils permettent de répondre aux problématiques de haute performance et
de haute disponibilité.
Ce travail a pour but de construire un algorithme de réplication performent
pour la gestion de cohérence dans une grappe de PC de petite taille destinée aux
applications de flux moyenne de données.
Mots-clés : réplication de base de données, grappe de PCs, réplication
multimaitre, réplication partielle, réplication asynchrone.
Abstract :
High performance and high availability of databases have traditionally been
managed through parallel database systems that are implemented on strongly
coupled multiprocessors. The parallel data processing is then obtained by
replicating the data across nodes in the multiprocessor to divide the processing
time. This solution requires a Database Management System (DBMS) with total
control over the data. Although effective, this solution is very costly in terms of
software and material. Today, clusters of personal computers (PC) provide an
alternative to highly coupled multiprocessors, clusters are composed of a set of
servers (PC) interconnected together by a network. They allow you to respond to
problematic high performance and high availability.
This work aims to propose a efficient algorithm of replication to manage
consistency in a cluster of small PC destined to applications of average data
stream.
Key words : database replication, cluster of PCs, multimaster replication,
partial replication, asynchronous replication.
Table matière
Introduction générale
1. Introduction………………………………………………………………………... 1
2. Problématique……………………………………………………………………… 2
3. Organisation de thèse………………………………………………………...……. 2
Chapitre 1 : LA réplication dans les grappes de base données une vue générale
1. Introduction………………………………………………………………………... 4
2. Réplication de base de données…………………………………………………… 4
2.1. Définition……………………………………………………………………... 4
2.2. Transactions et propriétés ACID……………………………………………… 5
2.3. Techniques de réplication…………………………………………………….... 6
2.3.1. Selon le mode de réplication…………………………………………….. 7
2.3.2. Selon le placement des données………………………………………… 7
2.3.3. Selon le rôle des nœuds…….…………………………………………………. 8
2.3.4. stratégie de propagation des mises à jour………………………………... 10
3. Les grappes de bases de données…………………………………………………... 13
3.1. Définition…………………………………………………………………….... 13
3.2. Les choix d’architectures en grappe…………………………………………… 14
3.3. Transparence de la grappe de bases de données…………………….……….... 15
4. La réplication dans les grappes…………………………………………………….. 16
4.1. Graphe Dirigé Acyclique……………………………………………………… 16
4.2. Diffusion optimiste…………………………………………………………….. 17
4.3. Utilisation du délai réseau……………………………………………………... 21
5. Conclusion…………………………………………………………………………. 23
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
1. Introduction………………………………………………………………………... 24
2. Présentation générale du système………………………………………………….. 24
2.1.Architecture globale en cinq couches…………………………………………... 24
2.2.Contenue d’un nœud…………………………………………………………..... 25
2.3.Processus de soumission des requêtes………………………………………….. 26
2.4.Exemple de routage…………………………………………………………….. 26
3. Algorithme de réplication asynchrone pessimiste…………………………………. 28
3.1.Introduction……………………………………………………………………... 28
3.2.Principe de l’algorithme………………………………………………………... 28
3.3.Architecture pour le module Gestionnaire de réplication………………………. 28
3.4. Algorithmes……………………………………………………………………. 31
- Module Propagator……………………………………………………………… 31
- Module Receiver………………………………………………………………… 31
- Module Refresher……………………………………………………………….. 32
- Module Deliver………………………………………………………………….. 33
4. Conclusion…………………………………………………………………………. 34 Chapitre 03 : Adaptation et optimisation de l’algorithme
1. Introduction………………………………………………………………………... 35
2. Caractéristiques et l’architecture de nouvel environnement…………………....... 35
3. Cycle de vie de requête ……………………………………………………………. 36
4. Architecture modifiée pour le module Gestionnaire de réplication……………….. 37
5. Optimisation de l’algorithme pessimiste…………………………………………... 37
5.1. Principe………………………………………………………………………… 38
5.2. Exemple………………………………………………………………………... 39
5.3. Algorithmes……………………………………………………………………. 39
5.3.1. Réception de transactions………………………………………………... 39
5.3.2. Soumission des requêtes ………………………………………………... 40
5.3.3. Propagation des transactions…………………………………………….. 41
6. Preuve……………………………………………………………………………… 41
7. Conclusion…………………………………………………………………………. 42
Chapitre 4 : Mise en œuvre et validation
1. Introduction……………………………………………………………………… 43
2. L’environnement à implémenter………………………………………………… 43
3. Les outils d’implémentation…………………………………………………….. 43
3.1. Le langage java…………………...…...…………………………………….. 43
3.1.1. Java et multithreading…………………………………………………… 43
3.1.2. Threads, variables partagés et synchronisation 43
3.1.3. Les sockets en java et la communication par échange de messages…….. 44
3.2. Le SGBD Postgresql……………………………………………………….... 44
4. Les états de gestion de file d’exécution………………………………………… 45
4.1. Exemple d’exécution de deux requêtes ordonnées………………………….. 45
4.2. Exemple d’exécution de deux transactions non-ordonnées………………..... 46
4.3. Exemple d’exécution de requêtes de lecture………………………………... 48
5. Conclusion………………………………………………………………………. 49
Conclusion générale et perspectives
1. Conclusion………………………………………………………………………. 50
2. Quelques points entour de cette thèse…………………………………………… 50
3. Perspectives……………………………………………………………………... 51
Bibliographie……………………………………………………………………………. 52
Table de figures
FIG 1.1 - Modèle général à 5 phases………………………………………………….. 7
FIG 1.2 - réplication selon le placement de données………………………………....... 8
FIG 1.3.1 - achitecture de réplication monomaître……………..……………………... 9
FIG 1.3.2 - achitecture de réplication multimaître………………...………………….. 9
FIG 1.4 - grappe de PC………………………………………………………………. 13
FIG 2.1 - Architecture globale en cinq couches……………………………………….. 24
FIG 2.2 - Exemple de routage de requête…………….………………………………. 27
FIG 2.3 – Architecture détaillée pour le module Gestionnaire de réplication…………. 29
FIG 3.1 – Architecture de nouveau système…………………………………………... 35
FIG 3.2 - Architecture en couches modifié……………………………………………. 36
FIG 3.3 - Architecture modifiée pour le module gestionnaire de réplication…………. 37
FIG 4.1 – PostgreSQL…………………………………………………………………. 44
FIG 4.2 – modifier produit en poste 01………………………………………………... 45
FIG 4.3 – modifier produit en poste 02………………………………………………... 45
FIG 4.4 – file d’exécution ordonné (1) en poste 01…………………………………… 46
FIG 4.5 – file d’exécution ordonné en poste 02……………………………………….. 46
FIG 4.6 – file d’exécution ordonné(2) en poste 01……………………………………. 47
FIG 4.7 – file d’exécution non-ordonnée en poste 02…………………………………. 47
FIG 4.8 – file d’exécution de poste 01 après la validation de T1……………………… 48
FIG 4.9 – affichage de liste de produits……………………………………………….. 48
FIG 4.10 – liste de produits……………………………………………………………. 48
FIG 4.11 – file d’exécution de poste 01 après la transaction de lecture……………….. 49
Introduction
générale
Introduction générale
1
Introduction
De nos jours, les grappes d’ordinateurs personnels (PC) fournissent une
alternative aux multiprocesseurs fortement couplés. Le concept de grappe est né
en 1995 avec le projet Beowulf sponsorisé par la NASA. Un des buts initiaux du
projet était l’utilisation des ordinateurs massivement parallèles pour traiter les
larges quantités de données utilisées dans les sciences de la terre et de l’espace.
La première grappe a été construite pour adresser des problèmes liés aux
gigantesques volumes de données des calculs sismiques. Les raisons d’être des
grappes sont multiples :
La démocratisation des ordinateurs permet désormais l’utilisation de
nouveaux types de composants produits en masse ;
La disponibilité de sous-ensembles entièrement assemblés
(microprocesseurs, cartes mères, disques et cartes d’interface de réseau) ;
La concurrence des marchés grand-public qui a poussé les prix vers le bas
et la fiabilité vers le haut pour ces sous-ensembles ;
L’existence des logiciels libres, des compilateurs et des outils de
programmation parallèles ;
L’expérience accumulée par les chercheurs dans les algorithmes
parallèles;
Les progrès très significatifs dans le développement des protocoles
réseaux à hautes performances à base de composants standard ;
L’augmentation des besoins de calcul dans tous les domaines.
Ces nouvelles solutions permettent aux utilisateurs de bénéficier de plates-
formes fiables et très performantes à des prix relativement faibles : le rapport
prix / performance d’une grappe de PC est de 3 à 10 fois inférieur à celui des
supercalculateurs traditionnels. Les grappes sont composées d’un ensemble de
serveurs (PC) interconnectés entre eux par un réseau. Ils permettent de répondre
aux problématiques de haute performance et de haute disponibilité. Elles ont été
utilisées avec succès par exemple, les moteurs de recherches internet utilisant
des fermes de serveurs à grands volumes (e.g., Google).
Introduction générale
2
Problématique
Les applications dans lesquelles sont utilisées les grappes sont typiquement
des applications de lectures intensives, ce qui rend plus facile l’exploitation du
parallélisme, ou dans modèles économique tel que es Fournisseurs de Services
d’Applications (ASP - Application Service Providers).
Bien sûr l’environnement de notre algorithme a une charge moyenne de flux
de données mais la problématique commune est le coût le plus élevé de
supercalculateurs et d’autre part la nécessité de parallélisme pour augmenter la
performance et la disponibilité par l’équilibrage de charge sur plusieurs nœuds
dans une configuration multimaitre et ça qui apparait plus couteuse avec des
matériaux spéciaux(supercalculateurs).
A ces points l’objectif de ce projet est de construire un algorithme de
réplication asynchrone optimiste avec une configuration multimaitre partielle
adapté avec les grappes de taille et de charge moyenne.
Organisation de thèse
Le chapitre 01 présente une vue générale sur les deux, (i) la réplication de
base de données son techniques, critères de classification, et la gestion
cohérence, (ii) une vue générale sur les grappes de PC son caractéristiques, et
ensuite nous présentons la spécificité de réplication dans une grappe et
l’architecture supporté, et en fin nous présentons trois types d’algorithme de
réplication pour la gestion de cohérence dans une grappe.
Dans le deuxième chapitre nous définissons brièvement le projet présenté par
«Cédric COULON » au Laboratoire d’Informatique de Nantes Atlantique
(LINA) sous-titre de "Réplication Préventive dans une grappe de bases de
données " nous définissons le modèle en couche supporté, comment il assure
l’autonomie des nœuds des applications et de SGBD, plus de détails sur la
couche de réplication et un algorithme pour leur gestion.
Dans le troisième chapitre nous présentons nos modifications
(simplification) sur les deux (i) le système présenté dans le chapitre précédent
pour adapter et exploite bien les caractéristiques des grappes de charge et de flux
de données moyenne et des applications simples (entreprise) (ii) et une
optimisation de l’algorithme pour augmenter la performance.
Introduction générale
3
Dans le chapitre quatre nous présentons les moyenne et les outils pour la mise
en œuvre de notre algorithme et on illustre avec des exemples.
Chapitre 1
La réplication dans les grappes
de base des données,
une vue générale
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
4
1. Introduction
La réplication présentée comme une solution qui rende un gros système de
base de données plus disponible et performant, l’idée principale de réplication
consiste à maintenir plusieurs copies de données distribuées sur plusieurs
machines séparées, afin d’améliorer les deux, la disponibilité par la possibilité
d’accès aux autres réplicas si certains tombent en cas de panne, et la perfor-
mance par (i) l’accès aux plus proches nœuds (ii) réduire le temps de réponse
en utilisant le parallélisme et la répartition de charge entre diverse nœuds, mais
le défis est comment assurer la cohérence entre les réplicas en cas de mise à
jours.
2. Réplication de base de données
2.1 Définition
La réplication [01] est une techniques implémentée par plusieurs systèmes de
gestion de bases de données, afin d’augmenter la disponibilité des données et
d’améliorer la fiabilité du système. Typiquement, la technique de réplication
implique l’utilisation d’un SGBD distribué composé de plusieurs sites connectés
par le bais d’un réseau d’interconnexion. Chaque site héberge une copie
complète ou partielle de la collection de données globale. En outre, la réplication
met en œuvre les mécanismes nécessaires pour garantir la cohérence des copies.
Ainsi, Les modifications apportées à un site sont capturées et stockées
localement, avant d’être transmises et appliquées à chacun des sites participants
à la réplication.
La réplication est un mécanisme de choix pour offrir de la haute performance.
Avec la vulgarisation d’internet, de nombreuses applications sont utilisées à
l’échelle mondiale, avec éventuellement des millions d’utilisateurs. Une telle
application peut réduire le temps de réponse, en permettant un accès
concurrentiel de ces utilisateurs.
La réplication est une technologie spécifique des bases de données distribuées,
dont l’objectif est de partager les données parmi des sites multiples. Dans le
même cadre, on identifie aussi la technique de fragmentation (appelé aussi
partitionnement). Néanmoins, les bases de données répliquées et les bases de
données fragmentées représentent deux notions distinctes. En fait, Dans une
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
5
base de données fragmentée, les données sont disponibles dans plusieurs
emplacements, mais une relation, voire un tuple, particulier est hébergé à un
emplacement bien précis. Tandis que la réplication signifie que les mêmes
données sont disponibles dans plusieurs sites.
2.2 Transactions et propriétés ACID
Une transaction peut être considérée comme une unité de traitement cohérente
et fiable. Une transaction prend un état d’une base de données, effectue une ou
des actions sur elle et génère un autre état de celle-ci. Les actions effectuées sont
des opérations de lecture ou d’écriture sur les données de la base. Par
conséquent, une transaction peut être définie comme étant une séquence
d’opérations de lecture et d’écriture sur une base de données, qui termine en
étant soit validée soit abandonnée. Si la base de données est cohérente au début
de la transaction, alors elle doit rester cohérente à la fin de l’exécution de la
transaction bien que cette dernière peut s’exécuter de manière concurrente avec
d’autres ou qu’une panne survienne lors de son exécution.
Une base de données est dite cohérente si elle est correcte du point de vue de
l’utilisateur, c’est à dire qu’elle maintient les invariants de la base ou les
contraintes d’intégrité. La notion de cohérence recouvre plusieurs dimensions
comme décrit dans [02]. Du point de vue des demandes d’accès, il s’agit de
gérer l’exécution concurrente de plusieurs transactions sans que les mises à jour
d’une transaction ne soient visibles avant sa validation, on parle de cohérence
transactionnelle ou isolation. Du point de vue des données répliquées, il consiste
à garantir que toutes les copies d’une même donnée soient identiques, on parle
de cohérence mutuelle. La cohérence transactionnelle est assurée à travers
quatre propriétés, résumées sous le vocable ACID :
– Atomicité : toutes les opérations de la transaction sont exécutées ou aucune ne
l’est. C’est la loi du tout ou rien. L’atomicité peut être compromise par une
panne de programme, du système ou du matériel et plus généralement par tout
évènement susceptible d’interrompre la transaction.
– Cohérence : La cohérence signifie que la transaction doit être correcte du
point de vue de l’utilisateur, c’est-à-dire maintenir les invariants de la base ou
contraintes d’intégrité. Une transaction cohérente transforme une base de
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
6
données cohérente en une base de données cohérente. En cas de non succès,
l’état cohérent initial des données doit être restauré.
– Isolation : elle assure qu’une transaction voit toujours un état cohérent de la
base de données. Pour ce faire, les modifications effectuées par une transaction
ne peuvent être visibles aux transactions concurrentes qu’après leur validation.
En outre, une transaction a une opération marquant son début (begin transaction)
et une autre indiquant sa fin (end transaction). Si la transaction s’est bien
déroulée, la transaction est terminée par une validation (commit). Dans le cas
contraire, la transaction est annulée (rollback, abort).
– Durabilité : une fois que la transaction est validée, ses modifications sont
persistantes et ne peuvent être défaites. En cas de panne de disque, la durabilité
peut être compromise.
2.3 Techniques de réplication
La réplication a fait l’objet de plusieurs études dans le contexte des systèmes
distribués et aussi dans les bases de données répliquées. La motivation
principale est la disponibilité pour les systèmes distribués et la performance
(parallélisme) pour les bases de données. Dans [03], l’auteur présente la gestion
de la réplication suivant plusieurs dimensions. Pour des soucis de présentation,
nous regroupons les dimensions décrites dans [04] en trois concepts à savoir la
distribution ou placement des données, la configuration (rôle) des répliques et la
stratégie de propagation des mises à jour.
- Modèle fonctionnel général à cinq phases
On peut représenter un algorithme de réplication par un modèle fonctionnel qui
comprend cinq phases [05] comme le montre la Figure 1.1 :
Phase 1 (Requête) : le client soumet une transaction à un noeud.
Phase 2 (Coordination des serveurs) : les serveurs se coordonnent afin de
savoir qui doit exécuter la transaction (ordonnancement des transactions et
prises de verrou...).
Phase 3 (Exécution) : La transaction est exécutée sur les copies concernées.
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
7
Phase 4 (Agrégation) : Les nœuds se mettent d’accord sur le résultat de la
transaction (pour garantir l’atomicité).
Phase 5 (Réponse) : La réponse est renvoyée au client.
1. Selon le mode de réplication, les phases ne s’exécutent pas toutes dans cet
ordre, par exemple dans la réplication asynchrone, la phase d’agrégation
(phase 4) a lieu avant la phase de réponse au client (phase 5). Et parfois,
certaines phases ne se sont même pas nécessaires au bon déroulement de la
réplication.
FIG 1.1 Modèle général à 5 phases
2. Selon le placement des données : Les données peuvent être répliquées
partiellement ou totalement. La réplication totale stocke entièrement la base
de données sur chaque site. La réplication partielle nécessite une partition des
données en fragments. Chaque fragment est stocké par la suite sur plusieurs
nœuds. L’avantage de la réplication partielle est qu’elle permet de réduire de
manière significative les accès concurrents aux données. En outre, le coût de
la mise à jour des copies est moins important que dans le cas de la réplication
totale compte tenu de la, faible portion des données sollicitée par les
opérations de mises à jour.
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
8
Figure 1.2 : réplication selon le placement de données
3. Selon le rôle des nœuds (mono-maître /multi- maître) :
Les mises à jour peuvent être effectuées sur une seule réplique (appelée
maître) avant d’être propagées vers les autres (esclaves). Une telle configuration
est appelée mono-maître (primary copy) car les autres répliques ne sont utilisées
que pour les requêtes de lecture seule, ce qui améliore les performances des
opérations de lecture seule. L’avantage d’une telle approche est qu’elle facilite
la gestion de la cohérence globale du système (cohérence mutuelle) puisque
toutes les mises à jour sont effectuées sur une seule copie.
Cependant, cet avantage est contradictoire avec le passage à l’échelle et avec
la disponibilité qui nécessitent que plusieurs copies soient utilisées en même
temps pour faire face à une charge applicative d’écritures très importante et
variable. Une approche multimaitre (update everywhere), dans laquelle les mises
à jour peuvent être exécutées sur n’importe quelle réplique, permet d’améliorer
aussi bien les performances des transactions de lecture seule que d’écriture.
L’inconvénient de cette approche est qu’elle requiert des mécanismes de
contrôle de concurrence distribués plus complexes pour garantir la cohérence
mutuelle. La configuration mono-maître profite plus aux applications de type
OLAP avec lesquelles les données de production (sujettes à des modifications)
doivent être séparées des données d’analyse (milliers d’opérations de lecture
seule). Par contre les applications OLTP tirent plus de bénéfices de l’approche
multimaitre et particulièrement quand le nombre de mises à jour est très
R1, S1
R2 , S2 R3 , S3
Site 01
Site 03 Site 02
Réplication totale
R1, S1
S2 R3
Site 01
Site 03 Site 02
Réplication partielle
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
9
important et provient de diverses sources (utilisateurs). Il existe beaucoup de
produits commerciaux qui offrent des solutions de réplication mono-maître ou
multimaitre.
Pour les architectures mono-maître, nous pouvons citer de manière non-
exhaustive Microsoft SQL Server replication, Oracle Streams, Sybase
replication Server, MySQL replication, IBM DB2 DataPropagator, GoldenGate
TDM platform, et Veritas Volume Replicator. Alors que les exemples de
solutions multi-maître incluent Continuent uni/Cluster, Xkoto Gridscale, MySql
Cluster, DB2 Integrated Cluster.
Site 4
esclave
Site 3
esclave
Site 2
esclave
Site 1
maître
Client
FIG 1.3.1:achitecture de réplication monomaître
Client
Site 1
Site 3
Site 2
FIG 1.3.2: achitecture de réplication multimaître
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
10
4. stratégie de propagation des mises à jour
Le dernier critère de classification permet de définir le moment où sont
rafraîchies les copies ("quand ?"). Elles peuvent être faites dans la transaction
originale (synchrone) ou en dehors (asynchrone).
Synchrone. Les mises à jour sont effectuées en une seule transaction. Il y a une
coordination forte entre les noeuds (tous valident la transaction ou aucun). La
réponse au client est renvoyée après que les serveurs se soient coordonnés.
Comme dans un système centralisé, avant d’accéder à une donnée, on
acquiert un verrou exclusif dessus. Avec le protocole ROWA (Read One Write
All) [06], on améliore la disponibilité des lectures en ne demandant le verrou
que sur une copie pour les lectures et sur toutes les copies pour les écritures. Par
la suite, le protocole est adapté aux pannes avec sa variante ROWA-A (Read
OneWrite All Available) [07, 08] où seules les copies disponibles sont mises à
jour. Dès qu’une copie redevient disponible, elle doit d’abord être synchronisée
avant d’être de nouveau utilisable.
D’autres protocoles synchrones comme le protocole NOn-Disjoint conflict
classes and Optimistic multicast (NODO) [09,10] se basent sur la division des
données en classes de conflits. On détermine ainsi que deux transactions
accédant à la même classe de conflit ont une grande probabilité de conflit. À
l’inverse, deux transactions qui n’accèdent pas aux mêmes classes peuvent
s’exécuter en parallèle. Les classes de conflits doivent être connues à l’avance et
chaque classe de conflit a un seul noeud maître. Pour exécuter une transaction,
le protocole diffuse deux messages.
Le premier message permet d’exécuter la transaction sur une copie ombre
(une copie de la dernière version cohérente de la base), le deuxième message
permet de valider la transaction ou alors de l’annuler pour la réordonnancer.
L’algorithme utilisé dans le système Database State Machine [11,12]
supporte les configurations répliquées partiellement et ne viole pas l’autonomie
des nœuds. Cependant, il requiert un protocole de terminaison atomique du
même type que la validation à 2 phases, et de tels protocoles sont connus pour
ne pas passer à l’échelle.
Une stratégie alternative de réplication est basée sur les quorums. Ces
protocoles requièrent d’accéder à un quorum de copies pour les opérations
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
11
d’écritures et de lectures [13, 14, 15, 16]. Tant que le quorum accepte d’exécuter
une opération, l’opération peut s’exécuter.
Par exemple, l’algorithme de consensus par quorum [13] requiert deux
quorums d’écritures et un quorum de lecture pour écrire sur une copie. Ainsi, au
moins une des copies secondaires aura la dernière valeur. Les autres solutions
combinent l’approche ROWA/ROWAA avec des protocoles utilisant des
quorums.
Ce modèle utilise un protocole de validation de type Validation à 2 Phases
(V2P) [17] pour valider la transaction. Le protocole s’assure alors que tous les
nœuds font le même choix : validation ou abandon de la transaction. Ce modèle
assure une cohérence forte sur toutes les copies.
Asynchrone. Les mises à jour se font dans des transactions séparées. Le serveur
initiateur renvoie la réponse au client immédiatement après la mise à jour sur sa
base de données. Il propage ensuite la mise à jour aux autres nœuds.
Ce modèle a la particularité d’envoyer la réponse au client (phase 4) avant la
coordination des copies et avant même la diffusion de la mise à jour sur les
autres copies (phase 5). Cette propriété impose une contrainte forte, une
réconciliation doit être effectuée pour assurer la cohérence de l’ensemble des
copies.
Cependant, les algorithmes de réplication asynchrone sont souvent
déterministes : ils appliquent les mises à jour en étant sûrs qu’elles ne donneront
pas d’incohérences. On peut classer les algorithmes de réplication synchrone en
deux grandes familles : la réplication asynchrone optimiste et la réplication
asynchrone pessimiste.
Avec la réplication asynchrone optimiste [18], les transactions sont exécutées
en parallèle sans contrôle de cohérence. En cas de conflit, il faut réconcilier les
copies pour que les données convergent vers la même valeur : soit en ré-
exécutant les transactions et en les réordonnant, soit en annulant certaines
transactions. Cette technique est efficace dans les cas où les conflits entre les
transactions sont rares [19, 20, 21, 22] et lorsque les transactions acceptent une
certaine incohérence des données. L’un des avantages de la réplication
asynchrone optimiste est que les transactions sont exécutées localement, un
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
12
nœud du système peut donc exécuter une transaction en étant déconnecté du
reste du système, la réconciliation se faisant à la reconnexion du nœud.
De plus, en l’absence de contrôle de cohérence, les transactions sont
exécutées sans les délais supplémentaires introduits par la réplication pessimiste
synchrone ou asynchrone. Un désavantage de cette technique est que la
réconciliation s’effectue après avoir renvoyé la réponse au client. Ainsi, le client
peut recevoir une réponse incohérente et le nœud peut se trouver dans un état
incohérent jusqu’à la réconciliation. En ce qui concerne le mécanisme de
réconciliation, il peut s’avérer coûteux et le choix des transactions à réordonner
ou à abandonner n’est pas trivial.
La réplication asynchrone pessimiste [23], tout comme la réplication
synchrone, garantit une cohérence forte. Chundi et al. [24] ont montré, que
même avec une configuration maître-paresseux, la sérialisabilité ne peut pas être
garantie dans tous les cas. Pour contourner ce problème, la solution consiste à
restreindre le placement des copies primaires et secondaires sur les nœuds.
L’idée principale est de définir un ensemble de configurations autorisées en
utilisant des graphes où chaque nœud du graphe est un site, et où un arc
représente un lien entre une copie secondaire et une copie primaire d’une même
donnée. Si le graphe est acyclique, la sérialisabilité peut être garantie en
propageant les mises à jour peu après la validation d’une transaction [24]. Pacitti
et al. [25, 26] améliorent ces résultats en au torisant certaines configurations
acycliques mais les transactions sur les nœuds secondaires doivent être
exécutées dans le même ordre total sur tous les nœuds en estampillant les
transactions.
Breitbart et al. [27] proposent une solution alternative en introduisant un
graphe dirigé de la configuration (les arcs sont dirigés de la copie primaire vers
les copies secondaires) qui ne doit pas avoir de cycles. Cette solution demande
aussi une stratégie de propagation des mises à jour plus complexe. Elle
transforme le graphe en arbre où une copie primaire n’est pas nécessairement
directement connectée avec toutes ses copies secondaires. La propagation est
alors effectuée le long du chemin du graphe. Breitbart et al. [27] proposent
également une solution hybride où la réplication synchrone est utilisée lorsqu’il
y a des cycles dans le graphe.
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
13
Bien que toutes ces solutions couvrent un large spectre de configurations,
dans les applications réelles (et spécialement dans les grappes), la restriction sur
le placement et l’approche centralisée des mises à jour sont trop restrictives et
limitent le type de transactions autorisées à être exécutées.
3. Les grappes de bases de données
3.1 Définition
Les “clusters” sont des grappes d’ordinateurs reliés par un réseau local haut
débit. Ils offrent depuis quelques années des environnements performants et
économiquement séduisants pour les sites centralisés qui doivent faire face à un
nombre toujours croissant de clients tout en conservant le même niveau de disp-
onibilité et d’efficacité. Google est un exemple de passage à l’échelle réussi : de
5 machines originelles logées dans un petit bureau de Stanford, leur grappe
contient aujourd’hui plus de 10000machines, toutes hébergées dans le même
bâtiment et accessibles sur le web via une unique URL.
FIG 1.4: grappe de PC
Le succès des grappes est dû aux avantages suivants :
Le faible coût : plusieurs ordinateurs personnels bon marché sont
moins coûteux qu’un seul système multiprocesseurs au tarif d’achat
et de remplacement prohibitif, surtout pour des entreprises de petite
ou moyenne taille.
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
14
La flexibilité : il suffit d’ajouter un nœud (une machine) pour gagner
en capacité de traitement et de stockage et s’adapter ainsi à
l’évolution des besoins des applications.
La disponibilité : en cas de panne, les autres nœuds sont toujours
disponibles, surtout lorsque les données sont répliquées sur tous les
nœuds.
L’efficacité : des traitements simultanés de plusieurs demandes
d’accès aux données peuvent s’exécuter sur plusieurs nœuds en
parallèle.
La simplicité : une grappe offre des délais bornés de communication,
ce qui délivre cette architecture de la gestion délicate de la plupart
des problèmes de distribution pure (détection de terminaison,
consensus, etc.).
Plus récemment, des grappes de base de données ont fait leur apparition.
Chaque nœud héberge un serveur de base de données (SGBD) et les données
sont accédées de façon transactionnelle. Différentes applications peuvent
bénéficier des avantages d’une grappe de base de données pour améliorer leurs
performances, comme par exemple les applications d’ASP (Application Service
Provider). En ASP, les clients installent leur application sur le site centralisé
d’un hébergeur, le site étant constitué d’une grappe de base de données.
L’hébergeur se charge de l’exécution et de la maintenance de l’application
tandis que le client ainsi libéré des tâches techniques peut se concentrer sur ses
aspects métier. Le nombre de nœuds dédiés à une application est fonction du
contrat passé avec le client.
3.2 Les choix d’architectures en grappe
Architecture sans partage : Ici chaque nœud est autonome, il possède son propre
processeur, sa mémoire et son disque dur. Chaque nœud possède alors ses
propres donnés et la répartition des clients doit être faite en priorité selon la
ressource à laquelle le nœud veut accéder. L’équilibrage de charge est donc
étroitement lié à la répartition des données sur le système. En revanche, le
passage à l’échelle en nombre de processeurs est très bon par rapport à une
architecture à disques partagés où les disques deviennent les goulots
d’étranglement. Si cette architecture respecte l’autonomie des nœuds, elle
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
15
implique un certain nombre de contraintes. Les nœuds doivent en effet échanger
de nombreux messages pour connaître leurs états, charges ou fraîcheurs. Enfin,
la détection des pannes est beaucoup plus difficile à mettre en œuvre sur ce type
d’architecture.
3.3 Transparence de la grappe de bases de données
Un aspect important est que la présence de la grappe doit être transparente à
l’application et aux SGBD. D’une part l’accès aux données doit être transparent
pour l’application. Autrement dit, la solution doit préserver l’autonomie de
l’application. La première raison est que la conception d’une application est plus
simple et plus flexible si la présence de la grappe est transparente, suivant en
cela les principes de conception logicielle de séparations des préoccupations. Ce
principe [29] dit qu’un problème donné implique différentes préoccupations, qui
doivent être identifiées et séparées pour mieux gérer la complexité du problème
et pour obtenir les qualités de conception nécessaires, telles que l’adaptabilité, la
maintenabilité, l’extensibilité et la réutilisabilité.
Dans notre cas, la logique de l’application doit être séparée de la méthode
d’accès aux données. La deuxième raison pour préserver l’autonomie de
l’application est que, si l’application existe déjà, sa migration sur une grappe est
un problème délicat et coûteux car une application qui fonctionne depuis de
nombreuses années peut prendre plusieurs années-hommes de travail pour être
portée sur un nouveau système. Rendre l’accès aux données de la base
transparent à l’application signifie que certaines techniques, de nature intrusive,
ne sont pas envisageables.
C’est le cas d’une solution comme l’offre de Windows Clustering dans
laquelle l’application utilise sa connaissance de la grappe (cluster aware
application) pour optimiser l’utilisation de la grappe à ses besoins, mais qui
nécessite de modifier le code de l’application. Pour la même raison, nous
n’utilisons pas de technique langage dédié en proposant par exemple une
extension SQL permettant d’adapter le traitement de l’application à l’existence
de la grappe.
Enfin, la solution proposée ne doit pas modifier les méthodes d’accès de
l’application au SGBD, par exemple en remplaçant l’utilisation d’un driver
JDBC par un nouveau mécanisme de communication (RPC, Corba, RMI, etc.).
Pour cette raison, nous proposons une solution qui se présente comme un driver
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
16
standard, rendant transparente à l’application l’existence de la grappe de base de
données.
D’autre part, la transparence de la grappe signifie qu’un nœud de données
doit pouvoir héberger n’importe quel SGBD, sans avoir à le modifier.
Autrement dit, la solution doit préserver l’autonomie des SGBD. Un avantage
est de rendre la solution plus générique car elle n’est pas liée à l’implémentation
particulière d’un SGBD (Oracle, Postgres, Sybase, DB2, MySQL, etc.).
De plus, même en spécialisant la solution à un seul SGBD, il n’est pas toujours
possible d’accéder aux sources des SGBD propriétaires. Dans tous les cas,
modifier le code d’un SGBD est difficile, donc source d’erreurs, car les SGBD
sont des logiciels extrêmement complexes. Enfin, les clients ont leurs
préférences et ne sont pas nécessairement prêts à stocker leurs données sur un
SGBD nouveau qui ne présente pas les mêmes garanties qu’un système connu,
fiable et maintenu. Néanmoins, préserver l’autonomie des SGBD rend le
contrôle des accès aux données plus complexes car il n’est pas possible de
contrôler la gestion interne des traitements.
Par exemple il n’est pas possible de contrôler l’ordre d’exécution des
opérations de demandes d’accès concurrentes sur un nœud de données, par
exemple en contrôlant la stratégie de verrouillage du gestionnaire de
concurrence. Il devient également difficile de savoir quelles sont les données
touchées par un accès puisque cette information n’est disponible qu’en interne
au moment du calcul du plan d’exécution de l’accès. Pour préserver la
transparence de la grappe, nous avons choisi d’insérer une couche intergicielle
entre l’application et la grappe, cette couche coordonnant les différents SGBD.
4. La réplication dans les grappes
4.1. Graphe Dirigé Acyclique
Dans cette section, nous présentons un algorithme qui utilise des graphes
dirigés acycliques pour garantir une cohérence forte des données entre les
noeuds. L’algorithme DAG(WT) [30], Directed Acyclic Graph (Without
Timestamp) définit un noeud maître pour chaque copie. Puis, d’après le graphe
de dépendance entre les noeuds, il construit un arbre avec la propriété suivante :
si le site Si est un fils du site Sj dans le graphe de dépendance, alors Si sera un
descendant de Sj dans l’arbre.
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
17
Lors d’une mise à jour (toujours sur le nœud maître), la transaction est
exécutée, la réponse est renvoyée au client puis les jeux d’écritures de la
transaction sont transmis aux nœuds fils de l’arbre (même s’ils ne sont pas
concernés par la transaction, leurs fils peuvent l’être) qui l’exécutent à leurs
tours avant de les diffuser à ses fils. Les jeux d’écritures sont validés et renvoyés
aux nœuds fils dans l’ordre dans lequel ils ont été reçus.
Cet algorithme n’est pas spécifique aux grappes, le choix de s’appuyer sur des
graphes dirigés acycliques avec l’emploi de copies primaire le rend mieux
adapté aux applications d’entrepôt de données. Il offre une cohérence forte grâce
à une exécution déterministe des transactions, éliminant ainsi tout abandon.
Cependant, l’algorithme possède quelques inconvénients. Tout d’abord sur le
choix de l’arbre, il n’existe pas un arbre optimal pour un graphe de dépendance.
La qualité d’un arbre dépendra des transactions qui seront exécutées dessus.
Il est donc impossible de choisir un arbre a priori. De plus, pour qu’une
transaction soit exécutée complètement, elle doit parcourir l’intégralité de
l’arbre, elle doit donc être exécutée et diffusée autant de fois qu’il y a de nœuds
dans le chemin de l’arbre. Cette dernière caractéristique rend le passage à
l’échelle impossible pour des graphes possédant beaucoup de nœuds.
1.1. Diffusion optimiste
Nous présentons dans cette section l’algorithme NODO (NOn-Disjoint conflict
classes and Optimistic multicast) [31, 32, 33, 34] qui s’appuie sur le service de
diffusion des messages en ordre total sur tous les noeuds pour garantir
l’ordonnancement des transactions. Pour gérer le contrôle de concurrence,
l’algorithme se base sur la division des copies en classes de conflits. Une classe
de conflit représente une copie ou une partie d’une copie. On détermine ainsi
que deux transactions accédant à la même classe de conflit ont une grande
probabilité de conflit. À l’inverse, deux transactions qui n’accèdent pas aux
mêmes classes peuvent s’exécuter en parallèle. L’algorithme ne permettant
d’associer à une transaction qu’une seule classe de conflit, une abstraction
supplémentaire regroupe des classes de conflits en groupe.
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
18
Algorithme 1 – Algorithme DAG(WT) Entrées:
G : l’arbre issu du graphe de dépendance
Variables:
T : une transaction d’un client C
ET : le jeu d’écriture de la transaction T
listeE : liste des jeux d’écriture reçus
1: début
2: boucler
3: sur la réception de la transaction T depuis un client C
faire
4: Exécuter T
5: Retourner la réponse au client
6: Extraire le jeu d’écriture ET issu de T
7: Diffuser ET à tous ses fils d’après G
8: fin sur
9: sur la réception du jeu d’écriture ET depuis un autre noeud
faire
10: Ajouter ET à la fin de listeE
11: fin sur
12: tant que listeE 6= vide faire
13: Extraire ET de la tête de listeE
14: Appliquer ET
15: Diffuser ET à tous ses fils d’après G
16: fin tant que
17: fin boucler
18: fin
de classes de conflit. On peut alors choisir d’associer à des transactions des
classes de conflits ou des groupes de classes de conflits. Les classes et les
groupes de classes de conflits doivent être connus à l’avance. De plus, chaque
classe de conflit a un seul noeud maître. Les transactions ne pouvant être
soumises qu’au noeud maître de la classe de conflit qu’ils touchent. Il faut donc
connaître la classe de conflit à laquelle accède une transaction avant son
exécution.
La Figure ce dessous montre une version simplifiée de l’algorithme NODO. Au
moment où le nœud maître reçoit une transaction, il la diffuse à tous les noeuds
(y compris lui-même). Ainsi, chaque noeud possède une file associée à un
groupe de classes de conflit. La diffusion des transactions dans le système se fait
en deux étapes. La première diffusion est une diffusion optimiste (optdeliver),
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
19
les messages sont diffusés sans garantie d’ordonnancement. À la deuxième
diffusion, ils ont une garantie d’ordre total (to-deliver). Le système doit
simplement garantir qu’un message opt-deliver ne précédera jamais un message
to-deliver. Quand une transaction est soumise au noeud maître par un client,
elle n’est exécutée que sur la copie ombre de ce noeud. Une transaction est dite
locale quand elle se trouve sur son nœud d’origine (le noeud maître). Ainsi,
annuler une transaction requiert simplement l’invalidation de la copie ombre.
Elle est ensuite diffusée sur tous les noeuds. Quand une copie reçoit le
message opt-deliver, la transaction est placée dans la ou les files
correspondantes aux classes de conflits que touchent la transaction. Dès que ce
message est en tête de l’une de ces files et que la transaction est locale, la
transaction est exécutée.
Une fois que la transaction est to-deliver, le noeud vérifie que les exécutions
se sont effectuées dans le bon ordre et valide la transaction. Si l’ordre total n’est
pas respecté, on se retrouve avec plusieurs cas :
Si aucun conflit n’est entraîné par l’absence d’agrément, l’ordre total
peut-être ignoré.
Si aucune transaction locale n’est impliquée, la transaction peut être tout
simplement réordonnancée et replacée dans sa file avant les transactions
déjà opt-deliver mais pas encore to-deliver. Ainsi, les transactions
suivront l’ordre total.
Algorithme 2 – Algorithme NODO Entrées:
T : une transaction d’un client
C(T) : les classes de conflits touchées par la
transaction T
Variables:
T : une transaction d’un client
CQ1, CQ2,. . ., CQn : files d’attentes des classes de
conflit C1, C2, . . ., Cn
1: début
2: boucler
3: sur la réception de la transaction T d’un client faire
4: Diffuser le message opt-deliver(T)
5: Diffuser le message to-deliver(T)
6: fin sur
7: sur la réception d’un message opt-deliver pour T faire
8: pour Pour toutes les classes de conflits Ci de CT
faire
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
20
9: Ajouter T en fin de CQi
10: fin pour
11: si T est locale et T est en tête de l’une des files
CQ1, CQ2,. . ., CQn alors
12: Exécuter T sur la copie ombre
13: Marquer T comme exécutée
14: fin si
15: fin sur
16: sur la fin de l’exécution de T faire
17: si T est locale et T est to-deliver alors
18: Valider la copie ombre
19: Diffuser le jeu d’écriture WST
20: fin si
21: fin sur
22: sur la réception d’un jeu d’écriture WST faire
23: si T n’est pas locale alors
24: Attendre que T soit to-deliver
25: pour Pour toutes les classes de conflits Ci de C(T)
faire
26: si Premier(CQi) = T alors
27: Appliquer WST correspondant à Ci
28: Enlever T de CQi
29: fin si
30: fin pour
31: sinon
32: Enlever T de toutes les CQi de CT
33: fin si
34: fin sur
35: sur la réception d’un message to-deliver pour T faire
36: Marquer T comme to-deliver
37: si T est locale et T est exécutée alors
38: Valider la copie ombre
39: Diffuser le jeu d’écriture WST
40: fin si
41: si T n’est pas locale alors
42: pour Pour toutes les classes de conflits Ci de C(T)
faire
43: si Premier(CQi) = Tj et Tj est locale alors
44: Abandonner Tj
45: fin si
46: Replacer Tj dans CQi
47: fin pour
48: fin si
49: fin sur
50: fin boucler
51: fin
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
21
Si une transaction locale est impliquée, la procédure est la même que
dans le cas précédent mais les transactions locales (celles qui ne suivent
pas l’ordre total) doivent être annulées et réordonnancées.
Bien que ce protocole garantisse la sérialisabilité-1-copie, la construction d’une
classe de conflit n’est pas claire (pas de règle) et les classes de conflit touchées
par une transaction doivent être connues à l’avance. De plus, avec un seul noeud
maître par groupe de classe de conflit, l’algorithme se rapproche plus d’un mode
de mise à jour Copie Primaire. Finalement, les transactions de lecture sont
favorisées par rapport aux écritures (selon les auteurs, le pourcentage de
transaction d’écriture optimal est 20%, au-delà les performances se dégradent).
1.2. Utilisation du délai réseau
Un autre algorithme de réplication qui garantit la sérialisabilité-1-copie est
présenté dans [35, 36]. Seules les configurations maîtres-paresseux (Lazy-
Master) sont supportées et doivent pouvoir être représentées par des graphes
dirigés acycliques. Afin de garantir la cohérence sur les noeuds secondaires,
l’algorithme utilise une communication de groupe avec une diffusion sûre FIFO
par émetteur. De plus, tous les nœuds doivent pouvoir fournir une estampille
globale. Finalement, l’hypothèse la plus forte implique que le temps de
transmission maximal d’un message soit connu (Max) [37].
Comme illustré sur la figure 3, les transactions de mises à jour sont exécutées
sur le nœud maître puis sont propagées à toutes les copies sous forme de
transaction de rafraîchissement. À la réception de l’une de ces transactions, le
nœud copie place la transaction dans une file d’attente, il y a une file d’attente
par maître que possède la copie. La transaction de rafraîchissement attend alors
un temps Max avant d’être élue et placée dans une file d’exécution. En attendant
un temps Max après son départ, on s’assure alors qu’aucun message n’a été émis
auparavant et transite encore sur le réseau (le réseau est fiable et un message met
au maximum un temps Max pour arriver à sa destination). Le moment exact où
le message sera élu pour exécution est donc : C + Max + ɛ.
Où c’est l’estampille globale (heure d’exécution de la transaction sur la copie
primaire), Max le temps maximal d’arrivée d’un message d’un nœud à l’autre et
ɛ le temps de traitement d’un message.
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
22
En revanche, les lectures n’attendent pas et sont exécutées directement. On
peut donc lire sur une copie secondaire une donnée obsolète puisqu’elle a pu
déjà être mise à jour ou est en train de l’être sur le nœud primaire. Cependant,
l’algorithme assure que l’on ne lira pas sur un nœud un état qui n’a pas existé ou
qui n’existera pas sur les autres nœuds.
Ce protocole garantit également la cohérence sérialisabilité-1-copie. Cependant,
contrairement au protocole précédent, il n’y a pas d’abandons des transactions
puisque l’algorithme est préventif et ne permet pas l’exécution d’une transaction
avant que celle-ci ait été ordonnée.
Algorithme 3 – Algorithme Lazy-Master Entrées:
T : une transaction d’un client C
Variables:
WST : le jeu d’écriture de la transaction T
qi, . . ., qj : files d’attente pour les noeud maîtres
des copies i, . . ., j
timer : compte à rebours
1: début
2: boucler
3: sur la réception de la transaction T depuis un client
C faire
4: Exécuter T
5: Retourner la réponse au client
6: Extraire le jeu d’écriture WST issu de T
7: Diffuser WST
8: fin sur
9: sur la réception du jeu d’écriture ET depuis un noeud
i faire
10: Ajouter WST à qi
11: WST ←jeu d’écriture avec l’estampille minimum parmi
ceux en tête de qi, . . ., qj
12: timer ←(estampille(WST ) + Max + ɛ) - temps-local 13: fin sur
14: sur timer expire faire
15: Appliquer WST
16: WST ←jeu d’écriture avec l’estampille minimum parmi
ceux en tête de qi, . . ., qj
17: timer ←(estampille(WST ) + Max + ɛ) - temps-local 18: fin sur
19: fin boucler
20: fin
Chapitre 01 : LA réplication dans les grappes de base données une vue générale
23
En revanche, l’algorithme attend un délai fixe de Max avant l’exécution de
chaque transaction ce qui oblige cette valeur Max a être parfaitement calibrée par
rapport au système si on ne veut pas que ce délai soit trop important. L’autre
point faible de l’algorithme est qu’il n’autorise que les copies primaires et
secondaires, de plus le placement est restreint puisque que seules les
configurations représentées par des graphes acycliques dirigés sont autorisées
afin de garantir la cohérence.
2. Conclusion
Ce chapitre est divisé en trois parties dans le premier nous présentons une vue
générale sur la réplication de base de données, les techniques et les critères de
classification tel que la distribution ou placement des données, la configuration
(rôle) des répliques et la stratégie de propagation des mises à jour, le deuxième
partie présente une vue sur les grappes de base de données, leur avantages et
caractéristiques, et le troisième partie nous présentons trois types d’algorithmes
pour la gestion de cohérence.
Chapitre 02
Algorithme de réplication
asynchrone pessimiste
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
24
1. Introduction
Dans ce chapitre nous définissons brièvement le projet présenté par «Cédric
COULON » au Laboratoire d’Informatique de Nantes Atlantique (LINA) sous-
titre de "Réplication Préventive dans une grappe de bases de données "
[38]premièrement nous présentons en détail les composants de ce
système(complexe) qui adapte ave le contexte ASP(forte charge), l’architecture
en couches d’un nœud (l’unité de base), comment ces nœuds communiquent
entre elles, l’indépendance entre elles, comment il assure l’autonomie des
nœuds, des applications et de SGBD à l’aide d’un exemple de routage ,
deuxièmement nous définissons comment les données sont distribuées
(réplication partielle) et les types de réplication (multimaitre ou copie primaire),
et enfin nous présentons l’architecture détaillée pour la couche de réplication et
une algorithme pessimiste pour leur gestion.
2. Présentation générale du système
2.1. Architecture globale en cinq couches
Premièrement, nous présentons l’architecture choisie. Cette architecture a pour
but de favoriser le passage d’un modèle centralisé vers un modèle pour grappe.
Celle-ci est basée sur un modèle sans partage. Elle est composée de cinq
couches indépendantes dont nous définissons brièvement le rôle. Nous nous
efforçons aussi de démontrer à la fois l’indépendance des nœuds et des couches.
FIG 2.1 - Architecture globale en cinq couches
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
25
- Routeur de Requêtes : (Request Router) Reçoit les requêtes du client et
les diffuse au noeud le mieux adapté.
- Gestionnaire d’Application (Application Manager) : Contient les
applications présentes sur le noeud.
- Équilibrage des transactions (Transaction Load Balancer) : Reçoit les
transactions depuis les applications et les envoie sur le noeud le mieux
adapté.
- Gestionnaire de Réplication (Replication Manager) : Gère la
réplication des données entre les noeuds. C’est la couche qui nous
intéresse plus particulièrement et que nous développerons dans la suite de
la thèse.
- SGBD : Traite les transactions.
- Le Moniteur de charge : permet de connaître la charge des autres nœuds.
Il est utilisé par les couches Routeur de requêtes et Équilibrage des
transactions qui effectuent toutes les deux de l’équilibrage de charge.
- Le Placement Global des Données : donne une connaissance du
placement des données et des applications sur la grappe. Il est utilisé par
les couches de Routeur de requêtes, Équilibrage des transactions et
Gestionnaire de réplication.
2.2. Contenue d’un nœud :
- Application : des programmes dont l’état ne change jamais. . C’est-à-
dire que l’exécution d’une requête ne modifie pas un programme. Plus
simplement, on peut considérer que les applications sont composées
uniquement de fichiers exécutables (aucun fichier de données). Ainsi, la
réplication des applications n’entraîne pas de gestion de cohérence entre
les différentes versions d’une même application comme peut en introduire
la réplication des données.
- Copies de données : Nous supposons qu’une copie est une table
relationnelle entière. Il est alors facile de considérer des partitions
horizontales ou verticales, il suffit de diviser la table avant son placement
sur la grappe, les partitions devenant autant de copies distinctes. Soit une
table R, il peut exister trois différents types de copies : primaires,
secondaires et multimaîtres. Une copie primaire, que l’on notera R, est
stockée sur un nœud appelé nœud maître. Une copie primaire peut être lue
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
26
et mise à jour. Alors qu’une copie secondaire, que l’on notera ri, est
stockée sur un ou plusieurs. nœuds esclaves i en lecture seule.
Finalement une copie multimaitre, que l’on notera Ri, est stockée sur un
ou plusieurs nœuds multimaitre i où la copie peut être lue et mise à jour.
2.3. Processus de soumission des requêtes :
1. Un client soumet une requête R au nœud quelconque N. Cette requête
appelle l’application A qui va elle-même mettre à jour une donnée D en
créant une transaction T.
2. La couche Routeur de requête de N va analyser la requête pour l’envoyer
à la couche Gestionnaire d’applications de nœud qui possède A et le
moins chargé qui peut être lui-même.
3. La soumission de requête au L’application A pour générer une
transaction T(A), et puis vers la couche Équilibrage des transactions de ce
nœud.
4. La transaction routée vers la couche Gestionnaire de réplication de nœud
qui possède la donnée D
5. Enfin la couche Gestionnaire de réplication de ce nœud soumise la
transaction à la couche Base de données (BD) et va aussi gérer la
cohérence entre les différentes copies de D.
2.4. Exemple de routage :
Pour nos exemples de routage de requêtes, nous supposons une grappe avec trois
nœuds N1, N2 et N1 ; deux applications A1 et A2 ; et deux données D1 et D2.
Le nœud N1 possède l’application A2 et la donnée D2. Le nœud N2 possède
l’application A1. Le nœud N3 possède les applications A1 et A2 et les données
D1 et D2. Cette configuration est représentée dans la figure ce dessous.
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
27
Fig 2.2 - Exemple de routage de requête
Dans l’exemple représenté sur la figure précédente, un client soumet une
requête R1. Cette requête appelle l’application A1 qui va elle-même mettre à
jour la donnée D1 en créant une transaction T1. On note une telle requête
R1(A1, T1(D1)). Dans un premier temps, la requête R1 est soumise au nœud
N1. La couche Routeur de requête (RR) va analyser la requête et comme le
nœud ne possède pas l’application A1, la couche va router la requête vers le
nœud le moins chargé qui possède A1.
Dans notre cas, la couche RR a le choix entre le nœud N2 et N3, mais comme
le nœud N3 est plus chargé, la requête est envoyée à la couche Gestionnaire
d’applications (GA) du nœud N2. La requête va alors être soumise à
l’application qui va générer une transaction T1 qui met à jour la donnée D1. La
transaction est récupérée par la couche GA pour être transmise à la couche
d’Équilibrage des transactions (ET) du nœud local. Ici, comme la transaction T1
met à jour la donnée D1 et que seul le nœud N3 possède cette donnée, alors la
transaction est routée vers la couche de Gestionnaire de réplication (GR) du
nœud N3. Finalement sur le nœud N3, la couche GR soumet la transaction à la
couche Base de données (BD) et va aussi gérer la cohérence entre les différentes
copies de D1.
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
28
3. Algorithme de réplication asynchrone pessimiste :
3.1. Introduction
Dans ce partie, nous nous présentons l’algorithme de réplication asynchrone
proposé par [38] pour la couche Gestionnaire de réplication il utilise la
réplication multimaitre partielle Le principe de l’algorithme de rafraîchissement
est de soumettre une séquence de transactions dans le même ordre
chronologique sur tous les nœuds. Avant de soumettre une transaction pour
l’exécution à un nœud i, on vérifier qu’aucune transaction plus ancienne n’est en
route pour le nœud i. Pour accomplir cela, la soumission d’une transaction est
retardée de Max + ɛ. (Max est le temps maximum pour diffuser une message et
ɛ est la différence maximum entre les horloges) Ainsi, la date de soumission
d’une transaction ayant pour estampille C est nommée le delivery-time et
correspond à la valeur C + Max + ɛ.
3.2. Principe de l’algorithme
Nous définissons une transaction de rafraîchissement, notée RT, comme
l’ensemble des écritures de la transaction T. Une transaction de rafraîchissement
peut donc être considérée comme le jeu d’écritures de la transaction T. Nous
pouvons alors utiliser cette transaction de rafraîchissement pour être exécutée
sur les nœuds qui ne possèdent pas toutes les copies. Cependant, RT doit
également être ordonnancée, et pour garantir la cohérence, il faut exécuter RT en
fonction de l’estampille de T. T est donc normalement diffusée aux autres
nœuds, mais, au lieu d’être soumise pour exécution, le nœud attend la
transaction de rafraîchissement associée RT en provenance du nœud d’origine.
Ainsi, sur le nœud d’origine, quand la validation de T est détectée, la transaction
RT est créée et diffusée aux nœuds qui en ont besoin. Ainsi, les nœuds en attente
sur T pourront remplacer le contenu de T par celui de RT et exécuter la
transaction.
3.3. Architecture pour le module Gestionnaire de réplication
Nous présentons l’architecture du gestionnaire de réplication supporté
(Replica Manager) nécessaire à l’implémentation de l’algorithme de
réplication. Le gestionnaire de réplication se situe entre le gestionnaire de
transaction et le SGBD dans l’architecture globale. Pour rendre l’algorithme de
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
29
réplication le plus indépendant possible de l’architecture générale l’auteur
considère la couche d’équilibrage de charge comme un client soumettant des
transactions. Ainsi, le gestionnaire de réplication n’a aucun objectif
d’équilibrage de charge du système. Pour construire cette architecture, il a ajouté
plusieurs composants autour du SGBD, mais toujours dans l’optique de
préserver son autonomie (sans utiliser les mécanismes internes du SGBD).
Figure 2.3 – Architecture détaillée pour le module Gestionnaire de réplication
3.3.1. Replica Interface :
- A pour but recevoir les requêtes des clients et d’estampiller les
transactions
- utilise le technique ROWA les transactions de lecture sont exécutées
localement et les transactions de mise à jour sont elle est envoyée au
module Propagator par une file appelée file de propagation qui est lue par
le Propagator.
- Envoyer la réponse provenant de Deliver aux clients.
3.3.2. Log Moniter :
- lire constamment les fichiers de journalisation du SGBD afin de détecter
si une copie a été mise à jour.
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
30
- Pour chaque transaction le module crée d’une transaction de
rafraîchissement RT et la soumette au module Propagator pour la
diffusion.
- Pour éviter les cases des pannes le Log Moniter stocke la RT dans le
journal des transactions de rafraîchissement (RT-Log). Tous les nœuds
capables d’exécuter T génèrent ainsi la RT correspondante et la stocke
dans le RT-Log.
3.3.3. Propagator :
- Attendre l’arrivée d’une nouvelle transaction dans la file de propagation
- Utilise le mode de diffusion FIFO par émetteur pour diffuser les transa-
ctions aux nœuds touchés par la transaction il a donc a donc besoin de
deux informations pour fonctionner correctement : la liste des copies
touchées par la transaction et le placement des copies dans le système.
3.3.4. Receiver : Récupère deux types de messages (transactions et
transactions de rafraîchissement) :
- soumettre les transactions au module Refresher.
- Envoyer les transactions de rafraîchissement directement au Deliver.
3.3.5. Refresher :
- choisir la transaction la plus ancienne (avec l’estampille la plus petite)
parmi les transactions en tête des files d’attente.
- Retirer la transaction prête a être exécutée (son timer expiré) de file
d’attente vers la file d’exécution de module Deliver.
3.3.6. Deliver :
- Soumettre séquentiellement les transactions (une par une) de file d’exé-
cution au SGBD.
- Si le nœud contient toutes les copies touchées par T il exécute T norma-
lement, sinon il attende la RT).
- Sur l’arrivé d’une transaction de rafraîchissement le module Deliver
remplace le contenue de T par son RT et la soumette directement au
SGBD.
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
31
3.4. Algorithmes :
Algorithme 4 – Module Propagator
Entrées:
file de propagation
Variables:
T : une transaction
1: début
2: boucler
3: sur l’arrivée d’une nouvelle transaction T ou RT dans la file de propagation
faire
4: retirer T ou RT de la file de propagation
5: diffuser T aux nœuds touchés par T ou RT
6: fin sur
7: fin boucler
8: fin
Algorithme 5 – Module Receiver
Sorties:
files d’attente q1,... qn
Variables:
T : une transaction
RT : transaction de rafraichissement
1: début
2: boucler
3: sur l’arrivée d’une nouvelle transaction T du nœud n faire
4: ajouter T à la file d’attente correspondante qn
5: fin sur
6: sur l’arrivée d’une nouvelle transaction RT du nœud n faire
7: envoyer RT au Delivers des nœuds touchés par RT
8: fin sur
9: fin boucler
10: fin
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
32
Algorithme 6 – Module Refresher
Entrées:
files d’attente q1,... qn
Sorties:
file d’exécution
Variables:
elueT : transaction actuellement élue pour être la prochaine à être exécutée
premierT : transaction avec la plus petite estampille dans les files d’attente
timer : compte à rebours local
1: début
2: elueT ⇐ 0
3: premierT ⇐0
4: boucler
5: sur l’arrivée d’une nouvelle transaction ou lorsque (timer.state = active et
timer.value
= 0) faire
6: Etape 1:
7: premierT ⇐ transaction avec l’estampille C la plus petite parmi les messages
en tête des files d’attente
8: Etape 2:
9: si premierT 6= elueT alors
10: elueT ⇐premierT
11: calculer delivery-time(elueT )
12: timer.value ⇐delivery-time(elueT ) - temps local
13: fin si
14: Etape 3:
15: si elueT 6= 0 et timer.value = 0 alors
16: ajouter elueT à la file d’exécution
17: enlever elueT de sa file d’attente
18: elueT ⇐ 0
19: saut à l’étape 1
20: fin si
21: fin sur
22: fin boucler
23: fin
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
33
Algorithme 7 – Module Deliver
Entrées:
file des jeux d’écritures
file d’exécution
listeT : couple (id local, id global) des transactions en cours d’exécution sur le noeud
Sorties:
SGBD
Replica Interface
Variables:
localT : identifiant local de la transaction T
globalT : identifiant global de la transaction T
wsT : les jeux d’écritures de la transaction T
T : une transaction
rT : la réponse du SGBD à T
1: début
2: boucler
3: sur l’arrivée d’une nouvelle transaction T dans la file d’exécution faire
4: enlever T de la file d’exécution
5: si le noeud possède toutes les copies pour exécuter T alors
6: démarrer T sur le SGBD
7: récupérer localT , l’identifiant local de T
8: créer une entrée (localT , globalT ) dans listeT
9: soumettre T au SGBD
10: valider T
11: si T est locale au noeud alors
12: envoyer rT au Replica Interface
13: fin si
14: sinon
15: démarrer T sur le SGBD
16: mettre T en attente
17: fin si
18: fin sur
19: sur l’arrivée d’un nouveau jeu d’écritures wsT dans la file des jeux d’écritures
faire
20: enlever wsT de la file des jeux d’écritures
21: réveiller la transaction T en attente
22: filtrer wsT pour ne garder que les opérations dont le noeud possède les copies
23: soumettre wsT au SGBD
24: valider T
25: fin sur
26: fin boucler
27: fin
Chapitre 2 : Algorithme de réplication asynchrone pessimiste
34
4. Conclusion
Dans ce chapitre nous présentons une vue générale sur le projet présenté par
l’auteur Cédric COULON qui offre un système complexe pour la gestion des
grappes ont une forte charge de transactions, ce chapitre est divisé en deux
parties, dans le premier partie nous présentons l’ architecture sans partage
adopté par l’auteur qui adapte au contexte ASP où une grappe contient les bases
de données mais aussi les applications d’un client, architecture, par sa
modélisation en cinq couches et l’utilisation de trois services, permet de garantir
l’autonomie des nœuds. Un exemple montre que l’architecture en couches
permet un équilibrage de charge à deux niveaux : les applications et les bases de
données.
De plus, par un routage des requêtes sur deux des couches, il autorise la
séparation des applications et des données sur plusieurs nœuds. Ce routage
permet également aux nœuds de pouvoir traiter n’importe quelle requête, et ceci
même si le nœud ne possède pas les applications ou les données nécessaires à la
requête, en la déléguant à un autre nœud. Finalement, les nœuds sont autonomes
les uns par rapport aux autres et la panne d’un nœud n’entraîne pas le blocage
des autres sites. De même chaque couche est indépendante l’une de l’autre et la
panne de l’une d’entre elles n’entraîne pas la panne des autres.
Dans la deuxième partie nous définissons l’algorithme pessimiste supporté
pour une configuration partielle assurer une cohérence forte entre les nœuds,
nous présentons l’architecture en couche pour le module le gestionnaire de
réplication, le rôle de chaque module et les algorithmes correspondants.
Chapitre 03
Adaptation et optimisation
de l’algorithme
Chapitre 03 : Adaptation et optimisation de l’algorithme
35
1. Introduction
Dans ce chapitre nous présentons nos modifications sur les deux (i) les
composants de système, le modèle en couches, la couche gestionnaire de
réplication (ii) l’optimisation de l’algorithme de réplication concerne le délai
introduit par la réplication. Pour garantir un ordre total des transactions, la
transaction doit attendre un délai Max + ɛ avant d’être envoyée au SGBD. Notre
première optimisation a donc pour but de supprimer ce délai en exécutant les
transactions de manière optimiste. Des exécutions optimistes impliquent
cependant des abandons. Nous montrons alors que notre algorithme garantit
toujours la cohérence forte malgré l’introduction d’abandons.
2. Caractéristiques et l’architecture de nouveau environnement : ce système
destiné aux les entreprises qui donnent des services simples et bien
déterminées aux son clients par exemple les agences touristiques, bancaires
et les centres commerciales :
- Un nombre de PC constituants le serveur de gestion de système.
- Le flux de transactions est moyen, alors le routage de transactions et la
concurrence gérés de façon simple.
FIG 3.1 – Architecture de nouveau système
Services Services Services Services
Gestionnaire
de réplication
Gestionnaire
de réplication
Gestionnaire
de réplication
Gestionnaire
de réplication
BD BD BD BD
Client 1 Client 2 Client 3 Client n
Chapitre 03 : Adaptation et optimisation de l’algorithme
36
3. Cycle de vie de requête :
- un agent applique un service, le nœud crée la transaction correspondant.
- On utilise la stratégie ROWA, Selon le type de transaction, soit de type
lecture qui exécuté localement, soit de type mise à jour qui propagé vers tous
les nœuds concernés.
- Le module gestionnaire de réplication est le responsable de router cette
transaction vers les nœuds concernés (qui ont la donnée changé) pour
garantir la cohérence entre les nœuds.
Services
Équilibrage des
transactions
Gestionnaire de
Réplication
Moniteur de
charge
Placement
globale de
données
SGBD
FIG 3.2 - Architecture en couches modifié
d’un nœud
Chapitre 03 : Adaptation et optimisation de l’algorithme
37
4. Architecture modifiée pour le module Gestionnaire de réplication :
FIG 3.3 - Architecture modifiée pour le module gestionnaire de réplication
Description
Dans cette architecture le module Interface de réplication gère tous les
composants de cette couche :
- Quand le nœud reçoit une transaction de ses services ou son receveur reçoit
une transaction d’autre nœud, l’Interface de réplication stocke cette
transaction dans la file d’attente et d’exécution
- Quand le nœud reçoit une transaction de ses services il la propager vers tous
les nœuds concerné a l’aide de service de Placement globale de données.
- L’interface de réplication gère les deux files selon le principe de l’algorithme
et soumettre les transactions au SGBD.
5. Optimisation de l’algorithme pessimiste (Élimination du délai d’attente) :
Pour ordonnancer les transactions dans un ordre total, l’algorithme
de réplication préventive utilise les propriétés réseau. Il garantit qu’une
transaction est en ordre total après un délai Max + ɛ où Max est le temps
Interface de
réplication
File d’exécution
Propagateur Receveur
File d’attente
T
Placement
globale de
données
SGBD Client
Rép
Réseau rapide
Log Monitor
Chapitre 03 : Adaptation et optimisation de l’algorithme
38
maximum mit par une transaction pour être diffusée et ǫ est la différence
maximale entre deux horloges. La valeur Max correspond au temps le plus
pessimiste de diffusion d’un message, l’écart entre le temps moyen de diffusion
(quelques millisecondes) et la valeur Max (quelques centaines de millisecondes)
peut donc être importante. Dans cette section. Nous présentons une optimisation
qui élimine ce temps d’attente en exécutant les transactions optimistiquement.
5.1. Principe
Dans un réseau de grappe qui est typiquement rapide et fiable, la plupart des
messages sont naturellement ordonnés. Seule une faible partie des messages est
reçue dans un ordre différent de celui de l’ordre d’émission. Nous appelons
message non-ordonné un message reçu en retard, c’est-à-dire qu’un message
plus récent a déjà été reçu. En nous basant sur cette propriété, nous pouvons
améliorer notre algorithme en soumettant une transaction pour exécution dès sa
réception. Ainsi nous supprimons le délai qui précède la soumission des
transactions. Nous avons cependant toujours besoin de garantir la cohérence
forte. Pour atteindre cette cohérence, nous n’ordonnançons plus les transactions
complètes mais uniquement leur validation. Une transaction ne peut donc
valider qu’après le délai Max + ǫ. Les transactions sont alors exécutées pendant
leur ordonnancement et non plus après. Ainsi, dans la plupart des cas le délai
(Max + ɛ) est supprimé.
L’exécution optimiste des transactions peut cependant entraîner des
abandons. En effet, si une transaction est reçue non-ordonnée, alors toutes les
transactions plus récentes déjà en exécution doivent être annulées. Ensuite on
resoumet les transactions en fonction de leur estampille. Notons qu’une
transaction plus récente ne pourra jamais être validée car elle n’a pas été
ordonnancée.
L’interface de réplication lit les transactions en tête des files d’attente et
garantit l’ordre chronologique en fonction de l’estampille de la transaction. Une
fois qu’une transaction T est ordonnée, alors Test prête à être exécuté. Pendant
ce temps, l’interface de réplication lit les messages en-tête de la file d’exécution
pour démarrer les transactions optimistiquement, l’une après l’autre, dans le
SGBD local. Une transaction validée uniquement lorsqu’elle est ordonnée.
Chapitre 03 : Adaptation et optimisation de l’algorithme
39
5.2. Exemple
Soit un nœud i possédant une copie maître de R. Le nœud i reçoit T1 et T2,
deux transactions mettant à jour R, respectivement du nœud j avec une
estampille C1 = 10 et du nœud i avec une estampille C2 = 15. T1 et T2 doivent
être exécutées dans l’ordre chronologique, soit d’abord T1 puis T2. Voyons ce
qui se passe lorsque les messages sont reçus non-ordonnés sur le nœud i. Dans
notre exemple, T2 est reçue avant T1 sur le nœud i et immédiatement écrite dans
la file d’exécution et dans la file d’attente correspondante.T2 est alors soumise
pour exécution mais doit attendre la décision pour valider.
Pendant ce temps, T1 est reçue sur le nœud i, elle est également écrite dans la
file d’exécution et dans la file d’attente correspondante au nœud j. Le module
détecte cependant qu’une transaction plus jeune, T2, a déjà été soumise pour
exécution avant T1. T2 est alors annulée puis redémarrée, entraînant sa
réinsertion dans la file d’exécution (après T1). T1 est ensuite soumise pour
exécution et également élue pour être validée. À la fin de son exécution T1 peut
valider. Ensuite, T2 est démarrée et élue pour être la prochaine transaction à
valider. Ainsi, les transactions sont validées dans l’ordre de leur estampille,
même si elles sont reçues non-ordonnées.
Avec cet exemple, nous pouvons voir une petite optimisation très simple
qui limite le nombre d’abandon de notre nouvel algorithme. Au lieu d’ajouter les
transactions en fin de la file d’exécution, elles sont insérées en fonction de leur
estampille, la plus jeune étant placée en queue de la file. Ainsi, les transactions
sont pré-ordonnancées. Cette optimisation n’est possible que pour les
transactions qui n’ont pas encore été soumises pour l’exécution.
5.3. Algorithmes :
5.3.1. Réception de transactions
Chapitre 03 : Adaptation et optimisation de l’algorithme
40
Algorithme 8 – réception d’une transactions
Sorties:
file d’attente et file d’exécution
Variables:
T : une transaction
1: début
2: boucler
3: sur l’arrivée d’une nouvelle transaction T du nœud n ou de mes services
faire
4: ajouter T à la file d’exécution
5: ajouter T à la file d’attente
6: fin sur
7: fin boucler
8: fin
5.3.2. Soumission des requêtes
Algorithme 8 – Soumission des transactions
Variables:
file d’exécution
file d’attente
une transaction T, T_estmp : l’estampille de T
T_fin : T_estmp + MAX + ɛ
T_etat : annuler ou valider
1: début
2: boucler
3 :Pour chaque T faire dans la file d’exécution faire
4 :Soumettre T au SGBD et attente la validation
5 :Quand T_fin =t
6 :Si T est bien ordonnée
7 :valder T , T_etat valider
8 :extraire T de file d’attente et file d’exécution
9 :sinon annuler T er réordonner
10 :Fin pour
11: fin boucler
8: fin
Chapitre 03 : Adaptation et optimisation de l’algorithme
41
5.3.3. Propagation des transactions
Algorithme 8 – Propagation des transactions
Sorties:
file de propagation
Variables:
T : une transaction
1: début
2: boucler
3: sur un client applique un service faire
Le nœud i crée la transaction T correspondant
Le nœud i ajoute T aux ses file d’attente et d’exécution
A l’aide de service de Placement globale de données
Le nœud i propage T vers tous les concernés qui ont la donnée touché par T
6: fin sur
7: fin boucler
8: fin
6. Preuves
Dans cette section, nous prouvons que les optimisations que nous avons
proposées n’introduisent pas d’incohérence dans le système et que la cohérence
forte est garantie.
Il faut montrer que l’exécution optimiste des transactions pour éliminer le
délai Max + ɛ n’introduit pas d’incohérence malgré l’exécution optimiste des
transactions et les abondons que cela entraîne.
Démonstration. Soit T1 et T2 deux transactions quelconques avec des
estampilles C1 et C2. Si T1 est plus ancienne que T2 (C1 < C2) et que T2 est
reçue sur le nœud i avant T1, alors T2 est exécutée optimistiquement. Cependant
T2 ne peut pas être validée avant C2 +Max + ɛ. Comme T1 est reçue sur le
nœud i au plus tard à C1 +Max + ǫ, alors T1 est reçue avant la validation de T2
(C1 +Max + ɛ < C2 +Max + ɛ). Par conséquent, T2 est abandonnées et les deux
transactions sont insérées dans la file d’exécution, exécutées et validées en
fonction de leur estampille. Au final, T1 est exécutée avant T2, et la cohérence
forte est garantie même dans le cas de messages non ordonnés.
Chapitre 03 : Adaptation et optimisation de l’algorithme
42
7. Conclusion
Pour réduire le temps de réponse, nous avons amélioré les points faibles de
l’algorithme de réplication pessimiste.
Nous avons éliminé le délai introduit par l’ordonnancement des transactions
en les exécutent de manière optimiste dès leur réception dans le nœud et non
plus après le délai Max + ɛ. Si les transactions n’ont pas été exécutées dans
l’ordre correct (celui de leurs estampilles), alors elles sont annulées et ré-
exécutées après ordonnancement. Le nombre d’abandons reste faible car dans un
réseau rapide et fiable les messages sont naturellement ordonnés. Malgré cette
optimisation la cohérence forte est garantie car nous retardons la validation des
transactions (et non plus la totalité de la transaction) exécutées
optimistiquement. Les transactions sont ordonnancées pendant leur exécution et
non plus avant, supprimant ainsi les délais d’ordonnancement.
Chapitre 4
mise en œuvre
Et validation
Chapitre 4 : Mise en œuvre et validation
43
1. Introduction
Dans ce chapitre nous essayons d’implémenter l’algorithme sur quatre PC
reliés par un réseau rapide avec une architecture sans partage, les PCs
communiquent par l’échange de messages pour gérer la cohérence entre elles.
Alors dans cette partie nous définissons les outils et les moyens pour
implémenter notre algorithme de réplication optimiste partiel multimaitre, nous
définissons l’équipement, matériels tel que les PCs le réseau et logiciels tel que
le langage et les outils de programmation utilisés, et on illustre la gestion de file
d’exécution par des interfaces graphiques.
2. L’environnement à implémenter :
Pour la validation nous essayons de construire et simuler une base de données
simple d’un centre commercial : les agents, les clients, les produits ses
catégories et ses prix... etc.
3. Les outils d’implémentation :
3.1. Le langage java :
Nous avons choisi d’utiliser Java qui est à la fois un langage de programmation
et une plateforme d’exécution.
3.1.1. Java et multithreading :
Le module d’interface de réplication qui gère la couche gestionnaire de
réplication tel que la gestion de files d’attentes, la file d’exécution, la réception
et la propagation des transactions sont des threads exécutées en parallèle et en
permanente.
3.1.2. Threads, variables partagés et synchronisation :
Par exemple le thread qui empile les transactions dans la file d’exécution et le
thread qui retire les transactions et les soumettre au SGBD, ces deux threads
utilisent le même variable, pour cela il faut protéger ce variable à l’accès
concurrente par l’utilisation de méthodes de synchronisation de threads en java.
Chapitre 4 : Mise en œuvre et validation
44
3.1.3. Les sockets en java et la communication par échange de messages :
Pour la gestion de cohérence les nœuds communiquent par l’envoi des
transactions de mise à jour entre elles, et l’outil meilleur est l’échange de
messages en utilisant les sockets qui assurent l’émission et la réception de
transactions enveloppés dans les messages.
3.2. Le SGBD Postgresql
La base de données c’est le point cible de l’algorithme, parce que l’objectif de
l’algorithme est garantir une cohérence entre les nœuds, c’est-à-dire, tous les
nœuds possèdent la même version de données à chaque moment, le SGBD
considéré comme une boite noire, dans notre implémentation nous utilisons le
PostgreSQL. Le PostgreSQL est un système de gestion de base de données
relationnelle et objet(SGBDRO)[39]. C'est un outil libre disponible selon les
termes d'une licence de type BSD.
Ce système est concurrent d'autres systèmes de gestion de base de données,
qu'ils soient libres (comme MySQL et Firebird), ou propriétaires (comme
Oracle, Sybase, DB2et Microsoft SQL Server).
FIG 4.1 – PostgreSQL
Chapitre 4 : Mise en œuvre et validation
45
4. Les états de gestion de file d’exécution
4.1. Exemple d’exécution de deux requêtes ordonnées : on exécute deux
requêtes sur deux postes déférentes chacun propage son requête vers
l’autre, dans ce cas les deux requêtes reçus en ordre correcte sur les
deux postes, alors elles validés normalement.
- Requête 1 : en poste 01
FIG 4.2 – modifier produit en poste 01
- Requete 2 : en poste 02
FIG 4.3 – modifier produit en poste 02
Chapitre 4 : Mise en œuvre et validation
46
La requête 1 crée avant la requête 2 et propagé, le poste 02 reçoit la requête 1 en
ordre correct et les deux files d’exécutions sont le même, les deux postes
exécutent req1puis req2.
FIG 4.4 – file d’exécution ordonné (1) en poste 01
FIG 4.5 – file d’exécution ordonné en poste 02
Le prix final est 35 DA
4.2. Exemple d’exécution de deux transactions non-ordonnées :
Dans ce cas nous essayons de produire deux requêtes et on retarde l’une de deux
Le poste 01 crée une transaction, la stocke dans son file et la propage vers le
poste 02, malheureusement T1 retardé, au ce moment le poste 02 aussi crée une
transaction T2 et la stocke dans son file et la propage vers le poste 01(les mêmes
transactions de l’exemple précédente).
Chapitre 4 : Mise en œuvre et validation
47
L’ordre d’exécution sur le deux postes est défirent, sur le poste 01 T1 puis T2,
mais sur le poste 02 T2 puis T1.Chaque poste exécute les transactions suivant
son file d’exécution mais heureusement elles attendent la validation.
Sur le poste 01 après un Tmax + ɛ pour chaque transaction l’ordre est correct,
T1 et T2 validés normalement.
Sur le poste 02 après un Tmax + ɛ l’ordre et T2 puis T2 mais estampille de
T1<estampille de T2, alors T1 validé mais T2 annulé et réordonné.
FIG 4.6 – file d’exécution ordonné(2) en poste 01
FIG 4.7 – file d’exécution non-ordonnée en poste 02
Chapitre 4 : Mise en œuvre et validation
48
Poste 02 annule T2, et la réordonne, valide T1 et la retire de sa file
d’exécution.
FIG 4.8 – file d’exécution de poste 01 après la validation de T1
4.3. Exemple d’exécution de requêtes de lecture
Les transactions de lecture exécutées localement, on les soumet directement
au SGBD sans propager et sans placer dans la file d’exécution.
Exemple : afficher la liste de produits
FIG 4.9 – affichage de liste de produits
Le résultat est :
FIG 4.10 – liste de produits
Chapitre 4 : Mise en œuvre et validation
49
La transaction de lecture n’inséré pas à la file
FIG 4.11 – file d’exécution de poste 01 après la transaction de lecture
5. Conclusion
Dans ce chapitre nous présentons les outils matériels et logiciels pour
l’implémentation de l’algorithme, alors on relie 04 PCs par un réseau rapide
avec une architecture sans partage, chaque PC possède sa propre mémoire,
processeur et disque, ces PCs communiquent entre elles par l’échange des
messages (en utilisant les sockets) contenants les transactions pour conserver la
cohérence entre les nœuds. La gestion de files d’exécution et d’attente est
assurée par le multithreading et la synchronisation en java .On choisit le
PostgreSQL comme un SGBD pour l’implémentation de la base de données. Et
enfin nous présentons les états possibles de gestion de file d’exécution illustrées
par des interfaces graphiques.
Conclusion
générale
Conclusion générale
50
1. Conclusion
Nous voici à la fin de notre travail qui s’intitule : Algorithme de réplication
multimaitre pour la gestion de cohérence dans une grappe de base de
données. Pour franchir la fin de notre cycle de master informatique LMD.
Ce travail était subdivisé en quatre chapitres :
Dans le premier : une vue générale sur les deux (i) la réplication de base de
données (ii) et les grappes de données pour présenter une idée complète sur les
concepts utilisés dans ce domaine.
Dans le deuxième : présentation de l’architecture et de l’algorithme qui destiné
aux environnements ont une fort charge de données.
Dans le troisième : optimisation et simplification de l’algorithme pour adapter
avec notre environnement (pas de forte charge) à une charge moyen.
Dans le quatrième : présentation des moyennes et les outils pour la mise en
œuvre de l’algorithme avec une explicitation graphique pour la gestion de file
d’exécution.
1. Quelques points entour de cette thèse :
- De centralisation vers la distribution :
Une base de données distribuée peut être vue comme une collection de plusieurs
bases de données physiquement distribuées sur un ensemble de sites,
sémantiquement reliées, car elles partagent le même schéma conceptuel. Les
données peuvent être fragmentées, ainsi chaque site héberge uniquement une
partie des données. L’autre option consiste à répliquer les données, cela
implique la duplication de la base de données sur chaque site (une copie par
site).
- L’Apparition de parallélisme, ses outils et ses algorithmes.
- protocoles réseaux à hautes performances à base de composants
standard.
- Les grappes de PCs :
présentés comme une alternative aux multiprocesseurs.
Conclusion générale
51
Son cout faible soit leurs maintenances, gestions et remplacements
par rapport les supercalculateurs.
- La réplication de base de données et gestion de cohérence:
La réplication est bon solution pour améliorer la performance et la disponibilité
de système qui consiste à maintenir plusieurs copies de données distribuées sur
plusieurs machines séparées. Alors il faut trouver un mécanisme pour assurer la
cohérence de données entre les nœuds de grappe.
2. Perspectives
Les perspectives de cette thèse concernent la maintenance de grappe c-à-dire la
mise en recharge dans le cas de panne d’un nœud ou en cas de l’addition des
autres nœuds.
Un test de performance de l’algorithme dans un environnement réel en termes de
gestion de cohérence et équilibrage de charge.
Enfin, nous terminons ce travail. En effet, ce travail étant une œuvre u humaine,
n’est pas un modèle unique et parfait, c’est pourquoi nous restons ouverts à
toutes les critiques et sommes prête à recevoir toutes les suggestions et
remarques tendant à améliorer d’avantage cette étude. Etant donné que tout
travail informatique a été toujours l’œuvre d’une équipe.
52
Bibliographie
[01] Silberschatz Korth Sudarshan.« Database System Concepts, Fourth Edition ».The
McGraw−Hill Companies, 2001.
[02] A. Schiper and M. Raynal. From group communication to transactions in distributed
systems. Commun. ACM, 39(4) :84–87, 1996.
[03] S. Gançarski. Cohérence et Fraîcheur dans les bases de données réparties. Habilitation à
diriger des recherches, Université Pierre et Marie Curie, Paris 6, France, October 2006.
[04] S. Gançarski. Cohérence et Fraîcheur dans les bases de données réparties. Habilitation à
diriger des recherches, Université Pierre et Marie Curie, Paris 6, France, October 2006.
[05] M.Wiesmann, F. Pedone, A. Schiper, B. Kemme, and G. Alonso. Understanding
replication in databases and distributed systems. In International Conference on Distributed
Computing Systems (ICDCS), Taipei, Taiwan, R.O.C., 2000. IEEE Computer Society.
[06] P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery
in Database Systems. Addison-Wesley, 1987.
[07] P. A. Bernstein and N. Goodman. An algorithm for concurrency control and recovery in
replicated distributed databases. ACM Transactions on Database Systems (TODS), 9(4):596–
615, 1984.
[08] N. Goodman, D. Skeen, A. Chan, U. Dayal, S. Fox, and D. Ries. A recovery algorithm
for a distributed database system. In ACM symposium on Principles of Database Systems
(PODS), pages 8–15, New York, NY, USA, 1983. ACM Press.
[09] B. Kemme and G. Alonso. Don’t Be Lazy, Be Consistent: Postgres-R, A New Way to
Implement Database Replication. In International Conference on Very Large Data Bases
(VLDB), pages 134–143. Morgan Kaufmann, 2000.
53
[10] M. Patiño-Martínez, R. Jiménez-Peris, B. Kemme, and G. Alonso. Scalable Replication
in Database Clusters. In International Symposium on Distributed Computing (DISC), pages
315–329, 2000.
[11] A. Sousa, R. Oliveira, F. Moura, and F. Pedone. Partial Replication in the Database State
Machine. In IEEE International Symposium on Network Computing and Applications (NCA),
pages 298–309, 2001.
[12] A. Sousa, J. Pereira, F. Moura, and R. Oliveira. Optimistic Total Order in Wide Area
Networks. In IEEE Symposium on Reliable Distributed Systems (SRDS), page 190,
Washington, DC, USA, 2002. IEEE Computer Society.
[13] D. K. Gifford. Weighted Voting for Replicated Data. In Symposium on Operating System
Principles (SOSP), pages 150–162, Asilomar Conference Grounds, Pacific Grove CA, 1979.
ACM, New York.
[14] S. Jajodia and D. Mutchler. Dynamic Voting Algorithms for Maintaining the
Consistency of a Replicated Database. ACM Transactions on Database Systems (TODS),
15(2):230–280, 1990.
[15] J-F. Pâris and D. D. E. Long. Efficient Dynamic Voting Algorithms. In International
Conference on Data Engineering (ICDE), pages 268–275. IEEE Computer Society, 1988.
[16] R. H. Thomas. A majority consensus approach to concurrency control for multiple copy
databases. ACM Transactions on Database Systems (TODS),
4(2):180–209, 1979.
[17] J. N. Gray and A. Reuter. Transaction Processing: concepts and techniques. Data
Management Systems. Morgan Kaufmann Publishers, Inc., San Mateo (CA), USA, 1993.
[18] Y. Saito and M. Shapiro. Optimistic Replication. Computing Surveys, 37(1):42– 81,
March 2005.
[19] Y. Amir and C. Tutu. From Total Order to Database Replication. In International
Conference on Distributed Computing Systems (ICDCS), Vienna, Austria, 2002. IEEE.
54
[20] J. N. Gray, P. Helland, P. O’Neil, and D. Shasha. The Dangers of Replication and a
Solution. In SIGMOD, pages 173–182, Montreal, Canada, 1996.
[21] C. Le Pape, S. Gançarski, and P. Valduriez. Trading freshness for performance in a
cluster of replicated databases. OTM Workshops, pages 14–15, 2003.
[22] C. Le Pape, S. Gançarski, and P. Valduriez. Refresco: Improving query performance
through freshness control in a database cluster. In CoopIS/DOA/ODBASE (1), pages 174–193,
2004.
[23] E. Pacitti and P. Valduriez. Replicated Databases: Concepts, Architectures and
Techniques. Networking and Information Systems (NIS), 1(4-5):519–546, 1998.
[24] P. Chundi, Daniel J. Rosenkrantz, and S. S. Ravi. Deferred Updates and Data Placement
in Distributed Databases. In International Conference on Data Engineering (ICDE), pages
469–476, Washington, DC, USA, 1996. IEEE Computer Society.
[pr25] E. Pacitti, P. Minet, and E. Simon. Fast Algorithms for Maintaining Replica
Consistency in Lazy Master Replicated Databases. In International Conference on Very Large
Databases (VLDB), Edinburgh - Scotland - UK, 7–10 1999.
[pr26] E. Pacitti, P. Minet, and E. Simon. Replica Consistency in Lazy Master Replicated
Databases. Distributed and Parallel Databases, 9(3):237–267, 2001.
[27] Y. Breitbart, R. Komondoor, R. Rastogi, S. Seshadri, and A. Silberschatz. Update
propagation protocols for replicated databates. In SIGMOD, pages 97–108, New York, NY,
USA, 1999. ACM Press.
[28] T. Ozsu and P. Valduriez. Principles of Distributed Database Systems (2nd Edition).
Prentice Hall, January 1999.
[29] EdsgerW. Dijkstra. A Discipline of Programming. Prentice-Hall, 1976.
55
[30] Y. Breitbart, R. Komondoor, R. Rastogi, S. Seshadri, and A. Silberschatz. Update
propagation protocols for replicated databates. In SIGMOD, pages 97–108, New York, NY,
USA, 1999. ACM Press.
[31] B. Kemme and G. Alonso. Don’t Be Lazy, Be Consistent: Postgres-R, A New Way to
Implement Database Replication. In International Conference on Very Large Data Bases
(VLDB), pages 134–143. Morgan Kaufmann, 2000.
[32] B. Kemme and G. Alonso. A New Approach to Developing and Implementing Eager
Database Replication Protocols. ACM Transactions on Database Systems (TODS), 25(3):333–
379, 2000.
[33] M. Patiño-Martínez, R. Jiménez-Peris, B. Kemme, and G. Alonso. Scalable Replication
in Database Clusters. In International Symposium on Distributed Computing (DISC), pages
315–329, 2000.
[34] R. Jiménez-Peris, M. Patiño-Martínez, B. Kemme, and G. Alonso. Improving the
Scalability of Fault-Tolerant Database Clusters. In International Conference on Distributed
Computing Systems (ICDCS), pages 477–484, 2002.
[35] E. Pacitti, P. Minet, and E. Simon. Fast Algorithms for Maintaining Replica Consistency
in Lazy Master Replicated Databases. In International Conference on Very Large Databases
(VLDB), Edinburgh - Scotland - UK, 7–10 1999.
[36] E. Pacitti, P. Minet, and E. Simon. Replica Consistency in Lazy Master Replicated
Databases. Distributed and Parallel Databases, 9(3):237–267, 2001.
[37] K. Tindell and J. Clark. Holistic schedulability analysis for distributed hard realtime
systems. Microprocess. Microprogram., 40(2-3):117–134, 1994.
[38] Cédric COULON. Thèse de doctorat « Réplication Préventive dans une grappe de bases
de données»
[39] [PGD 11] The PostgreSQL Global Development Group « Documentation PostgreSQL
9.0 ».