Notes De Cours Sur Le Stockage De Big Data

Chapitre 1

Contexte de génération

Extensibilité horizontale, extensibilité latérale ; utiliser plus de nœuds pour supporter un plus grand nombre de requêtes.

Extensibilité verticale, extensibilité verticale ; étendre la capacité d’un nœud pour supporter un plus grand nombre de requêtes.

Caractéristiques du Big Data : volume, vitesse, variété, valeur

Les besoins d’extensibilité horizontale, de fiabilité et de disponibilité du système, ainsi que les besoins de cohérence ne peuvent pas être efficacement résolus avec le modèle relationnel traditionnel

Quel type de stockage est nécessaire pour le Big Data

Le système de cluster de stockage de Big Data doit répondre aux exigences suivantes :

1. Pouvoir gérer, ordonner et surveiller de manière unifiée les ressources informatiques et de stockage au sein du cluster
2. Pouvoir stocker de manière dispersée et gérer de manière unifiée les données au sein du cluster
3. Les ordinateurs au sein du cluster peuvent accomplir ensemble une tâche, en collaborant et en équilibrant la charge
4. Lorsqu’un ordinateur du cluster tombe en panne, le cluster peut garantir l’efficacité des fonctions et que les données ne seront pas perdues (tolérance aux pannes de partition)
5. Pouvoir déployer le cluster, l’étendre et remplacer les nœuds défectueux de manière simple (extensibilité)

Classification technique

• Classification par mode de gestion des métadonnées : Stratégie de nœuds pairs, offrant une plus grande disponibilité en l’absence de nœud central. Stratégie de nœud central, offrant une meilleure extensibilité.
• Classification par modèle de données : Bases de données avec différents modèles de données pour différents modèles d’affaires
• Architecture distribuée Partition All - Partitionnement de bases de données et de tables

Partition Engine - Share Nothing

Partition Storage - Share Storage, séparation du calcul et du stockage

NoSQL et NewSQL

NoSQL est une base de données non relationnelle, principalement utilisée pour résoudre les problèmes d’extensibilité de SQL. Elle ne garantit pas les caractéristiques ACID, n’a pas de gestion des transactions, et peut s’étendre horizontalement sans opérations supplémentaires ;

NewSQL est une base de données relationnelle, combinant la capacité de gestion de stockage massif des bases de données NoSQL avec les caractéristiques ACID et la commodité de SQL des bases de données relationnelles.

Chapitre 2

Structure hiérarchique basée sur C/S

AP et DP

AP est un processeur d’application orienté utilisateur, utilisé pour compléter le traitement des données, capable de transmettre les requêtes et les données de l’utilisateur au CM.

DP est un processeur de données, responsable de la gestion des données, similaire à un système de gestion de base de données centralisé, acceptant les commandes et les données transmises par le CM et fournissant un retour.

Changement de fonction de l’AP

Base centralisée - ne stocke pas de données, équivalent à une entrée, l’hôte exécute tous les logiciels

Multi-client/serveur unique - application, service client (requête), communication

Multi-client/multi-serveur - application, service client (gestion de répertoire, gestion de cache, traitement de requête, protocole de soumission), communication

Client léger/serveur - serveur client Server2Server, les fonctions ci-dessus sont transférées au serveur, ne conservant que l’interface SQL et l’interface de programme ; AP est lié au calcul : gestion de répertoire, gestion de cache, traitement de requête, traitement de transaction, gestion des verrous, contrôle d’accès. De plus, le serveur a également des fonctions liées au stockage : relecture des journaux, récupération des pannes, conception des index, stockage physique.

Trois architectures

Compréhension personnelle, la validité ne peut être garantie. Article de référence

1. Discussion sur ces trois architectures distribuées basées sur l’architecture client léger/serveur Server-to-server
2. serveur - moteur de recherche - requête, optimisation, extraction ; contrôle de la concurrence ; soumission de transaction ; engine - partie transactionnelle (pour la récupération, car elle nécessite des journaux, a un état), index, journaux, récupération des pannes, partie du stockage physique
3. Définition des trois architectures
4. Caractéristiques d’extensibilité et de compatibilité de chaque partie

Les trois architectures sont essentiellement des façons différentes pour newSQL de vouloir combiner la forte cohérence et le support des transactions de SQL avec l’extensibilité facile de NoSQL, mais elles se retrouvent dans une compétition de tir à la corde entre extensibilité et compatibilité.

De haut en bas, il s’agit de Partition ALL (partitionnement de bases de données et de tables), Partition Engine (share nothing), Partition Storage (séparation du calcul et du stockage) ; de haut en bas, l’extensibilité diminue, au profit d’une augmentation de la compatibilité écologique. Le partitionnement de bases de données et de tables a une extensibilité exceptionnelle, des performances élevées ; mais le couplage d’affaires est important, nécessitant généralement une conception en fonction du scénario d’affaires, l’utilisateur devant gérer lui-même la stratégie de fragmentation, les transactions distribuées, les requêtes distribuées, avec une faible généralité. Chaque nœud est un DBMS complet. Share Nothing ne fait la fragmentation qu’au niveau du moteur, les nœuds étant relativement indépendants. Par rapport au partitionnement de bases de données et de tables traditionnel, les problèmes de transactions distribuées et de requêtes distribuées sont traités à l’intérieur de la base de données, masquant les détails des transactions distribuées à l’utilisateur, fournissant un service de base de données unifié, simplifiant l’utilisation par l’utilisateur.

