Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Syst` emes et algorithmes r´ epartis Donn´ ees r´ eparties Philippe Qu´ einnec,

Syst` emes et algorithmes r´ epartis Donn´ ees r´ eparties Philippe Qu´ einnec, G´ erard Padiou D´ epartement Informatique et Math´ ematiques Appliqu´ ees ENSEEIHT 29 aoˆ ut 2017 Syst` emes et algorithmes r´ epartis – VI 1 / 68 Principes Coh´ erence Mise en œuvre Premi` ere partie R´ eplication de donn´ ees Syst` emes et algorithmes r´ epartis – VI 2 / 68 Principes Coh´ erence Mise en œuvre plan 1 Principes 2 Coh´ erence Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles 3 Mise en œuvre Placement des copies Propagation des mises ` a jour Protocoles de coh´ erence Syst` emes et algorithmes r´ epartis – VI 3 / 68 Principes Coh´ erence Mise en œuvre Plan 1 Principes 2 Coh´ erence Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles 3 Mise en œuvre Placement des copies Propagation des mises ` a jour Protocoles de coh´ erence Syst` emes et algorithmes r´ epartis – VI 4 / 68 Principes Coh´ erence Mise en œuvre R´ eplication de donn´ ees R´ eplication Placement de plusieurs exemplaires d’une mˆ eme donn´ ee sur diﬀ´ erents sites. Int´ erˆ et de la r´ eplication Favorise les acc` es locaux : performance Tol´ erance aux pannes (copies multiples) R´ epartition de charge Mode d´ econnect´ e envisageable en coh´ erence ` a terme Syst` emes et algorithmes r´ epartis – VI 5 / 68 Principes Coh´ erence Mise en œuvre Principe g´ en´ eral Principe : fournir des objets partag´ es par couplage dans les espaces d’adressage de structures d’ex´ ecution (couplage virtuel) r´ eparties Partage par copie locale (eﬃcacit´ e) Programmation simple (acc` es local) Le syst` eme charge ´ eventuellement les donn´ ees ` a la demande Le syst` eme assure la coh´ erence des donn´ ees partag´ ees Syst` emes et algorithmes r´ epartis – VI 6 / 68 Principes Coh´ erence Mise en œuvre R´ eplication optimiste / pessimiste R´ eplication optimiste Autoriser l’acc` es ` a une copie sans synchronisation a priori avec les autres copies Modiﬁcations propag´ ees en arri` ere plan Conﬂits suppos´ es peu nombreux, et r´ esolus quand ils sont d´ etect´ es R´ eplication pessimiste Garantit l’absence de conﬂits M´ ecanisme bloquant de pr´ evention Where a pessimistic algorithm waits, an optimistic one speculates. Syst` emes et algorithmes r´ epartis – VI 7 / 68 Principes Coh´ erence Mise en œuvre R´ eplication et r´ epartition des donn´ ees Deux sujets : Une mˆ eme donn´ ee, r´ epliqu´ ee sur plusieurs sites ⇒mˆ emes valeurs ? Plusieurs donn´ ees, sur des sites diﬀ´ erents ⇒l’ensemble est-il coh´ erent ? Mais en fait, c’est le mˆ eme probl` eme ! P1 w(x)0 P2 w(x)1 r(x)0 P1 w(x)1 P2 w(y)1 r(x)0 r(y)0 wi(x)b = ´ ecriture, sur le site i, de la variable x avec la valeur b Syst` emes et algorithmes r´ epartis – VI 8 / 68 Principes Coh´ erence Mise en œuvre Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles Plan 1 Principes 2 Coh´ erence Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles 3 Mise en œuvre Placement des copies Propagation des mises ` a jour Protocoles de coh´ erence Syst` emes et algorithmes r´ epartis – VI 9 / 68 Principes Coh´ erence Mise en œuvre Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles Coh´ erence D´ eﬁnition Coh´ erence : relation que gardent entre elles les diﬀ´ erentes copies des donn´ ees Coh´ erence stricte, lin´ earisabilit´ e, coh´ erence s´ equentielle Coh´ erences faibles (weak consistency) coh´ erence ` a la sortie (release consistency) coh´ erence ` a l’entr´ ee (entry consistency) Coh´ erences non s´ equentielles coh´ erence causale coh´ erence ` a terme (eventual consistency) Syst` emes et algorithmes r´ epartis – VI 10 / 68 Principes Coh´ erence Mise en œuvre Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles Coh´ erence stricte Coh´ erence stricte Toute lecture sur un ´ el´ ement X renvoie une valeur correspondant ` a l’´ ecriture la plus r´ ecente sur X. Mod` ele id´ eal Diﬃcile ` a mettre en œuvre Synchronisation des horloges (diﬃcile d’avoir un r´ ef´ erentiel de temps absolu) Temps de communication (temps de propagation des mises ` a jour) Op´ erations instantan´ ees ⇒approximation de ce mod` ele par des mod` eles moins contraignants Syst` emes et algorithmes r´ epartis – VI 11 / 68 Principes Coh´ erence Mise en œuvre Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles Lin´ earisabilit´ e D´ eﬁnition Le r´ esultat d’une ex´ ecution parall` ele est le mˆ eme que celui d’une ex´ ecution s´ equentielle qui respecte l’enchaˆ ınement des op´ erations. Toutes les op´ erations sont ex´ ecut´ ees selon une certaine s´ equence S (comme en centralis´ e) Si deux op´ erations (lecture ou ´ ecriture) sont telles que la premi` ere ﬁnit avant que la deuxi` eme ne commence, alors elles ﬁgurent dans cet ordre dans S. La coh´ erence interne des donn´ ees est respect´ ee dans S (apr` es une ´ ecriture et jusqu’` a la prochaine, la lecture d´ elivre la valeur ´ ecrite) Note : le point 2 n´ ecessite un ordre total sur les dates de d´ ebut/ﬁn, par exemple le temps absolu. Syst` emes et algorithmes r´ epartis – VI 12 / 68 Principes Coh´ erence Mise en œuvre Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles Coh´ erence stricte vs lin´ earisabilit´ e P1 w(x)a P2 w(x)b P4 P3 r(x)? r(x)? S´ equences valides pour la lin´ earisabilit´ e : w1(x)a · w2(x)b · r3(x)b · r4(x)b (= stricte sur les d´ ebuts) w1(x)a · r3(x)a · w2(x)b · r4(x)b (= stricte sur les ﬁns) w2(x)b · w1(x)a · r3(x)a · r4(x)a S´ equences invalides pour la lin´ earisabilit´ e : w2(x)b · r3(x)b · w1(x)a · r4(x)a (d´ ebut r3 post´ erieur ` a ﬁn w1) w2(x)b · r4(x)b · w1(x)a · r3(x)a (d´ ebut r4 post´ erieur ` a ﬁn w1 / r3) Syst` emes et algorithmes r´ epartis – VI 13 / 68 Principes Coh´ erence Mise en œuvre Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles Coh´ erence s´ equentielle D´ eﬁnition Le r´ esultat d’une ex´ ecution parall` ele est le mˆ eme que celui d’une ex´ ecution s´ equentielle qui respecte l’ordre partiel de chacun des processeurs. Toutes les op´ erations sont ex´ ecut´ ees selon une certaine s´ equence S (comme en centralis´ e) Les op´ erations ex´ ecut´ ees par tout processus P ﬁgurent dans S dans le mˆ eme ordre que dans P La coh´ erence interne des donn´ ees est respect´ ee dans S (apr` es une ´ ecriture et jusqu’` a la prochaine, la lecture d´ elivre la valeur ´ ecrite) Remarque : on ne contraint pas l’ordre des op´ erations dans des processus diﬀ´ erents. Syst` emes et algorithmes r´ epartis – VI 14 / 68 Principes Coh´ erence Mise en œuvre Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles Lin´ earisabilit´ e/coh´ erence s´ equentielle/non s´ equentielle Lin´ earisable P1 w(x)a P2 w(x)b P4 r(x)a r(x)b P3 r(x)a r(x)b S = w1(x)a · r3(x)a · r4(x)a · w2(x)b · r4(x)b · r3(x)b Coh´ erence s´ equentielle P1 w(x)a P2 w(x)b P4 r(x)a r(x)b P3 r(x)a r(x)b S = w1(x)a · r3(x)a · r4(x)a · w2(x)b · r3(x)b · r4(x)b Coh´ erence non s´ equentielle P1 w(x)a P2 w(x)b P4 r(x)a r(x)b P3 r(x)a r(x)b Syst` emes et algorithmes r´ epartis – VI 15 / 68 Principes Coh´ erence Mise en œuvre Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles Coh´ erence s´ equentielle Les processeurs doivent s’accorder sur l’ordre des acc` es un acc` es en ´ ecriture est termin´ e si une lecture ` a la mˆ eme adresse rend la valeur ´ ecrite (quelque soit le processeur) chaque ´ ecriture doit ˆ etre termin´ ee pour continuer l’ex´ ecution (sinon deux ´ ecritures peuvent s’inverser) Dans la pratique, algorithme d’ordonnancement global diﬀusion des modiﬁcations ` a tous les sites (ordre total) ou un serveur n’autorisant qu’une seule copie en ´ ecriture (par unit´ e) lourd et ineﬃcace : r + w ≥t, o` u r est la dur´ ee d’une lecture, w d’une ´ ecriture, et t est le temps minimal de transfert d’un message mais assez intuitif Syst` emes et algorithmes r´ epartis – VI 16 / 68 Principes Coh´ erence Mise en œuvre Coh´ erence s´ equentielle Coh´ erence et synchronisation Coh´ erences non s´ equentielles Coh´ erence et synchronisation La pr´ esence de code de synchronisation (p.e. exclusion mutuelle ou verrous) simpliﬁe la coh´ erence n´ ecessaire : Coh´ erence uploads/s3/ cours-6-donnees-reparties 1 .pdf