Conception de BD réparties et requêtes

Préambule : Exemple Netflix

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 :
    • ti∈ Rj avec j = hash(ti.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\}
    • ti∈Rj 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 Ri
  • S : fragmentation horizontale dérivée → fragments Si
  • 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


 
m2ilc/fouille_dist_2.txt · Dernière modification: 2011/03/11 10:28 par suitable