Le problème est que la plupart des implémentations de partitionnement de bases de données et de tables masquent également les détails des transactions distribuées en introduisant des middlewares (traitement des données, gestion des données, équilibrage de charge, pilotage de la base de données), utilisant également des protocoles de cohérence tels que Multi Paxos pour garantir la cohérence des répliques, et fournissant également un accès unifié à la base de données à l’utilisateur, ce qui rend l’avantage de la stratégie Partition Engine apparemment pas si grand.

Continuer à déplacer la ligne de démarcation de la fragmentation vers le bas, jusqu’au niveau des systèmes de transaction et d’index. À ce stade, comme la partie 1 conserve un système de transaction complet, elle n’est plus sans état, et des nœuds distincts sont généralement conservés pour traiter les services. Ainsi, la partie 1 conserve principalement la logique liée au calcul, tandis que la partie 2 est responsable du stockage, comme REDO, le nettoyage et la récupération des pannes. Cette structure est donc également appelée architecture de séparation du calcul et du stockage, également connue sous le nom d’architecture Share Storage.

En conservant une couche de calcul complète, les changements que l’utilisateur doit percevoir par rapport à une base de données traditionnelle sont très peu nombreux, permettant une compatibilité écologique maximale. Cependant, comme seule la couche de stockage est fragmentée et dispersée, l’extensibilité est inférieure aux deux solutions mentionnées ci-dessus.

Structure des composants de DDBS

– Fonctionnalités du processeur d’application (AP) :

Interface utilisateur : vérifie l’identité de l’utilisateur, accepte les commandes utilisateur (comme SQL)

Contrôleur de données sémantiques : certaines contraintes (gestion des vues, contrôle de la sécurité, contrôle de l’intégrité sémantique)

Processeur de requêtes globales : traduit les commandes utilisateur en commandes de base de données ; génère un plan de requête global ; collecte les résultats des requêtes locales et les renvoie à l’utilisateur

Moniteur d’exécution global (gestionnaire de transactions global) : ordonne et surveille l’AP et le DP ; garantit la cohérence des données répliquées ; garantit l’atomicité des transactions globales

– Fonctionnalités du processeur de données (DP) :

Processeur de requêtes locales : commandes globales -> commandes locales ; choisit le meilleur chemin d’accès pour exécuter

Gestionnaire de transactions locales : ordonne et exécute les sous-transactions locales

Gestionnaire de planification locale : responsable du contrôle de la concurrence sur le site local

Gestionnaire de récupération locale : maintient la cohérence du site local en cas de panne

Gestionnaire de stockage : accède à la base de données ; contrôle le gestionnaire de cache de la base de données ; renvoie les résultats d’exécution locaux

Structure des modèles de DDBS

• Modèle externe global (GES) : Le modèle externe global est la vue utilisateur globale de la base de données distribuée, représentant l’abstraction la plus élevée de la base de données distribuée pour les utilisateurs.
• Modèle conceptuel global (GCS) : Le modèle conceptuel global est la vue conceptuelle globale, représentant l’abstraction globale de la base de données distribuée, incluant toutes les caractéristiques des données et la structure logique. Le modèle conceptuel global est ensuite mappé aux modèles conceptuels locaux via les modèles de fragmentation et de distribution.
• Le modèle de fragmentation décrit la vue de division logique des données globales. C’est-à-dire que la structure logique des données globales est divisée en structures de données locales selon certaines conditions. Chaque division logique devient un fragment. Dans une base de données relationnelle, une sous-relation d’une relation est appelée un fragment de cette relation.
• Le modèle de distribution décrit la vue de distribution physique des données locales logiques, c’est-à-dire la vue de distribution physique des fragments après division.
• Modèle conceptuel local (LCS) : Le modèle conceptuel local est la vue conceptuelle locale, un sous-ensemble du modèle conceptuel global. Le modèle conceptuel local est utilisé pour décrire la structure logique des données locales sur le site local. Lorsque le modèle de données global et le modèle de données local diffèrent, la conversion du modèle de données est également impliquée.
• Modèle interne local (LIS) : Définit la vue physique locale, décrivant la base de données physique, similaire à la couche interne d’une base de données centralisée.

Transparence des données de DDBS

• Transparence de la fragmentation : La fragmentation divise une relation en plusieurs sous-relations, chaque sous-relation étant appelée un fragment. L’utilisateur n’a pas besoin de se soucier de la propriété des données appartenant à un fragment, ce qui est appelé transparence de la fragmentation. Situé entre le modèle conceptuel global et le modèle de fragmentation.
• Transparence de la distribution : La base de données distribuée prend en charge la redondance contrôlée des données, c’est-à-dire que les données peuvent être stockées de manière répétée sur différents sites. L’utilisateur n’a pas besoin de se soucier du site de stockage de chaque fragment, ce qui est appelé transparence de la distribution. Situé entre le modèle de fragmentation et le modèle de distribution.
• Transparence du mappage local : L’utilisateur n’a pas besoin de se soucier de la forme de stockage locale des données, ce qui est appelé transparence du mappage local. Situé entre le modèle de distribution et le modèle conceptuel local.

