====== Conception de BD réparties et requêtes ====== > [[fouille_dist_tp|]] ===== Préambule : Exemple Netflix ===== * [[http://www.scribd.com/doc/40225102/Netflix%E2%80%99s-Transition-to-High-Availability-Storage-Systems|]] -- [[fouille_dist_fiche|fiche de lecture]] * Lecture complémentaire : * Brewer's 2000 Talk : {{:m2ilc:podc-keynote.pdf|}} * Gilbert and Lynch's proof : {{:m2ilc:10.1.1.20.1495.pdf|}} Netflix : utilisation de S3 en high availability * avantage et inconvénients * application de recommandation ^ recommandation : | analyser les notes des utilisateurs sur les filmes qu'ils ont vu -> prédire les filmes pour lesquels ils donneraient de bonnes notes (0 à 5). | triplet : [utilisateur, filme, note (,date) ] * matrice de notes filmes x utilisateurs * histogramme du nombre de notes dans le temps * on scinde les notes en deux parties chronologiques : de début jusqu'à 2008, puis 2009 à ... et prend la première partie pour définir le modèle de recommandation. * On valide la qualité de la recommandation avec la suite des données. * Ils ont fait un concours (Netflix prize) pour la production d'un algorithme performant. | => c'est énorme, beaucoup de calculs ^ => c'est extrêmement lent. | On veut mettre à jour continuellement. | Oracle ne marchait plus. Ils ont essayé S3. ===== Approche Décomposition ===== ==== Migration vers un BDR ==== * Décomposition en BD locales * pour la durabilité, confidentialité d'une partie des données (banques, etc.), démarche couteuse qui doit se mériter * Intégration logique des BD locales existantes * services de mash-up, par exemple * pas le sujet du jour aujourd'hui === Conception d'un BDR par décomposition === On veut des ~~morceaux~~ fragments disjoints. Puis on les alloue aux différents sites, avec un peu de redondance si utile. === Objectifs de la décomposition === * fragmentation * trois types : horizontale, verticale, mixte * performances en favorisant les accès locaux * équilibrer la charge de travail entre les sites * Duplication (réplication) * favoriser les accès locaux * augmenter la disponibilité des données ===== Fragmentation ===== ==== Fragmentation Correcte ==== * Complète : chaque élément de R doit se trouver dans un fragment * Reconstructible : on doit pouvoir recomposer R à partir de ses fragments * Disjointe : chaque élément de R ne doit pas être dupliqué === Fragmentation horizontale === * Round-robin : construire **m** lots en affectant ligne i à lot j = i mod m + 1. Utile pour des lectures séquentielles parallèles, guère autrement. * Hashage sur attribut //A// : * t_i∈ R_j avec j = hash(t_i.A) * sélection (A=v): ''select * from R where hashkey = hash(A)'' * équi-jointure (A=B) : si A et B sont traités avec la même fonction de hashage : ''select * from R,S where R.A = S.B'' * Par intervalle : * Fragmenter le domaine de l'attribut A en **m** intervalles * Vecteur \left\{a_1,\ldots ,a_{m-1}\right\} * t_i∈R_j avec a_{j-1} \leq T_i .A \lt a_j * sélection ("A between x and y") : ''select * from R where 10 ≤ R.A < 100'' On se rapproche à des fragmentation qui ressemble aux requêtes. === Fragmentation Horizontale par sélection === | nclient | nom | ville | ^ C1 ^ Dupont ^ Paris ^ | C2 | Martin | Lyon | ^ C3 ^ Martin ^ Paris ^ | C4 | Smith | Lille | ''create table client1 as select * from client where ville = 'Paris'; '' | nclient | nom | ville | ^ C1 ^ Dupont ^ Paris ^ ^ C3 ^ Martin ^ Paris ^ ''create table client2 as select * from client where ville != 'Paris' ;'' | nclient | nom | ville | | C2 | Martin | Lyon | | C4 | Smith | Lille | Une partie où ''ville = Paris'' et l'autre avec ''ville != Paris''. On peut reconstituer la table initiale par union ''create view client as select * from client1 union select * from client2;'' === Fragmentation selon n prédicats === FIXME voir slide ==== Fragmentation horizontale dérivée ==== Utilisation d'une clè étrangère: ''create table cde1 as select cde.* from cde, client1 where cde.client = client1.nclient'' ''create table cde2 as select cde.* from cde, client2 where cde.client = client2.nclient'' Propriétés de la fragmentation horizontale dérivée FIXME : recopier formules de slide 13 * R : fragmentation horizontale -> fragments R_i * S : fragmentation horizontale dérivée -> fragments S_i * complète * disjointe * reconstructible * => contrainte d'intégrité référentielle ==== Fragmentation Verticale ==== * exemple : ''sdss sky server'' * Fragments définis par projection * ''cde1 = cde(ncde, nclient)'' * ''cde2 = cde(ncde, produit, qté)'' * Reconstruction === Propriétés === FIXME : copier de slide 15 === Matrice d'affinité des attributs === ===== Allocation des Fragments ===== ===== Fragmentation des Requêtes ===== ==== Evaluation de Requêtes Réparties ==== Un moteur de requête analyse la fragmentation par rapport au schéma de fragmentation, et génère des requêtes sur fragments. Puis, il fait une optimisation avec le schéma d'allocation. === Exemple d'évaluation simple === | ''select A from R where B=b'' | ^ fragmentation : R = R1 ∪ R2 ^ | ''select A from R1 where B=b union select A from R2 where B=b'' | ^ Optimisation : ^ | R1 = R1@Site1 \\ R2=R2@Site2 \\ R2=R2@Site3 | ^ Réécriture | mettre la requete sous forme d'un arbre algébrique (feuille = relation, noeud = op. relationnel | ^ Reconstruction | remplacer chaque feuille par le programme de reconstruction de la relation globale | ^ Transformation | appliquer des techniques de réduction pour éliminer les opérations inutiles | ^ Notations utilisées | S : select \\ J : join \\ P : project | === Reconstruction === FIXME voir slide 26 === Réduction pour la fragmentation horizontale === __Règle :__ éliminer l'accès aux fragments inutiles. Exemple : * Client1 : Client where ville ='Paris' * Client2 : Client where ville != 'Paris' * ''select * from Client where ville='Lyon' '' * => inutile de consulter ''Client1'' car ''Lyon'' n'est jamais ''Paris'' === Réduction pour la Fragmentation Verticale === __Règle :__ éliminer l'accès aux relations de base qui n'ont pas d'attributs utiles pour le résultat final * Cde1 : Cde(ncode, nclient) * Cde2 : Cde(ncode, produit, qt2) * ''select nclient from Cde'' * On a besoin des deux attributs de Cde1, et que l'attribut ncde de Cde2 pour la jointure * Or Pncde(Cde1) = Pncde(Cde2) donc la jointure est inutile === Réduction pour la framgentation horizontale dérivée === __Règle__ distribuer les jointures par rapport aux unions et appliquer les réduciton pour la fragmentation horizontale ^ Exemple ^ | FIXME : slides 28-31 ===== Optimisation des Requêtes =====