Optimisation des requêtes SQL

Bases de Données Distribuées et Optimisation de Requêtes

Les systèmes de bases de données distribuées (SGBDD) et l'optimisation des requêtes sont des piliers fondamentaux de l'informatique moderne, particulièrement avec l'avènement du Big Data et la complexité croissante des applications. Un SGBDD est un ensemble de systèmes de gestion de bases de données (SGBD) s'exécutant sur plusieurs machines, coopérant pour offrir un point d'accès unique à une base de données logiquement unifiée mais physiquement distribuée.

1. Le Big Data : Contexte et Caractéristiques

Le Big Data représente un déluge de données dont la taille dépasse les capacités des outils logiciels conventionnels pour la capture, l'organisation, la gestion et le traitement dans un laps de temps tolérable.

1.1. Les 3 'V' Fondamentaux

Le Big Data est traditionnellement défini par trois caractéristiques principales :

• Volume: La quantité de données générées et stockées. Cela va des mégaoctets (MB) aux gigaoctets (GB), téraoctets (TB), pétaoctets (PB) et au-delà.

• Vélocité: La vitesse à laquelle les données sont générées, collectées et traitées. Elle peut être en temps réel, quasi-réel, périodique ou par lots (batch).

• Variété: La diversité des types et des formats de données. Elles peuvent être structurées (bases de données relationnelles), semi-structurées (XML, JSON) ou non structurées (texte libre, images, vidéos).

1.2. D'autres 'V' additionnels

Des définitions plus récentes incluent d'autres "V" pour affiner la compréhension du Big Data :

• Véracité: La qualité et la fiabilité des données. Les données du Big Data peuvent être incertaines, inexactes ou incomplètes.

• Vocabulaire: La sémantique des termes utilisés dans les documents, nécessitant une compréhension contextuelle.

• Venue (Location): La localisation géographique des données, influençant les latences et les réglementations.

2. Systèmes de Gestion de Bases de Données (SGBD) et Big Data

Le Big Data s'appuie sur une multitude de SGBD. Il existe diverses familles de SGBD, chacune répondant à des besoins spécifiques.

2.1. Familles de SGBD

3 Systèmes Distribués

Un système distribué est une collection d'éléments informatiques autonomes qui apparaissent à leurs utilisateurs comme un système cohérent unique. Comme le disait Leslie Lamport, "un système distribué est un système dans lequel la défaillance d'un ordinateur dont vous ne connaissiez même pas l'existence peut rendre votre propre ordinateur inutilisable".

3.1. Architectures des Systèmes Distribués

Il existe plusieurs architectures fondamentales :

• Shared Everything: Un SGBD s'exécutant sur un nœud unique avec ses propres processeurs, mémoire et disque.

• Shared Memory: Plusieurs CPU partageant la mémoire globale et le disque via un réseau d'interconnexion. Souffre d'une faible évolutivité.

• Shared Disk: Chaque CPU possède sa propre mémoire, mais tous les CPU partagent le même stockage sur disque via un réseau. Évolutivité modérée.

• Shared Nothing: Chaque nœud est autonome avec son propre CPU, mémoire et disque, interconnecté par un réseau. Offre une haute évolutivité. C'est l'approche la plus courante pour les systèmes distribués à grande échelle comme Cassandra ou MongoDB.

3.2. Concepts Clés des Systèmes Distribués

• Passage à l'échelle (Scalability): Capacité du système à gérer une charge croissante.

  • Vertical (Scaling Up): Augmenter les ressources d'une machine unique (mémoire, CPU, disques). Coût matériel élevé, limites physiques.

  • Horizontal (Scaling Out): Distribuer les données et traitements sur un plus grand nombre de machines. Coût matériel inférieur, pratiquement illimité.

  • Sharding (Fragmentation fonctionnelle): Distribution des données, où des parties distinctes d'une table sont stockées sur différentes machines. Par exemple, les utilisateurs sur un nœud, les transactions sur un autre, et les produits sur un troisième.

• Latence: Délai entre le début d'une action et l'observation de son impact. Elle varie considérablement selon l'opération et la localisation.

• Disponibilité (Availability): Proportion de temps pendant lequel un système est opérationnel. Elle est mesurée en "nines" (99%, 99.9%, etc.).

• Tolérance aux pannes (Fault Tolerance): Capacité d'un système à continuer de fonctionner correctement malgré la défaillance de certains de ses composants. La panne d'un composant est la norme, pas l'exception, dans un système distribué.

4. Systèmes de Gestion de Bases de Données Distribuées (SGBDD)

Les SGBDD sont apparus dans les années 80, gérant des OLTP (Online Transaction Processing) pour les transactions et OLAP (Online Analytic Processing) pour la décision.

4.1. SGBDD vs. SGBD Centralisé

• BD Centralisée: Un SGBD sur une machine unique. Vulnérable (SPOF), coûteux à faire évoluer, inadapté aux structures décentralisées.

• BD Non Centralisée (Distribuée): Plusieurs machines, plusieurs SGBD. Coopération entre sites, partage de données, interopérabilité.

4.2. SGBD Parallèle vs. Distribué

4.3. Objectifs et Défis des SGBDD