1
2
3
4

select . from S --transparence de la fragmentation
select . from S1 & S2 --transparence de la distribution
select . from S1 at site1 --transparence du mappage local
Execute:$SUPIMS($SNO,$FOUND,$SNAME) at L1 --non transparent

MDBS V.S. DDBS 4 points

Système de base de données distribuée : Conçu de manière descendante (top-down), il permet une conception flexible de la fragmentation et de la distribution. Cependant, le système de base de données distribuée a une limitation sur le nombre de composants de base de données, généralement pas plus de quelques dizaines.

Système d’intégration de bases de données multiples : Les données et les bases de données existent déjà, et il suit une approche ascendante (bottom-up) pour intégrer les données sur les sites locaux. Le système d’intégration de données peut étendre le nombre de composants de base de données à des centaines en limitant la capacité de gestion des données (ne supporte que la lecture).

Les deux doivent fournir aux utilisateurs un environnement d’accès aux données unifié, les données étant stockées de manière dispersée. La différence réside dans :

• Le modèle de données est-il préalablement défini ?
• Le SGBD est-il homogène ?
• La stratégie d’optimisation des requêtes est-elle générée automatiquement ?
• Existe-t-il nécessairement des utilisateurs locaux (MDBS oui) ?

Chapitre 3

3.1 Conception de bases de données distribuées (fragmentation, distribution, réplication)

3.1.1 Stratégie et étapes de conception

De haut en bas, analyse des besoins -> conception conceptuelle -> conception de la distribution -> conception physique -> optimisation des performances

3.1.2 Définition et rôle de la fragmentation

Fragmentation : Division logique des données globales.

Distribution : Désignation du site de stockage des fragments, appelée distribution. Lorsque le fragment est stocké sur plus d’un site, cela s’appelle la réplication des données. Si chaque fragment est stocké sur un seul site, cela s’appelle le stockage partitionné.

Rôle de la fragmentation :

• Réduire la quantité de données transmises sur le réseau
• Augmenter la localité du traitement des transactions
• Améliorer l’efficacité des requêtes et la fiabilité du système
• Équilibrer la charge Le processus de fragmentation consiste à diviser logiquement les données globales et à les distribuer physiquement. Les données globales sont définies en fragments par le modèle de fragmentation, et chaque fragment est défini par le modèle de distribution pour être stocké sur différents sites.

Principes de la fragmentation : Complétude (pas de perte de données), Reconstructibilité (pas de perte de relation), Non-intersection (description formelle)

Types de fragmentation : fragmentation horizontale (par tuple), fragmentation verticale (par attribut), fragmentation mixte

3.1.3 Fragmentation horizontale

Fragmentation horizontale : sélection

Exportation : semi-jointure

Conception basée sur les besoins de fragmentation, provenant de facteurs d’application et de facteurs de base de données

Critères de conception : définir un ensemble de prédicats simples avec complétude et minimalité

3.1.4 Fragmentation verticale

Représentation de la fragmentation : opération de projection

Preuve de complétude : opération d’union (attribut)

Preuve de reconstructibilité : opération de jointure

Preuve de non-intersection : opération d’intersection, le résultat n’est pas vide, c’est la clé principale

3.1.5 Méthodes de représentation de la fragmentation

Représentation graphique (tableau) et représentation arborescente

3.1.6 Conception de la distribution

Le processus de mappage des fragments aux sites physiques de stockage est appelé processus de conception de la distribution.

• Distribution non répliquée Si chaque fragment est stocké sur un seul site, cela s’appelle une distribution partitionnée, et la base de données correspondante est appelée base de données entièrement partitionnée.
• Distribution répliquée Si chaque fragment a une réplique sur chaque site, cela s’appelle une distribution entièrement répliquée, et la base de données correspondante est appelée base de données entièrement répliquée. Si chaque fragment n’a des répliques que sur certains sites, cela s’appelle une distribution partiellement répliquée, et la base de données correspondante est appelée base de données partiellement répliquée.

3.1.7 Technologie de réplication des données

Réplication synchrone et asynchrone ; réplication maître-esclave et réplication pair-à-pair ;

3.2 Optimisation des requêtes distribuées

(Reflète les étapes clés, expansion de la fragmentation, etc., ∪ est une opération binaire, cercle vide)

3.2.1 Importance de l’optimisation des requêtes

3.2.2 Processeur de requêtes

3.2.3 Décomposition des requêtes

Basé sur le modèle conceptuel global, décompose la requête calculée en requête algébrique. Obtenez l’arbre de plan de requête logique global. Les cinq étapes suivantes :

