These Contrôle de Qualité des Données Répliquées dans un Cluster

Informations

• Publié par: Choud
• Nombre de lectures: 55
• Langue: Français

Extrait

THÈSE
présentéedevant
l’UniversitéPierreetMarieCurie(ParisVI)
pourobtenirlegradede
DOCTEUR DE L’UNIVERSITÉ PIERRE ET MARIE CURIE
Mention INFORMATIQUE
par
CécileLE PAPE
Laboratoired’informatiquedeParis6-EquipeBasedeDonnées
EcoleDoctoraled’Informatique,TélécommunicationsetElectroniquedeParis
ContrôledeQualitédesDonnéesRépliquées
dansunCluster
Soutenuele1erdécembre2005,devantlacommission d’examen
Président Pierre SENS Professeuràl’UniversitéParisVI
Rapporteurs Marc SHAPIRO Directeurderechercheàl’INRIA
Philippe PUCHERAL Professeuràl’UniversitédeVersailles
Examinateurs Michel SCHOLL ProfesseurauCNAM
Invitée Anne DOUCET Professeuràl’UniversitéParisVI
Directeur Patrick VALDURIEZ Directeurderechercheàl’INRIA
Encadrant Stéphane GANÇARSKI MaîtredeConférenceàl’UniversitéParisVILaconnaissance est unarbredeviequi granditàla lumièredesautres.Remerciements
Je tiens tout particulièrement à remercier Stéphane Gançarski, Maître de Conférence à
l’UniversitéParisVI,quiaétéunguideconstant,disponible,patientetefficacetoutaulongde
cesannées.Jeleremercieégalementdesaconfiance,desonsoutiensansfailleetsagentillesse
àtouteépreuve.
Je remerciesincèrement Patrick Valduriez, Directeur de Rerchercheà l’INRIA, de m’avoir
accordé sa confiance depuis le tout début en maîtrise, puis en DEA lorsque ma grossesse a
rendulasituationdélicate.Grâceàlui,j’aibénéficiédeconditionsdetravailexceptionnelleset
d’unsoutienconstantmalgréladistance.
Je remerciePhilippe Pucheral, Professeur à l’Université de Versailles et MarcShapiro, Di-
recteurdeRechercheàl’INRIAd’avoiracceptéd’êtrerapporteursdecettethèseetpourleurs
commentairesinstructifs.
Je remercie Michel Scholl, Professeur au CNAM, d’avoir accepté de participer au jury de
cettethèse,ainsiquedelabienveillanceamicalequ’ilm’atoujoursaccordée.
JeremercieégalementPierreSens,Professeuràl’UniversitédeParisVI,d’avoiracceptéde
participeraujurydecettethèse.
Je remercie le Laboratoire de Paris 6, en particulier l’équipe d’administration et l’équipe
technique,dem’avoiraccueillidansseslocauxetd’avoirrendumonséjouraussiagréable.
Jeremercielesmembresdel’équipe BasedeDonnées duLIP6 qui m’ont accueillien DEA
et au sein de laquelle j’ai trouvé du soutien, des conseils et un cadrede travailexceptionnel :
Anne Doucet, que je remercie également d’avoir accepté de participer au jury de cette thèse,
HubertNaacke,dontladisponibilité,l’expertisetechniqueetlagentillesseenfontunprécieux
collaborateur, ainsi que Bernd Amann, Maha Abdallah, Alda Gançarski, Camélia Constantin
etJulienTanguy.
J’adresse un remerciement tout particulier à Nicolas Lumineau, compagnon de route et
ami,quiapartagétoutesmesjoies,maisaussitousmesdoutes,tousmesmomentsdefatigue,
toutesmesgalères.Monalter-ego,mondouble,monfrère.
Ma gratitude et mes remerciements les plus sincères vont également à Anneli et Bernard,
pourêtrelesamislesplusinconditionnels, lesplusexceptionnels,etbienplusencore.
Jeremercieégalement ma famille de m’avoir permis d’êtrece que je suis, d’oser avoir en-
vie,d’entreprendreetderéussir,grâceàleursoutienconstantetleuraffectionpermanente.
Enfin, mes pensées les plus émues vont, avec une tendresseet une affection sans limite, à
monfiancéFrédéricetàmafilleEline,quidonnentsimplementetentièrementtoutsonsensà
cettethèse.
J’adresseunetoutedernièrepenséeàmon amieStéphanie.Oùquetusois encejour,tues
prèsdemoi...Tabledesmatières
Introduction 3
1 Donnéesrépliquéesetdivergence 9
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Notiondedivergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1 Dimensions deladivergence . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Divergenceetcontrôledeconcurrencelocal. . . . . . . . . . . . . . . . . 11
1.2.3 Divergenceetcontrôledescopies. . . . . . . . . . . . . . . . . . . . . . . 14
1.2.4 Problématiqueducontrôledeladivergence . . . . . . . . . . . . . . . . 17
1.2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3 Préventiondeladivergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.1 Architectureclient/serveurenmodesérialisable . . . . . . . . . . . . . . 21
1.3.2 Méthodesderéplicationsynchrone . . . . . . . . . . . . . . . . . . . . . 23
1.4 Minimisationdeladivergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Propagationaussitôtquepossible . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Propagationpériodique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4.3 Propagationévénementielle . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4.4 Lessystèmescommerciaux . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.5 Contrôledeladivergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.5.1 Mesurebooléenneetvariantes . . . . . . . . . . . . . . . . . . . . . . . . 28
1.5.2 Mesuretemporelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.5.3 Mesuredeversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.5.4 Mesuresnumériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.5.5 Mesuresmixtes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.6 Contrôledeladivergenceetéquilibragedecharge . . . . . . . . . . . . . . . . . 34
1.6.1 Election . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.6.2 Routage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.7 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2 Contrôledequalité 39
2.1 Modèledequalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.1.1 Etatdestransactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.1.2 Ordredeprécédencedestransactions . . . . . . . . . . . . . . . . . . . . 41
2.1.3 Définition delaqualitédesdonnées . . . . . . . . . . . . . . . . . . . . . 42
2.1.4 Etatsd’unedonnée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.1.5 Contratdequalitépourdonnéesrelationnelles . . . . . . . . . . . . . . . 43
2.2 Evaluationetcontrôledelaqualité . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2.1 Graphedeprécédence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
12 Tabledesmatières
2.2.2 Graphed’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3 Architectured’unsystèmedecontrôledelaqualité 55
3.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.1 Présentationgénérale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.2 Contrôledesaccès . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.1.3 Contrôledesnœuds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.1.4 Evaluationdel’étatdelagrappe . . . . . . . . . . . . . . . . . . . . . . . 62
3.1.5 Métabase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2 Techniquesdegestionducontrôledelaqualité . . . . . . . . . . . . . . . . . . . 65
3.2.1 EvaluationduDataSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.2.2 Transcriptionducontratutilisateur . . . . . . . . . . . . . . . . . . . . . 70
3.2.3 Détectiondesconflits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.2.4 Evaluationdesmisesàjourd’unetransaction . . . . . . . . . . . . . . . 72
3.2.5 Routage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.2.6 Stratégiesderafraîchissement . . . . . . . . . . . . . . . . . . . . . . . . . 75
4 Validation:leprototypeREFRESCO 79
4.1 Validationdumodèledequalité . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.1.1 Environnementexpérimental . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.1.2 Paramètres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.1.3 Mesuresdeperformances . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.1.4 Impactduseuildedivergence . . . . . . . . . . . . . . . . . . . . . . . . 81
4.1.5 Impactdelagranularité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.1.6 Impactdunombredenœudsdelagrappe . . . . . . . . . . . . . . . . . 84
4.1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2 Etudedesperformancesdelajournalisationactive . . . . . . . . . . . . . . . . . 85
4.2.1 Environnementexpérimental . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.2.2 Paramètres. . .