Les SGBDD visent à améliorer les performances par le parallélisme, la scalabilité, la tolérance aux pannes et la haute disponibilité.

Bénéfices :

• Passage à l'échelle "sans limite" et moins coûteux.

• Tolérance aux pannes et haute disponibilité.

• Réduction du temps de latence.

Défis :

• Le réseau n'est pas fiable.

• Administration et maintenance complexes.

• Distribution optimale des données et des contrôles.

• Prise en compte des pannes.

• Conservation de la cohérence des données.

• Coût de mise en place élevé.

• Absence d'horloge globale.

• Gestion de l'appartenance à un groupe (group membership).

4.4. Principes des BD Distribuées

L'utilisateur doit avoir une vue unique de la base de données, sans se soucier des problèmes de fiabilité, d'optimisation, de transactions réparties ou de localisation. Cela implique une transparence totale via un schéma conceptuel ou une vue globale.

4.5. Avantages et Inconvénients de la Répartition des Données

Avantages :

• Efficacité et fiabilité d'accès aux données partagées.

• Gestion répartie (chaque site maîtrise ses données).

• Fiabilité et disponibilité accrues par duplication des données et maintien de l'exploitation en cas de panne.

Inconvénients :

• Complexité de coordination (développement, bugs, calculs supplémentaires).

• Servitudes système accrues (échanges de messages).

• Récupération plus complexe après pannes.

5. Réplication des Données

La réplication consiste à stocker des copies des données sur plusieurs sites, ce qui augmente la disponibilité et permet le parallélisme des traitements (lectures).

5.1. Avantages et Inconvénients de la Réplication

Avantages :

• Disponibilité accrue des données.

• Parallélisme des traitements (lectures locales).

• Meilleur débit en lecture.

Inconvénients :

• Complexité de la mise à jour : maintenir la cohérence entre toutes les répliques.

• La gestion des mises à jour alourdit le système.

5.2. Approches de Réplication

Lorsque les données changent, maintenir la cohérence est complexe.

Pour simplifier, on peut choisir une copie de référence (primaire).

5.2.1. Réplication avec Leader (Maître-Esclave)

C'est l'approche dominante, notamment pour les SGBDR.

• Un nœud est le leader (maître, master, primaire) et gère toutes les écritures.

• Les autres nœuds sont des followers (esclaves, slaves, secondaires, hot standby) et répliquent les écritures du leader. Les lectures peuvent être distribuées sur les esclaves.

• Scénario typique :

  1. Le client envoie une requête d'écriture au maître.

  2. Le maître enregistre l'écriture localement et l'envoie aux esclaves.

  3. Chaque esclave applique l'écriture à son stockage local.

  4. Le client peut lire depuis le maître ou un des esclaves.

5.2.2. Modes de Synchronisation Maître-Esclave

• Synchrone: Les esclaves sont toujours à jour. Le maître attend la confirmation de l'esclave avant de valider l'écriture.

  • Avantage : Cohérence forte.

  • Inconvénient : Latence élevée ; si un esclave ne répond pas, le maître est bloqué.

  

• Asynchrone: Le maître ne bloque pas pour attendre la confirmation des esclaves.

  • Avantage : Faible latence.

  • Inconvénient : Risque d'inconsistance des données sur les esclaves en cas de panne du maître avant que les écritures ne soient propagées.

• Semi-synchrone: Compromis où au moins un esclave est synchrone et les autres asynchrones. En cas de défaillance de l'esclave synchrone, un esclave asynchrone peut le remplacer.

5.2.3. Gestion des Pannes en Réplication Maître-Esclave

• Ajout d'un esclave: Copie d'un snapshot du leader, puis récupération des écritures manquantes via un log.

• Panne d'un esclave: L'esclave utilise son log de changements pour rattraper les mises à jour manquées une fois redémarré.

• Panne du maître: Plus complexe. Nécessite l'élection d'un nouveau maître parmi les esclaves (ex: algorithmes Zab, Raft, Paxos), puis notification aux clients et aux autres esclaves. Le maître est un Single Point of Failure (SPOF).

5.2.4. Types de Réplication selon le Log

• Réplication basée sur les requêtes: Le maître envoie les requêtes INSERT, UPDATE, DELETE aux esclaves. Simple, mais risque d'incohérence si les requêtes contiennent des opérations non déterministes (date(), valeurs aléatoires).

• Write Ahead Log (WAL) shipping: Utilise le log transactionnel de bas niveau du maître (octets modifiés). Forte dépendance entre le moteur de stockage et la réplication. Utilisé dans PostgreSQL, Oracle.

• Log logique (orienté tuple): Utilise un log distinct du WAL, enregistrant les modifications au niveau des tuples (INSERT: valeurs du tuple, UPDATE: tuple et nouvelles valeurs, DELETE: ID du tuple). Basé sur des triggers.

5.2.5. Gestion des Décalages et Consistance en Réplication Maître-Esclave

Les décalages entre maître et esclaves posent des défis de consistance :

• Lire ses propres écritures: Pour garantir qu'un utilisateur voit toujours ses dernières modifications, on peut forcer la lecture depuis le leader, ou ordonnancer les lectures sur les esclaves en fonction des timestamps des écritures.