1. Normalisation des requêtes (lois de commutation, d’association, de distribution)
2. Analyse syntaxique et sémantique (erreurs syntaxiques, requêtes sans signification, pas de permission, via le graphe de requête)
3. Réduction des requêtes
4. Réécriture des requêtes

3.2.4 Localisation des données

• Décomposez la table globale en utilisant les opérations d’union et de jointure en tables locales
• Dessinez d’abord l’arbre global, optimisez l’arbre global, convertissez-le en arbre de requête de fragment,
• Déplacez immédiatement l’opération de sélection, l’opération de jointure vers le bas, et exécutez ∞ avant ∪ (utilisez la loi de distribution)

3.2.5 Optimisation des requêtes de fragments

3.3 Optimisation de l’accès distribué

3.3.1 Concepts de base

3.3.2 Fondements théoriques de l’optimisation

Base de la relation : Indique le nombre de tuples contenus dans la relation R, noté Card(R)

• Longueur de l’attribut : Indique le nombre d’octets de la valeur définie par l’attribut A, noté Length(A) • Longueur du tuple : Nombre d’octets de chaque tuple dans la relation R, noté Length(R),

Length(R)=∑Length(Ai) • Taille de la relation : Nombre d’octets contenus dans la relation R, noté Size(R) Size(R)=Card(R) Length(R) • Valeur caractéristique de l’attribut : Indique le nombre de valeurs différentes prises par l’attribut A dans la relation R, noté Val(A) • Valeur maximale et minimale de l’attribut A : Noté Max(A) et Min(A)

Opération de sélection : Cardinalité : Card(S)=ρ Card(R)* Calcul de ρ : Considère uniquement le cas d’égalité de l’attribut de sélection A, où A est un attribut de R, X est une constante. Alors $\rho = \frac{1}{Val(R,A)}$

Calcul de Val(S,B) : Lorsque l’attribut B appartient à la condition de sélection, Val(S,B)=1 Lorsque l’attribut B est une clé (clé primaire), Val(S,B)=ρ Val(R,B) Lorsque l’attribut B n’appartient pas au prédicat de sélection, $$Val(S,B)=\begin{cases} Card(S), \quad if \quad Card(S) <= \frac{Val(R,B)}{2} \ \frac{Card(S)+Val(R,B)}{3} \ Val(R,B), \quad if \quad Card(S)>=2Val(R,B) \end{cases}$$

Opération de jointure :

Opération de semi-jointure :

3.3.3 Méthode d’optimisation de la semi-jointure

Il s’agit de voir si, en faisant ce détour, le coût de la semi-jointure est supérieur à celui de la jointure complète.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

Travail 1 Conception de la fragmentation
Il existe un système d'achat de produits, contenant deux relations globales : le tableau des utilisateurs USER(UID, UNAME, ADDRESS, HOBBY, CITY) et le tableau des commandes ORDER(UID, PID, PRICE), UID étant le numéro d'utilisateur, UNAME le nom de l'utilisateur, CITY la ville de résidence. PID est le numéro de produit, PRICE est le prix total de la commande, UID est la clé primaire dans le tableau USER, et la clé étrangère dans le tableau ORDER. Avant de créer la base de données distribuée, les règles de fragmentation sont :
(1) La relation USER est fragmentée verticalement selon le degré de sensibilité des attributs
U1 contient les attributs non sensibles : UID, UNAME, CITY
U2 contient les attributs sensibles : ADDRESS, HOBBY
(2) Tous les attributs non sensibles de USER sont ensuite fragmentés horizontalement selon CITY
U11 : CITY IN { Beijing, Shanghai, Guangzhou, Shenzhen}
U12 : CITY NOT IN { Beijing, Shanghai, Guangzhou, Shenzhen}
(3) La relation ORDER est fragmentée selon la relation de jointure avec USER, obtenant O1 et O2.

Travail 2 Optimisation des requêtes
Requête Q : "Rechercher toutes les commandes des utilisateurs de la ville de "Xuzhou" ayant acheté le produit numéro "P1", obtenir le numéro d'utilisateur, le nom de l'utilisateur, le numéro de produit et le prix total de la commande".
(1) Écrire l'expression algébrique relationnelle de la requête Q et la transformer en requête de fragment
(2) Optimiser l'arbre de requête de fragment

Travail 3 Optimisation de l'accès
Comme le montre l'image ci-dessous

Chapitre 4 HBase

Problèmes de HDFS

1. Ne prend pas en charge la réécriture aléatoire des données
2. HDFS n’a pas de concept de paquet de données
3. HDFS ne peut pas réaliser des opérations rapides pour des fonctions de requête de données courantes telles que le comptage de lignes, le filtrage et le balayage, nécessitant généralement l’utilisation de MapReduce.
4. (L’avantage est le stockage de gros fichiers, les multiples répliques, le découpage automatique)

Caractéristiques de HBase

1. Utilise HDFS pour le stockage sous-jacent, mais la structure des fichiers et les métadonnées sont maintenues par lui-même.
2. Utilise un mode de stockage colonne + paire clé-valeur
3. Peut réaliser une extensibilité horizontale pratique
4. Peut réaliser une fragmentation automatique des données
5. Possède une cohérence stricte de lecture-écriture et un basculement automatique
6. Prend en charge la recherche et le filtrage de texte intégral L’avantage est qu’il est bon pour traiter de grandes quantités de données, avec des performances élevées, une fiabilité élevée, une extensibilité ; le désavantage est qu’il ne prend pas en charge les requêtes associées et l’analyse de tables.

Région

Le serveur de région est un conteneur pour les régions ; une région est une partie des données d’une table, une région équivaut à un fragment de table dans une base de données relationnelle. Une table peut être stockée dans différentes régions. Caractéristiques :

1. Une région ne peut pas traverser plusieurs serveurs, un serveur de région peut avoir une ou plusieurs régions ;
2. Lorsque la quantité de données augmente, la région se divise ;
3. Pour équilibrer la charge, la région peut migrer ;
4. Toutes les opérations de stockage de données dans une région sont réalisées en appelant l’interface client de HDFS.

Les données de lignes différentes d’une même table peuvent être stockées sur des serveurs différents, les données de lignes identiques d’une même table peuvent également être stockées sur des serveurs différents. Comment comprendre cette phrase ? (Je ne comprends pas, je pense que la deuxième partie est problématique.) Un serveur est une structure de stockage de région, mais stocker une région ne signifie pas stocker une table ; chaque région contient plusieurs instances de magasin, chaque magasin correspondant à une famille de colonnes, stockée comme un objet de famille de colonnes, pas nécessairement une table, mais peut être un fragment de tables différentes.

Journal d’écriture anticipée WAL : Écrit d’abord dans WAL (un serveur de région n’a qu’un WAL), puis chargé dans memStore ;

Chaque région interne a plusieurs instances de magasin, chaque magasin correspondant à une famille de colonnes ; chaque magasin a une instance de memStore, lorsque memStore est plein, HDFS génère un nouveau fichier HFile (stocké avec un arbre LSM, sera trié rapidement avant l’écriture finale pour réaliser un stockage séquentiel des données écrites de manière aléatoire, améliorant l’efficacité de la lecture) ; memStore peut être considéré comme un cache en mémoire, que ce soit pour la lecture ou l’écriture, il passe d’abord par memStore.

Opérations de modification

• HBase ajoute une cellule, ajoutant une donnée dans HDFS
• HBase modifie une cellule, ajoutant une donnée dans HDFS, mais avec un numéro de version supérieur à celui précédent
• HBase supprime une cellule, ajoutant une donnée dans HDFS, mais cette donnée n’a pas de valeur, de type Delete, c’est-à-dire un marqueur de tombe (Tombstone), lors de la fusion des fichiers HFile, ces enregistrements seront réellement supprimés.

Processus de lecture-écriture

Article de référence : Processus de lecture-écriture HBase Zookeeper(ROOT)->RegionServer(META)->Region->memStore

1. Accès client, le nœud /hbase/meta-region-server de zookeeper recherche quelle région de serveur contient la table hbase : meta

2. Le client se connecte au serveur de région contenant la table hbase : meta. La table hbase : meta stocke les informations de plage de clés de ligne de toutes les régions, à travers cette table, on peut trouver la région où se trouve la clé de ligne demandée et le serveur de région où se trouve cette région

3. Le client, sur le serveur de région correspondant, recherche d’abord dans MemStore, puis dans HFile pour trouver les informations nécessaires.

4. Après le premier accès, le client met en cache les informations meta (BlockCache), lors de la prochaine opération, il recherche directement les informations meta dans BlockCache.

5. Accès client, le nœud /hbase/meta-region-server de zookeeper recherche quelle région de serveur contient la table hbase : meta

6. Le client se connecte au serveur de région contenant la table hbase : meta. La table hbase : meta stocke les informations de plage de clés de ligne de toutes les régions, à travers cette table, on peut trouver la région où se trouve la clé de ligne demandée et le serveur de région où se trouve cette région

7. Le client, sur le serveur de région correspondant, écrit les données à la fois dans Hlog et memstore

8. Lorsque memstore atteint le seuil, les données sont écrites dans un fichier HFIle, lors de la compactation, formant progressivement des fichiers HFIle de plus en plus grands, déclenchant une division, divisant le fichier HFIle actuel en deux, ce qui équivaut à diviser une grande région en deux régions

9. Si les données dans MemStore sont perdues, elles peuvent être récupérées à partir de HLog, lorsque plusieurs fichiers HFIle atteignent une certaine taille, une opération de compactation est déclenchée, fusionnant en un fichier HFIle, ici, la fusion des versions et la suppression des données sont effectuées

Conception de Rowkey