• Lectures monotones: Éviter qu'une seconde lecture ne voie une donnée plus ancienne que la première. Solution : Diriger les lectures d'un utilisateur vers la même réplique (via une fonction de hachage sur l'ID utilisateur).

5.2.6. Réplication Multi-Maîtres

Plusieurs maîtres peuvent gérer les écritures, augmentant la disponibilité et la performance en écriture.

• Intéressant lorsque les répliques couvrent plusieurs centres de données (ex: pour la tolérance aux pannes de data centers ou pour réduire la latence des utilisateurs).

  

• Complexité accrue: Conflits potentiels si les mêmes données sont modifiées concurremment sur différents maîtres. Nécessite une gestion des conflits (souvent "last write wins" - LWW, difficile à ordonner sans horloges synchronisées).

• PostgreSQL et MySQL nécessitent des outils externes pour le multi-maître, tandis que d'autres SGBD le supportent nativement mais le déconseillent (ex: MongoDB).

5.2.7. Topologies Multi-Maîtres

Des topologies spécifiques existent pour les systèmes avec plusieurs leaders :

• Circulaire (Anneau): Les nœuds sont connectés en cercle, la réplication se faisant d'un nœud à l'autre.

  

• Étoile: Un nœud central réplique vers tous les autres.

  

• Clique (Maille complète): Tous les nœuds sont connectés à tous les autres.

  

5.2.8. Réplication Sans Leader

Cette approche a réapparu avec les bases de données NoSQL (ex: Dynamo d'Amazon, Riak, Cassandra, Voldemort).

• Le client envoie directement ses écritures à différentes répliques ou via un coordinateur qui n'impose pas d'ordre strict.

  

• Quorum de lectures et écritures: Soit le nombre de répliques, le nombre de répliques confirmant une écriture, et le nombre de répliques confirmant une lecture. Si , on peut lire des données à jour dans la plupart des cas.

• Avec des valeurs plus faibles de , on obtient une latence plus faible et une meilleure disponibilité, mais au détriment de la cohérence.

• La réplication inter-datacenter est souvent asynchrone dans cette approche.

5.3. Fragmentation et Réplication

Les données peuvent être stockées de plusieurs manières dans un SGBDD :

• Duplication Complète: Chaque fragment sur chaque site (réplication totale).

• Duplication Partielle: Chaque fragment sur certains sites.

• Non-duplication: Chaque fragment sur un seul site (pure fragmentation).

Règle empirique : répliquer si le nombre de requêtes en lecture (read-only) est supérieur ou égal à 1. La réplication des mises à jour est plus complexe.

5.4. Réplication dans PostgreSQL

PostgreSQL offre deux types de réplication :

• Réplication physique: Réplique tout sans distinction. Les architectures matérielle et logicielle doivent être identiques.

• Réplication logique: Plus flexible.

  • Peut être partielle (sélection de tables, sous-ensemble de colonnes/lignes).

  • Accepte l'hétérogénéité des architectures.

  • Ne gère que la réplication des données, pas des schémas.

  • Basée sur une approche pub/sub.

  • Côté publication : CREATE PUBLICATION pub1 FOR ALL TABLES;

  • Côté souscription : CREATE SUBSCRIPTION sub1 CONNECTION '...' PUBLICATION pub1;

6. Stockage des données

• Fragmentation :

  • Partitionnées en différents fragments chacun sur site distinct.

• Réplication :

  • Le système maintient différentes copies des données sur les sites.

• Fragmentation et réplication :

  • Combinaison de la réplication et de la fragmentation.

7. Fragmentation et Partitionnement (Sharding)

7.1. Motivations du Partitionnement

Lorsque le volume d'une base de données dépasse la capacité de stockage d'une seule machine ou que le débit des écritures devient trop élevé, il est indispensable de découper la base. Les fragments sont répartis sur différentes machines d'un cluster, généralement selon une architecture sans partage (shared-nothing).

• Passage à l'échelle (Scalability) : C'est la principale motivation. La base est distribuée sur plusieurs disques et les requêtes réparties sur plusieurs processeurs.

• Transparence : La fragmentation doit être invisible pour l'utilisateur. Le SGBD permet l'écriture de requêtes globales sous une forme non fragmentée.

• Exécution des requêtes : Les requêtes ciblant une unique partition s'exécutent indépendamment. Les requêtes complexes nécessitent d'être parallélisées, rendant l'optimisation plus difficile.

7.2. Unités de Fragmentation

La fragmentation s'applique à différentes échelles :

1. Verticale : Partitionnement en ensembles de colonnes (attributs).

2. Horizontale : Partitionnement en ensembles de tuples (lignes).

3. Mixte : Combinaison des approches horizontale et verticale.

7.3. Répartition des Classes (Sous-schémas)

Consiste à disséminer des relations entières sur différents sites.

* Partitionnement : Définition des sous-schémas applicatifs sur les sites.

* Recomposition : Réunion des différents sous-schémas.

* Exemple : Placer la relation client sur le site 1 et la relation document sur le site 2.

8. Stratégies de Fragmentation Horizontale

8.1. Partitionnement Round-Robin

Pour un ensemble de n partitions, le i-ème tuple est systématiquement envoyé vers le disque D i%n. Cela garantit un équilibrage parfait.

8.2. Partitionnement par Gamme (Range)

Consiste à sélectionner un attribut comme clé, puis à attribuer un intervalle continu de valeurs à chaque disque (ex: A-F sur D1, G-Z sur D2). L'équilibrage dépend de la distribution naturelle des données.

8.3. Partitionnement par Hachage (Hash)

On utilise une fonction de hachage dont les résultats vont de 0 à n-1(n nombre de disque). Chaque tuple est affecté au disque correspondant. C'est la méthode par défaut de MongoDB, mais elle peut créer des déséquilibres en cas de biais dans les données.

### 8.4. Hachage Cohérent (Consistent Hashing)

Résout le problème du hachage classique lors de l'ajout ou la suppression d'un nœud.

* Mécanisme : Les nœuds et les clés sont projetés sur un anneau logique. Une clé est affectée au nœud le plus proche dans le sens horaire.

* Impact : Lors d'un changement d'architecture, seule une fraction $\frac{1}{n}$ des clés est déplacée.

* Réplication : Chaque clé est dupliquée sur les $k$ nœuds suivants (utilisé par Cassandra, DynamoDB).

8.5. Partitionnement par Liste

Une liste explicite de valeurs est affectée de manière rigide à un disque donné. Distribution non équilibrée

---

9. Analyse des Types d'Accès

9.1. Impact sur les Requêtes

Il existe trois manières principales d'interroger et de récupérer des données dans une base :

• Balayage complet (Scan) : Lecture de l'intégralité d'une table.

• Requête ponctuelle (Point query) : Récupération de tuples précis à l'aide d'un filtre strict (exemple : WHERE labotit LIKE 'EG %').

• Requête par intervalle (Range query) : Récupération de tous les tuples dont la valeur est comprise dans une plage donnée (exemple : de A à F).

Pour choisir la bonne stratégie de partitionnement, il faut évaluer deux critères : la capacité à équilibrer la charge entre les serveurs et le rapport entre les attributs utilisés dans les filtres et la clé de partitionnement.

L'efficacité de chaque approche de partitionnement varie fortement en fonction de la requête envoyée par l'utilisateur.

1. Le Partitionnement Round-Robin

• Balayage complet : Très efficace. La lecture d'une relation complète est facile car le scan en parallèle sur toutes les partitions offre un excellent équilibrage de charge.

• Requêtes ponctuelles et par intervalle : Inefficaces. Le système manque d'informations sur l'emplacement exact des tuples par rapport à la clé de recherche. Il est donc contraint de lancer une recherche en parallèle sur l'ensemble des partitions, ce qui gaspille les ressources.

2. Le Partitionnement par Hachage (Hash)

• Balayage complet : Peut être efficace, à condition que la fonction de hachage ait permis un bon équilibrage initial des données.

• Requêtes ponctuelles : Très performantes si la clé de recherche correspond exactement à la clé de partitionnement (le système calcule immédiatement le bon serveur). Si la clé diffère, la méthode perd toute son efficacité.

• Requêtes par intervalle : Inefficaces. La fonction de hachage détruit l'ordre des données, éparpillant des valeurs qui se suivent sur des disques différents.

3. Le Partitionnement par Gamme (Range) ou Liste

• Requêtes ponctuelles et par intervalle : Très bien adaptées si l'attribut de partitionnement correspond au filtre de la requête. La demande est envoyée vers un seul serveur ciblé, ce qui laisse les autres serveurs du cluster totalement libres pour traiter d'autres requêtes en parallèle.

• Balayage complet et requêtes peu sélectives : Les performances dépendent de la taille du résultat attendu. Si la requête est sélective (elle ramène peu de résultats), l'approche est très performante. À l'inverse, si elle ramène un énorme volume de données ou demande un scan complet, elle devient moins performante que le Round-Robin ou le Hachage. En effet, tout l'effort de lecture s'effectue sur un disque unique, rendant impossible la parallélisation.

9.2. Asymétrie des Données

Risque de déséquilibre (data skew) créant des points chauds (hot spots) où une machine est surchargée :

1. Liée aux valeurs : Une valeur spécifique apparaît dans une immense majorité des tuples.

2. Liée au partitionnement : Les plages définies sont intrinsèquement inégales.

10. Index Secondaires et Rééquilibrage

10.1. Index Local vs Global

• Local : Chaque partition maintient son propre index. Les requêtes nécessitent d'interroger tout le cluster (scatter/gather).

• Global : L'index est unifié et partitionné indépendamment. Plus rapide en lecture, mais pénalisant en écriture en raison des transactions réseau.

10.2. Rééquilibrage (Rebalancing)

• Sur-partitionnement (Hachage) : Création de nombreuses partitions logiques (ex: $hash(key) \pmod{n \times 10}$). Lors de l'ajout d'une machine, on migre des partitions entières sans recalculer les clés individuelles.

• Dynamique (Gamme) : Si une partition devient trop grosse, elle est scindée (split). Si elle est trop petite, elle est fusionnée.

10.3. Réplication

• Des copies de chaque partition sont stockées sur plusieurs nœuds.

• Un nœud peut stocker plus d'une partition.

• Le système peut fonctionner selon une approche à unique leader (modèle Leader / Follower).

Niveaux de duplication

Il existe trois configurations de duplication pour les fragments :

• Duplication complète : chaque fragment est présent sur chaque site.

• Duplication partielle : chaque fragment est présent sur certains sites.

• Non-duplication : chaque fragment est présent sur un et un seul site.

Réplication efficace quand

---

11. Optimisation des Requêtes Distribuées

11.1. Critères et Parallélisme

L'optimiseur intègre la localisation, les coûts CPU/IO et les coûts de transfert réseau.

1. Parallélisme inter-requête : Exécution simultanée de requêtes différentes pour maximiser le débit et reduire la latence.

2. Parallélisme intra-requête : Découpage d'une même requête sur plusieurs nœuds pour réduire la latence.

### 11.2. Algèbre et Semi-jointure (Semijoin)

Lorsqu'une relation est fragmentée, les filtres sont distribués :

$$\sigma_{pays=fra}(f_A \cup f_B) = \sigma_{pays=fra}(f_A) \cup \sigma_{pays=fra}(f_B)$$

La stratégie du Semijoin réduit le transfert réseau lors des jointures entre deux sites S1 et S2 :

1. Calcul des clés communes : $Temp_1 = \Pi_{R_1 \cap R_2}(r_1)$ sur S1.

2. Envoi de $Temp_1$ vers S2.

3. Filtrage local : $Temp_2 = r_2 \bowtie Temp_1$ sur S2.

4. Rapatriement exclusif des tuples utiles vers S1.

5. Jointure finale sur S1.

### 11.3. Exemple Numérique

Pour un réseau avec 0,5s de latence et 1000 octets/seconde :

* Approche naïve (Message par tuple) : Prend environ 8 minutes (503 secondes).

* Approche optimisée (Semijoin massif) : Prend 1,7 seconde, soit 300 fois plus rapide.

---

12. Transactions Distribuées

12.1. Concepts

Les transactions assurent les propriétés ACID( Atomique execution un bloc, Consistance passe d'un etat coherant un un autre etat coherant, Isolation pas de maj tant que pas commit, Durabilité des modifications sur la BD) . Une transaction globale manipule des données réparties et doit être validée (commit) ou annulée (abort) de manière unanime.

• Transaction Manager (TM) : Gère la concurrence et les logs au niveau local.

• Transaction Coordinator (TC) : demate une txn Orchestre le découpage et la validation globale des txn.

2 type de transaction :

• local : acces donne sur le site de txn

• Globa acces donne situee sur site different

12.2. Validation à Deux Phases (2PC)

Le protocole 2PC garantit l'atomicité et la cohérence des transactions distribuées en séparant l'exécution en deux étapes strictes entre un Coordinateur et plusieurs Participants.

Phase 1 : Préparation (Le vote)

1. Demande : Le coordinateur envoie un message <prepare T> à l'ensemble des participants.

2. Évaluation : Chaque participant exécute la transaction localement (sans la valider) pour s'assurer qu'il n'y a pas de conflit.

3. Réponse : Les participants écrivent leur intention dans leur journal local (log) et répondent au coordinateur par <yes T> ou <no T>.

Décision globale : Le coordinateur ne valide la transaction (Commit) que si 100 % des participants ont répondu "yes". Un seul "no" entraîne l'annulation globale (Abort).

Phase 2 : Application (La décision finale)

1. Ordre : Le coordinateur diffuse la décision finale (<commit T> ou <abort T>) à tous les participants.

2. Exécution : Les participants valident ou annulent les changements, puis libèrent les verrous sur les données.

3. Confirmation : Ils renvoient un accusé de réception (<acknowledge T>) au coordinateur pour clore la transaction.

12.3. Pannes et Blocages

1. Panne d'un Participant (Site)

• Avant le vote : Vu comme un <no> par le Coordinateur (Ci) ➔ Annulation.

• Après le vote : Ci ignore la panne et continue.

• Au redémarrage (analyse du log local) :

  • Log vide ➔ Annule (tombé avant de voter).

  • <commit> ou <abort> ➔ Applique la décision.

  • Uniquement <yes> (Incertitude) ➔ Interroge Ci ou les autres. Si injoignables ➔ Attente.

2. Panne du Coordinateur (Ci) Les sites tentent de déduire la décision finale :

• Si 1 site a <commit> ➔ Tous valident.

• Si 1 site a <abort> ➔ Tous annulent.

• Si 1 site n'a pas de <yes> ➔ Tous annulent.

• Le Blocage (Défaut majeur) : Si tous ont <yes> mais sans décision finale ➔ Système bloqué. Les verrous sont maintenus jusqu'au redémarrage de Ci.

3. Partitionnement Réseau

• Côté Ci : Le protocole continue normalement avec les sites joignables.

• Côté sites isolés : Traité comme une panne de Ci (tentative de décision ou blocage).

4. Alternative : Le 3PC

• Avantage : Élimine le problème de blocage.

• Défauts : Complexe, ajoute une phase, fait chuter les performances (pénalité réseau).

13. Contrôle de la Concurrence Distribuée

13.1. Gestion par Verrous

* Centralisée : Un site gère tout. Simple, mais crée un SPOF.

* Distribuée : Chaque site gère ses verrous. Complexe pour détecter les deadlocks inter-sites.

* Majorité : Nécessite l'accord de la moitié des répliques.

13.2. Horodatage (Timestamping)

Génération de timestamps distribuée en concaténant l'ID du nœud et l'horloge locale, ce qui pose le défi de la synchronisation (NTP).

13.3. Contrôle Optimiste (OCC)

Postule que les conflits sont rares.

1. Lecture : Travail sur copie locale.

2. Validation : Vérification des conflits avant commit.

3. Écriture : Validation ou Rollback/Retry automatique.

13.4. Multiversion (MVCC)

Maintien de plusieurs versions horodatées d'un tuple.

• Les lecteurs voient un instantané cohérent (snapshot).

• Lecteurs et écrivains ne se bloquent jamais mutuellement.

• Nécessite un nettoyage régulier (Garbage Collection).

Pdf tp1

Architecture distribuée (Réplication)

• Replica Set : Un groupe (cluster) de plusieurs serveurs MongoDB qui contiennent tous exactement la même copie de la base de données.

• Architecture Master/Slave : Un mode de fonctionnement où un serveur "chef" (Master) dirige, et des serveurs "esclaves" (Slaves) le copient.

• Nœud Primaire (Primary) : C'est le serveur "Master". C'est le seul autorisé à modifier la base de données (écritures).

• Nœud Secondaire (Secondary) : Ce sont les serveurs "Slaves". Ils copient en permanence le Primaire. On ne peut faire que des lectures dessus.

• Haute disponibilité : Le fait que la base de données reste toujours accessible pour les utilisateurs, même si un des serveurs physiques prend feu ou plante.

• Tolérance aux pannes (Failover) : La capacité du système à détecter la panne du Primaire et à réagir tout seul pour que le système continue de fonctionner.

• Mécanisme d'élection : Le vote automatique fait par les nœuds Secondaires entre eux pour désigner le nouveau Primaire quand l'ancien tombe en panne.

• Synchronisation : La mise à jour continue et ultra-rapide des nœuds Secondaires pour qu'ils aient les mêmes données que le nœud Primaire.

• Préférence de lecture (Read Preference) : Le réglage qui permet d'autoriser un client à aller lire les données sur un nœud Secondaire (pour éviter de surcharger le Primaire).

pdf tp2

Gestion et Topologie du Replica Set

• Ajout à la volée : Intégration de nouveaux nœuds sans arrêter le cluster.

• Réplication en chaîne (Chained Replication / chainingAllowed) : Capacité d'un Secondaire à se synchroniser depuis un autre Secondaire (et non depuis le Primaire) pour économiser la bande passante (syncSourceHost).

Types de Membres Spécifiques

• Membre Caché (Hidden Member) : Invisible pour les applications clientes, ne peut jamais devenir Primaire, mais possède le droit de vote. (Sauvegarde des données , Reporting / Statistique, backup)

• Membre Retardé (Delayed Member) : Un membre caché configuré avec un retard de synchronisation volontaire (utile en cas de suppression accidentelle de données).

• Arbitre (Arbiter) : Un nœud léger qui ne stocke aucune donnée utilisateur. Son unique rôle est de voter lors des élections pour départager les autres nœuds.

Élections et Tolérance aux Pannes

• Règle de la Majorité (N/2 + 1) : Nombre de votes requis pour qu'un nœud soit élu Primaire.

• Intérêt du nombre impair : Permet d'avoir toujours une majorité claire lors d'un vote.

• Split-Brain (Cerveau divisé) : Scénario catastrophique de partition réseau où deux parties isolées du cluster tenteraient d'élire chacune leur propre Primaire (bloqué par la règle de la majorité).

• Limites de vote : Un Replica Set peut contenir jusqu'à 50 nœuds, mais MongoDB limite à 7 le nombre maximum de nœuds votants (pour éviter la lenteur des élections).

Mécanismes Internes de Réplication

• Oplog (Operations Log) : Journal interne qui enregistre toutes les opérations modifiant les données. C'est le moteur de la réplication.

• Capped Collection : Type de collection utilisé par l'Oplog ayant une taille fixe (les anciennes données sont écrasées par les nouvelles quand il est plein).

• Write Concern : Niveau de garantie exigé lors d'une écriture (ex: attendre que l'écriture soit validée par la majorité avant de répondre au client).

pdf tp3

1. Le Sharding (Partitionnement des données)

Le sharding est la solution de MongoDB pour gérer des bases de données géantes. Au lieu de tout stocker sur un seul serveur surpuissant (ce qui a des limites), on "découpe" (fragmente horizontalement) la collection de données pour la répartir sur plusieurs serveurs.

L'architecture d'un cluster shardé repose sur 3 composants indissociables :

1. Les Shards (Serveurs de données) : Ce sont les serveurs physiques qui stockent les morceaux de la base de données. Chaque Shard ne possède qu'une partie des données totales.

2. Les Config Servers (Serveurs de configuration) : C'est le cerveau du cluster. Ils stockent le "plan" (les métadonnées) indiquant exactement sur quel Shard se trouve chaque morceau de donnée.

3. Le Mongos (Routeur) : C'est le point de contact pour l'utilisateur. Il reçoit la requête, demande au Config Server où se trouvent les données, transmet la requête aux bons Shards, fusionne les réponses, et renvoie le résultat à l'utilisateur. Le Mongos ne stocke aucune donnée.

2. Le Mécanisme de Distribution (Comment on découpe ?)

• La Clé de Sharding (Shard Key) : Pour découper les données, MongoDB a besoin d'un critère. L'administrateur choisit un champ spécifique (ex: l'âge, le code postal, ou un identifiant). La valeur de ce champ déterminera sur quel Shard le document sera envoyé.

• Les Chunks (Morceaux) : MongoDB ne répartit pas les documents un par un. Il crée des "blocs" de données contigus appelés chunks (ex: un chunk pour les codes postaux de 75000 à 75020). Par défaut, un chunk fait 64 Mo.

• L'Équilibreur de charge (Load Balancer) : Un processus automatique surveille les Shards. Si un serveur commence à stocker beaucoup plus de chunks que les autres, l'équilibreur va déplacer silencieusement des chunks vers les serveurs moins remplis pour répartir l'effort équitablement.

7. Évaluation et Optimisation des Requêtes

L'évaluation et l'optimisation des requêtes sont cruciales pour les performances des SGBD, surtout dans un contexte distribué.

7.1. Rappels sur le Stockage des Données

• Enregistrement (tuple): Un ensemble de champs formant une ligne dans une table.

• Bloc: Unité de chargement des données en mémoire principale, contenant une entête et plusieurs enregistrements.

• Fichier de données (table): Collection de blocs, organisée de manière séquentielle ou en tas (heap).

7.2. Rappels sur les Index

Les index accélèrent l'accès aux tuples ayant une valeur particulière d'un ou plusieurs attributs (clé de recherche).

Un index est un ensemble de <clé, pointeur>.

7.2.1. Types d'Index

• Dense/Non-dense: Un index dense a une entrée pour chaque enregistrement dans le fichier de données.

• Primaire/Secondaire: Un index primaire est sur la clé primaire de la table.

7.2.2. Structures de Données pour les Index

• Arbres:

  • B+-tree: Stocke les données uniquement dans les feuilles, les nœuds internes contiennent des clés de recherche et des pointeurs vers les nœuds enfants. Très utilisé pour les SGBD relationnels.

    

  • B-tree: Les données peuvent être stockées dans les nœuds internes et les feuilles.

• Tables de hachage (Hash): Distribuent les enregistrements dans des "buckets" via une fonction de hachage. Efficace pour les recherches d'égalité.

  

7.2.3. Avantages et Inconvénients des Index

• Avantage: Évaluation efficace des requêtes sur la clé indexée.

• Inconvénient: Coût de mise à jour de l'index en cas de modifications fréquentes de la table.

7.3. Algèbre Relationnelle et Plans d'Exécution

• SQL / Calcul Relationnel: Langage déclaratif, décrit le résultat souhaité.

• Algèbre Relationnelle: Langage procédural, décrit comment calculer le résultat (combinaison d'opérations sur des ensembles). Elle est à la base de l'optimisation des requêtes SQL.

Une requête SQL peut avoir plusieurs réécritures équivalentes en algèbre relationnelle, chacune pouvant donner lieu à un plan d'exécution différent avec des coûts variés. Par exemple, pour la requête SELECT DISTINCT nom, intitule FROM enseignant NATURAL JOIN enseigne NATURAL JOIN cours WHERE dpt = 'Info';, différentes réécritures sont possibles:

7.4. Analyse des Plans d'Exécution (Query Plan)

Les SGBD utilisent un optimiseur de requêtes pour choisir le plan d'exécution le plus efficace parmi les différentes alternatives. L'analyse d'un query plan (via EXPLAIN dans PostgreSQL) permet de comprendre comment une requête est exécutée et d'identifier les goulots d'étranglement.

1. Les méthodes de lecture (Scans)

C'est comment le moteur va physiquement chercher les lignes.

• Seq Scan (Sequential Scan) : Le balayage "stupide". Il lit toute la table de haut en bas, ligne par ligne.

• Index Scan : Il lit l'index pour trouver l'adresse de la ligne, puis va chercher la ligne complète dans la table.

• Bitmap Index Scan : Il lit l'index, mais au lieu d'aller chercher les lignes tout de suite, il crée une "carte" en mémoire (le bitmap) de tous les blocs physiques de la table qui contiennent des résultats.

• Bitmap Heap Scan : Il prend la "carte" générée par le Bitmap Index Scan et va chercher les vraies lignes sur le disque en optimisant les accès (il lit les blocs dans l'ordre physique pour ne pas faire d'allers-retours inutiles).

• Index Only Scan : Le Saint Graal de la performance. Le moteur ne lit que l'index et ne va même pas vérifier la table. Cela arrive si l'index contient toutes les colonnes demandées dans ton SELECT.

• CTE Scan (Common Table Expression Scan) : C'est l'action de lire les résultats temporaires générés par une clause WITH (une sous-requête nommée).

• Function Scan : Les lignes renvoyées ne viennent pas d'une table, mais d'une fonction PostgreSQL (par exemple generate_series(1, 100)).

• Foreign Scan : Le moteur va chercher des données qui ne sont pas physiquement sur ce serveur, mais sur une base de données distante (via un Foreign Data Wrapper).

2. Les Jointures (Joins)

Comment le moteur relie deux tables entre elles.

• Nested Loop (Boucle imbriquée) : Pour chaque ligne trouvée dans la Table A, il boucle sur la Table B pour chercher une correspondance. Très rapide si la Table A a peu de résultats et que la Table B est indexée.

• Hash Join : Il prend la plus petite des deux tables, la charge entièrement en mémoire vive (RAM) sous forme de dictionnaire (Table de hachage), puis il lit la grosse table et vérifie pour chaque ligne si elle correspond à une entrée du dictionnaire. Très efficace pour les grosses requêtes.

• Hash : C'est l'action préparatoire du Hash Join. C'est le moment où il construit la fameuse table de hachage en mémoire.

• Hash Semi Join : Utilisé pour les clauses EXISTS ou IN. Dès qu'il trouve une correspondance dans la deuxième table, il arrête de chercher pour cette ligne et passe à la suivante.

• Merge Join : Une méthode de jointure très efficace, mais qui exige que les deux tables soient déjà triées sur la colonne de jointure. Le moteur lit les deux listes en parallèle et les assemble un peu comme on ferme une fermeture éclair.

3. Les Conditions et Filtres

• Index Cond (Index Condition) : La condition de ta clause WHERE qui est utilisée pour naviguer à l'intérieur de l'index.

• Recheck Cond : Associé au Bitmap Heap Scan. Si la carte bitmap a manqué de mémoire, elle devient moins précise (elle cible des "zones" au lieu de lignes exactes). Postgres doit donc "re-vérifier" la condition sur les lignes une fois qu'il les a trouvées.

• Hash Cond : La condition exacte de ta jointure (le ON a.id = b.id) utilisée pendant un Hash Join.

• One-Time Filter : Une condition évaluée une seule fois au tout début (ex: WHERE 1 = 0). Si c'est faux, Postgres annule tout le plan et ne fait rien.

4. Sous-requêtes et Opérations d'ensemble

• Append : C'est la colle. Il prend le résultat de plusieurs requêtes et les met bout à bout (utilisé pour les UNION ou si tu lis une table partitionnée).

• SubPlan 1 : L'exécution d'une sous-requête (souvent exécutée pour chaque ligne de la requête principale, ce qui peut être très lent).

• Subquery Scan : Le moteur lit le résultat d'une sous-requête comme si c'était une vraie table.

• HashSetOp Intersect : Implémente l'opérateur INTERSECT en utilisant le système de hachage pour trouver les lignes communes entre deux requêtes.

5. Gestion de la mémoire et des résultats

• Materialize : Il stocke temporairement le résultat d'une opération en mémoire (ou sur disque) pour pouvoir le relire plusieurs fois sans avoir à recalculer. Très utilisé avec les Nested Loops.

• Heap Blocks : Pas une action, mais une métrique. Ça indique combien de blocs de données physiques de la table (Heap) ont été lus sur le disque ou trouvés dans le cache.

• Buckets / Batches : Ce sont les statistiques du Hash Join.

  • Buckets = les "cases" du dictionnaire en mémoire.

  • Batches = si la table était trop grosse pour la RAM, Postgres l'a coupée en "lots" (batches) qu'il a dû écrire sur le disque dur. S'il y a plus de 1 batch, ta requête est ralentie par le disque.

6. Les Tris, Limites et Agrégations

C'est ici que le moteur calcule tes ORDER BY, GROUP BY ou DISTINCT.

• Sort : L'action de trier les données. S'il y a assez de RAM, c'est fait en mémoire (quicksort). Sinon, Postgres crée des fichiers temporaires sur le disque (external merge), ce qui ralentit considérablement la requête.

• Limit : Le moteur arrête simplement de lire et de traiter des lignes dès qu'il a atteint le nombre demandé par ta clause LIMIT.

• Aggregate (HashAggregate / GroupAggregate) : C'est l'action qui calcule les fonctions mathématiques (comme SUM(), COUNT(), AVG()) ou qui regroupe les lignes pour un GROUP BY.

• WindowAgg (Window Aggregate) : Utilisé spécifiquement quand tu fais des calculs analytiques avec la clause OVER() (les fonctions de fenêtrage).

• Unique : Élimine les doublons adjacents pour satisfaire un SELECT DISTINCT. (Nécessite souvent que les données aient été triées juste avant).

7. Divers

• Result : Utilisé quand le moteur n'a même pas besoin de lire une table. Par exemple pour un simple SELECT 2 + 2; ou si un One-Time Filter a déterminé que la requête ne renverra rien de toute façon.

• ModifyTable (Insert / Update / Delete) : C'est le nœud de plus haut niveau quand tu fais une requête d'écriture. Il prend les lignes trouvées par les étapes précédentes et modifie physiquement la table.