• Trois principes : principe de longueur (le plus court possible), principe de dispersion (distribution équilibrée des données), principe d’unicité
• Salage, en attribuant un nombre aléatoire au début de rowkey ; le préfixe aléatoire peut les répartir dans différentes régions.
• Prépartition, résolvant les problèmes de points chauds et de division-fusion causés par la division automatique des régions (peut également réserver de l’espace pour l’extension) ; par exemple, générer un nombre aléatoire de 0 à 499, en définissant les plages de régions comme 0-50, 50-100, etc.
• Hachage, résolvant le besoin de stocker des données concentrées pour un même utilisateur le même jour ; en passant un paramètre (comme uid, date) dans un hachage, le résultat modulo 500, le reste ajouté au début, peut être combiné avec la prépartition pour répartir uniformément les données sur les serveurs de région tout en répondant aux besoins.
• Inversion, sacrifiant l’ordre de rowkey pour la randomisation ; résolvant les problèmes de points chauds avec des débuts fixes et des fins variables, comme les numéros de téléphone ; pour le temps (Long.MAX_VALUE - timestamp), cela peut répondre au besoin de priorité des enregistrements récents.

Chapitre 5 Structure d’index de Big Data

Les trois moteurs de stockage de données de base sont le hachage (recherche aléatoire efficace), l’arbre B (recherche de plage efficace), et l’arbre LSM (Log-Structured Merge Tree). Une famille de colonnes HBase est un arbre LSM, la partie mémoire est une liste chaînée, le stockage externe choisit un filtre de Bloom pour une identification rapide.

Liste chaînée

La liste chaînée (Skip List) est une structure de données en mémoire qui permet d’implémenter efficacement l’insertion, la suppression et la recherche, avec une complexité de ces opérations de $O(logN)$.

Scénarios d’application : Écriture rapide, faible coût de mise à jour, prise en charge de la requête de plage ; la différence avec l’arbre B+ est le faible coût de mise à jour, ce qui le rend adapté aux scénarios de Big Data.

Construction de la liste chaînée :

1. Donnez une liste chaînée ordonnée.
2. Choisissez les éléments maximum et minimum de la liste chaînée, puis sélectionnez aléatoirement certains éléments parmi les autres éléments selon un certain algorithme (aléatoire), et formez ces éléments en une liste chaînée ordonnée. Cette nouvelle liste chaînée est appelée une couche, la liste chaînée d’origine est appelée sa couche inférieure.
3. Pour chaque élément nouvellement sélectionné, ajoutez un champ de pointeur, ce pointeur pointe vers l’élément de la couche inférieure dont la valeur est égale à la sienne. Le pointeur Top pointe vers le premier élément de cette couche.
4. Répétez les étapes 2 et 3 jusqu’à ce qu’il ne soit plus possible de sélectionner des éléments autres que les éléments maximum et minimum.

Processus d’insertion dans la liste chaînée :

Lors de l’insertion dans la liste chaînée, le nouveau nœud doit générer un index dans la couche supérieure avec une certaine probabilité. Trouvez le nœud prédécesseur de l’élément à insérer -> insérez -> générez aléatoirement une valeur de hauteur -> modifiez l’index selon la valeur de hauteur

Arbre LSM

Pourquoi dit-on que l’arbre LSM est une structure de données conviviale pour l’écriture ? L’arbre LSM est plus convivial pour l’écriture, les opérations d’écriture sont toutes des écritures séquentielles, utilisant les avantages de HDFS.

1. Écriture séquentielle : Les opérations d’écriture de l’arbre LSM sont effectuées de manière séquentielle. Cela est dû au fait que les nouvelles données sont ajoutées aux journaux séquentiels (SSTables) sur le disque, plutôt que directement dans les fichiers de données d’origine. Par rapport aux opérations d’écriture aléatoire traditionnelles, l’écriture séquentielle a un coût moindre, ce qui peut considérablement améliorer les performances d’écriture.

2. Fusion différée : Les opérations de fusion de l’arbre LSM sont généralement différées, c’est-à-dire que la fusion entre plusieurs SSTables n’est pas effectuée immédiatement après chaque opération d’écriture. Cela permet d’éviter des opérations de fusion fréquentes pendant le processus d’écriture, réduisant ainsi le retard et le coût de l’écriture.

3. Cache mémoire : L’arbre LSM maintient généralement une zone de cache de données en mémoire pour stocker les données récemment écrites. Même lors de la vidange (flush) sur le disque, une nouvelle memstore est ouverte en mémoire pour servir les nouvelles écritures. Cela permet d’éviter l’accès au disque à chaque écriture, améliorant ainsi les performances d’écriture. En même temps, les données du cache mémoire peuvent également être régulièrement rafraîchies dans les SSTables sur le disque pour garantir la persistance des données.

Scénarios d’application : Écriture séquentielle à haut débit, recherche aléatoire, extensibilité (l’arbre LSM permet la partition des données).

Compaction : Entoure globalement les données avec des valeurs de clé identiques, choisit la version appropriée pour l’utilisateur.

Il existe principalement deux types :

1. Compactage majeur : Ne doit pas être utilisé fréquemment Avantage : Après la fusion, il n’y a qu’un seul fichier, les performances de lecture sont maximales Inconvénient : La fusion de tous les fichiers prend beaucoup de temps, consommant beaucoup de bande passante.
2. Compactage mineur : Avantage : Opération de compactage locale, moins d’E/S, réduit le nombre de fichiers, améliore les performances de lecture. Inconvénient : Opération globale, ne peut pas être complétée pendant le processus de fusion.

Filtre de Bloom

Type de problème résolu : Exclure efficacement certaines données qui ne sont certainement pas dans la base de données ; Principe de réalisation : Réalisé à l’aide d’un tableau et de plusieurs fonctions de hachage, pour chaque donnée, effectuer un hachage k fois, chaque résultat de hachage correspondant à une position dans le tableau est mis à 1 ; si lors de la recherche d’une donnée, toutes les positions indiquées par les résultats de hachage sont à 1, alors cette donnée peut être dans la base de données, sinon elle n’est certainement pas dans la base de données.

Pourquoi dit-on que HBase est une base de données distribuée “écriture séquentielle, recherche aléatoire” ? Recherche aléatoire : Bien que HBase utilise la structure d’index de l’arbre LSM, les opérations de requête de HBase ne sont pas basées sur l’arbre LSM, mais sur les clés de ligne (row key) dans les tables HBase. Organisation des informations de métadonnées par région.

Chapitre 6 Cohérence

Transactions distribuées

Une transaction est une séquence d’opérations dans une base de données, qui doit être effectuée entièrement ou pas du tout ; elle se compose de trois parties : marqueur de début, opérations, marqueur de fin (commit ou abort) ; selon la structure, elle peut être divisée en transactions plates (autonomes, indépendantes) et transactions imbriquées (l’exécution d’une transaction inclut une autre transaction, sous-fils extérieurs).

Caractéristiques des transactions imbriquées

• Dépendance de soumission : La soumission d’une sous-transaction doit attendre la soumission de la transaction parente ;
• Dépendance d’abandon : Si la transaction parente est abandonnée, la sous-transaction doit être abandonnée ;

Cohérence des transactions distribuées

Ce problème est dû à la réplication des données dans la base de données distribuée (qui apporte également fiabilité et disponibilité) ; Trois niveaux :

• Cohérence forte : Mise à jour immédiatement accessible
• Cohérence finale : Accessible après un certain temps
• Cohérence faible : Non accessible (commentaires d’achat en ligne, publicités)

CAP

Un système distribué ne peut pas satisfaire simultanément la cohérence, la disponibilité et la tolérance aux partitions, au maximum deux ;

• La cohérence est la caractéristique de maintenir la cohérence des données entre plusieurs répliques ;
• La disponibilité est le fait que le service fourni est toujours disponible - retourne un résultat dans un temps limité ;
• La tolérance aux partitions, en cas de partitionnement du réseau, garantit toujours la disponibilité et la cohérence du service ; Par exemple, écrire simultanément dans les bases de données de Pékin et de Guangzhou avec succès avant de retourner un succès et fournir un service dégradé (non accessible) en cas de panne réseau, satisfait CP.

BASE

Bascially Available, Soft State, Eventually consistent ; est le résultat du compromis entre disponibilité et cohérence dans CAP ;

Permet de perdre une partie de la disponibilité en cas de panne ; l’état doux signifie qu’il permet aux données d’exister dans un état intermédiaire incohérent, estimant que cela n’affecte pas la disponibilité ; toutes les répliques de données peuvent finalement atteindre un état cohérent après un certain temps ;

En général, la théorie BASE est orientée vers les systèmes distribués à grande échelle, hautement disponibles et extensibles, et est à l’opposé des caractéristiques ACID des transactions traditionnelles, elle est complètement différente du modèle de cohérence forte d’ACID, mais obtient la disponibilité en sacrifiant la cohérence forte et permet aux données d’être incohérentes pendant un certain temps, mais atteignent finalement un état cohérent.

Caractéristiques ACID de HBase (à comprendre)

Atomicité : Ne garantit que l’atomicité de WAL ; Cohérence : Cohérence forte ;

2PC (point clé)

Les transactions globales dans la base de données distribuée sont décomposées en sous-transactions exécutées sur chaque site. Ce n’est que lorsque toutes les sous-transactions sur chaque site sont correctement exécutées que la transaction globale peut être soumise. Tant qu’une sous-transaction ne peut pas être soumise, la transaction globale doit être abandonnée, et ensuite toutes les sous-transactions doivent également être abandonnées. Par conséquent, la soumission correcte de toutes les sous-transactions est la condition préalable à la soumission des transactions distribuées.

Processus d’exécution

Phase de décision : Le coordinateur envoie la commande de pré-soumission (prepare), puis attend la réponse des participants. Si tous les participants retournent “prêt à soumettre (ready)”, alors le coordinateur prend la décision de soumettre ; si au moins un participant retourne “prêt à abandonner”, alors le coordinateur prend la décision d’abandonner.

Phase d’exécution : Le coordinateur envoie la décision prise lors de la phase de décision aux participants. Si le coordinateur envoie la commande “soumettre” (Commit) à chaque participant, chaque participant exécute la soumission ; si le coordinateur envoie la commande “abandonner” (Abort) à chaque participant, chaque participant exécute l’abandon, annulant les modifications apportées à la base de données. Que ce soit “soumettre” ou “abandonner”, chaque participant, après avoir terminé l’exécution, doit retourner une réponse “confirmation” (Ack) au coordinateur, informant que l’exécution est terminée.

Problèmes existants

Blocage synchrone, problème de point unique, incohérence des données, trop conservateur

En cas de panne du coordinateur, les participants occupent des ressources mais ne peuvent pas exécuter la transaction, entrant dans un état de blocage ; le protocole de soumission en trois phases peut être utilisé pour l’éviter, et si déjà bloqué, le protocole de terminaison peut être utilisé pour récupérer.

Étape 1 : Choisissez un participant PT comme nouveau coordinateur.

Étape 2 : PT envoie la commande “accéder à l’état” à tous les participants, chaque participant retourne son état actuel.

Étape 3 : PT prend une décision en fonction de l’état actuel de chaque participant :

1. Si certains participants sont dans l’état “initial”, et d’autres dans l’état “prêt”, alors PT envoie la commande d’abandon ;
2. Si tous les participants sont dans l’état “prêt”, alors PT envoie la commande de soumission ;
3. Si au moins un participant est dans l’état “soumis”, alors PT envoie la commande de soumission ;
4. Si au moins un participant est dans l’état “abandonné”, alors PT envoie la commande d’abandon ;

Paxos

Prepare->Accept->Learn Proposer, Accepter, Apprenant

Chapitre 7 Contrôle de la concurrence

Objectif

Le principal objectif du contrôle de la concurrence est de garantir l’isolement des transactions, assurant finalement la cohérence des données ; résoudre les problèmes de perte de modification, de lecture non répétable, de lecture de données sales causés par la concurrence ; le contrôle de la concurrence est l’utilisation de méthodes correctes pour ordonner les séquences d’opérations concurrentes, éviter l’incohérence des données ; garantir qu’une transaction s’exécute sans être perturbée par d’autres transactions, garantissant la sérialisabilité des transactions concurrentes.

Sérialisabilité

Si la dernière opération d’une transaction est avant une autre transaction, ou vice versa, alors c’est un ordonnancement sériel. Critère d’équivalence : Ordre des opérations conflictuelles identique

Sérialisabilité : Équivalent à un ordonnancement sériel Sérialisabilité des transactions distribuées : n transactions dans une séquence concurrente sur m sites sont notées E ; Lorsque l’ordonnancement local de chaque site est sérialisable et dans la séquence totale, s’il y a $T_{i}<T_{j}$, dans chaque ordonnancement local, il doit également y avoir cette relation.

1
2
3
4
5

Supposons que les éléments de données a, b soient stockés sur le site S1, x, y soient stockés sur le site S2. Il y a des transactions distribuées T1 et T2, déterminez si chaque exécution ci-dessous est localement sérialisable et globalement sérialisable, expliquez respectivement les raisons.
1. Exécution 1 : Sur le site S1 R1(a) R2(a) W2(b) W1(a),
		Sur le site S2 R1(x) W1(x) R2(y) W2(x),
2. Exécution 2 : Sur le site S1 R1(a) R2(a) W1(a) W2(b)
		Sur le site S2 W2(x) R1(x) R2(y) W1(x).

Contrôle de la concurrence distribuée

Le contrôle de la concurrence dans les bases de données distribuées est le processus d’utilisation de certaines techniques pour contrôler l’accès concurrent dans un système de base de données distribuée, afin de garantir la cohérence et l’intégrité des données tout en satisfaisant les besoins d’accès concurrent des utilisateurs. Il résout principalement les problèmes suivants :

1. Problème de cohérence des données : Dans un environnement distribué, les données peuvent être dispersées sur plusieurs nœuds, il est donc nécessaire de prendre des mesures pour garantir la cohérence des données entre plusieurs nœuds, évitant les conflits et les incohérences de données.

2. Problème de contrôle de la concurrence : Plusieurs utilisateurs peuvent effectuer simultanément des opérations de lecture et d’écriture sur la même donnée, il est donc nécessaire d’adopter des stratégies de contrôle de la concurrence pour garantir la précision et l’intégrité des données, tout en maximisant la capacité de traitement concurrent du système.

Trois types typiques de verrouillage distribué

Méthode de base de données (MySQL) : Utiliser une table comme verrou, verrouiller en insérant un enregistrement avec l’ID de ressource comme clé primaire, déverrouiller en supprimant ;

Verrouillage distribué Redis : setnx, setnx est l’abréviation de set if not exists ; si la clé n’existe pas, la valeur de la clé est définie sur la valeur ; lorsque la clé existe, aucune opération n’est effectuée. Déverrouiller del key ;

Verrouillage distribué Zookeeper : Créer un répertoire pour la gestion des verrous, verrouiller en créant un nœud séquentiel temporaire dans ce répertoire, si le numéro de séquence est le plus petit, alors obtenir le verrou, sinon écouter le répertoire en attente ; déverrouiller en supprimant le nœud ;

Comparaison :

• Du point de vue de la facilité de compréhension (du plus bas au plus élevé) base de données > cache > Zookeeper
• Du point de vue des performances (du plus élevé au plus bas) cache > Zookeeper >= base de données
• Du point de vue de la fiabilité (du plus élevé au plus bas) Zookeeper > cache > base de données